Метод минимальной стоимости, — еще один метод построения первоначального плана поставок. Он состоит в следующем. На каждом шаге мы будем делать поставку в клетку с наименьшей стоимостью перевозки единицы груза среди всех незаполненных клеток.
Таблица 11
В1=135 | |||||
В2=145 | |||||
В3=250 | |||||
В4=310 | |||||
А1=125 | А2=130 | А3=55 | А4=95 | А5=435 | å=840 |
Шаг 1. Среди всех незаполненных клеток у клеток (1,2) и (4,5) наименьшая стоимость перевозки единицы груза — 1. Поэтому делаем поставку в одну из этих клеток. Находим минимумы в этих клетках:
min (130, 135) = 130, min (435, 310) = 310.
Сначала делаем поставки в клетку (4,5), т.к. в этой клетке наибольшая поставка 310 > 130 (находим максимум max (130, 310) = 310). Исключаем 4-ю строку. Делаем поставки в клетку (1,2) и исключаем 2-й столбец. В этих клетках спрос полностью удовлетворен.
После этого наша таблица примет следующий вид:
Таблица 12.
4 | |||||
3 | |||||
Второй столбец и 4-я строка в дальнейшем не рассматриваются.
|
|
Шаг 2. Среди всех незаполненных клеток у клетки (3,1) наименьшая стоимость перевозки единицы груза — 2. Поэтому делаем поставку в эту клетку. min (125, 250) = 125. Исключаем 1-й столбец.
После второго шага наша таблица примет следующий вид:
Таблица 13.
5 | 1 | ||||
4 | |||||
125 | 3 | ||||
Первый и второй столбец, 4-я строка в дальнейшем не рассматриваются.
Шаг 3. Среди всех незаполненных клеток у клетки (1,3) наименьшая стоимость перевозки единицы груза - 3. Поэтому делаем поставку в эту клетку. min (55, 135-130) = 5. Исключаем 2-ю строку.
После третьего шага наша таблица примет следующий вид:
Таблица 14.
5 | 1 | ||||
4 | |||||
125 | 3 | ||||
Первая строка, 4-я строка, 1-й столбец и 2-й столбец в дальнейшем не рассматриваются.
Шаг 4. Среди всех незаполненных клеток у клетки (3,3) наименьшая стоимость перевозки единицы груза — 4. Поэтому делаем поставку в эту клетку. min (55-5, 250-125) = 50. Исключаем 3-й столбец.
После четвертого шага наша таблица примет следующий вид:
Таблица 15.
5 | 1 130 | ||||
4 | |||||
125 | 3 | 50 | |||
Первая строка, 4-я строка, 1-й столбец, 2-й столбец и 3-й столбец в дальнейшем не рассматриваются.
Шаг 5. Среди всех незаполненных клеток у клетки (3,4) наименьшая стоимость перевозки единицы груза — 5. Поэтому делаем поставку в эту клетку. min (95, 250-125-50) = 75. Исключаем 3-ю строку.
|
|
После пятого шага наша таблица примет следующий вид:
Таблица 16.
5 | 1 130 | ||||
4 | |||||
125 | 3 | 50 | |||
Первая строка, 3-я строка, 4-я строка, 1-й столбец, 2-й столбец и 3-й столбец в дальнейшем не рассматриваются.
Шаг 6. Среди всех незаполненных клеток у клетки (2,4) наименьшая стоимость перевозки единицы груза — 8. Поэтому делаем поставку в эту клетку. min (95-75, 435-310) = 20. Исключаем 4-й столбец.
После шестого шага наша таблица примет следующий вид:
Таблица 17.
5 | 1 130 | 5 | |||
4 | |||||
125 | 3 | 50 | |||
Первая строка, 3-я строка, 4-я строка, 1-й столбец, 2-й столбец, 3-й столбец и 4-й столбец в дальнейшем не рассматриваются.
Шаг 7. Осталась одна незаполненная клетка (3,5), стоимость перевозки единицы груза — 9. Поэтому делаем поставку в эту клетку. min (435-310, 145-20) = 125. Исключаем 4-й столбец.
После седьмого шага наша таблица примет следующий вид:
Таблица 18.
5 | 1 130 | 5 | |||
4 | 125 | ||||
125 | 3 | 50 | |||
Таблица заполнена.
Получаем суммарные затраты:
1*130 + 3*5 + 8*20 + 9*125 + 2*125 + 4*50 + 5*75 + 1*310 = 2565.
Число отмеченных клеток = число строк + число столбцов – 1.
8 = 4 + 5 – 1
8 = 8