Построение опорного плана методом северо-западного угла.

Поставщики и их мощности, тыс.куб. м.			Потребители и их спрос, тыс.куб.м.				Остатки по строкам итерации
			В1	В2	В3	В4	1	2	3	4	5	6
			450	400	200	350
А1	300		6 300	8	7	10	0
А2	600		4 150	7 400	6 50	8		450	50	0
А3	500		9	8	5 150	12 350					350	0
Остатки по столбцам	Итерации	1	150
		2	0
		3		0
		4			150
		5			0
		6				0

В итоге получили некоторое возможное решение. Проверка сумм ∑X_ij по строкам и столбцам показывает на допу­стимость такого плана распределения поставок и отсутствие арифметических ошибок.

Вычислим значение целевой функции. Для этого перемножим удельные стоимости доставки на соответствующие объемы и найдем сумму

Рассмотрим еще один способ составления начального плана - способ минимального элемента.

Способ минимального элемента несколько сложнее, но позволяет отыскать начальное решение очень близкое к оптимальному, а иногда и оптимальное.

Сущность его заключается в следующем.

В матрице стоимостей отыскивается клетка с минималь­ным значением C_ij и в эту клетку записывается поставка X_ij =min (a_i b_j). Если матрица содержит несколько одинако­вых минимальных значений C_ij, то выбирают любое одно.

После этого вычеркивается строка или столбец. Если a_i> b_j, вычеркивают столбец, при a_i < b_j вычеркивают стро­ку.

Далее процесс (итерации, шаги) повторяют до тех пор, пока не будут распределены все поставки.

Если матрица большая и в уме не удержать нераспреде­ленные мощности и спрос на шагах в процессе распределе­ния на части значений a_i и b_j, в конце каждого шага оста­точные величины записывают.

Рабочая таблица имеет форму, приведенную в табл. 4.3.

Таблица 4.3.

Построение опорного плана по методу минимального элемента.

Поставщики и их мощности, тыс.куб. м.			Потребители и их спрос, тыс.куб.м.				Нераспределенные мощности на шагах
			В1	В2	В3	В4	1	2	3	4	5	6
			450	400	200	350
А1	300		6	8	7	10 300	300	300	300	300	0
А2	600		4 450	7 150	6	8	150	150	0
А3	500		9	8 250	5 200	12 50	500	300	300	50	50	0
Неудовлетворенный спрос на шагах		1	0	400	200	350	950
		2		400	0	350		750
		3		250		350			600
		4		0		350				350
		5				50					50
		6				0						0

Распределение поставок по методу минимального эле­мента выполняется в следующей последовательности.

Шаг 1. Находим минимальное значение стоимости C_ij. В нашем случае это будет C₂₁ = 4. В эту клетку таблицы за­писываем возможную поставку, т. е. минимальную из А₂ и В₁, Сравнивая А₂ = 600 и В₁ = 450, записываем в клетку Х₂₁ поставку 450. Вычисляем нераспределенные мощности по­ставщиков и неудовлетворенный спрос потребителей.

Потребитель В₁ — удовлетворен полностью, во вспомога­тельной части таблицы проставляем 0, а столбец в дальней­ших расчетах не рассматриваем.

Потребитель В₂ неудовлетворен, его спрос остался рав­ным 400, что и записываем во вспомогательной части табли­цы.

Потребитель В₃ — неудовлетворен, спрос остался — 200.

Потребитель В₄ — неудовлетворен, спрос —350.

Поставщик А₁ — мощность его не распределена, остаток нераспределенной мощности, равный 300, записываем во вспомогательной части таблицы справа.

Поставщик А₂ — часть мощности распределена потреби­телю В₁ но осталась нераспределенной мощность 600—450 = = 150, что и записываем во вспомогательную часть таблицы, как нераспределенную мощность на первом шаге.

Поставщик А₃ — мощность его не распределена и запи­сываем результат нераспределенной мощности 500.

Сумма нераспределенных мощностей и неудовлетворен­ного спроса по результатам первой итерации (шага) равна 950, что и записываем в итоге и это является проверкой того, что нет арифметических ошибок.

Шаг 2. Находим минимальное значение стоимости C_ij без вычеркнутого столбца В₁ это значение С₃₃ =5. Записы­ваем в эту клетку возможную поставку-минимум из А₃ = 500 и В₃=200, min=200, записываем нераспределенные мощно­сти и неудовлетворенный спрос на этом шаге и их сумму, равную 750, и вычеркиваем из дальнейшего рассмотрения столбец у которого спрос удовлетворен.

Шаг 3. Минимальный элемент А₂В₂ = 7. В эту клетку записываем минимальное значение из нераспределенной мощ­ности А₂=150 и спроса В₂=400, min=150. В результате третьего шага мощность поставщика А₂ исчерпана, а сумма нераспределенных мощностей и неудовлетворенного спросаосталась равной 600. Продолжая аналогично, доводим рас­пределение до конца,

Шаг 4. Минимальное C_ij из оставшихся имеют клетки А₁В₂ и А₃В₂ — выбираем А₃В_2. Записываем сюда поставку 250 как минимум из значений остатка потребителя В₂ и по­ставщика А₃ и так далее.

Результат распределения по методу минимального элемента показан в табл. 4.3.

Вычисляем значение целевой функции полученного начального решения:

R= 10* 300 + 4 *450 + 7 *150 + 8 *250 + 5*200+ 12*50 = 9450 тыс. руб.

Видим, что это решение более целесообразное, чем полученное методом северо-западного угла. Но это не значит, что полученное решение оптимальное.