Решаване на транспортни задачи по метода на потенциалите
Транспортният проблем на линейното програмиране сега се използва широко в теоретичната обработка и практическото приложение в транспорта и индустрията. Той е от особено значение за рационализирането на производството на най-важните видове промишлени и селскостопански продукти, както и за оптималното планиране на товарните потоци и работата на различни видове транспорт.
В допълнение, много други проблеми с линейното програмиране, като проблеми с присвояване, мрежа и планиране, се свеждат до проблеми от транспортен тип.
Формалният признак на транспортния проблем е, че всяка променлива е включена само в две ограничения и с коефициенти, равни на единица. Ако в този случай критерият за оптималност (сума на разходите, общ пробег) е пряко пропорционален на стойностите на променливите (потоците на трафика), възниква линеен транспортен проблем. В други случаи се разглежда нелинеен транспортен проблем, който може да бъде решен с други методи.
Методът на потенциалите, първият точен метод за решаване на транспортен проблем, е предложен през 1949 г. от L.V. Канторович и М. К. Гавурин. По същество този метод е усъвършенстване на метода за последователно подобряване на плана, приложен към транспортен проблем. Той обаче беше представен извън общите методи на линейното програмиране. Малко по-късно подобен алгоритъм е разработен от Данциг, който изхожда от общите идеи на линейното програмиране. В американската литература методът на потенциалите се нарича модифициран метод на разпределение. Методът на потенциалите позволява, като се започне от някакъв основен транспортен план, да се конструира решение на транспортния проблем в краен брой итерации (стъпки).
Целкурсова работа:
Овладейте математическата формулировка на решението на транспортната задача по метода на потенциалите.
Теоретични основи на метода
Методът на потенциалите позволява, като се започне от някакъв основен транспортен план, да се конструира решение на транспортния проблем в краен брой итерации (стъпки). Общата схема на отделна итерация е следната. Съгласно този основен план на всеки елемент от задачата се присвоява номер, наречен предварителен потенциал. Предварителните потенциали са избрани така, че тяхната разлика за всяка двойка точки
Ако разликата в предварителните потенциали за всяка двойка точки
В противен случай е посочен метод за получаване на нова базова линия, свързана с по-ниски транспортни разходи. След краен брой итерации, процесът на решаване завършва с изграждането на оптимален план и система от потенциални проблеми.
Преди да започнем подробно разглеждане на метода на потенциалите, естествено е да се върнем към концепцията за потенциал.
Функцията W, дефинирана върху множеството точки на производство и потребление на задача T, се нарича вектор на потенциалите или просто потенциалът на тази задача, ако
за всички X-съществени елементи на някакъв план X. Наричаме план X потенциален, ако съществува потенциал на проблема T, свързан с този план чрез условие (1.2). Съществува тясна връзка между оптималността и потенциалността на плановете на проблем T. За да бъде планът X оптимален, неговият потенциал е необходим и достатъчен.
Обърнете внимание, че потенциалът изобщо не трябва да се счита за зависим от конкретен оптимален дизайн на проблем T. Всеки потенциал на проблем T е свързан чрез условие (1.2) с който и да е от неговите оптимални дизайни (естествено, това твърдение има нетривиално значение само за транспортни проблеми с неуникално решение).Следователно функцията W може да се дефинира и по следния начин: W е потенциалът на задача T if
Спомнете си, че стойностите на потенциала W в точките на проблема T се наричат потенциали на тези точки. Изборът на този термин може да бъде обоснован със следната аналогия.
Представете си, че трябва да се пренесе определена единица маса от точка
Тогава произведената в този случай работа А се изчислява по формулата
Използвайки сега свойствата на потенциала на задача Т, имаме
Потенциалният метод се състои от краен брой итерации от един и същи тип. Всяка итерация е разделена на два етапа. На първия етап планът, получен в резултат на предишни итерации, се проверява за оптималност. Ако планът се окаже решението на проблема, процесът приключва. Ако това не е така, се извършва преход към втори етап. На втория етап се изгражда нов транспортен план, който в неизродения случай е свързан с по-ниски транспортни разходи.
Нека опишем отделна итерация на метода, като първо се ограничим до неизродения случай. И така, нека приемем, че k итерации на потенциалния метод вече са извършени и в резултат на това е получен референтен план