Приведение открытой транспортной задачи к закрытой

В открытой или несбалансированной задаче имеет место неравенство .

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

Пусть в исходной задаче предложение превышает спрос: Тогда условия задачи имеют вид (22) (23)

В каждое неравенство (22) введем дополнительную переменную x_{i, n+1}. В сумме эти переменные должны равняться величине дебаланса:

Добавляя это равенство к условиям (23), получаем закрытую задачу: Потребность b_n+1 называют фиктивной. Таким образом, чтобы сбалансировать задачу, достаточно ввести фиктивного потребителя с потребностью, равной дебалансу. Практически это означает, что к исходной таблице добавляется один столбец с потребностью b_n+1 и затратами C_{i, n+1} =0. Ненулевые дополнительные переменные в оптимальном решении будут показывать количество груза, остающееся в соответствующих ПО.

Спрос превышает предложение: . При этом исходные условия записываются в виде: Введем в каждое неравенство дополнительную переменную x_{m+ 1, j}. Очевидно, что сумма этих переменных равна величине дебаланса: С учетом этого равенства сбалансированная модель принимает вид:

Такое преобразование соответствует введению фиктивного поставщика (дополнительной строки) с возможностью a_{m+ 1} и нулевыми затратами C_{m+ 1, j}. Дополнительная переменная x_{m+ 1, j} имеет смысл количества груза, недопоставленного j- му ПН.

Алгоритм решения сбалансированной Т_d-задачи:

1. Построение начального плана перевозок. План может получиться как допустимый, так и искусственный (недопустимый). 2. Выделение базисных клеток. Если их меньше m+n- 1, то добавляются клетки на границе. 3. Нахождение потенциалов из системы (18).

4. Вычисление оценок по формуле (19)

5. Начало цикла. Определение множества G по матрицам плана и оценок.

6. Проверка признака оптимальности: если G =Æ (эквивалент (25)), переход на шаг 10.

7. Определение вводимой переменной (клетки kr) по (5.26) и построение цикла пересчета.

8. Построение нового плана: вычисление q₀ в зависимости от принадлежности kr по (27) или (28) и соответствующее перемещение по циклу.

9. Получение матрицы оценок нового плана с помощью преобразования матрицы оценок старого плана (как в Т-задаче). Переход на шаг 5.

10. Конец. Полученный план является оптимальным, если не содержит запрещенных перевозок (с затратами М).