Симплекс-метод онлайн

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

Інструкція. Виберіть кількість змінних і кількість рядків (кількість обмежень). Отримане рішення зберігається в файлі Word і Excel. При цьому обмеження типу xi ≥ 0 не зважайте. Якщо в завданні для деяких xi відсутні обмеження, то ЗЛП необхідно привести до КЗЛП, або скористатися цим сервісом. При вирішенні автоматично визначається використання М-методу (симплекс-метод зі штучним базисом) і двоетапного симплекс-методу.

Разом з цим калькулятором також використовують такі:

Рішення матричної гри
За допомогою сервісу в онлайн режимі можна визначити ціну матричної гри (нижню і верхню межі), перевірити наявність сідлової точки, знайти рішення змішаної стратегії методами: минимакс, симплекс-метод, графічний (геометричний) метод, методом Брауна.

Завдання динамічного програмування
Розподілити 5 однорідних партій товару між трьома ринками так, щоб отримати максимальний дохід від їх продажу. Дохід від продажу на кожному ринку G (X) залежить від кількості реалізованих партій товару Х і представлений в таблиці.

Обсяг товару Х (в партіях)

Якщо необхідно знайти екстремум цільової функції, то мова йде про пошук мінімального значення (F (x) → min. См. Приклад рішення мінімізації функції) і максимального значення ((F (x) → max. См. Приклад рішення максимізації функції)

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

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

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

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

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

Зауваження 2. Нехай в деякій крайній точці все сімплексні різниці невід'ємні Dk ³ 0 (k = 1..n + m), тобто. отримано оптимальне рішення і існує такий Аk - небазисной вектор, у якого Dk = 0. Тоді максимум досягається принаймні в двох точках, тобто має місце альтернативний оптимум. Якщо ввести в базис цю змінну xk. значення цільової функції не зміниться.

Зауваження 3. Рішення двоїстої задачі знаходиться в останній симплексній таблиці. Останні m компонент вектора симплексних різниць (в шпальтах балансових змінних) - оптимальне рішення двоїстої задачі. Значення цільових функцій прямої та двоїстої задачі в оптимальних точках збігаються.

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

Якщо задана умова «Необхідно, щоб сировина III виду було витрачено повністю», то відповідна умова є рівність.