Практическая работа № 8.2. « Транспортная задача с ограничениями»

Цель работы:

Значительное количество экономических задач (порой не имеющих ничего общего с транспортировкой грузов) могут быть сведены к модели транспортной задачи. При этом величины c_ijмогут означать стоимость, расстояние, время, производительность. В то же время в самой транспортной задаче возникают различные ограничения (например, по критерию времени, при наличии особо важного потребителя – в открытой задаче это означает, что его запросы должны быть удовлетворены полностью). Ниже для примера рассматривается ситуация, когда вводятся ограничения на пропускную способность. При этом необходимо учитывать следующие правила.

Правило 1 (для ограничения ). Перед решением задачи необходимо уменьшить запасы i -го поставщика и запросы j -го потребителя на величину a (резервируется перевозка ). После решения задачи в оптимальном плане найденный объем перевозок увеличивается на величину a.

Правило 2 (для ограничения ). Перед решением задачи необходимо вместо j -го потребителя ввести двух потребителей. Первый, с номером j, будет иметь запрос a, второй, с номером N+1 (в таблицу добавляем новый, последний столбец) будет иметь запрос B_j-a. Стоимости в новом столбце совпадут с исходными за исключением i -й строки (в ней стоимость принимается равной сколь угодно большому положительному числу – это обеспечивает «не появление в ней перевозок»). После решения задачи в оптимальном плане объемы перевозок j -го и N+1 -го потребителей суммируются.

Пример 8.2.1. Решить транспортную задачу с таблицей 8.2.1 и ограничениями:

В А


				Таблица 8. 2.1.

Решение. Задача изначально является закрытой (и запасы, и запросы равны 200). В соответствии со сказанным выше запасы во второй строке и запросы в первом столбце уменьшаются на 30 (учтено условие ). Далее во втором столбце запросы остаются равными 40, а мы достраиваем новый столбец с запросами 50-40=10. Стоимости в этом столбце совпадут с исходными, кроме ячейки в первой строке, куда запишем сколь угодно большое положительное число M. В результате нам нужно будет решать обычным способом транспортную задачу с таблицей 8.2.2. В таблице 8.2.3 приводится ее начальное опорное решение, найденное методом минимальной стоимости (читатель может провести построение сам).

В А
				М

Таблица 8.2.2.

В А
				М

Таблица 8.2.3.

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

В А					u_i
		6+(-1)-2=3>0	3+(-1)-4<0	6+(-1)-M<0 М	-1
	2+(-2)-3<0	6+(-2)-5<0		6+(-2)-5<0	-2

v_j

Таблица 8.2.4

Результаты вычислений, а также расчет оценок в свободных клетках приведены в таблице 8. 2.4. В ней в ячейке (1;2) находится положительная оценка, значит, решение не оптимальное. Цикл для перехода будем строить, начиная с этой ячейки (других «кандидатов» просто нет). В цикл войдут ячейки (1;2), (3;2), (3;1), (1;1). При этом у ячеек (1;2) и (3;1) знак «+», у ячеек (3;2) и (1;1) знак «-». Из значений в «отрицательных» ячейках (50 и 40) наименьшее 40, это и будет перемещаемый объем перевозок q.

В таблице 8.2.5 приведен результат перемещения по циклу (новое опорное решение), ячейка (3;2) освободилась, но число занятых клеток сохранилось. Результат нахождения потенциалов (проверьте!) и расчет оценок находятся в таблице 8.2.6.

В А
	М

		Таблица 8.2.5

В А

u_i

3+(-1)-4<0

6+(-1)-M<0 М

-1

2+(-2)-3<0

3+(-2)-5<0

6+(-2)-5<0

-2

3+0-6<0

v_j

Таблица 8.2.6. Итак, найденное решение оптимально (все оценки неположительны) – для задачи с таблицей 8.2.2. Теперь нужно вернуться к исходной задаче, в соответствии с правилами 1 и 2. Для этого объединим объемы перевозок из второго и четвертого столбца; запасы второй строки и запросы первого столбца увеличим на 30 (т.е. вернем в исходное состояние) и объем перевозок в ячейке (1;1) также увеличим на 30 (он был равен 0, поэтому получили 30).

В А

Таблица 8.2.7

Оптимальный план исходной задачи дан в таблице 8.2.7 (обратите внимание, что за счет объединения столбцов и появления ненулевого объема перевозок в ячейке (2;1) количество занятых клеток больше числа N+M-1, равного в данной задаче 3+3-1=5). Итак, остается найти оптимальное значение целевой функции: .