Задача:


1219 9
18582
22894
15673

Решение.

Примем некоторые обозначения:
i - индекс строки
j - индекс столбца
m - количество поставщиков
n - количество потребителей
Xi,j - перевозка между поставщиком Ai и потребителем Bj.
Di,j - ограничение пропускной способности коммуникации между поставщиком Ai и потребителем Bj.
M - некоторое число, близкое к бесконечности
e - некоторое число, близкое к нулю.
Красным цветом будем отображать ограничения пропускных способностей коммуникаций между поставщиками и потребителями.
Серым цветом будем отображать стоимости перевозок(тарифы).

Исходная таблица:

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

A1

5

0

M

 

8

0

M

 

2

0

M

 

18

A2

8

0

M

 

9

0

M

 

4

0

M

 

22

A3

6

0

M

 

7

0

M

 

3

0

M

 

15

Потребность

12

19

9

 


Транспортная задача является открытой, так как запас груза больше потребностей на 15 единиц. Приведем задачу к закрытому типу - введем фиктивного потребителя B4.

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

A1

5

0

M

 

8

0

M

 

2

0

M

 

0

0

M

 

18

A2

8

0

M

 

9

0

M

 

4

0

M

 

0

0

M

 

22

A3

6

0

M

 

7

0

M

 

3

0

M

 

0

0

M

 

15

Потребность

12

19

9

15

 


Находим опорный план для задачи с ограничениями, методом минимального элемента.
Введем некоторые обозначения:
Ai* - излишек нераспределенного груза от поставщика Ai
Bj* - недостача в поставке груза потребителю Bj
Di,j - ограничение пропускной способности коммуникации между поставщиком Ai и потребителем Bj

Находим незанятую клетку с минимальным тарифом: (1,4).
Помещаем туда меньшее из чисел A1*=18, B4*=15 и D1,4=M
Находим незанятую клетку с минимальным тарифом: (1,3).
Помещаем туда меньшее из чисел A1*=3, B3*=9 и D1,3=M
Находим незанятую клетку с минимальным тарифом: (3,3).
Помещаем туда меньшее из чисел A3*=15, B3*=6 и D3,3=M
Находим незанятую клетку с минимальным тарифом: (3,1).
Помещаем туда меньшее из чисел A3*=9, B1*=12 и D3,1=M
Находим незанятую клетку с минимальным тарифом: (2,1).
Помещаем туда меньшее из чисел A2*=22, B1*=3 и D2,1=M
Находим незанятую клетку с минимальным тарифом: (2,2).
Помещаем туда меньшее из чисел A2*=19, B2*=19 и D2,2=M

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

A1

5

M

 

8

M

 

2

3

M

 

0

15

M

 

18

A2

8

3

M

 

9

19

M

 

4

M

 

0

M

 

22

A3

6

9

M

 

7

M

 

3

6

M

 

0

M

 

15

Потребность

12

19

9

15

 

Целевая функция F=273

Решаем задачу c ограничениями методом потенциалов:

Этап 1

Так как суммарная величина нераспределенного груза/потребностей epsilon = 0, то текущий план является опорным планом транспортной задачи с ограничениями.

Этап 2

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Uj+Vi=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки.
Потенциалы Ui:
U1=0
V3=C1,3-U1= 2
V4=C1,4-U1= 0
U3=C3,3-V3= 1
V1=C3,1-U3= 5
U2=C1,2-V1= 3
V2=C2,2-U2= 6
Определяем значения оценок Si,j=Ci,j-(Vj-Ui) для всех свободных клеток:
Для случая Xi,j = 0 условие оптимальности оценки Si,j определяется следующим образом: Si,j >=0.
Для случая Xi,j = Di,j условие оптимальности оценки Si,j определяется следующим образом: Si,j <=0.
оценки Si,j для всех клеток, удовлетворяющих условию: Xi,j = 0 (неоптимальные выделены синим цветом)
S1,1 = c1,1 - (v1 + u1) = 0.
S1,2 = c1,2 - (v2 + u1) = 2.
S2,3 = c2,3 - (v3 + u2) = -1.
S2,4 = c2,4 - (v4 + u2) = -3.
S3,2 = c3,2 - (v2 + u3) = 0.
S3,4 = c3,4 - (v4 + u3) = -1.
оценки Si,j для всех клеток, удовлетворяющих условию: Xi,j = Di,j (неоптимальные выделены красным цветом)
отсутствуют
Если имеются неоптимальные оценки и для случая Xi,j = 0, и для случая Xi,j = Di,j, то наиболее потенциальной(неоптимальной) из них считается максимальная по модулю оценка. Если имеется несколько клеток с одним и тем же наиболее неоптимальным значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (2,4). Для нее оценка равна -3.

Строим для этой клетки цикл, помечая клетки цикла знаками "плюс" и "минус".

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

A1

5

M

 

8

M

 

+

2

3

M

 

-

0

15

M

 

18

A2

-

8

3

M

 

9

19

M

 

4

M

 

+

