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