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

Следует обратить внимание на столбцы 6 и 12. В результате преобразований вектор j (столбец 6) включен в базиc, а вектор n+i (столбец 12) исключен из базиcа. Так как направляющая строка выбрана в соотвествии с требованиями (3.15), все элементы правой части ограничений (столбец 2) неотрицательны. Действительно,

решение с большим значением целевой функции (так как на этапе 2 был выбран вектор с максимальной симплекс-разностью).

Необходимо отметить, что индексная строка (строка 7) после перехода к новому базису будет содержать новые оценки небазис-

(A

В самом деле, для небазисного вектора коэффициенты раз-

ложения по новому базису будут находиться в к-м столбце сим-

плексной таблицы. Например, вектор (A (столбец 4) содержит коэффициенты разложения по новому базису

91

Этап 5. Проверка нового опорного решения на оптимальость. Проводится анализ индексной строки на предмет наличия отри-

? 0

таблицу за исходную и переходим к этапу 2.

3.8.3 Пример решения задачи симплекс-методом

Рассмотрим пример решения задачи линейного программирования изложенным выше симплекс методом.

Задание. Фирма имеет возможность приобрести не более 19 трехлитровых банок краски и не более 17 пятилитровых. Цена трехлитровой банки 4 доллара, а пятилитровой – 5 долларов. Всего можно израсходовать не более 141 доллара. Сколько нужно приобрести банок краски, чтобы их суммарная емкость была максимальной?

Решение. Введем обозначения – количество трехлитровых

банок, – количество пятилитровых банок. Целевая функция: Y 3 A 5 ” max.

92

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

x2

gradient

A

x1

Рис. 3.6. Геометрическое решение задачи

93

Для отыскания решения построим симплекс-таблицу, добавив

для удобства еще один столбец, куда запишем отношение

(табл. 3.3).

Выбираем в качествеmaxразрешающего\¯Δ ¯&, ?столбца0. столбец , исходя из соотношения Вычисляя отношение

, выбирем в качестве разрешающей строки строку &. В указан-

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

94

Как видно, в индексной строке нет отрицательных элементов и в

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

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

3.8.4 Отыскание опорного решения

В дальнейшем запись базисных переменных в виде 3.17 будем называть стандартной. Попробуем получить опорное решение, по-

? 0

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

95

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

Алгоритм обмена свободных и базисных переменных с помощью симплекс-таблицы

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

ременных , а на ее место ввести базисную переменную . С алгорит-

лицы, в которой находится разрешающий элемент.

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

96

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

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

менты). Указанные действия не затрагивают сам разрешающий

6.Для каждого элемента / , не принадлежащего ни к разрешающей строке, ни к разрешающему столбцу, записываем в правый нижний угол соответствующей ячейки произведение выделенных чисел, находящихся в r-й строке и s-м столбце.

7.Переписываемa таблицу, заменив:

•на и обратно;

• элементы разрешающей строки и разрешающего столбца – числами, стоящими в правых нижних углах тех же ячеек;

• каждый из остальных элементов – суммой чисел, стоящих в

Для удобства составления симплекс-таблицы перепишем систе-

выделим в ней разрешающий элемент (выделен окружностью).

97

Найдем обратную величину λ 0,5 и умножимλ элементыλ разрешающей строки и разрешающего столбца на и соответственно. Результаты запишем в правый нижний угол табл. 3.8.

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

Втабл. 3.9 представлена симплекс-таблица, полностью готовая

кзамене переменных.

98

Окончательный вид новой симплекс-таблицы после замены пе-

Алгоритм выбора разрешающего элемента

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

2.Ищем в этой строке любой отрицательный элемент / . Если таких элементов в строке нет, то это признак того, что система

несовместна0 a 0 с условиями неотрицательности пе- ременных , ; т.е. задача не имеет допустимых ре-1. Выбираем в симплекс-таблице любую строку с отрицательным

99

шений.

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

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

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

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

7.Повторяем шаги 1-6 до тех пор, пока все свободные члены не станут неотрицательными, или пока не убедимся, что система ограничений противоречит условию неотрицательности переменных (см. п. 2).

Составим по записанной системе симплекс-таблицу (табл. 3.11),