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

4) Сроки доставки грузов (критерий - затраты времени).   

5) Приведенные затраты  (с учетом эксплуатационных расходов, зависящих от размеров движения  и капиталовложения в подвижной  состав).

6) Приведенные затраты  (с учетом полных эксплуатационных  расходов капиталовложений на  строительство объектов в подвижной  состав).

 

 

где    - эксплуатационные издержки;

 -расчетный коэффициент  эффективности капиталовложения;

 - капитальные вложения, приходящие  на 1 т груза на протяжении участка;

Т  - время следования;

Ц  - цена одной тоны груза.

Позволяет более полно  производить оценку рационализации разных вариантов планов перевозок, с достаточно полной выраженностью  количественно-одновременное влияние  нескольких экономических факторов [15].

 

 

Опорное решение транспортной задачи

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

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

Любое допустимое решение  транспортной задачи можно записать в ту же таблицу, что и исходные данные. Клетки таблицы транспортной задачи, в которых находится отличные от нуля или базисные нулевые перевозки, называются занятыми, остальные – незанятыми или свободными. Клетки таблицы нумеруются так, что клетка, содержащая перевозку , т.е. стоящая в i-й строке и j-м столбце, имеет номер (i,j). Каждой клетке с номером (i,j) соответствует переменная , которой соответствует вектор-условие .

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

Циклом называется такая последовательность клеток таблицы транспортной задачи (i₁,j₁), (i₁,j₂), (i₂,j₂), … , (i_k,j₁), в которой две и только две соседние клетки расположены в одной клетке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце.

Цикл изображают в таблице  транспортной задачи в виде замкнутой  ломаной линии. В любой клетке цикла происходит поворот звена  ломаной линии на 90⁰. Простейшие циклы изображены на рисунке 5, где звездочкой отмечены клетки таблицы, включенные в состав цикла [9].

 

 

*   *    *    *     *    *

     *     *     *     *

*   *     *    *    *      *

Рис.5. Цикл

 

Метод вычеркивания

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

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

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

Ниже приведены примеры  “вычеркиваемого” (опорного) и ”не вычеркиваемого” (не опорного) решений [8]:

 

;            

 

           “вычеркиваемое”            “не вычеркиваемое”

2. Методы построения начального опорного плана

Для определения опорного плана существует несколько методов: метод северо-западного угла (диагональный метод), метод минимальной стоимости(минимального элемента), метод двойного предпочтения и метод аппроксимации Фогеля.

Кратко рассмотрим каждый из них [12].

 

Метод северо-западного  угла

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

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

 

1. если  , то и исключается поставщик с номером i, , k=1, 2, …, n, k j, ;
2. если , то и исключается потребитель с номером j, , k=1, 2, …, m, k i, ;
3. если , то и исключается либо i-й поставщик, , k=1, 2, …, n, k j, , либо j-й потребитель, , k=1, 2, …, m, k i, .

 

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

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

Необходимо иметь в  виду, что метод северо-западного  угла не учитывает стоимость перевозок, поэтому опорное решение, построенное  данным методом, может быть далеко от оптимального.

 

Метод минимальной  стоимости

Метод минимальной стоимости прост, он позволяет построить опорное  решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи С=( ), i=1,2,,…,m,  j=1,2,…,n. Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости min { }, и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Очередную клетку, соответствующую , заполняют по тем же правилам, что и в методе северо-западного угла. Поставщик исключается из рассмотрения, если его запасы использованы полностью. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от данного поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь, затем поставщик исключается из рассмотрения. Аналогично с потребителем.

 

Метод двойного предпочтения

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

 

Метод аппроксимации Фогеля

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

 

Переход от одного опорного решения к другому

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

 

Означенный цикл.

Цикл называется означенным, если его угловые клетки пронумерованы по порядку и нечетным клеткам приписан знак «+», а четным – знак «-» (Рис.6.)       

 

    1+              2-

 

                                             6-                5+

 

                  3+                         4-

 

Рис.6. Означенный цикл

 

Сдвигом по циклу на величину называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком «+», на и уменьшение объемов перевозок во всех четных клетках, отмеченных знаком «-», на .

3. Итерации

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

 

Распределительный метод

Один из наиболее простых методов  решения транспортной задачи – распределительный  метод.

Пусть для транспортной задачи найдено  начальное опорное решение  и вычислено значение целевой функции на этом решении Z( ). По теореме6 для каждой свободной клетки таблицы задачи можно построить единственный цикл, который содержит эту клетку и часть клеток, занятых опорным решением. Означив этот цикл и осуществив сдвиг (перераспределение груза) по циклу на величину , можно получить новое опорное решение Х₂.

Определим, как изменится целевая  функция при переходе к новому опорному решению. При сдвиге на единицу  груза по циклу, соответствующему клетке (l, k), приращение целевой функции равно разности двух сумм: = , где - сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком  «+», - сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком  «-».

В клетках, отмеченных знаком  «+», величины груза прибавляются, что  приводит к увеличению значения целевой  функции Z( ), а в клетках, отмеченных  знаком  «-», величины груза уменьшаются, что приводит к уменьшению значения целевой функции.

Если разность сумм для свободной  клетки (l, k) меньше нуля, т.е. <0, то перераспределение величины по соответствующему циклу приведет к уменьшению значения Z( ) на величину , т.е. опорное решение можно улучшить. Если же величины , называемые оценками , для всех свободных клеток таблицы транспортной задачи неотрицательны, то значение целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальности распределительного метода является условие    =0.         

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

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

 

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

Этот первый точный метод  решения транспортной задачи предложен  в 1949 году Кантаровичем А. В. И Гавуриным  М. К. по существу он является детализацией метода последовательного улучшения  плана применительно к транспортной задаче. Однако в начале он был изложен вне связи с общими методами линейного программирования. Несколько позднее аналогичный алгоритм был разработан Данциом, который исходил из общей идеи линейного программирования. В американской литературе принято называть модифицированным распределительным методом. Метод потенциалов позволяет определитьотправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций).       

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