Методом минимального элемента

Построение первоначального плана перевозок

Методом «северо-западного угла»

Стоимость доставки единицы продукции от поставщика к потребителю располагается в правом верхнем углу ячейки.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2	3	6	8	7	40
А₂	5	9	5	7	2	35
А₃	1	4	3	7	3	45
Потребность	20	26	16	38	20

Замечание. В дальнейшем все действия должны проводится в этой таблице, хотя для удобства изложения на каждом шаге заполнения таблица будет представлена заново.

Для решения задачи необходимо выполнение следующего условия:

Cуммарные запасы продукции у поставщиков должны равняться суммарной потребности потребителей.

Проверим.

Запасы поставщиков: 40 + 35 + 45 = 120 единиц продукции.

Потребность потребителей: 20 + 26 + 16 + 38 + 20 = 120 единиц продукции.

Таким образом, суммарные запасы продукции у поставщиков равны суммарной потребности потребителей.

Для решения задачи необходимо выполнение следующего условия:

количество задействованных маршрутов = количество поставщиков + количество потребителей - 1.

В нашем случае проверка правильности вычисления первоначального плана состоит в следующем:

m- количество строк (3)

n- количество столбцов (5)

m+n-1=5+3-1=7 (= количеству заполненных клеток)

Поэтому если возникнет ситуация, в которой будет необходимо исключить столбец и строку одновременно, мы исключим что-то одно.

Начинаем заполнять таблицу от левого верхнего угла (клетка A₁,B₁) и постепенно "двигаемся" к правому нижнему (от северо-запада к юго-востоку).

Клетка A₁,B₁ соответствует пункту поставщика A₁и пункту потребителя B₁. Запас груза в пункте A₁равен 40, а потребность в грузе в пункте B₁ – 20 единицам.

Удовлетворим потребность пункта B₁ за счет поставщика A₁ и впишем 20 в клетку A₁,B₁.

Тем самым, потребность для потребителя B₁ полностью удовлетворена (пишем 0 в нижней строчке столбца B₁) поставщиком А₁.

Столбец В1 из дальнейшего рассмотрения удаляем.

Запас в A₁ стал равным 40-20=20 (табл. 1)

Другими словами, в клетку A₁,B₁мы записываем , т.е. либо потребность потребителя удовлетворяется полностью, либо на величину имеющегося запаса продукции.

Таблица 1.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 20	3	6	8	7	40 20
А₂	5	9	5	7	2	35
А₃	1	4	3	7	3	45
Потребность	20 0	26	16	38	20

Переходим к следующей незаполненной северо-западной клетке. Это А1, В2 (стоимость равна 3).

В нее записываем . Остаток запаса в А1 стал равен 20-20=0. Запас полностью исчерпан. Потребность потребителя В2 стала равной 26-20=0 (табл. 2).

Строку А1 из дальнейшего рассмотрения удаляем.

Таблица 2.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 20	3 20	6	8	7	40 20 0
А₂	5	9	5	7	2	35
А₃	1	4	3	7	3	45
Потребность	20 0	26 6	16	38	20

Переходим к следующей незаполненной северо-западной клетке. Это А1, В2 (стоимость равна 3).

В нее записываем . Остаток запаса в А2 стал равен 35-6=29. Потребность потребителя В2 стала равной 6-6=0 полностью удовлетворена (табл. 3).

Столбец В2 из дальнейшего рассмотрения удаляем.

Таблица 3.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 20	3 20	6	8	7	40 20 0
А₂	5	9 6	5	7	2	35 29
А₃	1	4	3	7	3	45
Потребность	20 0	26 6 0	16	38	20

Переходим к следующей незаполненной северо-западной клетке. Это А2,В3 (стоимость равна 9).

В нее записываем . Остаток запаса в А2 стал равен 29-16=13. Потребность потребителя В3 стала равной 16-16=0, т.е. полностью удовлетворена (табл. 4).

Столбец В3 из дальнейшего рассмотрения удаляем.

Таблица 4.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 20	3 20	6	8	7	40 20 0
А₂	5	9 6	5 16	7	2	35 29 13
А₃	1	4	3	7	3	45
Потребность	20 0	26 6 0	16 0	38	20

Следующая северо-западная клетка А2,В4 (стоимость равна 7). В нее записываем . Остаток запаса в А2 стал равен 13-13=0. Потребность потребителя В4 стала равной 38-13=25. Строку A2 из дальнейшего рассмотрения удаляем. (табл. 5).

Таблица 5.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 20	3 20	6	8	7	40 20 0
А₂	5	9 6	5 16	7 13	2	35 29 13 0
А₃	1	4	3	7	3	45
Потребность	20 0	26 6 0	16 0	38 25	20

Следующая северо-западная клетка А3,В4 (стоимость равна 7). В нее записываем . Остаток запаса в А3 стал равен 45-25=20. Потребность в В4 равна 25-25=0 т.е. полностью удовлетворена (табл. 6).

Столбец В4 из дальнейшего рассмотрения удаляем.

Таблица 6.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 20	3 20	6	8	7	40 20 0
А₂	5	9 6	5 16	7 13	2	35 29 13 0
А₃	1	4	3	7 25	3	45 20
Потребность	20 0	26 6 0	16 0	38 25 0	20

Последняя клетка А3,В5 (стоимость равна 3). В нее записываем . Остаток запаса в А3 равен 20-20=0, потребность в В5 равна 20-20=0 (табл. 7). Итак, все распределено.

Таблица 7.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 20	3 20	6	8	7	40 20 0
А₂	5	9 6	5 16	7 13	2	35 29 13 0
А₃	1	4	3	7 25	3 20	45 20 0
Потребность	20 0	26 6 0	16 0	38 ~~25 0~~	20 0

Проверка правильности вычисления первоначального плана:

m- количество строк (3)

n- количество столбцов (5)

m + n -1=5+3-1=7 (= количеству заполненных клеток)

Построение первоначального плана методом «северо-западного угла» закончено.

Стоимость перевозки по этому плану:

z=20*2 + 20*3 + 6*9 + 16*5 + 13*7 + 25*7 + 20*3 = 560

Замечание: в отчете должна быть окончательная таблица №7 и расчет стоимости перевозки

Построение первоначального плана перевозок

методом минимального элемента

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, как и в предыдущем методе, помещают меньшее из чисел А_i или В_j. Затем, также как и в методе северо-западного угла, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.

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

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

Таблица 8.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2	3	6	8	7	40
А₂	5	9	5	7	2	35
А₃	1	4	3	7	3	45
Потребность	20	26	16	38	20

Находим клетку с наименьшей стоимостью доставки – это А3, В1 (стоимость равна 1).

В нее записываем . Остаток запаса в А3 стал равен 45-20=25. Потребность потребителя В1 стала равной 20-20=0 (полностью удовлетворена). Столбец В1 из дальнейшего рассмотрения удаляем (табл. 9)

Таблица 9.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2	3	6	8	7	40
А₂	5	9	5	7	2	35
А₃	1 20	4	3	7	3	45 25
Потребность	20 0	26	16	38	20

Следующая клетка с наименьшей стоимостью доставки – это А2, В5 (стоимость равна 2).

В нее записываем . Остаток запаса в А2 стал равен 35-20=15. Потребность потребителя В1 стала равной 20-20=0 (полностью удовлетворена) (табл.10).

Столбец В5 из дальнейшего рассмотрения удаляем.

Таблица 10.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2	3	6	8	7	40
А₂	5	9	5	7	2 20	35 15
А₃	1 20	4	3	7	3	45 25
Потребность	20 0	26	16	38	20 0

Следующая клетка с наименьшей стоимостью доставки – это А1, В2 (стоимость равна 3).

В нее записываем . Остаток запаса в А1 стал равен 40-26=14. Потребность потребителя В2 стала равной 26-26=0 (полностью удовлетворена) (табл.11).

Столбец В2 из дальнейшего рассмотрения удаляем.

Таблица 11.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2	3 26	6	8	7	40 14
А₂	5	9	5	7	2 20	35 15
А₃	1 20	4	3	7	3	45 25
Потребность	20 0	26 0	16	38	20 0

Следующая клетка с наименьшей стоимостью доставки – это А3, В3 (стоимость равна 3).

В нее записываем . Остаток запаса в А3 стал равен 25-16=9. Потребность потребителя В3 стала равной 16-16=0 (полностью удовлетворена) (табл.12).

Столбец В3 из дальнейшего рассмотрения удаляем.

Таблица 12.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2	3 26	6	8	7	40 14
А₂	5	9	5	7	2 20	35 15
А₃	1 20	4	3 16	7	3	45 25 9
Потребность	20 0	26 0	16 0	38	20 0

Следующая клетка с наименьшей стоимостью доставки – это А2, В4 (стоимость равна 7).

