Като критерий за оптималност на транспортните превози. Критерий за оптималност на основното решение на транспортната задача. Методи за намиране на оптимално решение. Какви проблеми решава?

08.04.2024

Изборът на критерий зависи от: естеството на проблема, наличната информация и необходимата точност при намиране на оптимума.
Примери за локален критерий за оптималност за транспортен проблем включват:
а) критерий за минимален общ пробег (подходящ само за решаване на затворени транспортни задачи в рамките на един вид транспорт);
б) при оптимизиране на транспорта в рамките на една година, обичайният критерий за разходите е сумата от зависимите намалени разходи:
C = Ezav + Eper + Ep (K ps + C gr),
където Ezav е оперативните разходи, зависещи от трафика,
Kps - капиталови инвестиции в подвижен състав,
Cgr - цената на стоките в транзит,
Eper - разходи за претоварване;
в) при изготвянето на оптимални транспортни схеми за бъдещето е възможно да се увеличи капацитетът на линиите в зависимост от разположението на оптималните товарни потоци върху тях. Следователно критерият за оптималност взема предвид:
Kpost - разходи за необходимото развитие на пропускателна способност за постоянни устройства,
Enez - независими оперативни разходи.
Тогава
C = Ezav + Enez + Ep (Kps + Kpost + Cgr);
477
г) в някои случаи при решаване на отворени транспортни проблеми е разрешено да се използва като критерий сумата от производствените разходи и тарифните такси за транспорт;
д) при определени задачи за оптимизиране на спешни превози критерият е времето: тончасове (автомобилни часове) товар в процес на транспортиране или общото време за извършване на определена транспортна операция.
От многото методи за решаване на матрични проблеми най-често срещаните са: потенциалният метод (Л. А. Канторович и М. В. Говурин) и методът на условно оптималните планове (А. Л. Лури).
Методът на условно оптималните планове се отнася до методите за намаляване на остатъците:
в първоначалната версия се допуска нарушение на основните ограничения на транспортната задача
X Xij = Bj (j = 1, 2, ... l); X Xij = Ai (i = 1, 2, ... m);
аз дж
възникналите несъответствия и дисбаланси се отстраняват чрез извършване на редица промени.
Основните етапи на метода на условно оптималните планове могат да бъдат разгледани на примера на определен транспортен проблем (виж таблица 17.1), който изисква свързване на ресурсите на три доставчици A1, A2, A3 (редове на таблица 17.1) с нуждите на четири консуматора B1^B4 (колони на табл. .17.1). В горните десни ъгли на клетките на матрицата са показани разходите за транспортиране на Su за единица товар от доставчика и потребителя Bj - оптималното решение ще бъде получено в четири етапа на решение, които се наричат приближения на проблема и също са показани в табл. 17.1.
Пример за решаване на матричен транспортен проблем с помощта на метода на условно оптималните планове Приблизително число Доставчик и Потребител и неговата нужда, Bj Количество оферти Дисбаланси L, - неговият ресурс, LI B 7 B2 9 B3 9 B4 5 ^xij J J A1 10 10 /12 7 12/14 9 9/11 15/17 5 21 -11 1 A2 10 1 14
G 20 8 9 50 9 +1 A3 10 12 15 20 25 0 +10 Aj 12-10=2 15-12=3 - 25-15=10 A1 10 12/13 4/15 9 11/12 17/18 5 14 -4 2 A2 10 14 1 20 8 9 50 9 +1 A3 10 12 7 15 20 25 7 +3 Aj - 1 - 8 A1 10 i ^ 13/15 5/17 6 2/14 8/20 5 11 - 1 3 A2 10 14 1 20 8 9 50 9 +1 A3 10 2/14 7 15/17
3 20/22 25/27 10 -0 Aj 14-12=2 20-15=5 - 50-18=32 Aj 10 15 17 5 14 20 5 10 +0 4 A2 10 14 1 20 8 9 50 10 +0 A3 10 14
6 17 4 22 27 10 +0
Всеки етап от решението се състои от 9 стъпки (точки). 1. Изграждане на първоначалната версия.
В колони 3-6 на матрицата (Таблица 17.1) има клетка с минимална цена:
Сkj = min Cjj.
В тази клетка се въвежда доставка, равна на общото изискване на колоната:
Xkj = BJ.
Ако има няколко клетки с минимални разходи, доставката на Bj се разпределя между тях на случаен принцип.
В табл 17.1 за първата, втората и четвъртата колона минималните стойности се намират в първия ред (10, 12, 15), за третата колона - във втората (8).
Определяне на количествата на доставките и остатъците.
Количеството на доставките за всяка линия Z Xij и разликите между
Дж
ресурси на доставчика и предвидени доставки:
RI = 4 -z XIJ.
й
Разликите Rj се наричат остатъци или дисбаланси. И така, в таблицата, в приближение № 1, дисбалансите са показани в последната колона и са равни за трима доставчика, съответно -11, +1, +10.
Проверка за отрицателни дисбаланси.
Липсата на отрицателни дисбаланси показва оптималността на намереното решение. В приближение № 1 табл. 17.1, първият ред има отрицателен дисбаланс от -11, така че търсенето на оптималното решение ще продължи.
Класификация на низовете.
Ред i се счита за абсолютно недостатъчен, ако дисбалансът му е отрицателен, и за абсолютно излишен, ако дисбалансът му е положителен. Когато R = 0, редовете се класифицират на относително излишни и относително недостатъчни според бележката, която ще бъде посочена по-долу. В приближение № 1 (Таблица 17.1) 1-ви ред е абсолютно недостатъчен, 2-ри и 3-ти ред са абсолютно излишни.
Трансформация на матрицата на разходите. Включва следните действия:
а) във всяка колона, която има предлагане в недостатъчен ред, се намира минимумът на разходите в пресечната точка с излишните редове:
С rj = min Cj;
I gU
където U е множеството от абсолютно и относително излишни низове.
Например, в приближение № 1 в първата колона, най-ниската цена в излишните редове е:
С r1 = min (14, 12) = 12.
Във 2-ра колона най-ниската цена за излишни редове е Cr2 = min (20, 15), в 4-та колона - Cr4 = min (50, 25) = 25. В 3-та колона Cr1 min за излишни редове не се определя , тъй като тази колона няма доставка в единствения недостатъчен 1-ви ред;
б) във всяка колона, която има запас в недостатъчен ред, се определя разликата между минималната цена за излишните редове и минималната цена за колоната като цяло:
A j = C rj - C kj .
Стойността на Aj се записва в спомагателния ред (ред j в таблица 17.1).
Например в приближение № 1 в 1-ва колона Aj = 12-10 = 2, във 2-ра Aj = 15- = 12 = 3, в 4-та колона Aj = 15-15 = 10. В 3-та колона стойността на A3 не е дефиниран, тъй като доставката е в резервна линия;
в) намерете най-малката стойност от всички Aj:
A = min Aj, което се добавя за всички разходи във всички недостатъчни редове.
И така, за приближение № 1 получаваме:
A = min (2, 3, 10) = 2.
Всички стойности в недостатъчния 1-ви ред се увеличават с A = 2, в останалите не се променят. Стойностите на разходите на този етап от решението се показват като дроб в горния десен ъгъл на клетките в недостатъчните редове, а в числителя на фракцията - първоначалната стойност на разходите, в знаменателя - актуализирана в съответствие с стъпка 5 от алгоритъма за решаване на проблема.
6. Намиране на връзки на редове, възникнали в резултат на трансформацията на стойностите в стъпка 5.
Низът S се счита за свързан с низа t, ако са изпълнени 2 условия:
а) в някаква колона d има съвпадение на стойности
С sd = Ctd;
б) има захранване в клетка sd
Xsd > 0.
481
При тези условия има насочена връзка между клетките:
sd^td.
Когато извършвате ръчни изчисления, е удобно да показвате връзки със стрелки върху матрицата.
Значението на концепцията за низова връзка е следното. В разглеждания метод матричните клетки с минимални стойности на колоните са приемливи за доставки. След промяна на разходите в матрицата се появява нова валидна клетка (понякога няколко), в която може да се прехвърли част от доставката от недостатъчната линия.
Връзката на линията показва възможната посока на трансфер на доставка. По този начин, в приближение № 1, след промяна на стойностите в 1-ви ред, клетка 3.1 стана валидна. Това означава, че е възможно да се прехвърли доставката от клетка 1.1 към клетка 3.1, т.е. наличието на връзка между тези линии.
Намиране на последователност (верига) от връзки между абсолютно недостатъчни и всякакви излишни низове.
Една верига може да се състои от една или повече връзки и се появява след завършване на стъпка 6. Тя винаги включва новосформирана връзка в тази точка, от която е удобно да се търси веригата.
Например в приближение № 3 се появи нова връзка между клетки 3.1 и 2.1; от предишния цикъл (апроксимация), връзката между клетки 1.2 и 3.2 остава. Веригата от абсолютно недостатъчния 1-ви ред до излишния 2-ри ред минава през клетки 1.2-3.2 и 3.1-2.1. В приближение № 1 веригата се състои само от една връзка 1.1-3.1, тъй като тази връзка започва в абсолютно недостатъчна линия и завършва в излишна линия.
Определяне на количеството на прехвърляне на доставките AX, извършено едновременно по всички звена на намерената верига.
Тази стойност е равна на най-малкото от следните числа:
абсолютната стойност на дисбаланса в недостатъчната линия, където започва веригата;
дисбаланс в излишната линия, където веригата завършва;
стойността на доставките във всички клетки, където започват връзките, включени във веригата:
LF
х
AX = мин
/R/. Р
начало край
LF
където Xij са запаси в нечетни клетки на веригата, ако са пренаписани по ред от липсващия ред до излишния,
^начало, ^край, са несъответствия в редовете, където започва и завършва веригата за трансфер на доставка.
Например количеството на трансфера по веригата, намерено в приближение № 1, е равно на
AX = min (11, 10, 7) = 7 и според веригата, намерена в приближение № 3 -
AX = min (1,1,6,7) = 1.
9. Прехвърляне на консумативи.
Намерената стойност на AX се изважда от запасите във всички нечетни клетки на веригата и се добавя към запасите във всички четни. Резултатът е нова версия на плана, или оптимална, или с по-малък абсолютен размер на отрицателните дисбаланси от предишната версия. След това методът на условно оптималните планове включва преминаване към стъпка 2 и циклично продължаване на стъпките на алгоритъма, докато не се открие в момента, че вече няма отрицателни дисбаланси и намереното решение е оптимално.
По този начин, в приближение № 1, 7 единици доставки се прехвърлят от клетка 1.1 към клетка 3.1 и се осъществява преходът към приближение № 2.
Когато се изпълнява стъпка 9, в приближение № 2, 3 захранващи единици се прехвърлят от клетка 1.2 към клетка 3.2 и се осъществява преход към приближение № 3. В приближение № 3 захранващите единици се прехвърлят от клетка 1.2 към клетка 3.2 и от клетка 3.1 до клетка 2.1. Полученото приближение № 4, след проверка на стъпка 3 от алгоритъма за решение, се оказва оптимално.
Решаването на матричен транспортен проблем с помощта на компютри дава възможност да се използва друга версия на метода на условно оптималните планове - алгоритъмът за диференциална рента, при който не се извършват прехвърляния на доставки по връзки, а вместо това при всеки изчислителен цикъл всички доставки се разпределят отново в приемливи клетки (с най-ниските разходи в колоната, като се вземат предвид направените преди това промени в разходите).
За решаване на проблеми с мрежовия транспорт широко се използва потенциалният метод, който се основава на свойството потенциалност на оптималния план.
Нека има някаква схема на потоци от хомогенен ресурс (товар, празни автомобили) по транспортна мрежа с ограничен капацитет на връзките. Капацитетът на връзката r-s в посока към s ще бъде означен с drs. Всички връзки, в зависимост от наличието на поток x^ на даден товар, се разделят на три категории:
основни с конци
празен без потока на този товар xrs=0;
наситен xrs=drs.
Разглежда се проблем с един продукт.
В проблем с множество продукти връзките със сумата от потоците на всички стоки, равна на пропускателната способност, са наситени.
Ако диаграмата на потока е оптимална, на всички върхове на мрежата могат да бъдат присвоени потенциали U, които отговарят на следните условия:
за основни връзки Us - Ur = Crs, (17.7)
където Crs е разстоянието или цената (в зависимост от използвания критерий) за транспортиране на единица товар от r до s;
за празни връзки Us - Ur за наситени връзки Us - Ur > Crs.
Равенството Us - Ur = Crs е приемливо във всички случаи и не противоречи на оптималността на схемата. Нарушаване на условия (17.7) и (17.8), т.е. Us - Ur> Crs за празна връзка и Us - Ur При решаване на мрежов проблем първо се разработва първоначалната диаграма на потока. След това се извършва циклично изчисление за подобряване на плана. Всеки цикъл включва присвояване на потенциали на върховете, проверка на условията (17.7) и (17.8) и подмяна на диаграмата на потока.
1. Изграждане на първоначалния план.
Първоначалната технологична схема трябва да отговаря на следните изисквания:
а) съответствие с условието за баланс за всички върхове на мрежата:
Z Xks -Z Xrk = Rk;
(доставка) (приемане) + товарене разтоварване
б) не превишаване на пропускателната способност на връзките, поток Xrs в) липса на затворени контури, образувани от основни връзки с потоци 0 Препоръчително е да се изгради първоначална верига без очевидни нерационалности (случвания, кръгове), което ще намали броя на последващо въведените корекции .
2. Присвояване на потенциали на всички мрежови върхове.
На всеки връх, към който е съседна поне една основна връзка, се приписва произволен потенциал (число от същия ред с най-голям диапазон на транспортиране). След това потенциалите се присвояват на останалите върхове на мрежата, следвайки всички основни връзки и използвайки равенството Us-Ur = Crs. С поток от R^S, на върха S се присвоява потенциала Us=Ur+Crs (където Crs е дължината на връзката). Ако потокът върви от S към R, тогава потенциалът се определя по следната формула: Us=Ur - Crs.
Е -6
В този случай съществуващите основни връзки не са достатъчни, за да присвоят потенциали на всички върхове. След това се въвеждат n-1 нулеви потоци, свързващи отделни системи от основни връзки. Връзките с нулеви потоци се считат за основни и се използват за присвояване на потенциали.
485
В процеса на присвояване на потенциали може да бъде открит така нареченият случай на дегенерация: набор (граф) от основни връзки се разпада на n несвързани системи. На фиг. Фигура 17.10 показва две такива системи: B-A-G и D-B-E.
При проблем с ограничения на капацитета компонентите на базовата графа могат да бъдат разделени един от друг не само чрез празни, но и чрез наситени връзки. След това се въвеждат условни резерви с нулев капацитет на някои наситени връзки, които по-нататък се считат за основни.
3. Проверка на спазването на условията (17.7 и 17.8) на всички празни и наситени връзки на мрежата.
280
200
+29
Ако тези условия са изпълнени навсякъде, тогава проблемът е решен и планът е оптимален. Ако има несъответствия, изберете секцията с най-голямо несъответствие и отидете на точка 4. Фигура 17.11 показва първоначалната версия на плана за проблем с мрежов транспорт с ограничения на капацитета на връзката. Върховете на мрежата са присвоени потенциали. Необходима е проверка за празни връзки A-E, E-D и наситени връзки G-D. Останалите връзки са основни. Дължините на връзките в посока „там“ и „назад“ са еднакви.
Условие 17.7 е нарушено при връзка A-E: Ve - Ua = 440 - 220 = 220 > Cae = 200; Nae = 220 - 200 = 20. При връзката G-D е нарушено условие (17.8): Ud - Ur = 330 - 280 = 50 4. Намиране на път по основните връзки между върховете-краища на връзката с несъответствие.
Комбинацията от този път и връзката с несъответствието се нарича контур. За първоначалната версия на фигура 17.11 веригата се състои от връзки G-D, D-G, J-B и B-G. За втория вариант (виж Фиг. 17.12) веригата включва връзки A-E, E-B, V-Zh, Zh-D, D-G, G-A за третия вариант (виж Фиг. 17.13) веригата се състои от връзки B-Z, ZH-B; , V-E, E-A, A-G и G-B.
280
200
+29 240
280
200
По-нататъшните действия зависят от това дали връзката с остатъка е празна или наситена.
Класификация на циркулационните потоци.
a) Посоката на потока по връзката с остатъка се установява от по-нисък към по-висок потенциал;
б) всички други потоци във веригата са разделени на свързани и насрещни потоци към този поток. И така, за първоначалната версия (фиг. 17.11), връзките G-D и B-G са свързани и
D-G и ZH-B са противотокови, във втората версия (фиг. 17.12) връзките A-E, V-Z, ZH-D са свързани, а E-B, D-G и G-A са насрещно свързани, в третия вариант (фиг. 17.13) B-Zh, V-E, A-G преминават, а ZhB, BA, GB са насрещни.
Определяне на промените в потоците AX. Смяна на нишки:
а) за празна връзка с остатък:

