1.2.3 Построение опорного плана методом Фогеля

Согласно условию задачи построим опорный план методом Фогеля.

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

Из полученных разностей выберем наибольшую.

Наибольшей разностью обладает столбец 3. В данном столбце выберем ячейку A2B3, как обладающую наименьшим тарифом.

Стоимость доставки единицы продукции от поставщика A2 к потребителю B3, как минимум, на 2 ден.ед. меньше чем от остальных поставщиков к потребителю B3.

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

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

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

Наибольшей разностью обладает столбец 3. В данном столбце выберем ячейку A4B3, как обладающую наименьшим тарифом.

Стоимость доставки единицы продукции от поставщика A4 к потребителю B3, как минимум, на 5 ден.ед. меньше чем от остальных поставщиков к потребителю B3 (см. правую таблицу).

Запасы поставщика A4 составляют 70 единиц продукции. Потребность потребителя B3 составляет 30 единиц продукции.

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

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

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

Наибольшей разностью обладает строка 3. В данной строке выберем ячейку A3B2, как обладающую наименьшим тарифом.

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

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

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

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

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

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

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

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

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

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

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

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

S0 = 1 * 120 + 1 * 110 + 4 * 20 + 2 * 40 + 3 * 30 + 0 * 65 + 0 * 115 = 480 ден. ед.

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

По результатам построения опорных планов минимальное значение затрат было получено при построении опорного плана методом наименьшей стоимости и составили 450 ден.ед.

Перейдем к перепланировке перевозок методом потенциалов.