Метод потенциалов для задачи Td

 

Метод потенциалов - модификация симплекс - метода решения задач ЛП применительно к ТЗ. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. В отличие от обычной задачи, где равенство является необходимым и достаточным условием разрешимости задачи, здесь оно является лишь необходимым условием. Например, если , при каком-то i, то задача решения не имеет. Поэтому достаточным условием разрешимости задачи является существование хотя бы одного допустимого решения.

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

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

а_m+1 = и дополнительный (n+1) столбец с потребностями (аналогично открытой ТЗ). При этом с_{i, n+1}=c_{m+1, j}=M и с_{m+1, n+1}=0. Полученную расширенную задачу решают методом потенциалов, пока не освободятся все блокированные клетки. Если это удается, то получают опорное решение исходной задачи. В противном случае исходная задача не имеет допустимого решения.

Для оптимальности решения необходимо и достаточно существование потенциалов u₁, u₂,…, u_m, v₁, v₂, …, v_n таких, что выполняются следующие три условия:

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

Базисными переменными называются такие x_ij, которые удовлетворяют строгим неравенствам . Однако, если их число окажется меньше ранга r=m + n - 1, то к базисным переменным можно присоединить необходимое число клеток, для которых или при условии ацикличности.

 

Вопросы для самоконтроля

1. Сформулируйте постановку транспортной задачи.

2. Чем отличается закрытая транспортная задача от открытой?

3. Как осуществить переход от открытой транспортной модели к закрытой?

4. Какой план ТЗ называют опорным, оптимальным?

5. Какой опорный план ТЗ является вырожденным?

6. В чем сущность метода потенциалов?

7. Что называется циклом ТЗ?

8. Если добавлен фиктивный пункт запаса, то превышают суммарные потребности или запасы?

9. Как выразить плату за доставку единицы груза в оптимально плане ТЗ?

10. Как узнать, что получен оптимальный план ТЗ?

11.Сформулировать постановку ТЗ с ограничениями по пропускной способности.

12. Каковы условия разрешимости задачи?

13. Какова сущность метода потенциалов решения ТЗ с ограничениями по пропускной способности?

14. Какова сущность венгерского метода решения ТЗ? Каковы его достоинства?