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

У тих випадках, коли в задачах є 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? 0.

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

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

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

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

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

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

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

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