Транспортни проблем — разлика између измена
Садржај обрисан Садржај додат
мНема описа измене |
Нема описа измене |
||
Ред 3:
'''Транспортни проблем''' је један од проблема са поља [[операциона истраживања|операционих истраживања]]. Задатак је да се за дате спискове добављача и поручилаца неке [[роба|робе]] организује [[транспорт]] тако да његове цене буду оптималне.
== Опис
[[Слика:Transport matrix elements-sr.svg|300п|мини|Елементи матрице транспортног проблема]]
Прво треба саставити матрицу транс портног проблема. То је [[матрица (математика)|матрица]] типа -{m × n}-, где је -{m}- број достављача а -{n}- број купаца. Свако поље -{(i,j)}- је намењено бележењу трговине између -{i}--тог достављача и -{j}--тог купца. Поред тога, свако поље матрице такође има и једно потпоље у којем се налази цена транспорта једне јединице трговине. Вредности ''-{a<sub>1</sub>, ... , a<sub>m</sub>}-'' представљају редом расположиве капацитете достављача, а ''-{b<sub>1</sub>, ... , b<sub>n</sub>}-'' потребе поручилаца. Нека цена транспорта за поље -{(i,j)}- буде -{C<sub>i,j</sub>}-, а количина испоручене робе -{X<sub>i,j</sub>}-.
Ред 15:
Након овога следи итеративни поступак оптимизације укупне цене транспорта. У матрици се тражи циклус који садржи тачно једно празно поље и непаран број попуњених поља. Правило за формирање циклуса је да се следећи елемент може само тражити по вертикали или по хоризонтали. Уколико је, почев од непопуњеног поља, збир цена транспорта изабраних поља са непарним индексом мањи него код поља са парним индексом прелази се на следећи корак, у супротном се тражи нови циклус.
По налажењу једног циклуса који одговара горе наведеном правилу о сумама вредности својих чланова, изабире се минимална вредност свих поља која циклус укључује. Ова вредност се потом одузима од свих поља са парним индексом у циклусу а додаје се сваком пољу са непарним индексом. Ово поређење се такође може вршити сумом свих елемената низа, с тим што знак за сваки следећи елемент алтернира. Да би услов био испуњен, сума мора бити мања од нуле. Као што је већ поменуто, непопуњено поље има индекс број 1, а смер даљег нумерисања није битан јер је број изабраних поља увек паран.
Кад се количина испоручене робе у неком пољу анулира, у том пољу остаје број нула и оно се не рачуна као непопуњено. Процес тражења циклуса и модификовања бројева у њему се понавља докле год постоје циклуси који задовољавају наведене услове.
Ред 22:
:<math>\sum_{i=1}^m{\sum_{j=1}^n{X_{(i,j)} \cdot C_{(i,j)}}}</math>
== Пример ==
Рецимо да су дата три достављача, који редом располажу са 8, 5 и 6 пошиљки, и четири поручиоца са потражњама за 6, 4, 5 и 4 пошиљке. Уз то је позната и транспортна матрица:
:<math>C = \begin{bmatrix}
4 & 1 & 2 & 1 \\
1 & 3 & 5 & 1 \\
1 & 1 & 3 & 2 \\
\end{bmatrix}</math>
{|
|width="320"|Тада ће матрица транспортног проблема, пре почетне расподеле, изгледати овако:
|width="20"|
|width="320"|А након расподеле по методи северозападног угла, овако:
|-
|[[Слика:Transportation problem example 1-01.svg|250п]]
|width="20"|
|[[Слика:Transportation problem example 1-02.svg|250п]]
|}
Након расподеле методом северозападног угла углавном је до коначног решења потребно више итерација него након расподеле методом најмањих цена. Овде је изабран метод северозападног угла да би се проблем кроз већи број итерација што боље представио.
Следећи корак је трагање за циклусом који одговара наведеном услову. Један такав је означен на слици испод. Пошто је ''δ = 1 - 4 + 1 - 3 < 0'', у овом циклусу ће се у сваком „негативном“ пољу од испоручене робе одузети минимална вредност (у овом случају ''-{min{2, 2, 6} = 2}-''), а „позитивном“ пољу иста додати.
{|
|width="320"|Обележена матрица:
|width="20"|
|width="320"|Резултат је следећи:
|-
|[[Слика:Transportation problem example 1-03.svg|190п]]
|width="20"|
|[[Слика:Transportation problem example 1-04.svg|190п]]
|}
[[Категорија:Оптимизација]]
| |||