По дисципліні «дослідження операцій» icon

По дисципліні «дослідження операцій»




НазваПо дисципліні «дослідження операцій»
Сторінка1/5
Дата26.06.2012
Розмір0.83 Mb.
ТипКонспект
  1   2   3   4   5

НАЦІОНАЛЬНА МЕТАЛУРГІЙНА АКАДЕМІЯ УКРАЇНИ


КАФЕДРА ПРИКЛАДНОЇ МАТЕМАТИКИ ТА ОБЧИСЛЮВАЛЬНОЇ ТЕХНІКИ


КОРОТКИЙ КОНСПЕКТ ЛЕКЦІЙ

Програма

Варіанти індивідуальних завдань

ПО ДИСЦИПЛІНІ

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

ДЛЯ НАПРЯМКУ

0502 - «Менеджмент»


Сост.: Швачич Г.Г., канд. технічних наук, доцент,

Христян В.И. ст.викл.


Дніпропетровськ

2008

ЦІЛЬ ДИСЦИПЛІНИ


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

Мета й задачі дисципліни: одержання теоретичних знань і практичних|практичных| навичок |с| формалізації задач керування з використанням спеціалізованих оптимізаційних методів.

Предмет: моделі й методи системного аналізу, способи дослідження й оптимізації операцій.


^ ПРОГРАМА КУРСУ


ЛЕКЦІЙНИЙ КУРС


Тема 1. Предмет дослідження операцій. Особливості застосування дослідження операцій при рішенні| задачі економіко-математичного моделювання

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


Тема 2. Складання|складывание,сдача| математичних моделей організаційних структур економіки і їхній аналіз

Задача планування виробництва і її математична модель. Задача складання|складывания,сдачи| раціону (задачі про дієту й суміші) і особливості її математичної моделі. Математична модель задачі про завантаження встаткування. Математичні моделі задач розкрою матеріалу. Аналіз математичних моделей з погляду ефективних методів їхнього рішення|решения|. Особливості складання |решения| математичних моделей у середовищах МАТНСАD і ЕХСЕL.


Тема 3. Моделі дискретного лінійного програмування (ЛП|)

Область застосування цілочисельних задач ЛП| у плануванні й керуванні виробництвом, їх математична постановка. Складання|складывание,сдача| математичних моделей задач цілочисельного програмування. Геометрична інтерпретація рішень на площині. Методи Гоморрі. Метод гілок і границь|. Особливості рішення|решения| задач дискретного програмування в середовищі ЕХСЕL.


Тема 4. Моделі нелінійного програмування (НП|)

Класичні методи нелінійного програмування. Економічна|экономичная| сутність і постановки окремих типів задач НП|. Графічний метод рішення задач НП|. Класичний метод оптимізації задач НП| методом множників Лагранжа, економічна|экономичная| інтерпретація. Особливості рішення задач НП| графічним методом і методом невизначених множників Лагранжа в середовищі МАТНСАD.

Опукле програмування. Опуклі функції. Задача опуклого програмування. Необхідні й достатні умови існування сідлової точки. Теорема Куна-Такера.

Градієнтні методи рішення задач НП|. Метод найшвидшого спуска. Метод сполучених градієнтів Флетчера-Ривса. Метод Давидона-Флетчера-Пауэла (ДФП|). Штрафні функції. Застосування методу| ДФП| для розв’язування задач із обмеженнями.

Прямі методи розв’язування задач НП|. Метод Пауэла. Метод Хука-Дживса. Особливості рішення задач у середовищах МАТНСАD й ЕХСЕL.

Методи випадкового пошуку при рішенні задач НП|. Методи випадкового пошуку з лінійною і нелінійною тактиками. Особливості аналізу математичних моделей у середовищах МАТНСАD й ЕХСЕL.


Тема 5. Сітьове планування й керування (СПК|)

Призначення й область застосування СПК|. Мережна модель і її основні елементи. Порядок і правила побудови сітьових графіків. Впорядкування сітьового графіка. Сітьове планування в умовах невизначеності. Аналіз й оптимізація сітьового графіка. Оптимізація сітьового графіка методом "час - вартість". Особливості рішення задач СПК| в середовищах МАТНСАD й ЕХСЕL.


Тема 6. Системи масового обслуговування (СМО|)

Основні поняття й визначення. Класифікація СМО|. Поняття марковського випадкового процесу. Потоки подій. Рівняння Колмогорова. СМО| з відмовами. СМО| з очікуванням. Поняття про статистичне моделювання СМО| (метод Монте-Карло). Особливості рішення задач у середовищах МАТНСАD й ЕХСЕL.


