Оптимизация на транспортни проблеми

Придобиването на умения за решаване на транспортните проблеми с помощта на екипа на "търсене на решения" и потенциала на метода.

Математически модел на проблема транспорт

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

Точките на която т А1. А2. Am. в която определен брой единици на хомогенни доставчици на продукта ще бъде наричана по-нататък, концентрира се, означен AI (I = 1, 2 М). Този продукт се консумира п точки В1. В2. Bn. който ще бъде наречен на потребителя; консумация означен BJ (к = 1, 2 N). Известни разходи за транспортиране на елементи на продукти от - Ай да сочат Bj. Сий които са еднакви и са показани в матрица транспортни разходи С = (CIJ).

Необходимо е да се направи такава потребителите план прикрепят към доставчици, т.е. транспортиране план, в който всички продуктът е изваден от точки Ай в точки Vj според нуждите, и общата сума на разходите за транспорт ще бъде минимално.

Означаваме количеството продукт, транспортирани от точка до точка Ai Bj. от Hij. Всички променливи Xij. За краткост. Тогава целевата функция на проблема ще бъде:

и ограничения са, както следва:

Условия (11) означава пълно задоволяване на търсенето във всички точки на потребление; Условия (12) определят пълен износ на продукти от всички доставчици.

Необходимо и достатъчно условие за проблема (10) - (12) е състояние на равновесие:

Проблемът за транспорт, което се случва в уравнение (13), наречена затворена и може да бъде решен като линейното програмиране проблем с помощта на симплекс метод.

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

Ако салдото (13) не е изпълнено, тогава границата (11) или (12) има формата на неравенства, като "по-малка или равна на." Проблемът с транспорта в този случай се нарича отворена. За решаване на проблема с отворени транспортни потенциали своя затворен за намаляване на проблема чрез въвеждане или фиктивен потребител, ако състоянието на неравенството ред (12) или фиктивен доставчик - в случая на преминаване към ограниченията на неравенството (11).

Помислете за етапите на метода на потенциали за един затворен проблем с по-подробно. На първо място следва да се отбележи, че при условията на равновесие (13) ранга на системата от линейни уравнения (11) и (12) е равно на m + п - 1. Следователно от общо m х п неизвестни основа неизвестен е m + п - 1. Следователно, за всяко допустимо разпределение изходния (таблица доставка) на матрицата транспорт показано в общ вид на таблица. 6, ще работят точно m + п - 1 клетки, които ще бъдат наречени основните разлика от други свободни клетки. Вицове и клетка ще отбележи диагонала.

Таблица 6 - Matrix транспорт

Етап 1 .Pervonachalnoe осигуряване на потребителите за доставчици. Помислете два метода за получаване на първоначално разпределение (първоначална програма за подкрепа): метод северозападния ъгъл и метода на най-ниска цена. Всеки от тези методи по време на пълнене на клетка, с изключение на последния ред се заличава или само транспорт матрица, или само на колоната; само при попълване последната клетка зачеркната и линията и колоната. Този подход ще гарантира, че основната клетка ще точно m + п - 1. Ако при някои пълнене (не последен), клетките са едновременно изпълнени и доставчика на енергия и на потребителя се заличава, например, само на линията, и празна клетка се напълва в съответната колона толкова наречената "нулева доставка", а след отвод на колоната. За да се идентифицират клетки, обикновено в скоби показва броя на своя ред и колона. В метода на северозападния ъгъл е винаги на първо място се попълва клетка (сред възстановя) стои в горния ляв ъгъл (северозапад) ъгъл на матрицата на трафик. Пример на първоначална разпределение по този метод е показан в таблица. 7: попълнено клетки (1: 1) се заличава и първата колона е запълнена клетки (1, 2) и първия ред се заличава; попълнено клетка (2, 2) се заличава и втората колона; попълнено клетка (2, 3) и втория ред се заличава; попълнено клетка (3, 3) и третата колона се заличава; Накрая, клетката е запълнена с (3: 4) и стреля от последния ред и колона. Брой е m + п-1 клетки заети = 3 + 4-1 = 6. Общата стойност на изпълнението на плана за транспорта ще бъдат:

Таблица 7 - Пример на първоначалния метод разпределение северозападна ъгъл

Недостатък на този метод е, че той игнорира стойностите на елементите на матрицата Сий транспортни разходи, при което, получени по този метод първоначалното разпределение (първата референтна план транспорт) може да бъде достатъчно далеч от оптималното.

В различни модификации на метода на най-малко разходи за запълване на матрица клетки транспортни се извършва със стойностите на ЦНЖ на количества. Така че, в промяната на "двойна Preferences" марки клетки с най-ниски разходи за транспорт на първо място всеки ред и след това всяка колона. Клетките, които имат две марки попълнени на първо място, след това запълване на клетките с маркер и натоварвания на неразпределено данни се записват в необозначени клетки с най-ниска цена. Така две клетки с една и съща стойност на предпочитание клетъчната движение, чрез което по-голямо количество трафик. Заличаване на редовете и колоните се извършва в съответствие с правилата, описани по-горе за запълване на клетките. Пример първоначален метод разпределение на най-ниски разходи за същите входните данни по-горе, представени в таблицата. 8.

Таблица 8 - Пример на първоначалното разпределение на стойности от най

Процедура за попълване на клетките (2, 1), (3, 2), (1, 3), (2, 4), (1, 4), (3, 4). Общата стойност на транспорта, представени в таблица. 3.7, са както следва:

F (X) = 1 * 30 + 2 * 100 + 2 * 40 + 2 * 70 + 3 * 20 + 4 * 20 = 590.

Поради това планът за транспорт е много по-близо до оптимума от плана, изготвен по метода на ъгъла на север-запад.

Стъпка 2: Потвърждаване на получената оптимално транспортиране план. Ние въведат специални показатели UI за всеки транспортен линия на матрицата (всеки оператор), където I = 1, Т, и показатели VJ за всяка колона (всеки потребител), където, J = 1, п. Тези цифри се наричат ​​потенциали на доставчиците и потребителите, че е подходящо да се тълкува като цената на продукта в съответните параграфи от доставчиците и потребителите. Потенциалите са избрани така, че пълни клетки за (I; й) отговарят на уравнение (14). Наборът от уравнения (14), състоящ се от всички напълнени клетки (всички основа неизвестен) образува система от m + п - 1 линейни уравнения с п неизвестни М + интерфейс и VJ. Тази система е винаги съвместим, където един от неизвестен стойност може да се настрои произволно (например, u1 = 0), докато останалите неизвестни стойности са еднозначно от системата.

Помислете за процеса на намиране на потенциала за основата на първоначалното разпределение по метода на северозападния ъгъл, представен в таблица. 7. Чрез определяне u1 = 0 и използване формула (14), напълнена с клетки (1 1) и (1, 2), ние откриваме, v1 = v2 = 4 и 5. Знаейки v2, с пълнеж клетка (2; 2) намираме u2 = 2, и като се знае u2. от пълнеж клетка (2; 3) v3 = 8. намираме Знаейки v3, на завършената клетката (3; 3) намираме U3 = 1, и след това се напълва клетка (3, 4) намираме v4 = 5. Резултатите са показани в таблица. 9, където потенциалните доставчици са дадени в последната колона, както и потенциалните потребители - на последния ред.

Таблица 9 - Определяне на първоначалната база потенциал за метод разпределение северозападния ъгъл на картата

За оценка на оптималното разпределение на всички клетки (I; й) матрица трафик определят от оценката, която е обозначена с dij, съгласно формулата:

Използване на предварително приет тълкуването, изразът може да се тълкува като сбор от цената на продукта от доставчика, както и разходите за транспорт; чрез изваждане на тази сума се сравнява с цената на продукта на съответния потребител VJ. Очевидно е, че оценката на пълни клетки са равни на нула (потребителските цени покрива разходите за доставчика и доставка). По този начин, оптимално разпределение може да се съди по размера на наличната клетките. Ако оценката на свободна клетка е отрицателно, тя може да се тълкува по следния начин: цената, предложена от съответния потребител, икономически размер на доставчика и на разходите за транспорт, т.е. ако клетката е била заета, че би било възможно да се получи допълнителна икономическа изгода. Следователно, разпределението на условието за оптималност е състоянието на не-негативност на безплатни прогнози за трафика на матрица клетки.

Оценките на клетки, съгласно формула (15) е удобно представени под формата на един оценки матрица. За предварително счита разпределението получен чрез ъгъла на северозападна (виж таблица 9 ..), брой на матрица клетка е както следва:

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

(. Таблица 10) за разпределение на стойностите, получени по-малко, броят на матрица клетка е както следва:

Тъй като всички оценки са за отрицателни, а след това не е възможно да се подобри плана за транспортиране, т.е. е оптимално (общите разходи за транспортиране на плана са 590). Освен това, следва да се отбележи, че в този случай оценката на всички налични клетки строго по-големи от нула, т.е. всеки друг план осигуряването на заетост на най-малко един от тези клетки ще бъде по-малко от оптималното. Това предполага, че намери оптималния план е уникален. Наличието на нула оценки на свободните клетки в оптимален план на транспорта, а напротив, показва не-уникалност на оптимален план.

Етап 3. Повишаване неоптимално транспорт план (за преразпределение на цикъла). За да се подобри неоптимално транспорт план, транспортиране избрана клетъчна матрица с отрицателна оценка; ако такива клетки са няколко, обикновено (но не задължително) избрани клетки с най-голям абсолютната стойност на отрицателна оценка. Например, за разпределението представени в таблица. 9, такава клетка може да бъде клетка (1; 3) (виж матрични оценки (16).).

затворена крива се конструира за избраната клетка (верига), началната връх, който се намира в избрана клетка, докато всички други върховете са заети от клетки; при което посоките на отделните дължини на веригата могат да бъдат хоризонтални и вертикални само. Vertex верига с изключение на първия, е заета от клетка, в която сегментите на контур линия образуват ъгъл (не може да се разглежда като върховете, където хоризонталните и вертикалните сегменти контурни пресичат). Очевидно е, че броят на контурни сегменти, като върховете му, е още. Върховете на веригата са подредени последователно знаци "+" и "-" като се започва с знак "+" в избрания свободна клетка. Една проста схема е показан с контурна линия в таблица. 9, въпреки че формата на верига може да бъде доста варира (например контура в таблицата. 12).

количество преразпределя доставката на определена като най-малката от стойностите в върховете на доставките верига със знака "-", и тази стойност се увеличава доставянето на върховете със знака "+" и намаляване на доставката на върховете със знака "-". Това правило гарантира, че веригата не ще върховете отрицателен доставки, първоначално избраната клетка е зает, докато една от клетките използвани в този случай задължително безплатно. Ако стойността на преразпределя доставка е предоставяне на не една, а няколко върха контура със знака "-" (то просто се случва в преразпределението на веригата в Таблица 9.), Това освобождава само една клетка, обикновено с най-висока цена на транспорта, както и всички други такива клетки са заети с нула доставка.

В резултат на тези операции за представени в таблица. 9 разпределение доставка е показано в таблица. 11. Общата стойност на транспорт до по този план

F (X) = 4 * 30 + 5 * 0 + 2 * 30 + 3 * 100 + 7 * 10 + 4 * 110 = 990, което е значително по-малко от предходните суми разходите 1170, въпреки трафик в план на маса. 11 все още не е оптимално. Това се доказва от присъствието на отрицателни стойности в матрицата клетки на промени на плана (UI съответстващ потенциали VJ и е установено метода, описан в описанието на етап 2):

Таблица 11 - Резултати от транспортния проблем чрез решаване възможности на основата на първоначалното разпределение по метода на северозападния ъгъл

Транспортните проблеми в основните условия на трафик, които се срещат заети клетки с нулева доставка (или от първоначалното финансиране, или в процес на повторения) се наричат ​​изродени; пример на този проблем е показано в таблица. 11. В дегенеративен случай съществува риск от транспорт проблеми контур, т.е. безкрайно повторение на повторения (безкрайно изброяване на същите основни комбинации от заети клетки). Като правило, в практическите проблеми на транспорта като колоездене не се случи; Въпреки това, имайте предвид, че има специални правила, за да се измъкнем от примката ако примката все още ще се случи. При липса на потенциален метод за ограничен дегенерация и води до оптимално транспорт план за определен брой стъпки.