Построение первоначального т-плана методом наименьшей стоимости

Метод наименьшей стоимости осуществляет распределение продукта, имеющегося у поставщиков, между потребителями с учетом удельной стоимости перевозок с_ij. Поэтому данный метод позволяет получить Т-план, отвечающий как правило меньшим суммарным затратам, чем метод северо-западного угла.

Содержание метода:

1). Построим таблицу перевозок (Таблица 1).

2). Приведем задачу к сбалансированному виду, если это необходимо.

3). Выделим клетку таблицы с наименьшей удельной стоимостью перевозки груза. Пусть это будет клетка с адресом (l,k). Присвоим выбранной клетке объем поставкиx_l,k, равный минимальному из значенийа_l(объем продукта, имеющийся уl-го производителя) иb_k (объем продукта, необходимыйk-му потребителю):x_l,k=minа_l,b_k .

4). Рассмотрим случай, когда а_l > b_{k .} Эта ситуация означает то, что запросыk-гопотребителя полностью удовлетворены, а объем продукта, имеющийся уl-го производителя уменьшились на величину равнуюx_l,k. Следовательно необходимо вычеркнуть из таблицыk-й столбец и значениеа_l уменьшить наb_k.

В случае а_l < b_kпредполагается, что запас продуктаl-го производителя исчерпан, аk-употребителю необходимо доставить еще (b_k - а_l) объема продукта. Следовательно необходимо вычеркнуть из таблицы строку с номеромl, а значениеb_k уменьшить наа_l.

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

Замечание 5: если на очередном шаге метода отыщется несколько клеток с наименьшей удельной стоимостью перевозок, то предпочтение отдается:

во-первых клетке, соответствующей не фиктивному потребителю (поставщику);

во-вторых той клетке, где объем перевозок может быть наибольшим.

Проиллюстрируем применение метода наименьшей стоимости для построения первоначального Т-плана на примере ЗАДАЧИ (*).

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

2).Начнем построение первоначального Т-плана с нахождения клетки с минимальной удельной стоимостью. Это клетка (2;1). Поставим в соответствие ей величину поставки равную х₂₁ = minа₂,b₁=min130, 150=130. Следовательно, мы вывезли со склада В весь имеющийся груз, т.е. а₂=0. Вычеркнем вторую строку таблицы. В пункта необходимо доставить ещеb₁=150-130 = 20 усл.ед. груза (Отразим изменения в таблице 11).

• Следующая клетка с минимальной удельной стоимостью – (1;1). Впишем в нее величину поставки равную х₁₁ = minа₁,b₁=min100,20=20. Все потребности пунктааудовлетворены, поэтому вычеркнем 1-й столбец таблицы. Запасы груза на складе А уменьшились на 20 усл.ед., т.е. а₁=100-20=80 усл.ед. (Внесем изменения в таблицу 12).

Таблица 11 Таблица 12

		а	б	с	д				а	б	с	д
		(150)	120	80	50				(150)	120	80	50
		20							+0
А	100	3	5	7	11		А	(100) 80	3	5	7	11
									20
В	(130) 0	1	4	6	2		В	(130) 0	1	4	6	2
		130							130
С	170	5	8	12	7		С	170	5	8	12	7

- Выделим клетку (1,2), так как ей соответствует наименьшая удельная стоимость из числа оставшихся. Внесем в нее объем поставки х₁₂ = minа₁,b₂=min80,120=80. Таким образом, со склада А вывезли весь груз (1-ю строку вычеркиваем), а потребности 2-го потребителя сократились на 80 усл.ед. Внесем изменения в таблицу 13.

- На данном этапе наименьшая удельная стоимость соответствует клетке (3,4). Следовательно х₃₄ = minа₃,b₄=min170,50=50. Это означает, что запросы пунктадудовлетворены полностью (столбец №4 вычеркиваем), а запасы груза на складе С уменьшились на 50 усл.ед. (Табл.14).

- Выделим клетку (3;2) с наименьшей из числа оставшихся удельной стоимостью и х₃₂ = minа₃,b₂=min120,40=40. Потребности пунктабудовлетворены полностью – вычеркиваем 2-й столбец таблицы. Объем груза на складе С уменьшается на 40 усл.ед., т.е.b₂= 120-40=80 (Табл.14).

- Осталась одна свободная клетка (3;3) - выделим ее. Впишем в нее величину поставки х₃₃ = minа₃,b₃=min80,80=80. Получили: со склада С вывезли весь оставшийся груз, и потребности пунктасполностью выполнены (Табл. 15).

Таблица 13 Таблица 14

		а	б	с	д				а	б	с	д
		(150)	(120)	80	50				(150)	(120)	80	(50)
		+0	40						+0	40		+0
А	(100) 0	3	5	7	11		А	(100) 0	3	5	7	11
		20	80						20	80
В	(130) 0	1	4	6	2		В	(130) 0	1	4	6	2
		130							130
С	170	5	8	12	7		С	(170) 120	5	8	12	7
												50

Таблица 14 Таблица 15

		а	б	с	д				а	б	с	д
		(150)	(120)	80	(50)				(150)	(120)	(80)	(50)
		+0	+0		+0				+0	+0	+0	+0
А	(100) 0	3	5	7	11		А	(100) 0	3	5	7	11
		20	80						20	80
В	(130) 0	1	4	6	2		В	(130) 0	1	4	6	2
		130							130
С	(170) 80	5	8	12	7		С	(170) 0	5	8	12	7
			40		50					40	80	50

Построенный первоначальный план перевозок проверим на возможные ошибки:

1 строка: 100=20+80; 2 строка: 130=130; 3 строка: 170= 40+80+50.

1 столбец: 150=20+130; 2 столбец: 120=80+40; 3 столбец: 80=80; 4 столбец: 50=50.

Таким образом проверка показала, что первоначальный план перевозок построен верно. Дадим экономическую интерпретацию полученных результатов:

1). В пункт а перевезли 20 и 130 усл.ед груза со складов А и В соответственно; в пункт б – 80 и 40 усл.ед. груза со складов А и С соотв.; в пункт с – 80 усл.ед груза со склада С и в пункт д – 50 усл.ед груза со склада С.

2). Суммарные затраты при этом будут равны L=3*20+1*130+5*80+8*40+12*80+7*50=2220 (ден.ед.).

Построенный первоначальный Т-план необходимо проверить на оптимальность.