Понятие цикла транспортной задаче

Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке “Файлы работы” в формате PDF

Источник

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

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

Под планом перевозок понимают объем перевозок, т.е. количество товара, которое необходимо перевезти от i-го поставщика к j-му потребителю. Для построения математической модели задачи необходимо ввести m·n штук переменных хij, i= 1,…, n, j= 1, …, m, каждая переменная хij обозначает объем перевозок из пункта Ai в пункт Вj.
Набор переменных X = {xij} и будет планом, который необходимо найти, исходя из постановки задачи.

Ограничения задачи примут вид:

Это условие для решения закрытых и открытых транспортных задач (ЗТЗ).

Очевидно, что для разрешимости задачи 1 необходимо, чтобы суммарный спрос не превышал объема производства у поставщиков:

Если это неравенство выполняется строго, то задача называется «открытой» или «несбалансированной», если же , то задача называется «закрытой» транспортной задачей, и будет иметь вид (2):

 – условие сбалансированности.

Это условие для решения закрытых транспортных задач (ЗТЗ).

В силу ограничений (2) нетрудно увидеть, что ЗТЗ является задачей ЛП и может быть решена симплекс-методом после приведения ее к специальному виду. Но структура системы ограничений имеет некоторою специфику,
а именно: каждая переменная хij входит ровно два раза в неравенства системы, и все переменные входят в неравенства системы с коэффициентом 1. В силу этой специфики существует более простой метод решения, называемый методом потенциалов, который, по сути,
является некоторой модификацией симплекс-метода. По-прежнему идеей является переход от одного опорного плана к другому, обязательно «лучшему» с точки зрения значения целевой функции. Каждому опорному плану также соответствует своя распределительная таблица. Переход осуществляется от одного плана к другому, пока полученный план не будет удовлетворять условию оптимальности.
Необходимо научиться строить первоначальный опорный план. В качестве первоначального плана годится любое решение системы уравнений (2). Заметим, что это система линейных уравнений, состоящая из m + n уравнений с m*n неизвестными. Можно доказать, что линейно независимых уравнений в системе (2) m + n – 1, ввиду условия сбалансированности, т.е. базисных переменных должно быть m + n– 1. Итак, в качестве плана будем представлять себе таблицу размера m ∙ n, в которой должно быть занято m + n – 1 клеток, отвечающих базисным переменным xij.

Транспортные задачи с неправильным балансом

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

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

в рассмотрение вводится фиктивный потребитель с потребностью

и тарифами на перевозку ci ( k +1) =0.
Если же

то вводится фиктивный поставщик, запасы которого равны

с тарифами на перевозку c ( n +1)j=0.  Этим приемом задача сводится к закрытой транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи. Заметим, что при составлении начального опорного решения для ускорения вычислений в последнюю очередь следует (хотя и не обязательно) распределять запасы фиктивного поставщика и удовлетворять запросы фиктивного потребителя, несмотря на то, что им соответствуют наименьшие тарифы на перевозку (равные 0).

Построение первоначального опорного плана по правилу наименьшей стоимости

Построение плана по правилу наименьшей стоимости заключается в следующем. Рассматриваем матрицу (таблицу) транспортных расходов,
стоимостей, данную изначально в качестве условия задачи. Выбираем клетку с минимальной ценой перевозки (клетка с номером i, j) и помещаем в эту клетку наименьшее из чисел {ai, bj}. Затем исключаем из рассмотрения строку, соответствующую поставщику (если аi меньшее), или столбец, соответствующий потребителю (если вj меньшее). Исключение строки означает, что запасы i-го потребителя удовлетворены. Из оставшейся таблицы снова выбираем наименьшую стоимость, и т.д. продолжаем до тех пор, пока все запасы не исчерпаны, а потребности не удовлетворены. Проверьте, что сумма чисел в каждой строке получившейся таблицы равна аi,
а сумма чисел в каждом столбце равна вj, что и требовалось. Число занятых клеток должно равняться m + n – 1, в противном случае, если занятых клеток меньше, чем m + n – 1, дополним таблицу необходимым количеством нулей (нулевых перевозок) и будем считать эти клетки с нулями занятыми так, чтобы общее количество занятых клеток равнялось равно m + n – 1. Нули поставим в клетки, соответствующие минимальной стоимости.

Метод потенциалов

При построении плана мы ставим задачу найти хоть какой-нибудь, не обязательно лучший, оптимальный план, удовлетворяющий ограничениям задачи.
Теперь нам хотелось бы уметь отвечать на вопрос: является ли найденный опорный план оптимальным, и если нет, то «улучшать» его. Эту задачу решает метод потенциалов, предложенный в 1949 г. советскими учеными Л.В. Канторовичем и М.К. Гавуриным. теоретической основой метода является теорема.

Теорема. Если для некоторого опорного плана Х = {xij} транспортной задачи можно подобрать систему из m + n чисел u1, u2, …, um, v1, v2, … vn, называемых потенциалами, то план оптимален тогда и только тогда, когда выполняются условия:

1. ui+vj=cij для всех xij > 0                                                      (1)
2.  ui+vj ≤ cij для всех i = 1,m, j = 1,n

где (cij) – матрица стоимостей перевозок.

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

I шаг (вычисление потенциалов).

Условие (1) представляет собой систему из ( m + n – 1) линейных уравнений с (m + n) неизвестными потенциалами. Поэтому одно из неизвестных полагаем равным 0 для определенности, затем последовательно находим остальные потенциалы.

II шаг (проверка плана на оптимальность).

Для проверки плана на оптимальность необходимо проверить условие (2). Для занятых клеток это условие выполняется, именно на них достигается равенство. Остается посчитать суммы ui + vj для свободных клеток. Если ui + vj ≤ сij, то, по теореме, план является оптимальным и задача решена.

III шаг (улучшение плана).

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

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

Графически нетрудно представить цикл в виде ломаной, каждое звено которой лежит в строке или в столбце, причем в каждой строке или столбце не более чем по одному звену.

Примеры:

С понятием цикла связаны важные свойства планов:

1. допустимый план является опорным, когда из занятых этим планом клеток нельзя образовать ни одного цикла;
2. если имеем опорный план, то для каждой свободной клетки можно образовать единственный цикл, содержащий данную клетку и некоторые из занятых.

Улучшение плана производится по следующей схеме. В подчеркнутых клетках табл. 2 находим клетку с наибольшей разностью ui + vj – cij, т.е. где условие (2) нарушается максимально.

Затем для этой клетки, согласно утверждению 2, строим единственный цикл. Набор клеток в цикле помечаем поочередно знаками «+» и «–», начиная с «+» в свободной клетке.

Начиная с клетки (1, 1), где условие (2) нарушено максимально, строим цикл. Клетку (1, 1) помечаем знаком «+». Цикл единственен, у нас все занятые клетки вошли в цикл, но это необязательно. Строим новый план хn по правилу:

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

Виды транспортных задач

1. Классическая транспортная задача (перевозка грузов от поставщиков к потребителям);
2. Задача коммивояжера;
3. Задача о назначениях;

Методы решения транспортных задач

1. Классическая транспортная задача (перевозка грузов от поставщиков к потребителям);
   
   Методы решения: метод потенциалов, симплексный метод;
2. Задача коммивояжера;
   
   Методы решения: метод ветвей и границ, венгерский метод, метод минимальных линий;
3. Задача о назначениях;
   
   Методы решения: венгерский метод, метод Мака, метод минимальных линий;

Источник