Решение транспортной задачи методом потенциалов

1. Сравнивают общий запас груза с суммарным спросом и в случае нарушения баланса приводят задачу к закрытой модели.

2. Условие задачи записывают в форме транспортной таблицы.

3. Строят начальный опорный план перевозок.

4. Проверяют условие для базисных клеток (их должно быть). Если это условие выполняется, то в одну из свободных клеток (как правило, в клетку с наименьшим тарифом) вписывают число 0, и такая клетка считается базисной. Однако число 0 записывают только в те клетки, которые не образуют циклы с ранее заданными клетками.

5. Вычисляют потенциалы и. Каждому поставщику (каждой строке) ставят в соответствие некоторое число, называемое потенциалом поставщика,, и записывают справа от таблицы, а каждому потребителю (или столбцу) – некоторое число, называемое потенциалом потребителя,, и записывают под таблицей. Числа и выбирают так, чтобы в любой базисной клетке их сумма равнялась тарифу. т.е.. Так как количество всех потенциалов и составляет, а занятых клеток, то для определения чисел и придется решать систему из уравнений с неизвестными. Поэтому одному из неизвестных потенциалов придают произвольное значение. Тогда остальные определяются однозначно.

6. Для проверки оптимальности плана просматривают свободные клетки, для которых определяют оценки. Экономически оценка показывает, на сколько денежных единиц изменятся транспортные издержки от загрузки данной клетки единицей груза. Если все оценки неотрицательные, т.е., то план оптимальный и остается посчитать транспортные расходы. Иначе переходят к п. 7.

7. Из отрицательных оценок выбирают минимальную. Пусть это будет. Тогда клетку вводят в число базисных, т.е. строят цикл по загруженныс клеткам с началом в этой клетке и перераспределяют поставки так, чтобы баланс цикла сохранился. Для этого вершинам цикла приписывают чередующиеся знаки «+» и «-» (для «+»). В клетках с «-» отыскивают наименьший груз w, т.е., который и перемещается по клеткам замкнутого цикла, т.е. прибавляется к перевозкам в клетках со знаком «+» (включая свободную) и вычитается из перевозок в клетках со знаком «-». Следовательно, клетка станет свободной и переменная уйдет из базиса. Значение остальных базисных переменных переписываются. Таким образом, получают новую транспортную таблицу с улучшенным планом, для которого транспортные издержки изменятся на величину. Далее переходят к пункту 4.

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

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

Пример 9. Решить задачу из примера 8 методом потенциалов.

3. Занесем исходные данные задачи в таблицу:

1) в столбец - запасы картофеля i-го фермера,;

2) в строку - потребности j-го магазина,;

3) в нижний правый угол каждой клетки, расположенной в i-строке и j-м столбце, ‑ стоимости перевозок,,.

Находим, тогда. Так как, то из рассмотрения исключим строку с номером 2 и.

Из оставшихся клеток находим и тогда. Так как, то из рассмотрения исключаем столбец с номером 3 и и т.д.

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

5. Вычислим потенциалы фермеров и магазинов, используя уравнения для базисных (заполненных) клеток, при дополнительном условии:

Далее по формуле подсчитаем оценки небазисных (пустых) клеток и занесем их значения в левые нижние углы незаполненных клеток

Так как среди оценок есть отрицательные, то данный опорный план не оптимален. Построим цикл и присвоим вершинам цикла чередующиеся знаки «+» и «-». Далее выберем клетку «-» с наименьшим грузом и перераспределим груз с сохранением баланса:

Клетка (1,2) исключается из базового множества, а клетка (2,2) вводится вместо нее.

Подученный опорный план оптимален, так как среди его оценок нет отрицательных:

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

Общее решение.

Дата добавления: 2013-12-13