Задание II

/2/, c. 41–42, 47–49, 51–52, 54–56, 82–84, 94–104.

АЛГОРИТМ СИМПЛЕКСНЫХ ПРЕОБРАЗОВАНИЙ

(ПЕРЕХОДА К НЕХУДШЕМУ ОПОРНОМУ ПЛАНУ)

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

Столбец называется разрешающим. (Если задача решается на минимум, то разрешающий столбец выбирается из условия ).

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

Среди симплексных отношений определяют наименьшее, т.е.

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

1. Элементы строки новой таблицы равны соответствующим элементам разрешающей строки старой таблицы, делённым на разрешающий элемент.

2. Все элементы столбца новой таблицы равны нулю, за исключением

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

– – – –