Метод наименьшей стоимости

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

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

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

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

4 шаг. В оставшейся матрице выбирают ячейку с наименьшей стоимостью поставки единицы груза и повторяют шаги 2-4.

5 шаг. В случае полной реализации спроса и предложения процесс останавливают.

В качестве примера рассмотрим решение приведенной выше задачи №1 методом наименьшей стоимости. В матрице выберем ячейку (1,3) с наименьшей стоимостью поставки единицы (тонны) груза и введем условную поставку 25 т, удовлетворив тем самым спрос Магазина 3 (табл. 3.1.6). Третий столбец из дальнейшего рассмотрения вычеркиваем.

Таблица 3.1.6

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

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

Таблица 3.1.7

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

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

Таблица 3.1.8

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

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

Таблица 3.1.9

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

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

Таблица 3.1.10

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

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

Таблица 3.1.11

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

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

Z = 25*1 + 5*3 + 15*2 + 5*7 + 10*4 + 20*5 + 20*2 = 285 у.е.

Метод Фогеля

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

1 шаг. Рассчитать для каждой строки и каждого столбца штрафы (разность между двумя наименьшими значениями стоимости транспортировки единицы груза).

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

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

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

5 шаг. Соответствующая строка или столбец вычеркивается. Если значение спроса для ячейки (i.j) равно предложению, то вычеркивается строка или столбец на выбор.

6 шаг. В оставшейся матрице для каждой строки и столбца повторяются шаги 1–5.

7 шаг. Процесс считается завершенным, когда реализовано всё предложение и полностью удовлетворён спрос.

В качестве примера рассмотрим задачу №1. В матрице рассчитаем штрафы как разницу между двумя минимальными стоимостями поставки единицы груза для соответствующей строки или столбца (табл. 3.1.12).

Таблица 3.1.12

Максимальный штраф равен двум и соответствует как строкам, так и столбцам. Рассчитаем сумму штрафов по строкам и столбцам.

Сумма штрафов по строкам: 2 + 2 + 0 = 4

Сумма штрафов по столбцам: 1 + 1 + 1 + 2 + 2 = 7

Максимальная сумма штрафов – по столбцам. Следовательно, из четвертого и пятого столбцов выбираем ячейку с наименьшей стоимостью транспортировки единицы груза – ячейку (3,5).

Таблица 3.1.13

	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5	Штраф	Штраф	Предложение
РЦ 1					4	3 – 1 = 2	3 – 1 = 2
РЦ 2						4 – 2 = 2	4 – 2 = 2
РЦ 3						2 – 2 = 0	3 – 2 = 1	50 (30)
Штраф	3 – 2 = 1	5 – 4 = 1	2 – 1 = 1	5 – 3 = 2	4 – 2 = 2
Спрос					20 (20)

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

Максимальный штраф также находится и в строках, и в столбце.

Сумма штрафов по строкам: 2 + 2 + 1 = 5

Сумма штрафов по столбцам: 1 + 1 + 1 + 2 = 5

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

Таблица 3.1.14

	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5	Штраф	Штраф	Предложение
РЦ 1	4				4	3 – 1 = 2	3 – 1 = 2	30 (30)
РЦ 2						4 – 2 = 2	4 – 2 = 2
РЦ 3						2 – 2 = 0	3 – 2 = 1	50 (30)
Штраф	3 – 2 = 1	5 – 4 = 1	2 – 1 = 1	5 – 3 = 2	4 – 2 = 2
Штраф	3 – 2 = 1	6 – 4 = 2	4 – 2 = 2	7 – 5 = 2
Спрос				30 (30)	20 (20)

Сумма штрафов по строкам: 2 + 1 = 3

Сумма штрафов по столбцам: 1 + 2 + 2 + 2 = 7

Таблица 3.1.15

	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5	Штраф	Штраф	Штраф	Предложение
РЦ 1	4		1		4	3 – 1 = 2	3 – 1 = 2		30 (30)
РЦ 2						4 – 2 = 2	4 – 2 = 2	6 – 2 = 4
РЦ 3						2 – 2 = 0	3 – 2 = 1	4 – 3 = 1	50 (5)
Штраф	3 – 2 = 1	5 – 4 = 1	2 – 1 = 1	5 – 3 = 2	4 – 2 = 2
Штраф	3 – 2 = 1	6 – 4 = 2	4 – 2 = 2	7 – 5 = 2
Штраф	3 – 2 = 1	6 – 4 = 2
Спрос			25 (25)	30 (30)	20 (20)

Максимальная сумма штрафов – по столбцам, следовательно, выберем в столбцах два и три ячейку с наименьшей стоимостью транспортировки единицы груза.

В данную ячейку введем поставку, полностью удовлетворяющую спрос (табл. 3.1.15), и пересчитаем штрафы для строк. Третий столбец из дальнейшего рассмотрения вычеркнем.

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

Таблица 3.1.16

	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5	Штраф	Штраф	Штраф	Предложение
РЦ 1	4				4	3 – 1 = 2	3 – 1 = 2		30 (30)
РЦ 2						4 – 2 = 2	4 – 2 = 2	6 – 2 = 4	20 (5)
РЦ 3						2 – 2 = 0	3 – 2 = 1	4 – 3 = 1	50 (5)
Штраф	3 – 2 = 1	5 – 4 = 1	2 – 1 = 1	5 – 3 = 2	4 – 2 = 2
Штраф	3 – 2 = 1	6 – 4 = 2	4 – 2 = 2	7 – 5 = 2
Штраф	3 – 2 = 1	6 – 4 = 2
Спрос	15 (15)		25 (25)	30 (30)	20 (20)

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

Таблица 3.1.17

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

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

Z = 30*3 + 15*2 + 5*6 + 5*4 + 25*2 + 20*2 = 260 у.е.

Первоначальное решение задачи методами северо-западного угла, наименьшей стоимости и Фогеля показало, что наиболее близкое к оптимальному решение дает метод Фогеля.

Для нахождения оптимального плана перевозок товаров применяют распределительный метод, метод потенциалов.

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

Не нашли, что искали? Воспользуйтесь поиском: