Определение оптимального плана производства симплексным методом

Приведем задачу к каноническому виду. Для этого в ограничения задачи введем дополнительные переменные х3, х4, х5 и перепишем условие задачи в виде уравнений:

В качестве базисных переменных возьмем х3, х4, х5, тогда небазисные — х1, х2. Полагаем х1 = х2 = 0, тогда х3 =1000, х4=75, х5 =125.

1-я итерация.

Составляем первую симплексную таблицу, соответствующую исходному опорному решению (таблица 3):

или.

Таблица 3.

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

и т.д.

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

т. е. k =1.

За разрешающую строку принимаем строку переменной х3:

т. е. s =1.

Разрешающим является элемент а11=5, т. е. вводим в базис переменную х1, выводим х3.

2-я итерация.

Формируем следующую симплексную таблицу (таблица 4).

Таблица 4.

Из таблицы 4 находим опорный план:

.

В индексной строке таблицы 4 имеется одна отрицательная оценка. Полученное решение можно улучшить. Разрешающим элементом является а22=0,13.

3-я итерация.

Формируем следующую симплексную таблицу (таблица 5).

Таблица 5.

Из таблицы 5 находим опорный план:

.

Так как все оценки свободных переменных положительные, найденное решение является оптимальным:

Максимальная прибыль составит 6923 рублей, при этом необходимо произвести 153,8 кг бисквитного теста и 115,4 кг песочного теста. В оптимальном плане ресурсы яиц и сахара равны нулю (х3=х4=0), так как они используются полностью. А резерв трудовых ресурсов х5 = 28,8, что свидетельствует о излишках.

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

Обозначим через y1 — двойственную оценку дефицитности яиц, через y2 -сахара, y3 — трудовых ресурсов. Тогда прямая и двойственная задачи формулируются:

прямая задача.

двойственная задача.

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

Двойственные оценки ресурсов yi* - это оценочные коэффициенты j дополнительных переменных х3, х4, х5 в последней симплексной таблице.

Исходя из анализа оптимальных двойственных оценок, можно сделать следующие выводы.

Ресурсы яиц и сахара используются полностью. Полному использованию этих ресурсов соответствуют полученные оптимальные оценки y1, y2, отличные от нуля. Значит, трудовые ресурсы недоиспользуются (х5 = 28,8 чел.-ч.).