В нее записываем . Остаток запаса в А2 стал равен 15-15=0. Потребность потребителя В4 стала равной 38-15=23 (табл.12).

Таблица 12.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2	3 26	6	8	7	40 14
А₂	5	9	5	7 15	2 20	35 15 0
А₃	1 20	4	3 16	7	3	45 25 9
Потребность	20 0	26 0	16 0	38 23	20 0

Следующая клетка с наименьшей стоимостью доставки – это А3, В4 (стоимость равна 7).

В нее записываем . Остаток запаса в А3 стал равен 9-9=0. Потребность потребителя В4 стала равной 23-9=14

Таблица 13.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2	3 26	6	8	7	40 14
А₂	5	9	5	7 15	2 20	35 15 0
А₃	1 20	4	3 16	7 9	3	45 25 9 0
Потребность	20 0	26 0	16 0	38 23 14	20 0

Следующая клетка с наименьшей стоимостью доставки – это А1, В4 (стоимость равна 8).

В нее записываем . Остаток запаса в А1 стал равен 14-14=0. Потребность потребителя В4 стала равной 14-14=0 (полностью удовлетворена) (табл. 14).

Таблица 14.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2	3 26	6	8 14	7	~~40 14~~ 0
А₂	5	9	5	7 15	2 20	35 15 0
А₃	1 20	4	3 16	7 9	3	45 25 9 0
Потребность	20 0	26 0	16 0	38 23 14 0	20 0

Проверка правильности вычисления первоначального плана:

m- количество строк (3)

n- количество столбцов (5)

m + n -1=5+3-1=7 (= количеству заполненных клеток)

Стоимость перевозки по этому плану:

z = 26*3 + 14*8 + 15*7 + 20*2 + 20*1 + 16*3 + 9*7 = 466

Замечание. Стоимость перевозки, рассчитанная по методу наименьшей стоимости меньше, чем по методу северо-западного угла (как правило). В данном случае эта стоимость является оптимальной (совпадает со значением полученным в Excel). Однако, матрицы перевозок отличаются, т.е. решение, обеспечивающее минимум стоимости перевозок в данном случае неединственное.

Метод потенциалов

(начальное распределение рассчитано по методу «северо-западного угла»)

Каждому поставщику ставим в соответствие некоторое число , называемое потенциалом поставщика.

Каждому потребителю ставим в соответствие некоторое число , называемое потенциалом потребителя.

Возьмем первоначальный план (табл. 7), полученный по методу «северо-западного угла».

Таблица 15.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 20	3 20	6	8	7	u₁=
А₂	5	9 6	5 16	7 13	2	u₂=
А₃	1	4	3	7 25	3 20	u₃=
V	v₁=	v₂=	v₃=	v₄=	v₅=

Для каждой заполненной клетки, т. е. для каждой базисной переменной, строится соотношение:

Получаем систему с числом уравнений, равным количеству базисных переменных. Из этой системы определяем неизвестные потенциалы и , полагая одно из .

В нашем случае система уравнений и ее решение при взятом значении выглядит так:

A₂B₂ :	v₂ + u₂ = 9	v₂ = 9 - 0 = 9
A₂B₃ :	v₃ + u₂ = 5	v₃ = 5 - 0 = 5
A₂B₄ :	v₄ + u₂ = 7	v₄ = 7 - 0 = 7
A₃B₄ :	v₄ + u₃ = 7	u₃ = 7 - 7 = 0
A₃B₅ :	v₅ + u₃ = 3	v₅ = 3 - 0 = 3
A₁B₂ :	v₂ + u₁ = 3	u₁ = 3 - 9 = -6
A₁B₁ :	v₁ + u₁ = 2	v₁ = 2 - (-6) = 8

Записав эти значения в таблицу, получим:

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 20	3 20	6	8	7	u₁=-6
А₂	5	9 6	5 16	7 13	2	u₂=0
А₃	1	4	3	7 25	3 20	u₃=0
V	v₁=8	v₂=9	v₃=5	v₄=7	v₅=3

Вычислим разности для свободных клеток.

План перевозок будет являться оптимальным, если все являются неотрицательными.

