4. Потрібно забезпечити, щоб множина наборів Хj була не порожньою. З цією метою в економіко-математичних моделях по змозі слід уникати обмежень типу «=», а також суперечливих обмежень. Наприклад, ставиться обмеження щодо виконання контрактів, але ресурсів недостатньо, аби їх виконати. Якщо система (1.3) має єдиний розв'язок, то не існує задачі вибору оптимального плану.
Будь-який набір змінних 
, що задовольняє умови (1.3) і (1.4), називають допустимим планом, або планом. Очевидно, що кожний допустимий план є відповідною стратегією економічної системи, програмою дій. Саме зі словом «програма» і пов'язана назва предмета «математичне програмування». Кожному допустимому плану відповідає значення цільової функції, яке обчислюється за формулою (1.1).
Сукупність усіх розв'язків систем обмежень (1.3) і (1.4), тобто множина всіх допустимих планів, становить область існування планів.
План, за якого цільова функція набуває екстремального значення, називається оптимальним. Оптимальний план є розв'язком задачі математичного програмування (1.2)—(1.4).
Зауважимо, що в задачі математичного програмування передбачається одна цільова функція, яка кількісно визначена. У реальних економічних системах на роль критерію оптимальності (ефективності) претендують кілька десятків показників. Наприклад, максимум чистого доходу від виробленої продукції у вартісному виразі чи максимум рентабельності, мінімум собівартості виробленої продукції або мінімум витрат дефіцитних ресурсів. Некоректним є вираз «максимум товарної продукції за і мінімальної її собівартості». Хоча задача математичного програмування передбачає одну цільову функцію, але існують математичні методи побудови компромісних планів, тобто методи багато критеріальної оптимізації.
Перш ніж розглядати методи оптимізації, ознайомимося з класифікацією задач математичного програмування.
1.3. Найпростіша класифікація задач математичного програмування
Будь-яка класифікація передбачає вибір критерію, згідно з яким вона здійснюється. Оскільки математичне програмування передусім є строгою математичною дисципліною, то критеріями класифікації мають бути в основному математичні структури (властивості) задач і методів їх розв'язування. Зауважимо, що одна й та сама задача з погляду різних математичних критеріїв може належати до кількох класів. Адже кожний критерій підкреслює лише одну властивість задачі на противагу деякій іншій, тобто поділяє всі задачі на два класи (чи підкласи всередині певного класу).
Задачі математичного програмування поділяються на два великі класилінійні танелінійні. Якщо цільова функція (1.2) та обмеження (1.3) є лінійними функціями, тобто вони містять змінні J^ у першому або нульовому степені. В усіх інших випадках задача буде нелінійною. Важливою перевагою лінійних задач є те, що для їх розв'язування розроблено універсальний метод, який називаєтьсясимплексним методом. Теоретично кожну задачу лінійного програмування можна розв'язати. Для деяких класів лінійних задач, що мають особливу структуру, розробляють спеціальні методи розв'язування, які є ефективнішими. Наприклад, транспортну задачу можна розв'язати симплексним методом, але ефективнішими є спеціальні методи, наприклад метод потенціалів.
Економічні та технологічні процеси, як правило, є нелінійними, стохастичними, розвиваються в умовах невизначеності. Лінійні економіко-математичні моделі часто є неадекватними, а тому доводиться будувати нелінійні та стохастичні моделі. Розв'язувати нелінійні задачі набагато складніше, ніж лінійні, оскільки немає універсального методу розв'язування таких задач. Для окремих типів нелінійних задач розроблено численні спеціальні ефективні методи розв'язування. Проте слід зазначити, що на практиці застосовують, здебільшого, лінійні економіко-математичні моделі. Часто нелінійні залежності апроксимують (наближають) лінійними. Такий підхід на практиці є доволі ефективним.
У нелінійному програмуванні виокремлюють такі класи:опукле програмування. Для задач опуклого програмування існує низка добре обґрунтованих та ефективних методів їх розв'язування. Зазначимо, що задачі лінійного програмування є частковим випадком задач опуклого програмування.
Наголосимо, що коли область допустимих планів є опуклою множиною, а цільова функція є опуклою функцією, то задача математичного програмування має глобальний, єдиний екстремум (якщо такий існує).
Множина S в n-мірному евклідовому просторі називається опуклою множиною, якщо для будь-яких точок (елементів) цієї множини 
точки 
належать множині S за всіх значень m, які належать відрізку 
.
Геометричне це означає, якщо 
та 
належать до множини 5, то відрізок прямої, що з'єднує ці дві точки, також цілком належить до множини S.
Функція f{X), визначена на опуклій множині лінійного простору (на опуклій множині S), називається опуклою, якщо виконується нерівність
для всіх ц, які належать відрізку 
.
Квадратичне програмування — цільова функція квадратична, а обмеження лінійні.
Далі задачі математичного програмування поділяють на дискретні і неперервні. Дискретними називають задачі, в яких одна, кілька або всі змінні набувають лише дискретних значень. Окремий клас становлять задачі, в яких одна або кілька змінних набувають цілочислових значень, тобто задачі цілочислового програмування. Якщо всі змінні можуть набувати будь-якого значення в деяких інтервалах числової осі, то задача є неперервною.
Задачі математичного програмування поділяються також на детерміновані і стохастичні. Детерміновані задачі не містять випадкових змінних і параметрів, котрі набувають значень відповідно до функції розподілу. Наприклад, якщо в економіко-математичній моделі врожайності сільськогосподарських культур задані своїми математичними сподіваннями, то така задача є детермінованою. Якщо врожайності задані функціями розподілу, наприклад нормального з математичним сподіванням a і дисперсією s, то така задача є стохастичною.
Якщо у відповідних економічних процесах випадкові явища не відіграють істотної ролі, то задачу можна розв'язувати як детерміновану. У противному разі адекватна економіко-математична модель має бути стохастичною, тобто містити випадкові функції та величини. Структура та розв'язування таких задач вивчаються в окремому розділі, який називається стохастичним програмуванням.
Економічні процеси розвиваються в часі, а тому відповідні моделі мають відображати динаміку. Це означає, що для знаходження оптимального плану потрібно застосовувати класи задач математичного програмування статичні (однокрокові) і динамічні (багатокрокові). Поняття динамічності зрозуміле, воно пов'язане з часом. Наприклад, якщо йдеться про план розвитку України до 2005 року, мають бути обґрунтовані значення відповідних макроекономічних показників не лише на 2005 рік, а й на всі проміжні роки, тобто враховано динаміку розвитку народногосподарських процесів. Такий план називають стратегічним. У ньому має бути обґрунтована оптимальна (раціональна) траєкторія розвитку народного господарства. Проте під впливом некерованих чинників реальні показники щороку можуть відхилятися від планових. Тому постає потреба коригувати кожний річний план. Такі плани називають тактичними. Вони визначаються в результаті реалізації статичної економіко-математичної моделі.
Важливо чітко усвідомити відмінність між одно- та багатокроковими задачами. Багатокроковість як метод розв'язування задач математичного програмування зумовлюється, насамперед, їх багатовимірністю. Сутність цього методу полягає в тому, що оптимальні значення розглядуваної множини змінних знаходять крок за кроком, послідовно застосовуючи індукцію, причому рішення, яке приймається на кожному кроці, має задовольняти умови оптимальності щодо рішення, прийнятого на попередньому кроці. Така процедура може бути і не бути пов'язаною з часом. Однокрокові задачі, навпаки, характеризуються тим, що всі компоненти оптимального плану задачі визначаються одночасно на останній ітерації (кроці) алгоритму. Потрібно розрізняти ітераційність алгоритму і його багатокроковість. Наприклад, симплекс-метод розв'язування задач лінійного програмування є ітераційним, тобто якимось чином задаємо допустимий план і в результаті деякої кількості ітерацій дістаємо оптимальний план. Тут виконуються ітерації (кроки) алгоритму симплексного методу, але це не інтерпретується як багатокроковість економічного процесу (явища). Деякі задачі математичного програмування можна розглядати як одно- або багатокрокові залежно від способу їх розв'язування. Якщо задачу можна розв'язувати як одно крокову, то розв'язувати її як багатокрокову недоцільно, аби не застосовувати для знаходження оптимального плану складніших методів. Проте більшість економічних процесів с динамічними, їх параметри змінюються в часі й залежать від рішень керівництва, що їх доводиться приймати з метою досягнення розвитку економічної системи за траєкторією, яка визначається стратегічним планом.
Щойно було розглянуто лише найбільші класи задач математичного програмування, які визначені згідно з математичними критеріями. Можна також за різними ознаками виокремити й підкласи. Це особливо стосується задач лінійного, нелінійного і стохастичного програмування. Наприклад, як окремий клас розглядають дробово-лінійне програмування, коли обмеження є лінійними, а цільова функція — дробово-лінійна. Особливий клас становлять задачі теорії ігор, які широко застосовуються в ринковій економіці. Адже тут діють дві чи більше конфліктних сторін, які мають цілі, що не збігаються, або протилежні цілі. У сукупності задач теорії ігор, у свою чергу, також виокремлюють певні підкласи. Наприклад, ігри двох осіб із нульовою сумою.
Наведену класифікацію використано для структурування курсу «Математичне програмування».
1.4. Приклади економічних проблем, які доцільно розв’язувати, використовуючи методи і моделі математичого програмування.
ТЕМА 2
ЗАГАЛЬНА ЗАДАЧА ЛІНІЙНОГО ПРОГРАМУВАННЯ ТА МЕТОДИ ЇЇ РОЗВ'ЯЗУВАННЯ
2.1. Математична постановка задач лінійного програмування. Система гіпотез.
Загальна лінійна математична модель економічних процесів і явищ — так звана загальна задача лінійного програмування (ЛП) подається у вигляді:
знайти максимум (мінімум) функції 
або 
за умов
Отже, потрібно знайти значення змінних 
, які задовольняють умови (2.2) і (2.3), тоді як цільова функція набуває екстремального (максимального чи мінімального) значення.
Задачу (2.1)—(2.3) легко звести до канонічної форми, тобто до такого вигляду, коли в системі обмежень (2.2) всі 
невід'ємні, а всі обмеження є рівностями.
Якщо якесь bi від'ємне, то, помноживши i-те обмеження на (–1), дістанемо у правій частині відповідної рівності додатне значення. Коли i-те обмеження має вигляд нерівності 
то останню завжди можна звести до рівності, увівши допоміжну змінну 
.
Аналогічно обмеження виду 
зводимо до рівності, віднімаючи від лівої частини допоміжну змінну 
, тобто 
.
Приклад 2.1. Записати в канонічній формі таку задачу ЛП:
за умов
Розв'язування. Помножимо другу нерівність на (–1) і введемо відповідно допоміжні змінні x4 і x5 для другого та третього обмеження:
Неважко переконатися, що допоміжні змінні, у цьому разі x4 і x5, є невід'ємними, причому їх уведення не змінює цільової функції.
Отже, будь-яку задачу ЛП можна записати в такій канонічній формі:
знайти максимум функції 
за умов
Задачу (2.4)—(2.6) можна розв'язувати на мінімум, якщо цільову функцію помножити на (–1), тобто
2.2. Визначення множини допустимих планів задачі ЛП
Задачу ЛП (ЗЛП) зручно записувати за допомогою знака суми «S». Справді, задачу (2.4)—(2.6) можна подати так:
за умов
Ще компактнішим є запис ЗЛП у векторно-матричному вигляді:
за умов
де
є матриця коефіцієнтів при змінних
– вектор змінних; 
– вектор вільних членів;
— вектор коефіцієнтів при змінних у цільовій функції.
Часто ЗЛП зручно записувати у векторній формі:
за умов
де
є вектори коефіцієнтів при змінних.
2.3. Геометрична інтерпретація ЗЛП. Кононічна форма ЗЛП і її оптимальний план.
Геометричну інтерпретацію ЗЛП розглянемо на такому прикладі. Нехай фермер прийняв рішення вирощувати озиму пшеницю і цукровий буряк на площі 20 га, відвівши під цукровий буряк не менш як 5 га. Техніко-економічні показники вирощування цих культур наведені в таблиці:
| №
з/п
| Техніко-економічний показник із розрахунку на 1 га
| Сільськогосподарська культура
| Наявний ресурс
|
| Озима пшениця
| Цукровий буряк
|
|
| Жива праця, людино-днів
|
|
|
|
|
| Механізована праця, людино-днів
|
|
|
|
|
| Прибуток, тис. грн.
| 0,7
|
|
|
Критерієм оптимальності є максимізація прибутку.
Запишемо економіко-математичну модель структури виробництва озимої пшениці та цукрового буряка, скориставшись такими позначеннями:
x1 — шукана площа посіву озимої пшениці;
x2 — шукана площа посіву цукрового буряка.
ЗЛП має вигляд:
за умов
Геометричну інтерпретацію задачі наведено на рис. 2.1.
Область допустимих розв'язків дістаємо так. Кожне обмеження, наприклад 
, задає півплощину з граничною прямою 
. Будуємо її і визначаємо півплощину, яка описується нерівністю . З цією метою в нерівність підставляємо координати якоїсь характерної точки, скажімо 
і 
. Переконуємося, що ця точка належить півплощині . Цей факт на рис. 2.1 ілюструємо відповідною напрямленою стрілкою. Аналогічно будуємо півплощини, які відповідають нерівностям (2.8)—(2.12). У результаті перетину цих півплощин утворюється область допустимих розв'язків задачі (на рис. 2.1 — многокутник ABCD). Цільова функція 
описує сім'ю паралельних прямих, кожна з яких відповідає певному значенню Z. Зокрема, якщо Z = 0, маємо 
. Ця пряма проходить через початок системи координат. Коли Z = 3,5, дістаємо пряму 
.
Загальна задача лінійного програмування (2.1)—(2.3) геометричне інтерпретується так: кожне і-те обмеження, що має вигляд рівняння
у n-вимірному просторі основних змінних задає гіперплощину. Кожному обмеженню виду (2.2) і (2.3) відповідають гіперплощина та півпростір, який лежить по один бік цієї гіперплощини. У перетині всіх півпросторів, що визначаються обмеженнями задачі (2.2) і (2.3), утворюється опуклий многогранник допустимих її розв'язків. Цільову функцію
в n-вимірному просторі основних змінних можна геометричне інтерпретувати як сім'ю паралельних гіперплощин, положення кожної з яких визначається значенням параметра Z.
2.4. Основні аналітичні властивості розв'язків задач лінійного програмування
Вектор 
, координати якого задовольняють системі обмежень (2.2) і (2.3), називають допустимим розв'язком, або допустимим планом задачі. Сукупність допустимих розв'язків (планів) задачі утворює область допустимих розв'язків задачі.
Опорним планом задачі лінійного програмування називається план, утворений координатами вершини многогранника планів задачі. Отже, опорний план — це план, який задовольняє не менш ніж п лінійно незалежних обмежень (2.2) у вигляді строгих рівностей разом з обмеженням (2.3) щодо знака.
Опорний план називається невиродженим, якщо він є вершиною многогранника планів задачі, утвореного перетином точно п гіперплощин, тобто задовольняє п лінійно незалежних обмежень — строгих рівностей. У противному разі опорний план є виродженим.
Якщо задача лінійного програмування має розв'язок і серед її планів є опорні, то хоча б один із них буде оптимальним.
Сукупність усіх розв'язків задачі лінійного програмування є многогранною опуклою множиною, яку називають многогранником розв'язків.
Якщо задача лінійного програмування має оптимальний план, то екстремального значення цільова функція набуває в одній із вершин многогранника розв'язків. Якщо цільова функція набуває екстремального значення більш як в одній вершині цього многогранника, то вона досягає його і в будь-який точці, що є лінійною комбінацією таких вершин.
2.5. Графічний метод розв'язування задач лінійного програмування
