Ако проблемът с транспортирането едно от условията
модела на открита процедура. За този проблем има решение, е необходимо да се доведе до затворен тип, т.е. равенството.
Това се прави по следния начин: ако. добавената сляпо потребителското търсене (допълнителна колона показва в таблицата с разпределение), ако. след това добавете фиктивен доставчик с оферта (допълнителен ред ще се появи в таблицата за разпределение). И в двата случая, ставките са определени равни на нула. Допълнителна цел е постигната съгласно същата процедура, както е обсъдено.
Пишем алгоритъм за решаване на проблема транспорт:
1) Проверете ТК модел тип.
2) Изграждане на първоначален референтен план (по какъв начин).
3) Проверете плана за израждането.
4) Проверка план оптималност потенциал метод:
а) определяне на потенциала на системата
(За всички клетки попълнено);
б) проверка на втория условия оптималност
(За всички празни клетки).
5) Отидете на nehudshemu програма за подкрепа (ако е необходимо).
Пример. В складове имат запаси от стоки от същия вид и размер (35; 40; 40; 50), за да бъдат доставени на потребителите. Потребителските нужди определя вектор б (31; 52; 17; 20). разходи матрица за доставка на стоки от и-ти блок на й-ти доставчик на потребителя:
Направете си план за придвижване с минимални транспортни разходи.
Решение. Ние определяме вида на транспортен проблем модел. Общо доставчици мощност: 35 + 40 + 40 + 50 = 165 (празна); Резюме на потребителското търсене: 31 + 52 + 17 + 20 = 120 (елементи).
защото , тогава имаме модел отворен.
Представяме фиктивен потребителското търсене, което е
165 -120 = 45 (елементи).
Тарифи 0. По този начин получаване на модел от затворен тип, m = 4 - брой доставчици, п = 5 - брой на потребителите. Място матрица задача. Ние изграждането на първоначалния план справка от минималния елемент (най-ниска цена).
Броят на клетките попълнено разпределение таблица 8 равен на ранга на R = 8 проблеми матрица, следователно, плана за поддръжка е неособена матрица.
Транспортните разходи, съответната програма за подпомагане:
Ние разглеждаме основния план за оптималност, като се използва методът на потенциали.
Доплащане Таблица 1 колони и редове и потенциал. потенциал система намираме, като се използват първите оптимални условия за доставка на пълни клетки.
От се записва в системата :. , , , , , , , ,
Ние се провери втората условия за оптималност. За всички празни клетки неравенство следва да бъде изпълнен :.
(1: 1) + 1 0 - 5, 0 = -4;
(1; 2) 0 + 2-4 = 0 -2;
(1; 5) 0 - 4 - 0 = 0 -4;
(2; 3) + 3 1 - 5 0 = 1;
(2, 4) 1 + 1-8 = -6 0;
(2, 5) с 1 - 4 - 0 = 0 -4;
(3: 1) 4 + 1-6 = 0 1;
(3, 2) 4 + 2-8 = 0 -2;
(3, 3) 4 + 3-7 0 = 0;
(3, 4) + 1 4 - 10 = 0 -5;
(4: 1) 4 + 0 - 1 5 = 0;
(4; 4) 4 + с 1 - 2 3 = 0.
защото сред свободните клетки има, в който второто условие за оптималност не е спазено, планът не е оптимално.
Направете прехода към nehudshemu програма за подкрепа. Най-перспективните за запълване на клетката (4; 4), тъй като тя отговаря на най-високо положителната оценка
Ние считаме, преразпределението на цикълът на натоварването на клетката.
Избрани за запълване на клетката зададете знак "+", а след това заместник знаци. Сред върховете със знака "-" изберете най-ниското предлагане.
Преразпределяне на доставката на цикъла, като по този начин се пристъпи към нова програма за подкрепа.
Транспортните разходи, съответната програма за подпомагане:
Ние разглеждаме основния план за оптималност. Намираме потенциалната стойност на помощта на първото условие за оптималност. За да се запълни доставката клетка.
Ние се провери втората условия за оптималност. За всички празни клетки неравенство следва да бъде изпълнен :.
Нека пишат на клетките, в които състоянието се нарушават:
(1; 2) 0 + 5-4 = 1 0.
Направете прехода към nehudshemu програма за подкрепа. Най-перспективните за запълване на клетката (1, 2), както е тя отговаря на положителна оценка 1. натоварване Find преразпределение цикъл на клетката.
Броят на клетките попълнено разпределение таблица 8 равна на проблема г = 8 матрица на чин, следователно, програма подкрепа (Табл. 3) не е дегенерат.
Транспортните разходи, съответната програма за подпомагане:
Ние разглеждаме основния план за оптималност.
Намираме потенциалната стойност на помощта на първото условие за оптималност. За да се запълни доставката клетка.
Ние се провери втората условия за оптималност. За всички празни клетки неравенство следва да бъде изпълнен :.
Второ условие за оптималност е изпълнено за всички свободни клетки, така че планът е оптимално.
Най-ниските транспортни разходи.
А :; оптимално разпределение план предлагането е в графика 3.
Задачи за самостоятелна работа.
Направете си план за придвижване с минимални транспортни разходи.
Свързани статии