Первоначальное распределение поставок методом наименьших затрат

Пример 13. Пусть необходимо организовать перевозку продукции от нескольких поставщиков, например, молока с 3 ферм некоторому количеству потребителей, например, на 3 молокозавода (МЗ). Условия и решение транспортной задачи принято записывать в табличной форме:

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

Определим тип задачи. Суммарная мощность поставщиков равна 300. Суммарная мощность потребителей равна 300. Т.е. задача является закрытой.

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

Находим клетку (маршрут) с минимальной удельной стоимостью.

Если таких клеток несколько, можно начать с любой из них. Минимальная стоимость c₂₁=3. По маршруту 2 – 1 (с фермы 2 на завод 1) можно перевезти 75 единиц продукции. Ставим в нижний правый угол клетки 75 и перечеркиваем клетку сплошной линией. Клетка называется заполненной. При этом на ферме 2 нет остатка продукции, поэтому остальные клетки строки перечеркиваем пунктирной диагональной линией («вычеркиваем строку»). На завод 1 остается привезти 90 – 75 = 15 ед.продукции.

В незачеркнутых клетках таблицы находим клетку с минимальной удельной стоимостью: c₁₃=4. По соответствующему маршруту 1 – 3 можно перевезти 100 единиц продукции. Ставим в нижний правый угол клетки 100 и перечеркиваем клетку. При этом на ферме 2 нет остатка продукции, поэтому остальные клетки строки перечеркиваем пунктирной линией. На завод 3 остается привезти 130 – 100 = 30 ед.продукции.

В незачеркнутых клетках таблицы находим клетку с минимальной удельной стоимостью: c₃₃=4. По соответствующему маршруту 3 – 3 можно перевезти 30 единиц продукции, при этом запросы завода 3 будут удовлетворены полностью. На ферме 3 остатки продукции составят 95 ед. Ставим в нижний правый угол клетки 30 и перечеркиваем клетку.

В незачеркнутых клетках таблицы находим клетку с минимальной удельной стоимостью: c₃₁=5. По соответствующему маршруту 3 – 1 можно перевезти 15 единиц продукции, при этом запросы завода 1 будут удовлетворены полностью. На ферме 3 остатки продукции составят 80 ед. Ставим в нижний правый угол клетки 15 и перечеркиваем клетку.

Последняя свободная клетка соответствует перевозке продукции с фермы 3 на завод 2. Поставка 80 ед. продукции по этому маршруту удовлетворяет полностью запросы завода 2 и исчерпывает запасы фермы 3.

Ставим в эту клетку 80 и перечеркиваем её.

Таблица первоначального распределения поставок заполнена. Вычислим суммарные затраты на перевозку по всем маршрутам:

F=4*100+3*75+5*15+6*80+4*30=1300.

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

Данный метод заполнения основан на последовательном заполнении свободных клеток, начиная с верхней левой клетки («северо-западный угол»). При последовательном вычеркивании строк и столбцов каждый раз происходит заполнение верхней левой клетки незаполненной (незачеркнутой) области. Рассмотрим пример заполнения для предыдущей задачи. Начальные условия заданы в табличной форме.

Верхняя левая клетка соответствует маршруту с фермы 1 на завод 1 и по этому маршруту можно перевезти 90 ед.продукции. Ставим в нижний правый угол клетки 90, перечеркиваем клетку. Запросы завода 1 удовлетворены полностью, поэтому остальные клетки столбца перечеркиваем пунктирной линией. На ферме 1 остается 100 – 90 = 10 ед.продукции.

Верхняя левая клетка незаполненной области соответствует маршруту 1 – 2, по этому маршруту можно перевезти 10 ед.продукции. Ставим в нижний правый угол клетки 10, перечеркиваем клетку. При этом на ферме 1 нет остатка продукции, поэтому остальные клетки строки перечеркиваем пунктирной линией. На завод 2 остается привезти 70 ед.продукции.

Верхняя левая клетка незаполненной области соответствует маршруту 2 – 2, по этому маршруту можно перевезти 70 ед.продукции. Ставим в нижний правый угол клетки 70 и перечеркиваем клетку. При этом запросы завода 2 удовлетворены полностью, поэтому остальные клетки столбца перечеркиваем пунктирной линией. На ферме 2 остается 5 ед.продукции.

Верхняя левая клетка незаполненной области соответствует маршруту 2 – 3, по этому маршруту можно перевезти 5 ед.продукции. Ставим в нижний правый угол клетки 5 и перечеркиваем клетку. При этом на ферме 2 нет остатка продукции. На завод 3 остается привезти 125 ед.продукции.

Заполняем последнюю свободную клетку таблицы. Поставка 125 ед. продукции удовлетворяет полностью запросы завода 3 и исчерпывает запасы фермы 3. Ставим в эту клетку 125 и перечеркиваем её.

Таблица первоначального распределения поставок заполнена. Вычислим суммарные затраты на поставку по всем маршрутам:

F=6*90+5*10+7*70+5*5+4*125=1605.

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