183796 (584802), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

S11=3 S22=9 S24=1 S32=4

S15=14 S23=8 S31=3 S34=3

Так как все Sij0, то план оптимальный и единственный. Затраты на перевозки по оптимальному плану составляют:

min Z=1104+106+1308+705+804+805+205=

=440+60+1040+350+320+400+100=2710 руб.

Ответ: затраты на перевозки по оптимальному плану составляют 2710 рублей.

Задача II

Решить ТЗ с открытой моделью, если дана матрица планирования перевозок:

6	30	25	7	15	35
5	29	21	4	13	40
18	22	5	28	1	25
19	23	8	2	14	15
24	25	30	20	21

Решение:

а). Установим характер задачи:

, итак

модель задачи открытая, значит, вводим фиктивный пункт отправления А5 с запасами груза a5= - = 120 - 115=5, а тарифы перевозки этого груза будут С51=С52=С53=С54= С55=0.

Составляем распределительную таблицу по методу "минимального элемента":

	B1	B2	B3	B4	B5	ai
A1	6	30 25	25 10	7	15	35
A2	5 19	29	21 16	4 5	13	40
A3	18	22	5 4	28	1 21	25
A4	19	23	8	2 15	14	15
A5	0 5	0	0	0	0	5
bj	24	25	30	20	21	120 120

Итак, получили план X1. Суммарные расходы на перевозку зерна составляют:

Z(X1) =246+1130+1429+2621+45+2028+11+1514+50 =

= 144+330+406+546+20+560+1+210=2217 руб.

б). Построение нового улучшенного опорного плана по методу потенциалов.

Рассмотрим опорный план, найденный по методу “минимального элемента”.

	B1	B2	B3	B4	B5	ai	ui
A1	6	- 30 2 5	+ 25 10	7	15	35	0
A2	+ 5 1 9	29	- 21 16	4 5	13	40	- 4
A3	18	22	5 4	28	1 21	25	- 20
A4	19	23	8	2 15	14	15	- 6
A5	- 0 5	+ 0	0	0	0	5	- 9
bj	24	25	30	20	21	120 120
j	9	30	25	8	21

Проверяем условие m+n-1=5+5-1=9, число занятых клеток удовлетворяет этому условию.

Определяем потенциалы и находим оценки свободных клеток:

S11=-3 S25=-4 S41=16 S52=-21

S14=-1 S31=29 S42=-1 S53=-16

S15=-6 S32=12 S43=-11 S54=-1

S22=3 S34=40 S45=-1 S55=-12

S52 - наименьшая оценка.

С вершиной в клетке (5;

2) строим замкнутый цикл.

Найдем =min(5; 16; 25) =5, после пересчета получим новый цикл. Заменяя старый цикл на новый, получим следующую таблицу:

	B1	B2	B3	B4	B5	ai	ui
A1	6	30 20	25 15	7	15	35	0
A2	5 24	29	- 21 1 1	+ 4 5	13	40	- 4
A3	18	22	5 4	28	1 21	25	- 20
A4	19	23	+ 8	- 2 15	14	15	- 6
A5	0	0 5	0	0	0	5	- 30
bj	24	25	30	20	21	120 120
j	9	30	25	8	21

Определяем потенциалы и находим оценки свободных клеток:

S11=-3 S25=-4 S41=16 S51=21

S14=-1 S31=29 S42=-1 S53=5

S15=-6 S32=12 S43=-11 S54=22

S22=3 S34=40 S45=-1 S55=9

S43 - наименьшая оценка. С вершиной в клетке (4;

3) строим замкнутый цикл. Найдем =min(11; 15) =11, после пересчета получим новый цикл. Заменяя старый цикл на новый, получим следующую таблицу:

	B1	B2	B3	B4	B5	ai	ui
A1	+ 6 -	30 20	- 25 15	7	15	35	0
A2	- 5 24	29	21 -	+ 4 16	13	40	- 15
A3	18	22	5 4	28	1 21	25	- 20
A4	19	23	+ 8 11	- 2 4	14	15	- 17
A5	0	0 5	0	0	0	5	- 30
bj	24	25	30	20	21	120 120
j	20	30	25	19	21

Определяем потенциалы и находим оценки свободных клеток:

S11=-14 S23=11 S34=29 S51=10

S14=-12 S25=7 S41=16 S53=5

S15=-6 S31=18 S42=10 S54=11

S22=14 S32=12 S45=10 S55=9

S11 - наименьшая оценка. С вершиной в клетке (1;

Характеристики

Список файлов ответов (шпаргалок)