0

M

 

22

A3

+

6

9

M

 

7

M

 

-

3

6

M

 

0

M

 

15

Потребность

12

19

9

15

 

Перемещаем по циклу груз величиной в 3 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".
В результате перемещения по циклу получим новый план:

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

A1

5

M

 

8

M

 

2

6

M

 

0

12

M

 

18

A2

8

M

 

9

19

M

 

4

M

 

0

3

M

 

22

A3

6

12

M

 

7

M

 

3

3

M

 

0

M

 

15

Потребность

12

19

9

15

 

Целевая функция F= 264

Значение целевой функции изменилось на 9 единиц по сравнению с предыдущим этапом.

Этап 3

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Uj+Vi=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки.
Потенциалы Ui:
U1=0
V3=C1,3-U1= 2
V4=C1,4-U1= 0
U3=C3,3-V3= 1
U2=C4,2-V4= 0
V2=C2,2-U2= 9
V1=C3,1-U3= 5
Определяем значения оценок Si,j=Ci,j-(Vj-Ui) для всех свободных клеток:
Для случая Xi,j = 0 условие оптимальности оценки Si,j определяется следующим образом: Si,j >=0.
Для случая Xi,j = Di,j условие оптимальности оценки Si,j определяется следующим образом: Si,j <=0.
оценки Si,j для всех клеток, удовлетворяющих условию: Xi,j = 0 (неоптимальные выделены синим цветом)
S1,1 = c1,1 - (v1 + u1) = 0.
S1,2 = c1,2 - (v2 + u1) = -1.
S2,1 = c2,1 - (v1 + u2) = 3.
S2,3 = c2,3 - (v3 + u2) = 2.
S3,2 = c3,2 - (v2 + u3) = -3.
S3,4 = c3,4 - (v4 + u3) = -1.
оценки Si,j для всех клеток, удовлетворяющих условию: Xi,j = Di,j (неоптимальные выделены красным цветом)
отсутствуют
Если имеются неоптимальные оценки и для случая Xi,j = 0, и для случая Xi,j = Di,j, то наиболее потенциальной(неоптимальной) из них считается максимальная по модулю оценка. Если имеется несколько клеток с одним и тем же наиболее неоптимальным значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (3,2). Для нее оценка равна -3.
Строим для этой клетки цикл, помечая клетки цикла знаками "плюс" и "минус".

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

A1

5

M

 

8

M

 

+

2

6

M

 

-

0

12

M

 

18

A2

8

M

 

-

9

19

M

 

4

M

 

+

0

3

M

 

22

A3

6

12

M

 

+

7

M

 

-

3

3

M

 

0

M

 

15

Потребность

12

19

9

15

 

Перемещаем по циклу груз величиной в 3 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".
В результате перемещения по циклу получим новый план:

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

A1

5

M

 

8

M

 

2

9

M

 

0

9

M

 

18

A2

8

M

 

9

16

M

 

4

M

 

0

6

M

 

22

A3

6

12

M

 

7

3

M

 

3

M

 

0

M

 

15

Потребность

12

19

9

15

 

Целевая функция F= 255

Значение целевой функции изменилось на 9 единиц по сравнению с предыдущим этапом.

Этап 4

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Uj+Vi=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки.
Потенциалы Ui:
U1=0
V3=C1,3-U1= 2
V4=C1,4-U1= 0
U2=C4,2-V4= 0
V2=C2,2-U2= 9
U3=C2,3-V2= -2
V1=C3,1-U3= 8
Определяем значения оценок Si,j=Ci,j-(Vj-Ui) для всех свободных клеток:
Для случая Xi,j = 0 условие оптимальности оценки Si,j определяется следующим образом: Si,j >=0.
Для случая Xi,j = Di,j условие оптимальности оценки Si,j определяется следующим образом: Si,j <=0.
оценки Si,j для всех клеток, удовлетворяющих условию: Xi,j = 0 (неоптимальные выделены синим цветом)
S1,1 = c1,1 - (v1 + u1) = -3.
S1,2 = c1,2 - (v2 + u1) = -1.
S2,1 = c2,1 - (v1 + u2) = 0.
S2,3 = c2,3 - (v3 + u2) = 2.
S3,3 = c3,3 - (v3 + u3) = 3.
S3,4 = c3,4 - (v4 + u3) = 2.
оценки Si,j для всех клеток, удовлетворяющих условию: Xi,j = Di,j (неоптимальные выделены красным цветом)
отсутствуют
Если имеются неоптимальные оценки и для случая Xi,j = 0, и для случая Xi,j = Di,j, то наиболее потенциальной(неоптимальной) из них считается максимальная по модулю оценка. Если имеется несколько клеток с одним и тем же наиболее неоптимальным значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (1,1). Для нее оценка равна -3.
Строим для этой клетки цикл, помечая клетки цикла знаками "плюс" и "минус".

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

A1

+

5

M

 

8

M

 

2

9

M

 

-

0

9

M

 

18

A2

8

M

 

-

