Алгоритм симплекс-метода. Симплексные таблицы.

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

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

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

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

1) Находим базисный план и базисные переменные (выделяем n-переменных, которые составят базисный план)

2) С помощью элементарных преобразований приводим матрицу к единичной.

3) Вычисляем оценки

4) Оценка базисного плана:

если , то x=(b, 0) – решение задачи.

если , то находим координату (Н- небазисные) и переводим ее в базисный набор, используя ограничения: ,

Если , то бесконечности.

Симпликсная таблица:

Б		С	…	…	…
		…
…	…	…	…	…	…
	Z		…