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

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

.

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

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

1. Тогда условия задачи имеют вид

В каждое неравенство введем дополнительную переменную x_i,n+1. В сумме эти переменные должны равняться величине дебаланса:

получаем закрытую задачу:

Потребность b_n+1 - фиктивная.Чтобы сбалансировать задачу, достаточно ввести фиктивного потребителя с потребностью, равной дебалансу - к исходной таблице добавляется один столбец с потребностью b_n+1 и затратами C_i,n+1 =0. Ненулевые дополнительные переменные в оптимальном решении будут показывать количество груза, остающееся в соответствующих ПО.

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

Введем в каждое неравенство дополнительную переменную x_{m+ 1, j}. Сбалансированная модель:

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

Этот способ будет неприемлем, если потребители по-разному реагируют на недопоставки. Тогда возможны два варианта решения задачи:

1. ЛПР корректирует потребности, обеспечивая баланс.

2. Выявляется и учитывается влияние недопоставок для каждого потребителя. Если зависимость потерь от величины недопоставки линейная, то задача остается в классе линейных. Задача балансируется как при формальном подходе, но в дополнительной строке в качестве затрат берутся удельные потери от недопоставки.