Решение задачи коммивояжера

Решение задачи о ранце методом динамического программирования (рекуррентная схема)

Решение задачи о ранце методом динамического программирования (табличная форма)

Рассмотрим задачу о ранце с четырьмя предметами.

5x(1)+7x(2)+6x(3)+3x(4) max,

2x(1)+3x(2)+5x(3)+7x(4) 9,

x(i) {0,1}, i=1,2,3,4.

Все параметры задачи целые неотрицательные числа.

Обозначим через Z (k,p) - задачу, при условиях, что предметов k, k m (для нашей задачи m=4), а вместимость ранца p, p v(0) (для нашей задачи v(0)=9). Пусть R(k,p) - оптимум задачи Z(k,p). Тогда оптимум исходной задачи совпадает с оптимумом задачи Z(m,v(0)) и равен R(m,v(0)). Для определения величин R(m,v(0)) построим следующие рекуррентные соотношения:

R(k+1,p) = R(k,p), если v(k+1) > p, (1)

R(k+1, p) = max { R(k,p), c(k+1) + R(k, p- v(k+1)}, если p> v(k+1) + 1.

Эти рекуррентные соотношения, с учетом граничных условий

R(1,p) = 0, если с(1) > p, (2)

R(1,p) = c(1), если c(1) < p+1,

будем использовать для решения исходной задачи о ранце.

Результаты вычислений по рекуррентным соотношениям будем представлять в виде таблицы с m=4 строками и v(0)=9 столбцами, в которой приводятся значения соответственных величин R(k,p). Для того чтобы решить исходную задачу о ранце необходимо заполнить клетку таблицы с координатами: m=4, v(0)=9. Для этого не требуется заполнить все клетки таблицы, а лишь те, которые используются для вычисления значений величины R(4,9).

Таблица заполняется следующим образом.

R(4,9)=max { R(3,9), c(4)+ R(3,9-v(4))}= max { R(3,9), c(4)+ R(3, 9 - 7}=

max { R(3,9), c(4)+ R(3,2}. Таким образом, для заполнения ячейки (4,9) необходимо заполнить ячейки (3,9) и (3,2). В свою очередь для заполнения этих ячеек необходимо заполнить другие ячейки. Первой заполняется ячейка (1,1). В ней, согласно граничным условиям (2), значение R(1,1)=0. Затем, используя рекуррентные соотношения (1) заполняются остальные ячейки, пока ячейка с номером (4,9) не будет заполнена. Решение задачи о ранце, согласно содержанию ячейки (4,9), будет иметь вид:

x’(1)=0, x’(2)=1, x’(3)=1, x’(4)=0. Значение оптимума задачи F(x’)=13.

Рассмотрим задачу о ранце с четырьмя предметами.

5x(1)+7x(2)+6x(3)+3x(4) max,

2x(1)+3x(2)+5x(3)+7x(4) 9,

x(i) {0,1}, i=1,2,3,4.

Множество предметов G={1,2,3,4} - множество номеров предметов.

Обозначим через W(G’, p) - суммарную полезность тех предметов, которые будут положены в ранец из предметов множества G’, при вместимости ранца p, и наилучшем способе выбора предметов (с точки зрения функционала задачи),

G’ G, p v(0).

Обозначим через S = { i/ c(i) p, i G’}.

Тогда

W(G’,p) = max [ c(i) + W(G’\{i}, p - v(i)], (1)

где максимум берется по предметам из множества S.

Рекуррентные соотношения (1), с учетом граничных условий:

W(G’,p) = 0, если S - пустое множество, позволяют решить задачу о ранце.

W(G={1,2,3,4}, p=9) =max [5+ W({2,3,4},7), 7+ W({1,3,4},6), 6+ W({1,2,4},4), 3+ W({1,2,3},2)];

Отдельно найдем величины:

W({2,3,4},7)=max [7+ W({3,4},4), 6+ W({2,4},2), 3+ W({2,3},0)=max(7,6,3)=7(2).

W({1,3,4},6)=max[5+ W({3,4},4), 6+ W({1,4},1),]=max(5,6)=6(3).

W({1,2,4},4)=max[5+ W({2,4},2), 7+ W({1,4},1)]=max(5,7)=7(2).

W({1,2,3},2)=5(1).

Таким образом, получили:

W(G={1,2,3,4}, p=9)=max(5+7, 7+6, 6+7, 3+5)=13(2,3).

Оптимальное решение исходной задачи имеет вид:

x’ =(0,1,1,0). F(x’)=13.

3.1.4. Решить следующие задачи о ранце:

а)Методом ветвей и границ.

б)Методом динамического программирования (табличная форма).

в)Методом динамического программирования (рекуррентная схема).

Задача 1.1.

3x(1)+2x(2)+6x(3)+4x(4) max,

5x(1)+3x(2)+5x(3)+3x(4) 7

x(i) {0,1}, i=1,2,3,4.

Задача 1. 2.

5x(1)+2x(2)+5x(3)+4x(4) max,

6x(1)+3x(2)+5x(3)+3x(4) 7

x(i) {0,1}, i=1,2,3,4.

Задача 1.3.

7x(1)+4x(2)+6x(3)+x(4) max,

5x(1)+1x(2)+3x(3)+5x(4) 8

x(i) {0,1}, i=1,2,3,4.

Задача 1.4.

3x(1)+7x(2)+8x(3)+4x(4) max,

4x(1)+5x(2)+7x(3)+7x(4) 11

x(i) {0,1}, i=1,2,3,4.

Задача 1.5.

3x(1)+3x(2)+5x(3)+6x(4) max,

2x(1)+4x(2)+5x(3)+4x(4) 9

x(i) {0,1}, i=1,2,3,4.

Задача 1.6.

5x(1)+4x(2)+7x(3)+3x(4) max,

3x(1)+2x(2)+4x(3)+5x(4) 8

x(i) {0,1}, i=1,2,3,4.

Задача 1.7.

3x(1)+6x(2)+5x(3)+9x(4) max,

2x(1)+4x(2)+3x(3)+6x(4) 7

x(i) {0,1}, i=1,2,3,4.

Задача 1.8.

4x(1)+10x(2)+7x(3)+9x(4) max,

2x(1)+5x(2)+4x(3)+5x(4) 9

x(i) {0,1}, i=1,2,3,4.

Задача 1.9.

5x(1)+4x(2)+3x(3)+3x(4) max,

3x(1)+2x(2)+4x(3)+5x(4) 7

x(i) {0,1}, i=1,2,3,4.

Задача 1.10.

3x(1)+4x(2)+7x(3)+3x(4) max,

2x(1)+2x(2)+6x(3)+5x(4) 8

x(i) {0,1}, i=1,2,3,4.

Дата добавления: 2017-02-01; Просмотров: 68; Нарушение авторских прав?; Мы поможем в написании вашей работы!