2_0

Установка флажка «Линейная модель» обеспечивает ускорение про- цесса решения линейной задачи, а установление флажка «Неотрицательные значения» − неотрицательность переменных.

Подтверждаются установленные параметры нажатием кнопки «ОК».

Решение задачи

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

(рис. 2.2.12)

Рис. 2.2.12

Если задача не имеет решения из-за противоречивости системы огра- ничений или неограниченности целевой функции, сообщение будет иметь вид: «Поиск не может найти подходящего решения» или «Значения целевой ячейки не сходятся» соответственно. Иногда такой результат может быть связан с тем, что в ходе ввода данных были допущены ошибки. Поэтому в случае такого ответа надо проверить правильность ввода данных.

В окне «Результат поиска решения» приведены типы отчета: «Ре-

зультаты», «Устойчивость», «Пределы», которые используются для анали-

за чувствительности. Чтобы получить отчет, необходимо выбрать соответст- вующий тип и нажать кнопку «ОК». Результаты каждого отчета будут выве- дены на отдельных листах рабочей книги с названиями: «Отчет по результа- там 1», «Отчет по устойчивости 1», «Отчет по пределам 1» (рис. 2.2.13)

Рис. 2.2.13

Если необходимо получить только решение задачи, достаточно нажать кнопку «ОК» в диалоговом окне «Результат поиска решения» (рис. 2.2.12),

31

после чего на экране в соответствующих ячейках появятся значения пере- менных и целевой функции. В нашем примере значения переменных нахо- дятся в ячейках В2:C2, а значение целевой функции – в ячейке E2 (рис. 2.2.14).

Рис. 2.2.14

Итак, решение задачи найдено: х1 = 40; х2 = 80, Zmax = 52 000 . Заметим, что надстройка «Поиск решения» позволяет получать реше-

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

Дополнения вносятся на этапе ввода ограничений. К имеющимся в зада- че ограничениям необходимо добавить условие целочисленности перемен- ных. Для этого в диалоговом окне «Поиска решения» надо выбрать кнопку «Добавить», в поле «Ссылка на ячейку» ввести адрес ячеек, содержащих значения переменных (в примере это ячейки В2:С2), а в поле ввода знака ог- раничения выбрать целое (цел). (рис. 2.2.15)

Рис. 2.2.15

Подтверждается ввод условия целочисленности нажатием кнопки «ОК». Если задача имеет альтернативное решение, то с помощью компьюте- ра получаем только одно решение.

Чтобы провести анализ чувствительности, необходимо в диалоговом окне «Результаты поиска решения» выделить с помощью мыши требуемый тип отчета: «Результаты», «Устойчивость», «Пределы» (рис. 2.2.16) и на-

жать кнопку «ОК».

32

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

3.Коэффициенты целевой функции при соответствующих переменных.

4.Предельные приращения коэффициентов целевой функции, при ко- торых текущее базисное решение не изменится. Так, для переменной х1 гра-

ницы устойчивости коэффициента целевой функции составляют (250 ; 500) , поскольку максимальное увеличение коэффициента возможно на 200, а уменьшение − на 50. Другими словами, текущее оптимальное решение не изменится, пока цена за единицу первого вида продукции будет находиться в пределах от 250 до 500 грн.

Рис. 2.2.18. Отчёт по устойчивости (вторая таблица)

Вторая таблица содержит данные об ограничениях.

1.В столбце «Результ. значение» указано значение левой части огра- ничений.

2.В столбце «Теневая цена» находится решение двойственной задачи. Теневая цена показывает, на сколько изменится значение целевой функции, если правая часть ограничения увеличится на одну единицу. В приведенном примере третье ограничение не является связующим, то есть, третий вид сы- рья используется не полностью. Таким образом, можно закупать его меньше на соответствующую величину, то есть на 100 единиц. Это уменьшит затраты как на закупку сырья, так и на его хранение. Теневая цена первого ограниче- ния, равная 400, свидетельствует о том, что каждая дополнительная единица третьего вида сырья увеличит прибыль на 400 грн. Можно также утверждать, что это максимальная цена, которую можно заплатить за 1 единицу сырья первого вида.

34

3. В столбцах «Допустимое увеличение (уменьшение)» находятся предельные приращения правых частей ограничений, при которых текущий опорный план не изменится. В примере для первого вида сырья границы ус- тойчивости (75; 120) , так как допустимое уменьшение возможно на 25 ед., а увеличение на 20 Для второго вида сырья границы устойчивости составляют (100; 140), а для третьего – (200; +∞ ) (здесь 1Е+30 равносильна 1030 ). Это означает, что, до тех пор, пока количество сырья будет находиться в данных пределах, оптимальное решение задачи не изменится.

«Отчет по пределам» для рассматриваемой задачи имеет следующий вид (рис. 2.2.19):

Рис. 2.2.19. Отчёт по пределам (третья таблица)

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

Необходимо отметить, что при решении задачи с использованием над- стройки «Поиск решения» не важно, в какой форме записана задача линей- ного программирования и содержит ли система ограничений полный еди- ничный базис. Решение осуществляется так, как было описано выше.

