ПрограммированияПример 4. Для производства четырех видов продукции П1, П2, П3, П4 используются три вида ресурсов. Затраты каждого из видов ресурсов на ед. продукции, запасы ресурсов и прибыль, получаемая с ед. продукции каждого вида, приведены в таблице 2.5. Определить план производства, при котором обеспечивается максимальная прибыль.
Таблица 2.5
Решение. Обозначим через х1 план производства продукции П1, х2 - продукции П2, х3 - продукции П3, х4 - продукции П4. Математическая модель задачи:
Приведем задачу к каноническому виду. Для этого в ограничения задачи введем дополнительные переменные х5, х6, х7 и перепишем условие задачи в виде уравнений:
В качестве базисных переменных возьмем х5, х6, х7, тогда небазисные – х1, х2, х3, х4. Полагаем х1 = х2= х3= х4= 0, тогда х5 =16, х6 =110, х7 =100. 1-я итерация. Составляем первую симплексную таблицу, соответствующую исходному опорному решению (таблица 2.6):
Таблица 2.6
Все строки таблицы, за исключением индексной, заполняем по данным системы ограничений и целевой функции. Элементы последней строки рассчитываем:
В индексной строке четыре отрицательные оценки, значит, найденное решение не является оптимальным и его можно улучшить. В качестве разрешающего столбца следует принять столбец переменной х4:
За разрешающую строку принимаем строку переменной х7:
Разрешающим является элемент а34 =13, т.е. вводим в базис переменную х4, выводим х7. 2-я итерация. Формируем следующую симплексную таблицу (таблица 2.7), пересчитывая предыдущую по изложенному выше правилу формирования новой симплекс-таблицы. Таблица 2.7
Из таблицы 2.7 находим опорный план:
В индексной строке таблицы 2.7 имеется три отрицательные оценки. Полученное решение можно улучшить. Разрешающим элементом является а11 =9/13. 3-я итерация. Формируем следующую симплексную таблицу (таблица 2.8). Из таблицы 2.8 находим опорный план:
Таблица 2.8
В индексной строке таблицы 2.8 имеется одна отрицательная оценка. Полученное решение можно улучшить. Разрешающим элементом является а33 =2/3. 4-я итерация. Формируем следующую симплексную таблицу (таблица 2.9). Таблица 2.9
Из таблицы 2.9 находим опорный план:
Так как все оценки свободных переменных положительные, найденное решение является оптимальным:
Максимальная прибыль составит 1320 ден. ед., при этом необходимо произвести 10 ед. продукции П1 и 6 ед. продукции П3. В оптимальном плане резервы трудовых ресурсов и оборудования равны нулю (х5 = х7 =0), так как они используются полностью. А резерв ресурсов сырья х6 =26, что свидетельствует о его излишках.
|
или
,
,
,
и т.д.
, т.е. k =4.
, т.е. s =3.
, 
.
, 
.
, 
.
, 
.
