Тема: «Целочисленное программирование»

Задача 5.1

Имеется необходимость посетить n городов в ходе деловой поездки. Спланировать поездку нужно так, чтобы, переезжая из города в город, побывать в каждом не более одного раза и вернуться в исходный город. Задана матрица расстояний между городами c_ij.

Сформулированная задача - задача ЦП. Пусть х_ij = 1, если путешественник переезжает из i -ого города в j-ый и х_ij = 0, если это не так.

Формально введем (n+1) город, расположенный там же, где и первый город, т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города. При этом, если из первого города можно лишь выйти, то в (n+1) город можно лишь придти.

Введем дополнительные целые переменные, равные номеру посещения этого города на пути. u₁ = 0, u_n+1 = n. Для того, чтобы избежать замкнутых путель, выйти из первого города и вернуться в (n+1) введем дополнительные ограничения, связывающие переменные x_ij и переменные u_i. (u_i целые неотрицательные числа).

2. Математическая модель

Необходимые данные приведены ниже: Условия задачи 5.1

Задача 5.2

Решить задачу методом ветвей и границ.

Данные, необходимы для решения, приведены ниже: таблица 5.2
Приложение

Таблица 1.1

Вариант№

a11

a12

a13

a21

a22

a23

a31

a32

a33

b1

b2

b3

c1

c2

c3

k

bk

ck

a1l

a2l

a3l

pl

Таблица 1.2

Вариант№

b1

b2

b3

a11

a12

a13

a21

a22

a23

a31

a32

a33

c1

c2

c3

Таблица 2.1

Вариант№0

a1

a2

a3

s1

s2

s3

b1

b2

b3

b4

c11

c12

c13

c14

c21

c22

c23

c24

c31

c32

c33

c34

Таблица 2.2

Вариант№

A1

A2

A3

B1

B2

B3

B4

p11

p12

p13

p14

p21

p22

p23

p24

p31

p32

p33

p34

Таблица 3.1

Вариант№
d1	0,4	0,1	0,6	0,9	0,9	1,0	0,0	0,4	0,9	0,1	0,2	0,0	0,0	0,2	0,2	0,0	0,3	0,3	0,6	0,4	0,4	0,4	0,9	0,5	0,4	0,3	1,0	0,8	1,0	0,3
d2	1,0	0,1	0,7	0,8	1,0	0,5	0,3	0,8	0,4	0,8	0,1	0,2	0,1	0,4	0,5	0,5	0,4	1,0	0,0	0,2	0,0	0,9	0,1	0,3	0,8	0,7	0,8	0,7	0,1	0,1
d3	0,8	0,6	0,2	0,4	0,6	0,7	0,6	0,2	1,0	0,7	0,5	0,8	0,8	0,3	0,2	0,9	0,1	0,1	0,8	0,7	1,0	0,9	0,9	0,5	0,5	0,7	0,5	0,1	0,0	0,8
p1	2,4	2,7	2,7	2,4	2,1	2,1	2,4	2,9	2,3	2,9	2,3	2,0	2,9	2,3	2,8	2,4	2,2	2,7	2,6	2,8	2,4	2,4	2,4	2,7	2,0	2,2	2,2	2,4	2,6	2,4
p2	2,0	2,1	2,2	2,4	2,4	2,2	2,8	2,0	2,1	2,1	2,3	2,2	2,5	2,4	2,3	2,9	2,0	2,3	2,4	2,5	2,1	2,2	2,7	2,1	2,4	2,7	2,3	2,8	2,2	2,1
p3	2,9	2,5	3,0	2,3	2,2	3,0	2,8	2,2	2,8	2,8	2,9	2,7	2,0	2,3	2,2	2,6	2,2	2,9	2,9	2,4	2,4	2,9	2,4	2,6	2,3	2,5	2,9	2,9	2,0	2,5
q1	1,5	1,5	1,6	1,0	1,9	1,1	1,9	1,3	1,9	1,7	1,3	1,9	1,2	1,0	1,2	1,2	1,1	1,4	1,7	1,6	1,3	1,7	1,5	1,9	1,9	1,8	1,3	1,1	2,0	1,6
q2	1,0	1,6	1,5	1,5	1,9	1,4	1,3	1,8	1,6	2,0	1,4	1,1	1,4	1,0	1,6	1,7	1,7	1,9	1,1	1,5	2,0	1,7	1,2	1,1	1,9	1,5	1,5	1,6	1,6	1,1
q3	1,3	1,3	1,7	1,9	1,4	1,3	1,2	1,8	1,4	1,1	2,0	1,6	1,7	1,7	1,5	1,4	1,6	2,0	1,2	1,5	1,9	1,3	1,7	1,7	1,3	1,1	1,4	1,9	1,2	1,9
a1
a2
a3
b1
b2
b3
c1
с2
c3

Таблица 4.1

Вариант№

f1(20)

f2(20)

f3(20)

f4(20)

f1(40)

f2(40)

f3(40)

f4(40)

f1(60)

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:   1234  Сейчас читают про: Наследование по римскому праву Революция 1905-1907 гг.: причины, этапы, основные события, значение Цели, задачи и функции предпринимательства Индукция и дедукция. Анализ и синтез Анализ актива баланса Правовое положение сословий в Российском государстве в XVIII веке Самый сильный аргумент, почему эволюция человека не могла быть  Счастлив тот, кто счастлив у себя дома. © Лев Толстой ==> читать все изречения... 6255 6087 Понравился сайт? Поделись им с друзьями: