Транспортни проблем — разлика између измена
Садржај обрисан Садржај додат
м →Пример |
м упс... дешава се :о) |
||
Ред 13:
Након овога следи итеративни поступак оптимизације укупне цене транспорта. У матрици се тражи циклус који садржи тачно једно празно поље и непаран број попуњених поља. Правило за формирање циклуса је да се следећи елемент може само тражити по вертикали или по хоризонтали. Уколико је, почев од непопуњеног поља, збир цена транспорта изабраних поља са непарним индексом мањи него код поља са парним индексом прелази се на следећи корак, у супротном се тражи нови циклус.
По налажењу једног циклуса који одговара горе наведеном правилу о сумама вредности својих чланова, изабире се минимална вредност свих поља са парним индексом која циклус укључује. Ова вредност се потом одузима од свих поља са парним индексом у циклусу а додаје се сваком пољу са непарним индексом. Ово поређење се такође може вршити сумом свих елемената низа, с тим што знак за сваки следећи елемент алтернира. Да би услов био испуњен, сума мора бити мања од нуле. Као што је већ поменуто, непопуњено поље има индекс број 1, а смер даљег нумерисања није битан јер је број изабраних поља увек паран.
Кад се количина испоручене робе у неком пољу анулира, у том пољу остаје број нула и оно се не рачуна као непопуњено. Процес тражења циклуса и модификовања бројева у њему се понавља докле год постоје циклуси који задовољавају наведене услове.
Ред 42:
Након расподеле методом северозападног угла углавном је до коначног решења потребно више итерација него након расподеле методом најмањих цена. Овде је изабран метод северозападног угла да би се проблем кроз већи број итерација што боље представио.
Следећи корак је трагање за циклусом који одговара наведеном услову. Један такав је означен на слици испод. Пошто је ''δ = 1 - 4 + 1 - 3 < 0'', у овом циклусу ће се у сваком „негативном“ пољу од испоручене робе одузети минимална вредност (у овом случају ''-{min{
{|
|width="320"|Нађени циклус -{C<sub>21</sub>-C<sub>11</sub>-C<sub>12</sub>-C<sub>22</sub>}-:
Ред 51:
|}
Итеративно се опет тражи циклус који задовољава услове. На слици испод је обележен циклус код кога је опет ''δ = 2 - 5 + 1 - 4 < 0'', а минимална вредност ''-{min{3
{|
Ред 64:
{|
|width="320"|Циклус -{C<sub>31</sub>-C<sub>33</sub>-C<sub>13</sub>-C<sub>11</sub>}-<br />δ = 1 - 3 + 2 - 4 < 0<br />-{min{
|width="320"|Циклус -{C<sub>
|-
|[[Слика:Transportation problem example 1-07.svg|190п]]
Ред 72:
{|
|width="320"|Циклус -{C<sub>
|width="320"|Циклус -{C<sub>
|-
|[[Слика:Transportation problem example 1-09.svg|190п]]
Ред 85:
|}
Може се приметити да се кроз итерације испоруке гомилају око поља где је цена транспорта најмања, што је сигнификатор оптимизације. У овом случају алгоритам је од почетне укупне цене транспорта ''-{C<sub>1</sub> = 6·4 + 2·1 + 2·3 + 3·5 + 2·3 + 4·2 = 61}-'' дошао до цене ''-{C<sub>2</sub> =
== Специјални случајеви ==
Ред 93:
* '''Продавац ''-{i}-'' мора све да прода''': Потреба за овим условом се јавља кад је понуда већа од потражње. Решење је да се дефинише још један наручилац коме треба тачна разлика између понуде и потражње, с тим да су цене доставке њему од свих достављача, сем достављача ''-{i}-'' једнаке нули, а цена доставке од достављача ''-{i}-'' до овог наручиоца ∞.
* '''Наручилац ''-{j}-'' треба да буде намирен''': Аналогно претходном случају, дефинише се још један продавац, који нуди разлику између потражње и понуде и постави се да су цене транспорта од њега до свих осталих наручилаца једнаке нули, а до ''-{j}-''-ог ∞.
[[Категорија:Оптимизација]]
| |||