- •Варианты заданий к контрольной работе
- •Задание № 1. Оптимизация методом линейного программирования
- •Вариант 1
- •Вариант 2
- •Вариант 3
- •Вариант 4
- •Вариант 5
- •Вариант 6
- •Вариант 7
- •Вариант 8
- •Вариант 9
- •Вариант 10
- •Вариант 11
- •Вариант 12
- •Вариант 13
- •Вариант 14
- •Задание № 2. Многокритериальная оптимизация. Аналитический иерархический процесс (АИП)
- •Вариант 1
- •Вариант 2
- •Вариант 3
- •Вариант 4
- •Вариант 5
- •Вариант 6
- •Вариант 7
- •Вариант 8
- •Вариант 9
- •Вариант 10
- •Вариант 11
- •Вариант 12
- •Вариант 13
- •Вариант 14
- •Задание № 3. Принятие решений в условиях риска и неопределенности
- •Вариант 1
- •Вариант 2
- •Вариант 3
- •Вариант 4
- •Вариант 5
- •Вариант 6
- •Вариант 7
- •Вариант 8
- •Вариант 9
- •Вариант 10
- •Вариант 11
- •Вариант 12
- •Вариант 13
- •Вариант 14
- •Методические указания к выполнению контрольной работы
- •1. Оптимизация методом линейного программирования
- •1.1. Общая характеристика задачи линейного программирования
- •1.2. Решение задач линейного программирования с использованием Microsoft Excel
- •1.3. Анализ оптимального решения на чувствительность в MS Excel
- •1.4. Двойственная задача линейного программирования
- •2. Многокритериальная оптимизация. Аналитический иерархический процесс (АИП)
- •3. Принятие решений в условиях риска. Критерий максимизации ожидаемого дохода
- •Список литературы
28
Рис. 1.10. Экранная форма задачи (1.1) после получения решения
1.3. Анализ оптимального решения на чувствительность в MS Excel
Для анализа полученного оптимального решения в MS Excel предусмотрены три типа отчетов: отчет по результатам, устойчивости и пределам.
Проведем анализ чувствительности задачи (1.1). Для этого необходимо после запуска в Excel задачи на решение в окне Результаты поиска решения выделить с помощью мыши три типа отчетов: Результаты, Устойчивость и Пределы (рис. 1.11).
Рис. 1.11. Типы отчетов Отчет по результатам. Отчет по результатам состоит из трех таблиц (рис.1.12):
1)таблица 1 содержит информацию о целевой функции;
2)таблица 2 содержит информацию о значениях переменных, полученных в результате решения задачи;
3)таблица 3 показывает результаты оптимального решения для ограничений и для граничных условий.
Для ограничений в столбце Формула приведены зависимости, которые были введены в диалоговое окно Поиск решения; в столбце Значение приведены величины использованного ресурса.
29
Рис. 1.12. Лист отчета по результатам
Если ресурс используется полностью (то есть ресурс дефицитный), то в графе Статус соответствующее ограничение указывается как «связанное»; при неполном использовании ресурса (то есть ресурс недефицитный) в этой графе указывается «не связан.».
Для граничных условий (строки 24-27 на рис. 1.12) в графе Разница показана разность между значением переменной в найденном оптимальном решении и заданным для нее граничным условием.
Таблица 3 отчета по результатам дает информацию для анализа возможного изменения запасов недефицитных ресурсов при сохранении полученного оптимального значения целевой функции.
Так, если на ресурс наложено ограничение типа ≥, то в графе Разница дается количество ресурса, на которое была превышена минимально необходимая норма.
Если на ресурс наложено ограничение типа ≤, то в графе Разница дается количество ресурса, которое не используется при реализации оптимального решения.
Отчет по устойчивости. Отчет по устойчивости состоит из двух таблиц (рис.1.13). Таблица 1 содержит информацию, относящуюся к переменным:
-результирующие значения переменных;
-нормированная стоимость, т.е. дополнительные двойственные переменные, которые показывает, на сколько изменяется целевая функция при принудительном включении единицы этой переменной в оптимальное решение;
-коэффициенты целевой функции;
-допустимые значения приращения коэффициентов целевой функции, при которых сохраняется первоначальное оптимальное решение.
30
Рис. 1.13. Отчет по устойчивости Таблица 2 (рис. 1.13) содержит информацию, относящуюся к ограничениям:
-величина использованных ресурсов в колонке Результ. значение;
-теневые цены, т.е. двойственные оценки, которые показывают, как изменится целевая функция при изменении ресурсов на единицу. Теневая цена рассчитывается только для дефицитных ресурсов;
-значения приращения ресурсов, при которых сохраняется оптимальный набор переменных, входящих в оптимальное решение.
Отчет по пределам. В отчете пределам (рис. 1.14) показано, в каких пределах может изменяться выпуск продукции, вошедшей в оптимальное решение, при сохранении структуры оптимального решения.
Рис. 1.14. Отчет по пределам
1.4. Двойственная задача линейного программирования
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче.
Прямая задача |
Двойственная задача |
Целевая функция |
Целевая функция |
L(X )= c1x1 + c2 x2 +... + cn xn → max (min), |
F(Z )=b1z1 +b2 z2 +...+bm zm →min (max), |
31
|
|
|
|
при ограничениях |
|
|
|
|||||||||||
a |
|
x |
|
+a |
|
x |
2 |
+...+a |
|
x |
n |
≤(≥,=)b |
, |
|
||||
11 1 |
|
12 |
|
|
1n |
|
|
|
1 |
|
|
|||||||
a21x1 +a22 x2 +...+a2n xn |
≤(≥,=)b2 , |
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
... |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
|
x |
|
+a |
m2 |
x |
2 |
+...+a |
mn |
x |
n |
≤ |
(≥,=)b |
, |
||||
|
m1 1 |
|
|
|
|
|
|
m |
|
|||||||||
x |
j |
≥ |
0 (j =1,...,n). |
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
при ограничениях |
|
|
|||||||||||||
a |
|
z |
+a |
21 |
z |
2 |
+...+a |
m1 |
z |
m |
≤(≥,=)c |
, |
|||||||
|
11 |
1 |
|
|
|
|
|
|
1 |
|
|
||||||||
a12 z1 +a22 z2 +...+am2 zm ≤(≥,=)c2 , |
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
... |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
|
z |
+a |
2n |
z |
2 |
+...+a |
mn |
z |
m |
≤ (≥,=)c |
n |
, |
||||||
|
1n |
1 |
|
|
|
|
|
|
|
|
|
||||||||
z |
i |
≥ 0 (i =1,...,m). |
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рассмотрим задачу линейного программирования (1.1):
L (X )=130,5x1 +20x2 +56x3 +87,8x4 →max;−1,8x1 +2x2 + x3 −4x4 =756,
−6x1 +2x2 +4x3 − x4 ≥ 450,
4x 1−1,5x2 +10,4x3 +13x4 ≤89,x j ≥0; j =1,4.
В сформулированной задаче |
неравенство −6x1 +2x2 +4x3 − x4 ≥ 450 эквивалентно |
|
неравенству |
6x1 −2x2 −4x3 + x4 |
≤ 450 , а равенство −1,8x1 +2x2 + x3 −4x4 =756 можно |
представить |
как два неравенства: |
−1,8x1 +2x2 + x3 −4x4 ≤756 и 1,8x1 −2x2 − x3 +4x4 ≤−756. |
Таким образом, рассматриваемую задачу линейного программирования можно представить в виде (1.4):
L (X )=130,5x1 +20x2 +56x3 +87,8x4 |
→max; |
||||||||||||||||||||
−1,8x |
+2x |
2 |
+ x |
3 |
−4x |
4 |
≤756, |
|
|||||||||||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
1,8x1 − |
2x2 − x3 +4x4 ≤ −756 |
(1.4). |
|||||||||||||||||||
|
−2x2 −4x3 + x4 |
≤ −450, |
|||||||||||||||||||
6x1 |
|
||||||||||||||||||||
4x |
1 |
− |
1,5x |
2 |
+ |
10,4x |
3 |
+13x |
4 |
≤89, |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
j =1,4. |
|
|
|
|
|
|
|
|
|
|
|||||||
x j ≥0; |
|
|
|
|
|
|
|
|
|
|
|
||||||||||
Поэтому двойственная задача имеет следующий вид (1.5): |
|||||||||||||||||||||
F (Z )=756z1 −756z2 −450z3 +89z4 |
→min; |
||||||||||||||||||||
−1,8z1 +1,8z2 +6z3 +4z4 |
≥130,5, |
|
|||||||||||||||||||
|
|
|
|
2z2 −2z3 −1,5z4 ≥ 20 |
|
||||||||||||||||
2z1 − |
(1.5) |
||||||||||||||||||||
|
− z |
2 −4z3 +10,4z4 |
≥56 |
||||||||||||||||||
z1 |
|
||||||||||||||||||||
− |
4z |
1 |
+4z |
2 |
+ x |
3 |
+13z |
4 |
≥ |
87,8, |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
≥0; i =1,4. |
|
|
|
|
|
|
|
|
|
|
|||||||||||
zi |
|
|
|
|
|
|
|
|
|
|
Схема формирования двойственной задачи приведена на рисунке 1.15. Коэффициенты прямой целевой функции становятся правой частью ограничений. Правая часть ограничений становится коэффициентами новой целевой функции. Матрица коэффициентов ограничений транспонируется.
32
Рис. 1.15. Схема формирования двойственной задачи Ввод зависимостей для двойственной задачи показан на рисунке 1.16.
Рис. 1.16. Ввод зависимостей для двойственной задачи Левая часть ограничений представляет собой произведение матрицы коэффициентов
ограничений на вектор переменных. Целевая функция записывается как произведение транспонированного вектора коэффициентов целевой функции на вектор переменных.
Ограничения приведены на рисунке 1.17 в окне Поиск решения. Это положительность переменных и то, что вектор левой части ограничений должен быть больше вектора из правой части. Для целевой ячейки устанавливаем флажок минимизации.
33
Рис. 1.17. Окно Поиск решения с ограничениями для двойственной задачи Результаты решения двойственной задачи приведены на рисунке 1.18.
Рис. 1.18. Решение для двойственной задачи Открыв отчет по устойчивости (рис. 1.19), можно увидеть новые двойственные
оценки (в столбце Теневая цена) и убедиться, что значения переменных при решении задачи на максимизацию становятся двойственными оценками при задаче на минимизацию, и наоборот (сравните с рисунком 1. 13).
Рис. 1.19. Отчет по устойчивости для двойственной задачи