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

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

Рассмотрим следующую задачу линейного программирования, заданную в каноническом виде:

, (1)

(2)

, , …, .

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

Например, система

(3)

где , , является системой допустимого вида.

В этой системе переменные — базисные. Набор этих переменных (неизвестных) называется допустимым базисом переменных.

Переменные — свободные.

Пусть целевая функция (4), а система уравнений приведена к допустимому виду (3). Заменив в выражении (4) каждую базисную переменную ее выражением через свободные переменные, целевую функцию можно записать в виде:

(5)

Пусть .

Подставив в систему (3) вместо свободных переменных и число 0, получим .

Найденное решение системы (3):

(6)

называется базисным. Это решение является неотрицательным. Для базисного решения значение целевой функции .

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

, (1)

при условиях:

(2)

Или в допустимом виде:

, (3)

при условиях:

(4)

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

Таблица 4

Базисные переменные	Свободные переменные
	α				-α4	-α5
	β				-β4	-β5
	γ				-γ4	-γ5
Z	δ				-δ4	-δ5

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

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

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

Элемент таблицы, стоящий на пересечении отмеченных столбца и строки, называется разрешающим.

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

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

Пример 1. Определить минимальное значение функции при условиях