НМетАУКАФЕДРА ПРИКЛАДНОЇ МАТЕМАТИКИ ТА ОБЧИСЛЮВАЛЬНОЇ ТЕХНІКИМетодичні вказівкищодо вивчення дисципліни"Оптимізаційні методи та моделі ”для студентів економічних спеціальностейЗатверджено на засіданні кафедри Протокол № 1 від 01.09.2011 р.1Дніпропетровськ 2011 Методичні вказівки щодо вивчення дисципліни ""Оптимізаційні методи та моделі” ”/ Укл.: Г.Г. Швачич, О.В. Соболенко, В.І. Христян – Дніпропетровськ: НМетАУ, 2010. – 27 с.Укладачі: Г.Г. Швачич, канд. техн. наук, проф.., О.В. Соболенко, канд. техн. наук, доц., В.І.Христян, ст. викл.Відповідальна за випуск: Г.Г. Швачич, канд. техн. наук, проф.., зав. каф. ПМ та ОТ ^ 1. МЕТА ДИСЦИПЛІНИ"Оптимізаційні методи та моделі” – дисципліна, яка має досить важливе методологічне значення в системі підготовки сучасного економіста. В ній найбільш чітко реалізується одна із основних ідей вивчення математичних дисциплін в економічному вузі – ідея моделювання економічних процесів, обґрунтування рішень, які приймаються в результаті керування організаційними структурами.Мета та задачі дисципліни: одержання теоретичних знань і практичних навичок з формалізації задач управління з використанням спеціалізованих оптимізаційних методів.Предмет: моделі та методи системного аналізу, способи дослідження та оптимізації операцій.^ 2. ЗМІСТ ДИСЦИПЛІНИТема 1. Предмет дисципліни. Особливості застосування дисципліни при розв'язуванні задачі економіко-математичного моделювання Предмет, об'єкт, завдання та методологічні засади дисципліни. Загальна постанова задачі дослідження операцій. Операції та їх ефективність. Математична модель операції. Класифікація моделей та методів дослідження операцій. Приклади задач, які розв'язуються методами дослідження операцій.Тема 2. Складання математичних моделей організаційних структур економіки та їх аналіз Задача планування виробництвом та її математична модель. Задача складання раціону (задачі про дієту та суміші) та особливість її математичної моделі. Математична модель задачі про завантаження обладнання. Математичні моделі задач розкроювання матеріалу. Аналіз математичних моделей з точки зору ефективних методів їх розв'язування. Особливості розв'язування математичних моделей в середовищах МАТНСАD та ЕХСЕL.Тема 3. Моделі дискретного лінійного програмування (ЛП) Область застосування цілочисельних задач ЛП у плануванні і управлінні виробництвом та їх математична постановка. Складання математичних моделей задач цілочисельного програмування. Геометрична інтерпретація розв'язків на площині. Методи Гоморі. Метод гілок та границь. Особливості розв'язування задач дискретного програмування в середовищі ЕХСЕL.Тема 4. Моделі нелінійного програмування (НП)Класичні методи нелінійного програмування. Економічна сутність і постанова окремих типів задач НП. Графічний метод розв'язування задач НП. Класичний метод оптимізації задач НП методом множників Лагранжа, економічна інтерпретація. Особливості розв'язування задач НП графічним методом та методом невизначених множників Лагранжа в середовищі МАТНСАD.Опукле програмування. Опуклі функції. Задача опуклого програмування. Необхідні та достатні умови існування сідлової точки. Теорема Куна-Такера.Градієнтні методи розв'язування задач НП. Метод найшвидшого спуску. Метод спряжених градієнтів Флетчера-Рівса. Метод Давидона-Флетчера-Пауела (ДФП). Штрафні функції. Застосування метода ДФП до розв'язку задач з обмеженнями.Прямі методи розв'язування задач НП. Метод Пауела. Метод Хука-Дживса. Особливості розв'язування задач в середовищах МАТНСАD та ЕХСЕL.Методи випадкового пошуку для розв'язування задач НП. Методи випадкового пошуку з лінійною та нелінійною тактиками. Особливості аналізу математичних моделей в середовищах МАТНСАD та ЕХСЕL.Тема 5. Сітьове планування та керування (СПК) Призначення та область застосування СПК. Сітьова модель та її основні елементи. Порядок та правила побудови сітьових графіків. Впорядкування сітьового графіку. Сітьове планування в умовах невизначеності. Аналіз та оптимізація сітьового графіку. Оптимізація сітьового графіку за методом "час - вартість". Особливості розв'язування математичних моделей СПК в середовищах МАТНСАD та ЕХСЕL.Тема 6. Системи масового обслуговування (СМО) Основні поняття та означення. Класифікація СМО. Поняття марківського випадкового процесу. Потоки подій. Рівняння Колмогорова. СМО з відмовами. СМО з очікуванням. Поняття про статистичне моделювання СМО (метод Монте-Карло). Особливості розв'язування математичних моделей в середовищах МАТНСАD та ЕХСЕL.Тема 7. Моделі керування запасами Основні поняття та означення. Статистична детермінована модель без дефіциту. Статистична детермінована модель з дефіцитом. Стохастичні моделі керування запасами.^ 3. ТЕМИ ПРАКТИЧНИХ ЗАНЯТЬ Складання математичних моделей організаційних структур економіки. Моделі дискретного програмування. Моделі нелінійного програмування. Моделі сітьового планування. Системи масового обслуговування. Моделі керування запасами.^ 4. ОРІЄНТОВНИЙ ПЕРЕЛІК ПИТАНЬДЛЯ ПІДСУМКОВОГО КОНТРОЛЮ ЗНАНЬ (залік) Математична модель операції. Загальна постанова задачі дослідження операцій. Класифікація моделей та методів дослідження операцій. Приклади задач, які розв'язуються методами дослідження операцій. Задача планування виробництвом та її математична модель. Задача складання раціону (задачі про дієту та суміші) та особливість її математичної моделі. Математична модель задачі про завантаження обладнання. Математичні моделі задач розкроювання матеріалу. Аналіз математичних моделей з точки зору ефективних методів їх розв'язування. Область застосування цілочисельних задач ЛП у плануванні і управлінні виробництвом та їх математична постановка. Методи Гоморі.. Метод гілок та границь. Класичний метод оптимізації задач НП методом множників Лагранжа, економічна інтерпретація. Теорема Куна-Такера. Метод найшвидшого спуску. Метод спряжених градієнтів Флетчера-Рівса. Метод Давидона-Флетчера-Пауела (ДФП). Методи випадкового пошуку з лінійною та нелінійною тактиками. Сітьова модель та її основні елементи. Порядок та правила побудови сітьових графіків. Системи масового обслуговування (СМО).Основні поняття та означення. Класифікація СМО. Поняття про статистичне моделювання СМО (метод Монте-Карло). Моделі керування запасами^ 5. МЕТОДИЧНІ ВКАЗІВКИ ЩОДО ВИКОНАННЯ КОНТРОЛЬНОЇ РОБОТИНавчальним планом з дисципліни "Дослідження операцій" передбачено виконання контрольної роботи. Кількість задач контрольної роботи визначається викладачем. Перед розв’язуванням задач необхідно вивчити відповідний розділ теоретичного матеріалу. При виконанні контрольної роботи студент повинний дотримувати таких правил: Кількість завдань контрольної роботи визначається викладачем. Титульна сторінка роботи оформлюється за зразком, наведеним нижче. Контрольна робота виконується в зошиті, в якому необхідно залишити поля для зауважень рецензента і кілька чистих аркушів для доповнень і відповідей на ці зауваження. Розв’язування кожної задачі треба починати з наведення її повної умови. Рішення задач необхідно супроводжувати поясненнями, графіками та посиланнями на відповідні теоретичні поняття та формули. Якщо контрольна робота після перевірки не зарахована, треба виправити помилки згідно з зауваженнями викладача. Це необхідно робити у кінці роботи (або в окремому зошиті), написавши спочатку титул “Робота над помилками”. Вносити зміни до тексту вже перевіреної роботи категорично забороняється. Доопрацьована контрольна робота надсилається для повторної перевірки разом з першим варіантом. Студент, що не виконав контрольну роботу, до заліку не допускається.^ 6. Вибір варіантів контрольних робітНомер варіанту контрольної роботи обирається згідно з двома останніми цифрами залікової книжки, або студентського квитка. При чому, якщо цей номер перевищує цифру 50, то номер контрольної роботи визначається наступним чином: від цифри 100 віднімається цифра, що відповідає двома останніми цифрами залікової книжки, або студентського квитка. Наприклад, якщо номер двох останніх цифр залікової книжки відповідає цифрі 48, то студент виконує 48 варіант. В разі, коли номер двох останніх цифр залікової книжки 85, то варіант контрольної роботи обирається наступним чином: 100-85=15 і студент виконує 15 варіант контрольної роботи.6. ЛІТЕРАТУРА6.1. Основна Кремер Н.Ш. Исследование операций в экономике. - М.: Банки и биржи, 1997. Вагнер Г. Исследование операций.- В 3 - х томах. - М.: Мир, 1973. Вентцель Е.С. Исследование операций. Задачи, принципы, методология.– М. Наука, 1980. Горелик В.А., Ушаков В.А. Исследование операций. - М.: Машиностроение, 1996. Зайченко Ю.П. Исследование операций. - К.: Высшая школа, 1985. Зайченко Ю.П., Шумилова С.А. Исследование операций (сборник задач). – К.: Высшая школа, 1984.6.2. Додаткова Горчаков А.А., Орлова И.В. Компьютерные экономико-математические модели. М.: Компьютер, ЮНИТИ, 1995. Хедли Дж. Нелинейное и динамическое программирование. - М.:Мир, 1967. Щедрин Н.И., Кархов А.Н. Математические методы программирования в экономике. - М.: Статистика, 1974. Швачич Г.Г. Лінійна алгебра в розрахунках середовища МАТНСАD: Підручник. - Дніпропетровськ: ДАУБП, 2000.Додаток 1^ ТАБЛИЦЯ ВАРІАНТІВ ЗАВДАНЬ № варіанта Номери задач 0 1.6 2.10 3.4 4.1 5.6 6.6 1 1.3 2.2 3.9 4.2 5.4 6.2 2 1.10 2.8 3.4 4.4 5.3 6.4 3 1.2 2.4 3.3 4.5 5.1 6.8 4 1.4 2.6 3.10 4.7 5.9 6.9 5 1.9 2.5 3.5 4.8 5.7 6.3 6 1.2 2.3 3.9 4.9 5.8 6.1 7 1.5 2.1 3.4 4.6 5.2 6.7 8 1.4 2.9 3.8 4.3 5.5 6.5 9 1.10 2.7 3.3 4.10 5.4 6.10 10 1.8 2.10 3.4 4.2 5.6 6.5 11 1.6 2.1 3.9 4.5 5.10 6.4 12 1.1 2.5 3.2 4.8 5.2 6.6 15 1.8 2.9 3.7 4.3 5.4 6.1 14 1.3 2.7 3.6 4.6 5.9 6.3 15 1.4 2.5 3.1 4.9 5.6 6.7 16 1.6 2.3 3.8 4.1 5.7 6.9 17 1.7 2.2 3.10 4.4 5.3 6.8 18 1.10 2.8 3.1 4.7 5.1 6.5 19 1.4 2.4 3.6 4.8 5.5 6.2 20 1.9 2.6 3.7 4.9 5.3 6.10 21 1.4 2.5 3.9 4.6 5.1 6.6 22 1.7 2.2 3.5 4.3 5.6 6.1 23 1.3 2.8 3.4 4.2 5.4 6.7 24 1.1 2.10 3.9 4.1 5.5 6.2 25 1.6 2.1 3.3 4.4 5.4 6.9 26 1.5 2.3 3.1 4.7 5.9 6.4 27 1.10 2.4 3.5 4.10 5.7 6.3 28 1.1 2.9 3.2 4.2 5.8 6.10 29 1.8 2.7 3.6 4.5 5.5 6.9 30 1.2 2.3 3.5 4.4 5.7 6.3 31 1.5 2.1 3.3 4.9 5.2 6.5 32 1.3 2.5 3.7 4.1 5.1 6.8 33 1.4 2.9 3.9 4.3 5.3 6.3 34 1.4 2.10 3.10 4.2 5.8 6.1 35 1.6 2.6 3.1 4.8 5.9 6.7 36 1.7 2.1 3.1 4.3 5.3 6.5 37 1.10 2.9 3.8 4.6 5.1 6.10 38 1.4 2.7 3.10 4.9 5.5 6.5 39 1.9 2.5 3.1 4.1 5.3 6.4 40 1.4 2.3 3.6 4.4 5.1 6.6 41 1.5 2.2 3.7 4.7 5.6 6.1 42 1.4 2.8 3.9 4.8 5.4 6.3 43 1.10 2.4 3.5 4.9 5.5 6.7 44 1.8 2.6 3.4 4.6 5.4 6.9 45 1.6 2.5 3.9 4.3 5.9 6.8 46 1.1 2.2 3.3 4.2 5.7 6.5 47 1.8 2.8 3.1 4.1 5.8 6.6 49 1.3 2.3 3.5 4.4 5.3 6.3 49 1.4 2.5 3.2 4.7 5.7 6.2 50 1.6 2.7 3.8 4.10 5.2 6.10 Додаток 2^ ЗАДАЧІ КОНТРОЛЬНОЇ РОБОТИЗАДАЧА 1 Із листів металу розміру mxn необхідно виготовити N заготовок розміру m1xn1 та М заготовок розміру m2xn2. Скласти модель оптимізації розкроювання металу за мінімумом загальних відходів. № зад. m n N m1 n1 M m2 n2 1.1. 7 14 900 5 6 500 3 4 1.2. 6 14 800 3 5 400 2 4 1.3. 5 15 700 2 4 300 3 3 1.4. 6 15 600 3 4 400 3 5 1.5. 7 16 500 3 5 300 2 4 1.6. 8 17 400 4 6 400 3 5 1.7. 9 18 300 5 7 400 2 4 1.8. 8 19 350 6 8 370 5 7 1.9. 9 20 500 5 7 400 4 6 1.10. 10 20 500 5 6 450 3 5 ЗАДАЧА 2 В столярній майстерні мають в достатній кількості колод довжиною l метрів. Колоди необхідно розпиляти на заготовки двох видів: довжиною l1 та довжиною l2 метрів відповідно. Кожної подоби необхідно заготовити не менше m та n штук відповідно. Скласти модель оптимізації розпилювання колод за: мінімумом загальних відходів; мінімумом числа використаних колод. № зад. l l1 l2 m n 2.1 4 2 1,5 50 80 2.2 5 3 2 40 70 2.3 6 2,4 1,2 3 50 2.4 6 3 1,8 40 30 2.5 6 2,5 3,2 50 40 2.6 6 3 1,5 40 80 2.7 6 3,4 1,2 50 80 2.8 5 1,2 0,8 40 60 2.9 5 1,4 0,7 30 20 2.10 5 1,6 0,5 40 50 ЗАДАЧА 3 Знайти оптимальний розв’язок задачі цілочисельного лінійного програмування:3.1. 3.2. 3.3. 3.4. 3.5. 3.6. 3.7. 3.8.3.9. 3.10.ЗАДАЧА 4 Розв’язати задачу дробово-лінійного програмування4.1. 4.2.4.3. 4.4. 4.5. 4.6.4.7. 4.8. 4.9. 4.10.ЗАДАЧА 5 За методом Лагранжа знайти точку умовного екстремуму функції5.1. 5.2.5.3. 5.4.5.5. 5.6.5.7. 5.8. 5.9. 5.10. ЗАДАЧА 6Розв’язати задачу нелінійного програмування графічним методом6.1. 6.2. 6.3. 6.4.6.5. 6.6.6.7. 6.8. 6.9. 6.10. Навчальне виданняМетодичні вказівки щодо вивчення дисципліни "Оптимізаційні методи та моделі" Підписано до друку ________ Формат 60х84/16. Ум. друк. арк. Оперативна поліграфія. Зам. № ____. Тираж ____ прим.НМетАУ 49000, м. Дніпропетровськ, пр. Гагаріна,4.