Задача о диете (упрощенный вариант). Лекции Задачи оптимизации при принятии решений

• Название: Лекции Задачи оптимизации при принятии решений
• Анкор: Задача о диете (упрощенный вариант)
• Дата: 03.06.2022
• Размер: 441.46 Kb.
• Имя файла: Zadanie2.docx
• Тип: Лекции; #566651
• страница: 3 из 3

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

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

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

Не догружены ветки:

- между пунктами 3 и 2 - по ней направлена 1 единица груза при пропускной способности в 2 единицы;

- между пунктами 4 и 7 - по ней направлены 3 единицы груза при пропускной способности в 4 единицы;

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

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

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

РЕШЕНИЕ:
Требуется посетить все вершины графа и вернуться в исходную вершину, минимизировав затраты на проезд.

Д

В

Б

А

Каждые две вершины соединяют две дуги - туда и обратно.

1. Построение матрицы с исходными данными 

Затраты на проезд между городами города представим в виде следующей таблицы:

Город	А	Б	В	Д
А	-	2	1	5
Б	3	-	2	1
В	4	1	-	2
Д	5	3	3	-

2. Нахождение минимума по строкам 

Находим минимальное значение в каждой строке (di) и выписываем его в отдельный столбец.

Город	А	Б	В	Д	di
А	-	2	1	5	1
Б	3	-	2	1	1
В	4	1	-	2	1
Д	5	3	3	-	3

3. Редукция строк 

Производим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).

Город	А	Б	В	Д	di
А	-	1	0	4	1
Б	2	-	1	0	1
В	3	0	-	1	1
Д	2	0	0	-	3

4. Нахождение минимума по столбцам 

Далее находим минимальные значения в каждом столбце (dj). Эти минимумы выписываем в отдельную строку.

Город	А	Б	В	Д	di
А	-	1	0	4	1
Б	2	-	1	0	1
В	3	0	-	1	1
Д	2	0	0	-	3
dj	2	0	0	0	-

5. Редукция столбцов 

Вычитаем из каждого элемента матрицы соответствующее ему dj.

Город	А	Б	В	Д	di
А	-	1	0	4	1
Б	0	-	1	0	1
В	1	0	-	1	1
Д	0	0	0	-	3
dj	2	0	0	0	-

6. Вычисление оценок нулевых клеток 

Для каждой нулевой клетки получившейся преобразованной матрицы находим «оценку». Ею будет сумма минимального элемента по строке и минимального элемента по столбцу, в которых размещена данная нулевая клетка. Сама она при этом не учитывается. Найденные ранее di и dj не учитываются. Полученную оценку записываем рядом с нулем, в скобках.

Город	А	Б	В	Д
А	-	1	0 (1)	4
Б	0 (0)	-	1	0 (1)
В	1	0(1)	-	1
Д	0 (0)	0 (0)	0 (0)	-

7. Редукция матрицы 

Выбираем нулевую клетку с наибольшей оценкой. Заменяем ее на «М». Найдем один из отрезков пути. Выписываем его (от какого города к какому движемся, т.е. от А к В).

Город	А	Б	В	Д
А	-	1	M	4
Б	0 (0)	-	1	0 (1)
В	1	0(1)	-	1
Д	0 (0)	0 (0)	0 (0)	-

Оставшаяся часть пути очевидна.

А→В→Б→Д→А. Затраты на проезд составят 8.