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

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

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

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

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

Задача:

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

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

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

Транспортная задача, в которой суммарные запасы и суммарные потребности совпадают, называется закрытой моделью; в противном случае - открытой. Открытая модель решается приведением к закрытой. В случае, когда суммарные запасы превышают суммарные потребности, вводится фиктивный 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. Продолжаем так же «конем».

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

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

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

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


Наши рекомендации