A₁B₃ :	Δ₁₃ = c₁₃ - ( u₁ + v₃ ) = 6 - ( -6 + 5 ) = 7
A₁B₄ :	Δ₁₄ = c₁₄ - ( u₁ + v₄ ) = 8 - ( -6 + 7 ) = 7
A₁B₅ :	Δ₁₅ = c₁₅ - ( u₁ + v₅ ) = 7 - ( -6 + 3 ) = 10
A₂B₁ :	Δ₂₁ = c₂₁ - ( u₂ + v₁ ) = 5 - ( 0 + 8 ) = -3
A₂B₅ :	Δ₂₅ = c₂₅ - ( u₂ + v₅ ) = 2 - ( 0 + 3 ) = -1
A₃B₁ :	Δ₃₁ = c₃₁ - ( u₃ + v₁ ) = 1 - ( 0 + 8 ) = -7
A₃B₂ :	Δ₃₂ = c₃₂ - ( u₃ + v₂ ) = 4 - ( 0 + 9 ) = -5
A₃B₃ :	Δ₃₃ = c₃₃ - ( u₃ + v₃ ) = 3 - ( 0 + 5 ) = -2

Есть отрицательные значения. Значит план не является оптимальным.

ШАГ 1.

Выбираем клетку с максимальным отрицательным значением. Это клетка A₃B_1.

Строим цикл, т. е. замкнутый многоугольник, соединяющий выбранную клетку с ней же самой и проходящий через заполненные клетки.

Ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной клетки. Он единственный. Направление обхода не имеет значения.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 20 ⊖	3 20 ⊕	6	8	7	u₁=-6
А₂	5	9 6 ⊖	5 16	7 13 ⊕	2	u₂=0
А₃	1 ⊕	4	3	7 25 ⊖	3 20	u₃=0
V	v₁=8	v₂=9	v₃=5	v₄=7	v₅=3

В каждую клетку цикла поочередно вписывают знаки “+” и “–“. Из всех клеток с отрицательными знаками (в данном случае из А3,В4; А2,В2; А1,В1) выбирается минимальная величина поставки, обозначаемая как D.

В те вершины, которые имеют знак “+” прибавляется поставка D, а в вершинах со знаком “–“ поставки уменьшаются на величину D.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 20-6 ⊖	3 20+6 ⊕	6	8	7	u₁=-6
А₂	5	9 6-6 ⊖	5 16	7 13+6 ⊕	2	u₂=0
А₃	1 +6 ⊕	4	3	7 25-6 ⊖	3 20	u₃=0
V	v₁=8	v₂=9	v₃=5	v₄=7	v₅=3

При этом суммы поставок по строкам и столбцам не изменяются. В результате клетка, для которой строился цикл, станет занятой, а в одной из бывших занятых клеток окажется нулевая поставка и её надо объявить свободной. Общее количество заполненных клеток не изменится, следовательно, новый план перевозок является невырожденным.

Получили новое решение

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 14	3 26	6	8	7	40
А₂	5	9	5 16	7 19	2	35
А₃	1 6	4	3	7 19	3 20	45
Потребность	20	26	16	38	20

Стоимость перевозки по этому плану:

z=14*2 + 26*3 + 16*5 + 19*7 +6*1+ 19*7 + 20*3 = 518 (т.е. меньше, чем было 560)

(или z= 560 + Δ₃₁ * 6 = 560 -7 * 6 = 518)

Проверим, является ли полученное решение оптимальным.

Последовательно найдем значения потенциалов.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 14	3 26	6	8	7	u₁=
А₂	5	9	5 16	7 19	2	u₂=
А₃	1 6	4	3	7 19	3 20	u₃=
V	v₁=	v₂=	v₃=	v₄=	v₅=

Значение одного потенциала необходимо задать. Пусть u₃ = 0.

A₃B₁ :	v₁ + u₃ = 1	v₁ = 1 - 0 = 1
A₃B₄ :	v₄ + u₃ = 7	v₄ = 7 - 0 = 7
A₃B₅ :	v₅ + u₃ = 3	v₅ = 3 - 0 = 3
A₁B₁ :	v₁ + u₁ = 2	u₁ = 2 - 1 = 1
A₁B₂ :	v₂ + u₁ = 3	v₂ = 3 - 1 = 2
A₂B₄ :	v₄ + u₂ = 7	u₂ = 7 - 7 = 0
A₂B₃ :	v₃ + u₂ = 5	v₃ = 5 - 0 = 5

Записав эти значения в таблицу, получим:

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 14	3 26	6	8	7	u₁=1
А₂	5	9	5 16	7 19	2	u₂=0
А₃	1 6	4	3	7 19	3 20	u₃=0
V	v₁=1	v₂=2	v₃=5	v₄=7	v₅=3

Вычислим разности для свободных клеток.

