Примем некоторые обозначения: i - индекс строки j - индекс столбца m - количество поставщиков n - количество потребителей Xi,j - перевозка между поставщиком Ai и потребителем Bj. Di,j - ограничение

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

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

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

B5

A1

	M

	M

	M

	M

	M

A2

	M

	M

	M

	M

	M

A3

	M

	M

	M

	M

	M

A4

	M

	M

	M

	M

	M

Потребность

Транспортная задача имеет закрытый тип, так как суммарный запас груза равен суммарным потребностям.
Находим опорный план для задачи с ограничениями.
Введем некоторые обозначения:
A_i^* - излишек нераспределенного груза от поставщика A_i
B_j^* - недостача в поставке груза потребителю B_j
D_i,j - ограничение пропускной способности коммуникации между поставщиком A_i и потребителем B_j

Находим незанятую клетку с минимальным тарифом: (1,4).
Помещаем туда меньшее из чисел A₁^*=100, B₄^*=100 и D_1,4= M
Находим незанятую клетку с минимальным тарифом: (2,1).
Помещаем туда меньшее из чисел A₂^*=250, B₁^*=200 и D_2,1= M
Находим незанятую клетку с минимальным тарифом: (3,5).
Помещаем туда меньшее из чисел A₃^*=200, B₅^*=250 и D_3,5= M
Находим незанятую клетку с минимальным тарифом: (2,2).
Помещаем туда меньшее из чисел A₂^*=50, B₂^*=200 и D_2,2= M
Находим незанятую клетку с минимальным тарифом: (4,2).
Помещаем туда меньшее из чисел A₄^*=300, B₂^*=150 и D_4,2= M
Находим незанятую клетку с минимальным тарифом: (4,3).
Помещаем туда меньшее из чисел A₄^*=150, B₃^*=100 и D_4,3= M
Находим незанятую клетку с минимальным тарифом: (4,5).
Помещаем туда меньшее из чисел A₄^*=50, B₅^*=50 и D_4,5= M

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

B5

A1

	M

	M

	M

	M

	M

A2

	M

	M

	M

	M

	M

A3

	M

	M

	M

	M

	M

A4

	M

	M

	M

	M

	M

Потребность

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

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

Этап 1

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

Этап 2

Опорный план является вырожденным, так как число занятых клеток, удовлетворяющих условию 0 < X_i,j < D_i,j меньше, чем m+n-1=8.
Перечислим эти клетки: (1,4) (2,1) (2,2) (3,5) (4,2) (4,3) (4,5)

Сделаем план невырожденным, добавляя (в случае X_i,j = 0) или отнимая (в случае X_i,j = D_i,j) бесконечно малые, не равные между собой фиктивные перевозки e, 2e, 3e... в клетки с координатами (i,j): (3,4)
Введение в план фиктивных перевозок необходимо для избежания зацикливания в ходе решения задачи. При их введении будем модифицировать потребности/запасы груза соответствующих потребителей/поставщиков для сохранения баланса между запасами/потребностями

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

B5

A1

	M

	M

	M

	M

	M

A2

	M

	M

	M

	M

	M

A3

	M

	M

	M

e	M

	M

200+e

A4

	M

	M

	M

	M

	M

Потребность

100+e

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_j+V_i=C_i,j(i=1..m, j=1..n), просматривая все занятые клетки.
Потенциалы U_i:
U₁=0
V₄=C_1,4-U₁= 1
U₃=C_4,3-V₄= 1
V₅=C_3,5-U₃= 1
U₄=C_5,4-V₅= 12
V₂=C_4,2-U₄= -4
V₃=C_4,3-U₄= 0
U₂=C_2,2-V₂= 11
V₁=C_2,1-U₂= -9

Определяем значения оценок S_i,j=C_i,j-(V_j-U_i) для всех свободных клеток:
Для случая X_i,j = 0 условие оптимальности оценки S_i,j определяется следующим образом: S_i,j >=0.
Для случая X_i,j = D_i,j условие оптимальности оценки S_i,j определяется следующим образом: S_i,j <=0.
оценки S_i,j для всех клеток, удовлетворяющих условию: X_i,j = 0 (неоптимальные выделены синим цветом)
S_1,1 = c_1,1 - (v₁ + u₁) = 19.
S_1,2 = c_1,2 - (v₂ + u₁) = 11.
S_1,3 = c_1,3 - (v₃ + u₁) = 4.
S_1,5 = c_1,5 - (v₅ + u₁) = 3.
S_2,3 = c_2,3 - (v₃ + u₂) = -1.
S_2,4 = c_2,4 - (v₄ + u₂) = -6.
S_2,5 = c_2,5 - (v₅ + u₂) = -1.
S_3,1 = c_3,1 - (v₁ + u₃) = 16.
S_3,2 = c_3,2 - (v₂ + u₃) = 8.
S_3,3 = c_3,3 - (v₃ + u₃) = 2.
S_4,1 = c_4,1 - (v₁ + u₄) = 8.
S_4,4 = c_4,4 - (v₄ + u₄) = 3.
оценки S_i,j для всех клеток, удовлетворяющих условию: X_i,j = D_i,j (неоптимальные выделены красным цветом)
отсутствуют

Если имеются неоптимальные оценки и для случая X_i,j = 0, и для случая X_i,j = D_i,j, то наиболее потенциальной(неоптимальной) из них считается максимальная по модулю оценка. Если имеется несколько клеток с одним и тем же наиболее неоптимальным значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (2,4). Для нее оценка равна -6.

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

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

B5

A1

	M

	M

	M

	M

	M

A2

	M

-
	M

	M

+
	M

	M

A3

	M

	M

	M

-
e	M

+
	M

200+e

A4

	M

+
	M

	M

	M

-
	M

Потребность

100+e

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

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

B5

A1

	M

	M

	M

	M

	M

A2

	M

50-e	M

	M

e	M

	M

A3

	M

	M

	M

	M

200+e	M

200+e

A4

	M

150+e	M

	M

	M

50-e	M

Потребность

100+e

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

Этап 3

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_j+V_i=C_i,j(i=1..m, j=1..n), просматривая все занятые клетки.
Потенциалы U_i:
U₁=0
V₄=C_1,4-U₁= 1
U₂=C_4,2-V₄= 5
V₁=C_2,1-U₂= -3
V₂=C_2,2-U₂= 2
U₄=C_2,4-V₂= 6
V₃=C_4,3-U₄= 6
V₅=C_4,5-U₄= 7
U₃=C_5,3-V₅= -5

Определяем значения оценок S_i,j=C_i,j-(V_j-U_i) для всех свободных клеток:
Для случая X_i,j = 0 условие оптимальности оценки S_i,j определяется следующим образом: S_i,j >=0.
Для случая X_i,j = D_i,j условие оптимальности оценки S_i,j определяется следующим образом: S_i,j <=0.
оценки S_i,j для всех клеток, удовлетворяющих условию: X_i,j = 0 (неоптимальные выделены синим цветом)
S_1,1 = c_1,1 - (v₁ + u₁) = 13.
S_1,2 = c_1,2 - (v₂ + u₁) = 5.
S_1,3 = c_1,3 - (v₃ + u₁) = -2.
S_1,5 = c_1,5 - (v₅ + u₁) = -3.
S_2,3 = c_2,3 - (v₃ + u₂) = -1.
S_2,5 = c_2,5 - (v₅ + u₂) = -1.
S_3,1 = c_3,1 - (v₁ + u₃) = 16.
S_3,2 = c_3,2 - (v₂ + u₃) = 8.
S_3,3 = c_3,3 - (v₃ + u₃) = 2.
S_3,4 = c_3,4 - (v₄ + u₃) = 6.
S_4,1 = c_4,1 - (v₁ + u₄) = 8.
S_4,4 = c_4,4 - (v₄ + u₄) = 9.
оценки S_i,j для всех клеток, удовлетворяющих условию: X_i,j = D_i,j (неоптимальные выделены красным цветом)
отсутствуют

Если имеются неоптимальные оценки и для случая X_i,j = 0, и для случая X_i,j = D_i,j, то наиболее потенциальной(неоптимальной) из них считается максимальная по модулю оценка. Если имеется несколько клеток с одним и тем же наиболее неоптимальным значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (1,5). Для нее оценка равна -3.

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

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

B5

A1

	M

	M

	M

-
	M

+
	M

A2

	M

-
50-e	M

	M

+
e	M

	M

A3

	M

	M

	M

	M

200+e	M

200+e

A4

	M

+
150+e	M

	M

	M

-
50-e	M

Потребность

100+e

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

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

B5

A1

	M

	M

	M

50+e	M

50-e	M

A2

	M

	M

	M

	M

	M

A3

	M

	M

	M

	M

200+e	M

200+e

A4

	M

	M

	M

	M

	M

Потребность

100+e

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

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

Этап 4

Опорный план является вырожденным, так как число занятых клеток, удовлетворяющих условию 0 < X_i,j < D_i,j меньше, чем m+n-1=8.
Перечислим эти клетки: (1,4) (1,5) (2,1) (2,4) (3,5) (4,2) (4,3)

Сделаем план невырожденным, добавляя (в случае X_i,j = 0) или отнимая (в случае X_i,j = D_i,j) бесконечно малые, не равные между собой фиктивные перевозки e, 2e, 3e... в клетки с координатами (i,j): (3,3)
Введение в план фиктивных перевозок необходимо для избежания зацикливания в ходе решения задачи. При их введении будем модифицировать потребности/запасы груза соответствующих потребителей/поставщиков для сохранения баланса между запасами/потребностями

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

B5

A1

	M

	M

	M

50+e	M

50-e	M

A2

	M

	M

	M

	M

	M

A3

	M

	M

2e	M

	M

200+e	M

200+3e

A4

	M

	M

	M

	M

	M

Потребность

100+2e

100+e

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_j+V_i=C_i,j(i=1..m, j=1..n), просматривая все занятые клетки.
Потенциалы U_i:
U₁=0
V₄=C_1,4-U₁= 1
V₅=C_1,5-U₁= 4
U₂=C_4,2-V₄= 5
U₃=C_5,3-V₅= -2
V₁=C_2,1-U₂= -3
V₃=C_3,3-U₃= 5
U₄=C_3,4-V₃= 7
V₂=C_4,2-U₄= 1

Определяем значения оценок S_i,j=C_i,j-(V_j-U_i) для всех свободных клеток:
Для случая X_i,j = 0 условие оптимальности оценки S_i,j определяется следующим образом: S_i,j >=0.
Для случая X_i,j = D_i,j условие оптимальности оценки S_i,j определяется следующим образом: S_i,j <=0.
оценки S_i,j для всех клеток, удовлетворяющих условию: X_i,j = 0 (неоптимальные выделены синим цветом)
S_1,1 = c_1,1 - (v₁ + u₁) = 13.
S_1,2 = c_1,2 - (v₂ + u₁) = 6.
S_1,3 = c_1,3 - (v₃ + u₁) = -1.
S_2,2 = c_2,2 - (v₂ + u₂) = 1.
S_2,3 = c_2,3 - (v₃ + u₂) = 0.
S_2,5 = c_2,5 - (v₅ + u₂) = 2.
S_3,1 = c_3,1 - (v₁ + u₃) = 13.
S_3,2 = c_3,2 - (v₂ + u₃) = 6.
S_3,4 = c_3,4 - (v₄ + u₃) = 3.
S_4,1 = c_4,1 - (v₁ + u₄) = 7.
S_4,4 = c_4,4 - (v₄ + u₄) = 8.
S_4,5 = c_4,5 - (v₅ + u₄) = 2.
оценки S_i,j для всех клеток, удовлетворяющих условию: X_i,j = D_i,j (неоптимальные выделены красным цветом)
отсутствуют

Если имеются неоптимальные оценки и для случая X_i,j = 0, и для случая X_i,j = D_i,j, то наиболее потенциальной(неоптимальной) из них считается максимальная по модулю оценка. Если имеется несколько клеток с одним и тем же наиболее неоптимальным значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (1,3). Для нее оценка равна -1.

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

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

B5

A1

	M

	M

+
	M

50+e	M

-
50-e	M

A2

	M

	M

	M

	M

	M

A3

	M

	M

-
2e	M

	M

+
200+e	M

200+3e

A4

	M

	M

	M

	M

	M

Потребность

100+2e

100+e

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

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

B5

A1

	M

	M

2e	M

50+e	M

50-3e	M

A2

	M

	M

	M

	M

	M

A3

	M

	M

	M

	M

200+3e	M

200+3e

A4

	M

	M

	M

	M

	M

Потребность

100+2e

100+e

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

Этап 5

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_j+V_i=C_i,j(i=1..m, j=1..n), просматривая все занятые клетки.
Потенциалы U_i:
U₁=0
V₃=C_1,3-U₁= 4
V₄=C_1,4-U₁= 1
V₅=C_1,5-U₁= 4
U₄=C_3,4-V₃= 8
U₂=C_4,2-V₄= 5
U₃=C_5,3-V₅= -2
V₁=C_2,1-U₂= -3
V₂=C_4,2-U₄= 0

Определяем значения оценок S_i,j=C_i,j-(V_j-U_i) для всех свободных клеток:
Для случая X_i,j = 0 условие оптимальности оценки S_i,j определяется следующим образом: S_i,j >=0.
Для случая X_i,j = D_i,j условие оптимальности оценки S_i,j определяется следующим образом: S_i,j <=0.
оценки S_i,j для всех клеток, удовлетворяющих условию: X_i,j = 0 (неоптимальные выделены синим цветом)
S_1,1 = c_1,1 - (v₁ + u₁) = 13.
S_1,2 = c_1,2 - (v₂ + u₁) = 7.
S_2,2 = c_2,2 - (v₂ + u₂) = 2.
S_2,3 = c_2,3 - (v₃ + u₂) = 1.
S_2,5 = c_2,5 - (v₅ + u₂) = 2.
S_3,1 = c_3,1 - (v₁ + u₃) = 13.
S_3,2 = c_3,2 - (v₂ + u₃) = 7.
S_3,3 = c_3,3 - (v₃ + u₃) = 1.
S_3,4 = c_3,4 - (v₄ + u₃) = 3.
S_4,1 = c_4,1 - (v₁ + u₄) = 6.
S_4,4 = c_4,4 - (v₄ + u₄) = 7.
S_4,5 = c_4,5 - (v₅ + u₄) = 1.
оценки S_i,j для всех клеток, удовлетворяющих условию: X_i,j = D_i,j (неоптимальные выделены красным цветом)
отсутствуют

Так как все условия оптимальности выполнены, то полученный план является оптимальным.
Транспортная задача решена.

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

B5

A1

	M

	M

	M

	M

	M

A2

	M

	M

	M

	M

	M

A3

	M

	M

	M

	M

	M

A4

	M

	M

	M

	M

	M

Потребность

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

Дата добавления: 2015-11-04