AX = min[ min X; min(d - x)], където d е капацитетът на връзката.
Следователно корекцията е равна на по-малката от две стойности: най-малкия насрещен поток и най-малкия свободен оставащ капацитет за преминаващи потоци;
б) за наситена връзка с остатък (точно обратното правило):
> AX = min[ min X; min(d - x)], т.е. взема се най-малкият преминаващ поток и най-малкият от капацитетните резерви за насрещни потоци. При използване на правила (17.9) и (17.10) връзката с несъответствието се взема предвид сред асоциираните. За първоначалната версия големината на промяната в потоците AX1 ще бъде определена като минималната от следните стойности:
AX1 = min[(20.8, (16 -11), (10 - 6)] = 4, тъй като връзката с остатъка е празна.
За втория вариант големината на промяната в потоците AX2 ще бъде определена, както следва:
AX2 = min[(15,16,22, 30, (16 -14), (16 -15)] = 1, тъй като връзката с остатъка е наситена.
За третия вариант големината на промяната в потоците AX3 ще бъде определена, както следва:
AX3 = min[(10,14,21, (16 -15), (30 -1)(30 - 4)] = 1, тъй като връзката с остатъка е наситена.
7. Корекция на плана.
а) при коригиране на несъответствието на празна връзка потоците по всички свързани връзки на веригата (включително връзки с несъответствие) се увеличават с AX, а по противоположните намаляват с AX;
б) при коригиране на несъответствието на наситената връзка, напротив, потоците на всички свързани връзки на веригата намаляват, а на противоположните се увеличават с AX.
Изчислението произвежда нова версия на плана, за която се преопределят потенциалите, проверява се наличието на остатъци и др. (т.е. от точка 7 преминаваме към точка 2). Изчислението приключва, когато не се открият несъответствия в стъпка 3, което се случва в 4-та опция за решение, която е оптимална и е показана на фиг. 17.14.
200
Решението на проблема с мрежовия транспорт не съдържа директно стойностите на доставките чрез кореспонденция, а само предоставя диаграма на потоците по секции. Кореспондентските доставки трябва да бъдат получени въз основа на тази схема и една и съща оптимална схема на потока често съответства на много опции за доставка, които са еквивалентни по стойност на критерия за оптималност.
Такива еквивалентни оптимални опции се наричат алтернативни оптимуми. Например във версията, показана на фиг. 17.13 Товарът, пристигащ от B до D, може да бъде разтоварен в G или изпратен по-нататък до D като част от поток от 15 единици по участъка G-D. Ако има алтернативни оптимуми, човек може да избере по-удобния или изгоден от тях по причини, които не са взети предвид в критерия за оптималност. Простотата и яснотата на намирането на голям брой алтернативни оптимуми е едно от предимствата на мрежовата формулировка на транспортния проблем.

Една от областите на организиране на транспортната логистика е оптимизирането не само на разходите за използване на превозни средства в предприятието, но и оптимизирането на самия транспорт.

Уважаеми читатели! Статията говори за типични начини за разрешаване на правни проблеми, но всеки случай е индивидуален. Ако искате да знаете как реши точно твоя проблем- свържете се с консултант:

ЗАЯВЛЕНИЯ И ОБАЖДАНИЯ СЕ ПРИЕМАТ 24/7 и 7 дни в седмицата.

Бързо е и БЕЗПЛАТНО!

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

И наистина, съвременните методи позволяват да се предвидят голям брой превози в рамките на едно предприятие, каквито и да са те - на дълги разстояния, международни или междурегионални.

Какво е

Оптимизирането на автомобилния транспорт е използването на методи и технологии, които позволяват най-точно изчисляване на времето за управление на маршрутите и разходите, свързани с транспорта.

Такива проблеми могат да бъдат решени чрез изчисления, направени от служители на транспортния отдел, складове, звена за управление на инвентарния контрол и други отдели, използвайки компютърна програма. Сега той използва и двете на практика.

При дефинирането на концепцията за оптимизиране на автомобилния транспорт можем да подчертаем постоянното, редовно подобряване на транспортната система (доставка, товарене/разтоварване) на клиентските товари.

Днес такива технологии се предлагат от специалисти под формата на софтуер. Инсталирането и използването на компютърна програма, която може точно да изчисли маршрути, разходи, упътвания и други нюанси, ви позволява да нямате голям персонал в транспортния отдел. А някои организации вече изобщо нямат такъв.

Достатъчно е да обучите оператор-диспечер или счетоводител да работи в тази услуга и предприятието ще бъде напълно осигурено с ефективно решение на спедиторски, посреднически и други задачи.

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

Основната цел при решаването на такива проблеми е да се намалят разходите и да се оптимизира максимално дейността по превоз на товари на предприятието.

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

Информираността, спестяванията, изчисляването на маршрута и други технологии за оптимизация позволяват товара да бъде доставен на клиента бързо, навреме и с максимална безопасност на товара.

Какви проблеми решава?

Много компании, занимаващи се с превоз на товари, се опитват да намерят решения на следните проблеми:

Как да определим оптималните маршрути?
До каква степен е възможно да се определят най-кратките маршрути за доставка на товари?
Какво, как и къде можете да спестите пари?
Как да управлявате бизнес дейностите и да контролирате маршрутите, ако диспечерът не е на място или е нов в работата? И други въпроси.

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

Задачите на процес, който може оптимално да подобри логистиката в автомобилно транспортно предприятие, включват следните подходящи методи:

В някои случаи има ограничение за броя на контейнерите, както и за размера на превозните средства за превоз на товари.
Минимизиране на претоварването от едно превозно средство в друго, от един контейнер за транспортиране в друг.
Организиране на удобството на товаро-разтоварните операции в самата каросерия на камиона.
Автоматизирането на етикетирането на товара или пълното му премахване освобождава процеса на доставка от забавяне на времето за транспортиране.
Обединяване на броя на единиците или самия товар като цяло за превозното средство, с механизиране на разтоварването на място при клиента.
Съобразяване с вида на превозното средство за по-добър товарен капацитет.
Уверете се, че товарите са с еднакъв размер от поръчка до поръчка.
Увеличете честотата на доставките, без да увеличавате цената на транспортирана единица товар.
Намаляване на разходите за опаковане на транспортираната стока при максимално запазване на целостта й по време на процеса на придвижване от една точка до друга.
Стандартизиране на избора на типове машини за всяка поръчка, нейния размер.
Бързо определете кои доставки до клиентите са максимални и кои минимални.
Минимизиране на разходите за транспортиране на дефектни стоки и връщане на продукти.
Чрез системата за дистрибуция намалете дефектите, възникващи по време на транспортиране.
Намалете времето, изразходвано за всеки транзит на товара.
Намаляване на времето за всеки престой, възникнал по естествени причини – товарене/разтоварване.
Минимизиране на разходите за доставка на товара до клиента.
Направете потока от доставки на товари еднакъв. Това важи особено за сезонните особености.
Ако говорим за партиди за доставка, тогава е препоръчително да използвате минимален брой машини, използвани за тези цели.
Сортиране на товара по такъв начин, че да се побере максимално в превозното средство.
Намаляване на времето, изразходвано за получаване и получаване на тази или онази информация относно товара, заявките за доставка и самия транспорт. Например:
- информация за престой;
- оперативна информация за местоположението на камионите;
- кога автомобилът е пристигнал на местоназначението си (времето е посочено с точност до секунди);
- своевременно известяване на диспечера за аварии по пътя или други възникнали пречки за безопасно пристигане на местоназначението и др.

По този начин разбираме, че в допълнение към преките проблеми, които веднага се забелязват, има и косвени причини за намаляване на ефективността в областта на транспортния транспорт.

Например, лошо организираните изисквания за състоянието на автомобилите и техния навременен ремонт могат впоследствие значително да попречат на скоростта на доставка.

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

Методи за оптимизиране на транспорта

Съвременното практическо приложение на много задачи направи възможно днес да се избере един от най-оптималните методи - това е евристичният метод.

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

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

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

Нека дефинираме няколко от най-активните методи, използвани от транспортните работници днес:

Оперативни изследвания.
Линейно математическо програмиране (LP):
- приложение на линейни уравнения в изчисленията - линейна функция на елементите на пътищата на решение е целевата (ефективна) функция L (x);
- линейните равенства/неравенства представляват ограничаващи условия за възможни решения;
- целевата функция е най-голямата или най-малката стойност, търсена в математическото програмиране, като се имат предвид ограниченията;
- ограниченията могат да бъдат строги (точно тази сума и нищо друго) и нестроги (не повече или не по-малко от някаква приблизителна стойност).
Техника на северозападния ъгъл (евристика).
Техника за минитарифиране (евристика).
Метод на Фогел (евристика).
Методът на пътуващия търговец.
Прилагане на алгоритъма Svir (или както се казва - „портиер-чистач“, проблемите се решават чрез нематематически евристики).

Екип от учени и висококвалифицирани специалисти се занимава с изучаването, разработването и практическото приложение на определени техники за вземане на оптимални решения.

Този вид дейност обикновено се извършва от големи концерни и предприятия за доставки и превоз на товари. Това са онези организации, които могат да си позволят да поддържат отделни лаборатории или изследователски отдели за разработване на програми за оптимизация.

В допълнение към изследователските подходи има и математически изчисления на логистиците на практика. Те могат да използват не само линейни уравнения, но и произтичащи от тях матрични изчисления.

Евристиката ви позволява да подредите стойности в матрицата, като започнете с лявата клетка в горната част. И подреждането започва с най-ниска цена, по-евтини поръчки в посока на увеличение.

Този принцип се използва и при метода на минималната тарифа, но само тогава стойностите не се задават от ъгъла. Така можете да намерите необходимите решения – от предварителни до крайни оптимални резултати.

Техниката на Vogel предполага наличието на някакъв спомагателен коефициент, който трябва да се изчислява както по ред, така и по колона на матрицата.

Коефициентът ще бъде равен на разликата в тарифите (двете минимални), които са налични в реда или колоната. Разпределението на коефициентите следва принципа „от най-висок към най-нисък“.

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

Това предполага, че в условията на задачи, базирани на принципа на пътуващия търговец, ще бъдат зададени критерии за полза, базирани на цената на маршрута. Технически това изглежда така: по време на цялото пътуване камионът трябва да премине през всеки град по веднъж.

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

Как е организирано предприятието?

При практическото решаване на транспортни и товарни проблеми е необходимо да се координират всички нюанси. Необходимо е правилно да се планират маршрути, товарене на стоки, навременно разтоварване, връщане на превозното средство и други въпроси, свързани с операцията като цяло.

И за това те предприемат следните стъпки:

Организиране на координационен отдел или възлагане на задача на един координиращ служител (най-често това е шеф или мениджър).
Свързана работа между отделите, издаване на съответни заповеди и заповеди и друго взаимодействие между отделите.
Съвместно планиране на маршрути, координиране и изпълнение на тези планове, изграждане на графици между отдели или отдели.
Установяване на общи показатели между операциите, за да се постигне по-функционална производителност.
Ако е необходимо, ръководството се включва за установяване на връзки между отделите и отделите на предприятието.
Отговорностите между отделите и служителите трябва да бъдат ясно разделени.
Ако възникнат спорове, трябва да бъдат посочени лицата, които ще бъдат упълномощени да вземат окончателни решения.
Организирайте единно информационно поле, което да показва състоянието на маршрутите и превоза на товари.

Може да се създаде единно информационно пространство между отделите между склада, логистичния отдел, диспечерския център и други отдели, свързани с превоза на товари.

Математическата формулировка на транспортния проблем се състои в определяне на оптималния план за транспортиране на някои еднородни товари от Tизходни точки А 1 , А 2 , …, А T V Пдестинации IN 1 , ИН 2 , …, IN П . В този случай като критерий за оптималност обикновено се приемат или минималните разходи за транспортиране на целия товар, или минималното време за доставката му. Нека разгледаме транспортна задача, чийто критерий за оптималност е минималната цена за транспортиране на целия товар.

Да обозначим:

° С ij – тарифи за превоз на единица товар от iотправна точка в йта дестинация,

а i – товарни резерви в i-та отправна точка,

b й – необходимост от товари j– m дестинация,

х ij – брой единици товари, транспортирани от iотправна точка в йта дестинация.

Тогава математическата формулировка на задачата се състои в определяне на минималната стойност на функцията: (6.1)

при условия
(6.2)

(6.3)

Всяко неотрицателно решение на системи от линейни уравнения (6.2) и (6.3), определени от матрицата X=(x ij ) , се нарича план за транспортна задача.

Планирайте X*=(x*ij) , при което функция (6.1) приема минималната си стойност, се нарича оптимален план за транспортната задача.

Обикновено първоначалните данни на транспортна задача се записват под формата на таблица.

Има няколко метода за определяне на референтния план: метод на северозападния ъгъл, метод на най-ниската цена, метод на приближение на Vogel и др.

Метод на северозападния ъгъл

Максимално допустимият транспорт се въвежда в най-северозападната клетка на таблицата и или целият товар се отстранява от гарата А 1 и всички останали клетки от първия ред са зачертани, или нуждите на първия потребител IN 1 са напълно удовлетворени, тогава всички клетки в първата колона се задраскват. След това най-северозападната клетка става клетката А 1 IN 2 или IN 2 А 1 . Алгоритъмът продължава до попълване на таблицата. Недостатъци - не е отчетена цената на транспорта и резултатът е план, който е далеч от оптималния.

Метод на най-ниска цена

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

Апроксимационен метод на Фогел

На всяка итерация, като използвате всички колони и всички редове, намерете разликата между двете минимални тарифи, записани в тях. Тези разлики се записват в специално определен ред и колона в таблицата с условия на проблема. Сред посочените разлики се избира минималната. В реда или колоната, на която съответства тази разлика, се определя минималната тарифа.

Широко използван метод за решаване на транспортни проблеми е методът на потенциалите.

Този метод ви позволява да оцените първоначалното референтно решение и да намерите оптималното решение, като използвате метод за последователно подобрение.

Теорема 1. Ако опорният план X=(x ij ) е оптимална, има система от ( t+p)числа, наречени потенциали U i , V й, така че:

U i + V й =C ij ,за х ij >0 (основни променливи);

U i + V й =C ij ,за х ij =0 (свободни променливи).

По този начин, за да се провери оптималността на първоначалния оптимален план, трябва да бъдат изпълнени следните условия:

за всяка заета клетка сумата от потенциалите е равна на разходите за транспортиране на единица товар, стояща в тази клетка:

U i + V й =C ij

за всяка свободна клетка сумата от потенциали е по-малка или равна на разходите за транспортиране на единица товар, стояща в тази клетка:

U i + V й £ СЪС ij

Теорема 2. Всеки затворен транспортен проблем има решение, което може да бъде постигнато в краен брой стъпки на потенциалния метод.

Изграждане на цикъл и определяне на размера на преразпределението на натоварването.

Цикъл в транспортна таблица е прекъсната линия с върхове в клетки и ръбове, разположени по протежение на редовете или колоните на матрицата, отговаряща на две изисквания:

прекъснатата линия трябва да е свързана, т.е. от всеки от неговите върхове можете да стигнете до друг връх, като се движите по ръбовете;

Във всеки връх на цикъла се събират точно две ребра - едното в ред, другото в колона.

Безплатен цикъл на преизчисляване клетка е такъв цикъл, един от върховете на който е в свободна клетка, а останалите са в основни клетки.

Нека дадем примери за някои цикли.

Теорема 3. В транспортната таблица за всяка свободна клетка има един цикъл на преизчисляване.

Алгоритъм на потенциалния метод

Нека зададем всяка станция А iпотенциал И i, и всяка станция IN йпотенциал v й. За да направите това, за всяка попълнена клетка х ij ≠0 нека направим уравнение И i + v й =c ij . Нека добавим И 1 =1 (всяка друга стойност е възможна) и намерете всички други потенциали.

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

3. Цикълът на преизчисляване започва в свободна клетка, където поставяме знак плюс, а останалите клетки са заети. Знаците в тези клетки се редуват. Нека изберем най-малкия от транспортите в клетките със знак минус. След това добавяме този транспорт към транспорта със знак плюс и го изваждаме от транспорта със знак минус. Получаваме ново оптимално решение. Нека го проверим за оптималност.

4. За нови потенциали проверяваме условието за оптималност. Ако условията за оптималност са изпълнени, тогава се получава оптимално решение; ако не, тогава ние продължаваме да търсим оптималното решение, използвайки потенциалния метод.

Пример 7.1. Четири предприятия в този икономически район използват три вида суровини за производството на продукти. Потребностите от суровини на всяко предприятие са съответно 120, 50, 190 и 110 единици. Суровините са съсредоточени на три места, където се приемат, а запасите са съответно 160, 140, 170 единици. Суровините могат да бъдат внесени във всяко от предприятията от всяка точка на получаване. Транспортните тарифи са известни количества и се определят от матрицата
.

Направете транспортен план, в който общата цена на транспорта е минимална.

Решение:

затворена задача.

Нека съставим първия план на транспортната задача, използвайки метода на северозападния ъгъл. Нека започнем да попълваме клетките на таблицата от горната лява клетка.

S 1 =120·7+40·8+10·5+130·9+60·3+110·6=3120

Нека изготвим първия план, използвайки метода на минималните разходи. Ще запълним клетките с минимални тарифи.

S 2 =160 1+120 4+20 8+50 2+30 3+90 6=1530

Цената на този транспортен план е почти два пъти по-малка. Нека започнем да решаваме проблема с този план. Нека го проверим за оптималност. Нека въведем потенциалите α i – съответно заминавания, β j – съответно дестинации. Въз основа на заетите клетки съставяме система от уравнения α i + β j =c ij:

За свободните клетки на таблицата проверяваме критерия за оптималност

Нека компенсираме разликите

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

S 3 =70 1+90 2+120 4+20 8+50 2+120 3=1350

Цената на транспорта е по-ниска, т.е. планът е подобрен. Сега проверяваме новия план за оптималност. По заети клетки:

За свободни клетки:

Планът не е оптимален, защото има положителна оценка
Изграждаме цикъл на преизчисляване и преминаваме към нов план.

S 4 =50 1+110 2+120 4+20 5+30 2+140 3=1330

Проверяваме новия план за оптималност.

По заети клетки:

За свободни клетки:

Критерият за оптималност е изпълнен, т.е. последният план е оптимален.

Отговор:

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

1) Обем на транспортната работа (критерий - разстояние в т/км). Минималният пробег е удобен за оценка на транспортните планове, тъй като разстоянието на транспортиране може да се определи лесно и точно за всяка посока. Следователно критерият не може да разреши транспортни проблеми, включващи много видове транспорт. Успешно се използва при решаване на транспортни проблеми за автомобилния транспорт. При разработване на оптимални схеми за транспортиране на еднородни товари с превозни средства.

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

