Як вирішувати симплексним методом.

Якщо в задачі є N невідомих, то область допустимих рішень в системі обмежуючих умов буде опуклим багатогранником в N-вимірному просторі. Графічне рішення такого завдання неможливо, і в цьому випадку застосовується симплексний метод лінійного програмування.
Інструкція
1
Запишіть систему обмежень як систему лінійних рівнянь, число невідомих в якій буде більше кількості рівнянь. Виберіть R невідомих при ранзі системи R. Використовуючи метод Гаусса, приведіть систему до такого виду: x1 = b1 + a1r + 1x r + 1 + ... + a1nx n; x2 = b2 + a2r + 1x r + 1 + ... + a2nx n; ... xr = br + ar, r + 1x r + 1 + ... + amx n.
2
Надайте вільним змінним конкретні значення і після цього розрахуйте базисні величини. Їх значення повинні бути невід'ємними. Так, якщо за базисні величини прийняті значення від X1 до Xr, то рішення даної системи від b1 до 0 буде опорним, за умови, що значення від b1 до br? 0.
3
При граничної допустимості базисного рішення системи перевірте його на оптимальність. Якщо воно не буде відповідати оптимуму, перейдіть до наступного. Таким чином, від рішення до вирішення задана лінійна система буде наближатися до оптимуму.
4
Сформуйте симплекс-таблицю. Перенесіть в її ліву частину члени із змінними у всіх равенствах, а вільні від змінних - в праву. Таким чином, в шпальтах будуть вказані базові змінні, вільні члени, Х1 ... Xr, Xr + 1 ... Xn, в рядках відобразяться Х1 ... Xr, Z.
5
Перегляньте останній рядок і виберіть серед наведених коефіцієнтів або максимальне позитивне при пошуку на min, або мінімальне від'ємне число при пошуку на max. Якщо таких значень немає, базисне рішення вважається оптимальним. Перегляньте стовпець таблиці, тотожний обраному негативному або позитивному значенню в останньому рядку. Знайдіть у ньому позитивні величини. Якщо їх немає, то таке завдання не має рішення.
6
Оберіть з решти коефіцієнтів стовпця таблиці саме той, для якого різниця у ставленні до вільного члену мінімальна. Це значення буде вирішальним коефіцієнтом, а рядок, у якому він записаний - ключове. Переведіть вільну змінну з рядка, де знаходиться дозволяє елемент, в розряд базисних, а базисну, зазначену в стовпці - у вільну. Складіть ще одну таблицю із зміненими назвами і значеннями змінних.
7
Розподіліть всі елементи ключовою рядки, крім шпальти, де знаходяться вільні члени, на що вирішують елементи і нові отримані значення. Впишіть їх в рядок зі скоригованої базисної змінної в другій таблиці. Ті елементи ключового стовпця, які дорівнюють нулю, завжди тотожні одиниці. У новій таблиці також будуть збережені і стовпець з нулем в ключовий рядку і рядок з нулем у ключовому стовпці. Запишіть результати перетворення змінних з першої таблиці.
Лінійне програмування - математична область дослідження лінійних залежностей між змінними і рішення на їх основі завдань на пошук оптимальних значень того чи іншого показника. У зв'язку з цим методи лінійного програмування, в тому числі симплекс-метод, широко застосовуються в економічній теорії.
Інструкція
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 і система обмежень: 5x1 + 2x2 + 3x3? 25; x1 + 6x2 + 2x3? 20; 4x1 + 3x3? 18.Требуется знайти максимальне значення функції 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, то оптимальне рішення знайдено.
Відео по темі
 http://www.youtube.com/watch?v=FPhahnxco28