Расчет потенциалов и проверка критерия оптимальности, переход к новому базису

Для базисных переменных должно выполняться v_j:= u_i+c_ij. Положим u ₁=0, тогда по этой формуле по клетке (1,2) v ₂=0+2=2, по клетке (1,2) v ₂=0+7=7. Из клетки (2,2) u ₂=7–4=3. Продолжая аналогичным образом, получим информацию, приведенную в следующей таблице

j= 1

j= 2

j= 3

j= 4

b 1

b 2

b 3

b 4

i= 1

a 1

u 1

i= 2

a 2

u 2

–7

i= 3

a 3

u 3

–6

–2

v 1

v 2

v 3

v 4

Подсчитываем значения d_ij по формуле d_ij = v_j–u_i–c_ij и заносим в таблицу. Для базисных клеток d_ij =0. В клетке (1,4) d_ij >0, поэтому включаем эту клетку в базис, но нам нужно определить клетку, выходящую из базиса. Выполним это на следующей таблице, в ней клетка (1,4) затемнена. Легко видеть, что затемненные клетки образуют цикл (1,4)Þ(3,4)Þ(3,3)Þ(2,3)Þ(2,2,)Þ(1,2)Þ(1,4)

j= 1

j= 2

j= 3

j= 4

b 1

b 2

b 3

b 4

i= 1

a 1

«+»

u 1

«–»

i= 2

a 2

u 2

–7

«+»

«–»

i= 3

a 3

u 3

–6

–2

«+»

«–»

v 1

v 2

v 3

v 4

Заносим в позицию q клетки значения «+» и «–». В каждой строке и в каждом столбце их должно быть ровно по одному значению. Начинаем с клетки (1,4), далее идет чередование. В соответствии с этим, положим x _1,4= x _1,4+ Q, x _3,4= x _3,4– Q, x _3,3= x _3,3+ Q, x _2,3= x _2,3– Q, x _2,2= x _2,2+ Q, x _1,2= x _1,2– Q. Увеличиваем значение от нуля до значения, когда одна из этих переменных обратится в 0, это будет при Q =min(x ₃₄, x ₂₃, x ₁₂)=1. Этот минимум достигается на клетке (1,2), поэтому она исключается из базиса (если минимум достигнут на нескольких клетках, то исключается из базиса только одна). Выполним преобразования и данные внесем в таблицу

j= 1

j= 2

j= 3

j= 4

b 1

b 2

b 3

b 4

i= 1

a 1

u 1

i= 2

a 2

u 2

i= 3

a 3

u 3

v 1

v 2

v 3

v 4

Значение функционала на этом решении будет равно

F =2´10+4´1+4´16+3´1+3´13+7´11=191.

Этот алгоритм повторяем до тех пор, пока не окажется, что все значения d_ij £0. Оптимальным решением будут значения x_ij последней таблицы.

Самостоятельная работа 14.

Решить транспортную задачу при m =3, n =4. Значения векторов a и b, матрицы С взять из таблицы в соответствии с номером варианта:

 

Вариант	a	b	C

Динамическое программирование и потоки в сетях

 

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

Задача оптимизации многошаговых процессов, задача о ранце.

Задача оптимизации многошаговых процессов имеет вид

	(7.1)
при ограничениях
x 0= a 0Î X 0={ a 0},	(7.2)
xi = f i (xi –1, ui), i =1,2,3,..., n,	(7.3)
xi Î Xi, i= 1,2,3,..., n,	(7.4)
ui Î Ui, i= 1,2,3,..., n,	(7.5)
где Xi, Ui, i= 1,2,3,..., n, – конечные множества.

Обозначим через W_i (x_i) максимум в следующей задаче:

при ограничениях
xi Î Xi,
xk = f k (xk –1, uk), k = i+ 1,2,3,..., n,
xk Î Xk, k=i+ 1,2,3,..., n,
uk Î Uk, k=i+ 1,2,3,..., n,
где Xk, Uk, k=i+ 1,2,3,..., n, – конечные множества.

 

Справедливо следующее функциональное соотношение Беллмана:

Для того, чтобы решение ((x_i) _{i =0,1,2,..., n} , (u_i) _{i =1,2,3,..., n} ),удовлетворяющее ограничениям (7.1) – (7.5) было оптимальным, необходимо и достаточно, чтобы

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

Алгоритм.

Первый этап.

1. Для всех x Î X_n положить W_n (x)=0;

2. Последовательно для i = n –1, n –2, n –3,…,0 выполнить:

для всех x Î X_i положить:

Второй этап.

1. Положить x ₀:= a ₀;

2. Последовательно для i =1, 2,3,…, n положить:

Полученное в результате работы алгоритма решение ((x_i) _{i =0,1,2,..., n} , (u_i) _{i =1,2,3,..., n} )будет оптимальным для задачи (7.1) – (7.5). Оптимальное значение функционала будет равно W ₀(a ₀).

Задача о ранце имеет вид

	(7.6)
при ограничениях
	(7.7)

где u_i– целые числа i =1,2,3,..., n. Числа a_i также будем рассматривать целыми, i =1,2,3,..., n.

Введем переменные x ₀=0, . Из задачи (7.6) – (7.7) получим эквивалентную задачу

,	(7.8)
при ограничениях
x 0=0,	(7.9)
xi = f (xi –1, ui)= xi –1 +ai ´ ui, i= 1,2,3,..., n,	(7.10)
xi Î Xi ={0,1,2, ..., b }, i= 1,2,3,..., n,	(7.11)
ui Î Ui ={0,1,2, ..., b }, i= 1,2,3,..., n.	(7.12)

 

Задача (7.8) – (7.12) имеет такой же вид, как и задача (7.1) – (7.5), поэтому для ее решения можно применить алгоритм, описанный выше. Легко показать, что для задачи о ранце

при ограничениях

Соотношение Беллмана примет вид

где [ a ] – целая часть числа a.

Пример. Решить задачу:

u 1	+ 2 u 2	Þ	max
2 u 1	+u 2	£
u 1, u 2 – целые.

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

	i
W 0	u 1	W 1	u 2	W 2
x

Приведем пояснения к заполнению этой таблицы в соответствии с выполнением алгоритма.

Первый этап.

Заполнение столбца W ₂ понятно, оно соответствует выполнению пункта 1 первого этапа алгоритма. Покажем, как заполнялась клетка (x, i)=(0,1). Ее заполнение соответствует вычислению

для x =0, i =0,

или

В соответствии с этим, Так как W ₂(x)º0 (см. таблицу), то

Аналогично получены все остальные элементы этого столбца.

Покажем вычисления для клетки (0,0). Для нее

При u =0 ,

При u =1 ,

Таким образом, W ₀(0)=6, u ₁(0)=0.

Остальные клетки столбца 0 не заполняем, так как X ₀={0}.

Второй этап.

1. x ₀=0. (в следующей таблице клетка (0,0) выделена)

2. u ₁= u ₁(x ₀)= u ₁(0)=0, x ₁= x ₀+2´ u ₁=0 (клетка (0,1) выделена)

3. u ₂= u ₂(x 1)= u ₂(0)=3, x ₂= x ₁+1´ u ₂=3 (клетка (3,2) выделена)

	i
W 0	u 1	W 1	u 2	W 2
x

Ответ. Максимальное значение функционала в задаче равно 6, u ₁=0, u ₂=3.

Самостоятельная работа 15.

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

Вариант	Вектор a	Вектор с

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

i

W 0

u 1

W 1

u 2

W 2

u 3

W 3

u 4

W 4

u 5

W 5

x

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