Зміст навчального посібника ВІДПОВідає навчальній програмі дисципліни "Математичне програмування" загального курсу "Економіко-математичне моделювання" для студентів економічних спеціальностей вищих навчальних закладів. Крім теоретичного матеріалу, в навчальному посібнику розглядається практична сторона вивчення математичного програмування. У кінці кожного розділу наведено висновки та контрольні запитання. Усі алгоритми розв'язування задач наведено у вигляді блок-схем і рекомендовано для вивчення методів оптимізації. Така форма наочна, зручна і сприяє широкому використанню цих методів для пошуку оптимальних варіантів. ЗМІСТ Передмова ……………………………………………………6 Вступ ………………………………………………………………………………………..7 Розділ 1. Загальна задача лінійного програмування …………………………………………………..11 1.1. Основні означення ……………………………………………………………………………………………….…….12 1.2. Загальна характеристика задач лінійкою програмування …………………………………………………………..14 1.3. Основні типи прикладних задач лінійного програмування ……………………………………………………17 1.3.1. Задача на суміш ………………………………………………17 1.3.2. Транспортна-задача ……………………………………………………………………………………..19 1.4. Графічний метод ………………………………………………………………..21 1.5. Симплексний метод ……………………………………………………………………………….25 і .5.1. Основна ідея методу ……………………………………………..25 1.5.2. Умови оптимальності ……………………………………………………………………………………………27 1.5.3. Розширена форма математичної моделі ……………………………………………..28 1.5.4. Початковий базисний розв'язок ………………………………………………………………………………….31 1.5.5. Алгоритм перетворення ……………………………………………..33 1.5.6. Альтернативний оптимум ………………………………………………………………………………37 1.5.7. Випадок виродження та зациклювання …………………………………………………………………………41 1.6. Рекомендації щодо розв'язування задачі лінійного програмування …………………………………………………42 Висновки ……………………………………………...43 Контрольні запитання ………………………………………………………………………………….44 Розділ 2. Двоїсті задачі лінійного програмування …………………………………………...…45 2.1. Взаємно двоїсті задачі ………………………………………………………………………………………………….45 2.2. Алгоритм перетворення ………………………………………………………………………………………………..46 2.3. Математичні моделі двоїстої пари задач га приклади їх побудови ………………………………………..47 2.4. Економічний зміст двоїстої пари задач ……………………………………………………………………………….50 2.5. Теореми двоїстості …………………………………………..52 2.6. Розв'язування двоїстої задачі …………………………………………...53 2.7. Двоїстий симплекс-метод …………………………………………………56 2.8. Двоїсті оцінки …………………………………………………….60 2.8.1. Міра дефіциту ресурсів ……………………………………………………….60 2.8.2. Вплив зміни величини початковій ресурсів на цільову функцію …………………………………………......61 2.8.3. Аналіз рентабельності виготовлення продукції ……………………………………………………………….62 2.8.4. Аналіз на взаємозаміну ресурсів ………………………………………………………………………………..63 2.8.5. Аналіз доцільності розширення асортименту продукції, що випускається…………………………………64 Висновки ………………………………………65 Контрольні запитання ………………………………………………………………………………………………66 Розділ 3. Транспортна задача …………………………………………………………………………….67 3.1. Властивості га типи транспортних задач …………………………………………………….67 3.2. Умови оптимальності …………………………………………………………………………………………………..69 3.3. Випадок виродження ……………………………………………70 1.7. Метод розв'язування транспортної задачі ……………………………………………………………………...71 1.3.3. Діагональний спосіб ………………………………………………………………………………………72 1.3.4. Спосіб мінімального елемента ……………………………………………………………………………73 1.3.5. Спосіб подвійних позначок ……………………………………………………………………………….74 1.3.6. Аналіз плану на оптимальність ………………………………………………………………………......74 1.3.7. Побудова циклу перерозподілу ресурсів ………………………………………………………………...75 1.3.8. Знаходження нового плану розподілу ресурсів …………………………………………………………77 1.8. Альтернативний оптимум …………………………………………………………………….79 1.9. Рекомендації щодо розв'язування ………………………………………………………………………………83 Висновки ……………………………………………………………………………………………………………….84 Контрольні запитання ………………………………………………………………………..84 Розділ 4. Параметричне програмування …………………………………………………………………….86 Економічна інтерпретація задач параметричного програмування ………………………………………………86 Типи задач параметричного програмування ……………………………………………………………………….87 Геометрична інтерпретація …………………………………………………………………………………………89 Розв'язування задач ……………………………………………….90 Інші типи задач ……………………………………………….97 Висновки ……………………………………………98 Контрольні запитання ………………………………………………………………………98 Розділ 5. Елементи теорії ігор ………………………………………………………………………………..99 Загальна характеристика та класифікація ігрових задач …………………………………………………………99 Матрична гра з нульовою сумою …………………………………………………………………………………101 Мішані стратегії ………………………………………………105 Розв'язування матричної гри ……………………………………………………………………………..107 1.5.7. Графічний метод ……………………………………………………………………………..307 1.5.7. Зведення матричної гри з кульовою сумою до задач лінійного програмування……………………110 Висновки …………………………………………………………………….115 Контрольні запитання ………………………………………………………………………………………………………... 115 Розділ 6. Елементи динамічного програмування …………………………………………………………...116 2.9. Основні властивості задач динамічного програмування та недоліки Методу……………………………………………………………………………………………………………116 2.10. Загальна математична модель ………………………………………………..119 2.11. Розв'язування дискретних задач ………………………………………………………………………………120 2.8.6. Рекурентне співвідношенню ……………………………………………….120 2.8.7. Таблиця оптимальних розв'язків ………………………………………………………………………..124 2.8.8. Приклад ……………………………………………………………………………………………..125 2.12. Випадок двосторонніх обмежені на змінні …………………………………………………………………..130 2.13. Задачі з багатьма видами ресурсів ……………………………………………………………………………130 2.14. Неперервні моделі ……………………………………………………………………….......131 2.15. Задача управління запасами …………………………………………………………………………………...132 Висновки ……………………………………………………………………………………………………………...133 Контрольні запитання …………………………………………………………………………………………134 Розділ 7. Дискретне програмування …………………………………………………………………………135 1.9. Класифікація задач дискретного програмування …………………………………………………………………...135 1.9. Лінійні цілочислові задачі ……………………………………………………………………137 1.9. Метод відтинання. Додаткове обмеження …………………………………………………………………….137 1.9. Перший алгоритм Гоморі ……………………………………………………………………………………….139 1.9. Приклад ……………………………………………………………………………………………………………142 1.9. Задачі з бульовими змінними ………………………………………………………………………………….144 1.9. Задача про призначення ………………………………………………144 1.9. Угорський метод ………………………………………………………………………………………………...145 1.9. Приклад ……………………………………………………………………………………………………………147 1.9. Задача про кільцевий маршрут …………………………………………………….149 7.3, 5. Метод розгалужень і меж ……………………………………………………………………………………….151 7.3.6. Приклад …………………………………………………………………………………..154 Висновки ………………………………………………………………………………………….159 Контрольні запитання …………………………………………………………………………………………………………………160 Розділ 8. Програмування на мережах ………………………………………………………………………..161 Основні поняття теорії графів ……………………………………………………………………………………………..161 Засоби завдання графів. Зважені графи та мережі ……………………………………………………………………….163 Потоки на мережах. Поняття розрізу …………………………………………………………………………...164 Задача про максимальний потік …………………………………………………………………………………………...166 1.5.8. Загальна постановка …………………………………………………….166 1.5.9. Алгоритм Форда-Фалкерсона …………………………………………………………………………………..167 1.5.10. Приклад …………………………………………………………………………………………………………...169 Задача про найкоротшу відстань …………………………………………………………………………………………..171 2.16. Загальна постановка …………………………………………………………………………………………….171 2.17. Алгоритм розв'язування ………………………………………………………………………………………...172 2.18. Приклад………………………………………………………………………………………………………….174 Транспортна задача у сітьовій постановці ………………………………………………..175 Висновки…………………………………………………………………………………………………………………………………..178 Контрольні запитання ………………………………………………..178 Розділ 9. Нелінійне програмування ………………………………………………………………….………179 Властивості нелінійних задач …………………………………………………………………………….179 Деякі питання та визначення ………………………………………………………………………………………………182 Задачі опуклого програмування …………………………………………………………………………………………..183 Аналіз цільової функції на екстремум ……………………………………………………………………………………184 Алгоритми розв'язку найпростіших нелінійних задач ………………………………………………………….186 3.4. Метод множників Лаграижа ………………………………………………………………………..186 3.5. Градієнтні методи ……………………………………………………………………………………………….187 Висновки …………………………………………………………………………………………………………………….198 Контрольні запитання ……………………………………………………………….198 Рекомендована література.... ……………………………………………..199