Математичне програмування займається вивченням екстремальних завдань і пошуком методів їх вирішення. Завдання математичного програмування формулюються наступним чином. знайти екстремум деякої функції багатьох змінних f (x1. x2. xn) при обмеженнях gi (x1. x2. xn) * bi. де gi - функція, що описує обмеження, * - один з наступних знаків ≥, =, ≤, а bi - дійсне число, i = 1. m. f називається функцією цілі (цільова функція).
Лінійне програмування - це розділ математичного програмування, в якому розглядаються методи рішення екстремальних задач з лінійним функціоналом і лінійними обмеженнями, яким повинні задовольняти шукані змінні.
Завдання лінійного програмування можна сформулювати так. знайти min
Ці обмеження називаються умовами невід'ємності. Якщо всі обмеження задані у вигляді строгих нерівностей, то дана форма називається канонічної.
У матричної формі завдання лінійного програмування записують наступним чином. Знайти max c T x
за умови
A x ≤ b;
x ≥ 0,
де А - матриця обмежень розміром (m × n), b (m × 1) - вектор-стовпець вільних членів, x (n × 1) - вектор змінних, з Т = [c1. c2. cn] - вектор-рядок коефіцієнтів цільової функції.
Рішення х0 називається оптимальним, якщо для нього виконується умова з Т х0 ≥ з Т х. для всіх х E R (x).
Оскільки min f (x) еквівалентний max [- f (x)]. то завдання лінійного програмування завжди можна звести до еквівалентної задачі мінімізації.
Для вирішення завдань даного типу застосовуються методи:
вирішити онлайн задачу лінійного програмування методом штучного базису
Перед застосуванням симплекс методу завдання необхідно привести до канонічного виду. Це означає, що всі обмежуючі умови повинні бути представлені у вигляді рівності, а метою вирішення завдання повинен бути пошук максимуму цільової функції.
У разі якщо у вихідній задачі необхідно знайти мінімум - знаки коефіцієнтів цільової функції F змінюються на протилежні a0, n = -a0, n. Знаки коефіцієнтів обмежуючих умов зі знаком "≥" так само змінюються на протилежні. У разі якщо умова містить знак "≤" - коефіцієнти запишуться без змін. До кожного граничного умові, при переході від нерівностей до рівності, додається додаткова змінна xn + m. Додаткова змінна не буде впливати на значення цільової функції і на оптимальне рішення яке буде отримано в результаті.
Необхідно привести задачу до канонічного вигляду.
Змінимо знаки коефіцієнтів цільової функції на протилежні, і перейдемо тим самим до пошуку max. Змінимо знаки коефіцієнтів першого умови на протилежні т. К. Це умова зі знаком "≥", і додамо в нього додаткову змінну x4. Знаки другої умови залишимо без зміни, додавши до нього додаткову змінну x5.