Основные методы математического программирования

Задачи оптимального планирования, связанные с отысканием оптимума заданной целевой функции (линейной формы) при наличии ограничений в виде линейных уравнений или линейных неравенств относятся к задачам линейного программирования.

• 1) Линейное программирование — наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:
  • § математические модели очень большого числа экономических задач линейны относительно искомых переменных;
  • § эти типы задач в настоящее время наиболее изучены;
  • § для них разработаны специальные конечные методы, с помощью которых эти задачи решаются, и соответствующие стандартные программы для их решения на ЭВМ;
  • § многие задачи линейного программирования, будучи решенными, нашли уже сейчас широкое практическое применение в народном хозяйстве;
  • § некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования[18].

Итак, линейное программирование — это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием.

Необходимым условием постановки задачи линейного программирования являются ограничения на наличие ресурсов, величину спроса, производственную мощность предприятия и другие производственные факторы.

Сущность линейного программирования состоит в нахождении точек наибольшего или наименьшего значения некоторой функции при определенном наборе ограничений, налагаемых на аргументы и образующих систему ограничений, которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений переменных (аргументов функции F), которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция F, максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции F, называется оптимальным планом задачи.

Система ограничений, определяющая множество планов, диктуется условиями производства. Задачей линейного программирования (ЗЛП) является выбор из множества допустимых планов наиболее выгодного (оптимального).

Составление математической модели задачи линейного программирования включает:

a) Выбор переменных. Переменными задачи называются величины которые полностью характеризуют экономический процесс, описанный в задачи. Обычно записываются в виде вектора X = () Причём).

b) Составляют системы ограничений. Система ограничений — это совокупность уравнений и неравенств, которым удовлетворяют переменные задачи и которая следует из ограниченности экономических условий задачи.

c) Выбор целевой функции. Целевая функция — это функция Z (X) которая характеризует качество выполнения задачи, экстремум которой надо найти [4, 12 с].

В общем случае задача линейного программирования может быть записана в таком виде:

Z (X) = (max, min) (1).

Данная запись означает следующее: найти экстремум целевой функции (1) и соответствующие ему переменные X=(X₁, X₂,…, X_n) при условии, что эти переменные удовлетворяют системе ограничений (2) и условиям неотрицательности (3).

Допустимым решением задачи линейного программирования называется любой набор значений переменных удовлетворяющий системе ограничений и условной неотрицательности.

Множество допустимых решений образует область допустимых решений задачи (ОДР).

Оптимальным решением называется допустимое решение задачи, при котором целевая функция достигает экстремума [16].

2) Нелинейное программирование — это раздел математического программирования, изучающий задачи, где требуется определить значение некоторых параметров, при которых заданные функции не превосходят фиксированных величин, а некоторая выделенная, так называемая целевая функция достигает глобального минимума (максимума). При этом в отличие от линейного программирования, рассматриваемые функции не обязательно являются линейными.

Возникновение нелинейного программирования связано с тем, что предположение о линейной зависимости показателей рассматриваемого процесса от планируемых параметров при исследовании многих практических вопросов, в том числе экономических, оказывается слишком грубым.

Пусть f (x₁, х₂, …, х_n), g₁(x₁, x₂,…, x_n), g₂(x₁, x₂,…, x_n),…g_m(x_1,x₂,…, x_n) — нелинейные функции. Основная задача нелинейного программирования может быть сформирована следующим образом: требуется найти n-мерный вектор (x₁, x₂,…, x_n), удовлетворяющий условиям:

x_j 0, j = 1, 2, …, n; (4).

g_i () R 0, i= 1, 2,…, m,.

здесь R — отношения вида (?, ?,).

и доставляющий глобальный максимум (минимум) целевой функции f (x), то есть:

f (x) extr (5).

Определение 1. Множество точек, удовлетворяющих ограничениям (4) называется допустимым множеством задачи или допустимым планом.

Определение 2. Допустимая точка, в которой целевая функция (5) достигает максимума или минимума, называется оптимальным решением или оптимальным планом.

Нелинейное программирование охватывает столь широкий класс задач математического программирования, что эффективные универсальные численные методы их решения до настоящего времени не созданы. В первую очередь это связано с тем, что в задачах нелинейного программирования, как правило, существуют такие допустимые наборы параметров (удовлетворяющие условиям (4)), которые являются наилучшими среди достаточно близких к ним допустимых наборов, но которые, тем не менее, не являются оптимальными, то есть доставляющими искомый экстремум целевой функции. Задачи такого типа называются многоэкстремальными.

Эффективные численные методы разработаны лишь для отдельных классов задач нелинейного программирования, включающих задачи, про которые известно, что они не являются многоэкстремальными.

Для решения разных задач нелинейного программирования, отличающихся видом целевой функции и системы ограничений, разработаны специальные методы решения. К основным из них относятся:

• § метод множителей Лагранжа;
• § выпуклое программирование;
• § квадратичное программирование;
• § сепарабельное программирование [12, 45с.].
• 3) Динамическое программирование — это вычислительный метод для решения задач определенной структуры. Возникло и сформировалось в 1950;1953 гг. благодаря работам Р. Беллмана над динамическими задачами управления запасами. В упрощенной формулировке динамическое программирование представляет собой направленный последовательный перебор вариантов, который обязательно приводит к глобальному максимуму.

Основные необходимые свойства задач, к которым возможно применить этот принцип:

• § Задача должна допускать интерпретацию как n-шаговый процесс принятия решений.
• § Задача должна быть определена для любого числа шагов и иметь структуру, не зависящую от их числа.
• § При рассмотрении k-шаговой задачи должно быть задано некоторое множество параметров, описывающих состояние системы, от которых зависят оптимальные значения переменных. Причем это множество не должно изменяться при увеличении числа шагов.
• § Выбор решения (управления) на k-м шаге не должен оказывать влияния на предыдущие решения, кроме необходимого пересчета переменных.

Задача о выборе траектории, задача последовательного принятия решения, задача об использовании рабочей силы, задача управления запасами — классические задачи динамического программирования.

При постановке задач динамического программирования следует руководствоваться следующими принципами:

• 1. Выбрать параметры (фазовые координаты), характеризующие состояние S управляемой системы перед каждым шагом.
• 2. Расчленить операцию на этапы (шаги).
• 3. Выяснить набор шаговых управлений x_i для каждого шага и налагаемые на них ограничения.
• 4. Определить какой выигрыш приносит на i-ом шаге управление x_i, если перед этим система была в состоянии S, т. е. записать «функцию выигрыша»:

).

5. Определить, как изменяется состояние S' системы S под влиянием управление x_i на i-ом шаге: оно переходит в новое состояние:

6. Записать основное рекуррентное уравнение динамического программирования, выражающее условный оптимальный выигрыш W_i(S) (начиная с i-го шага и до конца) через уже известную функцию W_i+1(S):

Этому выигрышу соответствует условное оптимальное управление на i-м шаге x_i(S) (причем в уже известную функцию W_i+1(S) надо вместо S подставить измененное состояние .

7. Произвести условную оптимизацию последнего (m-го) шага, задаваясь гаммой состояний S, из которых можно за один шаг дойти до конечного состояния, вычисляя для каждого из них условный оптимальный выигрыш по формуле:

8. Произвести условную оптимизацию (m-1)-го, (m-2)-го и т. д. шагов по формуле (6.2), полагая в ней i=(m-1),(m-2),…, и для каждого из шагов указать условное оптимальное управление x_i(S), при котором максимум достигается.

Заметим, что если состояние системы в начальный момент известно, то на первом шаге варьировать состояние системы не нужно — прямо находим оптимальный выигрыш для данного начального состояния S₀. Это и есть оптимальный выигрыш за всю операцию.

).

9. Произвести безусловную оптимизацию управления, «читая» соответствующие рекомендации на каждом шаге. Взять найденное оптимальное управление на первом шаге изменить состояние системы по формуле (6.1); для вновь найденного состояния найти оптимальное управление на втором шаге х2* и т. д. до конца.

Данные этапы рассматривались для аддитивных задач, в которых выигрыш за всю операцию равен сумме выигрышей на отдельных шагах. Метод динамического программирования применим также и к задачам с так называемым «мультипликативным» критерием, имеющим вид произведения:

(если только выигрыши w_i положительны). Эти задачи решаются точно так же, как задачи с аддитивным критерием, с той единственной разницей, что в основном уравнении (6.2) вместо знака «плюс» ставится знак «умножения»:

Таким образом, в данной главе была выявлена природа математического программирования и рассмотрены его основные методы. В следующей главе будет рассмотрено практическое применение одного из этих методов [6, 366с.].