Основная задача линейного программирования Симплекс-метод

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

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

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

Этап 1 Просматривается дополнительная строка снизу, где записаны разности. Если все эти разности меньше, либо равны нулю, то план является оптимальным

Этап 2 Если есть столбцы, где в нижней строке есть величина больше нуля, то выбирается столбец с максимальным значением этой величины. Индекс j определит вектор, вводимый в базис. Пусть max(z j -c j )=z l -c l, то есть в базис надо вводить переменную x l. Назовем столбец, соответствующий этой переменной, направляющим столбцом. В дальнейшем мы будем направляющий столбец помечать символом.

Этап 3 Просматривается направляющий столбец. Если все a il 0, то находится min (i) (x i /a il ), где просматриваются лишь те дроби, для которых a il >0. Пусть этот минимум достигается для a kl. Тогда именно переменная x k подлежит выводу из базиса. Строка, соответствующая этой переменной, называется направляющей строкой. В дальнейшем в примерах мы будем помечать ее символом.

Этап 4 После того, как определены направляющие столбец и строка, начинает заполняться новая симплекс- таблица, в которой на месте направляющей строки будет стоять переменная x l. Обычно заполнение этой новой таблицы начинается именно с направляющей строки. В качестве компоненты опорного плана туда пишется величина x k /a kl. Остальные элементы этой строки заполняются величинами a lj =a kj /a kl.

Этап 4 Обратите внимание на особую роль элемента a kl, стоящего на пересечении направляющей строки и направляющего столбца. Именно на него делятся все бывшие элементы направляющей строки. На месте бывшего элемента автоматически появляется единица. Написанные выше формулы для пересчета элементов направляющей строки можно записать следующим правилом: a kl

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

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

Исходная симплекс-таблица Базиссiсi План x1x1 x2x2 x3x3 x4x4 x5x5 x6x6 x1x x4x x6x

Пример Обратите внимание на то, что из-за специфического вида системы ограничений в столбец "план" просто переписался вектор свободных членов системы ограничений. Ну, а величины z 0 и z j -c j приходится считать:

Первая итерация Просматривая дополнительную строку мы видим, что в ней всего один положительный элемент - в столбце, соответствующем переменной x 3. Следовательно, эту переменную надо вводить в базис и этот столбец и будет направляющим столбцом. В этом направляющем столбце есть два положительных числа - 4 и 3. Поэтому нужно рассмотреть два частных 12/4 и 10/3 и выбрать из них наименьшее. Так как min ((12/4), (10/3))=3 и он достигается на a 43 =4, то этот вектор подлежит выводу из базиса и соответствующая ему строка и будет направляющей строкой. Заполним теперь новую симплекс-таблицу, следуя сформулированным выше правилам. Начинается заполнение, естественно, со второй строки (так как она была направляющей), а затем пересчитываются все остальные строки.

Полученная симплекс-таблица Базиссiсi План x1x1 x2x2 x3x3 x4x4 x5x5 x6x6 x1x /201/420 x3x /211/400 x6x /20-3/ /20-3/4-20

Вторая итерация Просматривая дополнительную строку мы вновь видим в ней всего один положительный элемент это 1/2, стоящая в столбце x 2. Следовательно, этот вектор надо ввести в базис и этот столбец будет направляющим. В столбце, соответствующем x 2, всего один положительный элемент это 5/2в первой строке. Поэтому первая строка будет направляющей и переменная x 1 должна быть выведена из базиса.

Новая симплекс-таблица Базиссiсi План x1x1 x2x2 x3x3 x4x4 x5x5 x6x6 x2x2 142/5101/104/50 x3x3 -351/5013/102/50 x6x / /500-4/5-12/50