Кудрявтсев Методы оптимизатсии 2015

строки и разрешающего

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

λ 1

мент (выделен окружностью) и находим его обратную величину

. Делая замену соответствующих переменных, получим но-

вую симплекс-таблицу (таблица 3.12).

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

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

101

3.8.5 Отыскание оптимального решения

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

Алгоритм поиска оптимального решения

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

2.Проверяем указанное решение на оптимальность с помощью признака, изложенного в разделе 3.7. Если решение оптимально, то цель достигнута; в противном случае переходим к п. 3.

3.Выполняем приведенные выше преобразования линейной формы и Yдобавляем в симплекс-таблицу строку, соответствующую .

4.Производим обмен свободных и базисных переменных по правилу:

▪в качестве разрешающего столбца выбирается тот,Yгде коэффициент при свободной переменной в строке не

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

▪в качестве разрешающей строки выбирается та, где отношение свободного члена к элементу разрешающего

102

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

5. Повторяем п. 4 до тех пор,Yпока коэффициенты при свободных переменных в строке не будут удовлетворять признаку оптимальности опорного решения или не окажется, что ОДР неограничена.

Пример. Найти решение ОЗЛП, обращающее в минимум ли-

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

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

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

103

Таблица 3.14

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

Таблица 3.15

Делаем замену соответствующих переменных, в результате чего получаем новые симплекс-таблицы (табл. 3.16 — 3.18).

104

Таблица 3.16

Таблица 3.17

Таблица 3.18

105

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

Таблица 3.19

или

3.8.6 Общий алгоритм решения ОЗЛП

Подробно рассмотрев ход решения ОЗЛП, можно сформулировать общий алгоритм.

1.Привести ОЗЛП к стандартному виду:

▪выделить свободные и базисные переменные;

▪выразить линейную форму и базисные переменные через свободные переменные;

▪переписать полученные уравнения в стандартном виде для записи в симплекс-таблицу.

2.Удостовериться, что при выбранных свободных и базисных переменных есть опорное решение; если это не так, осущест-

106

вить поиск допустимого опорного решения (см. раздел 3.8.1).

3.Если в п. 2 удалось найти допустимое опорное решение, проверить его на оптимальность; если оно неоптимально, осуществить поиск оптимального решения (см. раздел 3.8.2).

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

1. Бесконечное множество решений. YВыявляется при наличии нулевых коэффициентов в строке после нахождения оптимального решения.

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

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

3.9 Метод искусственного базиса

В общей задаче ЛП помимо ограничений-равенств есть ограни- чения-неравенства. Для перехода от общей задачи ЛП к основной

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

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

107

раничений4вводятся вспомогательные (или искусственные) переменные согласно следующему правилу: по одной искусственной переменной добавляется со знаком «+» в те ограничения, которые в исходной системе имели тип «=» или « ».

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

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

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

Иными словами, ненулевое значение дополнительной переменной может (но не должно) сигнализировать о неоптимальности

решения. Ненулевое значение вспомогательной переменной сигнализирует о недопустимости решения.

В линейную± форму² 1 искусственные переменные вводятся с коэффициентом , который имеет смысл «штрафа» за введение искусственных переменных. В случае задачи минимизации искусственные переменные прибавляются к функции цели, в случае за-

дачи максимизации — вычитаются:

Y A A P A A ± 4 A 4 A P A 4 ‹ min, Y A A P A ± 4 A 4 A P A 4 ‹ max.

Для отражения этого факта в симплекс-таблицу вводится еще одна строка, которая соответствует так называемой «M-функции». Чтобы определить коэффициенты для этой строки, необходимо просуммировать коэффициенты строк, соответствующих искусственным переменным, и результат взять с обратным знаком.

После этого начинается обмен свободных и базисных перемен-

108

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

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

3.10 Двойственная задача линейного программирования

Задача линейного программирования заключается в максимизации некоторой целевой функции при определенных ограничениях. Подобные задачи часто формулируются экономистами, для которых важно получить максимальную прибыль при ограниченных ресурсах. Так, например,, , …предприятие, (обувная фабрика) выпускает продукцию вида (разные модели обуви)..Прибыль от реализации единицы продукции вида составляет Тогда сум-

марная прибыль предприятия составит

9 D T max,

и эту прибыль требуется максимизировать. Для производства обуви используются m технологических процессов (раскрой, пошив и т.д.). Для выпуска единицы j-го вида продукции требуется какая-то доля/затрат i-го технологического/ процесса (обозначим эту долю как ). Так,/например, – время раскроя одной пары обуви марки № 1, а ! – расход кожи для одной пары обуви марки № 3. Если – количество/ выпускаемой продукции за отчетный период времени, то – количество затраченного i-го ресурса при вы-

109

пуске -го вида продукции (например,∑ /! ! расход кожи на выпуск

обуви марки № 3). Выражение будет представлять из

j /

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

Если ввести себестоимость каждого технологического процесса

можно рассматривать как себестоимость единицы продукции j-го вида. , , … ,

Так как

суммарные затраты на производство, которые желательно миними-

В результате получена двойственная задача линейного программирования. Найти минимум целевой функции

110