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

Страницы работы

19 страниц (Word-файл)

Фрагмент текста работы

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

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

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

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

Решение :

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

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

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

1)

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

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

A 1

-

-

-

-

10 

-

12 

50

A 2

-

-

-

-

-

60

A 3

-

-

-

-

-

40

Потребность

30

20

55

20

25

2)

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

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

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

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

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

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

A 1

30

-

-

-

10 

-

12 

50

A 2

-

-

-

-

-

60

A 3

-

-

-

-

-

40

Потребность

30

20

55

20

25

3)

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

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

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

Разместим в ячейку A1B2 значение равное 20

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

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

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

A 1

30

20

-

-

10 

-

12 

50

A 2

-

-

-

-

-

60

A 3

-

-

-

-

-

40

Потребность

30

20

55

20

25

4)

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

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

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

Разместим в ячейку A2B3 значение равное 55

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

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

A 1

30

20

-

-

10 

-

12 

50

A 2

-

-

55

-

-

60

A 3

-

-

-

-

-

40

Потребность

30

20

55

20

25

5)

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

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

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

Разместим в ячейку A2B4 значение равное 5

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

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

A 1

30

20

-

-

10 

-

12 

50

A 2

-

-

55

5

-

60

A 3

-

-

-

-

-

40

Потребность

30

20

55

20

25

6)

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

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

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

Разместим в ячейку A3B4 значение равное 15

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

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

A 1

30

20

-

-

10 

-

12 

50

A 2

-

-

55

5

-

60

A 3

-

-

-

15

-

40

Потребность

30

20

55

20

25

7)

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

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

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

Разместим в ячейку A3B5 значение равное 25

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

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

A 1

30

20

-

-

10 

-

12 

50

A 2

-

-

55

5

-

60

A 3

-

-

-

15

25

40

Потребность

30

20

55

20

25

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

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

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

8)

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

Похожие материалы

Информация о работе