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

Відео: Лекція 2 Симплекс-метод

У тих випадках, коли в задачах є N-невідомих, то область допустимих рішень в рамках системи обмежуючих умов є опуклим багатогранників в N-вимірному просторі. Отже, вирішити таке завдання графічно неможливо, тут слід застосовувати симплекс-метод лінійного програмування.

Вам знадобиться

- математичний довідник

Інструкція

Відкрийте систему обмежень системою лінійних рівнянь, яка відрізняється тим, що число невідомих в ній більше кількості рівнянь. При ранзі системи 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

Надавайте конкретні значення вільним змінним, після чого розраховуйте базисні величини, значення яких невід`ємні. Якщо базисними величинами є значення від X1 до Xr, то рішення зазначеної системи від b1 до 0 буде опорним за умови, що значення від b1 до br gt; = 0.

При допустимості базисного рішення перевірте його на оптимальність. Якщо рішення не виявиться таким, перейдіть до наступного опорного рішення. При кожному новому рішенні лінійна форма наближатиметься до оптимуму.

Складіть симплекс таблицю. Для цього члени зі змінними у всіх равенствах переносяться в ліву частину, а вільні від змінних члени залишаються в правій частині. Все це відображається в табличній формі, де в стовпцях вказуються базові змінні, вільні члени, Х1 ... .Xr, Xr + 1 ... Xn, а в рядках відображаються Х1 ... .Xr, Z.

Переглядайте останній рядок таблиці і вибирайте серед коефіцієнтів або мінімальне від`ємне число при пошуку max, або максимальне позитивне при пошуку на min. Якщо подібних значень немає, значить, знайдене базисне рішення можна вважати оптимальним.

Переглядайте той стовпець таблиці, який тотожний обраному позитивному чи негативному значенню в останньому рядку. Виберіть в ньому позитивні величини. Якщо таких не виявляється, то завдання рішень не має.

Серед решти коефіцієнтів стовпця виберіть той, для якого співвідношення вільного члена до цього елементу мінімально. Ви отримаєте дозволяє коефіцієнт, а рядок, в якій він присутній, стане ключовою.

Переведіть базисну змінну, відповідну рядку дозволяє елемента, в розряд вільних, а вільну змінну, відповідну колонку дозволяє елемента - в категорію базисних. Побудуйте нову таблицю з іншими назвами базисних змінних.

Розділіть всі елементи ключовою рядки, крім стовпця вільних членів, на які дозволяють елементи і знову набутих значень. Внесіть їх в рядок з відкоригованої базисної змінної в новій таблиці. Елементи ключового стовпця, рівні нулю, тотожні завжди одиниці. Стовпець, де в ключовий рядку виявляється нуль, і рядок, де в ключовому стовпці знаходиться нуль, в новій таблиці збережуться. В інші графи нової таблиці запишіть результати перетворення елементів зі старої таблиці.

Досліджуйте варіанти доти, поки не знайдете оптимального рішення.

Зверніть увагу

Якщо в задачі присутня невелика кількість змінних і умов обмежень, то вона вирішується вручну. Якщо кількість змінних значно, потрібно використовувати симплекс таблиці, що представляють собою скорочений запис задачі в канонічній формі, яка попередньо перетворена і приведена до допустимого базисного увазі.

Корисна порада

Розгляньте умови для однієї з вершин багатогранника при пошуку максимуму. У тому випадку, якщо вона не відповідають мінімуму або максимуму, то перейдіть до сусідньої вершини. При цьому значення функції при орієнтуванні на мінімум зменшіть, при пошуку максимуму - збільште. Подібний перехід від вершини до вершини поліпшить значення функції мети. Сімлекс-метод можна застосовувати до будь-яких завдань лінійного програмування, представленим в канонічній формі.

Зроби сам