3) Експлоатационни разходи за транспортиране на товари (критерий - себестойност на оперативните разходи). По-точно отразява рентабилността на транспортирането с различни видове транспорт. Позволява ви да направите информирани заключения относно осъществимостта на преминаването от един вид транспорт към друг.

4) Срокове за доставка на стоките (критерий - разход на време).

5) Нивелирани разходи (като се вземат предвид оперативните разходи, в зависимост от размера на трафика и инвестициите в подвижен състав).

6) Дадени разходи (като се вземат предвид пълните оперативни разходи за капиталови инвестиции в изграждането на съоръжения за подвижен състав).

къде са оперативните разходи,

Очакван коефициент на инвестиционна ефективност,

Капиталови инвестиции на 1 тон товар в целия участък,

T - време за пътуване,

C - цената на един тон товар.

Позволява по-пълна оценка на рационализацията на различни варианти на транспортни планове, с доста пълно изразяване на количественото и едновременно влияние на няколко икономически фактора.

Нека разгледаме транспортна задача, чийто критерий за оптималност е минималната цена за транспортиране на целия товар. Нека означим чрез тарифите за транспортиране на единица товар от i-та точка на тръгване до j-та точка на местоназначение, през – товарните резерви в i-тата точка на тръгване, през – изискванията за товари в j-тата точка на местоназначение, а през – броят единици товар, транспортирани от i-тата точка на отпътуване до j-тото местоназначение. Тогава математическата формулировка на задачата се състои в определяне на минималната стойност на функцията

при условия

(2)

(3)

(4)

Тъй като променливите удовлетворяват системите от линейни уравнения (2) и (3) и условието за неотрицателност (4), тогава отстраняването на съществуващ товар от всички точки на тръгване, доставката на необходимото количество товар до всяка дестинация са осигурени и връщането транспортът е изключен.

По този начин T-проблемът е LP проблем с м*нброй променливи и m+nброй ограничения – равенства.

Очевидно общата наличност на товари от доставчици е равна на , а общото търсене на товари по дестинациите е равно на единици. Ако общото търсене на товари в дестинациите е равно на предлагането на товари в местата на произход, т.е.

тогава се нарича моделът на такъв транспортен проблем затворенили балансиран.

Има редица практически задачи, при които условието за баланс не е изпълнено. Такива модели се наричат отворен. Има два възможни случая:

В първия случай пълното задоволяване на търсенето е невъзможно.

Такъв проблем може да бъде сведен до конвенционален транспортен проблем, както следва. Ако търсенето надвишава запасите, т.е. фиктивен ( м+1)-та точка на тръгване с карго резерв и тарифите се приемат за нула:

След това трябва да минимизирате

при условия

Нека сега разгледаме втория случай.

По същия начин, когато фиктивен ( н+1)та дестинация с нужда и съответните тарифи се считат за равни на нула:

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

