Типовая задача оптимизации

Предприятие может получить максимальную выручку от реализации готовой продукции в 4110 ед. при выпуске 520 единиц продукции I вида и 110 единиц продукции III вида. При этом трудовые ресурсы и сырье второго вида будут использованы полностью, тогда как из 15 000 единиц сырья первого вида будет использовано только 12 600 единиц, а из 1500 единиц оборудования будет задействовано только 550 единиц.

Рис.8 Отчет по результатам

В отчете мы видим, что оптимальные значения переменных х1 = 520, х 2 = 0, х 3 = 110, значение целевой функции 4110 ед., а также левые части ограничений.

()* = (520;0;110)

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

Переменные.Исходная задача содержит 4 ограничения: труд, сырье 1, сырье 2, оборудование. Число переменных в двойственной задаче равно числу ограничений в исходной задаче. Следовательно, в двойственной задаче 4 неизвестных:

y1 - двойственная оценка ресурса "Труд" или "цена" труда

y2 - двойственная оценка ресурса "Сырье 1" или "цена" сырья 1

y3 - двойственная оценка ресурса "Сырье 2" или "цена" сырья 2

y4 - двойственная оценка ресурса "Оборудования" или "цена"

оборудования

Целевая функциядвойственной задачи формулируется на минимум. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи:

min g(y) = 2000 y1+15000 y2+7400 y3+1500 y4

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

Ограничения.Число ограничений в системе двойственной задачи равно числу переменных в исходной задаче. В исходной задаче 3 переменных, следовательно, в двойственной задаче будет 3 ограничения.

В правых частях ограничений двойственной задачи стоят коэффициенты при неизвестных в целевой функции исходной задачи. Левая часть ограничений определяет стоимость ресурсов, затраченных на производство единицы продукции. Каждое ограничение соответствует определенной норме использования ресурса на единицу продукции:

3 y1 + 20 y2 +10 y3 6;

y1 + 15 y2 + 15 y3 + 3 y410;

y1 + 20 y2 + 20 y3 + 5 y49.

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

Воспользуемся первым соотношением второй теоремы двойственности

= 0,

Тогда

y1(3 х1+ 6 х2+4 х3 - 2000) = 0;

y2(20 х1 + 15 х2 + 20 х3 - 15000) = 0;

y3(10 х1 + 15 х2 + 20 х3 - 7400) = 0;

y4(3 х2 + 5 х3 - 1500) = 0.

()* = (520;0;110)

Подставим оптимальные значения вектора в полученное выражение

y1(3*520+ 6*0+4*110 - 2000) = 0;

y2(20*520 + 15*0 + 20*110 - 15000) = 0;

y3(10*520 + 15*0 + 20 *110 - 7400) = 0;

y4(3 *0 + 5*110 - 1500) = 0.

Или

y1(2 000- 2 000) = 0;

y2 (12 600 - 15 000) = 0, т.к. 12 600 < 15 000, то y2 = 0;

y3 (7400-7400) = 0;

y4 (550-1500) = 0, т.к. 550 < 1500, то y4 = 0.

Воспользуемся вторым соотношением второй теоремы двойственности

, если >0, то

В нашей задаче х1=520 > 0 и х3 = 110 > 0, поэтому первое и третье ограничения двойственной задачи обращаются в равенства

х1(3 y1 + 20 y2 +10 y3 - 6) = 0;

х2(6 y1 + 15 y2 + 15 y3 + 3 y4 - 10) = 0;

х3 (4 y1 + 20 y2 + 20 y3 + 5 y4 -9) = 0.

Решая систему уравнений

*у1 + 20*у2+10у3 - 6 =0

у2 = 0

*у1 + 20*у2 + 20 у3 + 5*у4-9=0

у4 = 0,

получим у1 = 1,5, у2 = 0, у3 = 0,15, у4 = 0.

Необходимо проверить выполнение первой теоремы двойственности

g(y) = 2000 y1+15000 y2+7400 y3+1500 y4 = 2 000*1,5 + 7400*0,15 = 4 110

f(x) = 6 х1 + 10 х2 + 9 х3 = 6*520+9*110 = 4 110.