Зерно из четырех районов должно быть перевезено на три элеватора. Ожидаемый сбор зерна в районах: 1 – 400 тыс. ц., 2 – 500 тыс ц., 3 -800 тыс ц., 4 – 500 тыс ц. Мощность элеваторов 1 – 700 тыс. ц., 2 – 800 тыс. ц., 3 -700 тыс. ц. Затраты на перевозку 1 центнера зерна из районов к элеваторам приведена в таблице (руб.) Определить план перевозок зерна с минимальными транспортными затратами.
Районы
Элеваторы
1
2
3
1-й
1
4
3
2-й
7
1
5
3-й
4
8
3
4-й
4
2
8
Решение:
Исходная таблица:
Поставщик Потребитель Запасы груза
B1 B2 B3 A1 1
0
4
0
3
0
400
A2 7
0
1
0
5
0
500
A3 4
0
8
0
3
0
800
A4 4
0
2
0
8
0
500
Потребность 700 800 700
Транспортная задача имеет закрытый тип, так как суммарный запас груза равен суммарным потребностям.Находим опорный план по правилу северо-западного угла:Помещаем в клетку (1,1) меньшее из чисел A1*=400 и B1*=700Так как запасы поставщика A1 исчерпаны, то строка 1 в дальнейшем в расчет не принимаетсяПомещаем в клетку (2,1) меньшее из чисел A2*=500 и B1*=300Так как спрос потребителя B1 удовлетворен, то столбец 1 в дальнейшем в расчет не принимаетсяПомещаем в клетку (2,2) меньшее из чисел A2*=200 и B2*=800Так как запасы поставщика A2 исчерпаны, то строка 2 в дальнейшем в расчет не принимаетсяПомещаем в клетку (3,2) меньшее из чисел A3*=800 и B2*=600Так как спрос потребителя B2 удовлетворен, то столбец 2 в дальнейшем в расчет не принимаетсяПомещаем в клетку (3,3) меньшее из чисел A3*=200 и B3*=700Так как запасы поставщика A3 исчерпаны, то строка 3 в дальнейшем в расчет не принимаетсяПомещаем в клетку (4,3) меньшее из чисел A4*=500 и B3*=500
Поставщик Потребитель Запасы груза
B1 B2 B3 A1 1
400
4
3
400
A2 7
300
1
200
5
500
A3 4
8
600
3
200
800
A4 4
2
8
500
500
Потребность 700 800 700
Целевая функция F=1*400+7*300+1*200+8*600+3*200+8*500=12100
Решаем задачу методом потенциалов:
Этап 1
Потенциалы Ui_U1=0V1=C1,1-U1= 1U2=C2,1-V1=6V2=C2,2-U2= -5U3=C3,2-V2=13V3=C3,3-U3= -10U4=C4,3-V3=18Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток:S1,2 = c1,2 – (u1 + v2) = 9.S1,3 = c1,3 – (u1 + v3) = 13.S2,3 = c2,3 – (u2 + v3) = 9.S3,1 = c3,1 – (u3 + v1) = -10.S4,1 = c4,1 – (u4 + v1) = -15.S4,2 = c4,2 – (u4 + v2) = -11.Наиболее потенциальной является клетка (4,1). Для нее оценка равна -15.Строим для нее цикл, помечая клетки цикла знаками “плюс” и “минус”.
Поставщик Потребитель Запасы груза
B1 B2 B3 A1 1
400
4
3
400
A2 – 7
300
+ 1
200
5
500
A3 4
– 8
600
+ 3
200
800
A4 + 4
2
– 8
500
500
Потребность 700 800 700
Перемещаем по циклу груз величиной в 300 единиц, прибавляя эту величину к грузу в клетках со знаком “плюс” и отнимая ее от груза в клетках со знаком “минус”.В результате перемещения по циклу получим новый план:
Поставщик Потребитель Запасы груза
B1 B2 B3 A1 1
400
4
3
400
A2 7
1
500
5
500
A3 4
8
300
3
500
800
A4 4
300
2
8
200
500
Потребность 700 800 700
Целевая функция F= 7600
Этап 2
Потенциалы Ui_U1=0V1=C1,1-U1= 1U4=C4,1-V1=3V3=C4,3-U4= 5U3=C3,3-V3=-2V2=C3,2-U3= 10U2=C2,2-V2=-9Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток:S1,2 = c1,2 – (u1 + v2) = -6.S1,3 = c1,3 – (u1 + v3) = -2.S2,1 = c2,1 – (u2 + v1) = 15.S2,3 = c2,3 – (u2 + v3) = 9.S3,1 = c3,1 – (u3 + v1) = 5.S4,2 = c4,2 – (u4 + v2) = -11.Наиболее потенциальной является клетка (4,2). Для нее оценка равна -11.Строим для нее цикл, помечая клетки цикла знаками “плюс” и “минус”.
Поставщик Потребитель Запасы груза
B1 B2 B3 A1 1
400
4
3
400
A2 7
1
500
5
500
A3 4
– 8
300
+ 3
500
800
A4 4
300
+ 2
– 8
200
500
Потребность 700 800 700
Перемещаем по циклу груз величиной в 200 единиц, прибавляя эту величину к грузу в клетках со знаком “плюс” и отнимая ее от груза в клетках со знаком “минус”.В результате перемещения по циклу получим новый план:
Поставщик Потребитель Запасы груза
B1 B2 B3 A1 1
400
4
3
400
A2 7
1
500
5
500
A3 4
8
100
3
700
800
A4 4
300
2
200
8
500
Потребность 700 800 700
Целевая функция F= 5400
Этап 3
Потенциалы Ui_U1=0V1=C1,1-U1= 1U4=C4,1-V1=3V2=C4,2-U4= -1U2=C2,2-V2=2U3=C3,2-V2=9V3=C3,3-U3= -6Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток:S1,2 = c1,2 – (u1 + v2) = 5.S1,3 = c1,3 – (u1 + v3) = 9.S2,1 = c2,1 – (u2 + v1) = 4.S2,3 = c2,3 – (u2 + v3) = 9.S3,1 = c3,1 – (u3 + v1) = -6.S4,3 = c4,3 – (u4 + v3) = 11.Наиболее потенциальной является клетка (3,1). Для нее оценка равна -6.Строим для нее цикл, помечая клетки цикла знаками “плюс” и “минус”.
Поставщик Потребитель Запасы груза
B1 B2 B3 A1 1
400
4
3
400
A2 7
1
500
5
500
A3 + 4
– 8
100
3
700
800
A4 – 4
300
+ 2
200
8
500
Потребность 700 800 700
Перемещаем по циклу груз величиной в 100 единиц, прибавляя эту величину к грузу в клетках со знаком “плюс” и отнимая ее от груза в клетках со знаком “минус”.В результате перемещения по циклу получим новый план:
Поставщик Потребитель Запасы груза
B1 B2 B3 A1 1
400
4
3
400
A2 7
1
500
5
500
A3 4
100
8
3
700
800
A4 4
200
2
300
8
500
Потребность 700 800 700
Целевая функция F= 4800
Этап 4
Потенциалы Ui_U1=0V1=C1,1-U1= 1U3=C3,1-V1=3V3=C3,3-U3= 0U4=C4,1-V1=3V2=C4,2-U4= -1U2=C2,2-V2=2Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток:S1,2 = c1,2 – (u1 + v2) = 5.S1,3 = c1,3 – (u1 + v3) = 3.S2,1 = c2,1 – (u2 + v1) = 4.S2,3 = c2,3 – (u2 + v3) = 3.S3,2 = c3,2 – (u3 + v2) = 6.S4,3 = c4,3 – (u4 + v3) = 5.Так как все оценки Si,j>=0, то полученный план является оптимальным.Транспортная задача решена.
Поставщик Потребитель Запасы груза
B1 B2 B3 A1 1
400
4
3
400
A2 7
1
500
5
500
A3 4
100
8
3
700
800
A4 4
200
2
300
8
500
Потребность 700 800 700
Целевая функция F= 4800
