Пример 1. Табличный симплекс метод

Табличный симплекс метод

Фирма производит две модели А и В сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки.

Для каждого изделия модели А требуется 3 м² досок, а для изделия модели В - 4 м².

Фирма может получить от своих поставщиков до 1700 м² досок в неделю.

Для каждого изделия модели А требуется 12 мин машинного времени, а для изделия модели В - 30 мин. В неделю можно использовать 160 ч машинного времени. Сколько изделий каждой модели следует фирме выпускать в неделю, если каждое изделие модели А приносит 2 дол. прибыли, а каждое изделие модели В - 4 дол. прибыли?

(1)

(для досок),

(для машинного времени) (2)

Следовательно, задача состоит в том, чтобы найти значения x ₁и x ₂, удовлетворяющие условиям неотрицательности (1) и ограничениям типа неравенства (2) и максимизирующие функцию

z = 2 x ₁+ 4 x ₂.

В стандартной форме с неотрицательными дополнительными переменными ограничения и целевая функция принимают вид

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

Составим симплекс таблицу

Отрицательные коэффициенты в целевой функции свидетельствуют о том, что оптимальное решение не достигнуто.

Итерация 1. Продолжим поиск оптимального решения. Для этого попробуем внести в базис переменную х₂ Т.к. базисная переменная должна иметь коэффициент 1, разделим уравнение (ограничение) с большим коэффициентом при х₂ на этот коэффициент, т.е. разделим второе ограничение на 5. Получим

(3)

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

Для того чтобы удалить переменную х₂ из целевой функции, умножим уравнение (3) на коэффициент при переменной х₂ в целевой функции, т.е. на -4, а затем вычтем из целевой функции. Получим

Составим симплекс таблицу для итерации 1

Т.к. в целевой функции остался отрицательный коэффициент, продолжим поиск оптимального решения.

Итерация 2. Внесем в базис переменную х₁ Т.к. базисная переменная должна иметь коэффициент 1, разделим уравнение (ограничение) с большим коэффициентом при х₁ на этот коэффициент, т.е. разделим второе ограничение на 7/5. Получим

(4)

Далее, для того чтобы удалить переменную х₁ из второго ограничения, умножим уравнение (4) на коэффициент при переменной х₁ во втором ограничении, т.е. на 2/5, а затем вычтем из второго ограничения. Получим

Для того чтобы удалить переменную х₁ из целевой функции, умножим уравнение (4) на коэффициент при переменной х₂₁ в целевой функции, т.е. на -2/5, а затем вычтем из целевой функции. Получим

Составим симплекс таблицу для итерации 2

Т.к. коэффициенты в целевой функции положительны – найдено оптимальное решение.

Сводная симплекс таблица имеет вид: