Задача 1.
Решить графическим методом типовую задачу оптимизации.
Фирма производит два широко популярных безалкогольных напитка – «Лимонад» и «Тоник». Фирма может продать всю продукцию, которая будет произведена. Однако объем производства ограничен количеством основного ингредиента и производственной мощностью имеющегося оборудования. Для производства 1 л «Лимонада» требуется 0,02 час работы оборудования, а для производства 1 л «Тоника» - 0,04 ч. Расход специального ингредиента составляет 0,01 кг и 0,04 кг на 1 л «Лимонада» и «Тоника» соответственно. Ежедневно в распоряжении Фирмы имеется 24 ч времени работы оборудования и 16 кг специального ингредиента. Прибыль фирмы составляет 0,1 ден. ед. за 1 л «Лимонада» и 0,3 ден. ед. за 1 л «Тоника». Сколько продукции каждого вида следует производит ежедневно, если цель фирмы состоит в максимизации ежедневной работы?
Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на минимум и почему?
Решение
Введем следующие обозначения:
х1 – количество первого напитка («Лимонад»)
х2 – количество второго напитка («Тоник»)
Цена 1 л «Лимонада» таким образом составляет 0,1 х1 (ден. ед.), а цена 1 л «Тоника» составляет 0,3 х2 (ден. ед.). Т.к. нам необходимо максимизировать прибыль, получаем целевую функцию:
max f(х1,х2) = 0,1 х1 + 0,3 х2.
Ограничения задачи имеют вид:
0,02х1 + 0,04 х2 24;
0,01х1 + 0,04 х2 16;
х1,2 0.
Построим прямые, соответствующие ограничениям задачи: первая прямая имеет вид 0,02х1 + 0,04 х2 = 24, решением ее служат точки (1200;0) и (0;400); вторая прямая имеет вид 0,01х1 + 0,04 х2 = 16, решением ее служат точки (1600;0) и (0;600).
Решением каждого неравенства системы ограничений ЗЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее. Пересечение полуплоскостей, каждая из которых определяется соответствующим неравенством системы, называется областью допустимых решений.

рис. 1 Область допустимых решений
На рисунке 1 заштрихована область допустимых значений. Для определения движения к оптимуму построим вектор-градиент. При максимизации функции движемся вдоль вектора-градиента.
Решая систему уравнений
0,02х1 + 0,04 х2 = 24;
0,01х1 + 0,04 х2 = 16.
Находим, что х1 = 800, х2 = 200.
max f(х1,х2) = 0,1 800 + 0,3 200 = 140 (ден. ед.)
Ответ: Прибыль будет максимальной, если производить 800 л. «Лимонада» и 200 л. «Тоника» ежедневно (х1 = 800, х2 = 200). При решении задачи на минимум решения не будет, так как целевая функция не ограничена снизу (особый случай ЗЛП).
Задача 2.
Использовать аппарат теории двойственности для экономико-математического анализа оптимального плана задачи линейного программирования.
Для изготовления трех видов продукции используют четыре вида ресурсов. Запасы ресурсов, нормы расхода и цены реализации единицы каждого вида продукции приведены в таблице.
Вид ресурсов
Нормы расхода ресурсов на ед. продукции

Запасы
ресурсов


I
вид
II
вид
III
вид



Труд
Сырье 1
Сырье 2
Оборудование

3
20
10
0

6
15
15
3

4
20
20
5

2000
15000
7400
1500

Цена изделия
6
10
9


Требуется:
Сформулировать прямую оптимизационную задачу на максимум выручки от реализации готовой продукции, получить оптимальный план выпуска продукции.
Сформулировать двойственную задачу и найти ее оптимальный план с помощью теорем двойственности.
Пояснить нулевые значения переменных в оптимальном плане.
На основе свойств двойственных оценок и теорем двойственности:
проанализировать использование ресурсов в оптимальном плане исходной задачи;
определить, как изменятся выручка и план выпуска продукции при увеличении запаса ресурса первого вида на 24ед.;
оценить целесообразность включения в план изделия четвертого вида ценой 11ед., если нормы затрат ресурсов 8, 4, 20 и 6 ед.
Решение
1) Сформулировать прямую оптимизационную задачу на максимум выручки от реализации готовой продукции, получить оптимальный план выпуска продукции.
Введем условные обозначения:
х1 – норма расхода ресурсов на одно изделие I вида
х2 – норма расхода ресурсов на одно изделие II вида
х3 – норма расхода ресурсов на одно изделие III вида
Целевая функция имеет вид:
max f(x) = 6 х1 + 10 х2 + 9 х3
Ограничения задачи имеют вид:
3 х1 + 6 х2 + 4 х32000
20 х1 + 15 х2 + 20 х315000
10 х1 + 15 х2 + 20 х37400
3 х2 +5 х31500
х1,2,30
Оптимальный план найдем через поиск решения в надстройках Microsoft Excel (рис. 2 и рис. 3)

рис. 2 Поиск оптимального плана

рис. 3 Добавление ограничения задачи
Таблица 1
Результаты поиска решения
 
х1
х2
х3
 
 
 
 

значение
520
0
110
 
ЦФ
4110
 

коэф. в ЦФ
6
10
9
 
 
 
 

 
 
 
 
 
 
 
 

 
Ограничения
 
 
 
 

Тип ресурсов
 
 
 
 
Левая часть
Знак
Правая часть

Труд
3
6
4
 
2000
<=
2000

Сырье 1
20
15
20
 
12600
<=
15000

Сырье 2
10
15
20
 
7400
<=
7400

Оборудование
0
3
5
 
550
<=
1500

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

рис. 4 Содержание отчета по результатам
В отчете по результатам содержатся оптимальные значения переменных х1, х 2, х 3, которые равны 520;0;110 соответственно; значение целевой функции (4110 ед.), а также левые части ограничений.
()* = (520;0;110)
2) Сформулировать двойственную задачу и найти ее оптимальный план с помощью теорем двойственности.
Число переменных в двойственной задаче равно числу функциональных ограничений в исходной задаче. Исходная задача содержит 4 функциональных ограничения: труд, сырье 1, сырье 2, оборудование. Следовательно, в двойственной задаче 4 неизвестных:
y1 – двойственная оценка ресурса «Труд»
y2 – двойственная оценка ресурса «Сырье 1»
y3 – двойственная оценка ресурса «Сырье 2»
y4 – двойственная оценка ресурса «Оборудования»
Целевая функция двойственной задачи формулируется на минимум. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи:
min g(y) = 2000 y1+15000 y2+7400 y3+1500 y4
Необходимо найти такие «цены» на типы ресурсов (yi), чтобы общая стоимость используемых ресурсов была минимальной.
Число ограничений в системе двойственной задачи равно числу переменных в исходной задаче. В исходной задаче 3 переменных, следовательно, в двойственной задаче будет 3 ограничения.
В правых частях ограничений двойственной задачи стоят коэффициенты при неизвестных в целевой функции исходной задачи. Левая часть определяет стоимость ресурсов, затраченных на производство единицы продукции.
Каждое ограничение соответствует определенной норме использования ресурса на единицу продукции:
3 y1 + 20 y2 +10 y3 6;
6 y1 + 15 y2 + 15 y3 + 3 y410;
4 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.
Решая систему уравнений
3*у1 + 20*у2+10у3-6=0
у2 = 0
4*у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.
Это означает, что оптимальный план двойственности определен верно.
Решение двойственной задачи можно найти, выбрав команду Поиск решения – Отчет по устойчивости в Excel (рис. 5).

рис. 5. Отчет по устойчивост