Транспортни проблем — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
мНема описа измене |
||
Ред 7:
Прво треба саставити матрицу транс портног проблема. То је [[матрица (математика)|матрица]] типа -{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>}-.
Следећи корак је расподела транспорта тако да сви могући транспорти буду направљени тј. да збир испоручених јединица робе буде максималан
:<math>\sum_{i=1}^m{\sum_{j=1}^n{X_{(i,j)}}} = max</math>
Након овога следи итеративни поступак оптимизације. У матрици тражи циклус који садржи тачно једно празно поље и непаран број попуљених поља. Правило за формирање циклуса је да се следећи елемент може тражити по вертикали или хоризонтали. Уколико је, почев од непопуњеног поља, збир цена транспорта изабраних поља са непарним индексом мањи него код поља са парним индексом прелази се на следећи корак, у супротном се тражи нови циклус.▼
Овај почетни распоред не мора бити оптималан. Два поступка за добијање ових распореда су [[метод најмањих цена]] и [[метод северозападног угла]].
По налажењу једног циклуса који одговара горе наведеном правилу, изабире се минимална вредност свих поља која циклус укључује. Ова вредност се потом одузима од свих поља са парним индексом у циклусу а додаје се сваком пољу са непарним индексом. Као што је већ поменуто, непопуњено поље има индекс број 1, а смер даљег нумерисања није битан јер је број изабраних поља увек паран.▼
▲Након овога следи итеративни поступак оптимизације укупне цене транспорта. У матрици се тражи циклус који садржи тачно једно празно поље и непаран број
▲По налажењу једног циклуса који одговара горе наведеном правилу о сумама вредности својих чланова, изабире се минимална вредност свих поља која циклус укључује. Ова вредност се потом одузима од свих поља са парним индексом у циклусу а додаје се сваком пољу са непарним индексом. Као што је већ поменуто, непопуњено поље има индекс број 1, а смер даљег нумерисања није битан јер је број изабраних поља увек паран.
Кад се количина испоручене робе у неком пољу анулира, у том пољу остаје број нула и оно се не рачуна као непопуњено. Процес тражења циклуса и модификовања бројева у њему се понавља докле год постоје циклуси који задовољавају наведене услове.
| |||