Решаване на транспортния проблем с правилния баланс
Транспортната задача с правилния баланс е да се намери оптималният план за дадена транспортна маса, при който разходите за транспортиране ще бъдат минимални.
Тази задача е уместна в области, свързани с превоз на товари.
ДЪРЖАВА САРОВСКИ
ФИЗИКО-ТЕХНИЧЕСКИ ИНСТИТУТ
КАТЕДРА ПО МАТЕМАТИЧЕСКИ МЕТОДИ И
ИЗСЛЕДОВАТЕЛСКИ ОПЕРАЦИИ В ИКОНОМИКАТА
Формулиране на проблема. 4
Метод на решение. 5
Програмен език. 7
Описание на алгоритъма. 8
Описание на основните структури от данни. 12
Описание на потребителския интерфейс. 14
Програмен текст.. 18
Задачата е да се намери такъв метод на транспортиране, при който разходите, свързани с транспортирането, ще бъдат минимални.
Този проблем ме заинтригува, защото решението му е пряко свързано с икономии на разходи. Важно е да се намери такъв алгоритъм, който най-оптимално ще реши проблема.
Формулиране на проблема
Транспортната задача се поставя по следния начин: има m отправни точки A1, A2 , . Am , в които запасите от някои еднородни товари са съсредоточени съответно в размер на a1, a2. , съм. Има n дестинации B1 , B2 , . , Кандидатствалите съответно за b1 , b2 . , bnload. Известни разходи Сi,jтранспорт отвсяка отправна точка Ai до всяка крайна точка Bj. Дадени са всички числа Сi,j, образуващи правоъгълна таблица. Необходимо е да се изготви такъв транспортен план (от къде, къде и колко да се достави), така че всички заявки да бъдат изпълнени, а общата цена на целия транспорт да е минимална.
Метод на решение
1. Изготвяне на основен план.
Решаването на транспортния проблем започва с намирането на референтен план. Има различни начини за това. Например методът „северозападен ъгъл“ Помислете за конкретен пример:
Условията на транспортната задача се определят от транспортната таблица.
PN ВКЛ.Ще попълним таблицата с пратки постепенно, започвайки от горната лява клетка („северозападен ъгъл“ на таблицата). В този случай ще аргументираме следното. Точка B1 се прилага за 18 товарни единици. Нека удовлетворим тази заявка за сметка на наличния запас 48 в точка А1 и запишем транспорта 18 в клетка (1,1). След това заявлението по точка Б1 беше удовлетворено и в точка А1 останаха още 30 единици товар. Ще удовлетворим приложението на точка B2 (27 единици) за сметка на тях, ще напишем 27 в клетката (1.2); останалите 3 единици от точка A1 ще бъдат присвоени на точка B3. По прилагането на позиция Б3 са останали неудовлетворени 39 бр. От тях ще покрием 30 за сметка на точка А2, след което нейният запас ще бъде изчерпан и ще вземем още 9 от точка А3. отостаналите 18 единици от позиция А3 12 ще бъдат разпределени към позиция В4; останалите 6 единици ще бъдат причислени към позиция B5, която заедно с всичките 20 единици от позиция A4 ще покрие неговата кандидатура. Това завършва разпределението на запасите; всяка дестинация получи товара според заявката си. Това се изразява в това, че количеството трафик във всеки ред е равно на съответния запас, а в колоната - на приложението. Така веднага изготвихме транспортен план, който отговаря на балансовите условия. Полученото решение е основното решение на транспортната задача:
PN ВКЛ.Транспортният план, който съставихме, не е оптимален по отношение на разходите, тъй като при изграждането му изобщо не взехме предвид разходите за транспорт Сi,j.
2.Разпределителен метод за постигане на оптимален план
Сега нека се опитаме да подобрим плана, съставен по метода "северозападен ъгъл". Да прехвърлим например 18 единици от клетка (1.1) в клетка (2.1) и за да не нарушим баланса, ще прехвърлим същите 18 единици от клетка (2.3) в клетка (1.3). Да вземем нов план. След като изчислим цената на основния план (равнява се на 1039) и цената на новия план (равнява се на 913), лесно се вижда, че цената на новия план е 126 единици по-малко. По този начин, поради цикличната пермутация на 18 единици товар от една клетка в друга, успяхме данамаляване на цената на плана:
PN ВКЛ.Този метод за намаляване на разходите в бъдеще ще се основава на алгоритъма за оптимизиране на транспортния план. В транспортната задача ще наричаме цикъл няколко заети клетки, свързани със затворена прекъсната линия, която прави завой на 90° във всяка клетка.
Има няколко опции за цикъл:
Лесно се вижда, че всеки цикъл има четен брой върхове и следователно четен брой връзки (стрелки). Нека се съгласим да маркираме със знак „+“ тези върхове на цикъла, където транспортът трябва да бъде увеличен, и със знак „-“ тези върхове, където транспортът трябва да бъде намален. Цикъл с маркирани върхове ще се нарича "подписан". Прехвърлянето на определен брой единици товар по посочения цикъл означава увеличаване на транспортирането в положителните върхове на цикъла с този брой единици и намаляване на транспортирането в отрицателните върхове със същото количество. Очевидно, когато произволен брой единици се пренасят през цикъла, балансът между запасите и търсенето не се променя: както преди, сумата от доставките във всеки ред е равна на запасите от този ред, а сумата от доставките във всяка колона е търсенето на тази колона. По този начин, за всеки цикличен трансфер, който оставя транспортите неотрицателни, допустимият планостава в сила. Цената на плана в същото време може да се промени: да се увеличи или намали. Нека наречем цената на цикъла увеличението на разходите за транспорт при преместване на една единица товар през посочения цикъл. Очевидно цената на цикъла е равна на алгебричната сума на разходите във върховете на цикъла, като тези в положителните върхове се вземат със знака „+“, а тези в отрицателните със знака „-“. Върховете се редуват, започвайки с „+“. Нека означим цената на цикъла с g. При преместване на една единица товар през цикъла, цената на транспорта се увеличава със сумата g. При преместване на k единици товар по него, цената на транспорта ще се увеличи с kg. Очевидно, за да се подобри планът, има смисъл да се движи транспорт само през тези цикли, чиято цена е отрицателна. Всеки път, когато успеем да направим такъв ход, цената на плана се намалява със съответното количество кг. Тъй като транспортирането не може да бъде отрицателно, ще използваме само онези цикли, чиито отрицателни върхове лежат в базовите клетки на таблицата, където са разположени положителните транспорти. Ако в таблицата няма повече цикли с отрицателна цена, това означава, че по-нататъшното подобряване на плана е невъзможно, тоест оптималният план е достигнат.
Методът за последователно подобряване на транспортния план се състои в това, че в таблицата се намират цикли с отрицателна цена, транспортът се премества по тях и планът се подобрява, докато не останат цикли с отрицателна цена. Може да се докаже, че за всяка свободна клетка в транспортната таблица винаги съществува цикъл и освен това единственият, един от върховете на който се намира в тази свободна клетка, а всички останали в основните клетки. Ако цената на такъв цикъл, с плюс в свободна клетка, е отрицателна, тогава планът може да бъде подобрен чрез преместване на трафика по този цикъл. Брой единицитоварът k, който може да бъде преместен, се определя от минималната стойност на превозите, стоящи в отрицателните върхове на цикъла (ако преместите повече единици товар, ще има отрицателни превози).