Сведение открытой транспортной задачи к закрытой

Решение транспортной задачи начинается с выяснения вопроса о том, является ли задача открытой или закрытой.

Если задача является открытой, то необходимо провести процедуру сведения задачи к закрытой (закрытие задачи).

С этой целью при a < b добавляется фиктивный поставщик с запасом груза , если же a > b , то добавляется фиктивный потребитель с заказом груза .

В обоих случаях соответствующие фиктивным объектам тарифы перевозок полагаются равными нулю. В результате суммарная стоимость перевозок не изменяется.

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

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

• составление первоначального плана перевозок;
• последовательные улучшения плана перевозок (перераспределение поставок) до тех пор, пока план перевозок не станет оптимальным.

Решение ОЗЛП начинается с нахождения опорного плана. Для транспортной задачи такой план всегда существует. Ниже описываются два метода составления опорного плана (первоначального плана перевозок). При этом ненулевые элементы плана перевозок будем записывать в соответствующие пустые клетки транспортной таблицы с исходными данными задачи, а символом (i, j) будем обозначать клетку таблицы, содержащую информацию о перевозках груза от поставщика к потребителю .

3.1.Составление первоначального плана перевозок с помощью метода северо-западного угла

Составление первоначального плана перевозок начинается с перевозки запасов поставщика (находящегося в «северо-западном» угле таблицы). Будем за счет его запасов максимально возможно удовлетворять заказы сначала потребителя , затем и так далее. Таким образом, мы будем заполнять таблицу, начиная с клетки (1,1), и двигаться вправо по строке до тех пор, пока остаток запасов поставщика не окажется меньше заказа очередного потребителя. Для выполнения этого последнего (по строке) заказа используем остатки запаса поставщика , а недостающую часть добавим из запасов поставщика , то есть переместимся на следующую строку таблицы по столбцу, соответствующему указанному потребителю. Далее аналогичным образом распределим запасы поставщика , затем и так далее.

Теорема. Решение, построенное по методу северо-западного угла является опорным.

Проиллюстрируем алгоритм метода северо-западного угла на следующем примере.

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

Таблица.

Распределяя запасы поставщика сначала потребителю , а затем , получаем: = 100 , =40. После этого у поставщика остается еще 20 единиц груза, а потребителю нужно 80 единиц. Удовлетворим спрос потребителя , отправив ему 20 единиц груза, оставшихся у поставщика , 30 единиц груза от поставщика и 30 единиц груза от поставщика . Следовательно, = 20 , = 30 и = 30, причем у поставщика остается 60 единиц груза. Этот груз отправим потребителю . Таким образом = 60 , все запасы груза вывезены и все потребители удовлетворены.

Теперь мы можем подсчитать общую стоимость всех перевозок по данному плану:

z = 4 ×100 + 8 × 40 +10 × 20 + 2 ×30 + 6 ×30 + 5 × 60 = 1460 .

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

3.2. Составление первоначального плана перевозок с помощью метода наименьшей стоимости

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

Теорема. Решение, построенное по методу наименьшей стоимости является опорным.

Замечание. При наличии в таблице клеток с одинаковыми тарифами, планы, полученные с помощью этого метода, могут быть разными, однако они, несомненно, ближе к оптимальному плану, чем план, составленный по методу северо-западного угла.

Сформируем теперь первоначальный план по методу наименьшей стоимости для рассмотренного ранее примера и сравним результаты с результатами, полученными по методу северо-западного угла. Поскольку наименьший тариф (число 2) стоит в клетке (2,3), то запишем в эту клетку элемент = 30 . Тогда 50, а 2-ю строку таблицы можно больше не учитывать. Среди оставшихся клеток имеются три клетки с наименьшим тарифом перевозок, равным 4 - это (1,1); (3,1) и (3,2). Выберем, например, клетку (1,1) и запишем в нее число =100. Получаем, что 60, а 1-й столбец таблицы больше не рассматриваем. Теперь наименьший тариф, равный 4, проставлен в клетке (3,2), поэтому = 40, 50 и 2-й столбец больше не нужен. Далее выбираем клетку (1,4) с тарифом 5 и пишем в нее = 60 . Исключив из рассмотрения сразу 1-ю строку и 4-ый столбец (поскольку = 60), переходим к последней клетке (3,3), в которую записываем перевозку = 50.

Таблица.

Найдем суммарную стоимость перевозок по этому плану:

z = 4 ×100 + 5 × 60 + 2 × 30 + 4 × 40 + 6 × 50 = 1220.

Сравнивая это значение со стоимостью плана, полученного по методу северо-западного угла, видим, что 1220 < 1460, то есть мы получили более выгодный план перевозок.

4. Вырожденные планы. Циклы и пополнение плана

Прежде, чем перейти к анализу оптимальности планов и способам их улучшения, выясним, каким требованиям должны удовлетворять составляемые планы. Для этого вернемся к системе ограничений (1). В соответствии с определением плана перевозок у матрицы сумма элементов i-й строки равняется , а сумма элементов j-о столбца равняется . Условие закрытости транспортной задачи a = b означает, что среди уравнений системы (1) независимыми являются только уравнений, поэтому в любом базисном решении этой системы должно быть базисных переменных. Поскольку свободные переменные в таком решении равны нулю, то в транспортной таблице им будут соответствовать пустые клетки.

Определение. Клетки таблицы, в которые записаны отличные от нуля перевозки, называются базисными, а остальные (пустые) - свободными.

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

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

Определение. Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией так, чтобы две соседние вершины ломаной были расположены либо в одной строке, либо в одном столбце. Ломаная линия может иметь точки самопересечения, но не в клетках цикла.

Определение. План называется ациклическим, если его базисные клетки не содержат циклов.

Пример.

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

Замечание. Планы, полученные с помощью метода северо-западного угла и метода наименьшей стоимости, ациклические.

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

Возвращаясь к рассматриваемому примеру, видно, что первоначальный план, полученный по методу наименьшей стоимости, имеет 5 базисных клеток, однако = 3 + 4 -1 = 6. Значит, план нужно пополнить еще одной базисной клеткой. Попробуем выбрать для этого клетку (2,2). Соединив базисные клетки горизонтальными и вертикальными отрезками (рис. 1), получаем:

(1,1) ––––––––––––– (1,4) (1,1) –––––––––––––– (1,4)

(2,2) –– (2,3) (2,3) –– (2,4)

(3,2) –– (3,3) (3,2) –– (3,3)

рис.1 рис.2

Видим, что пополненный таким образом план содержит цикл из клеток (2,2); (2,3); (3,3) и (3,2), следовательно, клетка (2,2) была выбрана неудачно. Взяв вместо нее клетку (2,4), получим ациклический план (рис. 2). Поэтому можно заполнить эту клетку, положив =0.

5. Проверка оптимальности плана и перераспределение поставок с помощью метода потенциалов

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

Дата добавления: 2015-06-30; просмотров: 424; Нарушение авторских прав

Мы поможем в написании ваших работ!