Методы построения начального решения

Метод северо-западного угла (СЗУ)

Рассмотрим шаги получения начального базисного решения.

1 шаг. Выделяется крайняя левая верхняя ячейка матрицы планирования (ячейка, расположенная на северо-западе).

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

3 шаг. Вычеркивается строка или столбец с полностью удовлетворенным спросом или реализованным предложением. В случае если в ячейке (i, j) значение спроса равно значению предложения, то вычеркивается на выбор строка или столбец.

4 шаг. В оставшейся матрице снова выбирается крайняя левая верхняя ячейка, и повторяются шаги 2-4.

5 шаг. Если остается не вычеркнутым только одна строка или один столбец, процесс останавливается.

Задача 1. Построение первоначального решения методом СЗУ

Три распределительных центра снабжают продукцией пять сетевых магазинов, потребность которых в ежедневных поставках товара составляет 15, 10, 25, 30, 20 т. соответственно. Каждый распределительный центр может осуществлять ежедневные поставки товаров в количестве 30, 20 и 50 т. соответственно. Стоимость перевозки единицы (тонны) груза от поставщиков в магазины представлена в виде матрицы. Необходимо распределить поставки товаров из распределительных центров в магазины с наименьшими затратами.

 

	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5
Распределительный центр 1 (РЦ 1)
Распределительный центр 2 (РЦ 2)
Распределительный центр 3 (РЦ 3)

Решение

Первоначально определим сбалансированность данной задачи. Суммарное предложение от распределительных центров равно 100 т. Суммарный спрос пяти магазинов 100 т. Так как суммарный спрос равен суммарному предложению, то задача сбалансирована.

На первом шаге (табл. 3.1.1) в ячейку (1,1) введем условную поставку 15 т удовлетворяющую потребность первого магазина в товаре. Предложение первого распределительного центра в данном случае уменьшится на 15 т. Первый столбец из дальнейшего рассмотрения исключаем.

Таблица 3.1.1

	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5	Предложение
(РЦ 1)						30 (15)
(РЦ 2)
(РЦ 3)
Спрос	15 (15)

 

В оставшейся матрице выбираем крайнюю верхнюю левую ячейку (1,2) и полностью удовлетворяем потребность (табл. 3.1.2) второго магазина в товаре. Суммарное предложение первого распределительного центра уменьшится на 25 т. Второй столбец из дальнейшего рассмотрения вычеркиваем.

 

Таблица 3.1.2

	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5	Предложение
РЦ 1	15	10				30 (25)
РЦ 2
РЦ 3
Спрос	15 (15)	10 (10)

 

В оставшейся матрице выбираем крайнюю верхнюю левую ячейку (1,3) и полностью реализуем предложение первого распределительного центра, удовлетворяя потребность (табл. 3.1.3) третьего магазина в товаре на 5 т за счет первого распределительного центра. Первую строку из дальнейшего рассмотрения вычеркиваем.

Таблица 3.1.3

	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5	Предложение
РЦ 1	4	10				30 (30)
РЦ 2
РЦ 3
Спрос	15 (15)	10 (10)	25 (20)

 

В оставшейся матрице выбираем ячейку (2,3) и полностью удовлетворяем потребность третьего магазина в товаре (20 т), тем самым реализуем предложение второго распределительного центра (табл. 3.1.4). Вычеркнем третий столбец из дальнейшего рассмотрения.

Таблица 3.1.4

	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5	Предложение
РЦ 1	15	10	5			30 (30)
РЦ 2						20 (20)
РЦ 3
Спрос	15 (15)	10 (10)	25 (25)

 

Выбираем ячейку (2,4) и вводим поставку равную 0 т, т.к. предложение второго распределительного центра реализовано полностью. В оставшихся двух ячейках вводим соответствующие поставки, удовлетворяющие спрос четвертого и пятого магазинов и реализующие предложение третьего распределительного центра (табл. 3.1.5).

Таблица 3.1.5

	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5	Предложение
РЦ 1						30 (30)
РЦ 2						20 (20)
РЦ 3						50 (50)
Спрос	15 (15)	10 (10)	25 (25)	30 (30)	20 (20)

 

Количество поставок в базисном решении для данной задачи равно 7, что соответствует числу независимых ограничений (m + n – 1).

Суммарные затраты на транспортировку 100 т. товаров от трех распределительных центров в пять сетевых магазинов для полученного первоначального решения будут:

Z = 15*4 + 10*5 + 5*1 + 20*4 + 0*7 + 30*5 + 20*2 = 385 у.е.