Алгоритмы решения транспортной задачи - pismo.netnado.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Алгоритмы решения транспортной задачи - страница №1/1



Транспортная задача

Содержание


Содержание 2

Алгоритмы решения транспортной задачи 3

Формулировка транспортной задачи 3

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

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

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

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

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

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



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

Алгоритм решения транспортной задачи методом потенциалов 7

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


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

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

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

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


Алгоритмы решения транспортной задачи

Формулировка транспортной задачи


Однородный груз сосредоточен у m поставщиков в объемах . Данный груз необходимо доставить n потребителям в объемах . Известны , i=1,2,,…,m, j=1,2,…,n- стоимости перевозки единицы груза от каждого I-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны.

Исходные данные транспортной задачи обычно записываются в таблице 1.









































….

….











Таблица 1.

Исходные данные задачи могут быть представлены также в виде вектора запасов поставщиков А=(), вектора запросов потребителей

В=() и матрицы стоимостей .


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

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

Такая задача называется задачей с правильным балансом, а ее модель – закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель – открытой .

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


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

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

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

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



Циклом называется такая последовательность клеток таблицы транспортной задачи (i1,j1), (i1,j2), (i2,j2), … , (ik,j1), в которой две и только две соседние клетки расположены в одной клетке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце.

Цикл изображают в таблице транспортной задачи в виде замкнутой ломаной линии. В любой клетке цикла происходит поворот звена ломаной линии на 900. Простейшие циклы изображены на рисунке 1, где звездочкой отмечены клетки таблицы, включенные в состав цикла.


* * * * * *

* * * *
* * * * * *

Рис 1.

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




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


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

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



  1. если , то и исключается поставщик с номером i, , k=1, 2, …, n, kj, ;

  2. если , то и исключается потребитель с номером j, , k=1, 2, …, m, ki, ;

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

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

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



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

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


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

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

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


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

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

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


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

+ -

- 5 +


6

+ -


  1. 4

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

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


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


Широко распространенным методом решения транспортных задач является метод потенциалов. Этот метод позволяет упростить наиболее трудоемкую часть вычислений – нахождение оценок свободных клеток.

Признак оптимальности опорного решения. Если допустимое решение Х=(), i=1,2,,…,m, j=1,2,…,n транспортной задачи является оптимальным, то существует потенциалы (числа) поставщиков , i=1,2,,…,m и потребителей , j=1,2,…,n, удовлетворяющие следующим условиям:

+= при >0,

+ при =0.


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

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



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

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

  3. Строят систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений += при >0. Для того чтобы найти частное решение системы, одному из потенциалов (обычно тому, которому соответствует большее число занятых клеток) задают произвольно некоторое значение (чаще нуль). Остальные потенциалы однозначно определяются по формулам =- при >0, (24)

если известен потенциал , и

=- при >0, (25)

если известен потенциал .



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

  2. Переходят к новому опорному решению, на котором значение целевой функции будет меньше. Для этого находят клетку таблицы задачи, которой соответствует наибольшая положительная оценка max{}=. Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину =. Клетка со знаком «-», в которой достигается , остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным m+n-1. Далее возвращаемся к пункту 3 алгоритма.



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

1. Закрытая транспортная задача.






b1 = 150

b2 = 150

b3 = 300

a1 = 100

2

1

2

a2 = 200

5

7

6

a3 = 300

3

2

5

2. Строим 1-ое опорное решение методом наименьших стоимостей.

 

b1 = 150

b2 = 150

b3 = 300

 

a1 = 100

2

100 1

2

u1

a2 = 200

5

7

200 6

u2

a3 = 300

150 3

50 2

100 5

u3

 

v1

v2

v3

 

3, 4. Проверяем 1-ое опорное решение на оптимальность методом потенциалов.

u1 + v2 = 1

u2 + v3 = 6

u3 + v1 = 3

u3 + v2 = 2

u3 + v3 = 5

u1 = 0 v1 = 2

u2 = 2 v2 = 1

u3 = 1 v3 = 4

11 = 2 – (0 + 2) = 0

13 = 2 – (0 + 4) = -2 < 0

21 = 5 – (2 + 2) = 1 > 0

22 = 7 – (2+ 1) = 4 > 0

Вывод: 1-ый план не является оптимальным.

5. Переходим к новому опорному решению, на котором значение целевой функции будет меньше. Строим цикл.



- 100 + 0

+ 50 - 100

0 100





  1. 0




 

b1 = 150

b2 = 150

b3 = 300

 

a1 = 100

2

0 1

100 2

u1

a2 = 200

5

7

200 6

u2

a3 = 300

150 3

150 2

5

u3

 

v1

v2

v3

 

Проверяем 2-ое опорное решение на оптимальность методом потенциалов.

u1 + v2 = 1

u1 + v3 = 2

u2 + v3 = 6

u3 + v1 = 3

u3 + v2 = 2

u1 = 0 v1 = 2

u2 = 4 v2 = 1

u3 = 1 v3 = 2

11 = 2 – (0 + 2) = 0

21 = 5 – (4 + 2) = -1 < 0

22 = 7 – (4+ 1) = 2 > 0

33 = 5 – (1 + 3) = 2 > 0

Вывод: 2-ий план не является оптимальным.

- + 100


+ 0  - 200

- 150 + 150
100


0   200


  1. 150




 

b1 = 150

b2 = 150

b3 = 300

 

a1 = 100

2

1

100 2

u1

a2 = 200

0 5

7

200 6

u2

a3 = 300

150 3

150 2

5

u3

 

v1

v2

v3

 

Проверяем 3-ье опорное решение на оптимальность методом потенциалов.

u1 + v3 = 2

u2 + v1 = 5

u2 + v3 = 6

u3 + v1 = 3

u3 + v2 = 2

u1 = 0 v1 = 1

u2 = 4 v2 = 0

u3 = 2 v3 = 2

11 = 2 – (0 + 1) = 1 > 0

12 = 1 – (0 + 0) = 1 > 0

22 = 7 – (4+ 0) = 3 > 0

33 = 5 – (2 +2) = 1 > 0

Получили оптимальное решение.

x11 = 0

x12 = 0

x13 = 100

x21 = 0

x22 = 0

x23 = 200

x31 = 150

x32 = 150

x33 = 0



L(x) = 100*2 + 0*5 + 200*6 + 150*3 + 150*2 = 2150 (у. е.)