1. Транспортная модель будет иметь следующий вид: требуется составить план перевозок x = (x₁₁, x₁₂,..., x₁₅, x₂₁,..., x₂₅, x₃₁,..., x₃₅), удовлетворяющий условиям


и минимизирующий целевую функцию


Решение разбиваем на два этапа: построение исходного допустимого плана одним из известных методов (северо-западного угла, двойного предпочтения, наименьших стоимостей и т.п.) и оптимизация его методом потенциалов.

2. Метод наименьших стоимостей состоит в следующем:
выбираем перевозку с наименьшей стоимостью (если таких несколько, выбираем любую);
определяем максимально возможную отгрузку как минимум из величины потребности соответствующего потребителя и запаса соответствующего поставщика;
уменьшаем потребность и запас на величину отгрузки;
если потребность стала равна нулю, то исключаем соответствующего потребителя из дальнейшего рассмотрения;
аналогично, если запас стал равен нулю, то исключаем соответствующего поставщика;
повторяем для оставшихся потребителей и поставщиков, пока не будут распределены все запасы и удовлетворены все потребности.
Метод удобно реализовать в виде таблицы, которая в данном случае будет иметь следующий вид:

28	12	7	18	7	280
35	14	12	15	3	300
30	16	11	25	15	220
170	120	190	140	180	800

Здесь правый столбец содержит запасы, нижняя строка - потребности, нижняя правая клетка - общий баланс, остальные клетки - стоимость перевозок. Наименьшая стоимость перевозки в таблице равна 3 (клетка 2:5). Потребность равна 180, запас - 300, поэтому отгрузка будет равна min(180,300)=180.

28	12	7	18	7	280
35	14	12	15	3	300
30	16	11	25	15	220
170	120	190	140	180	800

Потребность потребителя 5 стала равна 180-180=0, запас поставщика 2 стал равен 300-180=120, поэтому исключаем из дальнейшего рассмотрения пятый столбец (соответствующую потребителю 5).

28	12	7	18	7	280
35	14	12	15	3*180	120
30	16	11	25	15	220
170	120	190	140	0	620

В оставшейся части таблицы наименьшая стоимость перевозки будет равна 7 (клетка 1:3). Потребность равна 190, запас - 280, поэтому отгрузка будет равна min(190,280)=190.

28	12	7	18	7	280
35	14	12	15	3*180	120
30	16	11	25	15	220
170	120	190	140	0	620

Потребность потребителя 3 стала равна 190-190=0, запас поставщика 1 стал равен 280-190=90, поэтому исключаем из дальнейшего рассмотрения третий столбец.

28	12	7*190	18	7	90
35	14	12	15	3*180	120
30	16	11	25	15	220
170	120	0	140	0	430

Дальше действуем аналогично: клетка 1:2 (стоимость 12) с отгрузкой min(120,90)=90 и исключением первого поставщика

28	12*90	7*190	18	7	0
35	14	12	15	3*180	120
30	16	11	25	15	220
170	30	0	140	0	340

клетка 2:2 (стоимость 14) с отгрузкой min(30,120)=30 и исключением второго потребителя

28	12*90	7*190	18	7	0
35	14*30	12	15	3*180	90
30	16	11	25	15	220
170	0	0	140	0	310

клетка 2:4 (стоимость 15) с отгрузкой min(140,90)=90 и исключением второго поставщика

28	12*90	7*190	18	7	0
35	14*30	12	15*90	3*180	0
30	16	11	25	15	220
170	0	0	50	0	220

для единственного оставшегося поставщика 3 отгрузки выбираются однозначно

28	12*90	7*190	18	7	0
35	14*30	12	15*90	3*180	0
30*170	16	11	25*50	15	0
0	0	0	0	0	0

Все строки и столбцы исключены (то есть оставшиеся потребности и запасы равны нулю), следовательно, опорный план построен верно. Вычислим общую стоимость перевозок:


3. Метод потенциалов для оптимизации опорного решения выглядит следующим образом:
всем поставщикам i и потребителям j ставим в соответствие некоторые значения u_i и v_j, называемые потенциалами. Один из потенциалов задаём (например, u₁=0), остальные определяем исходя из того, что для стоимости c_ij поставки, входящей в опорное решение, должно выполняться равенство c_ij=u_i+v_j;
находим для всех поставок оценки по формуле ?_ij=c_ij-(u_i+v_j). Для поставок, входящих в опорное решение, они будут нулевые, для остальных могут отличаться от нуля;
если нет отрицательных оценок, то текущее решение является оптимальным, и оптимизация заканчивается;
в противном случае выбираем ячейку с наименьшей оценкой (то есть с максимальной по абсолютной величине отрицательной оценкой;
начиная с выбранной ячейки, строим в таблице замкнутый цикл, содержащий ячейки опорного решения;
обходим ячейки цикла в произвольном порядке, помечая их по очереди как "положительные" и "отрицательные" (выбранная ячейка с наименьшей оценкой помечается как "положительная");
находим минимальное значение величины поставки для всех "отрицательных" ячеек;
уменьшаем на эту величину объёмы поставок для всех "отрицательных" ячеек цикла и увеличиваем - для всех "положительных";
получаем новое опорное решение, для которого повторяем всё сначала.

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

28	12*90	7*190	18	7	280
35	14*30	12	15*90	3*180	300
30*170	16	11	25*50	15	220
170	120	190	140	180	800

Вычислим потенциалы:
u₁=0;
c₁₂=u₁+v₂=12 ⇒ v₂=12-0=12;
c₁₃=u₁+v₃=7 ⇒ v₄=7-0=7;
c₂₂=u₂+v₂=14 ⇒ u₂=14-12=2;
c₂₄=u₂+v₄=15 ⇒ v₄=15-2=13;
c₂₅=u₂+v₅=3 ⇒ v₅=3-2=1;
c₃₄=u₃+v₄=25 ⇒ u₃=25-13=12;
c₃₁=u₃+v₁=30 ⇒ v₁=30-12=18
добавим их в таблицу:

28	12*90	7*190	18	7	280	0
35	14*30	12	15*90	3*180	300	2
30*170	16	11	25*50	15	220	12
170	120	190	140	180	800
18	12	7	13	1

найдём оценки поставок:
Δ₁₁=c₁₁-(u₁+v₁)=28-(0+18)=10;
Δ₁₄=c₁₄-(u₁+v₄)=18-(0+13)=5;
Δ₁₅=c₁₅-(u₁+v₅)=7-(0+1)=7;
Δ₂₁=c₂₁-(u₂+v₁)=35-(2+18)=15;
Δ₂₃=c₂₃-(u₂+v₃)=12-(2+7)=3;
Δ₃₂=c₃₂-(u₃+v₂)=16-(12+12)=-8;
Δ₃₃=c₃₃-(u₃+v₃)=11-(12+7)=-8;
Δ₃₅=c₃₅-(u₃+v₅)=15-(12+1)=2
(остальные равны 0) и добавим их в таблицу (для ячеек, не входящих в опорное решение):

28/10	12*90	7*190	18/5	7/7	280
35/15	14*30	12/3	15*90	3*180	300
30*170	16/-8	11/-8	25*50	15/2	220
170	120	190	140	180	800

(значения потенциалов больше не требуются). Отрицательную оценку (-8) содержат две ячейки - 3:2 и 3:3. Выберем любую, например 3:2. Вместе с ячейками 2:2, 2:4 и 3:4 она образует замкнутый цикл, в котором ячейки 3:2 и 2:4 - "положительные", а 2:2 и 3:4 - "отрицательные":

28/10	12*90	7*190	18/5	7/7	280
35/15	14*30	12/3	15*90	3*180	300
30*170	16/-8	11/-8	25*50	15/2	220
170	120	190	140	180	800

Среди "отрицательных" ячеек наименьшее значение поставки достигается в 2:2 (30). Уменьшаем на 30 объём поставок для ячеек 2:2 и 3:4, увеличиваем на 30 объём поставок для ячеек 3:2 и 2:4. Получаем новое опорное решение:

28	12*90	7*190	18	7	280
35	14	12	15*120	3*180	300
30*170	16*30	11	25*20	15	220
170	120	190	140	180	800

и вычисляем новую стоимость перевозок:

Можно заметить, что по сравнению с исходным опорным решением стоимость изменилась на величину -240 = -8·30, равную произведению оценки выбранной ячейки (-8) на величину изменения объёмов поставок для ячеек цикла (30).
Вычислим потенциалы:
u₁=0;
c₁₂=u₁+v₂=12 ⇒ v₂=12-0=12;
c₁₃=u₁+v₃=7 ⇒ v₃=7-0=7;
c₃₂=u₃+v₂=16 ⇒ u₃=16-12=4;
c₃₁=u₃+v₁=30 ⇒ v₁=30-4=26;
c₃₄=u₃+v₄=25 ⇒ v₄=25-4=21;
c₂₄=u₂+v₄=15 ⇒ u₂=15-21=-6;
c₂₅=u₂+v₅=3 ⇒ v₅=3-(-6)=9
добавим их в таблицу

28	12*90	7*190	18	7	280	0
35	14	12	15*120	3*180	300	-6
30*170	16*30	11	25*20	15	220	4
170	120	190	140	180	800
26	12	7	21	9

найдём ненулевые оценки поставок:
Δ₁₁=c₁₁-(u₁+v₁)=28-(0+26)=2;
Δ₁₄=c₁₄-(u₁+v₄)=18-(0+9)=9;
Δ₁₅=c₁₅-(u₁+v₅)=7-(0+9)=-2;
Δ₂₁=c₂₁-(u₂+v₁)=35-(-6+26)=15;
Δ₂₂=c₂₂-(u₂+v₂)=14-(-6+12)=8;
Δ₂₃=c₂₃-(u₂+v₃)=12-(-6+7)=11;
Δ₃₃=c₃₃-(u₃+v₃)=11-(4+7)=0;
Δ₃₅=c₃₅-(u₃+v₅)=15-(4+9)=2
и добавим их в таблицу:

28/2	12*90	7*190	18/9	7/-2	280
35/15	14/8	12/11	15*120	3*180	300
30*170	16*30	11/0	25*20	15/2	220
170	120	190	140	180	800

Отрицательную оценку (-2) содержит ячеёка 1:5. Вместе с ячейками 1:2, 3:2, 3:4, 2:4 и 2:5 она образует замкнутый цикл, в котором ячейки 1:5, 3:2 и 2:4 - "положительные", а 1:2, 3:4 и 2:5 - "отрицательные":

28/2	12*90	7*190	18/9	7/-2	280
35/15	14/8	12/11	15*120	3*180	300
30*170	16*30	11/0	25*20	15/2	220
170	120	190	140	180	800

Среди "отрицательных" ячеек наименьшее значение поставки (20) достигается в 3:4. Уменьшаем на 20 объём поставок для ячеек 1:2, 3:4 и 2:5, увеличиваем на 20 объём поставок для ячеек 1:5, 3:2 и 2:4. Получаем новое опорное решение:

28	12*70	7*190	18	7*20	280
35	14	12	15*140	3*160	300
30*170	16*50	11	25	15	220
170	120	190	140	180	800

и вычисляем новую стоимость перевозок:

либо как

Для нового решения вычислим потенциалы:
u₁=0;
c₁₂=u₁+v₂=12 ⇒ v₂=12-0=12;
c₁₃=u₁+v₃=7 ⇒ v₃=7-0=7;
c₁₅=u₁+v₅=7 ⇒ v₅=7-0=7;
c₂₅=u₂+v₅=3 ⇒ u₂=3-7=-4;
c₂₄=u₂+v₄=15 ⇒ v₄=15-(-4)=19;
c₃₂=u₃+v₂=16 ⇒ u₃=16-12=4;
c₃₁=u₃+v₁=30 ⇒ v₁=30-4=26;
добавим их в таблицу

28	12*70	7*190	18	7*20	280	0
35	14	12	15*140	3*160	300	-4
30*170	16*50	11	25	15	220	4
170	120	190	140	180	800
26	12	7	19	7

найдём ненулевые оценки поставок:
Δ₁₁=c₁₁-(u₁+v₁)=28-(0+26)=2;
Δ₁₄=c₁₄-(u₁+v₄)=18-(0+19)=-1;
Δ₂₁=c₂₁-(u₂+v₁)=35-(-4+26)=13;
Δ₂₂=c₂₂-(u₂+v₂)=14-(-4+12)=6;
Δ₂₃=c₂₃-(u₂+v₃)=12-(-4+7)=9;
Δ₃₃=c₃₃-(u₃+v₃)=11-(4+7)=0;
Δ₃₄=c₃₄-(u₃+v₄)=25-(4+19)=2;
Δ₃₅=c₃₅-(u₃+v₅)=15-(4+9)=2
и добавим их в таблицу:

28/2	12*70	7*190	18/-1	7*20	280
35/13	14/6	12/9	15*140	3*160	300
30*170	16*50	11/0	25/2	15/2	220
170	120	190	140	180	800

Отрицательную оценку (-1) содержит ячеёка 1:4. Вместе с ячейками 2:4, 2:5 и 3:5 она образует замкнутый цикл, в котором ячейки 1:4 и 2:5 - "положительные", а 2:4 и 1:5 - "отрицательные":

28/2	12*70	7*190	18/-1	7*20	280
35/13	14/6	12/9	15*140	3*160	300
30*170	16*50	11/0	25/2	15/2	220
170	120	190	140	180	800

Среди "отрицательных" ячеек наименьшее значение поставки (20) достигается в 1:5. Уменьшаем на 20 объём поставок для ячеек 1:5 и 2:4, увеличиваем на 20 объём поставок для ячеек 1:4 и 2:5. Получаем новое опорное решение:

28	12*70	7*190	18*20	7	280
35	14	12	15*120	3*180	300
30*170	16*50	11	25	15	220
170	120	190	140	180	800

и вычисляем новую стоимость перевозок:

либо как

Для нового решения вычислим потенциалы:
u₁=0;
c₁₂=u₁+v₂=12 ⇒ v₂=12-0=12;
c₁₃=u₁+v₃=7 ⇒ v₃=7-0=7;
c₁₄=u₁+v₄=18 ⇒ v₄=18-0=18;
c₂₄=u₂+v₄=15 ⇒ u₂=15-18=-3;
c₂₅=u₂+v₅=3 ⇒ v₅=3-(-3)=6;
c₃₂=u₃+v₂=16 ⇒ u₃=16-12=4;
c₃₁=u₃+v₁=30 ⇒ v₁=30-4=26;
добавим их в таблицу

28	12*70	7*190	18*20	7	280	0
35	14	12	15*120	3*180	300	-3
30*170	16*50	11	25	15	220	4
170	120	190	140	180	800
26	12	7	18	6

найдём ненулевые оценки поставок:
Δ₁₁=c₁₁-(u₁+v₁)=28-(0+26)=2;
Δ₁₅=c₁₅-(u₁+v₅)=7-(0+5)=2;
Δ₂₁=c₂₁-(u₂+v₁)=35-(-3+26)=12;
Δ₂₂=c₂₂-(u₂+v₂)=14-(-3+12)=5;
Δ₂₃=c₂₃-(u₂+v₃)=12-(-3+7)=8;
Δ₃₃=c₃₃-(u₃+v₃)=11-(4+7)=0;
Δ₃₄=c₃₄-(u₃+v₄)=25-(4+18)=3;
Δ₃₅=c₃₅-(u₃+v₅)=15-(4+6)=5.
Отрицательных оценок нет, следовательно, последнее решение со стоимостью 10770 является оптимальным. Соответствующий план перевозок можно записать как

Последнее редактирование 27.02.2022, 20:13 Коцюрбенко Алексей Владимирович (Старший модератор)