Минимизиране

при условия:

Това свежда проблема до обикновен транспортен проблем, от чийто оптимален план се получава оптималният план на първоначалния проблем.

По-нататък ще разгледаме затворен модел на транспортния проблем. Ако моделът на конкретен проблем е отворен, тогава, въз основа на горното, ще пренапишем таблицата с условия на проблема, така че да е изпълнено равенство (5).

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

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

· от складовата наличност на съответния диспечерски пункт;

· според нуждите на съответната дестинация.

Пример.

Четири предприятия в този икономически район използват три вида суровини за производството на продукти. Потребностите от суровини на всяко предприятие са съответно 120, 50, 190 и 110 единици. Суровините са съсредоточени на три места, където се приемат, а запасите са съответно 160, 140, 170 единици. Суровините могат да бъдат внесени във всяко от предприятията от всяка точка на получаване. Транспортните тарифи са известни количества и се определят от матрицата

Направете транспортен план, в който общата цена на транспорта е минимална.

Решение. Нека означим с броя на единиците суровини, транспортирани от i-тата точка на получаване до j-то предприятие. Тогава условията за доставка и извоз на необходимите и налични суровини се осигуряват при изпълнение на следните равенства:

(6)

С този план транспорт, общата цена на транспорта ще бъде

По този начин математическата формулировка на този транспортен проблем се състои в намирането на такова неотрицателно решение на системата от линейни уравнения (6), в което целевата функция (7) приема минимална стойност.

