Линейное программирование

Министерство  образования РФ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Прикладные  методы оптимизации

Лабораторная  работа №1

«Линейное программирование»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Новосибирск

2010

Цель работы:

 

1. Приобрести  практические навыки и опыт решения  задач ЛП с помощью ПК;
2. Углубить представление о свойствах и особенностях решения пары двойственных задач;
3. Научиться проводить анализ устойчивости решения ЗЛП и двойственных оценок аналитическими методами.

 

 

Ход работы:

 

1. Ознакомилась  с работой ПЭР в режиме «Линейное  программирование» (опция 1 ФМ «Обзор для  LP системы принятия решений»).

 

 

2. Ввела условия  задачи №1 РГР по своему варианту 6.

 

Условие задачи. Коммерческая фирма предполагает осуществить  оптовую закупку продовольствия, располагая для этого суммой 18000 рублей. Номенклатура продовольствия включает пять наименований. Покупная цена каждого вида продукта равна соответственно 60, 70, 40, 10 и 50 рублей за килограмм. В распоряжении фирмы имеются холодильные камеры общей площадью 40 квадратных метров. Площадь, необходимая для хранения одного кг продукта каждого вида, равна соответственно 0.2, 0.7, 1.3,1.1, кв. м; при этом продукт пятого вида хранению не подлежит и должен быть реализован немедленно. При своевременной реализации продукта каждого вида прибыль фирмы составит соответственно 24, 49, 52, 22, 10 рублей за килограмм.

Требуется определить объемы закупки  продовольствия каждого вида, при  которых фирма может рассчитывать на максимальную прибыль.

 

	I	II	III	IV	V	Ресурсы
Холодильники	0.2	0.7	1.3	1.1	0	40
Цена	60	70	40	10	50	18000
Прибыль	24	49	52	22	10
	X1	X2	X3	X4	X5

 

1)

2)

 

 

3. Решила задачу  симплекс-методом (опция 5 ФМ «Решение  задачи»).

 

Нашла оптимальное  решение задачи

 

 

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

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

1) по сумме на закупку продовольствия:

=> => =>

 

=> .

2) по площади, необходимой для  хранения товара:

=> => =>

 

 

 

5. Убедилась в правильности  определения интервалов устойчивости  оценок с помощью ПЭР.

 

 

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

Используя формулу

,

пусть Z = 1500 (рублей), D = 15.

 

 

7. Оценила  целесообразность закупки 6-го  вида продукции, покупная цена которой равна руб. за s₆кг, площадь, необходимая для хранения, - v₆ м² /кг, а прибыль от реализации р₆ руб. за кг.

,

пусть S₆=18; V₆= 0.5; P₆=25.

 

Так как H₆*> 0  следует, что данный вид продукции не целесообразно вводить в план.

 

8. Оценила  целесообразность аренды дополнительных  холодильных камер площадью V_доп = 1,5 м² по цене 15 тыс. руб (С)за квадратный метр.

Данное мероприятие  будет эффективным, если оно обеспечит дополнительную прибыль, т.е.если v_iy_i^* - v_ip_i >0 (Y берем из двойственной задачи в след. пункте.9)

Получаем: 0,2*0,2+60*0,7+0*1,3+7*1,1-1.5*15 = 27,24 => мы получили положительное  число, а это означает, что данное мероприятие по аренде дополнительных холодильных камер будет эффективным, т.е. будет приносить дополнительную прибыль.

 

9. Ввела задачу, двойственную к исходной, и решила ее средствами ПЭР. Определила значения переменных и оценок и сравнила их с результатами, полученными при решении исходной задачи.

 

Z_дв(Y*) = 18000y₁+40y₂ →min

 

60y₁+0.2y₂ ≥ 24;

70y₁+0.7y₂ ≥ 49;

40y₁+1.3y₂ ≥ 52;

10y₁+1.1y₂ ≥ 22;

50y₁ ≥ 10.

 

= 6000 тыс.руб.

Таким образом, мы имеем, что оптимальный план, полученный в прямой задаче, совпадает с оптимальным  планом – в двойственной задаче. А так и должно быть, т.к. об этом гласит основная теорема двойственности!

Мы получили:

= (Y₁*=0,2; Y₂*=60;Y₃*=0; Y₄*=7; Y₅*=34; Y₆*=46; Y₇*=0)

 

      Двойственные оценки Y₄*,Y₅*, Y₆*подтверждают, что товары 2-го,3-го и 4-го типов нецелесообразно закупать.  Двойственные переменные являются мерой убыточности производства соответствующего типа продукции, следовательно, величина Y₄*=7 говорит о том, что стоимость ресурсов, расходуемых на производство (закупку) 1 ед. товара 2-го типа в оптимальных ценах (т.е. фактически наши затраты), превосходит цену этого товара (т.е. наши доходы) на 7 единиц в стоимостном выражении. Это следует из ограничения (2):

 

Y

=a₁₂Y₁* + a₂₂Y₂* – c₂ = 70*0,2  +  0,7*60  – 49  =  7.

 

      Точно так же значения Y₅* и Y₆* показывают нам степень нерентабельности производства (закупки) товаров 3-го и 4-го типов. Ограничения (3) и (4) задачи доказывают это:

 

Y₅*=a₁₃Y₁* + a₂₃Y₂* – c₃ =40*0,2 + 1,3*60 – 52 = 34,

 

Y₆*=a₁₄ Y₁* + a₂₄Y₂* – c₄ = 10*0,2 + 1,1*60 – 22 = 46.

 

Из последних выражений  следует (сравниваем правые части), что  товар 4-го типа является самым невыгодным, потому что его закупка обходится  дороже всего.

Теперь обратимся  к дополнительным переменным прямой задачи. Их значения показывают остатки  соответствующего вида ресурса после  выполнения оптимального плана. Таким  образом, величина X₆* говорит, что 1-й ресурс – деньги – будет израсходован полностью. Действительно, из ограничения (*) прямой задачи следует:

 

X₆*=60X₁*+70X₂*+40X₃*+10X₄*+50X₅*- 18000 =

=60*200 + 50*120 –  18000 = 0.

 

То же самое можно  сказать про остатки 2-го ресурса  – площади холодильников –  их не будет, так как из ограничения (**) очевидно, что:

 

X₇*=0,2X₁*+0,7X₂*+1,3X₃*+1,1X₄*+0X₅*- 40 =

=0,2*200 – 40 = 0.

 

Двойственные оценки Y₁* и Y₂*, которые показывают степень использования соответствующего ресурса, подтверждают это, так как их значения больше нуля. Тогда изменения обоих видов ресурсов (как увеличение, так и уменьшение) должны приводить к такому же изменению общего дохода, т.е. целевой функции, как это и следует из 3-й теоремы двойственности. Для нашей задачи она запишется так:

 

ΔZ≈Y₁*•Δb₁+ Y₂*•Δb₂=1,2Δb₁+ 60Δb₂.  

 

Таким образом, изменение 1-го ресурса на единицу ведет  к такому же изменению (увеличению/уменьшению) дохода на 1,2 ед., а 2-го ресурса –  на 60 ед. в стоимостном выражении.

   Анализ устойчивости  коэффициентов целевой функции  в двойственной задаче будет  совпадать с анализом устойчивости  правой части в прямой задаче. А также аналогично: анализ устойчивости  правой части двойственной задачи  совпадает с анализом устойчивости  коэффициентов целевой функции  прямой задачи.

 

Вывод: я приобрела практические навыки и опыт решения задач линейного программирования с помощью ПЭР; изучила свойства и особенности решения пары двойственных задач; научилась проводить анализ устойчивости решения ЗЛП и двойственных оценок аналитическими методами.