Транспортни проблем

Из Википедије, слободне енциклопедије

Транспортни проблем је један од проблема са поља операционих истраживања‎. Задатак је да се за дате спискове добављача и поручилаца неке робе организује транспорт тако да његове цене буду оптималне.

Опис решења[уреди]

Елементи матрице транспортног проблема

Прво треба саставити матрицу транс портног проблема. То је матрица типа m × n, где је m број достављача а n број купаца. Свако поље (i,j) је намењено бележењу трговине између i-тог достављача и j-тог купца. Поред тога, свако поље матрице такође има и једно потпоље у којем се налази цена транспорта једне јединице трговине. Вредности a1, ..., am представљају редом расположиве капацитете достављача, а b1, ..., bn потребе поручилаца. Нека цена транспорта за поље (i,j) буде Ci,j, а количина испоручене робе Xi,j.

Следећи корак је расподела транспорта тако да сви могући транспорти буду направљени тј. да збир испоручених јединица робе буде максималан.

\sum_{i=1}^m{\sum_{j=1}^n{X_{(i,j)}}} = max

Овај почетни распоред не мора бити оптималан. Два поступка за добијање ових распореда су метод најмањих цена и метод северозападног угла.

Након овога следи итеративни поступак оптимизације укупне цене транспорта. У матрици се тражи циклус који садржи тачно једно празно поље и непаран број попуњених поља. Правило за формирање циклуса је да се следећи елемент може само тражити по вертикали или по хоризонтали. Уколико је, почев од непопуњеног поља, збир цена транспорта изабраних поља са непарним индексом мањи него код поља са парним индексом прелази се на следећи корак, у супротном се тражи нови циклус.

По налажењу једног циклуса који одговара горе наведеном правилу о сумама вредности својих чланова, изабире се минимална вредност свих поља са парним индексом која циклус укључује. Ова вредност се потом одузима од свих поља са парним индексом у циклусу а додаје се сваком пољу са непарним индексом. Ово поређење се такође може вршити сумом свих елемената низа, с тим што знак за сваки следећи елемент алтернира. Да би услов био испуњен, сума мора бити мања од нуле. Као што је већ поменуто, непопуњено поље има индекс број 1, а смер даљег нумерисања није битан јер је број изабраних поља увек паран.

Кад се количина испоручене робе у неком пољу анулира, у том пољу остаје број нула и оно се не рачуна као непопуњено. Процес тражења циклуса и модификовања бројева у њему се понавља докле год постоје циклуси који задовољавају наведене услове.

Укупна цена транспорта у сваком моменту је сума производа вредности испоручене робе и цене транспорта сваког поља.

\sum_{i=1}^m{\sum_{j=1}^n{X_{(i,j)} \cdot C_{(i,j)}}}

Пример[уреди]

Рецимо да су дата три достављача, који редом располажу са 8, 5 и 6 пошиљки, и четири поручиоца са потражњама за 6, 4, 5 и 4 пошиљке. Ово је најоптималнији случај када је потражња једнака поунди. У пракси се чешће срећу тржиште оријентисано ка купцима, где је понуда већа од потражње и тржиште оријентисано ка продавцима, где је потражња већа од понуде.

Уз то је позната и матрица са ценама транспорта:

C = \begin{bmatrix}
  4 & 1 & 2 & 1 \\
  1 & 3 & 5 & 1 \\
  1 & 1 & 3 & 2 \\
\end{bmatrix}
Тада ће матрица транспортног проблема, пре почетне расподеле, изгледати овако: А након расподеле по методи северозападног угла, овако:
Transportation problem example 1-01.svg Transportation problem example 1-02.svg

Након расподеле методом северозападног угла углавном је до коначног решења потребно више итерација него након расподеле методом најмањих цена. Овде је изабран метод северозападног угла да би се проблем кроз већи број итерација што боље представио.

Следећи корак је трагање за циклусом који одговара наведеном услову. Један такав је означен на слици испод. Пошто је δ = 1 - 4 + 1 - 3 < 0, у овом циклусу ће се у сваком „негативном“ пољу од испоручене робе одузети минимална вредност (у овом случају min{2, 6} = 2), а „позитивном“ пољу иста додати.

Нађени циклус C21-C11-C12-C22: Резултат је следећи:
Transportation problem example 1-03.svg Transportation problem example 1-04.svg

Итеративно се опет тражи циклус који задовољава услове. На слици испод је обележен циклус код кога је опет δ = 2 - 5 + 1 - 4 < 0, а минимална вредност min{3, 4} = 3:

Нађени циклус C13-C23-C21-C11: Резултат:
Transportation problem example 1-05.svg Transportation problem example 1-06.svg

Следи итеративно налажење даљих циклуса и њихова оптимизација:

Циклус C31-C33-C13-C11
δ = 1 - 3 + 2 - 4 < 0
min{1,2} = 1:
Циклус C32-C33-C13-C12
δ = 1 - 3 + 2 - 1 < 0
min{1,4} = 1:
Transportation problem example 1-07.svg Transportation problem example 1-08.svg
Циклус C14-C12-C32-C34
δ = 1 - 1 + 1 - 2 < 0
min{3,4} = 3:
Циклус C24-C21-C31-C34
δ = 1 - 1 + 1 - 2 < 0
min{5,1} = 1:
Transportation problem example 1-09.svg Transportation problem example 1-10.svg
Коначни резултат
Transportation problem example 1-11.svg

Може се приметити да се кроз итерације испоруке гомилају око поља где је цена транспорта најмања, што је сигнификатор оптимизације. У овом случају алгоритам је од почетне укупне цене транспорта C1 = 6·4 + 2·1 + 2·3 + 3·5 + 2·3 + 4·2 = 61 дошао до цене C2 = 5·2 + 3·1 + 4·1 + 1·1 + 2·1 + 4·1 = 24.

Специјални случајеви[уреди]

У пракси се може јавити и пар додатних услова који донекле мењају ток решавања.

  • Доставка од продавца i до наручиоца j није могућа: Постави се да цена доставке Ci,j буде ∞ и на то поље се не распоређује никаква доставка при почетном распоређивању.
  • Продавац i мора све да прода: Потреба за овим условом се јавља кад је понуда већа од потражње. Решење је да се дефинише још један наручилац коме треба тачна разлика између понуде и потражње, с тим да су цене доставке њему од свих достављача, сем достављача i једнаке нули, а цена доставке од достављача i до овог наручиоца ∞.
  • Наручилац j треба да буде намирен: Аналогно претходном случају, дефинише се још један продавац, који нуди разлику између потражње и понуде и постави се да су цене транспорта од њега до свих осталих наручилаца једнаке нули, а до j-ог ∞.