Тема 7. Моделі керування запасами|припасами|

Основні поняття й визначення. Статистична детермінована| модель без дефіциту. Статистична детермінована| модель із дефіцитом. Стохастичні моделі керування запасами|припасами|.


^ ТЕМИ ЛАБОРАТОРНИХ РОБІТ


  1. Складання|складывание,сдача| математичних моделей організаційних структур економіки.

  2. Моделі дискретного програмування.

  3. Моделі нелінійного програмування.

  4. Моделі сітьового планування.

  5. Системи масового обслуговування.

  6. Моделі керування запасами|припасами|.



ОРІЄНТОВНИЙ ПЕРЕЛІК|перечисление| ПИТАНЬ

^ ДЛЯ ПІДСУМКОВОГО КОНТРОЛЮ ЗНАНЬ


  1. Математична модель операції. Загальна постановка задачі дослідження операцій.

  2. Класифікація моделей і методів дослідження операцій. Приклади|приклады| задач, які|какие| вирішуються методами дослідження операцій.

  3. Задача планування виробництва і її математична модель.

  4. Задача складання|складывания,сдачи| раціону (задачі про дієту й суміші) і особливість її математичної моделі.

  5. Математична модель задачі про завантаження встаткування.

  6. Математичні моделі задач розкрою матеріалу.

  7. Аналіз математичних моделей з погляду ефективних методів їхнього рішення|решения|.

  8. Використання цілочисельних задач ЛП| у плануванні й керуванні виробництвом і їхньою математичною постановкою.

  9. Методи Гоморри.

  10. Метод гілок і границь|.

  11.  Класичний метод оптимізації задач НП.| Метод невизначених множників Лагранжа, економічна|экономичная| інтерпретація.

  12.  Теорема Куна-Такера.

  13. Метод найшвидшого спуска.

  14. Метод сполучених градієнтів Флетчера-Ривса.

  15. Метод Давидона-Флетчера-Пауела (ДФП|).

  16. Методи випадкового пошуку з лінійною й нелінійною тактиками.

  17. Мережна модель і її основні елементи. Порядок і правила побудови сіткових графіків.

  18. Системи масового обслуговування (СМО|). Основні поняття й визначення. Класифікація СМО|.

  19. Поняття про статистичне моделювання СМО| (метод Монте-Карло).

  20. Моделі керування запасами.

|припасами|..


^ 1. ЦІЛОЧИСЕЛЬНЕ ЛІНІЙНЕ ПРОГРАМУВАННЯ (ЦЛП)

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

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

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

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

Іншою класичною задачею такого типу є задача про ранець. Розглянемо формулювання цієї задачі. Є n предметів, при цьому відомо: aj – вага j-ого предмета, cj - цінність j-ого предмета, А – вантажопідйомність ранця. Необхідно завантажити ранець набором предметів максимальної цінності.

Складемо математичну модель задачі про ранець. На першому етапі введемо змінні:



У такому випадку функція цілі буде мати такий вигляд:

(1)

Задача вирішується в рамках наступних обмежень:

, (2)

.

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

У загальному випадку ЗЦЛП формулюється в такий спосіб: знайти оптимальний план , що забезпечує досягнення цільовою функцією екстремального значення:

. (3)

Задача вирішується в рамках обмежень:

(4)

(5)

(6)

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

Відомо, що экстремум ЗЛП досягається у вершинах опуклого багатогранного тіла, що є ОДР (областю припустимих рішень) задачі. Для ЦЗЛП значення экстремуму може досягатися в будь-якій вершині ОПР. Це означає, що методи розв’язування ЗЛП у раніше освітленому виді (у курсі математичного програмування) не можуть бути застосовані для рішення ЦЗЛП.

Проілюструємо сказане геометрично.




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

Отже, для рішення ЦЗЛП необхідно розглядати спеціальні методи.

Такі методи діляться на три основні групи:

I група - методи відсікання;

II група - комбінаторні методи (методи розсічення);

III група - наближені методи. У методах даної групи використовуються два основних підходи:

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

- застосування спрямованого випадкового пошуку з локальною оптимізацією.

^ МОДЕЛІ ЦЗЛП

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


Задача 1. З жерстин розміром 6 на13 необхідно виготовити 800 деталей розміром 4 на 5 і 400 деталей розміром 2 на 3. Скласти модель оптимізації розкрою матеріалу по:

а) min сумарних відходів;

б) min кількості використаних листів.

На першому етапі приведемо можливі варіанти розкрою матеріалу

1











































































































































































































































2











































































































































































































































3











































































































































































































































4













































































































































































































































Складемо таблицю, що характеризує кожний з отриманих результатів.




кількість деталей

відходи

№ вар.

45

23

1

0

13

0

2

1

9

4

3

2

6

2

4

3

1

2

кількість

деталей

800

400




На другому етапі складемо математичну модель задачі.

а) Задача оптимізації по мінімуму сумарних відходів.

Для складання математичної моделі введемо змінні х1, х2, х3, х4. Кожна з них відповідає кількості листів розміром 6 на13, які повинні розрізатися відповідним способом (1, 2, 3, 4). У цьому випадку функція цілі, що визначає мінімум відходів при відповідному розкрої, має вигляд



при обмеженнях







б) Задача оптимізації по мінімуму числа використаних листів



при обмеженнях







Задача 2. Є досить велика кількість колод довжиною 3 м. Колоди необхідно розпиляти на заготівки двох видів: довжиною l1 = 1,2 м і довжиною l2 = 0,9 м. Заготівки кожного виду необхідно одержати в кількостях не менш 50 й 81 штук відповідно. Кожна колода може бути розпиляна на зазначені заготівки декількома способами. Потрібно знайти мінімальне число колод, що розпилюють кожним способом для того, щоб одержати необхідне число заготівок.

Розглянемо можливі варіанти розпила колоди.

1
0,3
.

2.

3.


Зазначені варіанти представлені в таблиці.




число заготівок

відходи

№ вар.

l1

l2

1

0

3

0,3

2

1

2

0

3

2

0

0,6

кількість

заготівок

 50

 81




Далі складемо математичну модель задачі:

а) по min сумарної кількості розпиляних колод









б) по min кількості відходів









^ 2. КОМБІНАТОРНІ МЕТОДИ РОЗВ’ЯЗУВАННЯ ЦЗЛП

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

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

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

До комбінаторних методів відносять наступні методи розв’язування ЦЗЛП:

- адитивний алгоритм Балаша;

- алгоритм Літла, Муті, Суіні і Керела для розв’язування задачі комівояжера;

- метод неявного перебору (метод Джеферсона)

- метод Фора й Мальгаранжа.

  1   2   3   4   5

Схожі:

По дисципліні «дослідження операцій» iconКонтрольні домашні завдання по дисципліні «Дослідження операцій»

По дисципліні «дослідження операцій» iconКонтрольні домашні завдання по дисципліні «Дослідження операцій»

По дисципліні «дослідження операцій» iconI. Предмет І задачі дослідження операцій
Навчальний посібник являє собою конспект лекцій для студентів економічних фахів по однойменній дисципліні. У кожній главі розглядаються...
По дисципліні «дослідження операцій» iconПо дисципліні «дослідження операцій»
У ній найбільше чітко реалізуються основні ідеї вивчення математичних дисциплін на економічних спеціальностях|экономичном| – ідеї...
По дисципліні «дослідження операцій» iconТематичнийпла н по видах занять з курсу "Дослідження операцій"
Операція, основні поняття І якості. Прямі та зворотні задачі. Управління операцією, оцінка якості. Математичні моделі операцій. Допустимі...
По дисципліні «дослідження операцій» iconЗвіт до лабораторної роботи №5 «Дослідження залежності показників діяльності людини-оператора від структур алгоритмів діяльності та способів виконання операцій»
...
По дисципліні «дослідження операцій» iconЗвіт до лабораторної роботи №5 «Дослідження залежності показників діяльності людини-оператора від структур алгоритмів діяльності та способів виконання операцій»
...
По дисципліні «дослідження операцій» iconПара 6/18/2013
Дослідження операцій в транспортних системах, корп. 4, ауд. 1-7А, Пристінський М. Г., Екзамен
По дисципліні «дослідження операцій» iconМетодичні вказівки щодо виконання контрольної роботи з навчальної дисципліни " дослідження операцій" для студентів заочної форми навчання
Методичні вказівки щодо виконання контрольної роботи з навчальної дисципліни „Дослідження операцій” для студентів заочної форми навчання...
По дисципліні «дослідження операцій» iconПитання з дисциплини «дослідження операцій»
Розподіл капіталовкладень між підприємствами; постановка задачі, функціональні рівняння
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи