6. Алгоритм решения задачи симплексным методом

1. Привести задачу линейного программирования к каноническому виду (5), (6) и записать в векторной форме.

2. Найти начальное опорное решение с базисом из единичных векторов и коэффициенты разложения векторов условий по векторам базиса.

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

4. Проверить выполнение критерия оптимальности (26) или (27). Если выполняется признак единственности (29) оптимального плана, то решение задачи заканчивается.

5. Если критерий оптимальности выполняется, но не выполняется критерий единственности (29), то задача имеет бесконечное множество решений (альтернативный оптимум):

. (33)

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

6. Если выполняется условие (31) неограниченности целевой функции, то задача не имеет решения.

7. Если пункты 4-6 алгоритма не выполняются, сделать следующий шаг вычислений симплекс-методом: перейти к новому базису, найти новое опорное решение и перейти к пункту 3.

6. Метод искусственного базиса

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

.

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

В этом случае для построения начального опорного плана используется метод искусственного базиса.

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

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

, (34)

, (35)

<, (36) , , , , (37)

где среди векторов нет единичных.

Составим расширенную задачу с помощью введения искусственных переменных.

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

Каждая искусственная переменная входит в левую часть одного из уравнений системы ограничений с коэффициентом , а в целевую функцию с коэффициентом в задаче максимизации, и с коэффициентом в задаче минимизации, где - сколь угодно большое число:>>1.

В общем случае расширенная задача максимизации (M-задача), имеет вид:

, (38)

, (39)

(40)

,,,,,. (41)

Таким образом, в расширенную задачу входит переменных, из которых – искусственные переменные.

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

Тогда расширенная задача имеет начальный опорный план, полученный из системы ограничений (39)

, (42)

а ее решение может быть найдено симплекс-методом.

Теорема. Если расширенная задача линейного программирования (38)-(41) имеет оптимальный план

, (43)

в котором все искусственные переменные равны нулю , то исходная задача (34)-(37) имеет оптимальный план

, (44)

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

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

Если расширенная задача линейного программирования не имеет решения по причине неограниченности целевой функции, то исходная задача не имеет решения по той же причине.