Метод северо-западного угла. Оптимальное решение доставки продукции от поставщиков к потребителям, минимизирующие стоимость доставки

Стоимость доставки единицы продукции от поставщика A₁ к указанным потребителям равна 7 , 6 , 8 , 10 , 12 ден.ед.

Стоимость доставки единицы продукции от поставщика A₂ к указанным потребителям равна 9 , 5 , 7 , 4 , 6 ден.ед.

Стоимость доставки единицы продукции от поставщика A₃ к указанным потребителям равна 6 , 8 , 4 , 9 , 7 ден.ед.

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

Решение :

Что мы будем делать? Найдем начальное решение методом северо-западного угла. Если начальное решение окажется оптимальным, то задача решена. Если начальное решение окажется не оптимальным, используя метод потенциалов, будем последовательно получать решение за решением, причем каждое следующее, как минимум, не хуже предыдущего. И так, до тех пор, пока не получим оптимальное решение.

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

В нашем случае, потребность всех потребителей - 150 единиц продукции равна запасам всех поставщиков .

1)

Согласно условию задачи составим таблицу. (тарифы c_ij располагаются в нижнем правом углу ячейки)

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

50

A ₂

60

A ₃

40

Потребность

30

20

55

20

25

2)

Рассмотрим маршрут доставки от поставщика A₁ к потребителю B₁ (ячейка A₁B₁).

Запасы поставщика A₁ составляют 50 единиц продукции. Потребность потребителя B₁ составляет 30 единиц продукции. (см. таблицу пункта 1)

От поставщика A₁ к потребителю B₁ будем доставлять min = { 50 , 30 } = 30 единиц продукции.

Разместим в ячейку A₁B₁ значение равное 30

Мы полностью удовлетворили потребность потребителя B₁. Вычеркиваем столбец 1 таблицы, т.е исключаем его из дальнейшего рассмотрения.

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

50

A ₂

60

A ₃

40

Потребность

30

20

55

20

25

3)

Рассмотрим маршрут доставки от поставщика A₁ к потребителю B₂ (ячейка A₁B₂).

Запасы поставщика A₁ составляют 20 единиц продукции. Потребность потребителя B₂ составляет 20 единиц продукции. (см. таблицу пункта 2)

От поставщика A₁ к потребителю B₂ будем доставлять 20 единиц продукции.

Разместим в ячейку A₁B₂ значение равное 20

Мы полностью израсходoвали запасы поставщика A₁. Вычеркиваем строку 1 таблицы, т.е исключаем ее из дальнейшего рассмотрения.

Мы полностью удовлетворили потребность потребителя B₂. Вычеркиваем столбец 2 таблицы, т.е исключаем его из дальнейшего рассмотрения.

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

50

A ₂

60

A ₃

40

Потребность

30

20

55

20

25

4)

Рассмотрим маршрут доставки от поставщика A₂ к потребителю B₃ (ячейка A₂B₃).

Запасы поставщика A₂ составляют 60 единиц продукции. Потребность потребителя B₃ составляет 55 единиц продукции. (см. таблицу пункта 3)

От поставщика A₂ к потребителю B₃ будем доставлять min = { 60 , 55 } = 55 единиц продукции.

Разместим в ячейку A₂B₃ значение равное 55

Мы полностью удовлетворили потребность потребителя B₃. Вычеркиваем столбец 3 таблицы, т.е исключаем его из дальнейшего рассмотрения.

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

50

A ₂

60

A ₃

40

Потребность

30

20

55

20

25

5)

Рассмотрим маршрут доставки от поставщика A₂ к потребителю B₄ (ячейка A₂B₄).

Запасы поставщика A₂ составляют 5 единиц продукции. Потребность потребителя B₄ составляет 20 единиц продукции. (см. таблицу пункта 4)

От поставщика A₂ к потребителю B₄ будем доставлять min = { 5 , 20 } = 5 единиц продукции.

Разместим в ячейку A₂B₄ значение равное 5

Мы полностью израсходoвали запасы поставщика A₂. Вычеркиваем строку 2 таблицы, т.е исключаем ее из дальнейшего рассмотрения.

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

50

A ₂

60

A ₃

40

Потребность

30

20

55

20

25

6)

Рассмотрим маршрут доставки от поставщика A₃ к потребителю B₄ (ячейка A₃B₄).

Запасы поставщика A₃ составляют 40 единиц продукции. Потребность потребителя B₄ составляет 15 единиц продукции. (см. таблицу пункта 5)

От поставщика A₃ к потребителю B₄ будем доставлять min = { 40 , 15 } = 15 единиц продукции.

Разместим в ячейку A₃B₄ значение равное 15

Мы полностью удовлетворили потребность потребителя B₄. Вычеркиваем столбец 4 таблицы, т.е исключаем его из дальнейшего рассмотрения.

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

50

A ₂

60

A ₃

40

Потребность

30

20

55

20

25

7)

Рассмотрим маршрут доставки от поставщика A₃ к потребителю B₅ (ячейка A₃B₅).

Запасы поставщика A₃ составляют 25 единиц продукции. Потребность потребителя B₅ составляет 25 единиц продукции. (см. таблицу пункта 6)

От поставщика A₃ к потребителю B₅ будем доставлять 25 единиц продукции.

Разместим в ячейку A₃B₅ значение равное 25

Мы полностью израсходoвали запасы поставщика A₃. Вычеркиваем строку 3 таблицы, т.е исключаем ее из дальнейшего рассмотрения.

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

50

A ₂

60

A ₃

40

Потребность

30

20

55

20

25

Заполненные нами ячейки будем называть базисными, остальные - свободными.

Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.

Количество базисных ячеек равно 6. Требуется, чтобы было 7.

8)

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