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

Задача 2. Решить задачу о лакокрасочной фабрике симплекс-методом.

Математическая модель задачи (смотрите пример1):

(1)

Приведём задачу к каноническому виду, приводя ограничения типа ˝ ˝ к ограничениям типа ˝=˝, вводя неотрицательные остаточные переменные S₁, S₂, S₃, S₄, причём, , если знак в ограничении , и , если знак .

(2)

Выпишем расширенную матрицу ограничений (коэффициенты при неизвестных в ограничениях):

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

Замечание 1. Единичная подматрица может получаться и путём перестановки столбцов.

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

Замечание 2. В данной задаче базисные переменные можно было бы не выражать, т.к. Z не содержит базисных переменных.

Переносим в Z неизвестные в левую часть:

- Z-строка начальной симплекс-таблицы.

Строим начальную симплекс-таблицу (смотрите таблицу 1) и доводим её до оптимальной.

Таблица1

Б	Z	x₁	x₂	S₁	S₂	S₃	S₄	Реш.		Ком.
Z		-3	-2						-	Не опт.
S₁										x₁→Б
S₂										Б→S₂
S₃		-1							-
S₄									-

Данная симплекс-таблица не оптимальна, т.к. в Z-строке у переменных есть отрицательные коэффициенты (относительные оценки). Выбираем наименьшую отрицательную относительную оценку и эта переменная входит в базис: x₁→Б (ведущий столбец). Делим элементы столбца ˝Решение˝ на положительные элементы ведущего столбца x₁ и результаты записываем в столбец . Выбираем в столбце наименьшее число и эта переменная выходит из базиса: Б→S₂ (ведущая строка). Обнуляем элементы ведущего столбца методом Гаусса (на пересечении ведущей строки и ведущего столбца получаем 1, а остальные 0). Следующую симплекс-таблицу (таблица 2) получаем следующим образом: ; ; ; ; .