Практическая работа по «Линейному программированию»

Махмутдинова Регина

вариант 5

Задача. Для изготовления четырех видов продукции используется три вида сырья. Запасы сырья, нормы его расхода и прибыль от реализации каждого продукта приведены в таблице.

 

Тип сырья	Нормы расхода сырья на одно изделие				Запасы сырья
	А	Б	В	Г
I	2	1	3	2	200
II	1	2	4	8	160
III	2	4	1	1	170
Прибыль от реализации изделия	5	7	3	6

 

1. Сформулируйте прямую оптимизационную задачу на максимум общей прибыли, рассчитайте оптимальную производственную программу, используя процедуру Поиск решения в Excel.

2. Проанализируйте использование ресурсов в оптимальном плане. Укажите статус ресурсов: дефицитный или недефицитный. Увеличение запасов какого вида ресурсов наиболее предпочтительно с точки зрения увеличения прибыли? Укажите интервалы изменения объемов используемых ресурсов, при которых сохраняются текущие оптимальные двойственные оценки. Определите, как изменится общая прибыль при увеличении запасов сырья I вида на 8 единиц.

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

4. Сформулируйте двойственную задачу и найдите ее оптимальное решение, используя соотношения о дополняющей нежесткости. Сравните полученные результаты с результатами, полученными с помощью процедуры Поиск решения.

 

Решение.

Введем условные обозначения:

x1 – норма расхода сырья на одно изделие вида А;

x2 – норма расхода сырья на одно изделие вида Б;

x3 – норма расхода сырья на одно изделие вида В;

x4 – норма расхода сырья на одно изделие вида Г.

Целевая функция будет иметь вид:

.

Ограничения задачи имеют вид:

Оптимальную производственную программу найдем через надстройку Microsoft Excel "Поиск решения" (рис. 1 и рис. 2).

Рисунок 1 – Ввод параметров в диалоговое окно «Поиск решения»

Рисунок 2 – Результат решения задачи

Полученное решение означает, что максимальную прибыль от реализации продукции (460 у.е.) можно получить при изготовлении 80 единиц продукции вида А и 10 единиц продукции вида Г, то есть оптимальный план предусматривает производство продукции вида А и Г (рис. 3).

Рисунок 3 – Отчет по результатам

Для того, чтобы продукция вида Б и В вошли в оптимальный план производства необходимо увеличить их стоимость на 3 и 1,1333 (у.е.) соответственно (нормированная (приведенная) стоимость).

Сырье 2 и 3 типов расходуются полностью, остается неиспользованным 20 ед. сырья 1-го типа. Следовательно, сырье 2 и 3 типов являются дефицитными.

Рисунок 4 – Отчет об устойчивости

Согласно отчету об устойчивости (рис.4) можно сделать следующие выводы:

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

продукция вида А: [5-1,5;   5+7];

продукция вида В: [7-0;      7+3];

продукция вида С: [3-0;  3+1,13];

продукция вида D: [6-2,43; 6+34].

2) Двойственные оценки (теневые цены) 2 и 3 типов сырья положительные.  Это еще раз подтверждает, что сырье 2 и 3 типа являются дефицитными. Двойственная оценка 2 типа сырья показывает, что при его изменении на 1 единицу значение целевой функции измениться на 0,47 единицы. Аналогично двойственная оценка 3 типа сырья, показывает изменение значения целевой функции на 2,27 единицы, при изменении сырья 3-ого типа на 1 единицу. Следовательно, наиболее предпочтительным (с точки зрения увеличения запаса сырья) из дефицитных ресурсов является сырье 3 типа, поскольку его изменение обеспечивает наибольший прирост  целевой функции.

3) интервалы изменения объемов используемого сырья, при которых сохраняется текущие оптимальные двойственные оценки, следующие:

1 тип сырья: [200-20;   200+0];

2 тип сырья: [160-75;   160+150];

3 тип сырья: [170-150; 170+21,43].

Изменение количества ресурсов за пределами интервалов устойчивости приводит к новым оценкам ресурсов. Так, увеличение ресурса 1 типа на 8 ед. не приведет к увеличению целевой функции, поскольку двойственная оценка будет иметь другое значение.

Сформулируем двойственную задачу и найдем ее оптимальное решение.

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

Целевая функция:

.

Ограничения двойственной задачи имеют вид:

Используя соотношения о дополняющей нежесткости находим:

Так как , ,

Решая систему уравнений, получим

, , .

Значение целевой функции двойственной задачи на минимум совпадает с максимальным значением целевой функции исходной задачи:

.

Полученные результаты совпадают с результатами, полученными с помощью надстройки «Поиск решения».