Методом наименьшей стоимости

Метод наименьшей стоимости осуществляет распределение продукта, имеющегося у поставщиков, между потребителями с учетом удельной стоимости перевозок с_ij. Поэтому данный метод позволяет получить Т-план, отвечающий как правило меньшим суммарным затратам, чем метод северо-западного угла.

Содержание метода:

1). Построим таблицу перевозок (Таблица 1).

2). Приведем задачу к сбалансированному виду, если это необходимо.

3). Выделим клетку таблицы с наименьшей удельной стоимостью перевозки груза. Пусть это будет клетка с адресом (l,k). Присвоим выбранной клетке объем поставки x_l_,_k, равный минимальному из значений а_l (объем продукта, имеющийся у l -го производителя) и b _k (объем продукта, необходимый k -му потребителю): x_l_,_k=min { а_l, b _k }.

4). Рассмотрим случай, когда а_l > b _k _. Эта ситуация означает то, что запросы k-го потребителя полностью удовлетворены, а объем продукта, имеющийся у l -го производителя уменьшились на величину равную x_l_,_k. Следовательно необходимо вычеркнуть из таблицы k- й столбец и значение а_l уменьшить на b _k.

В случае а_l < b _k предполагается, что запас продукта l -го производителя исчерпан, а k-у потребителю необходимо доставить еще (b _k - а_l) объема продукта. Следовательно необходимо вычеркнуть из таблицы строку с номером l, а значение b _k уменьшить на а_l.

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

Замечание 5: если на очередном шаге метода отыщется несколько клеток с наименьшей удельной стоимостью перевозок, то предпочтение отдается:

во-первых клетке, соответствующей не фиктивному потребителю (поставщику);

во-вторых той клетке, где объем перевозок может быть наибольшим.

Проиллюстрируем применение метода наименьшей стоимости для построения первоначального Т-плана на примере ЗАДАЧИ (*).

1). Используем уже построенную таблицу исходных данных (Таблица 4). При рассмотрении предыдущего метода было доказано, что задача является сбалансированной.

2).Начнем построение первоначального Т-плана с нахождения клетки с минимальной удельной стоимостью. Это клетка (2;1). Поставим в соответствие ей величину поставки равную х₂₁ = min {а₂, b₁}= min {130, 150}=130. Следовательно, мы вывезли со склада В весь имеющийся груз, т.е. а₂=0. Вычеркнем вторую строку таблицы. В пункт а необходимо доставить еще b₁=150-130 = 20 усл.ед. груза (Отразим изменения в таблице 11).

- Следующая клетка с минимальной удельной стоимостью – (1;1). Впишем в нее величину поставки равную х₁₁ = min {а₁,b₁}= min {100,20}=20. Все потребности пункта а удовлетворены, поэтому вычеркнем 1-й столбец таблицы. Запасы груза на складе А уменьшились на 20 усл.ед., т.е. а₁=100-20=80 усл.ед. (Внесем изменения в таблицу 12).

Таблица 11 Таблица 12

(150)

(100)

(130)

- Выделим клетку (1,2), так как ей соответствует наименьшая удельная стоимость из числа оставшихся. Внесем в нее объем поставки х₁₂ = min {а₁,b₂}= min {80,120}=80. Таким образом, со склада А вывезли весь груз (1-ю строку вычеркиваем), а потребности 2-го потребителя сократились на 80 усл.ед. Внесем изменения в таблицу 13.

- На данном этапе наименьшая удельная стоимость соответствует клетке (3,4). Следовательно х₃₄ = min {а₃,b₄}= min {170,50}=50. Это означает, что запросы пункта д удовлетворены полностью (столбец №4 вычеркиваем), а запасы груза на складе С уменьшились на 50 усл.ед. (Табл.14).

- Выделим клетку (3;2) с наименьшей из числа оставшихся удельной стоимостью и х₃₂ = min {а₃,b₂}= min {120,40}=40. Потребности пункта б удовлетворены полностью – вычеркиваем 2-й столбец таблицы. Объем груза на складе С уменьшается на 40 усл.ед., т.е. b₂= 120-40=80 (Табл.14).

- Осталась одна свободная клетка (3;3) - выделим ее. Впишем в нее величину поставки х₃₃ = min {а₃,b₃}= min {80,80}=80. Получили: со склада С вывезли весь оставшийся груз, и потребности пункта с полностью выполнены (Табл. 15).

Таблица 13 Таблица 14

(150)

(120)

(150)

(120)

(50)

(100)

(130)

(170)

Таблица 14 Таблица 15

(150)

(120)

(50)

(150)

(120)

(80)

(50)

(100)

(130)

(170)

Построенный первоначальный план перевозок проверим на возможные ошибки:

1 строка: 100=20+80; 2 строка: 130=130; 3 строка: 170= 40+80+50.

1 столбец: 150=20+130; 2 столбец: 120=80+40; 3 столбец: 80=80; 4 столбец: 50=50.

Таким образом проверка показала, что первоначальный план перевозок построен верно. Дадим экономическую интерпретацию полученных результатов:

1). В пункт а перевезли 20 и 130 усл.ед груза со складов А и В соответственно; в пункт б – 80 и 40 усл.ед. груза со складов А и С соотв.; в пункт с – 80 усл.ед груза со склада С и в пункт д – 50 усл.ед груза со склада С.