4.2.4. Метод минимальной стоимости для решения закрытой транспортной задачи

В связи с тем, что реальные ТЗ имеют большую размерность тп – порядка 100 и выше, для них разработаны специальные численные методы, которые являются менее трудоемкими, чем методы линейного программирования. Данный метод относится к классу эвристических.

Исходные данные для решения задачи записываются в табличной форме.

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

сij xij	1	2	3	4	5	(Запасы)
1	10	8	5	6	9	48
2	6	7	8	6	5	30
3	8	7	10	8	7	27
4	7	5	4	6	8	20
(Заявки)	18	27	42	12	26	125

Содержательная постановка задачи. Имеется m пунктов производства некоторой однородной продукции с объемом производства a_i единиц в i-м пункте, , и n пунктов потребления данной продукции с объемом потребления b_j единиц в j-м пункте, . Суммарные объемы производства и потребления продукции равны:

.

Перевозка продукции возможна из любого пункта производства в любой пункт потребления, при этом стоимость перевозки единицы продукции из i-го пункта производства в j-й пункт потребления равна c_ij .

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

Алгоритм эвристического метода включает в себя следующие этапы:

1. Формируется таблица с заданными a_i, b_j, c_ij и с начальными нулевыми объемами перевозимой продукции (x_ij)_mn – распределительная таблица.

2. В таблице стоимости перевозок (без учета «вычеркнутых» строк и столбцов) выполняется поиск минимального элемента (ячейки таблицы с минимальной стоимостью перевозок). Пусть это будет ячейка (e,f ) с элементом c_ef  – стоимостью перевозки продукции из пункта производства e в пункт потребления f .

3. Возможны три случая:

   1. Если a_e < b_f , то потребность пункта потребления b_f  уменьшается на a_e , строка e «вычеркивается», т.к. вся продукция из пункта производства вывозится полностью: x_ef = a_e , b_f = b_f  – a_e , a_e = 0;

   2. Если a_e > b_f , то ресурс пункта производства a_e уменьшается на b_f , столбец f  «вычеркивается», т.к. потребность пункта потребления удовлетворяется полностью: x_ef = b_f , a_e = a_e – b_f , b_f = 0;

   3. Если a_e = b_f , то используется, либо случай a, либо случай b. Если выбирается случай а, считают, что потребность пункта потребления b_f = 0 должна быть полностью удовлетворена. Если же выбирается случай b, полагают, что ресурс пункта производства a_e = 0 должен быть полностью вывезен.

4. «Вычеркнутая» строка или столбец далее на этапе 2 не используется.

5. Если вычеркнуты не все строки и столбцы, то переходят к п. 2.

6. Завершить работу алгоритма.

Решение, полученное с помощью данного метода, отличается от точного решения по значению критерия оптимальности на 5-15%, что вполне приемлемо для практики.

Пример. Примером может служить модель производства и доставки кирпича с кирпичных заводов на стройки республики.

Пусть имеется 3 кирпичных завода (m = 3) и 4 крупные стройки (n = 4).

Производственные мощности каждого завода равны соответственно 10, 20 и 30 тонн кирпича в смену, т.е. а₁ = 10, а₂ = 20, а₃ = 30. Потребности строек составляют 30 т., 10 т., 15 т., 5 т. кирпича в смену, т.е. b₁ = 30, b₂ = 10, b₃ =15, b₄ = 5.

Определить оптимальные количества перевозимого кирпича с каждого завода на четыре стройки из условия минимума суммарной стоимости поставок.

Исходная таблица стоимостей перевозок:

Стройки Заводы	1	2	3	4
1	5	4	1	3	10
2	6	2	7	5	20
3	8	3	9	2	30
	30	10	15	5	60

Математическая модель суммарной стоимости перевозок:

.

Согласно алгоритму находим ячейку с наименьшей стоимостью: ячейка 1-3, для нее а₁ = 10 < b₃ = 15, т.о. весь кирпич первого завода будет направлен на третью стройку, потребность третьей стройки уменьшится на 15 – 10 = 5 т., следовательно, в ячейку 1-3 записываем x₁₃ = 10, вычеркиваем первую строку, b₃ стало равно 5. В оставшейся части таблицы ячейки с наименьшим значением стоимости – 2-2 и 3-4, выбираем 2-2:

Стройки Заводы	1	2	3	4
1	5	4	1 10	3	10
2	6	2	7	5	20
3	8	3	9	2	30
	30	10	5	5	60

а₂ = 20 > b₂ = 10, следовательно, x₂₂ = 10, то есть вторая стройка полностью может быть обеспечена кирпичом со второго завода, на котором осталось а₂ = 20 – 10 = 10, второй столбец вычеркиваем. Следующая ячейка с наименьшей стоимостью 3-4:

Стройки Заводы	1	2	3	4
1	5	4	1 10	3	10
2	6	2 10	7	5	10
3	8	3	9	2	30
	30	10	5	5	60

И так далее.

Стройки Заводы	1	2	3	4
1	5	4	1 10	3	10
2	6	2 10	7	5	10
3	8	3	9	2 5	25
	30	10	5	5	60

Стройки Заводы	1	2	3	4
1	5	4	1 10	3	10
2	6 10	2 10	7	5	10
3	8	3	9	2 5	25
	20	10	5	5	60

Стройки Заводы	1	2	3	4
1	5	4	1 10	3	10
2	6 10	2 10	7	5	10
3	8 20	3	9 5	2 5	5
	20	10	5	5	60

Оставшиеся 5т. кирпича с 3-го завода будут направлены на третью стройку.

Таким образом, получили следующее решение:

,

которое можно представить в виде графа (рис. 4.4).

Рис. 4.4

Суммарная стоимость перевозок составила