A₁B₃ :	Δ₁₃ = c₁₃ - ( u₁ + v₃ ) = 6 - ( 1 + 5 ) = 0
A₁B₄ :	Δ₁₄ = c₁₄ - ( u₁ + v₄ ) = 8 - ( 1 + 7 ) = 0
A₁B₅ :	Δ₁₅ = c₁₅ - ( u₁ + v₅ ) = 7 - ( 1 + 3 ) = 3
A₂B₁ :	Δ₂₁ = c₂₁ - ( u₂ + v₁ ) = 5 - ( 0 + 1 ) = 4
A₂B₂ :	Δ₂₂ = c₂₂ - ( u₂ + v₂ ) = 9 - ( 0 + 2 ) = 7
A₂B₅ :	Δ₂₅ = c₂₅ - ( u₂ + v₅ ) = 2 - ( 0 + 3 ) = -1
A₃B₂ :	Δ₃₂ = c₃₂ - ( u₃ + v₂ ) = 4 - ( 0 + 2 ) = 2
A₃B₃ :	Δ₃₃ = c₃₃ - ( u₃ + v₃ ) = 3 - ( 0 + 5 ) = -2

Есть отрицательные оценки. Значит план не является оптимальным.

ШАГ 2.

Выбираем клетку с максимальным отрицательным значением. Это клетка A₃B_3.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 14	3 26	6	8	7	u₁=
А₂	5	9	5 16 -16⊖	7 19+16⊕	2	u₂=
А₃	1 6	4	3 +16 ⊕	7 19-16 ⊖	3 20	u₃=
V	v₁=	v₂=	v₃=	v₄=	v₅=

Из всех клеток с отрицательными знаками (в данном случае из А2,В3; А3,В4) выбирается минимальная величина поставки, обозначаемая как D.

Получили новое решение.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 14	3 26	6	8	7	40
А₂	5	9	5	7 35	2	35
А₃	1 6	4	3 16	7 3	3 20	45
Потребность	20	26	16	38	20

Стоимость перевозки по этому плану:

z=14*2 + 26*3 + 35*7 +6*1+16*3 + 3*7 + 20*3 = 486

(или z= 518 + Δ₃₃ * 16 = 518 -2 * 16 = 486)

Проверим, является ли полученное решение оптимальным.

Последовательно найдем значения потенциалов.

Значение одного потенциала необходимо задать. Пусть u₃ = 0

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 14	3 26	6	8	7	u₁=
А₂	5	9	5	7 35	2	u₂=
А₃	1 6	4	3 16	7 3	3 20	u₃=
V	v₁=	v₂=	v₃=	v₄=	v₅=

A₃B₁ :	v₁ + u₃ = 1	v₁ = 1 - 0 = 1
A₃B₃ :	v₃ + u₃ = 3	v₃ = 3 - 0 = 3
A₃B₄ :	v₄ + u₃ = 7	v₄ = 7 - 0 = 7
A₃B₅ :	v₅ + u₃ = 3	v₅ = 3 - 0 = 3
A₁B₁ :	v₁ + u₁ = 2	u₁ = 2 - 1 = 1
A₁B₂ :	v₂ + u₁ = 3	v₂ = 3 - 1 = 2
A₂B₄ :	v₄ + u₂ = 7	u₂ = 7 - 7 = 0

Записав эти значения в таблицу, получим:

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 14	3 26	6	8	7	u₁=1
А₂	5	9	5	7 35	2	u₂=0
А₃	1 6	4	3 16	7 3	3 20	u₃=0
V	v₁=1	v₂=2	v₃=3	v₄=7	v₅=3

Вычислим разности для свободных клеток.

A₁B₃ :	Δ₁₃ = c₁₃ - ( u₁ + v₃ ) = 6 - ( 1 + 3 ) = 2
A₁B₄ :	Δ₁₄ = c₁₄ - ( u₁ + v₄ ) = 8 - ( 1 + 7 ) = 0
A₁B₅ :	Δ₁₅ = c₁₅ - ( u₁ + v₅ ) = 7 - ( 1 + 3 ) = 3
A₂B₁ :	Δ₂₁ = c₂₁ - ( u₂ + v₁ ) = 5 - ( 0 + 1 ) = 4
A₂B₂ :	Δ₂₂ = c₂₂ - ( u₂ + v₂ ) = 9 - ( 0 + 2 ) = 7
A₂B₃ :	Δ₂₃ = c₂₃ - ( u₂ + v₃ ) = 5 - ( 0 + 3 ) = 2
A₂B₅ :	Δ₂₅ = c₂₅ - ( u₂ + v₅ ) = 2 - ( 0 + 3 ) = -1
A₃B₂ :	Δ₃₂ = c₃₂ - ( u₃ + v₂ ) = 4 - ( 0 + 2 ) = 2

