Цель работы:
Значительное количество экономических задач (порой не имеющих ничего общего с транспортировкой грузов) могут быть сведены к модели транспортной задачи. При этом величины cijмогут означать стоимость, расстояние, время, производительность. В то же время в самой транспортной задаче возникают различные ограничения (например, по критерию времени, при наличии особо важного потребителя – в открытой задаче это означает, что его запросы должны быть удовлетворены полностью). Ниже для примера рассматривается ситуация, когда вводятся ограничения на пропускную способность. При этом необходимо учитывать следующие правила.
Правило 1 (для ограничения ). Перед решением задачи необходимо уменьшить запасы i -го поставщика и запросы j -го потребителя на величину a (резервируется перевозка ). После решения задачи в оптимальном плане найденный объем перевозок увеличивается на величину a.
Правило 2 (для ограничения ). Перед решением задачи необходимо вместо j -го потребителя ввести двух потребителей. Первый, с номером j, будет иметь запрос a, второй, с номером N+1 (в таблицу добавляем новый, последний столбец) будет иметь запрос Bj-a. Стоимости в новом столбце совпадут с исходными за исключением i -й строки (в ней стоимость принимается равной сколь угодно большому положительному числу – это обеспечивает «не появление в ней перевозок»). После решения задачи в оптимальном плане объемы перевозок j -го и N+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.
При нахождении потенциалов удобно считать, что . Тогда оставшиеся значения быстро находятся из системы уравнений (по занятым клеткам)
|
|
В А | ui | ||||
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 | ||
vj |
Таблица 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. |
| ||||||||||||||||||||||||
В А | ui | ||||||||||||||||||||||||
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 | |||||||||||||||||||||||||
vj | |||||||||||||||||||||||||
Таблица 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). Итак, остается найти оптимальное значение целевой функции: .