183501 (596674), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

(58)

(59)

Витрати бюджету часу транспортних з асобів, що укладаються з витрат на перевезення вантажів, витрат під час оренди і позаесплуатаційних витрат, не повинні перевищувати загального календарного бюджету часу транспортних засобів даного типу в даний період:

(60)

де

(61)

Витрати на аренду не повині перевищувати виділену для цього суму

(62)

Обсяги надання транспортних засобів в оренду не повинні перевищувати відповідних потреб:

(63)

(64)

Витрати бютжету часу арендованих транспортних засобів не можуть більше максимально м ожливих:

(65)

Витрати бюджету часу, обсяги перевезень і обсяги вантажів невід’:

(66)

Особливістю даної моделі в порівнянні з запропонованими: раніше є те, що в ній істотно враховується сезонність вантажопотоків і обмеження на використання транспортних засобів на окремих напрямках перевезень у різний час року, припускається перенос перевезення деяких вантажів на інший період часу,' враховуються утрати від невчасного вивозу вантажів, обов'язковість деяких із перевезень і можливість оренди транспортних засобів.

У зв'язку з тим що для значних транспортних організацій сформульована задача має надзвичайно велику розмірність, було запропоновано використовувати для її рішення декомпозиційний метод.

У результаті декомпозиції шляхом розкладання обмежень (58), (59), (62), (63) по групах типів транспортних засобів , задача (57)-(66) зводиться до двохрівневому комплексу задач меншої розмірності.

На другому (верхньому) рівні вирішуються задачі розподілу обсягів вантажів, обсягів решти транспортних засобів в оренду і коштів між групами транспортних засобів:

де коефіцієнти цільових функцій характеризуютьдоцільність збільшення для j-й групи транспортних засобів що виділяється обсягу решти транспортних засобів в аренду, кількості коштів і обсягу вантажів відповідно.

На першому (нижньому) рівні для кожної групи j (j =1, J) визначаються обсяги перевезень власними й арендованими транспортними засобами, обсяги вантажів, перевезення котрих переноситься на інші планові періоди, а також обсяги аренди і решти в оренду транспортних засобів, що забезпечують отримання максимального економічного ефекту

при виконанні обмежень (59)-(61), (64), (65), специфічних для даної групи транспортних засобів, а також заданих другим рівнем обмежень на загальні обсяги перевезень вантажів власними, арендованими і що здаються в аренду транспортними засобами

і на загальні витрати, пов'язані з орендою транспортних засобів,

та умовневід’ємності змінних

Для узгодження рішень отриманих підзадач другого і першого рівня з метою досягнення оптимального рішення вихідної задачі застосовується ітеративний алгоритм.

Розроблені однорівнева і дворівнева моделі дозволяють оптимізувати розподіл транспортних засобів по напрямках перевезень з урахуванням сезонної нерівномірності вантажопотоків. Ефективне використання ресурсів транспорту досягається завдяки раціональному розподілу перевезень між транспортними засобами різного типу, висновку транспортних засобів з експлуатації в період Мінімального навантаження, оренді транспортних засобів в інших підприємств у період максимального навантаження і решті в оренду власних транспортних засобів у період мінімальної.

Запропоновані моделі можуть бути використані для рішення цілого ряду практичних задач поточного і перспективного планування, у тому числі для планування роботи транспортного підприємства, розподіли планових завдань на перевезення вантажів між різноманітними транспортними підприємствами, оптимізації структури парку транспортних засобів, визначення оптимальної кількості що закуповуються (мурованих, арендованих) і що списуються в зв'язку з моральним зносом транспортних засобів кожного типу і т.п.

Для рішення практичних задач розподілу потоків вантажів між різноманітними типами транспортних засобів розроблені програми: GRASS1, що дозволяє вирішити задачу (57)-(66) звичайним алгоритмом лінійного програмування, і GRASS2, що реалізує декомпозиционный алгоритм рішення цієї задачі. Програми побудовані по модульному принципі, мають оверлейную структуру і містять такі модулі:

GRAS1, GRAS2 - модулі, що управляють викликом підпрограм при рішенні задача (57)-(66) та відповідно задач другого і першого рівнів у дворівневоймоделі;

INPUT1, INPUT2 - підпрограми для запровадження вихідних даних і формування на їхній основі матриць умов задачі лінійного програмування;

