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

У тих випадках, коли в задачах є N-невідомих, то область допустимих рішень в рамках системи обмежуючих умов є опуклим багатогранником в N-вимірному просторі. Отже, вирішити таке завдання графічно неможливо, тут слід застосовувати симплекс-метод лінійного програмування.
Вам знадобиться
  • - математичний довідник
Інструкція
1
Відобразите систему обмежень системою лінійних рівнянь, яка відрізняється тим, що число невідомих у ній більше кількості рівнянь. При ранзі системи R виберіть R невідомих. Наведіть систему методом Гауса до вигляду: x1 = b1 + a1r + 1x r + 1 + ... + a1nx nx2 = 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
Переглядайте останній рядок таблиці і вибирайте серед коефіцієнтів або мінімальне від'ємне число при пошуку max, або максимальне позитивне при пошуку на min. Якщо подібних значень немає, значить, знайдене базисне рішення можна вважати оптимальним.
6
Переглядайте той стовпець таблиці, який тотожний обраному позитивному чи негативному значенню в останньому рядку. Виберіть у ньому позитивні величини. Якщо таких не виявляється, то завдання рішень не має.
7
Серед решти коефіцієнтів стовпця виберіть той, для якого співвідношення вільного члена до цього елементу мінімально. Ви отримаєте дозволяючий коефіцієнт, а рядок, у якому він присутній, стане ключовою.
8
Переведіть базисну змінну, відповідну рядку дозволяє елемента, в розряд вільних, а вільну змінну, відповідну колонку дозволяє елемента - в категорію базисних. Побудуйте нову таблицю з іншими назвами базисних змінних.
9
Розділіть всі елементи ключовою рядки, крім стовпця вільних членів, на що вирішують елементи і знову отримані значення. Внесіть їх в рядок з відкоригованої базисної змінної в новій таблиці. Елементи ключового стовпця, рівні нулю, тотожні завжди одиниці. Стовпець, де в ключовий рядку виявляється нуль, і рядок, де в ключовому стовпці знаходиться нуль, в новій таблиці збережуться. В інші графи нової таблиці запишіть результати перетворення елементів зі старої таблиці.
10
Дослідіть варіанти доти, поки не знайдете оптимального рішення.
Зверніть увагу
Якщо в задачі присутня невелика кількість змінних і умов обмежень, то вона вирішується вручну. Якщо кількість змінних значно, потрібно використовувати симплекс таблиці, що представляють собою скорочений запис задачі у канонічній формі, яка попередньо перетворена і приведена до допустимого базисного увазі.
Корисна порада
Розгляньте умови для однієї з вершин багатогранника при пошуку максимуму. У тому випадку, якщо вона не відповідають мінімуму або максимуму, то перейдіть до сусідньої вершини. При цьому значення функції при орієнтуванні на мінімум зменшите, при пошуку максимуму - збільшіть. Подібний перехід від вершини до вершини поліпшить значення функції мети. Симлекс-метод застосуємо до будь-яких завдань лінійного програмування, представленим в канонічній формі.