Оптимальний розподіл поїздів на залізниці

Розробка програмного продукту, який виконує розрахунок оптимального розподілу механізмів по роботах. Алгоритм методу мінімального елемента, побудови опорного плану транспортної задачі. Реалізація алгоритмів мовою С++. Методи побудови опорного плану.
Краткое сожержание материала:

Размещено на

Размещено на

Міністерство освіти і науки України

Черкаський національний університет ім.. Б.Хмельницького

Факультет інформаційних технологій та біомедичної кібернетики

Курсова робота

з дисципліни: «Математичні методи дослідження операцій»

на тему: «Оптимальний розподіл поїздів на залізниці»

по спеціальності: 6.080403 - програмне забезпечення АС

УКР.ЧНУ.00701010-01

Виконав

студентка 4 курсу

групи ЗКС-071

Дейнеко І.В.

Керівник

викл. Корепанов А.С.

Черкаси 2010г.



ВСТУП

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

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

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

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

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

1. ПОСТАНОВКА ТЕХНІЧНОГО ЗАВДАННЯ

1.1 Постановка завдання та вимог до програмного продукту

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

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

Розрахунок результатів зводиться до транспортної задачі.

1.2 Вибір мови програмування та середовища розробки

Для виконання завдання курсової роботи було обрано версію C++Builder 2010, що була випущена у серпні 2009. На сьогоднішній день дана реалізація є однією з найновіших.

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

1.3 Аналіз поставленого завдання та огляд існуючих аналогів

Формалізація задачі:

Розглянемо поставлену задачу: Знайти оптимальний розподіл трьох взаємозамінних механізмів по чотирьом видам земельних робіт при заданих ресурсах часу кожного механізму 240,160 і 150 год., продуктивності механізмів 30, 55, 18 м³/год., об'ємі виконуваних робіт 5, 2, 3 і 8 тис. м³ і матриці С собівартостей робіт, грн/м³.

Представимо вихідні дані в вигляді таблиці:

	Робота1	Робота2	Робота3	Робота4	Ресурси часу	Продуктивність
Механізм1	2	1	0,5	1,2	240	33
Механізм 2	0,8	1,2	0,9	0,8	160	55
Механізм 3	0,5	1	0,6	0,9	150	18
Об'єм робіт	5000	2000	3000	8000

Приведемо вихідні дані до класичного вигляду транспортної задачі (перемноживши ресурси часу механізмів і продуктивності їх роботи отримаємо наявний запас робіт в м³):

	В1	В2	В3	В4	Запаси
А1	2	1	0,5	1,2	7200
А2	0,8	1,2	0,9	0,8	8800
А3	0,5	1	0,6	0,9	2700
Потреби	5000	2000	3000	8000

Сумарні потреби: 5000+2000+3000+8000=18000.

Сумарні запаси: 7200+8800+2700=18700.

Сумарні запаси більші за сумарні потреби отже задача відкрита.

Математична модель відкритої задачі

Щоб перетворити дану відкриту задачу в закриту додамо ще один пункт споживання (вартості перевезень в даний пункт споживання рівні 0).

Закрита задача:

	В1	Другие файлы: Кількісні показники вагонопотоків залізниці та її дирекцій з перевезень Визначення розмірів ввезення навантажених вагонів. Правила їх розподілу по станціях залізниці. Розрахунок балансу порожніх вагонів по стикових пунктах... Розрахунки строків служби елементів колії та її ремонтів Вибір типу рейок, що підлягають укладанню на ділянці залізниці. Визначення строку служби рейок та щебеневого баласту на ділянці залізниці. Встановленн... Рух поїздів Техніко-експлуатаційна характеристика дільниць дирекції залізничних перевезень. Розрахунок інтервалів схрещення, неодночасного прибуття, попутного слі... Розробка технологічного процесу дільничної станції на підставі інтенсифікації станційних процесів Технічна та експлуатаційна характеристика станції. Технологія обробки поїздів і вагонів. Розрахунок норм часу на операції з поїздами і вагонами. Розро... Реконструкція ділянки залізниці Реконструкція поздовжнього профілю ділянки залізниці. Аналіз технічного оснащення і стану земляного полотна, штучних споруд та будови колії. Розрахуно...