Линейное программирование. Теория двойственности. Вариант № 14

Министерство Образования и науки Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет Бизнеса

Кафедра Экономической информатики

Расчетно-графическая работа

По теме: "ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. ТЕОРИЯ ДВОЙСТВЕННОСТИ"

ВАРИАНТ - 14

Группа: ФБИ-51

Студент:

Преподаватель: Кириллов Ю. В.

Новосибирск

2007

Цель работы:

1.  Понимать смысл, различать, осознанно использовать следующие понятия: математическая модель задачи линейного программирования (ЗЛП); формы записи ЗЛП; геометрическая интерпретация ЗЛП; линии уровня функции; градиент функции; двойственные задачи; двойственные оценки; устойчивость решения ЗЛП; устойчивость оценок.

2.  Получить навыки, уметь: строить математические модели ЗЛП; переходить от одной формы записи ЗЛП к другой; решать графически ЗЛП с двумя переменными; строить модель задачи, двойственной к исходной; находить решение ЗЛП на основе решения задачи, двойственной к ней; интерпретировать полученные результаты в терминах решаемой задачи; проводить анализ устойчивости решения ЗЛП на основе геометрической интерпретации.

Условие задачи:

Коммерческая фирма предполагает осуществить оптовую закупку продовольствия, располагая для этого суммой Sрублей. Номенклатура продовольствия включает пять наименований. Покупная цена каждого вида продукта равна соответственно s₁, s₂, s₃, s₄ и s₅ рублей за килограмм. В распоряжении фирмы имеются холодильные камеры общей площадью V кв. метров. Площадь, необходимая для хранения одного килограмма продукта каждого вида, равна соответственно v₁, v₂, v₃, v₄ кв. м; при этом продукт пятого вида хранению не подлежит и должен быть реализован немедленно. При своевременной реализации продукта каждого вида прибыль фирмы составит соответственно p₁, p₂, p₃, p₄ и p₅рублей за килограмм.

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

Задание:

1.  Записать математическую модель задачи.

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

3.  Решить двойственную задачу графически. Используя полученный результат, найти решение исходной задачи.

4.  Дать экономическую интерпретацию двойственным оценкам.

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

6.  Решить задачу с помощью Пакета экономических расчетов (ПЭР) и сравнить результаты решения с результатами, полученными вручную.

Исходные данные:

№ вар	S	V	s1	s2	s3	s4	s5	v1	v2	v3	v4	p1	p2	p3	p4	p5
14	25 000	40	60	110	65	25	40	0.1	0.5	1.0	1.0	18	55	65	50	8

Ход работы:

1.  Составляем математическую модель:

Пусть: X₁ - 1 кг 1-го вида продукции, X₂ - 1 кг 2-го вида продукции, X₃ - 1 кг 3-го вида продукции, X₄ - 1 кг 4-го вида продукции, X₅ - 1 кг 5-го вида продукции.

Тогда целевая функция принимает следующий вид:

Z=P₁X₁+ P₂X₂+ P₃X₃+ P₄X₄+ P₅X₅ à max

Z=18*X₁+ 55*X₂+ 65*X₃+ 50*X₄+ 8*X₅ à max

Ограничения:

 

S1X1+ S2X2+ S3X3+ S4X4+ S5X5 <=S;      V1X1+V2X2+V3X3+V4X4+V5X5 <=V,        Xj >=0, j = 1…5 Xj – целые

60*X1+110*X2+65*X3+25*X4+40*X5<=25000; 0,1*X1+0,5*X2+1*X3+1*X4+0*X5<=40, Xj >=0, j = 1…5 Xj – целые

2. Рассматривается ЗЛП в симметричной форме:

                                               (1.1)

при ограничениях

                                           (1.2)

Двойственная задача будет иметь вид:

                                                   (1.3)

при ограничениях

                                          (1.4)

В соответствии с формулами 1.3 и 1.4 составим модель двойственной задачи:

Целевая функция: Z=Y₁S+Y₂Và min

Z=Y₁*25000+Y₂*40à min

Ограничения:

y1s1+y2v1>=p1,  y1s2+y2v2>=p2,  y1s3+y2v3>=p3,  y1s4+y2v4>=p4,  y1s5+y2v5>=p5,  y1,y2>=0;

y1*60+y2*0,1>=18,  y1*110+y2*0,5>=55,  y1*65+y2*1,0>=65,  y1*25+y2*1,0>=50,  y1*40+y2*0>=8,  y1,y2>=0;

Решаем двойственную задачу графическим методом:

Построим линии:

 y₁*10/3+y₂/180=1,

 y₁*2+y₂/110=1,

 y₁*1+y₂/65=1,

 y₁/2+y₂/50=50,

 y₁*5+y₂*0=1,

Строим линию уровня:

Тогда точка В точка оптимума (0,2; 66);

Подставляем эту точку в целевую функцию двойственной задачи:

Z=25000*0,2+40*66=7640

Из второй теоремы двойственности найдем решение прямой задачи:

(60*0,2 + 0,1*66 – 18)*X₁^* = 0           0,6*X₁^* = 0          X₁^* = 0

(110*0,2 + 0,5*66 – 55)*X₂^* = 0         0*X₂^* = 0             X₂^* ≠  0

(65*0,2 + 1,0*66 – 65)*X₃^* = 0           14*X₃^* = 0           X₃^* = 0

(25*0,2 + 1,0*66 – 50)*X₄^* = 0           21*X₄^* = 0           X₄^* = 0

(40*0,2 – 8)*X₅^* = 0                             0*X₅^* = 0             X₅^* ≠ 0

Таким образом, в плане X^* прямой задачи только координаты x₁ и x₃ отличны от нуля. Согласно той же теореме о двойственности, x₂^* и x₅^* должны удовлетворять следующим соотношениям:

 

(110*X₂^*+40*X₅^*-25000)*y₁=0,

(0.5*X₂^*+0*X₅^*-40)*y₂=0,

Т.к. y₁^*>0 и y2^*>0, то:

X₂^* = 80;   X₅^* = 405;

Итак, решение исходной задачи: X^* = (0;40;0;0;405)

Z_пр^*  = Z_дв^* = 7640

Теперь проведем экономический анализ полученного решения.

X^* = (x₁^* = 0; x₂^* = 80; x₃^* = 0; x₄^* = 0; x₅^* = 405; x₆^* = 0; x₇^* = 0).

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

Y^* = (y₁^* = 0,2; y₂^* = 66; y₃^* = 0,6; y₄^* = 0; y₅^* = 14; y₆^* = 21; y₇^* = 0).

Величины x₂^* и x₅^* показывают, что товары первого типа необходимо закупить в количестве 80 штук, третьего типа – в количестве 405 штук. Товары 1, 3, 4 типов закупать нецелесообразно. Двойственные оценки y₃^*, y₅^*, y₆^* это подтверждают.

Из второй теоремы двойственности следует:

(1) y₃^* = a₁₁* y₁^* + a₂₁* y₂^* = 60*0,2 + 0,1*66 – 18 = 0,6 (степень нерентабельности товара первого типа)

Аналогично:

(2) y₅^* = a₁₃* y₁^* + a₂₃* y₂^* = 65*0,2 + 1,0*66 – 65 = 14 (степень нерентабельности товара третьего типа)

(3) y₆^* = a₁₄* y₁^* + a₂₄* y₂^* = 25*0,2 + 1,0*66 – 2 = 21 (степень нерентабельности товара четвертого типа)

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

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

Из ограничения прямой задачи по деньгам следует: