Определяне на оптималния план на проблема с транспорта - studopediya

Най-често е методът на потенциали.

Теорема. Ако по някаква програма за подпомагане Х * = [х * у] транспортиране проблем и са числа, така че за Xij> 0 и Xij = 0 за всички, тогава X * - оптимално план.

Числата се наричат ​​потенциали, съответно местата на отпътуване и местоназначение.

Тази теорема ни дава възможност да се изгради един алгоритъм за решаване на проблема транспорт:

1. Намерете програма за подкрепа на проблема с транспортирането един от разгледаните по-горе методи.

2. Изчислете потенциални точки на отпътуване и дестинациите, с помощта на връзката:

където ЦНЖ - тарифи, стоящи по пълни клетките на таблицата на условията за транспорт проблемни.

Резултатът е система линейни уравнения, състояща се от (m + п-1) уравнения с (м + н) - неизвестен, т.е. системата е несигурна.

За да го реши, една от променливите, свързани с произволна стойност и последователно намерите останалите неизвестни (например, помислете # 945; 1 = 0)

3. За всички клетки са безплатни # 945; IJ от състоянието:

Ако сред числата # 945; ц не е положителна, т.е. всички # 945; у ≤0 това намерено програма за подпомагане е оптимално.

Ако за някои безплатни клетки # 945; у> 0, планът може да бъде подобрено.

4. Изграждане на подобреният план:

От всички числа # 945; се изисква у> 0vybirayut максимум и полето, съответстващо на тази редица. Това може да стане чрез колоездене цикъл (цикъл)

Ако прекъснатата линия образува линия пресича върха точката на пресичане самостоятелно не е (фиг. В)

Ако програмата за подкрепа е построен правилно, само един цикличен път може да бъде изграден за безплатните клетки.

За да преминете към нова програма за подкрепа, при конструирането на цикличен веригата, е необходимо да се извърши движението на товари в рамките на клетката, свързана кръгъл контур, т.е. приложи промяна цикъл преобразуване

Негови са следните правила:

1. Всяка клетка включени в циклична верига се определя определен знак "+" знак на свободната клетка, докато останалите алтернативно "-", "+".

2. Свободните клетките се прехвърлят от по-малък брой Hij. стоящи по "-" клетки. Един и същ номер се добавя към броя в "плюс" клетките и изважда от цифрите, изправени пред "минус" клетки. В резултат на избрания свободна клетка става зает, и "минус" на клетката, в която имаше минимален брой Hij - безплатно.

При преместване на цикъла на реализация, на броя на заетите клетки трябва да остане постоянна, равна на (m + п-1).

Ако "минус" клетки има две или повече идентични брой Hij. безплатно в една клетка, а останалата част се счита за условно работа с нулев трафик.

При изграждането на програма за подкрепа или в процеса на решаване на проблема може да бъде получена от изроден план. За да се избегне този случай примка. план трябва да доведе до не-дегенеративен, за които празни клетки (за предпочитане с минимални нива на трафика) напълнени произволно малък транспортиране, т.е. поставя в тези клетки, например, броят на E = 0.001, и клетките се считат обикновено се използват. При определяне на цената на транспорта и да вземат в оптималния план E = 0.

3. Superior план отново проверява за оптималност, т.е., преминете към стъпка 2.