Первый алгоритм симплекс метода

ВЫЧИСЛИТЕЛЬНЫЕ АЛГОРИТМЫ СИМПЛЕКС-МЕТОДА

Приведём описание алгоритма применительно к ЗЛП, записанной в канонической форме с односторонними ограничениями:

Пусть известен начальный опорный план с базисом , т.е. - базисные компоненты, - небазисные компоненты.

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

	C		…		…
№		P	B		…		…		t
					…		…
…	…	…	…	…	…	…	…	…
					…		…
…	…	…	…	…	…	…	…	…
m					…		…
					…		…

Порядок вычислений по первому алгоритму:

Шаг 1. Найти обратную к матрицу .

Шаг 2. Вычислить коэффициенты разложения векторов условий по базису , используя расчётную формулу:

и заполнить ими столбцы симплекс-таблицы нулевой итерации.

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

Полученными значениями заполнить -ю строку симплекс-таблицы.

Шаг 4. Проверить оптимальность опорного плана.

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

· Если хотя бы в одном столбце с отрицательной оценкой все элементы меньше или равны 0 , то линейная форма не ограничена сверху и решения ЗЛП не существует. На этом процесс решения ЗЛП также завершается.

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

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

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

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

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

Шаг 6. Заполнить новую симплекс-таблицу в следующей последовательности.

· На -тых позициях столбцов и записать соответственно и , а на остальных позициях этих столбцов оставить прежние элементы.

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

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

Этим завершается построение новой симплекс-таблицы.

Описанный процесс построения симплекс-таблиц повторяется до получения оптимального опорного плана или до установления неограниченности линейной формы, т.е. неразрешимости ЗЛП.

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