Транспортная задача

Размещено на http://www.allbest.ru/

Транспортная задача

Вар 3

Никита Пазенко

	15	15	16	15	15
19	21	17	12	24	30
19	6	1	9	5	9
19	7	5	24	6	13
19	29	22	21	5	7

Потребителей 5, Поставщиков 4

Проверим ТЗ на замкнутость: .

, т.е. задача замкнутого типа.

Решением ТЗ будет служить минимальное значение целевой функции и значения xij

	B1=15	B2=15	B3=16	B4=15	B5=15	U
A1=19	21 15	17 - 4	12 +	24	30	U1=0
A2=19	6	1 + 11	9 - 8	5	9	U2=-16
A3=19	7	5	24 8	6 11	13	U3= -1
A4=19	29	22	21	5 4	7 15	U4= -2
V	V1=21	V2=17	V3=25	V4=7	V5=9

L1 = 21*15+4*17+11+72+24*8+66+20+7*15=315+68+11++72+192+86+105=849

Итерация 1

u1= 0

v1= 21

v2= 17

v3=25

u2= - 16

v4= 7

u3= - 1

u4= - 2

Проверим план на оптимальность.

Признак оптимальности:sij= cij -(ui+vj) ? 0 opt, для всех i, j.

Определим значения оценок sij= cij - (ui+vj) ? 0 для всех свободных клеток:

S13= -13

S14= 17

S15= 21

S21= 1

S24= 14

S25= 16

S31= 27

S32= - 11

S35= 5

S41= 10

S42= 7

S43= - 2

План не оптимален. Наиболее потенциальной является клетка (1,3). Для нее «невязка» равна -13. В клетку с наибольшей «невязкой» ввожv перевозку, выявляем цикл и пересчитываем клетки цикла.

Введем перевозку (1,3), построим граф и запишем цикл.



13-23-22-12

+ - + -

Из клеток со знаком «-» выбираем клетку с наименьшей величиной груза. В нашем случае это клетка (1, 2) с грузом 4.

Перемещаем по циклу груз величиной в 4 единицы, прибавляя её к грузу в клетках со знаком «+» и отнимая ее от груза в клетках со знаком «-». В результате перемещения по циклу получим новый план.

	B1=15	B2=15	B3=16	B4=15	B5=15	U
A1=19	21 - 15	17	12 + 4	24	30	U1=0
A2=19	6	1 15	9 4	5	9	U2=-3
A3=19	7 +	5	24 - 8	6 11	13	U3=12
A4=19	29	22	21	5 4	7 15	U4=11
V	V1=21	V2=4	V3=12	V4= -6	V5=-4
L2=315+48+15+36+192+66+20+105=797

Итерация 2

u1= 0

v1= 21

v2= 4

v3=12

u2= - 3

v4= - 6

u3= 12

u4= 11

Проверим план на оптимальность.

Признак оптимальности:sij= cij -(ui+vj) ? 0 opt, для всех i, j.

Определим значения оценок sij= cij - (ui+vj) ? 0 для всех свободных клеток:

S12= 13

S14= 30

S15= 34

S21= -12

S24= 14

S25= 16

S31= - 27

S32= - 11

S35= 5

S41= -3

S42= 7

S43= -2

План не оптимален. Наиболее потенциальной является клетка (3,1). Для нее «невязка» равна -27. В клетку с наибольшей «невязкой» ввожv перевозку, выявляем цикл и пересчитываем клетки цикла.

Введем перевозку (3,1), построим граф и запишем цикл.



31-11-13-33

+ - + -

Из клеток со знаком «-» выбираем клетку с наименьшей величиной груза. В нашем случае это клетка (3,3) с грузом 8.

Перемещаем по циклу груз величиной в 8 единицы, прибавляя её к грузу в клетках со знаком «+» и отнимая ее от груза в клетках со знаком «-». В результате перемещения по циклу получим новый план.

	B1=15	B2=15	B3=16	B4=15	B5=15	U
A1=19	21 - 7	17	12+ 12	24	30	U1=0
A2=19	6	1 15	9- 4	5 +	9	U2= -3
A3=19	7 + 8	5	24	6 - 11	13	U3=-14
A4=19	29	22	21	5 4	7 15	U4=- 15
V	V1=21	V2=4	V3=12	V4= 20	V5=22

L3=147+144+15+36+56+66+20+105=589

Итерация 3

u1= 0

v1= 21

v2= 4

v3=12

u2= -3

v4= 20

u3= - 14

u4= - 15

Проверим план на оптимальность.

Признак оптимальности: sij= cij -(ui+vj) ? 0 opt, для всех i, j.

Определим значения оценок sij= cij - (ui+vj) ? 0 для всех свободных клеток:

S12= 13

S14= 4

S15= 8

S21=- 12

S24= - 12

S25= - 10

S32= 15

S33= 26

S35=5

S41= 23

S42= 33

S43= 24

План не оптимален. Наиболее потенциальной является клетка (2,4). Для нее «невязка» равна -12. В клетку с наибольшей «невязкой» ввожv перевозку, выявляем цикл и пересчитываем клетки цикла.

Введем перевозку (2,4), построим граф и запишем цикл.



24-34-31-11-13-23

+ - + - + -

Из клеток со знаком «-» выбираем клетку с наименьшей величиной груза. В нашем случае это клетка (2,3) с грузом 4.

Перемещаем по циклу груз величиной в 4 единицы, прибавляя её к грузу в клетках со знаком «+» и отнимая ее от груза в клетках со знаком «-». В результате перемещения по циклу получим новый план.

	B1=15	B2=15	B3=16	B4=15	B5=15	U
A1=19	21 3	17	12 16	24	30	U1=0
A2=19	6	1 15	9	5 4	9	U2= - 15
A3=19	7 12	5	24	6 7	13	U3=- 14
A4=19	29	22	21	5 4	7 15	U4=- 15
V	V1=21	V2=16	V3=12	V4=20	V5= 22

транспортный задача перевозка цикл

L4=63+192+15+20+84+42+20+105=541

Итерация 3

u1= 0

v1= 21

v2=16

v3=12

u2= - 15

v4= 20

u3= - 14

u4= - 15

v5= 22

Проверим план на оптимальность.

Признак оптимальности:sij= cij -(ui+vj) ? 0 opt, для всех i, j.

Определим значения оценок sij= cij - (ui+vj) ? 0 для всех свободных клеток:

S12= 1

S14= 4

S15= 8

S21= 0

S23= 12

S25= 2

S32= 3

S33= 26

S35= 5

S41=23

S42= 21

S43= 24

Ответ: L=541

X11=3

X13=16

X22=15

X24=4

X31=12

X34=7

X44=4

X45=15

Размещено на Allbest.ru