9

16

M

 

4

M

 

+

0

6

M

 

22

A3

-

6

12

M

 

+

7

3

M

 

3

M

 

0

M

 

15

Потребность

12

19

9

15

 

Перемещаем по циклу груз величиной в 9 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".
В результате перемещения по циклу получим новый план:

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

A1

5

9

M

 

8

M

 

2

9

M

 

0

M

 

18

A2

8

M

 

9

7

M

 

4

M

 

0

15

M

 

22

A3

6

3

M

 

7

12

M

 

3

M

 

0

M

 

15

Потребность

12

19

9

15

 

Целевая функция F= 228

Значение целевой функции изменилось на 27 единиц по сравнению с предыдущим этапом.

Этап 5

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Uj+Vi=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки.
Потенциалы Ui:
U1=0
V1=C1,1-U1= 5
V3=C1,3-U1= 2
U3=C1,3-V1= 1
V2=C3,2-U3= 6
U2=C2,2-V2= 3
V4=C2,4-U2= -3
Определяем значения оценок Si,j=Ci,j-(Vj-Ui) для всех свободных клеток:
Для случая Xi,j = 0 условие оптимальности оценки Si,j определяется следующим образом: Si,j >=0.
Для случая Xi,j = Di,j условие оптимальности оценки Si,j определяется следующим образом: Si,j <=0.
оценки Si,j для всех клеток, удовлетворяющих условию: Xi,j = 0 (неоптимальные выделены синим цветом)
S1,2 = c1,2 - (v2 + u1) = 2.
S1,4 = c1,4 - (v4 + u1) = 3.
S2,1 = c2,1 - (v1 + u2) = 0.
S2,3 = c2,3 - (v3 + u2) = -1.
S3,3 = c3,3 - (v3 + u3) = 0.
S3,4 = c3,4 - (v4 + u3) = 2.
оценки Si,j для всех клеток, удовлетворяющих условию: Xi,j = Di,j (неоптимальные выделены красным цветом)
отсутствуют
Если имеются неоптимальные оценки и для случая Xi,j = 0, и для случая Xi,j = Di,j, то наиболее потенциальной(неоптимальной) из них считается максимальная по модулю оценка. Если имеется несколько клеток с одним и тем же наиболее неоптимальным значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (2,3). Для нее оценка равна -1.
Строим для этой клетки цикл, помечая клетки цикла знаками "плюс" и "минус".

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

A1

+

5

9

M

 

8

M

 

-

2

9

M

 

0

M

 

18

A2

8

M

 

-

9

7

M

 

+

4

M

 

0

15

M

 

22

A3

-

6

3

M

 

+

7

12

M

 

3

M

 

0

M

 

15

Потребность

12

19

9

15

 

Перемещаем по циклу груз величиной в 3 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".
В результате перемещения по циклу получим новый план:

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

A1

5

12

M

 

8

M

 

2

6

M

 

0

M

 

18

A2

8

M

 

9

4

M

 

4

3

M

 

0

15

M

 

22

A3

6

M

 

7

15

M

 

3

M

 

0

M

 

15

Потребность

12

19

9

15

 

Целевая функция F= 225

Значение целевой функции изменилось на 3 единиц по сравнению с предыдущим этапом.

Этап 6

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Uj+Vi=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки.
Потенциалы Ui:
U1=0
V1=C1,1-U1= 5
V3=C1,3-U1= 2
U2=C3,2-V3= 2
V2=C2,2-U2= 7
V4=C2,4-U2= -2
U3=C2,3-V2= 0
Определяем значения оценок Si,j=Ci,j-(Vj-Ui) для всех свободных клеток:
Для случая Xi,j = 0 условие оптимальности оценки Si,j определяется следующим образом: Si,j >=0.
Для случая Xi,j = Di,j условие оптимальности оценки Si,j определяется следующим образом: Si,j <=0.
оценки Si,j для всех клеток, удовлетворяющих условию: Xi,j = 0 (неоптимальные выделены синим цветом)
S1,2 = c1,2 - (v2 + u1) = 1.
S1,4 = c1,4 - (v4 + u1) = 2.
S2,1 = c2,1 - (v1 + u2) = 1.
S3,1 = c3,1 - (v1 + u3) = 1.
S3,3 = c3,3 - (v3 + u3) = 1.
S3,4 = c3,4 - (v4 + u3) = 2.
оценки Si,j для всех клеток, удовлетворяющих условию: Xi,j = Di,j (неоптимальные выделены красным цветом)
отсутствуют
Так как все условия оптимальности выполнены, то полученный план является оптимальным.
Транспортная задача решена.

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

A1

5

12

M

 

8

M

 

2

6

M

 

0

M

 

18

A2

8

M

 

9

4

M

 

4

3

M

 

0

15

M

 

22

A3

6

M

 

7

15

M

 

3

M

 

0

M

 

15

Потребность

12

19

9

15

 

Целевая функция F= 225
15 единиц груза из хранилища A2 осталось нераспределенным.