Математичне програмування: Навч. посіб

Наконечний С. І., Савіна С. С. Математичне програмування: Навч. посіб. — К.: КНЕУ, 2003. — 452 с.

Навчальний посібник написано відповідно до програми курсу «Математичне програмування» для підготовки бакалаврів з економіки. У посібнику розглядаються основні математичні методи та моделі дослідження економічних систем та процесів, що є основою для прийняття обґрунтованих управлінських рішень в реальних умовах. Розділи з першого по п’ятий присвячені задачам лінійного програмування, теорії двоїстості, економічному аналізу оптимальних планів. З шостого по одинадцятий розділи розглядаються складніші задачі математичного програмування: цілочислові, нелінійні, динамічні, стохастичні, дробово-лінійні, задачі теорії ігор. Теоретичний матеріал ілюструється числовими економіко-математичними моделями, які адекватно відображають основні виробничо-економічні процеси. В кількох розділах наведено понадпрограмний матеріал.

Рекомендується для бакалаврів університетів з напрямку «Економіка і підприємництво» та студентів інших навчальних закладів, які вивчають курси «Математичне програмування» та «Дослідження операцій», а також для слухачів різних курсів і шкіл підвищення кваліфікації для економістів.

ЗМІСТ
Передмова	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. Аналіз обмежень дефіцитних і недефіцитних ресурсів	167
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

Остання редакція: 02.03.15

Київський національний економічний університет імені Вадима Гетьмана

Математичне програмування: Навч. посіб