Призначення сервісу. Онлайн-калькулятор призначений для вирішення завдань лінійного програмування симплексним методом шляхом переходу до КЗЛП і СЗЛП. При цьому завдання на мінімум цільової функції зводяться до задачі на пошук максимуму через перетворення цільової функції F * (X) = -F (X). Також є можливість скласти двоїсту задачу.
Інструкція. Виберіть кількість змінних і кількість рядків (кількість обмежень). Отримане рішення зберігається в файлі Word.
Перехід від завдання мінімізації цільової функції до задачі максимізації
Завдання мінімізації цільової функції F (X) легко може бути зведена до задачі максимізації функції F * (X) при тих же обмеженнях шляхом введення функції: F * (X) = -F (X). Обидва завдання мають одне і те ж рішення X *, і при цьому min (F (X)) = -max (F * (X)).
Проілюструємо цей факт графічно:
Для оптимізації функції мети використовуємо такі поняття і методи.
Опорний план - план з певними через вільні базисними змінними.
Базисний план - опорний план з нульовими базисними змінними.
Оптимальний план - базисний план, що задовольняє оптимальної функції мети (ФЦ).
Ведучий (що дозволяє) елемент - коефіцієнт вільної невідомої, яка стає базисної, а сам коефіцієнт перетворюється на одиницю.
Напрямна рядок - рядок провідного елементу, в якій розташована з одиничним коефіцієнтом базисна невідома, исключаемая при перетворенні (рядок з мінімальним граничним коефіцієнтом, див. Далі).
Направляючий стовпчик - стовпчик провідного елементу, вільна невідома якого перекладається в базисну (стовпець з максимальною вигодою, див. Далі).
Змінні x1. ..., xm. вхідні з одиничними коефіцієнтами тільки в одне рівняння системи, з нульовими - в інші, називаються базисними або залежними. У канонічної системі кожному рівнянню відповідає рівно одна базисна змінна. Перехід здійснюється за допомогою методу Гаусса-Жордана. Основна ідея цього методу полягає в зведенні системи m рівнянь з n невідомими до канонічного виду за допомогою елементарних операцій над рядками.
Решта n-m змінних (xm + 1, ..., xn) називаються небазисними або незалежними змінними.
Базисне рішення називається допустимим базисним рішенням. якщо значення назв базисних змінних xj ≥0, що еквівалентно умові незаперечності bj ≥0.
Допустиме базисне рішення є кутовий точкою допустимого безлічі S завдання лінійного програмування і називається іноді опорним планом.
Якщо серед невід'ємних чисел bj є рівні нулю, то допустиме базисне рішення називається виродженим (вироджених кутовий точкою) і відповідне завдання лінійного програмування називається вироджених.
Приклад №1. Звести задачу лінійного програмування до стандартної ЗЛП.
F (X) = x1 + 2x2 - 2x3 → min при обмеженнях:
4x1 + 3x2 - x3 ≤10
- 2x2 + 5x3 ≥3
x1 + 2x3 = 9
Для приведення ЗЛП до канонічної формі необхідно:
1. Поміняти знак у цільової функції. Зведемо задачу F (X) → min до задачі F (X) → max. Для цього множимо F (X) на (-1). У першому нерівності сенсу (≤) вводимо базисну змінну x4; у другому нерівності сенсу (≥) вводимо базисну змінну x5 зі знаком мінус.
4x1 + 3x2 -1x3 + 1x4 + 0x5 = 10
0x1 -2x2 + 5x3 + 0x4 -1x5 = 3
1x1 + 0x2 + 2x3 + 0x4 + 0x5 = 9
F (X) = - x1 - 2x2 + 2x3
Перехід до СЗЛП.
Розширена матриця системи обмежень-рівностей даної задачі: