Задача 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).
