нійною залежністю між змінними і лінійним критерієм. Необхідною умовою постановки задачі лінійного програмування є обмеження на наявність ресурсів, величину попиту, виробничу потужність підприємства та інші виробничі фактори. Сутність лінійного програмування полягає в знаходженні точок найбільшого або найменшого значення деякої функції при певному наборі обмежень, що накладаються на аргументи і утворюють
систему обмежень , яка має, як правило, нескінченна безліч рішень. Кожна сукупність значень
В· змінних (Аргументів функції F ), які задовольняють системі обмежень, називається допустимим планом задачі лінійного програмування. Функція F , максимум або мінімум якої визначається, називається цільової функцією завдання. Допустимий план, на якому досягається максимум або мінімум функції F , називається оптимальним планом завдання. Система обмежень, визначальна безліч планів, диктується умовами виробництва. Завданням лінійного програмування ( ЗЛП ) є вибір з безлічі допустимих планів найбільш вигідної (оптимального). У загальній постановці задача лінійного програмування виглядає наступним чином:
Є якісь змінні х = (х 1 , х 2 , ... х n ) і функція цих змінних f (x) = f (х 1 , х 2 , ... х n ) , яка носить назву цільової функції. Ставиться завдання: знайти екстремум (максимум чи мінімум) цільової функції f (x) за умови, що змінні x належать деякій області G :
Залежно від виду функції f (x) та області G і розрізняють розділи математичного програмування: квадратичне програмування, опукле програмування, цілочисельне програмування і т.д. Лінійне програмування характеризується тим, що
а) функція f (x) є лінійною функцією змінних х 1 , х 2 , ... х n
б) область G визначається системою лінійних рівності або нерівностей. p> Математична модель будь-якої задачі лінійного програмування включає в себе:
В· максимум або мінімум цільової функції (критерій оптимальності);
В· систему обмежень у формі лінійних рівнянь і нерівностей;
В· вимога невід'ємності змінних. p> Приклад
В інших ситуаціях можуть виникати завдання з великою кількістю змінних, в систему обмежень яких, крім нерівностей, можуть входити і рівності. Тому в найбільш загальній формі завдання лінійного програмування формулюють наступним чином:
(2.4)
(2.5)
(2.6)
Коефіцієнти a i, j , b i , c j , j = 1, 2, ... , N, i = 1, 2, ... , M - будь-які дійсні числа (можливо 0). p> Отже, рішення, що задовольняють системі обмежень (2.4) умов завдання і вимогам невід'ємності (2.5), називаються допустимими , а рішення, задовольняють...
