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

Среди универсальных методов решения задач линейного программирования наиболее распространен симплексный метод (или симплекс-метод), разработанный американским ученым Дж. Данцигом. Суть этого метода заключается в том, что вначале получают допустимый вариант, удовлетворяющий всем ограничениям, но необязательно оптимальный (так называемое начальное опорное решение); оптимальность достигается последовательным улучшением исходного варианта за определенное число этапов (итераций). Нахождение начального опорного решения и переход к следующему опорному решению проводятся на основе применения метода Жордана-Гаусса для системы линейных уравнений в канонической форме, в которой должна быть предварительно записана исходная задача линейного программирования (ЗЛП); направление перехода от одного опорного решения к другому выбирается при этом на основе критерия оптимальности (целевой функции) исходной задачи.

Симплекс-метод основан на следующих свойствах ЗЛП:

1. Не существует локального экстремума, отличного от глобального. Другими словами, если экстремум есть, то он единственный.

2. Множество всех планов задачи линейного программирования выпукло.

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

4. Каждой угловой точке многогранника решений отвечает опорный план ЗЛП.

Рассмотрим две разновидности симплексного метода: симплекс-метод с естественным базисом и симплекс-метод с искусственным базисом (или М-метод).

Симплекс-метод с естественным базисом. Для применения этого метода ЗЛП должна быть сформулирована в канонической форме, причем матрица системы уравнений должна содержать единичную подматрицу размерностью m * m. В этом случае очевиден начальный опорный план (неотрицательное базисное решение). Для определенности предположим, что первые t векторов матрицы системы составляют единичную матрицу. Тогда очевиден первоначальный опорный план: (,,.,,0,.,0). Проверка на оптимальность опорного плана проходит с помощью критерия оптимальности, переход к другому опорному плану - с помощью преобразований Жордана-Гаусса и с использованием критерия оптимальности. Полученный опорный план снова проверяется на оптимальность и т.д. Процесс заканчивается за конечное число шагов, причем на последнем шаге либо выявляется неразрешимость задачи (конечного оптимума нет), либо получаются оптимальный опорный план и соответствующее ему оптимальное значение целевой функции. [1, 156-157]

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

Теорема 1. Если для некоторого вектора, не входящего в базис, выполняется условие

- , где , j=

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

а) если все координаты вектора, подлежащего вводу в базис, не положительны, то ЗЛП не имеет решения;

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

Теорема 2. Если для всех векторов выполняется условие - 0, то полученный план является оптимальным.

На основании признака оптимальности в базис вводится вектор, давший минимальную отрицательную величину симплекс-разности:

- = min ( - )

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

Q= =;

Строка , называется направляющей, столбец и элемент - направляющими (последний называют также разрешающим элементом).

Элементы вводимой строки, соответствующей направляющей строке, в новой симплекс-таблице вычисляются по формулам

= , j=

а элементы любой другой i-й строки пересчитываются по формулам:

, i=; j=

Значения базисных переменных нового опорного плана (показатели графы "план") рассчитываются по формулам:

для i=r, = , i= для ir.

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

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

Для использования приведенной выше процедуры симплекс - метода к минимизации линейной формы f () следует искать максимум функции () = - f (), затем полученный максимум взять с противоположным знаком. Это и будет искомый минимум исходной ЗЛП. Рассмотрим алгоритмы симплекс-метода на конкретной задаче.

Пример 1. Для производства продукции типа П₁ и П₂ предприятие использует два вида сырья: С₁ и С₂. Данные об условиях приведены в табл.1.

Таблица 1

Составить план производства по критерию "максимум прибыли".

Решение. Обозначим объем производства продукции П₁ через , продукции П2 -через . С учетом этих обозначений математическая модель задачи имеет вид:

max f () =2+3+0+0

B

+++=

или

++=150,0, j= .

Задача обладает исходным опорным планом (0,0,300,150), и ее можно решить симплекс-методом; решение ведется в симплекс-таблицах (табл. 2).

В исходной симплекс-таблице строка оценок = - определяется по приведенной выше формуле

= - = 0

= - = 0

Исходный опорный план (0,0,300,150) не является оптимальным, так как среди оценок имеются отрицательные. Переход к новому опорному плану осуществим, введя в базис вектор , имеющий минимальную отрицательную оценку. Определяем вектор, выходящий из базиса: Q = min (, ) = 100, т.е. вектор Аз следует вывести из базиса. Главным направляющим элементом является = 3 (выделен рамочкой). Переход к следующей симплекс-таблице осуществляем с помощью преобразований Жордана-Гаусса.

Второй опорный план (0,100, 0,50) не оптимальный; переход к следующему опорному плану осуществим, вводя в базис вектор и выводя вектор . В результате получаем оптимальный план (75,75,0,0), т.е. предприятие получит максимум прибыли в размере 375,0 тыс. руб., если выпустит 75 единиц продукции первого вида и 75 единиц продукции второго вида.

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

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

В полученной задаче первоначальный опорный план очевиден. При применении к этой задаче симплекс-метода оценки теперь будут зависеть от "буквы М". Для сравнения оценок нужно помнить, что М - достаточно большое положительное число, поэтому из базиса будут выводиться в первую очередь искусственные переменные.

В процессе решения М-задачи следует вычеркивать в симплекс-таблице искусственные векторы по мере их выхода из базиса. Если все искусственные векторы вышли из базиса, то получаем исходную задачу. Если оптимальное решение М-задачи содержит искусственные векторы или М-задача неразрешима, то исходная задача также неразрешима.

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

Пример 2. Найти максимум целевой функции: max f () = З+ 2+ при условиях

2+ = 8, + + = 6, 0, 0, 0.

Решение. Матрица условий содержит только один единичный вектор, добавим еще один искусственный вектор (искусственную неотрицательную переменную в первое ограничение):

= .

Получим следующую М-задачу: найти максимум целевой функции max f () = З+ 2+ - при условиях

2+ = 8, + + = 6, 0, 0, 0, 0.

М-задачу решаем симплекс-методом. Начальный опорный план (0,0,6,8), решение проводим в симплекс-таблицах (табл.3).

В начальной таблице наименьшее соответствует вектору - он вводится в базис, а искусственный вектор из базиса выводится, так как ему отвечает наименьшее Q. Столбец, соответствующий , из дальнейших симплексных таблиц вычеркивается.

Полученный новый опорный план является опорным планом исходной задачи. Для него все 0, поэтому он является и оптимальным. Таким образом получен оптимальный план исходной задачи (4,0,2), и максимальное значение целевой функции f () = 14.

Рассмотрим основные понятия и выводы специального раздела линейного программирования - теорию двойственности. Любую задачу линейного программирования можно записать следующим образом:

В этой главе для большей наглядности используются записи типа , эквивалентные записям .

С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной; первоначальная задача называется исходной или прямой.

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

Хорошо разработанный математический аппарат линейного программирования позволяет не только получать с помощью эффективных вычислительных процедур оптимальный план, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, двойственной к исходной ЗЛП. Переменные двойственной задачи ; называют объективно обусловленными оценками, или двойственными оценками. Модель двойственной задачи имеет вид:

Каждая из задач двойственной пары фактически является самостоятельной задачей линейного программирования и может быть решена независимо от другой. Однако при определении симплексным методом оптимального плана одной из задач находится решение и другой задачи.

Двойственная задача по отношению к исходной составляется согласно следующим правилам:

1) целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи - на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид , а в задаче на минимум - вид ;

2) матрица

составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица

в двойственной задаче получаются друг из друга транспонированием;

3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи - числу переменных в исходной задаче;

4) коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи - коэффициенты при неизвестных в целевой функции исходной задачи;

5) каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничению, записанному в виде неравенства , соответствует переменная, связанная условием неотрицательности. Если функциональное ограничение исходной задачи является равенством, то соответствующая переменная двойственной задачи может принимать как положительные, так и отрицательные значения.

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

Первая теорема двойственности. Для взаимодвойственных ЗЛП имеет место один из взаимоисключающих случаев:

1. В прямой и двойственной задачах имеются оптимальные решения, при этом значения целевых функций на оптимальных решениях совпадают:

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

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

4. Обе из рассматриваемых задач имеют пустые допустимые множества.

Вторая теорема двойственности (теорема о дополняющей нежесткости). Пусть - допустимое решение прямой задачи, - допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соответствующих взаимодвойственных задач, необходимо и достаточно, чтобы выполнялись следующие соотношения [2, 189-197]:

2. Практическая часть. Решение задач

Решите графическим методом типовую задачу оптимизации. Осуществите проверку правильности решения с помощью средств MS Excel (надстройка Поиск решения).

Условие: Фирма выпускает два вида комплексных удобрений для газонов в упаковке - обычное и улучшенное. Обычное удобрение стоит 3 ден. ед. /уп. и включает 3 кг азотных, 4 кг фосфорных и 1 кг калийных удобрений. Улучшенное удобрение стоит 4 ден. ед. /уп. и включает 2 кг азотных, 6 кг фосфорных и 3 кг калийных удобрений. Для подкормки некоторого газона требуется по меньшей мере 10 кг азотных, 20 кг фосфорных и 7 кг калийных удобрений. Определите, сколько и каких удобрений нужно купить, чтобы обеспечить эффективное питание растений и минимизировать стоимость покупки. Постройте экономико-математическую модель задачи, дайте необходимые комментарии к ее элементам и получите решение графическим методом. Что произойдет, если решать задачу на максимум, и почему?

Решение. Обозначим за Х1 количество обычных наборов удобрений, за Х2 - улучшенных. Ограничения:

3x1 + 2x2 10 (азотные удобрения)

4x1 + 6x2 20 (фосфорные удобрения)

1xl + 3x2 7 (калийные удобрения)

Целевая функция (общие расходы):