Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Сигал И.Х. -> "Введение в прикладное дискретное программирование " -> 44

Введение в прикладное дискретное программирование - Сигал И.Х.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 38 39 40 41 42 43 < 44 > 45 46 47 48 49 50 .. 84 >> Следующая


ж2Є{0;1}

52(0) = 0, X2= 0;

0г(1) = 0і(1) = 0, X2 = O',

52(2)=^(2) = 5, X2 = O-
Гл. 4• Применение метода динамического программирования 127

д2 (3) = max (Tx2 + ді (3 - Зж2)) = max (7 + дг (O); дг (3)) =

*26(0,1} = max (7 + 0; 5) = 7; х2 = I;

52 (4) = max (Ix2 + gi (4 - Sx2)) = max (7 + gi (I); дг (4)) =

ж2Є{о,і} = max (7 + 0; 5) = 7; X2 = I;

д2 (5) = max (Tx2 + gi (5 - Zx2)) = max (7+ 51 (2)\gi (5)) =

Z2G(OjI) = max (7 + 5; 5) = 12; X2 = I.

Аналогично, gi (6) = ... = gi (9) = 12, X2 = I. Полученные значения заносим в табл. 4.3, максимальное значение 12 соответствует значению X2 — 1.

3. Вычислим дз(у):

Зз (у) = max (с3х3 +д2(у- а3х3)), у - а3х3 > 0;

ж3Є{0;1)

Зз (у) = max (6ж3 + д2

жзЄ{0;1)

^3(O)=O, ж3=0;

53(1)=52(1)=0, X3 =

Зз(2)=52(2)=5, X3 =

Зз(3) = д2(3) = 7, х3 =

Зз (4) = #2 (4) = 7, X3 =

д3 (5) = max (6ж3 + д2

ж3Є{0;1}

д3 (6) = max (6ж3 + д2

ж3Є{0;1}

д3 (7) = max (6х3 + д2

ж3Є{0;1}

9з (8) = max (6х3 + д2

жзЄ{0;1)

9з (9) = max (6х3 + д2

жзЄ{0;1)

Заносим данные в табл. ветствует Жз = 1.

4. Вычислим д4:(у):

д4(у) = max (с4х4 + д3 (у - а4х4)), у-а4х4> 0;

Ж4Є{0;1)

д4 (у) = max (Зх4 + д3(у- ^x4)), у- 7ж4 > 0;

ж4Є{0;1}

^4(O) =0, X4= 0;

34(1)=3з(1)=0, х4 = 0;

(у - 5ж3)), у — 5х3 > 0;

0;

0;

0;

0;

(5 - 5ж3)) = max (6+ 52 (0) ;зг (5)) =

= max (6 + 0; 12) = 12; X3 = 0;

(6 - 5ж3)) = max (6+ 52 (1) !32 (6)) =

= max (6 + 0; 12) = 12; X3 = 0;

(7 - 5х3)) = max (6 + д2 (2); д2 (7)) =

= max (6 + 5; 12) = 12; X3 = 0;

(8 - 5х3)) = max (6 + д2 (3); д2 (8)) =

= max (6 + 7; 12) = 13; X3 = 1;

(9 - 5х3)) = max (6 + д2 (4); д2 (9)) =

= max (6 + 7; 12) = 13; х3 = 1.

4.3 и фиксируем, что максимум 13 соот-
128

Разд. II. Комбинаторные методы решения задач

54(2)=53(2) = 5, X4 = 0;

54(3)=5з(3) = 7, Xi = 0;

54(4) = 5з(4) = 12, Xi = 0;

54(6) = 5з (6) = 12, Xi = 0;

д4 (7) = max (Зж4 + 53 (7 - 7ж4)) = max (3 + g3 (0); g3 (7)) =

Ж4Є{0;1} = max (3 + 0; 12) = 12; X4 = 0;

54(8)= max (Зж4 + 5з (8 - 7х4)) = max (3 + g3 (I); g3 (8)) =

Ж4Є{0;1} = max (3 + 0; 13) = 13; X4 = 0;

g4 (9) = max (Зж4 + 5з (9 - 7ж4)) = max (3 + g3 (2); g3 (9)) =

ж4є{од} = max (3 + 5; 13) = 13; х4 = 0.

Заносим данные в табл. 4.3 и фиксируем, что максимум 13 соответствует Х4 = 0.

Найдем оптимальное решение X0 = (ж^, ж!], Ж3, Ж4).

Полагая R0 = 9 находим в девятой строке, что #4(9) = 13, х\ = 0. Полагая Rq = 9 — а^х\ = 9, находим, что д% (9) = 13, = 1.

Полагая Rq = 9 — азх® =9 — 5 = 4, находим, что #2 (4) = 7, х\ = 1. Полагая R0 = 4 — а2х\ = 4 — 3 = 1, находим, что gi (1) = 0, х\ = 0. Оптимальное решение: X0 = (0; I; 1; 0), / (ж0) = 13.

Аналогично найдем оптимальное решение для всех 2 < у < 9. Эти решения представлены в табл. 4.4.

Таблица 4.4

У 9*(у) ж 0
9 13 0; 1; 1; 0
8 13 0; 1; 1; 0
7 12 1; 1; 0; 0
6 12 1; 1; 0; 0
5 12 1; 1; 0; 0
4 7 0; 1; 0; 0
3 7 0; 1; 0; 0
2 5 1; 0; 0; 0

Пример 4.2. Решить задачу о ранце

f(x) = Зжі + 4^2 + Xs + Ж4 + Ж5 —>• max,

4жі H- Зз?2 H- 2жз H- 5з?4 H- 2,х§ ^ б, жі Є {0; 1}, j = 1,2,...,5.

Решение этого примера не будем приводить так подробно, как в предыдущем случае; приведем лишь результирующие таблицы. В
Гл. 4• Применение метода динамического программирования 129

табл. 4.5 приведены все значения (у), О < у < б, I < к < 5 и соответствующие значения Xk.

Таблица 4.5

У до(у) 9і(у) Xi 92(у) Ж2 дз(у) хз 04(2/) Х4 9б(у) X5
0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 і 1 1 0 1 1
3 0 0 0 4 1 4 0 4 0 4 0
4 0 3 1 4 1 4 0 4 0 4 0
5 0 3 1 4 1 5 1 5 0 5 1
6 0 3 1 4 1 5 1 5 0 5 1

Найдем оптимальное решение X0 = (ж^, ж®, Ж3, х\, х®).

Полагая Ro = б, находим в шестой строке, что ^5 (6) = 5, = 1.

Полагая Rq = 6 — 2 = 4, находим, что д4 (4) = 4, Ж4 = 0, Ro сохранит значение 4.

Далее находим, что #з(4) =4, Ж3 = 0, i?o сохранит значение 4. Находим, что #2 (4) = 4, = I, Ro = 4 — 0,2X2 = 4 — 3 = 1.

Находим, что ^i(I) = 0, X1 = 0, и оптимальное решение имеет вид х° = (0; 1; 0; 0; 1), / (ж0) = 5.

T а б л и ц а 4.6

У 04(2/)
6 5 0; 1; 0; 0; 1
5 5 0; 1; 0; 0; 1
4 4 0; 1; 0; 0; 0
3 4 0; 1; 0; 0; 0
2 1 0; 0; 0; 0; 1

В табл. 4.6 приведены оптимальные решения для всех 2 < у < 6.

4.3. Задача о минимизации суммы функций двух переменных

4.3.1. Постановка задачи и общая схема решения. Задача рассматривается в следующем виде:

п—1

f (X1,X2,...,Xn) = fi(xi,xi+ i)-s>min, (431)

Xi Є Gi, IGjI=TOi, і = 1,2,...,п.

9 И.Х. Сигал, А.П. Иванова
130

Разд. II. Комбинаторные методы решения задач

Здесь Xi — скалярные переменные, функции / (xi, X2,..., хп) будем также называть аддитивными или сепарабельными. Перепишем задачу в следующем виде:

F1(XljX2) = Zl(XlrX2),

F2(Xl7X2yX3) = J1(XlyX2) + f2(x2,x3) = F1(XlyX2) + Mx2,X3),

F3 (X1,X2, X3, Xi) = F2 (X1, X2,X3) + f3(x3,xi),

Fk (X1, X2,..., Xk-^1) — Fk-1 (X1, х2,..., Xk) fk(xk> Xk-^1),

Fn-1 (X1, X2, ... , Xn) — Fn-2 (X1, X2, . . . , Жп_і) + fn—I (Xn-i , xn). Сложив эти равенства, получим
Предыдущая << 1 .. 38 39 40 41 42 43 < 44 > 45 46 47 48 49 50 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100