Пример. В этой задаче n=2, b=3, поэтому таблица с результатами вычислений будет иметь вид:

Решить задачу:

u₁+2u₂-> max

2u₁+u₂ £ 3

u₁, u₂ - целые.

В этой задаче n =2, b =3, поэтому таблица с результатами вычислений будет иметь вид:

 

x	i=0	i=1	i=2
	W0	u1	W1	u2	W2
0	6	0	6	3	0
1			4	2	0
2			2	1	0
3			0	0	0

 

Запишем соотношение Беллмана:

W_i(x)= max (C_i+1u+W_i+1(x+A_i+1u)), uÎ U_i+1(x),

u_i+1(x) = {0, 1,..., [(b-x)/A_i+1]},

u _i+1(x)= argmax{ C_i+1u+W_i+1(x+A_i+1u)| uÎ U _i(x)}.

 

Первый этап:

W₂(x)=0, xÎ {0, 1, 2, 3} - (смотри последний столбец предыдущей таблицы)

W₁(x)= max[ 2u+W₂(x+u)], xÎ {0, 1, 2, 3}, uÎ U₂(x), U₂(0)={0, 1, 2, 3},

W₁(0)=max[0, 2, 4, 6]=6, u₂(0)=3, U₂(1)={0, 1, 2},

W₁(1)= max[0, 2, 4]=4, u ₂(1)=2, U₂(2)= {0, 1},

W₁(2)= max[0, 2]=2, u ₂(2)=1, U₂(3)={0},

W₁(3)=max[0]=0, u ₂(3)=0,

W₀(x)= max[ u+W₁(x+2u)], uÎ U₁(x_i), U₁(0)={0, 1}

W₀(0)= max[u+ W₁(0+2u)]=max[6, 5]=6, uÎ {0, 1}, u ₁(0)=0.

Второй этап:

x₀? =0, u₁? =u₁(x₀?)=u₁(0)=0, x₁? =x₀? +A₁u₁? =0;

u₂=u₂(x₁)=u₂(0)=3, x₂=x₁+A₂u₂=3.

Итак, значение функционала составит W₀ (0)=6, при этом

u₁=0, u₂=3; x₀=0, x₁=0, x₂=3.

 

Задание 10

Решить задачу о ранце при n=5, b=8, значения c(i), a(i), iÎ [1..n], взять из следующей таблицы в соответствии с номером варианта.

 

N	C	A
	2, 4, 4, 3, 1.	2, 5, 3, 3, 4
	3, 4, 5, 2, 2	2, 3, 4, 5, 1
	4, 5, 2, 2, 3	3, 4, 5, 1, 2
	5, 2, 2, 3, 4	4, 5, 1, 2, 3
	2, 2, 3, 4, 5	5, 1, 2, 3, 4
	2, 3, 4, 5, 2	1, 2, 3, 4, 5
	2, 4, 3, 5, 1	2, 5, 1, 3, 4
	4, 3, 5, 1, 2,	5, 1, 3, 4, 2
	3, 5, 1, 2, 4	1, 3, 4, 2, 5
	4, 5, 1, 2, 3	3, 4, 2, 5, 1
	5, 1, 2, 3, 4	4, 2, 5, 1, 3
	5, 1, 3, 2, 4	4, 2, 5, 3, 1
	1, 3, 2, 4, 5	2, 5, 3, 1, 4
	3, 2, 4, 5, 1	5, 3, 1, 4, 2
	2, 4, 5, 1, 3	3, 1, 4, 2, 5
	4, 5, 1, 3, 2	1, 4, 2, 5, 3
	5, 1, 3, 2, 4	4, 2, 5, 3, 1
	1, 3, 2, 4, 5	2, 5, 3, 1, 4
	3, 2, 4, 5, 1	5, 3, 1, 4, 2
	2, 4, 5, 1, 3	3, 1, 4, 2, 5
	4, 5, 3, 1, 2	1, 4, 5, 2, 3
	5, 3, 1, 2, 4	4, 5, 2, 3, 1
	3, 1, 2, 4, 5	5, 2, 3, 1, 4
	1, 2, 4, 5, 3	2, 3, 1, 4, 5
	2, 4, 5, 3, 1	3, 1, 4, 5, 2
	4, 5, 3, 1, 2	1, 4, 5, 2, 3

 

 

Результаты представить в виде таблицы

 

x

i=0

i=1

i=2

i=3

i=4

i=5

W0

u1

W1

u2

W2

u3

W3

u4

W4

u5

W5

0

1

2

3

4

5

6

7

8

 

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

Метод ветвей и границ для решения задачи о коммивояжере.

 

Пусть имеется (n+1) городов A(0), A(1), A(2), A(3),..., A(n). Между всеми парами городов известно расстояние c(i, j) ³ 0. Коммивояжер, который находится в городе A(0), должен обойти все города, побывав в каждом ровно один раз и вернуться в город A(0) так, чтобы длина пройденного пути была наименьшей.

Путь коммивояжера (i(0), i(1), i(2),..., i(n), i(0)) образует замкнутый маршрут. Его длина

l(i(0), i(1), i(2),..., i(n), i(0))=c(i(0), i(1))+c(i(1), i(2)) + c(i(2), i(3)) +...+c(i(n), i(0)).

Не трудно видеть, что число таких маршрутов равно n!. Для поиска минимального (оптимального) маршрута применим метод ветвей и границ. Общая схема этого метода приведена в лабораторной работе " Метод ветвей и границ (алгоритм Ленд и Дойга) для решения задач целочисленного линейного программирования". Дадим описание этого метода для задачи о коммивояжере.

Алгоритм.

Шаг 1. Задание множества X(0, 1) и вычисление оценки x(0, 1).

Множество X(0, 1) есть множество всех возможных маршрутов коммивояжера. Оценку x(0, 1 ) получаем, используя процедуру приведения матрицы C= (c(i, j)), iÎ [0..n], j Î [0..n], следующим образом.

Для всех iÎ [0..n], h(i): = min{c(i, j) | jÎ [0..n]},

c'(i, j): = c(i, j) - h(i), i Î [0..n], j Î [0..n].

Для всех jÎ [0..n], H(j): = min{c'(i, j) | iÎ [0..n]},

c" (i, j): = c'(i, j) - H(i), i Î [0..n], j Î [0..n].

Переменные h(i), H(j) называют коэффициентами приведения. Матрицу

C" = (c" (i, j)), iÎ [0..n], jÎ [0..n], называют приведенной матрицей.

Полагаем x(0, 1)=S {h(i) | iÎ [0..n] } +S {H(j) | jÎ [0..n] }.