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

Рис. 9.5.

Восьмая итерация

Седьмая итерация

Шестая итерация

Ш А Г 2. Находим Г(х₉) = {х₁, х₂, х₆, х₇, х₈}. Метка вершины х₆ временная, следовательно пересчитываем ее значение:

L(х₆) = min [17, 11 + 9] = 17.

Ш А Г 3. На данном шаге итерации имеем следующие временные метки вершин:

L(х₃) = 23, L(х₅) = 12, L(х₆) = 17.

Очевидно, что минимальную метку, равную 12 имеет вершина х₅.

Ш А Г 4. За следующую текущую метку принимаем вершину х₅, т. е. p = х₅, а ее метка становится постоянной, L(х₅) = 12⁺.

Ш А Г 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу 2.

Ш А Г 2. Находим Г(х₅) = { х₄, х₆ }. Метка вершины х₆ временная, следовательно, пересчитываем ее значение:

L(х₆)= min [17, 12 + 10 ] = 17.

Ш А Г 3. На данном шаге итерации имеем следующие временные метки:

L(х₃) = 23, L(х₆) = 17.

Очевидно, что минимальную метку, равную 17 имеет вершина х₆.

Ш А Г 4. За следующую текущую метку принимаем вершину х₆, т. е. p = х₆, а ее метка становится постоянной, L(х₆) = 17⁺.

Ш А Г 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу 2.

Ш А Г 2. Находим Г(х₆) = { х₃, х₅, х₇, х₈, х₉ }. Метка вершины х₃ временная, следовательно, пересчитываем ее значение:

L(х₃) = min [ 23, 17 + 20 ] = 23.

Ш А Г 3. На данном шаге итерации имеем одну временную метку вершины: L(х₃) = 23, которая становится постоянной.

Ш А Г 4. Все вершины имеют постоянные метки, поэтому алгоритм окончен.

Для нахождения кратчайшего пути между вершинами, например, х₂ и начальной х₁ последовательно используем соотношение (**): L(x^'₂)+c(x^'₂,x₂)=L(x₂)=5, где вершина x^'₂ – это вершина, непосредственно предшествующая х₂ в кратчайшем пути от х₁ к х₂.

Единственной такой вершиной является вершина х₇. Далее соотношение (**) применяем второй раз:

L(x₇')+ с(x₇’, x₇) = L(x₇) = 3

Единственной такой вершиной является вершина х₁. Поэтому кратчайший путь от х₁ к х₂ есть (х₁, х₇, х₂). Вершина х₁, называемая базой и дающая все кратчайшие пути от х₁ представляет дерево.

Рассмотрим несколько типичных задач принятия решений, связанных с оптимизацией на графах.

Задача коммивояжера. Требуется посетить все вершины графа и вернуться в исходную вершину, минимизировав затраты на проезд (или минимизировав время).

Исходные данные здесь - это граф, дугам которого приписаны положительные числа - затраты на проезд или время, необходимое для продвижения из одной вершины в другую. В общем случае граф является ориентированным, и каждые две вершины соединяют две дуги - туда и обратно. Действительно, если пункт А расположен на горе, а пункт Б - в низине, то время на проезд из А в Б, очевидно, меньше времени на обратный проезд из Б в А.

Многие постановки экономического содержания сводятся к задаче коммивояжера. Например:

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

Задача о кратчайшем пути. Как кратчайшим путем попасть из одной вершины графа в другую? В терминах производственного менеджмента: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из пункта А в пункт Б? Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число - время движения по этой дуге от начальной вершины до конечной. Рассмотрим пример (рис. 8.7).

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

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

Таблица 8.4. Исходные данные к задаче о кратчайшем пути
Начало дуги	Конец дуги	Время в пути

как кратчайшим путем попасть из вершины 1 в вершину 4?

Решение. Введем обозначение: С(Т) - длина кратчайшего пути из вершины 1 в вершину Т. (Поскольку любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается.) Рассматриваемая задача состоит в вычислении С(4) и указании пути, на котором этот минимум достигается.

Для исходных данных, представленных на pис. 8.7 и в табл. 8.4, в вершину 3 входит только одна стрелка, как раз из вершины 1, и около этой стрелки стоит ее длина, равная 1, поэтому. Кроме того, очевидно, что.

В вершину 4 можно попасть либо из вершины 2, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 5. Поэтому справедливо соотношение

Таким образом, проведена реструктуризация (упрощение) задачи - нахождение сведено к нахождению и.

В вершину 5 можно попасть либо из вершины 3, пройдя путь, равный 2, либо из вершины 6, пройдя путь, равный 3. Поэтому справедливо соотношение

Мы знаем, что. Поэтому

Поскольку очевидно, что - положительное число, то из последнего соотношения вытекает, что.

В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение

Нам известно, что. Поэтому

Теперь мы можем найти:

Таким образом, длина кратчайшего пути равна 8. Из последнего соотношения ясно, что в вершину 4 надо идти через вершину 5. Возвращаясь к вычислению С(5), видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно попасть только из вершины 1. Итак, кратчайший путь таков:

Задача о кратчайшем пути для конкретных исходных данных (рис. 8.7 и табл. 8.4) полностью решена.

Оптимизационные задачи на графах, возникающие при подготовке управленческих решений в производственном менеджменте, весьма многообразны. Рассмотрим в качестве примера еще одну задачу, связанную с перевозками.

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

Для решения этой задачи каждой дуге ориентированного графа, соответствующего транспортной системе, должно быть сопоставлено число - пропускная способность этой дуги. Рассмотрим пример (рис. 8.8).

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

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

Таблица 8.5. Исходные данные к задаче о максимальном потоке
Пункт отправления	Пункт назначения	Пропускная способность

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

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

Далее надо добиться, чтобы все 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 единицы.

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

Таблица 8.6. Решение задачи о максимальном потоке
Пункт отправления	Пункт назначения	План перевозок	Пропускная способность

Задача линейного программирования при максимизации потока.

Дадим формулировку задачи о максимальном потоке в терминах линейного программирования. Пусть ХKM - объем перевозок из пункта К в пункт М. Согласно рис. 8.8, причем перевозки возможны лишь в пункт с большим номером. Значит, всего имеется 9 переменных, а именно, Задача линейного программирования, нацеленная на максимизацию потока, имеет вид:

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

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

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

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

и - целые числа.

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

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

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

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

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

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

Таблица 8.7. Исходные данные к задаче о максимальном потоке
Пункт отправления	Пункт назначения	Пропускная способность

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

Таблица 8.8. Исходные данные к задаче коммивояжера
Город отправления	Город назначения	Затраты на проезд
А	Б
А	В
А	Д
Б	А
Б	В
Б	Д
В	А
В	Б
В	Д
Д	Ф
Д	Б
Д	В

Добавить построение дерева и т.д. по Девяткову