Транспортная задача. Пример решения.

Задача:

Решение.

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

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

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

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

Находим незанятую клетку с минимальным тарифом: (1,4).
Помещаем туда меньшее из чисел A₁^*=18, B₄^*=15 и D_1,4=M
Находим незанятую клетку с минимальным тарифом: (1,3).
Помещаем туда меньшее из чисел A₁^*=3, B₃^*=9 и D_1,3=M
Находим незанятую клетку с минимальным тарифом: (3,3).
Помещаем туда меньшее из чисел A₃^*=15, B₃^*=6 и D_3,3=M
Находим незанятую клетку с минимальным тарифом: (3,1).
Помещаем туда меньшее из чисел A₃^*=9, B₁^*=12 и D_3,1=M
Находим незанятую клетку с минимальным тарифом: (2,1).
Помещаем туда меньшее из чисел A₂^*=22, B₁^*=3 и D_2,1=M
Находим незанятую клетку с минимальным тарифом: (2,2).
Помещаем туда меньшее из чисел A₂^*=19, B₂^*=19 и D_2,2=M

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

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

Этап 1

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

Этап 2

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_j+V_i=C_i,j(i=1..m, j=1..n), просматривая все занятые клетки.
Потенциалы U_i:
U₁=0
V₃=C_1,3-U₁= 2
V₄=C_1,4-U₁= 0
U₃=C_3,3-V₃= 1
V₁=C_3,1-U₃= 5
U₂=C_1,2-V₁= 3
V₂=C_2,2-U₂= 6
Определяем значения оценок 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₁) = 0.
S_1,2 = c_1,2 - (v₂ + u₁) = 2.
S_2,3 = c_2,3 - (v₃ + u₂) = -1.
S_2,4 = c_2,4 - (v₄ + u₂) = -3.
S_3,2 = c_3,2 - (v₂ + u₃) = 0.
S_3,4 = c_3,4 - (v₄ + u₃) = -1.
оценки S_i,j для всех клеток, удовлетворяющих условию: X_i,j = D_i,j (неоптимальные выделены красным цветом)
отсутствуют
Если имеются неоптимальные оценки и для случая X_i,j = 0, и для случая X_i,j = D_i,j, то наиболее потенциальной(неоптимальной) из них считается максимальная по модулю оценка. Если имеется несколько клеток с одним и тем же наиболее неоптимальным значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (2,4). Для нее оценка равна -3.

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

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

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

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

Этап 3

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_j+V_i=C_i,j(i=1..m, j=1..n), просматривая все занятые клетки.
Потенциалы U_i:
U₁=0
V₃=C_1,3-U₁= 2
V₄=C_1,4-U₁= 0
U₃=C_3,3-V₃= 1
U₂=C_4,2-V₄= 0
V₂=C_2,2-U₂= 9
V₁=C_3,1-U₃= 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₁) = 0.
S_1,2 = c_1,2 - (v₂ + u₁) = -1.
S_2,1 = c_2,1 - (v₁ + u₂) = 3.
S_2,3 = c_2,3 - (v₃ + u₂) = 2.
S_3,2 = c_3,2 - (v₂ + u₃) = -3.
S_3,4 = c_3,4 - (v₄ + u₃) = -1.
оценки S_i,j для всех клеток, удовлетворяющих условию: X_i,j = D_i,j (неоптимальные выделены красным цветом)
отсутствуют
Если имеются неоптимальные оценки и для случая X_i,j = 0, и для случая X_i,j = D_i,j, то наиболее потенциальной(неоптимальной) из них считается максимальная по модулю оценка. Если имеется несколько клеток с одним и тем же наиболее неоптимальным значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (3,2). Для нее оценка равна -3.
Строим для этой клетки цикл, помечая клетки цикла знаками "плюс" и "минус".

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

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

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

