ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


І.В. Подкопай, Р.В. Посилаєва

Загрузка...

ДОСЛІДЖЕННЯ ОПЕРАЦІЙ

 

Навчально – методичний посібник

 

 

 

Харків 2010

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

 

ХАРКІВСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ

УНІВЕРСИТЕТ БУДІВНИЦТВА ТА АРХІТЕКТУРИ

 

 

Н.Ю.Іохвидович, Е.В. Поклонський,

І.В. Подкопай, Р.В. Посилаєва

 

ДОСЛІДЖЕННЯ ОПЕРАЦІЙ

 

 

Рекомендовано

методичною радою університету

як навчально–методичний посібник

для студентів напряму 6.030601

 

Харків 2010

 

 

Рецензенти:

 

А.А.Янцевич, доктор фіз.-матем. наук, професор каф. вищої математики і інформатики Харківського національного університету ім. В.Н.Каразіна

 

О.О. Аршава, канд. фіз.-мат. наук, доцент, зав. кафедри вищої математики Харківського державного технічного університету будівництва та архітектури

 

 

Рекомендовано кафедрою вищої математики,

протокол № 9 від 27.05.09

Затверджено методичною радою університету,

Протокол № 1 від 30..09.09

 

 

Автори: Н.Ю.Іохвидович

Е.В. Поклонський

І.В. Подкопай

Р.В. Посилаєва

 

 

Н.Ю.Іохвидович, Е.В. Поклонський, І.В. Подкопай, Р.В. Посилаєва. Дослідження операцій: навчально – методичний посібник – Харків, ХДТУБА, 2010. – 80 с.

 

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

 

 

Іл: ; табл.: ;бібліогр.: назв

 

 

© Н.Ю.Іохвидович, Е.В. Поклонський, І.В. Подкопай, Р.В. Посилаєва, 2010

Загальні відомості

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

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

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

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

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

Розглянемо типові моделі задач теорії дослідження операцій.

IЗадачі розподілу.

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

До задач розподілу можна віднести транспортну задачу, яка розглядається в курсі «Математичне програмування», задачу про призначення (маємо n посад та m претендентів на них, потрібно так розподілити претендентів, щоб витрати на заробітну плату були мінімальними).

IIЗадачі масового обслуговування.

Ці задачі виникають в аналізі процесів, що призводять до затримки обслуговування і черг.

IIIЗадача мережевого планування.

Потрібно виконати велику кількість робіт, при цьому роботи треба розподілити так, щоб витрати часу були мінімальними.

IVЗадачі теорії розкладу.

VЗадачі вибору маршруту (задача комівояжера).

VIЗадача про пошук.

VIIЗадачі теорії ігор.

Сформулюємо типові етапи розв’язання задач теорії дослідження операцій.

IПорушення проблеми:

а) виявлення проблеми;

б) формулювання мети і критерію ефективності;

в) аналіз проблеми;

г) побудова математичної моделі задачі.

IIЗнаходження оптимального розв’язку:

а) розв’язок математичної моделі з різноманітними цільовими функціями;

б) синтез оптимального розв’язку (тобто комбінація отриманих рішень).

IIIПрийняття і реалізація рішень.

У подальшому детально розглянемо деякі з означених вище задач.

 

Глава 1 Задача теорії розкладу

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

Така задача повністю розв’язана для випадку n деталей і 2-х верстатів.

Для двох верстатів існує (n!)2 можливостей обробки деталей (для одного верстата це n! способів обробки n деталей).

Доведено, що деталі на другому верстаті повинні оброблятися в тому ж порядку, що і на першому. Це скорочує число можливих варіантів обробки з (n!)2 до n! Ідея полягає в тому, щоб максимально скоротити простої другого верстата при повному винятку переривання в роботі першого.

Алгоритм Джонсона для розв’язання цієї задачі полягає в наступному. Нехай ai – час обробки i-ї деталі на I-му верстаті,

bi – час обробки i-ї деталі на II-му верстаті,

i=1,2,…,n.

Знаходимо min(a1, a2,…, an, b1, b2,…, bn). Якщо цей мінімум дорівнює aj (знаходиться серед ai), то j-та деталь обробляється першою. Якщо цей мінімум дорівнює bk (знаходиться серед bi), то k-та деталь обробляється останньою. Далі процедура повторюється.

Приклад. Маємо 5 деталей, задано час їх обробки на I-му та II-му верстатах.

I
ai (I верстат)
bi (II верстат)
Послідовність обробки

 

З часових осей бачимо, що час простою дорівнює 8 одиниць часу.

Задача розкладу для n деталей і трьох верстатів у загальному випадку не розв’язана. Але у випадку, коли min ai ≥ max bi або min ci ≥ min bi , де ai, bi, ci – це час обробки i-ї деталі відповідно на I, II і III верстатах, оптимальний порядок обробки деталей визначається за сумами ai+bi, і bi+ci, що зводиться до задачі про два верстати.

Питання для самоперевірки

1 Сформулюйте постановку задачі про розклад.

2 Опишіть алгоритм Джонсона для розв’язання задачі про розклад.

3 Для якого випадку застосовується цей алгоритм?

Задачі для самостійної роботи

1 Маємо 2 верстати і 10 деталей. Скласти розклад обробки.

I
ai (I)
bi (II)

2 Маємо три верстати і 5 деталей. Скласти розклад обробки.

I
ai (I)
bi (II)
ci (III)

 

Загрузка...

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти