Теория двойственности

Вариант 18

 

Содержание

Задача 1 3

Задача 2. 8

Задача 3. 8

 

 

Задача 1

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

• Ассортимент выпускаемой продукции включает пастеризованное молоко, кефир и сметану, а также дополнительную продукцию молочный коктейль.
• Затраты сырого молока составляют:

• На пастеризованное молоко – 1,01 кг/кг;
• На кефир – 1,01 кг/кг;
• На сметану - 9,45 кг/кг;
• На молочный коктейль – 0,95 ц/ц.

• Затраты на сахар при производстве молочного коктейля составляют 4 кг/ц. Суточный рацион сахара составляет 60кг.

• Поставщики в состоянии поставить не более 140 ц молока в сутки.
• Фасовка молока и кефира осуществляется на автоматизированной линии производительностью 5 ц молока или 6 ц кефира в час. В течение суток линия может эксплуатироваться не более 21 часа. На этой же линии производится упаковка молочного коктейля с производительностью 0,5 ц/ч.
• Фасовка сметаны осуществляется на другой автоматизированной линии производительностью 30 кг сметаны в час. В течение суток линия может эксплуатироваться не более 16 часов.
• Цена реализации пастеризованного молока – 2,4, кефира – 2,7, сметаны - 13,8 тыс. руб/ц , молочного коктейля – 2050 руб/ц.
• План должен обеспечивать максимальную выручку от реализации молочной продукции (контракт на поставку молока уже оплачен)

 

 

 

Решение:

Сведем все данные в  таблицу и переведем все данные в одну единицу измерения –  центнер.

Таблица 1. Исходные данные прямой задачи

Состав	Продукция				Ограничение по ресурсам
	Пастеризо-ванное молоко	Кефир	Сметана	Молочный коктейль
Затраты молока, ц	1,01	1,01	9,45	0,95	140
Затраты сахара, ц	0	0	0	0,04	0,6
Затраты раб. времени на фасовку 1 линии, ц в час	5	6	0	0,5	21
Затраты раб. времени на фасовку 2 линии, ц в час	0	0	0,3	0	16
Цена, тыс. руб за ц	2,4	2,7	13,8	2,05

 

Построим математическую модель двойственной задачи.

Обозначим через y₁ - количество молока, y₂ – количество сахара, y₃ – рабочее время на фасовку пастеризованного молока, кефира и молочного коктейля, y₄ – рабочее время на фасовку сметаны. Тогда ЦФ примет вид: 140y₁+0,6y₂+21y₃+16y₄→min. Целевая функция в двойственной задаче определяет стоимость запасов всех ресурсов. Левая часть ограничений определяет стоимость ресурсов в альтернативных ценах, затраченных на x_j.

С учетом ограничений и  не отрицательности y₁, y₂, y₃ и y₄ получаем:

min ЦФ=140y₁+0,6y₂+21y₃+16y₄

При ограничениях:

 

Приведем систему ограничений  к системе неравенств смысла ≤, умножив  соответствующие строки на (-1). и получим:

min ЦФ=140y₁+0,6y₂+21y₃+16y₄

При ограничениях:

 

Перейдем к канонической форме:

min ЦФ=140y₁+0,6y₂+21y₃+16y₄+0*y₅+0*y₆ +0*y₇+0*y₈

При ограничениях:

 

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

Таблица 2.

БП	СБ	А	У1	У2	У3	У4	У5	У6	У7	У8
			140	0,6	21	16	0	0	0	0
У5	0	-2,4	-1,01	0	-5	0	1	0	0	0
У6	0	-2,7	-1,01	0	-6		0	1	0	0
У7	0	-13,8	-9,45	0	0	-0,3	0	0	1	0
У8	0	-2,05	-0,95	-0,04	-0,5	0	0	0	0	1
FJ-CJ		0	-140	-0,6	-21	-16	0	0	0	0

 

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

В нашем случае, начальный  опорный план не оптимален (таблица 2) так как в базовом столбце А есть отрицательные значения, следовательно, необходимо перейти к не худшему опорному плану.

Разрешающая строка определяется по максимальной по модулю оценке в базисном столбце среди отрицательных, в таблице 2 разрешающая строка третья.

Разрешающий столбец определяется по минимальной оценке отношению А и значению в индексной строке, в таблице 2 разрешающий столбец – Y₁.

После симплексных преобразований, не худший опорный план представлен в таблице 3:

Таблица 3.

БП	СБ	А	У1	У2	У3	У4	У5	У6	У7	У8
			140	0,6	21	16	0	0	0	0
У5	0	-0,9251	0	0	-5	0,032	1	0	-0,1	0
У6	0	-1,2251	0	0	-6	0,032	0	1	-0,1	0
У1	140	1,4603	1	0	0	0,032	0	0	-0,1	0
У8	0	-0,6627	0	-0,04	-0,5	0,03	0	0	-0,1	1
FJ-CJ		204,444	0	-0,6	-21	-11,6	0	0	-15	0

Полученный опорный план не оптимален. Перейдем к новому не худшему опорному плану.

Разрешающая строка – вторая, разрешающий столбец в таблице 3 – Y₃.

После симплексных преобразований получаем таблицу 4.

Таблица 4.

БП	СБ	А	У1	У2	У3	У4	У5	У6	У7	У8
			140	0,6	21	16	0	0	0	0
У5	0	0,09582	0	0	0	0,005	1	-1	-0	0
У3	21	0,2042	0	0	1	-0,01	0	-0	0,02	0
У1	140	1,4603	1	0	0	0,032	0	0	-0,1	0
У8	0	-0,5606	0	-0,04	0	0,027	0	-0	-0,1	1
FJ-CJ		208,732	0	-0,6	0	-11,7	0	-4	-14	0

Полученный опорный план не оптимален. Перейдем к новому не худшему опорному плану.

Разрешающая строка – четвертая, разрешающий столбец в таблице 4 – Y₂.

После симплексных преобразований получаем таблицу 5.

Таблица 5.

БП	СБ	А	У1	У2	У3	У4	У5	У6	У7	У8
			140	0,6	21	16	0	0	0	0
У5	0	0,09582	0	0	0	0,005	1	-1	-0	0
У3	21	0,20418	0	0	1	-0,01	0	-0	0,02	0
У1	140	1,46032	1	0	0	0,032	0	0	-0,11	0
У2	0,6	14,0152	0	1	0	-0,69	0	2,1	2,29	-25
FJ-CJ		217,141	0	0	0	-12,1	0	-2,25	-13,066	-15

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

Оптимальный план двойственной задачи равен:

Y*=(1,46032;14,0152;0,20418;0;0;-2,25;-13,066;-15), при этом ЦФ=140*1,46+0,6*14,02+21*0,2+16*0=217.14

Получаем, что max ЦФ прямой задачи равен min ЦФ двойственной задачи. По критерию оптимальности полученного решения, если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.