Для составления и анализа двойственной задачи рассмотрим вначале дополнительно основные понятия двойственности.

При составлении двойственных задач будем пользоваться определени- ем. Если задача задана на max то ограничение вида «≤» будем называть со- гласованным или правильным, а «≥» – неправильным, несогласованным. Если задача задана на min, то ограничение « ≥ » – правильное, а « ≤ » – не- правильное.

Для написания двойственной задачи сформулируем соотношение меж- ду отдельными элементами прямой и двойственной задач:

1.Количество двойственных переменных равно количеству ограниче- ний исходной задачи (каждому ограничению ставится в соответствие двойст- венная переменная).

2.Целевая функция двойственной задачи имеет вид F = b1y1+ b2y2+…+

bmym.

35

3.Если Z → max, то F → min; если Z → min, то F → max (направление цели F противоположно направлению цели Z).

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

ограничение в двойственной задаче правильное. Если x j ≤ 0 , то j-е ограниче-

ние – неправильное, если x j имеет любой знак, то j-е ограничение является равенством.

6.Если i-е ограничение исходной задачи правильное, то yi ≥ 0 , если i-е ограничение исходной задачи неправильное, то yi ≤ 0 , если i-е ограничение исходной задачи « = », то yi может иметь любой знак.

7.Матрицы исходной и двойственной задач взаимно транспонирован-

ные.

Для задачи оптимального выпуска продукции прямая и двойствен- ная записываются в виде:

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

36

Решение двойственной задачи можно получить, исследуя решение ис- ходной на основании первой и второй теорем двойственности.

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

Если одна из пары двойственных задач не ограничена, то у второй не- совместна система ограничений.

Если одна из пары двойственных задач несовместна, то вторая несо- вместна или неограниченная.

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

Чтобы найти y1 надо:

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

вующий вектору Àk ;

2)в этом столбце взять число, которое находится в индексной строке последней симплексной таблицы, т.е. zk − ck ;

3)к этому числу прибавить коэффициент целевой функции из этого

столбца. Это будет y1 , т.е. y1 = zk − ck + ck = zk .

Аналогично по второй, третьей строке и т. д. первой симплексной таб- лицы и элементам индексной строки последней таблицы находятся y2 , y3 и т. д.

При нахождении решения двойственной ЗЛП надо пользоваться пра- вилом:

при умножении целевой функции на -1 двойственные переменные ме- няют знак.

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

при умножении i-го ограничения на -1 i-я двойственная переменная ме- няет знак.

Значения двойственных переменных можно выписать из значения те- невых цен.

4. Напишем двойственную задачу в примере 2.2.1.

F = 100y1 + 120y2 + 300y3 → min,

y1 ≥ 0, y2 ≥ 0, y3 ≥ 0.

37

5. Находим значения двойственных переменных из табл. 2.2.5.

Их можно выписать из теневых цен или из индексной строки последней симплекс-таблицы.

6. Определяем дефицитность ресурсов

На фирме цинк и медь и будет использовано полностью, а олово нет. Олова используется 200 кг, а остаётся 100 кг.

7. Найдём интервалы устойчивости по сырью и ценам

Чтобы план сохранял структуру, интервалы изменения ресурсов каж- дого в отдельности при неизменности других имеют вид

8. Целесообразность выпуска третьего изделия

Для проверки целесообразности выпуска третьего изделия по цене c3 = 400 400 грн. и затратами металла a23 = 1, a23 = 0,5 и a23 = 2,5 килограм- мов соответственно находим величину

3 = y1 a13 + y2 a23 + y3 a33 − c3 = 400 1+ 100 0,5 + 0 2,5 − 400 = 50 .

Затраты на единицу продукцию больше её цены, поэтому её нецелесо- образно включать в план.

2.3. Симплекс-метод с искусственным базисом. Двойственный сим- плекс-метод

Задача 2.3.1. Решить задачу методом искусственного базиса и с помо- щью «Поиска решений», написать двойственную задачу и записать её ре- шение.

38

Z = 2x1 + x2 − x3 → max,

xj ≥ 0 (j = 1,3).

Решение. Переходим к канонической форме модели. Для этого с левой части первого уравнения вычитаем балансовую переменную x4 , а в левую часть третьего уравнения прибавляем балансовую переменную x5 . В целе- вую функцию их не дописываем (дописываем с нулевыми коэффициентами). Получаем задачу линейного программирования в канонической форме

Z = 2x1 + x2 − x3 + 0x4 + 0x5 → max,

xj ≥ 0 (j = 1,3).

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

Если этого нет, то базисные переменные можно формально дописать в соответствующие уравнения.

В первое и второе уравнения прибавляем искусственные переменные х6 и х7 с коэффициентом равным единице. В целевую функцию их дописыва- ем с большим отрицательным коэффициентом (−M ) . Получим расширен-

ную задачу с полным единичным базисом.

Z′ = 2x1 + x2 − x3 + 0x4 + 0x5 − M x6 − M x7 → max,

xj ≥ 0 (j = 1,3).

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

39