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

Пример.

1. Проверим, является ли данная задача замкнутой.

Подсчитаем суммарные запасы груза и суммарные потребности заказчиков

, .

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

2. Построим первый опорный план транспортной задачи методом северо-западного угла.

Начинаем заполнение распределительной таблицы с верхней левой клетки, то есть построение исходного опорного плана начинаем с удовлетворения потребностей первого потребителя b1 за счет запасов первого поставщика a1. Для этого сравниваем запас a1 = 200 с потребностями b1 = 150. Так как a1 > b1, то потребности b1 полностью удовлетворяем за счет a1, и в первую клетку помещаем min (200, 150)=150. У первого поставщика осталось 50 единиц груза. Так как потребности первого получателя груза полностью удовлетворены, исключим из рассмотрения первый столбец, заполнив в нем оставшиеся клетки точками. Далее заполняем таблицу по строкам слева направо и сверху вниз. Следующая самая верхняя левая незаполненная клетка – (1,2). Потребителю b2 поставляем 50 единиц груза, оставшихся у первого поставщика. Поскольку от первого поставщика весь груз вывезен, заполняем оставшиеся клетки первой строки точками. Второму получателю, пока что, недопоставлено 80 единиц груза. Следующая незаполненная клетка – (2,2). Потребителю b2 отправляем недостающие 80 единиц груза, при этом его потребности полностью удовлетворены, поэтому оставшиеся клетки во втором столбце заполняем точками. У второго поставщика a2 осталось еще 100 единиц груза. Аналогичным образом заполняем оставшиеся клетки, пока не удовлетворим всех потребителей и не вывезем все запасы груза у поставщиков.

В результате распределения груза получим первый опорный план, в котором x11 = 150, x12 = 50, x22 = 80, x23 = 100, x33 = 50, x34 = 140. Эти переменные соответствуют заполненным клеткам и являются базисными, остальные переменные, соответствующие клеткам с точками, являются свободными (значения свободных переменных равны нулю). Первый опорный план можно представить в матричном виде

Число заполненных клеток k = 6. Это число должно равняться рангу системы ограничений r = m + n – 1 = 3 + 4 – 1 = 6. Так как k = r = 6, то построенный план является невырожденным. Подсчитаем затраты на перевозку по этому плану

.

3. Построим первое опорное решение транспортной задачи методом минимальной стоимости (минимального тарифа).

Найдем клетку с минимальным тарифом. Это клетка (1,3) с тарифом

C13 =1. Построение исходного опорного плана начинаем с занесения поставки груза в клетку с наименьшей стоимостью c13. Заполняем клетку x13 = 150. Оставшиеся клетки третьего столбца заполняем точками, так как потребности третьего получателя полностью удовлетворены. У первого поставщика осталось 50 единиц груза. Ищем следующую клетку с минимальным тарифом. Таких клеток две: c14 =2, c32 =2. Заполним сначала клетку (3,2). Поставим в нее x32=min (190, 130)=130. Второй столбец заполняем точками. У третьего поставщика осталось 60 единиц груза. Ищем следующую клетку с наименьшим тарифом – это клетка (1,4). В нее помещаем 50 единиц груза, min(50,140)=50. Первую строку заполняем точками, так как от первого поставщика вывезен весь груз. Четвертому получателю недопоставлено 90 единиц. Аналогичным образом распределяем весь имеющийся груз и получаем первый опорный план перевозок.

Подсчитаем затраты на перевозку по этому плану.

.

Итак, в каждой строке и в каждом столбце таблицы заполнена хотя бы одна клетка, циклов по заполненным клеткам нет, число заполненных клеток m+n-1=6, следовательно, план опорный и невырожденный.

4. Проверка первого опорного плана (решения) на оптимальность. Метод потенциалов

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

В таблице в дополнительном столбце справа помещаем потенциалы отправителей , а в строке снизу – потенциалы получателей. Составим систему уравнений для определения потенциалов:

Из этой системы находим

Считаем оценки для свободных клеток:

Запишем получившиеся оценки в левом верхнем углу свободных клеток.

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

Сроим цикл пересчета, начиная с клетки (3,3), в которую нужно поместить поставку груза (её отмечают знаком «+»), и двигаясь по занятым клеткам (в данном случае это клетки (3,4), (1,4), (1,3)), поочередно отмечая их знаками «-», «+». Если в клетку (3,3) добавили +, то в смежных по циклу клетках необходимо вычесть для сохранения баланса перевозок по третьей строке и третьему столбцу. Звенья цикла должны быть параллельны строкам или столбцам таблицы, причем в каждой вершине цикла встречаются ровно два звена, одно из которых находится в строке, а другое – в столбце. Количество вершин в цикле должно быть четно. В результате построения цикла в соответствующих строках и столбцах должно быть парное количество знаков «-», «+».

Определяем величину поставки в клетку (3,3), как минимальную величину из поставок, стоящих в отрицательных клетках, то есть . Перераспределяем по циклу поставки на величину . Значение записываем в незанятую клетку (3,3), отмеченную знаком «+», двигаясь по циклу, прибавляем эту величину к поставкам в клетках со знаком «+», вычитаем в клетках со знаком «-».

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

Если освобождается больше одной клетки, то есть число заполненных клеток меньше числа m + n - 1, то такой план называется вырожденными, и для определения потенциалов необходимо ввести недостающее количество нулевых элементов в число основных базисных переменных. Свободные клетки заполняют нулевыми поставками так, чтобы они не образовывали цикл по заполненным клеткам, и чтобы в каждой строке и в каждом столбце находилась хотя бы одна заполненная клетка. Проверим новый опорный план на оптимальность. Пусть =0. Тогда найдем все остальные потенциалы, рассматривая только заполненные клетки и помня, что для них , то есть что сумма потенциалов должна быть равна тарифу, стоящему на пересечении соответствующих потенциалам строки и столбца.

Число заполненных клеток k=m+n-1, следовательно, план невырожденный. Найдем оценки Для всех клеток с точками, где стоят свободные переменные. Данный опорный план не является оптимальным, так как не все оценки для свободных клеток , а именно, .

Возьмем клетку (2,2) за начало цикла пересчета. Цикл будет проходить по клеткам (2,2), (3,2), (3,3), (1,3), (1,4), (2,4) и опять вернется в (2,2).

Ищем количество единиц груза , перераспределяемых по циклу пересчета, как минимум по клеткам, помеченных знаком минус. Получаем новый опорный план

Проверяем данный опорный план на оптимальность

Полученный опорный план является оптимальным, так как все оценки для свободных клеток . Выписываем оптимальный план: x11 = 0; x12 = 0; x13 = 60; x14 =140; x21 = 150; x22 = 30; x23 = 0; x24 = 0; x31 = 0; x32 = 100; x33 = 90; x34 = 0. Или в матричной форме

Высчитываем минимальные затраты на транспортировку продукции:

< Предыдущая		Следующая >