Симплекс-метод розв’язання задачі лінійного програмування

Постановка задачі

Ця сторінка призначена для навчання студентів симплекс-методу розв’язання задачі лінійного програмування. На ній ви зможете розв’язати свій варіант ІДЗ. Задача лінійного програмування повинна бути заданою в канонічному вигляді:

Тут c = gradz − вектор-стовпчик довжини n; A − матриця розмвром r×n, що містить r базисних стовпців (по одній одиниці в кожному стовпці у різних рядках, решта елементів кожного такого стовпця − нулі); ранг цієї матриці rgA = r; b − вектор-стовпчик невід’ємних правих частин довжини n.

Якщо базисного розв’язку отримати не вдалося, скористайтеся методом штучного базису (двохетапним симплекс-методом).

З теорією розв’язання задачі лінійного програмування симплекс-методом можна ознайомитися, наприклад, в [1].

Розв’язання задачі

Введіть у наступних областях введення вектор c, матрицю A та вектор b.

В першій області введіть вектор c. Він вводиться у вигляді одновимірного масива довжиною n. Його довжина визначає кількість невідомих. Числа розділяйте пробілами.

У другій області введіть матрицю A з долученим до неї справа вектором-стовпчиком b. Розмір розширеної матриці (A|b) − r×(n+1). Числа в кожному рядку розділяйте пробілами, а рядки − переведенням на новий рядок (клавіши Enter або Return). Розміри цієї матриці визначають rgA = r − кількість незалежних обмежень-рівностей.

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

Увага! Щоб можна було вводити та вводити змінні у базис та з базису, дозвольте своєму браузеру створювати спливаючі вікна. Ніякої реклами на сторінці немає.

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

c =
(A|b) =