2.2.Постановка задачи

Некоторое предприятие из четырех видов имеющихся ресурсов может производить пять видов различной продукции. Исходные данные задачи представлены в табл.2.2.1.

Таблица 2.2.

Исходные данные задачи

N ресурсов	Запасы ресурсов	Норма расхода ресурсов на 1 ед. продукции.
1	400	1	8	2	3	6
2	800	5	1	1	1	5
3	350	4	2	3	4	3
4	500	3	4	1	2	4
Цена реализации ед.продукции		5	6	3	5	7

Найти:

1. оптимальный план выпуска продукции, обеспечивающий максимальный доход от реализации произведенной продукции;

2. оптимальное решение двойственной задачи;

3. исследовать полученные оптимальные решения по свойствам двойственных оценок;

4. провести анализ модели на чувствительность:

а) в границах устойчивости дефицитного ресурса и за границами устойчивости;

б) в границах устойчивости цен на рентабельную продукцию и за границами устойчивости;

5. решить задачу с заданным ассортиментом выпуска продукции;

6. решить задачу в условиях реализации излишка недефицитного ресурса и приобретения дефицитного.

Составим математическую модель исходной задачи. Найти оптимальный план выпуска продукции (х₁^*,х₂^*,х₃^*,х₄^*,х₅^*), удовлетворяющий условиям:

_(2.15)

Z=5x₁+6x₂+3x₃+4x₄+7x₅ (2.16)

Двойственная задача:

Найти оптимальные оценки ресурсов удовлетворяющие условиям:

(2.17)

(2.18)

Система ограничений (2.15) характеризует использование ресурсов на производство продукции. Целевая функция z(2.16) определяет стоимость произведенной продукции.

Ограничения двойственной задачи (2.17) характеризуют оценки ресурсов на производство единицы каждого вида продукции. Целевая функция w(2.18) характеризует оценку ресурсов.

2.3. Ход выполнения работы

Данную задачу будем решать, используя пакет прикладных программ (ППП) QMforWindows, содержащий раздел линейного программирования.

Задав в диалоговом окне число ограничений (NumberofConstraints), равным 6 (два резервных для ассортиментного выпуска продукции), и число переменных (Numberofvariables), равным 6 (одна резервная), и, щелкнув в случае необходимостиMaximize(максимум), введем коэффициенты и знаки неравенств в таблицу исходных данных. Нужный знак ограничения можно установить с помощью щелчка по стрелке вниз, появляющейся в соответствующем столбце, если в него поместить курсор ввода.

После решения задачи щелчком по меню Windowможно вызвать окна результатов решения:LinearProqramminqResults,Ranqinq,SolutionList(Рис. 2-3)

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

На рис.2 раскрыто окно результатов. В последней строке этого отчета под соответствующими переменными указаны их значения в оптимальном решении, а также значение целевой функции (в столбце RHS). В последнем столбце (Dual-двойственный) указаны двойственные оценки оптимального решения.

Рис.3. Окно границ устойчивости параметров задачи

На рис.3 показано окно Ranqinq- (размах), в котором отражены границы устойчивости параметров исходной задачи. В столбцеValue-(величина) указаны значения переменных в оптимальном плане задачи. В столбцеReduce- (уменьшенный) указаны величины, на которые нужно уменьшить левую или увеличить правую части соответствующего ограничения двойственной задачи для того, чтобы они сравнялись. В следующем столбцеOriqinalVal- (первоначальная величина) указаны коэффициенты целевой функции при соответствующих переменных. В последних двух столбцах указаны нижние и верхние границы изменения этих коэффициентов. Если коэффициенты изменяясь, не будут выходить за пределы этих границ, то основные переменные исходной задачи не изменят свой статус в оптимальном решении, т.е. если были базисными в оптимальном решении, то таковыми останутся и в новом решении (структура выпуска продукции не изменится).

В нижней части (рис.3) указаны границы устойчивости переменных двойственной задачи (двойственных оценок). В первом столбце (DualValue) указаны двойственные оценки оптимального решения для каждого ограничения, во втором (Slack/Surplus) - значения балансовых переменных, в третьем (OriqinalVal) - исходные значения правых частей ограничений. В последних двух столбцах - нижняя и верхняя границы изменения правых частей. Если правые части ограничений изменяясь, не выйдут за пределы этих границ, то двойственные оценки оптимального плана останутся неизменными.

Рис.4. Окно списка решения задачи

На рис.4 раскрыто окно (SolutionList) списка решения задачи. В этом окне отражен перечень всех переменных задачи, их статус (базисная или свободная) и значения этих переменных.

Приведем математические модели исходной (2.15-2.16) и двойственной задачи (2.17-2.18) к основному виду, добавив в левые части систем ограничений неотрицательные балансовые переменные. Получим:

Здесь означает остатокi-го вида ресурса. Двойственная задача в основной форме имеет вид:

Здесь означает превышение оценок ресурсов на выпуск единицы

j-го вида продукции над ценой единицы этой продукции.

Из (рис.2) выпишем оптимальное решение исходной и двойственной задачи соответственно:

Т.е. предприятие получит максимальную выручку в 630,9525 усл.ден.ед, если будет производить продукцию первого вида в объеме 42,8571 единиц, пятого 59,5238 ед. и откажется от производства продукции второго, третьего и четвертого вида (х₂^*= х₃^*= х₄^*= 0).

При таком производстве полностью будут израсходованы ресурсы первого и третьего вида, их остатки S₁=S₃=0. Остатки второго ресурсаS₂=288,0952 и четвертогоS₄=133,3333.

Исследуем полученное оптимальное решение задачи по свойствам двойственных оценок. Под двойственной оценкой будем понимать оценку единицы i–го вида ресурса () или, по другому, теневой ценойi–го ресурса.

1. Двойственная оценка как мера влияния на значение целевой функции. Двойственная оценка ресурса показывает, насколько изменится значение целевой функции при изменении объема соответствующего ресурса на единицу, если изменение этого ресурса не выходит за границы устойчивости. Согласно этому свойству дополнительное приобретение второго и четвертого ресурсов при неизменных объемах первого и третьего даст нулевой вклад в целевую функцию. Данная ситуация вполне объяснима. Узкими местами производства являются первый и третий ресурсы, так как они лимитированы в производстве и расходуются без остатка. Приобретение дополнительно второго и четвертого ресурсов при неизменных объемах первого и третьего видов ресурсов будет лишь загружать склады предприятия. При приобретении дополнительно дефицитных ресурсов производство расширяется и дополнительный выпуск продукции влечет за собой увеличение дохода. Причем, увеличение дохода при увеличении i–го ресурса на величину Δ (в границах устойчивости) ∆z= .

В нашем примере каждая дополнительная единица первого и третьего ресурса приведет к увеличению дохода соответственно на 0,619 и 1,0952 усл.ден.ед. Именно с точки зрения вклада в целевую функцию третий ресурс является более дефицитным. Таким образом, при наличии выбора руководитель предприятия должен ориентироваться на увеличение дохода, в первую очередь, за счет третьего ресурса.

2. Двойственная оценка как мера дефицитности ресурсов. Согласно этому свойству оценка недефицитного (т.е. не полностью используемого) ресурса равна нулю, дефицитный ресурс имеет положительную оценку.

Проверим это свойство для первого и второго ресурса, подставив значение в первое и второе ограничения исходной задачи.

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

3. Двойственная оценка как мера эффективности выпуска продукции. Наше предприятие выпускает продукцию первого и пятого вида, отказываясь от производства остальных видов продукции. Проверим эффективность производства для первой продукции, подставив значения в первое ограничение двойственной задачи:

,

т.е. оценка ресурсов на производство единицы продукции совпадает с ценой единицы этой продукции. Аналогично для третьей продукции. Оценка же ресурсов на производство единицы второго, третьего и четвертого видов продукции превышает цену за единицу на 1,1429;1,5238и2,2381усл.ден.ед. соответственно. Проверим для второй продукции:

на 1,1424.

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

4. Двойственные оценки как мера соизмерения затрат и результатов. Вычислим значения целевых функций исходной и двойственной задач.

Таким образом, эффект от выпуска продукции в оптимальном плане совпадает с затратами, исчисленными в ''теневых ценах''. Исходя из полученных оптимальных решений двойственных задач можно определить план действий при формировании запасов ресурсов для дальнейшего производства, определить ассортимент выпускаемой продукции, наметить мероприятия по переводу продукции из нерентабельной в рентабельную, как при этом можно изменять цены на продукцию и запасы ресурсов без резкого изменения полученного оптимального решения. Речь здесь идет об определении границ устойчивости полученного решения.

Под устойчивостью понимается неизменность набора базисных переменных при изменении цен на продукцию и неизменность оценок при изменении запасов ресурсов. Базисными переменными в оптимальном решении исходной задачи являются х₁и х₅,s₂иs₄. Их значения отличны от нуля. Остальные переменные являются свободными.

На рис.3 приведены границы изменения цен на продукцию и запасов ресурсов. Цена на первую продукцию может меняться в пределах от 2,3333до7,на вторую - от 0 до7,1429(-Infinity, т.е.заменяем 0 исходя из смысла коэффициента):

Пока цена будет оставаться в указанных пределах, в базисе будут те же переменные х₁,х₅,s₂,s₄, их значения также не изменяются. Значения у_iи

изменятся. Проверим это. Увеличим цену на пятую продукцию до 10 (в границах устойчивости). План выпуска продукции при этом x₁^*=(42,8571;0; 0; 0; 59,5238),т.е. сохранился полностью и по ассортименту и по количеству. Изменение дохода при этомΔΔ(809,5238-630,9524=178,5714).

= (1,1905; 0; 0,9524; 0).Значения у_i в оптимальном плане двойственной задачи изменились (рис. 5).

Рис.5. Окно результатов решения задачи с изменением с₅в границах устойчивости

Изменим теперь с₅за границами устойчивости (с₅=5). Получаем оптимальный план х₂^* = (66,6667;41,6667,0,0,0),у₂^* = (0,4667;0;1,1333;0),z²_max=583,3333. Т.е. изменился и ассортимент выпуска продукции и значения оценок ресурсов (рис. 6).

Рис.6. Окно результатов решения задачи с изменением с₅за границами устойчивости

Аналогичные рассуждения можно провести для других видов продукции.

Проведем теперь анализ первоначального решения задачи при изменении запасов ресурсов (правых частей ограничений-RHS). Утверждается, что как и в случае изменения цен, при изменениях в границах устойчивости базис останется неизменным, но значения базисных переменных изменится, т.е. сохранится ассортимент выпуска продукции. При этоми останутся без изменения. Изменим запас дефицитного ресурса третьего вида до 400 (не выходя за границы устойчивости), цены на продукцию заданы исходные.

Получим = (57,3429;0;0;0;57,1429),

= (0,619;0;1,0952;0),

= 685,7143.

Изменение целевой функции произошло на величину

ΔΔили по-другому, Δz₃ =685,7143-630,9524=54,76.

Т.е. структура выпуска продукции в оптимальном плане осталась без изменения, но производство продукции - в другом количестве. Оценки ресурсов и величиныостались неизменными (рис.7).

Рис.7. Окно результатов решения задачи с изменением в границах устойчивости

Изменим запас третьего ресурса за границами устойчивости. Положим b₃=600.

Получим = (102,8571;0;20;0;42,8571),

= (0,3143;0;0,4857;0,9143),

=874,2857.

План выпуска продукции изменился и по базису (ассортименту) и по количеству. Изменились также оценки ресурсов (рис 8).

Рис. 8. Окно результатов решения задачи с изменением b₃ за границами устойчивости