Задачи линейного программирования

СИМПЛЕКС-МЕТОД РЕШЕНИЯ

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

Например, для системы

базисным и опорным решением является .

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

Обозначим базисные переменные, входящие в первое, …, -е, …, последнее уравнения через

, …, , …, ,

соответственно, а коэффициенты при этих переменных в целевой функции – , …, , …, .

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

	Базис		…		…		В
	…		…
			…		…
…	…	…	…	…	…	…	…
			…		…
…	…	…	…	…	…	…	…
			…		…
			…		…

Последняя строка таблицы называется индексной строкой. Числа , …, , …, называются оценками переменных , …, , …, , соответственно. Вычисляются оценки по формулам

, …,

,…,

Оценки, соответствующие базисным переменным, равны нулю.

Число равно значению целевой функции на опорном решении, соответствующем базису , …, , …, .

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

Пример. Для задачи