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

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

Таблица 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.