Этап 4

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_j+V_i=C_i,j(i=1..m, j=1..n), просматривая все занятые клетки.
Потенциалы U_i:
U₁=0
V₃=C_1,3-U₁= 2
V₄=C_1,4-U₁= 0
U₂=C_4,2-V₄= 0
V₂=C_2,2-U₂= 9
U₃=C_2,3-V₂= -2
V₁=C_3,1-U₃= 8
Определяем значения оценок 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₁) = -3.
S_1,2 = c_1,2 - (v₂ + u₁) = -1.
S_2,1 = c_2,1 - (v₁ + u₂) = 0.
S_2,3 = c_2,3 - (v₃ + u₂) = 2.
S_3,3 = c_3,3 - (v₃ + u₃) = 3.
S_3,4 = c_3,4 - (v₄ + u₃) = 2.
оценки S_i,j для всех клеток, удовлетворяющих условию: X_i,j = D_i,j (неоптимальные выделены красным цветом)
отсутствуют
Если имеются неоптимальные оценки и для случая X_i,j = 0, и для случая X_i,j = D_i,j, то наиболее потенциальной(неоптимальной) из них считается максимальная по модулю оценка. Если имеется несколько клеток с одним и тем же наиболее неоптимальным значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (1,1). Для нее оценка равна -3.
Строим для этой клетки цикл, помечая клетки цикла знаками "плюс" и "минус".

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

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

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

Этап 5

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_j+V_i=C_i,j(i=1..m, j=1..n), просматривая все занятые клетки.
Потенциалы U_i:
U₁=0
V₁=C_1,1-U₁= 5
V₃=C_1,3-U₁= 2
U₃=C_1,3-V₁= 1
V₂=C_3,2-U₃= 6
U₂=C_2,2-V₂= 3
V₄=C_2,4-U₂= -3
Определяем значения оценок 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,2 = c_1,2 - (v₂ + u₁) = 2.
S_1,4 = c_1,4 - (v₄ + u₁) = 3.
S_2,1 = c_2,1 - (v₁ + u₂) = 0.
S_2,3 = c_2,3 - (v₃ + u₂) = -1.
S_3,3 = c_3,3 - (v₃ + u₃) = 0.
S_3,4 = c_3,4 - (v₄ + u₃) = 2.
оценки S_i,j для всех клеток, удовлетворяющих условию: X_i,j = D_i,j (неоптимальные выделены красным цветом)
отсутствуют
Если имеются неоптимальные оценки и для случая X_i,j = 0, и для случая X_i,j = D_i,j, то наиболее потенциальной(неоптимальной) из них считается максимальная по модулю оценка. Если имеется несколько клеток с одним и тем же наиболее неоптимальным значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (2,3). Для нее оценка равна -1.
Строим для этой клетки цикл, помечая клетки цикла знаками "плюс" и "минус".

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

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

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

Этап 6

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_j+V_i=C_i,j(i=1..m, j=1..n), просматривая все занятые клетки.
Потенциалы U_i:
U₁=0
V₁=C_1,1-U₁= 5
V₃=C_1,3-U₁= 2
U₂=C_3,2-V₃= 2
V₂=C_2,2-U₂= 7
V₄=C_2,4-U₂= -2
U₃=C_2,3-V₂= 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,2 = c_1,2 - (v₂ + u₁) = 1.
S_1,4 = c_1,4 - (v₄ + u₁) = 2.
S_2,1 = c_2,1 - (v₁ + u₂) = 1.
S_3,1 = c_3,1 - (v₁ + u₃) = 1.
S_3,3 = c_3,3 - (v₃ + u₃) = 1.
S_3,4 = c_3,4 - (v₄ + u₃) = 2.
оценки S_i,j для всех клеток, удовлетворяющих условию: X_i,j = D_i,j (неоптимальные выделены красным цветом)
отсутствуют
Так как все условия оптимальности выполнены, то полученный план является оптимальным.
Транспортная задача решена.

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