Пропонований підручник складається з трьох розділів: "Моделі та методи лінійного, дискретного та динамічного програмування", "Моделі та методи нелінійного програмування" та "Використання пакетів прикладних програм у математичному програмуванні". У перших двох розділах викладено теоретичні основи розв'язування відповідного типу задач та методи їх економіко-математичного аналізу, розглянуто приклади застосовування цих методів. До кожної глави додається навчальний тренінг, у якому запропоновано контрольні запитання і завдання для самостійної роботи. Пакети прикладних програм, наведені у третьому розділі, показують можливості сучасних інформаційних технологій у розв'язуванні задач математичного програмування. Імітаційне моделювання, теорія ігор, теорія масового обслуговування, теорії управління запасами, методи мережевого планування та управління як складові курсу "Дослідження операцій" буде розглянуто у наступній книзі, яка нині готується авторами до друку. Для студентів і аспірантів економічних спеціальностей та спеціальності "Прикладна математика". Книга буде корисною також викладачам вищих навчальних закладів, науковцям, всім, кого цікавлять методи оптимізації соціально-економічних систем. ЗМІСТ ПЕРЕДМОВА 11 ВСТУП 15 РОЗДІЛ І. МОДЕЛІ ТА МЕТОДИ ЛІНІЙНОГО, ДИСКРЕТНОГО ТА ДИНАМІЧНОГО ПРОГРАМУВАННЯ 23 Глава 1. МОДЕЛІ ЛІНІЙНОГО ПРОГРАМУВАННЯ ТА МЕТОДИ ЇХ КІЛЬКІСНОГО АНАЛІЗУ 23 1.1. Загальна задача лінійного програмування 23 1.2. Геометрична інтерпретація: задачі лінійного програмування 28 1.3. Властивості допустимої множини та множини розв'язків задачі лінійного програмування 33 1.4. Симплекс-метод 37 1.4.1. Обґрунтування симплекс-методу для невироджених задач лінійного програмування 37 1.4.2. Алгоритм симплекс-методу та його реалізація за допомогою симплекс-таблиць 51 1.5. Знаходження початкового базисного розв'язку задачі лінійного програмування 62 1.6. Поняття виродженості задач лінійного програмування та спосіб усунення зациклювання у симплекс-методі 70 1.7. Модифікований симплекс-метод 74 Навчальний тренінг 81 Глава 2. МОДЕЛІ ЛІНІЙНОГО ПРОГРАМУВАННЯ ТА МЕТОДИ ЇХ ЯКІСНОГО ЕКОНОМІКО-МАТЕМАТИЧНОГО АНАЛІЗУ 90 2.1. Основи теорії двоїстості та їх економічна інтерпретація 90 2.1.1. Пара двоїстих задач та їх економічна інтерпретація 90 2.1.2. Теореми двоїстості та їх економічна інтерпретація 94 2.1.3. Економіко-математичний аналіз оптимального розв'язку задач лінійного програмування: 105 2.2. Двоїстий симплекс-метод 111 2.3. Аналіз чутливості розв'язку задач лінійного програмування 121 2.4. Параметричне програмування 131 2.4.1. Параметричні зміни коефіцієнтів цільової функції 132 2.4.2. Параметричні зміни коефіцієнтів правої частини обмежень 136 Навчальний тренінг 140 Глава 3. СПЕЦІАЛЬНІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ ТА МЕТОДИ ЇХ РОЗВ'ЯЗУВАННЯ 146 3.1. Транспортна задача 146 3.1.1. Постановка та математична модель транспортної задачі 146 3.1.2. Розв'язування транспортної задачі 152 3.2. Задача про призначення 162 3.3. Динамічне програмування 172 3.3.1. Вступ до динамічного програмування 172 3.3.2. Рекурентні співвідношення динамічного програмування 173 3.3.3. Обчислювальний алгоритм 175 3.3.4. Метод динамічного програмування за наявності двох обмежень 182 3.3.5. Задача про заміну обладнання 183 3.4. Задачі лінійного програмування великої розмірності 187 3.4.1. Характеристика підході]} до розв'язування задач великої розмірності 187 3.4.2. Метод декомпозиції Данцига - Вульфа 189 Навчальний тренінг 208 Глава 4. МОДЕЛІ ТА МЕТОДИ ДИСКРЕТНОГО ЛІНІЙНОГО ПРОГРАМУВАННЯ 217 4.1. Загальна задача дискретного програмування та її різновиди 217 4.2. Характеристика методів розв'язування задач дискретного програмування 223 4.3. Методи відтинання 225 4.3.1. Перший алгоритм Гоморі 225 4.3.2. Другий алгоритм Гоморі 230 4.3.3. Алгоритм Дальтона - Ллевеліна 233 4.3.4. Третій алгоритм Гоморі 237 4.4. Комбінаторні методи 241 4.4.1. Метод гілок та меж 241 4.4.2. Метод гілок та меж для задачі комівояжера 249 4.4.3. Адитивний алгоритм 257 4.5. Наближені методи 263 4.5.1. Методи випадкового пошуку 263 4.5.2. Детерміновані наближені методи 272 Навчальний тренінг 276 РОЗДІЛ II. МОДЕЛІ ТА МЕТОДИ НЕ ЛІНІЙНОГО ПРОГРАМУВАННЯ 285 Глава 5. ЕКОНОМІЧНІ ПРОБЛЕМИ, ЯКІ ПРИВОДЯТЬ ДО НЕЛІНІЙНОСТЕЙ. ОСОБЛИВОСТІ РОЗВ'ЯЗУВАННЯ НЕЛІНІЙНИХ ЗАДАЧ 285 5.1. Приклади економічних задач, які приводять до моделей нелінійного типу 285 5.2. Загальна постановка задач нелінійної оптимізації та їх класифікація 289 5.3. Геометрична інтерпретація задачі нелінійного програмування у випадку функції двох змінних 289 5.4. Труднощі розв'язування нелінійних задач 291 Навчальний тренінг , 295 Глава 6. ЕЛЕМЕНТИ ОПУКЛОГО АНАЛІЗУ ТА ТЕОРЕТИЧНІ ОСНОВИ ОПУКЛОГО ПРОГРАМУВАННЯ 299 6.1. Опуклі множини та їх властивості 299 6.2. Опуклі функції та їх властивості 303 6.3. Ідентифікація оптимального розв'язку 307 6.4. Метод множників Лагранжа для розв'язування нелінійних задач з обмеженнями 314 Навчальний тренінг 317 Глава 7. МЕТОДИ ОДНОВИМІРНОЇ ОПТИМІЗАЦІЇ 322 7.1. Постановка задачі 322 7.2. Метод ділення відрізка навпіл 323 7.3. Метод золотого перерізу 324 7.4. Метод Пауелла 328 7.5. Метод Девіса, Свена та Кемпі 330 Навчальний тренінг 334 Глава 8. МЕТОДИ РОЗВ'ЯЗУВАННЯ ЗАДАЧ БЕЗУМОВНОЇ ОПТИМІЗАЦЙ 336 8.1. Градієнтні методи 338 8.2. Методи покоординатного спуску 345 8.3. Метод Ньютона 350 8.4. Метод спряжених напрямків 357 8.4.1. Загальна схема методів спряжених напрямків 357 8.4.2. Метод спряжених градієнтів Флетчера - Рівса 357 Навчальний тренінг 363 Глава 9. МЕТОДИ РОЗВ'ЯЗУВАННЯ ЗАДАЧ УМОВНОЇ ОПТИМІЗАЦІЇ 365 9.1. Методи можливих напрямків 366 9.2. Метод відтинаючих гіперплощин 372 9.3. Метод лінеаризації 376 9.4. Методи штрафних функцій 382 9.4.1. Метод зовнішніх штрафів 384 9.4.2. Метод внутрішніх штрафів 386 Навчальний тренінг 390 Глава 10. МЕТОДИ КВАДРАТИЧНОГО ПРОГРАМУВАННЯ 395 10.1. Постановка задачі квадратичного програмування та застосування теорії опуклого аналізу для її розв'язування……...395 10.2. Квадратичний симплекс-метод 402 Навчальний тренінг 406 Глава 11. ЗАДАЧІ СЕПАРАБЕЛЬНОГО ПРОГРАМУВАННЯ ТА МЕТОДИ ЇХ РОЗВ'ЯЗУВАННЯ 408 11.1. Постановка задачі сепарабельного програмування та ідея її розв'язування 408 11.2. Побудова апроксимуючої задачі та визначення локального максимуму 409 Навчальний тренінг 418 Глава 12. МЕТОДИ ОПТИМІЗАЦЙ НЕГЛАДКИХ ФУНКЦІЙ 420 12.1. Узагальнений градієнт 420 12.2. Методи узагальнених градієнтів 426 Навчальний тренінг 429 Глава 13. СТОХАСТИЧНЕ ПРОГРАМУВАННЯ 431 13.1. Необхідність застосування стохастичного підходу при економічному плануванні 431 13.2. Методи врахування випадкового характеру вхідних даних у математичних моделях 432 13.3. Двохетапна задача стохастичного програмування 435 13.4. Чисельні методи стохастичного програмування 438 13.5. Методи розв'язування двохетапної стохастичної задачі 443 13.6. Методи якісного аналізу н стохастичному програмуванні 44 5 Навчальний тренінг 450 РОЗДІЛ III. ВИКОРИСТАННЯ ПАКЕТІВ ПРИКЛАДНИХ ПРОГРАМ У МАТЕМАТИЧНОМУ ПРОГРАМУВАННІ 456 Глава 14. МАТЕМАТИЧНІ ПАКЕТИ ПРИКЛАДНИХ ПРОГРАМ 457 14.1. Система МАТНЕМАТІСА5 460 14.1.1. Реалізація методів безумовної оптимізації 458 14.1.2. Реалізація методів умовної оптимізації 464 14.1.3. Лінійна оптимізація 467 14.2. Система MAPLE9 470 14.2.1. Реалізація методів безумовної оптимізації 474 14.2.2. Реалізація методів умовної оптимізації 476 14.2.3. Лінійна оптимізація 480 14.3. Система MATHCAD11 487 14.3.1. Реалізація методів безумовної оптимізації 490 14.3.2. Реалізація методів умовної оптимізації 491 14.3.3. Застосування додаткового пакета оптимізації 495 14.4. Узагальнення 497 Навчальний тренінг 499 Глава 15. СУЧАСНІ ТАБЛИЧНІ ПРОЦЕСОРИ 500 15.1. Система Excel 501 15.1.1. Реалізація методів оптимізації 503 15.1.2. Лінійна оптимізація 510 Навчальний тренінг 515 Глава 16. СПЕЦІАЛІЗОВАНІ ПАКЕТИ ОПТИМІЗАЦІЇ ТА ПРИКЛАДНІ ПРОГРАМИ 516 16.1. Пакет LINGO 517 16.1.1. Реалізація методів нелінійної оптимізації 519 16.1.2. Лінійна оптимізація 525 16.2. Пакет UNDO 528 16.2.1. Лінійна оптимізація 531 16.2.2. Реалізація методів цілочисельного та квадратичного програмування 536 16.3. Прикладні програми оптимізації 539 Навчальний тренінг 542 ТЕРМІНОЛОГІЧНИЙ СЛОВНИК 543 ЛІТЕРАТУРА 555