Транспортна задача - да се научите как да се свържете!
оптимален метод за програмиране се използва за решаване на икономическите и технико-икономически цели, като например организирането на рационална специализация и коопериране на предприятията, най-добрите индустрии за индустриални отношения и зони, основана на науката териториалното разпределение на общественото производство и др.
Отделна зона в оптимално програмиране е посоката на комбиниране на проучването на различни технически и икономически проблеми на използване на капацитета, рационално рязане на материали, най-изгодно място на съхранение на материали, депото, прикрепването на потребителите на доставчиците, и така нататък. Н.
Най-общия въпрос за тези проблеми е въпросът за това как да използвате най-добре наличните ресурси, как да ги разпределя по резултат да се получи максимален ефект.
Оптимално планиране е метод за решаване на икономически проблеми, което позволява да се извърши най-рационално, оптимално разпределение на ресурсите.
Сред проблемите на оптимално планиране най-пълно, разработени и прилагани на практика, е проблем на транспорта, същността на която се намира в начина, по който хомогенни продукти (пясък, чакъл, цимент, тухли и др. Г.), който се намира в Пунта заминаване (складове, кариери, фабрики ), разпределени между потребителите (строителни обекти, производствени предприятия). на сумата от разходите за транспорт на стоки и общата пробег (тонкилометри) ще бъде минимално.
Има различни начини за решаване на проблема транспорт: потенциален метод, което позволява на термини, метода на диференциалната рента, симплекс методи и др.
Целта на тази лаборатория работа е практическото развитие на един от методите за решаване на проблема с транспорта - потенциала на метода. Тази програма ще ви помогне - физическо лице, интерактивен и симулатор за обучение - ". Идиот"
1. Отчет за проблема с транспортирането.
В М точки напускането на хомогенна доставка на концентриран продукт
Количество (1). и (2). и (т) единици на продукта трябва да разпространяват N в потребителите количество: (1). в (20). в (N) единици. Да означим всяка една от претенциите произход (доставчик) през A (I). и дестинацията (потребителите) чрез B (J). Транспортни разходи на единица продукция от I-ти точката на произход до местоназначението -ty J - С (у) (Таблица 1).
Количеството на продуктите, транспортирани от I-ия отправна точка до местоназначението J -ty равно X (Ig)
транспортиране план. В общия случай.
Задачата е да се определи количеството на продукта X (I, J). транспортирани по всички маршрути (I, к), при спазване на минимума от общите разходи за транспорт.
Математическият формулирането на проблема или обективната функция
С = # 931; # 931; C (I, й) X (I, J) = мин
Гранични условия за този проблем са както следва:
1) общата сума на доставки от всички доставчици М А (I) за употреба В (J) трябва да бъде равна на нуждите му т. Е.
2) общия обем на захранване с (I) всички потребители на N-те доставчик трябва да са равни на присъствието си от доставчик т. Е.
3) обема на трафика, не трябва да бъде отрицателен. т. е.
Допълнително условие: общите ресурси на доставчици са общи нужди (средства) на потребителите.
Задачите, които отговарят на това условие, се отнасят до затворен тип, а ако не - да се отвори.
Open задача винаги могат да се държат затворени с въвеждането на фиктивен доставчик (потребител) с фиктивен марж (изискване) и не-цена транспорт.
Проблемът за транспорт се редуцира до решаване система М + п линейни уравнения линейното програмиране с М * п променливи.
транспортна схема е оптимална, ако е предвидено пълно търсенето и предлагането се получава при минимална цена от изпълнението на обема на трафика. Индикатори за критерия за оптималност при такива проблеми е цената на транспорта на тези продукти. В някои случаи, транспорт разстояние може да се използва като критерий.
2. Решението транспортен проблем с потенциал
Решението, с потенциален проблем се състои от два последователни етапа:
1) осигуряване на база (начална), първоначалния план на транспорт;
2): съответства на подобрение план основа на оптимума.
2.1. Изграждане на основния план от северозападния ъгъл. (По диагонал метод)
Предимството на този метод е неговата строг формализация, липсата на - е далеч от оптималното основния план, което увеличава броя на повторения (Таблица 2)
Попълване на основния план на матрицата започва с горния ляв клетката (северозапад). Той сравнява количеството (марж) и продавача (1) изискването за потребителите в (1). Най-малкият от тези стойности се приема стойността на доставчика транспорт А (1) за контрол на потребителя (1) и е писано в клетката (1,1). т. е.
Изграждане на основния план от северозападния ъгъл
Bold - обемите на доставка
Обичайна - запълване на ред.
Трудността за решаване на проблема, се определя до голяма степен от рационалното изграждане на основния план, това зависи от броя на стъпките (повторения), необходими за оптималното решение.
А марж (1) и в необходимостта от (1) намалява със стойност X на превоз (1,1). В резултат на това в матрични клетки показват, или за която А (1) = 0 или V (1) = 0. Тези клетки не се броят (зачеркнато) в следващия план за застрояване. След това, позицията на следващите северозападните клетки и пълненето се извършва, по метода, описан по-горе.
Основният план ще бъде построен, ако:
2.2. Изграждане на основния план с по-ниска цена.
Този метод се използва за основен план близо до оптималното. Във всички клетки на матрицата (в най-добрите си десен ъгъл) направени разходи за превоз на единица товар-тото доставчик к к-, че потребителя.
За разлика от метода на северозападния ъгъл на плана на база строителство започва с пълнене на клетката с най-ниска цена, и всички операции, свързани с тях не могат да бъдат разграничени от методите, описани северозападна ъгъл.
Изграждане на основния план с по-ниска цена.
В центъра на клетката - обемът на доставките,
В долните краища - последователността на пълнене,
В горните ъгли - разходите за транспорт.
2.3.Proverka и настройка на основния план.
Методът на потенциали, както и редица други методи на линейното програмиране изисква основния план и всички следващи версии отговарят на условията:
1) броя на стойности X (I, J), различен от нула (попълнено матрични клетки), трябва да отговаря на условието:
2), напълнена с основна клетка матрица трябва да бъдат разположени така, че да се осигури тяхното взаимно свързване, а именно във всеки ред има най-малко една основна клетка, която е в колона, в която има най-малко една основна клетка. Това позволява на основните клетки на сухожилие, че е необходимо да се обърне внимание на потенциалния проблем на метода;
3) Основният план не трябва да съдържа всички затворени контури, т. Е. Ако се движат от матрицата, като се започне с основна или клетки и да се превръща в основните клетки, така че е невъзможно да се върне към първоначалната клетка.
Ако не първото условие, т. Е. на N В този случай, броят на основните клетки се предоставя в съответствие с първото условие чрез зареждане на необходимото количество "празни" ( "свободни") клетъчни доставки нула [X (у) = 0]. че в следващите изчисления ще се счита заредени (основни фиктивни клетки). Местоположение на сляпо клетки трябва да отговарят на условията, посочени по-горе (претенция 2 и 3). 3.Optimizatsiya планират потенциал метод. Оптимизиране транспорт план чрез многократно извършване на определен брой стъпки, всяка от които се състои от три стъпки: I. Изчисляване на потенциали, II. инспекционен план за оптималност; III. преразпределение на доставките. Когато има оптимален план транспортни номера система, състояща се от изграждане на доставчици (редове) U (и) и на потребителите потенциали (колони) V (й). което отговаря едновременно на следните две отношения: 1) за основните заредени клетки [X (I, J)> 0] 2) за ненатоварени (свободни) клетки [X (I, к) = 0] От това следва, че ако такава система е потенциален U (и) и V (й) съществува, тогава оптималната план, а ако няма такава система, това не е най-добрият план. 3.1. ИЗЧИСЛЯВАНЕ НА потенциал. Възможностите са изчислени на предположението, че планът оценява (например база) е оптимално. След това, потенциала на линии U (I) и колона V (J) са основни (заредени) клетки при използване на състоянието (3). В този предварително Предполага се, че една от възможностите или U (I). или V (к) се приема, равно на 0 (раздел. 4) Оценка и подбор на оптимални план обещава клетките. В клетка левия ъгъл - клетъчни потенциали; Под прав ъгъл - разходите за транспорт; подпише> отбелязани клетки, чиито потенциали са по-големи от разходите, знакът ### проспективно клетката. 3.3. Преразпределение на обема на доставките. (План за подобрение) Ако планът не е оптимално, е необходимо да я подобрим, за да разпространявате обемите на доставките, така че общата стойност на доставките е намалял. Преразпределение на обеми в следния ред: I. 1) определя от "обещаващ" клетка - една празна клетка, за които разликата между потенциала на клетките, P (I, J) и неговата стойност C (I, J) е най-високата (Таблица 5) II. 2) планирано преразпределение цикъл - един порочен ред. който започва и завършва с "перспектива" клетка, и неговите краища са разположени на заредени клетки (Таблица 6). III. 3) всички клетки ъглово цикъл трансфер са възложени променлив + и - признаци. като се започне с "обещаващи", който винаги се използва знака +; ако ъглов ISCED назначен право; във всеки ред и колона номер на ъгловото клетката с + ще е равен на броя на клетките със знака -; IV. 4) минимум на доставките на негативни клетки се добавя или изважда от обема на ъглови клетъчни според техния знак. В. В резултат на това преразпределение превръща нов и подобрен план, и поставяне на пълни клетки варира дължи на факта, че "дългосрочно" клетка става пълни, и изпълнен ъглов - е свободен (Таблица 6). Получената тествани за оптималност начин план описано по-горе.