Лінійне програмування - математична область дослідження лінійних залежностей між змінними і вирішення на їх основі завдань на пошук оптимальних значень того чи іншого показника. У зв 'язку з цим методи лінійного програмування, в тому числі симплекс-метод, широко застосовуються в економічній теорії.
Інструкція
1. Симплекс-метод - один з основних способів вирішення завдань лінійного програмування. Він полягає в послідовній побудові математичної моделі, що характеризує розглянутий процес. Рішення розбивається на три основні етапи: вибір змінних, побудова системи обмежень і пошук цільової функції.
2. Виходячи з цього поділу, умову завдання можна перефразувати наступним чином:знайти екстремум цільової функції Z (X) = f (x1, x2,..., xn) ^ max (min) і відповідні змінні, якщо відомо, що вони задовольняють системі обмежень:Φ_i (x1, x2,..., xn) = 0 при i = 1, 2,..., k;Φ_i (x1, x2,..., xn)) 0 при i = k + 1, k + 2,..., m.
3. Систему обмежень потрібно привести до канонічного вигляду, тобто до системи лінійних рівнянь, де кількість змінних більша за кількість рівнянь (m > k). У цій системі обов 'язково знайдуться змінні, які можна висловити через інші змінні, а якщо це не так, то їх можна ввести штучно. У цьому випадку перші називаються базисом або штучним базисом, а другі - вільними.
4. Зручніше розглянути симплекс-метод на конкретному прикладі. Нехай дана лінійна функція f (x) = 6x1 + 5x2 + 9x3 і система обмежень:5х1 + 2x2 + 3x3. 25; x1 + 6x2 + 2x3. 20; 4x1 + 3x3. Потрібно знайти максимальне значення функції f (x).
5. На першому етапі задайте початкове (опорне) рішення системи рівнянь абсолютно довільним чином, яке при цьому має задовольняти даній системі обмежень. У даному випадку потрібно введення штучного базису, тобто базисних змінних x4, x5 і x6 наступним чином:5x1 + 2x2 + 3x3 + x4 = 25;x1 + 6x2 + 2x3 + x5 = 20;4x1 + 3x3 + x6 = 18.
6. Як бачите, нерівності перетворювалися на рівності завдяки доданим змінним x4, x5, x6, які є неотрицательными величинами. Таким чином, ви привели систему до канонічного вигляду. Змінна x4 входить в перше рівняння з коефіцієнтом 1, а в два інших - з коефіцієнтом 0, те ж справедливо для змінних x5, x6 і відповідних рівнянь, що відповідає визначенню базису.
7. Ви підготували систему і знайшли початкове опорне рішення - X0 = (0, 0, 0, 25, 20, 18). Тепер представте коефіцієнти змінних та вільні члени рівнянь (цифри праворуч від знака =) у вигляді таблиці для оптимізації подальших обчислень (див. рис).
8. Суть симплекс-методу полягає в тому, щоб привести цю таблицю до такого виду, в якому всі цифри в рядку L будуть неотрицательными величинами. Якщо ж з 'ясується, що це неможливо, то система взагалі не має оптимального рішення. Для початку виберіть мінімальний елемент цього рядка, це -9. Цифра стоїть у третьому стовпці. Перетворіть відповідну змінну x3 на базисну. Для цього розділіть рядок на 3, щоб у комірці [3,3] вийшов 1.
9. Тепер потрібно, щоб комірки [1,3] і [2,3] звернулися в 0. Для цього відніміть від елементів першого рядка відповідні цифри третього рядка, помножені на 3. Від елементів другого рядка - елементи третього, помножені на 2. І, нарешті, від елементів рядка L - помножені на (-9). Ви отримали друге опорне рішення: f (x) = L = 54 при x1 = (0, 0, 6, 7, 8, 0).
10. У рядку L залишилося тільки одне від 'ємне число -5 у другому стовпчику. Тому будемо перетворювати до базисного вигляду змінну x2. Для цього елементи стовпчика повинні прийняти вигляд (0, 1, 0). Розділіть всі елементи другого рядка на 6.
11. Тепер від елементів першого рядка відніміть відповідні цифри другого рядка, помножені на 2. Потім відніміть від елементів рядка L ті самі цифри, але з коефіцієнтом (-5).
12. Ви отримали третє і остаточне опорне рішення, оскільки всі елементи рядка L стали неотрицательными. Отже, X2 = (0, 4/3, 6, 13/3, 0, 0) і L = 182/3 = -83/18x1 - 5/6x5 -22/9x6. Максимальне значення функції f (x) = L (X2) = 182/3. Оскільки всі x_i в рішенні X2 неотрицательны, як і саме значення L, то оптимальне рішення знайдено.