Есть отрицательные оценки. Значит план не является оптимальным.

ШАГ 3.

Выбираем клетку с максимальным отрицательным значением. Это клетка A₂B_5.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 14	3 26	6	8	7	40
А₂	5	9	5	7 35-20⊖	2 +20 ⊕	35
А₃	1 6	4	3 16	7 3+20 ⊕	3 20-20 ⊖	45
Потребность	20	26	16	38	20

Из всех клеток с отрицательными знаками (в данном случае из А2,В4; А3,В5) выбирается минимальная величина поставки, обозначаемая как D.

Получили новое решение.

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 14	3 26	6	8	7	40
А₂	5	9	5	7 15	2 20	35
А₃	1 6	4	3 16	7 23	3	45
Потребность	20	26	16	38	20

Стоимость перевозки по этому плану:

z=14*2 + 26*3 + 15*7 +20*2+6*1+16*3 + 23*7 = 466

(или z= 486 + Δ₂₅ * 20 = 486 -1 * 20 = 466)

Проверим, является ли полученное решение оптимальным.

Последовательно найдем значения потенциалов.

Значение одного потенциала необходимо задать. Пусть u₃ = 0

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 14	3 26	6	8	7	u₁=
А₂	5	9	5	7 15	2 20	u₂=
А₃	1 6	4	3 16	7 23	3	u₃=
V	v₁=	v₂=	v₃=	v₄=	v₅=

A₃B₁ :	v₁ + u₃ = 1	v₁ = 1 - 0 = 1
A₃B₃ :	v₃ + u₃ = 3	v₃ = 3 - 0 = 3
A₃B₄ :	v₄ + u₃ = 7	v₄ = 7 - 0 = 7
A₁B₁ :	v₁ + u₁ = 2	u₁ = 2 - 1 = 1
A₁B₂ :	v₂ + u₁ = 3	v₂ = 3 - 1 = 2
A₂B₄ :	v₄ + u₂ = 7	u₂ = 7 - 7 = 0
A₂B₅ :	v₅ + u₂ = 2	v₅ = 2 - 0 = 2

Записав эти значения в таблицу, получим:

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 14	3 26	6	8	7	u₁=1
А₂	5	9	5	7 15	2 20	u₂=0
А₃	1 6	4	3 16	7 23	3	u₃=0
V	v₁=1	v₂=2	v₃=3	v₄=7	v₅=2

Вычислим разности для свободных клеток.

A₁B₃ :	Δ₁₃ = c₁₃ - ( u₁ + v₃ ) = 6 - ( 1 + 3 ) = 2
A₁B₄ :	Δ₁₄ = c₁₄ - ( u₁ + v₄ ) = 8 - ( 1 + 7 ) = 0
A₁B₅ :	Δ₁₅ = c₁₅ - ( u₁ + v₅ ) = 7 - ( 1 + 2 ) = 4
A₂B₁ :	Δ₂₁ = c₂₁ - ( u₂ + v₁ ) = 5 - ( 0 + 1 ) = 4
A₂B₂ :	Δ₂₂ = c₂₂ - ( u₂ + v₂ ) = 9 - ( 0 + 2 ) = 7
A₂B₃ :	Δ₂₃ = c₂₃ - ( u₂ + v₃ ) = 5 - ( 0 + 3 ) = 2
A₃B₂ :	Δ₃₂ = c₃₂ - ( u₃ + v₂ ) = 4 - ( 0 + 2 ) = 2
A₃B₅ :	Δ₃₅ = c₃₅ - ( u₃ + v₅ ) = 3 - ( 0 + 2 ) = 1

Нет отрицательных оценок. Следовательно, уменьшить общую стоимость доставки продукции невозможно и этот план является оптимальным.

Ответ:

Поставщик	Потребитель					Запас
Поставщик	B₁	B₂	B₃	B₄	B₅
А₁	2 14	3 26	6	8	7	40
А₂	5	9	5	7 15	2 20	35
А₃	1 6	4	3 16	7 23	3	45
Потребность	20	26	16	38	20

Стоимость перевозки по этому плану:

z=14*2 + 26*3 + 15*7 +20*2+6*1+16*3 + 23*7 = 466

Дата добавления: 2020-12-22; просмотров: 69; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!