- •Двойственная задача и её решение.
- •Выводы:
- •Задание 3 Многокритериальная оптимизация
- •Оптимальный план задачи по критерию максимальной прибыли мы уже нашли в 1-ой задаче.
- •Решим задачу методом свертки.
- •Выводы:
- •Решим задачу методом последовательных уступок. Воспользуемся средствами Microsoft Excel.
- •Выводы:
Расчетная работа по дисциплине «Методы оптимальных решений»
Вариант 3
Задание 1
Игры с природой
Розничное торговое предприятие разработало несколько вариантов продажи товаров на предстоящей ярмарке с учетом меняющейся структуры рынка и спроса покупателей, получающиеся от их возможных сочетаний величины прибыли представлены в виде матрицы выигрышей. Определить оптимальный план продажи товаров.
æ = 0,6
-
Величина прибыли, тыс. руб.
План продажи
Состояние конъюнктуры рынка и спроса
1
3
2
5
3
3
2
2
1
2
5
1
4
1
1
2
Pi
0,25
0,2
0,25
0,3
Решение:
Максимальный критерий Вальда.
Воспользуемся формулой:
W =
где - это элемент матрицы выигрышей.
Сначала из каждой строки матрицы выбираем минимальный элемент, а затем среди полученных значений выбираем максимальное. Таким образом, получаем:
что соответствует стратегиям П1, П3, П4. Таким образом, согласно критерию Вальда, наилучшими являются стратегии П1, П3, П4, гарантирующая выигрыш, равный 1.
Критерий минимального риска Сэвиджа.
S = ̓
где - это элемент матрицы рисков, которая получается из матрицы выигрышей по формуле:
= -
Матрица рисков имеет ту же размерность, что и матрица выигрышей, и формируется по столбцам матрицы выигрышей. В каждом столбце максимальный элемент заменятся нулем, а остальные элементы получаются как результат вычитания соответствующего элемента матрицы выигрыша из максимального в своем столбце. Таким образом в данном случае получаем:
Теперь применяем формулу:
Минимум дают стратегии П1, П2, которые являются наилучшими с точки зрения критерия Сэвиджа.
Критерий пессимизма – оптимизма Гурвица. Согласно этому критерию, оптимальной считается стратегия, для которой выполняется соотношения:
G = [ + (1 - ) ],
Пусть = 0,6. Получим:
Согласно критерию Гурвица, оптимальными следует считать стратегии П1 и П3.
Критерий Байеса (максимума математического ожидания выигрыша).
Отсюда средний выигрыш от применения i-ой стратегии:
М i = ij P ij
Среди этих выигрышей выбираем максимальный:
М1 =
М2 =
М3 =
М4 =
По критерию максимума математического ожидания выигрыша имеем = M1 = 2,85, что соответствует наилучшей стратегии П1.
Критерий минимального среднего риска.
R i = ij P ij
R1 =
R2 =
R3 =
R4 =
Отсюда = 1,5, что соответствует наилучшей стратегии П1.
Вывод:
Согласно критерию Вальда, наилучшими являются стратегии П1, П3, П4. Критерии Сэвиджа, показывает, что наилучшими стратегиями являются П1, П2. Согласно критерию Гурвица, оптимальными следует считать стратегии П1 и П3. По критерию Байеса и минимального среднего риска наилучшей стратегией является П1.
По совокупности критериев в данном случае оптимальной следует принять стратегию П1.
Задание 2
Оптимизация использования ограниченных ресурсов
Фирма планирует оптовые поставки телевизоров, пылесосов и холодильников. Для годовой поставки тысячи телевизоров необходимо Sт квадратных метров площадей на складе, Vт вагонов и Rт человек персонала. Для поставки тысячи пылесосов необходимо Sп квадратных метров площадей на складе, Vп вагонов и Rп человек персонала. Для поставки тысячи холодильников необходимо Sх квадратных метров площадей на складе, Vх вагонов и Rх человек персонала. Прибыль с тысячи телевизоров равна Pт миллионов рублей, с тысячи пылесосов – Pп млн. руб., с тысячи холодильников – Pх млн. руб. Фирма располагает складами с общей площадью Sобщ квадратных метров, количество вагонов у фирмы равно Vобщ и количество рабочих – Rобщ человек.
Цель: определить оптимальную с точки зрения получения прибыли годовую партию поставки (количество телевизоров, пылесосов и холодильников).
-
Составить экономико-математическую модель задачи.
-
Найти оптимальное решение. Дать экономическую интерпретацию полученного решения. Сформулировать оптимальное управленческое решение в описанных условиях.
-
Определить интервалы устойчивости полученного плана при изменении коэффициентов целевой функции. Сделать выводы об устойчивости полученного плана к изменению рыночных цен (прибыли от единицы площади каждого вида).
-
Определить двойственные оценки ресурсов. Дать экономическую интерпретацию двойственных оценок. Определить интервалы устойчивости двойственных оценок при изменении каждого ресурса по отдельности. Сделать выводы о рентабельности приобретения дополнительных ресурсов и их количества.
-
Записать четкий ответ для поставленной экономической проблемы.
Sт |
Vт |
Rт |
Sп |
Vп |
Rп |
Sх |
Vх |
Rх |
Pт |
Pп |
Pх |
Sобщ |
Vобщ |
Rобщ |
3 |
6 |
8 |
3 |
2 |
5 |
5 |
5 |
3 |
4 |
3 |
6 |
1850 |
2300 |
2480 |
Решение:
-
Составим экономико-математическую модель задачи. Для этого обозначим – количество тысяч телевизоров, – количество тысяч пылесосов, – количество тысяч холодильников. Эта задача является задачей оптимального использования сырья, поэтому система ограничений имеет вид:
(1)
где справа стоит количество каждого вида сырья, которое не может быть превышено в процессе производства изделий. Эти ограничения являются нетривиальными.
Далее, количество изделий физически является неотрицательными (нельзя произвести отрицательное количество изделия), что дает нам тривиальные ограничения задачи:
. (2)
Наконец, функция цели (целевая функция) представляет собой общую стоимость построенных зданий, и эта функция в данной задаче оптимизируется на максимум:
(3)
-
Найдем решения этой задачи с помощью сервиса Excel Поиск решения.
Открываем электронную книгу Excel и, как и для решения однокритериальной задачи определяем ячейки под переменные x1, x2, x3.
Вызываем надстройку «Поиск решения» в меню «Сервис». Оптимизируем целевую функцию.
После открытия окна «Поиск решения» в поле «Установить целевую» ставим курсор и делаем ссылку на ячейку F5, щелкая по ней мышью. В окне появится $F$5. В связи с тем, что целевая функция максимизируется, далее нужно проверить, что флажок ниже поля стоит напротив надписи «Равной максимальному значению».
Для запуска вычислений нажимаем кнопку «Выполнить». Получаем результат.
,
Для достижения максимальной прибыли 2280 требуется поставить 150 тысяч телевизоров и 280 тысяч холодильников.
-
В процессе поиска оптимального решения MS-Excel формирует так называемый отчет об устойчивости, в котором, в частности, выдает интервал изменений коэффициентов целевой функции, внутри которого их изменение не приводит к изменению oоптимального решения. Для получения этого отчета, после того как "Поиск решения" нашел оптимальное решение, нужно в окне "Результаты поиска решения", перед тем как нажать на кнопку Ok, щелкнуть мышкой по строке "Устойчивость" в списке "Тип отчета". Тогда после нажатия на кнопку Ok MS-Excel создаст дополнительный лист "Отчет об устойчивости".
Microsoft Excel 12.0 Отчет по устойчивости |
|
|
|
||||
Рабочий лист: [3 задача ВАР 3.xlsx]Лист1 |
|
|
|
||||
Отчет создан: 31.03.2013 17:36:58 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Изменяемые ячейки |
|
|
|
|
|
||
|
|
|
Результ. |
Нормир. |
Целевой |
Допустимое |
Допустимое |
|
Ячейка |
Имя |
значение |
стоимость |
Коэффициент |
Увеличение |
Уменьшение |
|
$B$8 |
ПЛАН T1 |
150 |
0 |
4 |
1,399999999 |
0,4 |
|
$C$8 |
ПЛАН T2 |
0 |
-0,46666666 |
3 |
0,466666666 |
1E+30 |
|
$D$8 |
ПЛАН T3 |
280 |
0 |
6 |
0,666666667 |
0,583333333 |
|
|
|
|
|
|
|
|
Ограничения |
|
|
|
|
|
||
|
|
|
Результ. |
Теневая |
Ограничение |
Допустимое |
Допустимое |
|
Ячейка |
Имя |
значение |
Цена |
Правая часть |
Увеличение |
Уменьшение |
|
$F$2 |
P1 ЗАТРАТЫ |
1850 |
1,066666667 |
1850 |
450 |
300 |
|
$F$3 |
P2 ЗАТРАТЫ |
2300 |
0,133333333 |
2300 |
212,9032258 |
450 |
|
$F$4 |
P3 ЗАТРАТЫ |
2040 |
0 |
2480 |
1E+30 |
440 |
Первая таблица отчета об устойчивости "Изменяемые ячейки" содержит столбцы "Целевой коэффициент", "Допустимое увеличение" и "Допустимое уменьшение". В первом из них даны исходные значения целевых коэффициентов: прибыль от поставки телевизоров (4 млн. руб.), пылесосов (3 млн. руб.) и холодильников (6 млн. руб.). Второй и третий столбцы содержат информацию об интервале устойчивости найденного оптимального решения. При увеличении прибыли от поставки телевизоров до 5,4 млн. руб. (на 1,4 млн. руб. больше исходного значения) и при ее уменьшении до 3,6 млн. руб. оптимальное решение не изменяется. Аналогично второй целевой коэффициент может изменяться в пределах от -∞ (уменьшение на -∞ относительно исходного значения) до 3,47 млн. руб. и третий целевой коэффициент может изменяться в пределах от 5,42 млн. руб. до 6,67 млн. руб.
-
Двойственная задача и её решение.
Рассмотрим исходную задачу. При переходе к двойственной задаче нужно выполнить ряд правил. Во-первых, каждому ограничению исходной задачи соответствует переменная двойственной задачи. Таким образом, здесь будут три двойственные переменные , , . Во-вторых, ограничения двойственной задачи соответствуют столбцам системы; неравенства типа превращаются в неравенства типа , а свободными членами становятся коэффициенты при соответствующих переменных целевой функции. В-третьих, целевая функция двойственной задачи оптимизируются не на максимум, а на минимум; коэффициентами становятся свободные члены системы. Наконец, двойственные переменные , как и переменные задачи, подчиняются тривиальным условиям неотрицательности. С учетом этих замечаний задача, двойственная задаче, имеет вид:
Решение двойственной задачи можно получить из "Отчета об устойчивости".
Теневые цены - это оценки yi двойственной задачи.
Таким образом, , , .
Данные оценки показывают, по каким минимальным ценам следует продавать ресурсы, чтобы прибыль от их реализации была больше прибыли, полученной от реализации продукции, изготавливаемой с использованием этих ресурсов.
Пределы изменения bi, в которых оптимальное решение соответствует той же самой угловой точке, также даны в таблице "Ограничения" ("Допустимое увеличение" и "Допустимое уменьшение"). Получаем интервалы устойчивости двойственных оценок по отношению к изменению ресурса каждого вида
-
Выводы:
Для достижения максимальной прибыли 2280 требуется поставить 150 тысяч телевизоров и 280 тысяч холодильников.
При увеличении прибыли от поставки тысячи телевизоров до 5,4 млн. руб. и при ее уменьшении до 3,6 млн. руб. оптимальное решение не изменяется. Прибыль от поставки тысячи пылесосов может изменяться в пределах от -∞ до 3,47 млн. руб. и прибыль от поставки тысячи холодильников может изменяться в пределах от 5,42 млн. руб. до 6,67 млн. руб.
Интервалы устойчивости двойственных оценок по отношению к изменению ресурса каждого вида:
Для стройматериалов: ;
Для техники:
Для рабочих: .
Задание 3 Многокритериальная оптимизация
Для задачи предыдущего задания найти решение при двух дополнительных критериях оптимизации. Для этого смоделировать следующие условия.
Затраты на износ оборудования и помещений при поставке тысячи телевизоров равны Wт тыс. руб., при поставке тысячи пылесосов Wп тыс. руб., при поставке тысячи холодильников Wх тыс. руб.
Рост репутации фирмы при поставке тысячи телевизоров равен Нт баллов, при поставке тысячи пылесосов Нп баллов, при поставке тысячи холодильников Нх баллов.
Рассмотреть вариант оптимизации трех критериев: максимизации прибыли от перевозки (как и было ранее в задании 2); минимизации износа оборудования и помещений; максимизации роста репутации фирмы.
1. Определить оптимальные планы и значения критериев при оптимизации по каждому из них.
2. Определить оптимальный план методом свертки (взвешивания критериев). Вес первого критерия положить равным 5, второго 3, третьего 2. При взвешивании провести операцию обезразмеривания, поделив значения целевых функций на их максимальный коэффициент. Оценить значения критериев при таком подходе. Насколько они далеки от оптимальных при соответствующей однокритериальной оптимизации?
3. Определить оптимальный план методом последовательных уступок. Уступка по первому критерию может составлять не более 20%, по второму – не более 35%. Оценить значения критериев при таком подходе. Как они отличаются от значений, определенных другими способами? Во всех случаях записать четкий ответ, представляющий собой развернутое управленческое решение для поставленной экономической проблемы.
Wт |
Wп |
Wх |
Hт |
Hп |
Hх |
300 |
100 |
700 |
5 |
7 |
4 |
Решение:
Составим экономико-математическую модель задачи. Для этого обозначим – количество тысяч телевизоров, – количество тысяч пылесосов, – количество тысяч холодильников. Эта задача является задачей оптимального использования сырья, поэтому система ограничений имеет вид:
(1)
. (2)
Целевые функции равны:
(3)
Будем оформлять все вычисления в таблице Excel:
ресурсы |
T1 |
T2 |
T3 |
ЗАПАСЫ |
ЗАТРАТЫ |
ОСТАТКИ |
|
|
|
P1 |
3 |
3 |
5 |
1850 |
1744 |
-328,571 |
|
|
|
P2 |
6 |
2 |
5 |
2300 |
1296 |
-203,571 |
|
|
|
P3 |
8 |
5 |
3 |
2480 |
2480 |
-111,429 |
|
Уступки |
|
ДОХОД |
4 |
3 |
6 |
MAX |
1824 |
5 |
0,1667 |
20% |
|
АМОРТИЗАЦИЯ |
300 |
100 |
700 |
MIN |
100800 |
-3 |
0,0014 |
35% |
|
ПОПУЛЯРНОСТЬ |
5 |
7 |
4 |
MAX |
3456 |
2 |
0,1429 |
|
|
ПЛАН |
0 |
448 |
80 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
CВЕРТКА |
2075,42857 |
ДОХОД |
|
|
|
ДОХОД |
2280 |
|
|
|
|
ПЛАН |
150 |
0 |
280 |
АМОРТИЗАЦИЯ |
241000 |
|
|
|
|
|
|
|
|
ПОПУЛЯРНОСТЬ |
1870 |
|
|
Оптим. |
С уступкой |
|
|
|
|
|
|
|
Доход |
2280 |
1824 |
АМОРТИЗАЦИЯ |
|
|
|
ДОХОД |
0 |
|
Аморт |
100800 |
136080 |
ПЛАН |
0 |
0 |
0 |
АМОРТИЗАЦИЯ |
0 |
|
|
|
|
|
|
|
|
ПОПУЛЯРНОСТЬ |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ПОПУЛЯРНОСТЬ |
|
|
|
ДОХОД |
1488 |
|
|
|
|
ПЛАН |
0 |
496 |
0 |
АМОРТИЗАЦИЯ |
49600 |
|
|
|
|
|
|
|
|
ПОПУЛЯРНОСТЬ |
3472 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Свертка |
|
|
|
ДОХОД |
1963,125 |
|
|
|
|
ПЛАН |
0 |
428,125 |
113,125 |
АМОРТИЗАЦИЯ |
122000 |
|
|
|
|
|
|
|
|
ПОПУЛЯРНОСТЬ |
3449,375 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Уступки |
|
|
|
ДОХОД |
1824 |
80,00% |
|
|
|
ПЛАН |
0 |
448 |
80 |
АМОРТИЗАЦИЯ |
100800 |
41,83% |
|
|
|
|
|
|
|
ПОПУЛЯРНОСТЬ |
3456 |
184,81% |
|
|
|