Проверка план оптималност nondegenerate еталонен потенциал метод (втори параграф алгоритъм)
1 Всеки доставчика възлага на потенциала и възможностите на всеки клиент.
След това всяка заета клетка ще съответства на уравнение
Тъй като всички заети клетки да бъдат m + п - 1, т.е. един по-малко от броя на потенциали, след това да се намери необходимостта за решаване на система от m + п - 1 уравнения с m + п неизвестни. Системата е линейно зависим и да се намери специално разтвор, един от потенциалната необходимост да се инжектира произволна цифрова стойност, след това останалите потенциали се определя еднозначно. Например, потенциала на редове и колони за първоначална програма за подпомагане намерени в последния пример, методът от минималния елемент на системата определят разтвори
Система зависи линейно, за намиране на един от най-конкретните решения Нека дадем един от цифровата стойност на потенциала, например, след това
За плана за изследване за оптимални настройки за всяка свободна клетка помисли оценка по формулата
;
а) ако всички оценки са положителни, ние открихме, оптимална програма за подкрепа и е уникален;
б) ако, заедно с положителни оценки и е установено, резултат нула, а след това намери референтния план е оптимално, но тя не е единствена;
в) ако оценката на най-малко една свободна клетка е отрицателен, основния план не е оптимално, тя може да се подобри чрез зареждане на клетката. Ако тези клетки са няколко, най-обещаващи за изтеглянето е клетката с най-малко точки. Например, за да има клетка за оценка. Тук най-голям потенциал (проспективно за изтегляне) е клетка.
Преход към nehudshemu програма за подкрепа (в третата точка на алгоритъма)
Подобряване на транспорта план поради изтегляне безплатно клетка с отрицателна оценка на тази за най-обещаващия безплатно клетка изработена затворен цикъл с върхове в натоварени клетки. Върховете на цикъла условно определени значки: безплатно клетъчни - плюс следното, в посока на часовниковата стрелка или обратно на часовниковата стрелка, натоварения клетката - минус следващата - отново плюс, и т.н. На доставките в цикъла клетки с "негативна" най-малко количество товари избран върхове, и се премества от клетките на този цикъл се добавя към предлагането в "положителни" върхове и изважда от доставката до "негативни" върхове, което води до баланс цикъл не е нарушен.
цикъл преобразуване
Като цяло, цикъла на преобразуване е затворен полигон линия, състояща се от връзки, които се пресичат под прав ъгъл. Всяка връзка свързва две линии на клетки (колони). Цикълът включва безплатен клетка, ангажирани друга клетъчния цикъл. Цикълът е винаги четен брой клетки. За безплатна клетка винаги може да се изгради един цикъл.
Ако се образува служители на клетъчния цикъл, планът за превоз не е препратка. Цикълът е изграден само за свободните клетки.
Например, ние намерите безплатни клетки програма първоначална оценка вградена поддръжка последния пример, на метода на минималния елемент. Използването на горните резултати от потенциала на редове и колони, изчисляването на прогнозите за свободни клетки:
Тъй като оценката, беше установено, че планът не е оптимално. Тя може да се подобри чрез зареждане на клетката.
Създаване на цикъла на превръщане спрямо клетката () (вж. Таблица 19).
Свързани статии