3. Метод дифференциальных рент.

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

Для определения решения транспортной задачи методом дифференциальных рент используют следующий алгоритм:

1. В каждом столбце определяют минимальный тариф и выделяют соответствующую клетку.

2. Выделенные клетки заполняют максимально возможными числами.

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

ОПРЕДЕЛЕНИЕ 6. Строки, соответствующие поставщикам, запасы которых исчерпаны, а потребности выделенных потребителей не удовлетворены, являются отрицательными.

ОПРЕДЕЛЕНИЕ 7. Строки, соответствующие поставщикам, запасы которых не исчерпаны полностью, являются положительными.

ОПРЕДЕЛЕНИЕ 8. Строки, соответствующие поставщикам, запасы которых исчерпаны, а потребности выделенных потребителей удовлетворены, имеют нулевую оценку. При этом, если вторая заполненная клетка, стоящая в столбце, связанном с данной строкой еще одной заполненной клеткой, расположена в положительной строке, данная строка с нулевой оценкой считается положительной. В противном случае - отрицательной.

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

5. Среди полученных разностей определяют минимальную. Это число называют промежуточной рентой.

6. Строят новую таблицу, при этом тарифы, стоящие в положительных строках, переписываются без изменения, а тарифы, стоящие в отрицательных строках, увеличиваются на величину промежуточной ренты.

7. Переходят к п.1.

ЗАМЕЧАНИЯ:

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

2. Если удается распределить все запасы, то получают оптимальный план транспортной задачи.

4. Дополнительные ограничения транспортной задачи.

1. Запрещенные маршруты.

Если по каким-либо причинам невозможно поставлять продукцию из п. А_i в п. В_j , предполагают тариф этого пути сколь угодно большой величиной М, с_ij = М, и решают задачу обычным способом.

2. Обязательные поставки.

а) Если необходимо из п. А_i перевезти в п. В_j определенное количество продукции d_ij, соответствующую клетку заполняют сразу числом d_ij, а в дальнейшем решают задачу, считая заполненную клетку свободной, но с тарифом, с_ij = М, равным очень большому числу, а запасы и потребностиуменьшают на величину d_ij.

б) Если необходимо из п. А_i в п. В_j перевезти не меньше определенного количества продукции d_ij, то считают запасы и потребностименьше на величину d_ij, это количество d_ij считают перевезенным по маршруту А_i В_j, и решают задачу далее обычным способом.

в) Если необходимо перевезти из п. А_i в п. В_j не более определенного количества продукции d_ij, вводят дополнительный пункт назначения с потребностью, равной (- d_ij), потребность в п. В_j делают равной d_ij. Тарифы на перевозки в дополнительный пункт назначения равны тарифам п. В_j , кроме i-той строки, тариф в которой будет равен сколь угодно большому числу М. Решают задачу обычным образом, а при записи ответа объединяют основного и дополнительного потребителя (складывают содержимое столбцов).