Графический метод решения задач линейного программирования

_{Согласно  правилу учета  наименьших затрат мы должны дать поставку в клетку имеющую наименьший показатель затрат, это клетка (А1; В1) показатель затрат равен  1, в эту клетку мы дадим 250 единиц груза, при этом  потребности В1 удовлетворены полностью, а мощность поставщика А1 уменьшились до 50 единиц груза.}

Пункты  отправления	Мощности  поставщиков	Пункты  назначения и их спрос
		250-250=0	200	290	260
	300-250=50	1     250	4	5	11
	320	12	8	3	14
	380	10	15	7	9

_{Далее мы дадим поставку в клетку (А2; В3), где  показатель затрат равен 3. Передав в эту  клетку 290 единиц груза, мы полностью удовлетворим потребности пункта В3 и уменьшим мощность поставщика А2 до 30 единиц груза.}

Пункты  отправления	Мощности  поставщиков	Пункты  назначения и их спрос
		0	200	290-290=0	260
	50	1     250	4	5	11
	320-290=30	12	8	3    290	14
	380	10	15	7	9

_{Заполняя  аналогичным образом, соответствующие  клетки таблицы придем к следующей схеме  поставок:}

Пункты  отправления	Мощности  поставщиков	Пункты  назначения и их спрос
		250-250	200-50-30-120	290-290	260-260
	300-250-50	1     250	4     50	5	11
	320-290-30	12	8     30	3    290	14
	380-120-260	10	15  120	7	9     260

_{При данном распределении поставок целевая функция  F будет равна:}

_{F=250+4*50+8*30+15*120+3*290+9*260=5700}

_{Далее необходимо проверить  является ли данная схема поставок оптимальной, для этого снизу и справа имеющейся таблицы присоединим дополнительные строку и столбец.}

Пункты  отправления	Мощности  поставщиков	Пункты  назначения и их спрос
		250	200	290	260
	300	1     250	4     50	5	11
	320	12	8     30	3    290	14
	380	10	15  120	7	9     260

_{Каждой  клетке таблицы поставим в соответствие ее оценку, полученную как алгебраическую сумму показателя затрат клетки и соответствующих  чисел, записанных в  дополнительных строке и столбце. Эти  числа подбираются  таким образом, чтобы  оценки заполненных  клеток равнялись  нулю. Оценки свободных  клеток могут быть положительными, отрицательными или равными нулю.}

_{Впишем  в правый верхний  угол каждой клетки ее оценку.}

 

 

 

 

 

Пункты  отправления	Мощности  поставщиков	Пункты  назначения и их спрос
		250	200	290	260
	300	7 0 1     250	0 0 4     50	6 0 5	9 133 11	-1
	320	12	8     30	3    290	14	-5
	380	-2 10	0 15  120	-3 7	0 9     260	-12
		0	-3	2	3

 

_{Таким образом определили, что первоначальное распределение поставок не является оптимальным (в  клетках (А3; В1) и (А3; В3) отрицательные  оценки). Необходимо произвести перераспределение  поставок. Сделаем поставку в клетку (А3; В3). Но очевидно, что поставка в эту клетку повлечет изменения поставок в соседние клетки, другими словами образуется цикл. Передадим 120 единиц груза из клетки (А3; В2) в клетку (А3; В3), затем увеличим на 120 единиц поставку в клетку (А2; В2), а поставку в клетке (А2; В3) уменьшим на 120 единиц. Получили:}

Пункты  отправления	Мощности  поставщиков	Пункты  назначения и их спрос
		250	200	290	260
	300	7 0 1     250	0 0 4     50	6 0 5	9 103 11	-1
	320	12	8     150	3    170	14	-5
	380	1 10	0 15	0 7    120	0 9     260	-9
		0	-3	2	0

_{При данном распределении поставок целевая функция  F будет равна:}

_{F=250+4*50+8*150+3*170+7*120+9*260=5340}

_{Таблица не содержит пустых клеток с отрицательными оценками, а значит мы нашли оптимальное  решение данной задачи.}

_{Следует отметить, что данное распределение поставок могло бать получено при первоначальном распределении по правилу северо-западного  угла.}