Задачи оптимизации при принятии решения

Рис.8. Исходные данные к задаче о максимальном потоке

Исходные данные о транспортной системе, например, внутризаводской, приведенные  на рис.8, можно также задать таблицей (табл.5).

Решение задачи о максимальном потоке может быть получено из следующих  соображений.

Очевидно, максимальная пропускная способность транспортной системы  не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3.

Таблица 5.

Исходные данные к задаче о максимальном потоке

Пункт отправления	Пункт назначения	Пропускная способность
0	1	2
0	2	3
0	3	1
1	2	4
1	3	1
1	4	3
2	3	1
2	4	2
3	4	2

 

 

Далее надо добиться, чтобы  все 6 вышедших из пункта 0 единиц груза  достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить  в пункт 4. Пришедшие в пункт 2 грузы  придется разделить: 2 единицы сразу  направить в пункт 4, а 1 единицу - в промежуточный пункт 3 (из-за ограниченной пропускной способности участка  между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 2. Их направляем в пункт 4.

Итак, максимальная пропускная способность рассматриваемой транспортной системы - 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между  пунктами 1 и 3. Не догружена ветка  между пунктами 1 и 4 - по ней направлены 2 единицы груза при пропускной способности в 3 единицы.

Решение можно представить  в виде таблицы (табл.6).

Таблица 6.

Решение задачи о максимальном потоке

Пункт отправления	Пункт назначения	План перевозок	Пропускная способность
0	1	2	2
0	2	3	3
0	3	1	1
1	2	0	4
1	3	0	1
1	4	2	3
2	3	1	1
2	4	2	2
3	4	2	2

Задача линейного  программирования при максимизации потока. Дадим формулировку задачи о максимальном потоке в терминах линейного программирования. Пусть Х_KM - объем перевозок из пункта К в пункт М. Согласно рис.8 К = 0,1,2,3, М = 1,2,3,4, причем перевозки возможны лишь в пункт с большим номером. Значит, всего имеется 9 переменных Х_{KM ,} а именно,  Х_{01 ,} Х_{02 ,} Х_{03 ,} Х_{12 ,} Х_{13 ,} Х_{14 ,} Х_{23 ,} Х_{24 ,} Х₃₄ . Задача линейного программирования, нацеленная на максимизацию потока, имеет вид:  

F   → max , 

Х₀₁ + Х₀₂   + Х₀₃ = F (0) 

- Х₀₁ + Х₁₂  + Х₁₃ + Х₁₄  = 0 (1) 

- Х₀₂ - Х₁₂  + Х₂₃ + Х₂₄ = 0 (2) 

- Х₀₃  - Х₁₃   - Х₂₃ + Х₃₄ = 0 (3) 

- Х₁₄   - Х₂₄   - Х₃₄  = - F (4)

Х₀₁  ≤ 2 

Х₀₂  ≤ 3 

Х₀₃  ≤ 1 

Х₁₂  ≤ 4 

Х₁₃  ≤ 1 

Х₁₄  ≤ 3 

Х₂₃  ≤ 1 

Х₂₄  ≤ 2 

Х₃₄  ≤ 2 

Х_КМ  ≥ 0 , К, М = 0, 1, 2, 3, 4

F ≥ 0 . 

Здесь F - целевая функция, условие (0) описывает вхождение грузов в транспортную систему. Условия (1) - (3) задают балансовые соотношения для узлов 1- 3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен выходящему потоку, грузы не скапливаются внутри и системы и не "рождаются" в ней. Условие (4) - это условие "выхода" грузов из системы. Вместе с условием (0) оно составляет балансовое соотношение для системы в целом ("вход" равен "выходу"). Следующие девять неравенств задают ограничения на пропускную способность отдельных "веток" транспортной системы. Затем в системе ограничений задачи линейного программирования указана неотрицательность объемов перевозок и целевой функции. Ясно, что последнее неравенство вытекает из вида целевой функции (соотношения (0) или (4)) и неотрицательности объемов перевозок. Однако последнее неравенство несет некоторую общую информацию - через систему может быть пропущен либо положительный объем грузов, либо нулевой (например, если внутри системы происходит движение по кругу), но не отрицательный (он не имеет экономического смысла, но формальная математическая модель об этом "не знает").

О многообразии оптимизационных  задач. В различных проблемах принятия решений возникают самые разнообразные задачи оптимизации. Для их решения применяются те или иные методы, точные или приближенные. Задачи оптимизации часто используются в теоретико-экономических исследованиях. Достаточно вспомнить оптимизацию экономического роста страны с помощью матрицы межотраслевого баланса Василия Леонтьева или микроэкономические задачи определения оптимального объема выпуска по функции издержек при фиксированной цене (или в условиях монополии) или минимизации издержек при заданном объеме выпуска путем выбора оптимального соотношения факторов производства (с учетом платы за них).

Кроме затронутых выше методов  решения задач оптимизации, напомним о том, что гладкие функции  оптимизируют, приравнивая 0 производную (для функций нескольких переменных - частные производные). При наличии  ограничений используют множители  Лагранжа. Эти методы обычно излагаются в курсах высшей математики и потому опущены здесь.

Представляют интерес  задачи оптимизации  с нечеткими переменными [5], а также задачи оптимизации, возникающие в эконометрике [6]. Они рассматриваются в соответствующей литературе.

Литература

1. Гасс С. Путешествие  в страну линейного программирования / Пер. с англ. - М.: Мир, 1973. - 176 с. 

2. Кофман А., Фор Р. Займемся  исследованием операций / Пер. с  франц.. - М,: Мир, 1966. -280 с.

3. Белов В.В., Воробьев  Е.М., Шаталов В.Е. Теория графов. - М.: Высшая школа, 1976. - 392 с.

4. Бурков В.Н., Заложнев  А.Ю., Новиков Д.А. Теория графов в управлении организационными системами. – М.: Синтег, 2001. – 124 с.

5. Орлов А.И. Задачи  оптимизации и нечеткие переменные. – М.: Знание, 1980. – 64 с.

6. Орлов А.И. Эконометрика. – М.: Изд-во «Экзамен», 2002. – 576 с.

Задачи по методам  принятия решений

1. Изобразите на плоскости  ограничения задачи линейного  программирования и решите (графически) эту задачу:  

400 W₁ + 450 W₂ → min ,   

5 W₁ + 10 W₂ ≥ 45,  

20 W₁ + 15 W₂ ≥ 80,  

W₁ ≥ 0, W₂ ≥  0.

2. Решите задачу линейного  программирования:  

W₁ + 5 W₂ → max ,   

0,1 W₁ + W₂ ≤ 3,8 ,   

0,25 W₁ + 0,25 W₂ ≤ 4,2 ,   

W₁ ≥ 0 , W₂ ≥ 0 . 

3. Решите задачу целочисленного  программирования:  

10 Х + 5 У → max .  

8 Х + 3 У ≤ 40,  

3 Х + 10 У ≤ 30,   

Х ≥ 0 , У ≥ 0 , Х и У - целые числа.

4. Решите задачу о ранце:

Х₁ +  Х₂ + 2 Х₃ + 2Х₄ + Х₅ + Х₆  → max ,

0,5 Х₁ + Х₂ + 1,5 Х₃ + 2Х₄ + 2,5Х₅ + 3Х₆    ≤ 3.

Управляющие параметры Х_k, k = 1,2,…, 6 , принимают значения из множества, содержащего два элемента - 0 и 1.

5. Транспортная сеть (с  указанием расстояний) приведена  на рис.9. Найдите кратчайший путь из пункта 1 в пункт 4.

4

Рис.9. Исходные данные к задаче о кратчайшем пути.

7. Решите задачу коммивояжера  для четырех городов (маршрут  должен быть замкнутым и не  содержать повторных посещений). Затраты на проезд приведены  в табл.7.

Таблица 7.

Исходные данные к задаче коммивояжера

Город отправления	Город назначения	Затраты на проезд
А	Б	2
А	В	1
А	Д	5
Б	А	3
Б	В	2
Б	Д	1
В	А	4
В	Б	1
В	Д	2
Д	А	5
Д	Б	3
Д	В	3

8. Как послать максимальное  количество грузов из начального  пункта 1 в конечный пункт 8, если  пропускная способность путей  между пунктами транспортной  сети (рис.10) ограничена (табл.8)?

Рис.9. Транспортная сеть к  задаче о максимальном потоке.

Таблица 8. 

Исходные данные к задаче о максимальном потоке

Пункт отправления	Пункт назначения	Пропускная способность
1	2	1
1	3	2
1	4	3
2	5	2
3	2	2
3	4	2
3	6	1
4	7	4
5	8	3
6	5	2
6	7	1
6	8	1
7	8	3

Темы докладов и рефератов

1.              Классификация оптимизационных задач принятия решений.

2.              Решения, оптимальные по Парето.

3.              Многокритериальные задачи принятия решений: различные методы свертки критериев.

4.              Задачи оптимизации и нечеткие переменные (на основе работы [5]).

5.              Моделирование и экспертные оценки при принятии решений.

6.              Интерактивные системы принятия решений.

7.              Методы учета неопределенностей принятия решений: вероятностные модели, теория нечеткости, интервальная математика.

8.              Эконометрические методы принятия решений (на основе монографии [6]).

9.              Имитационное моделировании и метод статистических испытаний (Монте-Карло) при принятии решений.

10.          Декомпозиция задач принятия решений.

11.             Методы теории игр (теория конфликтов), роль информации и равновесие по Нэшу в теории принятия решений.

12.              Проблемы комбинированного применения различных методов в конкретных прикладных работах.

13.              Информационные технологии поддержки принятия решений.