LINK1, LINK2- підпрограми для перетворення розширеної матриці умов, задача лінійного програмування (яка містить строчку коефіцієнтів критерію і стовпчик правих частин обмежень) у компактну форму (без нульових елементів);

SIMPL1, SIMPL2 - підпрограми для рзшзния задач лінійного програмування з компактною формою матриці обмежень;

SOLVE1, SOLVE2- підпрограми, що реалізують звичайний Ц декомпозиционный алгоритми рішення задачі з використанням одноуровневой і двухуровневой моделей відповідно;

2.7 Основні задачі оптимізації транспортних потоків

Всі задачі оптимізації транспортних потоків можна розділити на два класи: задача, у яких транспортні потоки рахуються незалежними, і задача, у яких враховується взаємозв'язок транспортних потоків різноманітних видів.

Перший клас задач вивчений достатньо докладно, і йому присвячене значне спало робіт, чого не можна сказати про другий клас, порівняно мало досліджуваному.

Відповідно до яскраво вираженого розходження в технології перевезень і задачах керування ними всі задачі оптимізації незалежних потоків можна розділити на задачі оптимізації транспортних потоків, що відповідають масовим і мілкоштучними перевезенням вантажів.

Найбільше добре вивченими і широко застосовуваними є задачі визначення максимального транспортного потоку однієї групи (потоку вантажів, транспортних засобів і т.п.), що протікає від джерела s у стік t мережі. При цьому кожній дузі (i, j) мережі G (K, А) приписана деяка пропускна спроможність, що визначає найбільше значення транспортного потоку, що може протікати по даній дузі.

Якщо є декілька пунктів зародження п поглинання транспортних потоків (джерела п стоків), причому між різноманітними джерелами і стоками протікають різнорідні транспортні потоки і сума усіх видів потоків через відповідну дугу обмежена її пропускною спроможністю, така задача максимизації сумарного потоку між джерелами і стоками називається задачею про багатопродуктовий потік.

У випадку, коли на додаток до пропускних спроможностей задані також вартості переміщення одиниці транспортного потоку по кожній дузі мережі, виникає задача перебування транспортного потоку, вартість переміщення якого мінімальна.

Одним з окремих випадків задач оптимізації потоків, розв'язуваних при керуванні масовими перевозками, є визначення найкоротших шляхів на транспортній мережі. Ця задача необхідна для упорядкування матриць кореспонденції: таблиць міжпортових кореспонденції - на морському транспорті і шахів-маток кореспонденції - на залізничному транспорті.

Якщо відмовитися від припущення, що в процесі переміщення по дузі розмір транспортного потоку залишається незмінної, тобто якщо на виході з дуги розмір потоку дорівнює розміру потоку на; її вході, помноженої на деяке ненегатовние число, те задача про потік між я и г стає задачею про потоки з посиленнями або втратами.

В усіх розглянутих вище випадках неявно припускалися, що транспортні потоки, що існують у мережі, є статистичними, тобто не враховується такий важливий показник, як час переміщення потоку по дузі. Припустимо, що кожна дуга характеризуется додатково і часом проходження по ній одиниці потоку. При цьому можливими потоками рахуються тільки, такі, у котрих кожна одиниця потоку проходить із джерела в стік за час, що не перевищує задане. Задача про динамічний потік складається в тому, щоб визначити оптимальний транспортний потік із джерела в стік у зазначений час за умови, по в кожній вершині мережі G (K, А) потік може відправлятися негайно або затримуватися. У такий важливої в практичному відношені постановці задачі можуть бути облічені також витрати на перевалювання, обмеження на ємність складів, пропускні здатності пунктів перевалювання, витрати на збереження і т.д. Задача динамічному потоку грає істотну роль у постановці та рішенні великого класу задач упорядкування графіків і роскладу роботи транспортних засобів.

У розглянутих вище задачах передбачається, що потік вантажів від відправника до одержувача значно вище вантаже під’ємності транспортного засобу (масові перевезення) і його можна виміряти кількістю транспортних засобів, необхідних для його освоєння. При цьому непарністю потоку вантажомісткості:транспортних засобів припустимо зневажати, тобто можна невраховувати цілочисльність потоку.

