Икономическо-математически методи
При тези условия е необходимо да се определи директно план за доставяне на зърно от производствени пункта до асансьорите, при които всички продавачи са взели наличната зърно до зърно асансьори, силози капацитет ще бъде напълно заредена, а общата стойност на разходите за транспортиране на зърно ще бъде минимално.
Задачата може лесно да бъде намален до т.нар една стока (зърно) класически транспортни модели, за които съществуват решения много методи, една от които е описано по-долу.
Официалното изявление и математически нотация zadachi.Dano:
m - брой производствени точки (I = 1,2 м.);
п - номер на потребление точки (J = 1,2 н.);
AI - количество на продукцията в I-ти точката (I = 1,2 м.);
BJ - търсене разтворител за продукти в J-ти параграф (J = 1,2 н.);
ЦНЖ - разходите за пряко производствена единица доставя-тото позиция в производството на J-ти точка на потреблението.
Искаш ли да се намери план директни доставки, при които общите транспортни разходи ще бъдат минимални.
Нека Hij чрез доставка от производителя до потребителя й -та -тата.
Очевидно е, че проблемът се свежда до намиране на стойностите на Hij, осигуряване на минимална обща цена:
Да предположим, че има баланс между търсенето и предлагането:
След това ограниченията на задачите могат да бъдат написани като:
Ако се наруши баланса (3.2). Можете да въведете допълнителни обеми фиктивни производител или потребителски разлики производството и потреблението, определяне на стойността на общуването с него нула.
За разлика от общите линейни програмни ограничения на транспорта в съответствие проблем много планове е ограничен и поради това, този проблем е винаги решими.
Имайте предвид, че m + п ограничения (3,3) - (3,4) са линейно зависими, и един от тях може да бъде пренебрегнато. Съответно, план позоваване транспорт проблем не може да съдържа повече от М + М-1 положителни компоненти. Програмите за подпомагане, които съставляват по-малко от положителния м + N-1. Те призоваха дегенерат.
3.2. Решение от Дж Данциг
След проверка на затворения модел (баланс на съвкупното търсене и предлагане), се пристъпи към избора на програмата за първоначална подкрепа. Ръководейки се от правилото: на следващия избрания маршрут зададете максималната допустима транспорт. по този начин се изчерпва способността на доставчика или на потребителя.
Същността на един от методите за търсене на програмата за първоначална подкрепа - метод северозападния ъгъл. Започваме с "северозападния ъгъл на" "шахматна дъска", т.е. клетки с (1,1) и да X11 = минути (a1, Ь1) = мин (5,5) = 5 (максималния възможен превоз със съответните търсенето и предлагането). Очевидно е, че когато X12 = Х13 = X14 = 0 и Х21 = X31 = 0. Вземете северозападния ъгъл на матрицата от изключени реда и колоната, т.е. клетки (2,2), и да намерят Х22 = минути (а2, b2) = минути (8,5) = 5. Очевидно е, че когато X32 = 0. След това ние се стремим X23 = минути (а2 -X22, b3) = мин (8-5,5) = 3 и Х24 = 0. Тъй като броят на висящите само един ред компонент на плана, реда за подбор не е от значение и за получаване на стойностите X33 и X34.
Според тази теорема, в случай на оптимални планове във всяка двойка двойно условие Xij аз 0, UI + VJ £ ЦНЖ> условие, строгото неравенство, са изпълнени толкова строги равенство подходящи условия.
Съответно, оптималност е формулиран, както следва: валиден транспорт план, и едва след това е оптимална при всяка позиция на производството и потреблението може да бъде свързана с оценка (двойна променливи), следните две условия:- брой гласове производствени точки (ПИ) и потребление (VJ), между които планираната транспорт е единичната цена на превоз продукт (ЦНЖ) между тези точки, т.е.
С помощта на формулираната теста оптималност може да провери не само за оптималност всеки валиден план, но в случай на откази точка метод за подобряване на плана.
Позовавайки се на примера, който се обмисля:
Критерият за оптималност на проблема (D у = UI + VJ -Cij J 0) не е изпълнено; Ето защо, не намери оптимален вариант и е препоръчително да се отиде до другия в подкрепа на плана. по-близо до оптимума.
D ий Отрицателните стойности показват, че превоз според указанията неблагоприятни (за всяка единица на транспортируемия продукт може да претърпят загуби, в сравнение с предходния референтен план, за IJ на количество D). В клетки, където D у> 0. Обратно, ефектът може да бъде получена в D IJ на количество на транспортната единица.
В нашия пример, една такава клетка 34 D = 2. Определяне на обема на предлагането в клетката, трябва да се ръководи от следните съображения:
· Въвеждане в това някаква сума на транспорта трябва да се изважда едно и също количество от други заети клетки, да не се нарушава съотношението на баланса, внос и износ;
· Броят на клетките, включени в новия транспортен план, следва да остане непроменен (един по-малко от общия брой на доставчици и клиенти). Ето защо, вместо клетки слезе един от предишния план за придвижване на клетките трябва да бъдат изключени.
И двете състояния са лесни за извършване, ако доставките да извърши преразпределение на "затворен цикъл".
Нека обемът на новото предлагане е Q> 0. Влезте «- Q» етикет на клетката, от която ще бъде приспадната от стойността на преразпределя знак доставка «+ Q» - напротив. Желана стойност преразпределя доставка определи минималната стойност на застанал клетки със знака "минус".
Тъй като всички стойности на D у nonpositive да отстоява намери оптимален план. В сравнение с първите модели-разходи са намалени от 4 единици (L (Х0) = 75 ® L (X1) = 71).
Между другото, ако намери оптимално план ще покаже D у нулева стойност за всички "незаети клетки" (nonground компонент), това показва, че има и други оптимални планове (преход към плана, която е равна на съответния компонент Q. не се придружава от промени в стойността на обективната функция , QD у = 0).
3.3. Модификация на транспортния проблем
Проблемът с назначаването на персонал
Проблемът за намиране на разпределението с максимална обща ефективност води до проблема, характеризираща се с транспорт изискване максимизиране на целевата функция. В процеса на решаване на този проблем е достатъчно, за да изберете най-първоначалната програма за подкрепа на максимална ефективност и постигане на целеви стойности D IJ аз 0.
Проблемът с транспорта в създаването на мрежа
Проблемът възниква, когато транспортната мрежа с междинни възли и ограничения на комуникационни възможности. Тези проблеми са решени с по-сложни техники, като например известната "унгарски метод". въз основа на отношенията на дуалността.
Проблемът с транспорта в критерий време
Тук критерий за оптималност не е свързана с разходите и времето за извършване на комплексна трафик (в случай на авария да изпълнява прехвърляне на товари в най-кратък срок, независимо от цената). Тези цели са постигнати чрез отново определяне на двойна проблема включващи търсене алгоритъм "максимален поток в транспортни мрежи" (същия алгоритъм се използва в споменатата унгарски Метод) [1].
Тази задача група застъпва един вид продължение на транспортирането възникне проблем при определянето на средствата по вид на работа, когато се определят средства за маршрутите, при подготовката на енергийни баланси, при планирането на военни операции с най-голямо поражение на целите в разпределението на поръчките между фирми и така нататък. Н.
Един пример за един от тези проблеми е проблемът.
Има м типове превозни средства в количества Ai (I = 1. т). който следва да се посочи п обем маршрути трафик равно Bj (J = 1. п). Оперативни разходи и обема на трафика на един вид машина-тото да й-ти път са ЦНЖ и Lij. Задължително да се намери разпределението с минимални експлоатационни разходи.
Максимална проблем поток
Ние считаме, че транспортната мрежа, в която се подчертава елементи - източници (вода, нефт, газ, автомобили) и мивки (потребители). Всяка дъга (сегмент), свързваща точките и Й. номер картирани dij> 0. нарича дъга пропускателна способност - максималния брой агенти (вода, газ, самолети, автомобили и др ...), които могат да се простират по дъга, съответстваща на единица време. Задължително да се намери максималният поток в мрежата (така че да не се спука тръбата при налягане, движение безопасен режим и т.н.).