Методы оптимальных решений (стр. 7 )

9.  Из незачеркнутых элементов минимальный 3 по двум маршрутам А1 М3 и А4 М4. Сравниваем их по количеству доставляемых кг. Выбираем тот, где доставка больше. В нашем случае количество муки одинаково, значит берем любой. Например, А1 М3.

	М1	М2	М3	М4	Запасы
А1	220	4	3100	5	120 100
А2	1 80	3	4	7	80
А3	6	7	5	8	200
А4	3	1.550	4	3	150 100
Надо	100 20	50	230 130	170

10.  Четвертый маршрут определили А1 к М3 100 кг х 3 руб. = 300 руб. У поставщика А1 ничего больше нет, вычеркиваем его из рассмотрения. Магазину М3 осталось докупить 130 кг, записываем в его потребности.

11.  Снова выбираем из светлых оставшихся минимальный по цене маршрут, это А4 М4 по 3 руб. У А4 осталось 100 кг, М4 надо 170 кг, значит везем по маршруту 100 кг.

	М1	М2	М3	М4	Запасы
А1	220	4	3100	5	120 100
А2	1 80	3	4	7	80
А3	6	7	5	8	200
А4	3	1.550	4	3100	150 100
Надо	100 20	50	230 130	170 70

12.  Пятый маршрут определили А4 М4 100 кг х 3 руб. = 300 руб. А4 вычеркиваем из рассмотрения, запасы кончились, магазину М4 еще надо докупить 70 кг. Пишем в его потребности.

13.  Из оставшихся двух берем меньший по цене, это А3М3 по 5 руб. У А3 есть 200 кг, М3 нужно 130 кг. Отправляем по маршруту 130 кг.

	М1	М2	М3	М4	Запасы
А1	220	4	3100	5	120 100
А2	1 80	3	4	7	80
А3	6	7	5130	8	200 70
А4	3	1.550	4	3100	150 100
Надо	100 20	50	230 130	170 70

14.  Шестой маршрут А3М3 130 кг х 5 руб. = 650 руб. Магазин М3 вычеркиваем, ему больше ничего не надо. У А3 осталось еще 70.

15.  Остался последний маршрут по 8 руб. 70 кг. А3М4 выделяем его.

Седьмой маршрут А3М4 70 кг х 8 руб. = 560 руб.

Окончательно матрица перевозок примет вид:

	М1	М2	М3	М4	Запасы
А1	220	4	3100	5	120 100
А2	1 80	3	4	7	80
А3	6	7	5130	870	200 70
А4	3	1.550	4	3100	150 100
Надо	100 20	50	230 130	170 70

16.  Все поставщики доставили свой товар во все магазины. Магазины закупили сколько было необходимо. Первая схема перевозок определена.

17.  Проверяем сумму перевозок по столбцам и строкам. По столбцам перевозки равны потребностям магазина, по строкам перевозки равны запасам поставщиков.

18.  Определяем общую стоимость всех маршрутов:

S = 80 + 75 + 40 + 300 + 300 + 650 + 560 = 2005 руб.

19.  Проводим проверку на оптимальность разработанной схемы перевозок. Для этого каждому магазину и каждому поставщику присвоим неизвестную переменную, которая отражает его потенциал. Для магазинов обозначим потенциалы m1 m2 m3 m4 соответственно. Для поставщиков а1 а2 а3 а4. Разместим их под соответствующими магазинами и поставщиками. Столбец запасы и строку потребностей можно не писать, они нам больше не потребуются.

	М1 m1	М2 m2	М3 m3	М4 m4
А1 а1	220	4	3100	5
А2 а2	1 80	3	4	7
А3 а3	6	7	5130	870
А4 а4	3	1.550	4	3100

20.  Всего потенциалов получилось 8, маршрутов по первой схеме у нас 7, поэтому любому из потенциалов присваиваем нулевое значение, например a1=0. Находим остальные, исходя из условия, что для каждой задействованной в маршруте ячейки цена перевозки 1 кг муки равна сумме соответствующих потенциалов поставщика и магазина данного маршрута.