Динамическое программирование. Оптимальное распределение ресурсов. Задача коммивояжера

 

i  j	4	5	6	di
1	2	0(2)	M	2
2	0(2)	M	0(1)	0
4	M	0(1)	1	1
dj	2	0	1	0

Максимальное значение 2 дает отказ от узла (1,5). Следовательно, включаем в маршрут движения участок 1"5. При этом отказ от участка приводит к увеличению стоимости проезда, таким образом Н + d(1,5) = 107 + 2 = 109.

10.После выбора узла (1,5) вычеркиваем 1-ую строку и 5-ый столбец, при этом запретим возврат 5-го пункта в 1-ый. Получим матрицу:

i  j	4	6	di
2	0	0	0
4	M	1	1
dj	0	0	1

 

Сумма констант приведения сокращенной  матрицы:

 ∑d_i + ∑d_j =1

Нижняя граница (1,5) равна:

 H₁ (1,5) = 107 + 1 = 108  <  109

 

 В соответствии с этой  матрицей включаем в маршрут  (2,4) и (4,6).

 В результате по дереву  ветвлений цикл образуют узлы:

 (6,1), (1,5), (5,3), (3,2), (2,4), (4,6). 
Последовательность объезда городов: 6"1"5"3"2"4"6

Стоимость проезда по этому пути равна 108.

Длина маршрута равна = (6,1) + (1,5) + (5,3) + (3,2) + (2,4) + (4,6) =108 

 

 

 

 

Оптимальным маршрутом коммивояжера будет маршрут F " A " E " C "B"D"А

 

 

Заключение

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

 

Решив задачу методом динамического  программирования, мы получили оптимальное  решение - максимум эффекта при ограничениях по объему ресурсов и потребности  в них.

 

2. Задача коммивояжера

Сравнивая две решенные задачи, мы видим, что после того как переменные были изменены, изменился и маршрут, в связи с этим и длина маршрута, а также его стоимость. В первой задаче путь был короче, а стоимость проезда меньше.

Метод ветвей и границ позволяет  найти оптимальное решении быстро и точно. Метод удобен и прост. Для практической реализации идеи метода ветвей и границ применительно к задаче коммивояжера нужно найти метод определения нижних границ подмножества и разбиения множества гамильтоновых контуров на подмножества (ветвление). Такое определение нижних границ базируется на том утверждении, что если ко всем элементам i-й строки или j-го столбца матрицы C прибавить или отнять число , то задача останется эквивалентной прежней, то есть оптимальность маршрута коммивояжера не изменится, а длина любого гамильтонова контура изменится на данную величину .

Используя ЭВМ, методом ветвей и  границ можно решить задачи коммивояжера для  .

 

Список литературы: 
1.А..Т. Надев, О. С. Данилова, Е. С. Прохорова «Разработка управленческих решений», (Н.Новгород, ВВАГС, 2007г).

2. Н. В. Глебова «Применение  методов линейного программирования  для решения экономических задач  (Учебно-методическое пособие, Н.  Новгород, ВВАГС, 2001 г.)