Решение на транспортния проблем

Основните стъпки при решаването на транспортен проблем:

1. Намерете първоначалния изпълним план.

2. Изберете от неосновните променливи тази, която ще бъде въведена в основата. Ако всички неосновни променливи отговарят на условията за оптималност, завършете решението, в противен случай преминете към следващата стъпка. стъпка.

3. Изберете променлива, получена от основата, и намерете ново основно решение. Върнете се към стъпка 2.

Всяко неотрицателно решение на системи от линейни уравнения (2) и (3), определени от матрицата , се нарича план за транспортна задача. Референтен (базисен) план на Т-задача се нарича всяко нейно допустимо, основно решение.

Обикновено първоначалните данни на транспортна задача се записват под формата на таблица.

Матрицата C се нарича матрица на транспортните разходи, матрицата X, която удовлетворява условията на Т-проблема (2) и (3), се нарича транспортен план, а променливите се наричат транспорт. Планът, при който целевата функция е минимална, се нарича оптимален.

Брой променливи в транспортна задача с мотправни точки и нравни дестинации м*н, а броят на уравненията в системи (2) и (3) е равен на m+n. Тъй като приемаме, че условие (5) е изпълнено, броят на линейно независимите уравнения е равен на m+n–1. Следователно референтният план на транспортен проблем може да има не повече от m+n–1ненулеви неизвестни.

