Математическая экономика

По (2.46) и (2.47) составляем начальную симплекс-таблицу (табл. 2.15), которая после преобразований сводится к конечной табл. 2.17.

Из нее видно, что оптимальное решение ПЗ образуют x*2 = 6, x1* = 2, причем ~y = −46 , следовательно y = 46. Для получения оптимального решения ДЗ выделяем базисные переменные в конечной таблице (это x2 и x1 ) и за-

Затем выделяем базисные переменные в начальной таблице – это x3 и x4 и записываем матрицу из соответствующих им столбцов конечной таблицы:

т.е. u1* =1 и u*2 = 4 .

Связь между решениями задач, образующих двойственную пару, по-

зволяет использовать для решения данной конкретной задачи ЛП переход

к двойственной для нее задаче. При этом вычисления, необходимые для решения ДЗ, могут оказаться проще, чем для ПЗ. Отметим, что трудоем-

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

51

Пример. Необходимо найти значения переменных u1, u2 , удовлетво-

ряющих условиям

при которых ЦФ z = 2u1 +5u2 принимает наименьшее значение.

Решение. Данная задача является двойственной по отношению к задаче об отыскании переменных x1, x2 , x3, x4 , удовлетворяющих условиям

Ее решение симплекс-методом представлено в табл. 2.18 – 2.20.

52

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

В заключение отметим, что существует довольно интересная с практической точки зрения экономическая интерпретация двойственности в задачах ЛП. С ней можно ознакомиться, например, в [19, 20, 32].

§ 2.6. Целочисленные задачи линейного программирования

Рассмотрим задачу ЛП, в которой переменные xi должны удовле-

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

[32].

1.Решается симплекс-методом поставленная задача без учета требования целочисленности (так называемая задача с ослабленными ограничениями).

2.Анализируются значения переменных в найденном решении. Если все они оказались целыми, то решение данной ЦЗЛП найдено, иначе нужно перейти к следующей операции.

3.Составляется дополнительное условие-ограничение, добавление которого к имеющейся системе ограничений было бы эквивалентно отсечению той части ОДР, в которой находится полученное неподходящее решение и не содержится ни одной точки с целочисленными коэффициентами.

4.Решается полученная задача с дополнительным ограничением, после чего осуществляется переход к п. 2.

Рассмотрим вопрос о том, как следует формировать указанное в п. 3 дополнительное ограничение. Выделим в симплекс-таблице строку, соот-

ветствующую базисной переменной xi , для которой свободный член βi оказался дробным. Представим его в виде βi =[βi ] +{βi}, где [βi ] – наибольшее целое число, не превышающее βi , а {βi} =βi −[βi ] – дробная часть числа (0 ≤{βi} <1).

Аналогично представим все коэффициенты при свободных переменных в рассматриваемой строке: αi =[αi ] +{αi}.

53

Тогда в соответствии с [32] дополнительное ограничение можно записать в виде

где суммирование осуществляется по всем свободным переменным x j .

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

ветствующую оптимальному решению без учета целочисленности переменных:

x1 =β1 = 7 / 2, x2 =β2 =3.

Как видим, одна из переменных – x1 оказалась дробной. В соответствии с алгоритмом Гомори сформируем дополнительное ограничение. Для

54

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

дробной частей:

7 / 2 =3 +1/ 2; −1/ 2 = −1 +1/ 2; 1/ 2 = 0 +1/ 2

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

12 x3 + 12 x4 ≥ 12

где x5 – дополнительная переменная. Так как свободный член в выражении для x5 отрицателен, то имеющееся распределение переменных на базисные ( x1, x2 , x5 ) и свободные ( x3, x4 ) не соответствует допустимому опорному плану. Для решения задачи в этой ситуации воспользуемся М-методом (см. § 2.4). Для этого преобразуем уравнение (2.49), используя

считая М большим числом.

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

Поскольку все переменные оказались целыми, полученное решение является искомым оптимальным решением, при котором yinf = −4.

55

§2.7. Замечания

1.При использовании симплекс-метода широкое распространение получили две различные формы симплекс-таблиц. Одна из них была описана и использована выше. Правила составления и использования таблицы иного вида см., например, в [1, 14, 32].

2.При решении некоторых задач ЛП могут возникать особые случаи: вырожденность, альтернативные оптимальные решения, неограниченные решения, отсутствие допустимых решений. Они достаточно подробно рассмотрены в [32]. Здесь же изложена методика анализа чувствительности решений задач ЛП к изменению исходных данных.

3.Существуют классы задач ЛП, например транспортные задачи, для решения которых разработаны специальные алгоритмы. Их применение оказывается обычно более эффективным (с точки зрения затрат времени, необходимого объема памяти и т.п.) по сравнению с симплекс-методом. Такие алгоритмы рассмотрены в гл. 3 и 4.

4.Для решения задач целочисленного ЛП часто рекомендуют вместо алгоритма отсечений Гомори использовать метод ветвей и границ. Его сущность описана, например, в [22, 32].

5.В [1] сформулированы задачи параметрического и дробнорационального ЛП и изложены методики их решения.

6.Как было показано выше, в основе решения различных модификаций задачи ЛП лежит анализ коэффициентов при переменных в выражении для ЦФ и преобразование системы линейных алгебраических уравненийограничений. Эти операции по ходу решения приходится выполнять несколько раз. При решении задач «вручную» даже при невысокой их размерности указанные операции оказываются довольно трудоемкими и их выполнение желательно автоматизировать (с помощью ЭВМ). Во многих задачах ЛП, возникающих на практике, особенно при оптимальном планировании производства, содержатся сотни, а нередко и тысячи переменных

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

56

Контрольные вопросы

1.Как формулируется общая задача линейного программирования в развернутом и кратком векторно-матричном виде?

2.В чем состоит особенность канонической задачи ЛП?

3.Каким образом осуществляется переход от общей ЗЛП к канонической?

4.Что называется областью допустимых решений ЗЛП?

5.Как формулируется условие совместности системы линейных алгебраических уравнений (ограничений-равенств)?

6.Каким образом осуществляется графическое решение задачи ЛП, при каких условиях оно может быть осуществлено?

7.Что называется опорным решением ЗЛП?

8.При каких условиях симплекс-преобразования, осуществляемые при алгебраическом решении ЗЛП, приостанавливаются, а получаемое при этом решение является искомым оптимальным решением?

9.Каким условием определяется выбор разрешающего столбца в сим- плекс-таблице?

10.Как выбирается разрешающая строка в симплекс-таблице?

11.Как называется элемент симплекс-таблицы, стоящий в разрешающем столбце и разрешающей строке?

12.В чем состоит проблема отыскания начального опорного плана задачи ЛП?

13.В чем состоит сущность М-метода (метода штрафов) для отыскания начального опорного решения?

14.Какие трудности могут возникнуть в ходе выполнения расчетов на ЦВМ при решении ЗЛП методом штрафов?

15.В чем состоит сущность двухэтапного метода решения ЗЛП с отысканием начального опорного решения методом искусственного базиса?

16.Как формулируется двойственная задача ЛП по прямой ЗЛП?

17.Каким образом связаны между собой решения прямой и двойственной задач ЛП?

18.В чем состоит особенность целочисленной задачи ЛП?

19.В чем состоит сущность метода отсекающих плоскостей (дробного алгоритма Гомори) для решения целочисленной ЗЛП?

57

Задачи для самостоятельного решения

Найти графическим методом решение следующих задач ЛП:

58

59

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

Используя метод искусственного базиса и симплекс-метод, решить следующие задачи ЛП.

60