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

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

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

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

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

Інструкція

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

    x1 = b1 + a1r +1 x r +1 + … + a1nx n

    x2 = b2 + a2r +1 x r +1 + … + a2nx n

    … … … … … … … … … ..

    xr = br + ar, r +1 x 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. Дослідіть варіанти до тих пір, поки не знайдете оптимального рішення.

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

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

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

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