Третий этап: указание процедуры целенаправленного перехода к следующей крайней точке.

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

После чего записываются координаты нового базисного плана:

Здесь k и l – номера векторов , входящего в новый базис, и , выходящего из старого базиса. После того как мы нашли координаты нового базисного плана, проверяем этот план на

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

Симплекс итерация - описанный переход от одного базисного плана к другому. 25

Симплекс таблица

При ручной реализации симплекс метода очень удобно пользоваться симплекс таблицей, которая строиться следующим образом:

 

В первом столбце записана нумерация строк, во втором – векторы базиса , в третьем - стоимости соответствующие базисным столбцам, в четвертом b – координаты

крайних точек. На первом этапе это как раз и есть ограничение.

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

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

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

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

 

26