Xreferat.com » Рефераты по экономико-математическому моделированию » Математична модель транспортної системи підприємства

Математична модель транспортної системи підприємства

/> на перевалювання одиниці вантажу з одного виду транспорту на інший. З деяких пунктів можливий вивіз надпланових вантажів (наприклад, на морському транспорті такими вантажами є вантажі іноземних фрахтувальників).

Потрібно знайти розмір агрегованого потоку вантажів по дугах графа { }, обсяги відправлення і доставки вантажів { }, { }, обсяги перевалювання вантажів із М-го виду транспорту на L-й і навпаки в кожному пункті перевалювання { }, { },обсяги відправлення надпланових вантажів { }, кількості вантажів, що спрямовуються кожним видом транспорту на склади або вивезених із складів { }, { }, і визначити частки { } і { } початкової кількості вантажів на складах у кожному пункті і загальній ємності складів, що виділяються в розпорядження кожного виду транспорту, при яких досягається максимум економічного ефекту


При цьому повинні виконуватися умови зберігання агрегованого потоку вантажів n-го роду ( ) при проходженні через вершини графа в кожний період часу t( )


(37)

(38)

(39)


де


(40)


Обмеження (37) відповідає пунктам відправлення і доставки вантажів, що одночасно є пунктами перевалювання, обмеження (38) - пунктам, що є тільки пунктами відправлення і доставки, а обмеження (39) - іншим пунктам. Крім того, виконуються обмеження на максимально можливі обсяги відправлення і доставки вантажів


(41)


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

(42)


обмеження на пропускну спроможність ланки агрегованої транспортної мережі:


(43)


і обмеження на використання ємності складів у вузлах агрегованої транспортної мережі різноманітними видами транспорту


(44)


де


(45)


Кількість вантажів кожного роду, що зберігаються на складах у кожний момент часу, невід’ємна:


(46)


де початкової кількості вантажів п-го роду, що може бути вивезена M-м видом транспорту,


(47)

Крім того, повинні виконуватися умови невід’ємності:


(48)


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

Шляхом розкладання обмежень (41), (42), (45), (47) на окремі обмеження для кожного підграфа вихідна задача (36) - (48) зводиться до двохрівневої системи більш простих задач. Ця система складається з розв'язуваних на другому рівні задач розподілу обсягів відправлення і доставки вантажів , пропускних спроможностей пунктів перевалювання , ємностей складів і початкової кількості вантажів у них між різноманітними видами транспорту:



і розв'язуваних на першому рівні задач визначення агрегованых потоків вантажів по окремим підграфами , що відповідають різноманітним видам транспорту М:



Крім того, повинні виконуватися обмеження (37)-(39), (43), (44), (46), (48).

Застосування методу декомпозиції дозволяє істотно | зменшити розрахункові труднощі. Задача другого рівня 1 мають просту структуру, і їхні рішення можуть бути виписані 3 у явному виді, а задача першого рівня вирішуються на окремих підграфах і можуть бути зведені до задач про однопродуктовий потік мінімальної вартості, для яких є ефективні спеціальні алгоритми [14-26] (як зазначено в [13], за допомогою даних алгоритмів задачі вирішуються приблизно в 50-100 разів швидше, чим за допомогою звичайних методів лінійного програмування. Так, наприклад, задача з 1200 вершинами і 4000 дуг була вирішена усього за 20 с).

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

2.6 Модель нижнього рівня - оптимізація транспортних потоків на транспортних мережах окремих видів транспорту


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


(49)

при виконанні обмежень


(50)

(51)

(52)

(53)


де відображаючих умови зберігання потоку вантажів кожного роду.

Крім того, повинні виконуватися обмеження на максимально можливі обсяги відправлення і доставки вантажів


(54)


обмеження на кількість вантажів, що можуть бути спрямовані на склад:

(55)


і узяті зі складів:


(56)


Розглянемо математичну модель і метод рішення.

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

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

Одна з перших формулювань задачі розставляння транспортних засобів з одночасною побудовою схем їхній переміщення запропонована в [44]. У даній роботі транспортна мережа містить тільки пункти відправлення і пункти призначення вантажів одного роду і потрібно визначити оптимальну кількість порожніх у навантажених транспортних засобів кожного типу, що переміщаються по ланках транспортної мережі, при якому забезпечуються мінімальні сумарні витрати бюджету часу транспортних засобів. Задано обмеження на розмір бюджету часу кожного типу транспортних засобів на необхідні обсяги перевезень із кожного пункту відправлення в кожний пункт призначення, а також обмеження, що відбивають умови зберігання потоку транспортних засобів при проходженні через вузли транспортної мережі.

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

У [17] сформульована задача планування перевезень декількох родів вантажів у різноманітні періоди часу. Частина вантажів повинна бути перевезена обов'язково, перевезення інших вантажів є факультативної. Поряд з обмеженнями, розглянутими в [14, 15], задані обмеження на припустиме скупчення транспортних засобів в однім регіоні і на мінімально припустимий обсяг перевезення вантажів між пунктами відправлення та пунктами призначення. Враховується також кількість транспортних засобів, що повинні вводитися в експлуатацію і виводитися з її в окремих вузлах транспортної мережі.

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

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

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

У [19] запропонований двохетапний метод рішення задачі розставляння транспортних засобів.

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

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

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

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

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

У зв`язку із цим у [15] запропонований декомпозиційний метод для рішення задач, що мають велику розмірність.

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

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

Перед тим, як переходити до формулювання моделі, уведемо деякі позначення:

- обсяг перевезень вантажів n-го роду по l-му напрямку в період транспортними засобами m-го типу, що належать підприємству (усі типи транспортних засобів т діляться на групи );

- обсяги перевезень транспортними засобами m-го типу, орендованими в іншого підприємства р для виконання окремих перевезень і на весь період відповідно;

- обсяг вантажів n-го роду, що транспортне підприємство повинно перевезти по напрямку l у заданий період, часу [];

- залишок вантажів n-го роду на l-й напрямку в період ;

- обсяг перевезень транспортними засобами m-го типу, зданими в оренду іншому підприємству р для виконання окремих перевезень;

- витрати бюджету часу транспортних засобів, наданих у ореду іншому підприємству р на період ;

- позаексплуатаційні витрати бюджету часу (наприклад, на плановий ремонт), розподіл яких по період дам часу {} можна регулювати;

- трудомісткість перевезення вантажу n-го роду по l-му напрямку в період транспортними засобами m-го типу;

- прибутки від перевезення одиниці вантажу;

- експлуатаційні витрати на перевезення единиці вантажу;

- арендна платня за перевезення лдиниці вантажу та за одинцю бютжетного часу арендованого транспортного засобу;

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

- втрати від невивозу вантажу n-го роду на l-ном напрямку в період (щодо обов’язкових перевезень ).

Математична модель планування об’ємів перевезень має наступний вигляд.

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


(57)


При цьому повинні бути виконані такі обмеження.

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


(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, А) приписана деяка пропускна спроможність, що визначає найбільше значення транспортного потоку, що може протікати по даній дузі.

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

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

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

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

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: