1.2.1 Построение опорного плана методом северо-западного угла

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

В нашем случае, запасы поставщиков - 320 единиц продукции меньше, чем потребность потребителей - 500 на 180 единиц. Введем в рассмотрение фиктивного поставщика A5, с запасом продукции равным 180. Стоимость доставки единицы продукции от данного поставщика ко всем потребителям примем равной нулю.

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

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

Запасы поставщика A1 составляют 120 единиц продукции. Потребность потребителя B1 составляет 225 единиц продукции.

От поставщика A1 к потребителю B1 будем доставлять min = (120 , 225) = 120 единиц продукции.

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

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

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

Запасы поставщика A2 составляют 110 единиц продукции. Потребность потребителя B1 составляет 105 единиц продукции.

От поставщика A2 к потребителю B1 будем доставлять min = (110 , 105) = 105 единиц продукции.

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

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

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

Запасы поставщика A2 составляют 5 единиц продукции. Потребность потребителя B2 составляет 135 единиц продукции.

От поставщика A2 к потребителю B2 будем доставлять min = ( 5 , 135 ) = 5 единиц продукции.

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

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

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

Запасы поставщика A3 составляют 20 единиц продукции. Потребность потребителя B2 составляет 130 единиц продукции.

От поставщика A3 к потребителю B2 будем доставлять min = (20 , 130) = 20 единиц продукции.

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

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

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

Запасы поставщика A4 составляют 70 единиц продукции. Потребность потребителя B2 составляет 110 единиц продукции. От поставщика A4 к потребителю B2 будем доставлять min = ( 70 , 110) = 70 единиц продукции.

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

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

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

Запасы поставщика A5 составляют 180 единиц продукции. Потребность потребителя B2 составляет 40 единиц продукции. От поставщика A5 к потребителю B2 будем доставлять min = ( 180 , 40 ) = 40 единиц продукции.

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

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

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

Запасы поставщика A5 составляют 140 единиц продукции. Потребность потребителя B3 составляет 140 единиц продукции. От поставщика A5 к потребителю B3 будем доставлять 140 единиц продукции.

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

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

В результате решения получим следующую таблицу.

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

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

Количество базисных ячеек (задействованных маршрутов) равно 7, что и требовалось.

Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

S0 = 1 * 120 + 3 * 105 + 4 * 5 + 4 * 20 + 3 * 70 + 0 * 40 + 0 * 140 = 745 ден. ед.

Общие затраты на доставку всей продукции, для начального решения , составляют 745 ден. ед..

Дальнейшие наши действия будут состоять из шагов, каждый из которых состоит в следующем:

* Находим потенциалы поставщиков и потребителей для имеющегося решения.

* Находим оценки свободных ячеек. Если все оценки окажутся неотрицательными - задача решена.

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

* Находим новое решение, как минимум, не хуже предыдущего.

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