3.Метод Фогеля.
А/B |
В1(40) |
В2(60) |
В3(50) |
В4(70) |
1 |
2 |
|
А1(50) |
4 |
3 |
2\50 |
6\- |
1 |
1 |
|
А2(70) |
2 |
4 |
5 |
1\70 |
1 |
|
|
А3(100) |
3 |
6 |
7 |
5\- |
2 |
3 |
|
1 |
1 |
1 |
3 |
4 |
|
|
|
2 |
1 |
3 |
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Пример:
Поставщики |
ПОТРЕБИТЕЛИ |
Запас груза |
||||
B1 |
B2 |
B3 |
B4 |
|||
А1 |
5\230 |
1\70 |
2\- |
3\- |
300 |
|
A2 |
6\- |
3\200 |
7\- |
1\- |
200 |
|
А3 |
4\- |
5\150 |
3\350 |
2\- |
500 |
|
А4 |
2\- |
4\- |
6\300 |
4\400 |
700 |
|
Потребность в грузе |
230 |
420 |
650 |
400 |
1700 |
|
4+4-1=7
4.Метод потенциалов и др.
Перейдем к построению оптимального плана перевозок. По данному опорному плану, у которого число занятых клеток m+n-1. Каждому поставщику и каждому потребителю передается число, называемое потенциалом. Потенциалы выбираются так, чтобы их сумма для каждой загруженной грузом клетки была равна тарифу перевозки единицы груза. Так если клетка (I,k) – базисная(занятая), то ui +vk=Cik где у итое поьенцтал итого поставщика.
Тогда вычисляем оценки свободных клеток по формуле: Sij=Cij-(Ui+Vj)
Если для свободных клеток все оценки Sij больше или ровны 0, то полученный план перевозок оптимален. При наличии хотя бы одной оценки Sij < 0 число базисных вводят в клетку, для которой оценка Sij минимальной. Для такой клетки строится цикл и производится перемещение груза так, чтобы баланс цикла сохранялся.
A/B |
B1(80) |
B2(170) |
B3(150) |
B4(180) |
B5(70) |
A1(300) |
4/80 |
7/- |
1/150 |
5/- |
2/70 |
A2(150) |
6/- |
2/- |
4/- |
1/150 |
3/0 |
A3(200) |
5/- |
6/170 |
7/- |
4/30 |
8/- |
U1=0
U2=
U3= В заполненой клетке таріф равен сумме потенциалов
A/B |
B1(80) |
B2(170) |
B3(150) |
B4(180) |
B5(70) |
A1(300) |
|
7/- |
1/150 |
5/- |
|
A2(150) |
6/- |
2/- |
4/- |
|
3/0 |
A3(200) |
|
6/170 |
7/- |
4/30 |
8/- |
4/80
2/70
1/150
5/-
V1=4
V2=2
V3=1
V4=0
V5=2
S12=5
S14=5
S21=1
S22=-1
S23=2
S31=-2
S33=2
S35=2
A/B |
B1(80) |
B2(170) |
B3(150) |
B4(180) |
B5(70) |
A1(300) |
4/80 |
7/- |
1/150 |
5/- |
2/70 |
A2(150) |
6/- |
2/- |
4/- |
1/150 |
3/- |
A3(200) |
5/0 |
6/170 |
7/- |
4/30 |
8/- |
F=320+150+140+150+1020+120=1900
A/B |
B1(80) |
B2(170) |
B3(150) |
B4(180) |
B5(70) |
A1(300) |
4/80 |
7/- |
1/150 |
5/- |
2/70 |
A2(150) |
6/- |
2/- |
4/- |
1/150 |
3/- |
A3(200) |
5/0 |
6/170 |
7/- |
4/30 |
8/- |
0
-2
1
4 5 1 3 2
A/B |
B1(80) |
B2(170) |
B3(150) |
B4(180) |
B5(70) |
A1(300) |
4/80 |
7/- |
1/150 |
5/- |
2/70 |
A2(150) |
6/- |
2/150 |
4/- |
1/- |
3/- |
A3(200) |
5/0 |
6/20 |
7/- |
4/180 |
8/- |
0
-3
1
4 5 1 3 2
S12=7-0-5=2
S14=5-0-3=2
S21=6+3-4=5
S23=4+3-1=6
S24=1+3-3=1
S25=3+3-2
S31=5-1-4=0
S33=7-1-1=5
S35=8-1-2=5
F=1750
A/B |
B1() |
B2(170) |
B3(150) |
B4(180) |
A1(40) |
6/- |
|
2/30 |
7/- |
A2(36) |
8/24 |
10/10 |
14/- |
12/2 |
A3(24) |
16/- |
12/- |
6/- |
13/24 |
4/10
0
6
7
2 4 2 6
S11=4
S14=1
S23=6
S31=7
S32=1
S33=-3
Min(30,10,24)
A/B |
B1() |
B2(170) |
B3(150) |
B4(180) |
A1(40) |
6/- |
4/20 |
2/20 |
7/- |
A2(36) |
8/24 |
10/- |
14/- |
12/12 |
A3(24) |
16/- |
12/- |
6/10 |
13/14 |
0
3
4
5 4 2 9
S11=1
S14=-2
S22=3
S23=9
s31=7
s32=4
min(14,20)=14
|
В1(50) |
В2(55) |
В3(70) |
В4(45) |
В5(10) |
|
А1(60) |
4\15 |
10\- |
5\- |
3\45 |
0\- |
0 |
А2(100) |
6\30 |
7\- |
2\70 |
8- |
0\- |
2 |
А3(70) |
8\5 |
9\55 |
12\- |
11\- |
0\10 |
4 |
|
4 |
5 |
0 |
3 |
-4 |
|
230-220 = 10 ЗНАЧИТ ДОБАВИМ В5
S12=10-0-5=5 S13=-5 S15=4 S22=0 S24=3 S25=3 S33=8 S34=4
F=60+135+180+140+40+495=1050