1. Аналитический симплекс метод. Геометрическая интерпретация. Критерий оптимальности решения.

Согласно свойствам задач линейного программирования оптимум целевой функции находится в некоторой угловой точке области допустимых решений (ОДР). Переход от графического метода лежит через алгебраическое описание угловых точек ОДР. Реализация общего алгебраического симплекс-метода основана на аналитических преобразованиях уравнений системы ограничений.

Z = CX ® max (min), АХ = В, Х ³ 0.

Где С = (с₁,…,с _j ,..., с_n), В = (b₁,...b_i ,...b_m) ^Т, Х = (х_1, х₂, ..., х _n ) ^Т ,

А =

Такая форма необходима для получения базисных решений. Из свойств задач линейного программирования допустимые базисные решения полностью определяют угловые точки ОДР.

Этапы реализации симплекс-метода:

определение первоначального допустимого базисного решения (плана); переход к «лучшему» решению на основе свойств линейной целевой функции.

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

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

2. Табличный симплекс метод

Таблица 1 содержит строку «Z» (значение целевой функции при первоначальном базисном решении, далее значения коэффициентов целевой функции с противоположным знаком), столбец правой части «В» и основную матрицу коэффициентов (столбцы «х₁» , «х₂» , «х₃ », «х₄ », «х₅», «х₆»).

Для выбора разрешающего столбца используют значения коэффициентов целевой функции. Так как оптимальное решение должно содержать положительные значения коэффициентов, в качестве разрешающего столбца выбираем столбец с отрицательным коэффициентом. В данном случае столбец «х₂». Для выбора разрешающей строки заполним еще один столбец «Оценочные отношения».

Среди полученных значений столбца «Оценочные отношения» выбираем наименьшее (строка х₅). На пересечении разрешающего столбца и строки находится разрешающий элемент. Дальнейший расчет выполняется по схеме Жордана – Гаусса:

1. Элементы разрешающей строки делятся на разрешающий элемент;

2. Элементы разрешающего столбца обнуляются за исключением разрешающего элемента;

3. Остальные элементы пересчитываются по правилу «прямоугольника»:

а_ij ^*= (а_ijа_sk – а_ikа_sj) / а_sk.

Где а_sk – разрешающий элемент, а_ij – пересчитываемый элемент, а_ij ^* – новое числовое значение, элементы а_ik и а_sj образуют с указанными вершины прямоугольника:

а_ij … а_ik

… … …

а_sj … а_sk

Например, b₁^*= (18*1 – 3*5) / 1 = 3.

В столбце «Базис» вместо переменной х₅ указана новая базисная переменная х₂.

3. Особые случаи симплексного метода

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

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

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

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

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

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

Отсутствие конечного оптимума Геометрическая интерпретация данного особого случая - неограниченность целевой функции на открытом множестве допустимых решений.