Протилежний випадок має місце при плануванні дрібних перевезень, коли вантажомісткість використовуваних транспортних засобів значно вище ваги партії. Основними задачами оптимізації дрібних перевезень є- задача маршрутизації й упорядкування графіків прямування транспортних засобів.

У задачах маршрутизації при заданих множинах пунктів гроизводства, споживання, розміщення рухливого складу,

У якості таких критеріїв використовуються найменше число транспортних засобів, найкоротший час виконання перевезень, мінімальна сумарна відстань або вартість виконання перевезень і т.д.

У випадку, що коли вирішує чинником у плануванні роботи транспортного підприємства є урахування динаміки транспортного процесу, виникають задачі упорядкування графіків прямування транспортних засобів. У графіках визначаються маршрути прямування транспортних засобів, що задовольняють заданим моментам їхній прибуття або відправлення в пункти транспортної мережі. Будь-яке транспортне підприємство, плануючи свою роботу на тривалий період T, як правило, намагається організувати роботу частини транспортних засобів із якоюсь періодичністю. Графіки з повторюваною структурою на інтервалах часу [(k - 1)T; kT], k = 1, 2,... будемо називати розкладом роботи транспортного засобу. Період Т може бути, наприклад, дорівнює 24 ч для роботи міського і приміського транспорту, тижню чи місяцю для роботи морських і річкових судів.

Таким чином, задача упорядкування графіків прямування транспортних засобів є подальшим ускладненням задач маршрутизації.

Задача маршрутизації й упорядкування графіків і розкладів прямування транспортних засобів є надзвичайно складними з обчислювальної точки зору. Відповідно до теорії обчислювальної складності рішення задач дискретної оптимізації [2] ефективно розв'язуваної називається задача, для рішення якої існує алгоритм із числом операцій, статечним уявою залежних від розмірності вихідних даних. Задача називається важковирішальною, або NP-складною, якщо для будь-якого відомого алгоритму її точного рішення можна побудувати приклад, для якого число операцій алгоритму буде виражатися експоненціальною функцією від розмірності вихідних даних задачі.

Показано, що задача оптимізації потоку транспортних засобів, що чинять дрібні перевезення, не мають ефективних точних алгоритмів рішення [3]. Застосування точних алгоритмів, заснованих на методах математичного програмування, для одержання чисельного рішення задач реальної розмірності надається практично неспроможним. Ці методи дозволяють вирішувати задача незначних розмірностей і мають головною уявою теоретичне значення. Тому для рішення задач маршрутизації й упорядкування графіків використовуються наближені й евристичні алгоритми.

Другим класом задач оптимізації транспортних потоків є задачі про взаємозалежні транспортні потоки, у котрих додані умови, що відбивають залежність розміру транспортного потоку одного виду, що протікає по якийсь дузі мережі, від розміру транспортних потоків інших видів, що протікають по цей же дузі. (Наприклад, залежність потоку вантажів від потоку транспортних засобів, що перевозять ці вантажі. ) Крім того, у цих задачах може враховуватися можливість перетворення транспортних потоків одного виду в інші. Така ситуація має місце, зокрема, у транспортних вузлах, де відбувається перевалювання вантажів з одного виду транспорту на другий.

2.8 Математичні моделі, у яких враховується взаємозв'язок потоків

Ці моделі більш точно описують реальний транспортний процес. Проте алгоритми рішення задач про взаємозалежні потоки значно складніше алгоритмів для задач про незалежні потоки і в даний час їхнє дослідження тільки починається.

На практику частіше інших зустрічаються задачі, у яких потрібно оптимізувати два види взаємозалежних транспортних потоків: потік вантажів різного роду і потік різноманітних видів транспортних засобів.

Задача оптимізації вантажопотоків і потоків транспортних засобів можуть мати досить високу розмірність, особливо якщо мова йде про оптимальний розподіл вантажопотоків між усіма видами транспорту. У цьому випадку доцільно використовувати не одну математичну модель, а ієрархічну систему взаємодіючих моделей, у якій модель верхнього рівня описує весь транспортний процес із використанням агрегованих показників, а моделі нижнього рівня дають детальний опис окремих складового цього процесу. Рішення, отримане за допомогою агрегированої моделі, використовують для узгодження рішень детальних задач, а рішення детальних задач - для уточнення агрегованої моделі.

Характеристики

Список файлов ВКР