ЗМІСТ
Передмова 3
Розділ 1. Предмет, сфери та особливості застосування
математичного програмування в економіці.
Класифікація задач 7
1.1. Предмет та об’єкти математичного програмування 7
1.2. Математична постановка задачі математичного програмування 10
1.3. Приклад економіко-математичної моделі 13
1.4. Багатокритеріальна оптимізація 14
1.5. Історична довідка 18
1.6. Класифікація задач математичного програмування 19
1.7. Приклади економічних задач математичного програмування 23
Розділ 2. Загальна задача лінійного програмування
та деякі з методів її розв’язування 26
2.1. Приклади побудови економіко-математичних моделей
економічних процесів та явищ 26
2.2. Загальна економіко-математична модель задачі
лінійного програмування 36
2.3. Форми запису задач лінійного програмування 38
2.4. Геометрична інтерпретація задачі лінійного програмування 40
2.5. Основні властивості розв’язків задачі лінійного програмування 43
2.6. Графічний метод розв’язування задач лінійного програмування 48
2.7. Приклади розв’язування задач графічним методом 55
2.8. Симплексний метод розв’язування задач лінійного
програмування 64
2.8.1. Початковий опорний план 65
2.8.2. Перехід від одного опорного плану до іншого 66
2.8.3. Оптимальний розв’язок. Критерій оптимальності плану 68
2.8.4. Алгоритм розв’язування задачі лінійного
програмування симплексним методом 71
2.8.5. Приклад розв’язування задачі симплекс-методом 77
2.8.6. Метод штучного базису 83
2.8.7. Зациклення в задачах лінійного програмування 96
2.8.8. Геометрична інтерпретація симплексного методу 97
2.9. Модифікації симплексного методу 98
Заключні зауваження 101
Контрольні запитання 102
Завдання для самостійної роботи 103
Розділ 3. Теорія двоїстості та двоїсті оцінки
у лінійному програмуванні 105
3.1. Економічна інтерпретація прямої та двоїстої задач
лінійного програмування 105
3.2. Правила побудови двоїстих задач 107
3.3. Основні теореми двоїстості та їх економічний зміст 111
3.3.1. Перша теорема двоїстості 113
3.3.2. Друга теорема двоїстості 116
3.3.3. Третя теорема двоїстості 120
3.4. Приклади застосування теорії двоїстості для знаходження
оптимальних планів прямої та двоїстої задач 122
3.5. Післяоптимізаційний аналіз задач лінійного програмування 129
3.5.1. Аналіз діапазону зміни компонент вектора обмежень 130
3.5.2. Аналіз діапазону зміни коефіцієнтів цільової функції 135
3.5.3. Аналіз діапазону зміни коефіцієнтів матриці обмежень 138
3.6. Двоїстий симплексний метод 139
3.7. Параметричне програмування 143
3.7.1. Параметричні зміни вектора обмежень 144
3.7.2. Параметричні зміни вектора коефіцієнтів цільової функції 148
Заключні зауваження 154
Контрольні запитання 154
Приклади та завдання для самостійної роботи 155
Розділ 4. Аналіз лінійних моделей економічних задач 156
4.1. Приклад економічної інтерпретації пари спряжених задач 157
4.2. Аналіз розв’язків спряжених економіко-математичних
задач 159
4.3. Оцінка рентабельності продукції, яка виробляється,
і нової продукції 161
4.4. Аналіз обмежень дефіцитних і недефіцитних ресурсів 164
4.5. Аналіз коефіцієнтів цільової функції 170
4.6. Аналіз коефіцієнтів матриці обмежень 173
4.7. Приклад практичного використання двоїстих оцінок
у аналізі економічної задачі 175
Заключні зауваження 181
Контрольні запитання 181
Приклади та завдання для самостійної роботи 182
Розділ 5. Транспортна задача 184
5.1. Економічна і математична постановка транспортної задачі 184
5.2. Властивості опорних планів транспортної задачі 189
5.3. Методи побудови опорного плану транспортної задачі 194
5.4. Випадок виродження опорного плану транспортної задачі 201
5.5. Методи розв’язування транспортної задачі 203
5.5.1. Задача, двоїста до транспортної 203
5.5.2. Метод потенціалів розв’язування транспортної задачі 204
5.5.3. Монотонність і скінченність методу потенціалів 207
5.5.4. Приклади розв’язування транспортних задач
методом потенціалів 209
5.5.5. Угорський метод розв’язування транспортної задачі 214
5.6. Транспортна задача з додатковими умовами 225
5.7. Двохетапна транспортна задача 230
5.8. Транспортна задача за критерієм часу 236
5.9. Розв’язування транспортної задачі на мережі 241
5.9.1. Транспортна задача у мережевій формі 242
5.9.2. Метод потенціалів на мережі 244
5.10. Приклади економічних задач, що зводяться
до транспортних моделей 247
Заключні зауваження 252
Контрольні запитання 253
Приклади та завдання для самостійної роботи 254
Розділ 6. Цілочислові задачі лінійного програмування.
Основні методи їх розв’язування та аналізу 255
6.1. Економічна і математична постановка цілочислової
задачі лінійного програмування 255
6.2. Геометрична інтерпретація розв’язків цілочислових
задач лінійного програмування на площині 256
6.3. Загальна характеристика методів розв’язування
цілочислових задач лінійного програмування 258
6.4. Методи відтинання. Метод Гоморі 259
6.5. Комбінаторні методи. Метод гілок та меж 266
6.6. Наближені методи. Метод вектора спаду 272
6.7. Приклади застосування цілочислових задач лінійного
програмування у плануванні та управлінні
виробництвом 276
Заключні зауваження 298
Контрольні запитання 298
Приклади та завдання для самостійної роботи 299
Розділ 7. Задачі дробово-лінійного програмування.
Основні методи їх розв’язування та аналізу 300
7.1. Економічна і математична постановка задачі
дробово-лінійного програмування 300
7.2. Геометрична інтерпретація задачі дробово-лінійного
програмування 301
7.3. Розв’язування дробово-лінійної задачі зведенням
до задачі лінійного програмування 304
Заключні зауваження 309
Контрольні запитання 309
Приклади та завдання для самостійної роботи 310
Розділ 8. Задачі нелінійного програмування.
Основні методи їх розв’язування та аналізу 311
8.1. Економічна і математична постановка задачі нелінійного
програмування 311
8.2. Геометрична інтерпретація задачі нелінійного програмування 313
8.3. Основні труднощі розв’язування задач нелінійного
програмування 315
8.4. Класичний метод оптимізації. Метод множників Лагранжа 318
8.4.1. Умовний та безумовний екстремуми функції 318
8.4.2. Метод множників Лагранжа 320
8.5. Необхідні умови існування сідлової точки 326
8.6. Теорема Куна—Таккера 330
8.6.1. Опуклі й угнуті функції 333
8.7. Опукле програмування 336
8.8. Квадратичне програмування 337
8.8.1. Квадратична форма та її властивості 338
8.8.2. Метод розв’язування задач квадратичного програмування 339
8.9. Економічна інтерпретація множників Лагранжа 345
8.10. Градієнтний метод 351
Заключні зауваження 357
Контрольні запитання 357
Приклади та завдання для самостійної роботи 357
Розділ 9. Динамічне програмування 359
9.1. Економічна сутність задач динамічного програмування 359
9.2. Задача про розподіл капіталовкладень між двома підприємствами на п років 361
9.2.1. Метод рекурентних співвідношень 363
9.3. Задача про розподіл капіталовкладень між підприємствами 364
9.4. Принцип оптимальності 374
9.5. Багатокроковий процес прийняття рішень 375
9.6. Приклади розв’язування задач динамічного програмування 377
Заключні зауваження 389
Контрольні запитання 389
Приклади та завдання для самостійної роботи 390
Розділ 10. Стохастичне програмування 391
10.1. Загальна математична постановка задачі стохастичного
програмування 392
10.2. Особливості математичної постановки задач
стохастичного програмування 393
10.3. Приклади економічних задач стохастичного
програмування 402
10.4. Одноетапні задачі стохастичного програмування 405
10.5. Двохетапні задачі стохастичного програмування 411
Заключні зауваження 419
Контрольні запитання 420
Приклади та завдання для самостійної роботи 420
Розділ 11. Теорія ігор 422
11.1. Основні поняття теорії ігор 422
11.2. Класифікація ігор 424
11.3. Матричні ігри двох осіб 424
11.4. Гра зі змішаними стратегіями 430
11.5. Геометрична інтерпретація гри 2 × 2 432
11.6. Зведення матричної гри до задачі лінійного програмування 436
Заключні зауваження 440
Контрольні запитання 441
Приклади та завдання для самостійної роботи 442
Рекомендована література 443