Вопрос 22 Метод потенциалов для решения стандартной транспортной задачи

МП – модификация симплекс-метода решения задачи ЛП применительно к СТЗ.

Первый точный метод решения транспортной задачи. предложен в 1949 году Кантаровичем А. В. и Гавуриным М. К. по существу он является детализацией метода последовательного улучшения плана применительно к транспортной задаче.

Метод потенциалов позволяет, отправляясь от некоторого опорного плана перевозок, построить решение транспортной задачи за конечное число шагов (итераций).

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

Задача:

Однородный груз, имеющийся в m пунктах отправления (производства) А1, А2,...Аm соответственно в количествах а1, а2,...аm единиц, требуется доставить в каждый из n пунктов назначения (потребления) В1, В2,..., Вn соответственно в количествах b1, b2..., bn единиц. Стоимость перевозки единицы продукции -cij (i=1,m; j=1,n).

Требуется составить такой план перевозок, чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна.

Транспортная задача, в которой суммарные запасы и суммарные потребности совпадают, называется закрытой моделью; в противном случае - открытой. Открытая модель решается приведением к закрытой. В случае, когда суммарные запасы превышают суммарные потребности, вводится фиктивный n+1 потребитель. В случае, когда суммарные потребности превышают суммарные запасы, т.е., вводится фиктивный m+1 поставщик. Для фиктивного тарифы = 0.

Теорема 1. Базисное решение закрытой модели транспортной задачи содержит m+n-1 базисных компонент.

допустимое решение - план, базисное - опорный план, оптимальное - оптимальный план.

Теорема 2. Оптимальный план закрытой модели транспортной задачи существует всегда.

Решение разбивается на 2 этапа:

· Исходное опорное решение

· Приближение к оптим реш-ю

Этап.

· опорный план: способ северо-западного угла.

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

· опорный план: способ min эл-та.

Запись отгрузок в первую очередь в ячейки с min тарифом cij

Этап.

Переменные:

-базисные (заполненные)

-свободные (пустые)

Отыскание симплекс множителей.

-В крайний правый столбец внесем значения неизвестных u1,…,um,

-в нижнюю строку - значения неизвестных v1,…,vn,.

Эти m + n неизвестных для всех (i, j), соответствующих базисным переменным, должны удовлетворять uj = vi - cij.

Полагают u1 = 0. U1+c1j=vj (1j-клетка заполненная). Теперь знаем vj. Vj-cfj=uf (fj-заполненная). Узнали uf. Продолжаем так же «конем».

Потом строим матрицу Д (). Где наим.отр.элемент -будет вершина цикла. Прямые углы, только заполненные клетки. Знаки + и – через одну вершину. Перемещаем максимум сколько возможно. Снова матрица Д, снова если есть отр. элементы, то перемещаем.

1. Строят систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений . Чтобы найти частное решение, одному из потенциалов задают произвольное значение (чаще нуль).

2. Если для всех свободных клеток , то решение заканчивается. Если для каких-то клеток <0, то решение не является оптимальным.

3. Переходят к новому опорному решению. Для этого находят клетку таблицы задачи, которой соответствует наименьшая отрицательная оценка. Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла поочередно расставляют знаки «+» и «-», начиная с «+» в клетке с наименьшей отрицательной оценкой. Осуществляется сдвиг по циклу на величину . Клетка со знаком «-», в которой достигается минимум, остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток было m+n-1. Далее возвращаются к пункту 3 алгоритма. Для экономической интерпретации двойственных оценок под понимаются локальные цены однородного продукта у поставщика, а под - локальная цена у потребителя.