Алгоритм симплекс-метода

Шаг 1. Получение начального решения

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

Остальные переменных называются свободными.

Все свободные переменные полагаются равными 0, а базисные переменные – правым частям соответствующих ограничений системы.

Пусть базисных переменных – это переменные , . Тогда начальное решение имеет следующий вид:

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

Шаг 2. Выражение функции только через свободные переменные.

Переход к шагу 3

Шаг 3. Проверка решения на оптимальность.

Составляется симплекс-таблица.

Базисные переменные	Коэффициенты при переменных	Свободные члены
		…		…		…
			…		…		…
			…		…		…
…	…	…	…	…	…	…	…	…	….
			…		…		…
…	…	…	…	…	…	…	…	…	….
			…		…		…
			…		…		…

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

Для проверки решения на оптимальность просматривается последняя -строка.

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

Полученное решение единственно, если все эти коэффициенты положительны.

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

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

Шаг 4. Получение нового решения.

Шаг 4.1. Выбор переменной, вводимой в список базисных переменных.

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

Шаг 4.2. Выбор переменной, выводимой из списка базисных переменных.

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

Шаг 4.3. Выполнение симплекс-преобразования и переход к новой симплекс-таблице.

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

Переход к шагу 3.

Алгоритм поиска допустимого начального решения (в случае )

Шаг 1. Выражение функции через свободные переменные.

Шаг 2. Составление симплекс-таблицы.

Шаг 3. Выбор переменной, вводимой в список базисных.

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

Шаг 4. Вывод переменной, выводимой из списка базисных переменных.

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

Шаг 5. По формулам проводят симплекс-преобразование и переходят к новой симплекс-таблице. Если в новой таблице все свободные члены неотрицательны, то найденное решение является допустимым и следует перейти к шагу 3 алгоритма симплекс-метода, в противном случае – к шагу 2 рассматриваемого алгоритма.

Пример

Базисные переменные: .

Свободные переменные: .

Симплекс-таблица имеет следующий вид:

Базисные переменные	Коэффициенты при переменных	Свободные члены

	-1
	-5	-3
	-2

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

Пример

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

Начальное решение .

Симплекс-таблица имеет следующий вид:

Базисные переменные	Коэффициенты при переменных	Свободные члены

			-1

	-2
	-5		-3

Ввод переменной в список базисных переменных означает, что ей приписывается отличное от 0 положительное значение, т.е. ее значение увеличивается. Из формулы для целевой функции видно, что увеличение значения приводит только к уменьшению , т.е. переменную бессмысленно вводить в список базисных переменных. Увеличение переменных и приводит к увеличению значения , при этом на б о льшую величину значение меняется с увеличением , следовательно, переменная должна стать базисной переменной. Максимальное значение коэффициента при в формуле для соответствует максимальному по абсолютной величине отрицательному элементу в последней строке симплекс-таблицы, следовательно, понятен выбор новой базисной переменной.

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

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

ПОЯСНЕНИЕ

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

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

Подставив в первое уравнение, получим

Окончательно получим

- базисные переменные, поэтому решение имеет вид

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

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

Выразив через , получим

Следовательно, в новом решении , что противоречит условию неотрицательности , поэтому в шаге 4.2 пренебрегают делением на отрицательное число, полагая равным результат от деления.