 |
Ввести параметры для решения ЗЛП
|
|
|
|
• В диалоговом окне указатель мышки на кнопку «Параметры». На экране появляется диалоговое окно «Параметры поиска решения» (рис. 11).
Рис.11. Установление параметров поиска решения
• Установите флажки в окнах «Линейная модель» (это обеспечит применение симплекс - метода) и «Неотрицательные значения».
• Указатель мышки на кнопку «ОК». На экране диалоговое окно «Поиск решения».
• Указатель мышки на кнопку «Выполнить».
Через непродолжительное время появится диалоговое окно «Результаты поиска решения» иисходная таблица с заполненными ячейками А3:В3 для значений Хi и ячейка С3 с максимальным значением целевой функции (рис.12).
Рис.12. Итоги решения задачи
Если указать тип отчета «Устойчивость», то можно получить дополнительную информацию об оптимальном решении (Рис. 13).
Рис. 13. Отчет по устойчивости
В результате решения задачи получили ответ:
Х1 = 70 - необходимо сшить женских костюмов,
Х2 = 80 - необходимо сшить мужских костюмов,
F(x) = 2300 что бы получить максимальную прибыль.
Рассмотрим решение еще одной задачи.
Фабрика имеет в своем распоряжении определенное количество ресурсов: рабочую силу, деньги, сырье, оборудование, производственные площади и т. п. Допустим, например, ресурсы трех видов рабочая сила, сырье и оборудование имеются в количестве соответственно 80(чел/дней), 480(кг), 130(станко/часов). Фабрика может выпускать ковры четырех видов. Информация о количестве единиц каждого ресурса необходимых для производства одного ковра каждоговида и доходах, получаемых предприятием от единицы каждого вида товаров, приведена в табл.1.
Таблица 1
| Ресурсы | Нормы расхода ресурсов на единицу изделия | Наличие ресурсов | |||
| Ковер А | Ковер В | Ковер С | Ковер D | ||
| Труд | |||||
| Сырье | |||||
| Оборудование | |||||
| Цена (тыс.руб.) |
|
|
|
Требуется найти такой план выпуска продукции, при котором общая стоимость продукции будет максимальная.
1. Сформулируем экономико - математическую модель задачи.
Обозначим через Х1, Х2, Х3, Х4 количество ковров каждого типа.
Целевая функция - это выражение, которое необходимо максимизировать f(x) = 3Х1 +4Х2 +3Х3 +Х4
Ограничения по ресурсам
7Х1 +2Х2 +2Х3 +6Х4 
80
5Х1 +8Х2 +4Х3 +3Х4 480
2Х1 +4Х2 +Х3 +8Х4 130
Х1, Х2, Х3, Х4 
0
Решение
Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки).
В нашей задаче оптимальные значения вектора Х =(Х1, Х2, Хз, Х4) будут помещены в ячейках ВЗ:ЕЗ, оптимальное значение целевой функции в ячейке F4.
Ввести исходные данные.
Введем исходные данные в созданную форму. В результате получим (Рис.14):
Рисунок 14. Исходная экранная форма
Введем зависимость для целевой функции
• Курсор в F4.
• Курсор на кнопку Мастер функций.
На экране диалоговое окно Мастер функций шаг 1 из 2.
• Курсор в окно Категория на категорию Математические.
Рис.15. Вводится функция для вычисления целевой функции
• Курсор в окно Функции на СУММПРОИЗВ.
• В массив 1 ввести[3] В$3:E$3.
• В массив 2 ввести В4:E4.
• Готово. На экране: в F4 введена функция, как показано на Рисунке 15.
4. Введем зависимость для левых частей ограничений:
• Курсор в F4.
• Копировать в буфер.
• Курсор в F7.
• Вставить из буфера.
• Курсор в F8.
• Вставить из буфера.
• Курсор в F9.
• Вставить из буфера.
На этом ввод зависимостей закончен.
Запуск Поиска решения.
6) Назначение целевой функции (установить целевую ячейку).
¨ Курсор в поле Установить целевую ячейку.
¨ Ввести адрес $F$4.
¨ Ввести направление целевой функции: Максимальному значению.
|
|
|
Ввести адреса искомых переменных:
¨ Курсор в поле Изменяя ячейки.
¨ Ввести адреса В$3:E$3.
Ввод ограничений.
Курсор в поле Добавить. Появится диалоговое окно Добавление ограничения (Рис. 16.).
Рис.16. Ввод правых и левых частей ограничений.
· В окне Ссылка на ячейку ввести $F$7.
· Ввести знак ограничение £..
· Курсор в правое окно.
·Вести $H$7.
· Добавить. На экране опять диалоговое окно Добавление ограничения. Ввести остальные ограничения.
· После ввода последнего ограничения ввести ОК.
На экране появится диалоговое окно Поиск решения с введенными условиями (Рис.17).
Рис.17. Введены все условия для решения задачи.
8) Ввод параметров для решения ЗЛП (Рисунок 18).
§ Открыть окно Параметры поиска решения.
§ Установить флажок Линейная модель, что обеспечивает применение симплекс-метода.
§ Установить флажок Неотрицательные значения.
§ ОК (На экране диалоговое окно поиска решения).
§ Выполнить (На экране диалоговое окно результаты поиска решения – Рисунок 19. ).
Рис. 18. Ввод параметров
Рис.19. Решение найдено
Полученное решение означает, что максимальный доход 150 тыс. руб. фабрика может получить при выпуске 30 ковров второго вида и 10 ковров третьего вида. При этом ресурсы труд и оборудование будут использованы полностью, а из 480 кг пряжи (ресурс сырье) будет использовано 280 кг.
Создание отчета по результатам поиска решения
Excel позволяет представить результаты поиска решения в форме отчёта. Существует три типа таких отчетов:
§ Результаты (Answer). В отчет включаются исходные и конечные значения целевой и влияющих ячеек, дополнительные сведения об ограничениях
§ Устойчивость (Sensitivity). Отчет, содержащий сведения о чувствительности решения к малым изменениям в изменяемых ячейках иди в формулах ограничений.
§ Пределы (Limits). Помимо исходных и конечных значений изменяемых и целевой ячеек в отчет включаются верхние и нижние границы значений, которые могут принимать влияющие ячейки при соблюдении ограничений.
1. Отчет по результатам.
| Отчет по результатам | ||||
| Целевая ячейка (Максимум) | ||||
| Ячейка | Имя | Исходно | Результат | |
| $F$4 | коэф. в ЦФ ЦФ | |||
| Изменяемые ячейки | ||||
| Ячейка | Имя | Исходно | Результат | |
| $B$3 | значение Х1 | |||
| $C$3 | значение Х2 | |||
| $D$3 | значение Х3 | |||
| $E$3 | значение Х4 | |||
| Ограничения | ||||
| Ячейка | Имя | Значение | Формула | |
| $F$7 | труд левая часть | $F$7<=$H$7 | ||
| $F$8 | сырье левая часть | $F$8<=$H$8 | ||
| $F$9 | оборудование левая часть | $F$9<=$H$9 |
|
|
|
В отчете по результатам содержатся оптимальные значения переменных Х1, Х2, Х3, Х4, которые соответственно равны 0,10, 30,0; значение целевой функции – 150, а также левые части ограничений.
Решение двойственной задачи можно найти в отчете Поиска решений. Отчет по устойчивости. Теневые цены ресурсов труд, сырье и оборудование соответственно равны 4/3, 0, 1/3 или в десятичных дробях 1.3333, 0, 0.3333.
| Отчет по устойчивости | |||||||
| Изменяемые ячейки | |||||||
| Результ. | Нормир. | Целевой | Допустимое | Допустимое | |||
| Ячейка | Имя | Значение | Стоимость | Коэффициент | Увеличение | Уменьшение | |
| $B$3 | Значение Х1 | -7 | 1E+30 | ||||
| $C$3 | Значение Х2 | ||||||
| $D$3 | Значение Х3 | 1.75 | |||||
| $E$3 | Значение Х4 | -9.667 | 9.667 | 1E+30 | |||
| Ограничения | |||||||
| Результ. | Теневая | Ограничение | Допустимое | Допустимое | |||
| Ячейка | Имя | Значение | Цена | Правая часть | Увеличение | Уменьшение | |
| $F$7 | труд левая часть | 1.333 | |||||
| $F$8 | сырье левая часть | 1E+30 | |||||
| $F$9 | Оборудование левая часть | 0.333 |
Проведем анализ полученного оптимального решения исходной задачи с помощью двойственных оценок.
1) Анализ использования ресурсов в оптимальном плане выполняется с помощью соотношений второй теоремы двойственности.
Ресурсы труд и оборудование имеют отличные от нуля оценки 4/3 и 1/3 – эти ресурсы полностью используются в оптимальном плане, являются дефицитными, сдерживающими рост целевой функции. Правые части этих ограничений равны левым частям.
|
|
|
7Х1 +2Х2 +2Х3 +6Х4 80
2Х1 +4Х2 +Х3 +8Х4 130
7´0 +2´30 +2´10 +6´0=80=80
2´0 +4´30 +1´10 +8´0=130=130
Ресурс сырье используется не полностью (280<480), поэтому имеет нулевую двойственную оценку (Y2=0).
5Х1 +8Х2 +4Х3 +3Х4 480
5´0 +8´30 +4´10 +3´0=280<480
Этот ресурс не влияет на план выпуска продукции.
Общая стоимость используемых ресурсов при выпуске 30 ковров второго вида и 10 ковров третьего вида составит 150 тыс. руб.
g 
= 80 ´Y1 + 480´Y2 + 130´Y3 =80 ´4/3 +480´0+130´1/3 =150 тыс. руб.
По условию (4) не использованный полностью в оптимальном плане ресурс получает нулевую оценку. Нулевая оценка ресурса свидетельствует о его не дефицитности. Ресурс не дефицитен не из-за его неограниченных запасов (они ограничены величиной bi), а из-за невозможности его полного использования в оптимальном плане. Так как суммарный расход недефицитного ресурса меньше его общего количества, то план производства им не лимитируется. Данный ресурс не препятствует и дальше максимизировать целевую функцию f(X).
Заметим, что ценность различных видов ресурсов нельзя отождествлять с действительными ценами, по которым осуществляется его закупка. В данном случае речь идет о некоторой мере, имеющей экономическую природу, которая характеризует ценность ресурса только относительно полученного оптимального решения.
2) Анализ эффективности отдельных вариантов плана выполняется на основе соотношений из 2 теоремы двойственности.
Если изделие вошло в оптимальный план (Xj >0), то в двойственных оценках оно не убыточно, то есть, стоимость ресурсов, затраченных на производство единицы изделия равна его цене. Такие изделия эффективны, выгодны с точки зрения принятого критерия оптимальности. В нашей задаче это ковры второго и третьего видов.
Если стоимость ресурсов, затраченных на производство одного изделия больше его цены, то это изделие не войдет в оптимальный план из-за его убыточности. В нашей задаче в план выпуска не вошли ковры первого и четвертого видов, потому что затраты по ним превышают цену на 7 (10-3) тыс. руб. и 9.666 (10.666-1) тыс. руб. соответственно. Это можно подтвердить, подставив в ограничения двойственной задачи оптимальные значения вектора Y.
7 ´4/3 + 5´0+ 2´1/3=30/3=10 >3
2 ´4/3 + 8´0+ 4´1/3=12/3= 4= 4
2 ´4/3 + 4´0+ 1´1/3= 9/3= 3= 3
6´4/3 + 3´0+ 8´1/3=32/3= 10.666 > 1
Разницу между правыми и левыми частями ограничений двойственной задачи можно найти в Отчете по устойчивости в столбце Нормируемая стоимость.
2) Анализ влияния изменения правых частей ограничений на значения целевой функции (Чувствительность решения к изменению запасов сырья).
|
|
|
Предположим, что запас сырья ресурса «труд» изменился на 12 единиц, т. е. теперь он составляет 80 + 12 = 92 единиц. Из теоремы об оценках, известно, что колебание величины bi приводит к увеличению или уменьшению f(X). Оно определяется величиной yi в случае, когда при изменении величин bi значения переменных yi в оптимальном плане соответствующей двойственной задачи остаются неизменными. В нашей задаче увеличение запасов ресурса «труд» приведет к увеличению значения целевой функции на 16 тыс. руб.(Df(x)= Db1´ y1 =12 ´ 4/3 = 16 ). Для двойственных оценок оптимального плана весьма существенное значение имеет их предельный характер. Точной мерой влияния ограничений на функционал оценки являются лишь при малом приращении ограничения. Известно, что оценки не меняют своей величины, если не меняется набор векторов, входящих в базис оптимального плана, тогда как интенсивность этих векторов (значения неизвестных) в плане могут меняться.
Поэтому необходимо знать такие интервалы изменения каждого из свободных членов системы ограничений исходной ЗЛП, или интервалы устойчивости двойственных оценок, в которых оптимальный план двойственной задачи не менялся бы. Эту информацию можно получить из Отчета по устойчивости. В нашей задаче в ниже приведенном фрагменте отчета видно, что запасы дефицитных ресурсов труд и оборудование могут быть, как уменьшены, так и увеличены, увеличение запаса ресурса сырье не повлияет на план выпуска продукции.
| Ограничение | Допустимое | Допустимое |
| правая часть | Увеличение | уменьшение |
| 1E+30 | ||
После увеличения запаса ресурса труд до 92 чел/ часов было получено новое решение задачи. Изменение запасов ресурсов в пределах интервалов устойчивости двойственных оценок привело не только к изменению значения целевой функции на 16 тыс. руб., но и к изменению плана выпуска. При этом структура плана не изменилась - изделия, которые были убыточны не вошли и в новый план выпуска, т.к. цены на ресурсы не изменились. Новый план выпуска составляет 28 ковров второго вида и 18 ковров третьего вида. Изменение общей стоимости продукции на 16 тыс. руб. (24-8=16) получено за счет уменьшения на 2 единицы ковров второго вида по цене 4 тыс. руб. (4 тыс. руб.´(28-30)= -8 тыс. руб.) и увеличения на 8 единиц ковров третьего вида по цене 3 тыс. руб. (3 тыс. руб.´(18-10)= 24 тыс. руб.).
| Отчет по устойчивости 2 | |||||||
| Изменяемые ячейки | |||||||
| Результ | Нормир. | Целевой | Допустимое | Допустимое | |||
| Ячейка | Имя | значение | Стоимость | коэффициент | увеличение | уменьшение | |
| $B$3 | значение Х1 | -7 | 1E+30 | ||||
| $C$3 | значение Х2 | ||||||
| $D$3 | значение Х3 | 1.75 | |||||
| $E$3 | значение Х4 | -9.667 | 9.667 | 1E+30 | |||
| Ограничения | |||||||
| Результ | Теневая | Огранич. | Допустимое | Допустимое | |||
| Ячейка | Имя | значение | цена | правая часть | увеличение | уменьшение | |
| $F$7 | труд левая часть | 1.333 | |||||
| $F$8 | сырье левая часть | 1E+30 | |||||
| $F$9 | оборудование левая часть | 0.333 |
[1] Примечание: Адреса ячеек во все диалоговые окна удобно вводить не с клавиатуры, а протаскивая мышь по ячейкам, чьи адреса следует ввести.
[2] Относительные и абсолютные ссылки. В зависимости от выполняемых задач в Excel можно использовать относительные ссылки, определяющие положение ячейки относительно положения ячейки формулы, или абсолютные ссылки, которые всегда указывают на конкретные ячейки. Если перед буквой или номером стоит знак доллара, например, $A$2, то ссылка на столбец или строку является абсолютной. Относительные ссылки автоматически корректируются при их копировании, а абсолютные ссылки — нет.
[3] Адреса ячеек во все диалоговые окна удобно вводить не с клавиатуры, а протаскивая мыщь по ячейкам, чьи адреса следует ввести.
|
|
|
