Определяне на оптималния план

12.4. Определяне на оптималната план

Като вземете предвид методите за конструиране на първоначалната програма за подкрепа може да бъде получена дегенерат или програма, които не са изродени подкрепа. Застроена план транспорт проблем, тъй като линейното програмиране проблем могат да бъдат доведени до оптимума, използвайки метода на симплекс. Въпреки това, поради големите размери на симплекс маси, съдържащи млн неизвестен, и голямо количество изчислителна работа по-прости методи, използвани за получаване на оптимален план. Най-често използваният метод на потенциали (модифициран метод разпределение) и метода на диференциални наем.

Методът на потенциали. Общият принцип на определяне на оптималния план на транспорта проблем на този метод е подобен на този на решаване на метод на линейното програмиране проблем симплекс, а именно: на първо място, намери подкрепата на плана проблем на транспорта, и след това тя постепенно се подобрява, докато оптимален план.

Teorema12.2 (оптималност критерий). За да е валиден план за транспорта в проблема с транспортирането е оптимален, ако и само ако съществуват такива числа и. че

Броят и призова потенциалните точки на тръгване и пристигане, съответно.

Тази теорема ни дава възможност да се изгради един алгоритъм за намиране на решения на проблема с транспортирането. Той е както следва. Нека един от най-дискутираните по-горе намери програма за подкрепа методи. За този план, в която М + N - 1, основните клетки могат да бъдат определени потенциал и така, че състоянието (12.4). Тъй като системата (12.4) съдържа М + N - 1 уравнения и m + п неизвестни, един от тях може да бъде произволно избран (например, равна на нула). След това на m + п - 1 уравнения (12.4) и потенциала определя от останалите стойности се изчисляват за всеки от наличните клетки. Ако установите, че. оптималния план. Ако поне един празен клетка. планът не е оптимално и може да се подобри чрез прехвърляне на цикъла съответстващ на тази клетка-безплатно.

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

план за подобряване на процес продължава толкова дълго, колкото са изпълнени условията (12.5).

Пример. На три бази влезе хомогенна товари, което е необходимо за извършване на четири дестинация. Тарифи за трафика, акции и изисквания са посочени в таблица 12.3. Транспорт план, така че общата им стойност е минимална.