Ако в опорния план броят на ненулевите компоненти е точно m+n–1, тогава планът е неизроден, а ако е по-малък, тогава е изроден.

Както за всеки проблем с линейно програмиране, оптималният план за транспортен проблем също е референтен план.

Построяване на допустим (опорен) план в транспортна задача

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

Най-лесният начин да го намерите се основава на така наречения метод на северозападния ъгъл. Същността на метода е последователното разпределение на всички запаси, налични в първата, втората и т.н. точки на производство, през първата, втората и т.н. точки на потребление. Всяка стъпка на разпределение се свежда до опит за пълно изчерпване на резервите в следващата точка на производство или до опит за пълно задоволяване на нуждите в следващата точка на потребление. Всяка стъпка от пътя р са посочени стойностите на текущите неразпределени резерви и i(q ) и настоящи незадоволени нужди - b j (q ) . Изграждането на приемлив първоначален план, според метода на северозападния ъгъл, започва от горния ляв ъгъл на транспортната маса, докато предполагаме a i (0) = a i, b j (0) = b j . За следващата клетка, разположена в реда i и колона й , стойностите на неразпределените запаси в i -та точка на производство и незадоволена потребност й та точка на потребление, от тях се избира минимумът и се задава като обем на транспортиране между тези точки: x i, j =min(a i (q) , b j (q) ) . След това стойностите на неразпределения запас и неудовлетворената нужда в съответните точки се намаляват с тази сума:

a i (q+1) = a i (q) - x i, j, b j (q+1) = b j (q) - x i, j

Очевидно на всяка стъпка е изпълнено поне едно от равенствата: и i (q+1) = 0 или b j (q+1) = 0 . Ако първото е вярно, това означава, че целият запас на i-та производствена точка е изчерпан и трябва да се премине към разпределение на запасите в производствената точка i+1 , т.е. преминете към следващата клетка надолу в колоната. Ако b j (q+1) = 0, това означава, че необходимостта от й та точка, последвана от преход към клетката, разположена от дясната страна на линията. Новоизбраната клетка става текуща и за нея се повтарят всички горни операции.

Въз основа на условието за баланс между запаси и потребности не е трудно да се докаже, че в краен брой стъпки ще получим допустим план. Поради същото условие, броят на стъпките на алгоритъма не може да бъде по-голям от m+n-1 , следователно винаги ще остане свободен (нула) mn-(m+n-1) клетки. Следователно полученият план е основен. Възможно е на някаква междинна стъпка текущият неразпределен запас да се окаже равен на текущото неудовлетворено търсене (a i (q) =b j (q)) . В този случай преходът към следващата клетка се извършва в диагонална посока (текущите точки на производство и потребление се променят едновременно), което означава „загуба“ на един ненулев компонент в плана или в друг думи, израждането на изградения план.

Характеристика на допустимия план, конструиран по метода на северозападния ъгъл, е, че целевата функция върху него приема стойност, която като правило е далеч от оптималната. Това се случва, защото при конструирането му стойностите не се вземат предвид по никакъв начин c i, j . В тази връзка на практика се използва друг метод за получаване на първоначалния план - метод на минимален елемент, в който при разпределяне на обемите на трафика първо се заемат клетки с най-ниски цени.

Пример за намиране на референтен план

F=14 x 11 + 28 x 12 + 21 x 13 + 28 x 14 + 10 x 21 + 17 x 22 + 15 x 23 + 24 x 24 + 14 x 31 + 30 x 32 +25 x 33 + 21 x 34

Първоначалният план е получен по метода на северозападния ъгъл. Задачата е балансирана (затворена).

маса 1

Цената на транспорта по този план е: 1681:

F=14 *27 + 28* 0 + 21*0 + 28*0 + 10 *6 + 17 *13 + 15*1 + 24 *0 + 14 *0 + 30 *0 +25*26 + 21 *17 = 1681 г