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


 

Якщо в задачі є 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. Перегляньте останній рядок і виберіть серед наведених коефіцієнтів або максимальне позитивне при пошуку на min, або мінімальне від’ємне число при пошуку на max. Якщо таких значень немає, базисне рішення вважається оптимальним. Перегляньте стовпець таблиці, тотожний обраному негативного або позитивного значення в останньому рядку. Знайдіть в ньому позитивні величини. Якщо їх немає, то таке завдання не має рішення.
  6. Виберіть з решти коефіцієнтів стовпця таблиці саме той, для якого різниця у ставленні до вільного члену мінімальна. Це значення буде вирішує коефіцієнтом, а рядок, в якій він записаний — ключове. Переведіть вільну змінну з рядка, де знаходиться дозволяє елемент, в розряд базисних, а базисну, зазначену в стовпці — у вільну. Складіть ще одну таблицю зі зміненими назвами і значеннями змінних.
  7. Розподіліть всі елементи ключовою рядки, крім стовпця, де знаходяться вільні члени, на що дозволяють елементи і нові отримані значення. Впишіть їх в рядок зі скоригованої базисної змінної в другій таблиці. Ті елементи ключового стовпця, що дорівнюють нулю, завжди тотожні одиниці. У новій таблиці також будуть збережені і стовпець з нулем в ключовий рядку і рядок з нулем у ключовому стовпці. Запишіть результати перетворення змінних з першої таблиці.