Двоїстий симплекс-метод онлайн калькулятор з покроковим розв'язком

Кількість обмежень:

Кількість змінних:

F =

matrixF,0,0,matrix

x₁

matrixF,0,1,matrix

x₂

matrixF,0,2,matrix

x₃

matrixF,0,3,matrix

x₄

→

matrixA,0,0,matrix

x₁

matrixA,0,1,matrix

x₂

matrixA,0,2,matrix

x₃

matrixA,0,3,matrix

x₄

matrixA,0,4,matrix

matrixA,1,0,matrix

x₁

matrixA,1,1,matrix

x₂

matrixA,1,2,matrix

x₃

matrixA,1,3,matrix

x₄

matrixA,1,4,matrix

matrixA,2,0,matrix

x₁

matrixA,2,1,matrix

x₂

matrixA,2,2,matrix

x₃

matrixA,2,3,matrix

x₄

matrixA,2,4,matrix

matrixA,3,0,matrix

x₁

matrixA,3,1,matrix

x₂

matrixA,3,2,matrix

x₃

matrixA,3,3,matrix

x₄

matrixA,3,4,matrix

=Розв'язати

Про калькулятор двоїстого симплекс-методу

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

Щоб почати обчислення, спочатку необхідно ввести розміри задачі у поля вводу у верхній частині екрана, а також вибрати потрібну операцію з бічного меню.

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

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

Далі внизу знаходиться панель інструментів, яка дозволяє налаштувати калькулятор та спростити роботу з ним. Вона візуально розділена на три частини, кожна з яких відповідає за таку функціональність:

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

Що таке двоїстий симплекс-метод?

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

Як розв'язати задачу лінійного програмування двоїстим симплекс-методом?

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

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

Перехід до двоїстого симплексу

F(x) = 3x₁+4x₂ → max

2x₁+x₂ ≤ 600

≤ 225

5x₁+4x₂ ≤ 1000

-2x₂ ≤ -150

≤ 0

Z(t) = 600t₁+225t₂+1000t₃-150t₄+0t₅ → min

2t₁+5t₃ ≥ 3

t₁+4t₃-2t₄ ≥ 4

Правила переходу

1) Коефіцієнти правої частини обмежень прямої задачі стають коефіцієнтами цільової функції двоїстого симплексу;

2) Коефіцієнти лівої частини обмежень двоїстого симплексу формуються транспонуванням матриці коефіцієнтів лівої частини обмежень прямої задачі;

3) Коефіцієнти правої частини обмежень двоїстого симплексу формуються зі значень цільової функції прямої задачі для відповідних керованих змінних;

4) Якщо F → max , то Z → min
Якщо ≤ , то ≥
Якщо = , то ≥

5) Якщо F → min , то Z → max
Якщо ≥ , то ≤
Якщо = , то ≤

Опис

F(x) = 600x₁+225x₂+1000x₃-150x₄+0x₅ → min

F(x) = 600x₁+225x₂+1000x₃-150x₄+0x₅+0x₆+0x₇+Mx₈+Mx₉ → min

2x₁+5x₃ ≥ 3

2x₁+5x₃-x₆+x₈ = 3

x₁+4x₃-2x₄ ≥ 4

x₁+4x₃-2x₄-x₇+x₉ = 4

Попередній етап починається з необхідності позбутися від'ємних значень у правій частині обмежень. Для цього відповідні обмеження множаться на -1. Після цієї маніпуляції знак нерівності змінюється на протилежний.

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

Тепер у системі обмежень необхідно знайти достатню кількість базисних змінних. Кожне обмеження повинно мати одну базисну змінну. Базисна — це змінна, яка має коефіцієнт 1 при ній та зустрічається лише в одному обмеженні. Якщо в деякому обмеженні базисних змінних немає, то ми додаємо їх штучно, і штучні змінні входять до цільової функції з коефіцієнтом -M, якщо цільова функція прямує до max, і M, якщо цільова функція прямує до min.

Опис

Ітерація 1

B	Cb	P	x₁	x₂	x₃↓	x₄	x₆	x₇	x₈	x₉	Q
B	Cb	P	600	225	1000	-150	0	0	M	M	Q
x₈←	M	3	2	0	5	0	-1	0	1	0	35
x₉	M	4	1	0	4	-2	0	-1	0	1	1
min		7M	3M-600	-225	9M-1000	-2M+150	-M	-M	0	0

Елементи стовпця базису (B)

Переносимо до таблиці базисні елементи, які були визначені на попередньому етапі:

B₁ = x₈;

B₂ = x₉;

Елементи стовпця Cb

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

Cb₁ = M;

Cb₂ = M;

Значення вільних змінних і стовпця P

На цьому етапі обчислень не потрібно, просто переносимо значення з попереднього етапу до відповідних клітинок таблиці:

P₁ = 3;

P₂ = 4;

x_1,1 = 2;

x_1,2 = 0;

x_1,3 = 5;

x_1,4 = 0;

x_1,5 = 0;

x_1,6 = -1;

x_1,7 = 0;

x_1,8 = 1;

x_1,9 = 0;

x_2,1 = 1;

x_2,2 = 0;

x_2,3 = 4;

x_2,4 = -2;

x_2,5 = 0;

x_2,6 = 0;

x_2,7 = -1;

x_2,8 = 0;

x_2,9 = 1;

Значення цільової функції

Обчислюємо значення цільової функції шляхом поелементного множення стовпця Cb на стовпець P та підсумовування результатів добутків.

Min_P = (Cb₁ * P₁) + (Cb₂ * P₂) = (M * 3) + (M * 4) = 7M;

Оцінки керованих змінних

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

Min_x₁ = ((Cb₁ * x_1,1) + (Cb₂ * x_2,1)) - k_x₁ = ((M * 2) + (M * 1)) - 600 = 3M-600;

Min_x₂ = ((Cb₁ * x_1,2) + (Cb₂ * x_2,2)) - k_x₂ = ((M * 0) + (M * 0)) - 225 = -225;

Min_x₃ = ((Cb₁ * x_1,3) + (Cb₂ * x_2,3)) - k_x₃ = ((M * 5) + (M * 4)) - 1000 = 9M-1000;

Min_x₄ = ((Cb₁ * x_1,4) + (Cb₂ * x_2,4)) - k_x₄ = ((M * 0) + (M * -2)) - -150 = -2M+150;

Min_x₅ = ((Cb₁ * x_1,5) + (Cb₂ * x_2,5)) - k_x₅ = ((M * 0) + (M * 0)) - 0 = 0;

Min_x₆ = ((Cb₁ * x_1,6) + (Cb₂ * x_2,6)) - k_x₆ = ((M * -1) + (M * 0)) - 0 = -M;

Min_x₇ = ((Cb₁ * x_1,7) + (Cb₂ * x_2,7)) - k_x₇ = ((M * 0) + (M * -1)) - 0 = -M;

Min_x₈ = ((Cb₁ * x_1,8) + (Cb₂ * x_2,8)) - k_x₈ = ((M * 1) + (M * 0)) - M = 0;

Min_x₉ = ((Cb₁ * x_1,9) + (Cb₂ * x_2,9)) - k_x₉ = ((M * 0) + (M * 1)) - M = 0;

Елементи стовпця Q

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

Кількість змінних у базисі завжди стала, тому необхідно вибрати, яку змінну виводити з базису, для чого обчислюємо Q.

Елементи стовпця Q обчислюються шляхом ділення значень зі стовпця P на значення зі стовпця, що відповідає змінній, яка вводиться до базису:

Q₁ = P₁x_1,3 = 35 = 35;

Q₂ = P₂x_2,3 = 44 = 1;

Виводимо з базису змінну з найменшим додатним значенням Q.

На перетині рядка, що відповідає змінній, яка виводиться з базису, і стовпця, що відповідає змінній, яка вводиться до базису, знаходиться розв'язуючий елемент.

Цей елемент дозволить нам обчислити елементи таблиці наступної ітерації.

Опис

Ітерація 2

B	Cb	P	x₁	x₂	x₃	x₄	x₆↓	x₇	x₈	x₉	Q
B	Cb	P	600	225	1000	-150	0	0	M	M	Q
x₃	1000	35	25	0	1	0	-15	0	15	0	∞
x₉←	M	135	-35	0	0	-2	45	-1	-45	1	2
min		135M+600	-35M-200	-225	0	-2M+150	45M-200	-M	-145M+200	0

Елементи стовпця базису (B)

За результатами обчислень попередньої ітерації виводимо змінну з базису x₈ та ставимо на її місце x₃. Всі інші клітинки залишаються незмінними.

Елементи стовпця Cb

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

Cb₁ = 1000;

Cb₂ = M;

Значення вільних змінних і стовпця P

(Дані з попередньої ітерації беруться як вхідні дані)

Заповнюємо нулями всі клітинки, що відповідають змінній, яка щойно введена до базису:

(Розв'язуючий елемент залишається незмінним)

x_2,3 = 0;

Переносимо рядок з розв'язуючим елементом із попередньої таблиці до поточної, поелементно поділивши його значення на розв'язуючий елемент:

x_1,1 = x_1,1x_1,3 = 25 = 25;

x_1,2 = x_1,2x_1,3 = 05 = 0;

x_1,3 = x_1,3x_1,3 = 55 = 1;

x_1,4 = x_1,4x_1,3 = 05 = 0;

x_1,5 = x_1,5x_1,3 = 05 = 0;

x_1,6 = x_1,6x_1,3 = -15 = -15;

x_1,7 = x_1,7x_1,3 = 05 = 0;

x_1,8 = x_1,8x_1,3 = 15 = 15;

x_1,9 = x_1,9x_1,3 = 05 = 0;

P₁ = P₁x_1,3 = 35 = 35;

Решта порожніх клітинок, крім рядка оцінок та стовпця Q, обчислюються методом прямокутника відносно розв'язуючого елемента:

x_2,1 = (x_2,1 * x_1,3) - (x_2,3 * x_1,1)x_1,3 = (1 * 5) - (4 * 2)5 = -35;

x_2,2 = (x_2,2 * x_1,3) - (x_2,3 * x_1,2)x_1,3 = (0 * 5) - (4 * 0)5 = 0;

x_2,4 = (x_2,4 * x_1,3) - (x_2,3 * x_1,4)x_1,3 = (-2 * 5) - (4 * 0)5 = -2;

x_2,5 = (x_2,5 * x_1,3) - (x_2,3 * x_1,5)x_1,3 = (0 * 5) - (4 * 0)5 = 0;

x_2,6 = (x_2,6 * x_1,3) - (x_2,3 * x_1,6)x_1,3 = (0 * 5) - (4 * -1)5 = 45;

x_2,7 = (x_2,7 * x_1,3) - (x_2,3 * x_1,7)x_1,3 = (-1 * 5) - (4 * 0)5 = -1;

x_2,8 = (x_2,8 * x_1,3) - (x_2,3 * x_1,8)x_1,3 = (0 * 5) - (4 * 1)5 = -45;

x_2,9 = (x_2,9 * x_1,3) - (x_2,3 * x_1,9)x_1,3 = (1 * 5) - (4 * 0)5 = 1;

P₂ = (P₂ * x_1,3) - (x_2,3 * P₁)x_1,3 = (4 * 5) - (4 * 3)5 = 135;

Значення цільової функції

Min_P = (Cb₁ * P₁) + (Cb₂ * P₂) = (1000 * 35) + (M * 135) = 135M+600;

Оцінки керованих змінних

Min_x₁ = ((Cb₁ * x_1,1) + (Cb₂ * x_2,1)) - k_x₁ = ((1000 * 25) + (M * -35)) - 600 = -35M-200;

Min_x₂ = ((Cb₁ * x_1,2) + (Cb₂ * x_2,2)) - k_x₂ = ((1000 * 0) + (M * 0)) - 225 = -225;

Min_x₃ = ((Cb₁ * x_1,3) + (Cb₂ * x_2,3)) - k_x₃ = ((1000 * 1) + (M * 0)) - 1000 = 0;

Min_x₄ = ((Cb₁ * x_1,4) + (Cb₂ * x_2,4)) - k_x₄ = ((1000 * 0) + (M * -2)) - -150 = -2M+150;

Min_x₅ = ((Cb₁ * x_1,5) + (Cb₂ * x_2,5)) - k_x₅ = ((1000 * 0) + (M * 0)) - 0 = 0;

Min_x₆ = ((Cb₁ * x_1,6) + (Cb₂ * x_2,6)) - k_x₆ = ((1000 * -15) + (M * 45)) - 0 = 45M-200;

Min_x₇ = ((Cb₁ * x_1,7) + (Cb₂ * x_2,7)) - k_x₇ = ((1000 * 0) + (M * -1)) - 0 = -M;

Min_x₈ = ((Cb₁ * x_1,8) + (Cb₂ * x_2,8)) - k_x₈ = ((1000 * 15) + (M * -45)) - M = -145M+200;

Min_x₉ = ((Cb₁ * x_1,9) + (Cb₂ * x_2,9)) - k_x₉ = ((1000 * 0) + (M * 1)) - M = 0;

Елементи стовпця Q

Q₁ = P₁x_1,6 = 35-15 = ∞;

Q₂ = P₂x_2,6 = 13545 = 2;

Виводимо з базису змінну з найменшим додатним значенням Q.

Цей елемент дозволить нам обчислити елементи таблиці наступної ітерації.

Опис

Ітерація 3

B	Cb	P	x₁	x₂	x₃	x₄	x₆	x₇	x₈	x₉	Q
B	Cb	P	600	225	1000	-150	0	0	M	M	Q
x₃	1000	1	14	0	1	-12	0	-14	0	14
x₆	0	2	-34	0	0	-212	1	-114	-1	114
min		1000	-350	-225	0	-350	0	-250	-M	-M+250

Елементи стовпця базису (B)

За результатами обчислень попередньої ітерації виводимо змінну з базису x₉ та ставимо на її місце x₆. Всі інші клітинки залишаються незмінними.

Елементи стовпця Cb

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

Cb₁ = 1000;

Cb₂ = 0;

Значення вільних змінних і стовпця P

(Дані з попередньої ітерації беруться як вхідні дані)

Заповнюємо нулями всі клітинки, що відповідають змінній, яка щойно введена до базису:

(Розв'язуючий елемент залишається незмінним)

x_1,6 = 0;

x_2,1 = x_2,1x_2,6 = -3545 = -34;

x_2,2 = x_2,2x_2,6 = 045 = 0;

x_2,3 = x_2,3x_2,6 = 045 = 0;

x_2,4 = x_2,4x_2,6 = -245 = -212;

x_2,5 = x_2,5x_2,6 = 045 = 0;

x_2,6 = x_2,6x_2,6 = 4545 = 1;

x_2,7 = x_2,7x_2,6 = -145 = -114;

x_2,8 = x_2,8x_2,6 = -4545 = -1;

x_2,9 = x_2,9x_2,6 = 145 = 114;

P₂ = P₂x_2,6 = 13545 = 2;

x_1,1 = (x_1,1 * x_2,6) - (x_1,6 * x_2,1)x_2,6 = (25 * 45) - (-15 * -35)45 = 14;

x_1,2 = (x_1,2 * x_2,6) - (x_1,6 * x_2,2)x_2,6 = (0 * 45) - (-15 * 0)45 = 0;

x_1,3 = (x_1,3 * x_2,6) - (x_1,6 * x_2,3)x_2,6 = (1 * 45) - (-15 * 0)45 = 1;

x_1,4 = (x_1,4 * x_2,6) - (x_1,6 * x_2,4)x_2,6 = (0 * 45) - (-15 * -2)45 = -12;

x_1,5 = (x_1,5 * x_2,6) - (x_1,6 * x_2,5)x_2,6 = (0 * 45) - (-15 * 0)45 = 0;

x_1,7 = (x_1,7 * x_2,6) - (x_1,6 * x_2,7)x_2,6 = (0 * 45) - (-15 * -1)45 = -14;

x_1,8 = (x_1,8 * x_2,6) - (x_1,6 * x_2,8)x_2,6 = (15 * 45) - (-15 * -45)45 = 0;

x_1,9 = (x_1,9 * x_2,6) - (x_1,6 * x_2,9)x_2,6 = (0 * 45) - (-15 * 1)45 = 14;

P₁ = (P₁ * x_2,6) - (x_1,6 * P₂)x_2,6 = (35 * 45) - (-15 * 135)45 = 1;

Значення цільової функції

Min_P = (Cb₁ * P₁) + (Cb₂ * P₂) = (1000 * 1) + (0 * 2) = 1000;

Оцінки керованих змінних

Min_x₁ = ((Cb₁ * x_1,1) + (Cb₂ * x_2,1)) - k_x₁ = ((1000 * 14) + (0 * -34)) - 600 = -350;

Min_x₂ = ((Cb₁ * x_1,2) + (Cb₂ * x_2,2)) - k_x₂ = ((1000 * 0) + (0 * 0)) - 225 = -225;

Min_x₃ = ((Cb₁ * x_1,3) + (Cb₂ * x_2,3)) - k_x₃ = ((1000 * 1) + (0 * 0)) - 1000 = 0;

Min_x₄ = ((Cb₁ * x_1,4) + (Cb₂ * x_2,4)) - k_x₄ = ((1000 * -12) + (0 * -212)) - -150 = -350;

Min_x₅ = ((Cb₁ * x_1,5) + (Cb₂ * x_2,5)) - k_x₅ = ((1000 * 0) + (0 * 0)) - 0 = 0;

Min_x₆ = ((Cb₁ * x_1,6) + (Cb₂ * x_2,6)) - k_x₆ = ((1000 * 0) + (0 * 1)) - 0 = 0;

Min_x₇ = ((Cb₁ * x_1,7) + (Cb₂ * x_2,7)) - k_x₇ = ((1000 * -14) + (0 * -114)) - 0 = -250;

Min_x₈ = ((Cb₁ * x_1,8) + (Cb₂ * x_2,8)) - k_x₈ = ((1000 * 0) + (0 * -1)) - M = -M;

Min_x₉ = ((Cb₁ * x_1,9) + (Cb₂ * x_2,9)) - k_x₉ = ((1000 * 14) + (0 * 114)) - M = -M+250;

Відповідь

Оскільки серед оцінок керованих змінних немає додатних значень, поточна таблиця має оптимальний розв'язок.

Значення цільової функції:

F* = 1000;

Змінні, що присутні в базисі, дорівнюють відповідним клітинкам стовпця P, всі інші змінні дорівнюють нулю:

x₁ = 0;

x₂ = 0;

x₃ = 1;

x₄ = 0;

x₅ = 0;

Опис

Answer

F → max

F* = 1000

X* = (0; 0; 1; 0; 0)

Змінні2Обмеження5Цільова функціяmaxF*1000

Часті запитання

Що таке двоїстий симплекс-метод?

Двоїстий симплекс-метод зберігає виконання умови оптимальності, водночас відновлюючи допустимість — на противагу прямому симплекс-методу, який зберігає допустимість і прямує до оптимальності. Він корисний, коли початковий базис є оптимальним, але недопустимим.

Коли слід використовувати двоїстий симплекс-метод замість прямого?

Він найефективніший, коли у вас уже є двоїсто-допустимий (оптимальний, але недопустимий) базис — наприклад, після додавання обмеження до розв'язаної задачі або під час аналізу чутливості — оскільки він може повторно оптимізувати без перезапуску з нуля.

Як двоїстий симплекс-метод пов'язаний з прямою задачею?

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

Чи дає двоїстий симплекс-метод той самий оптимум, що й прямий симплекс-метод?

Так. Для задачі зі скінченним оптимумом обидва методи досягають одного й того самого оптимального значення цільової функції та оптимального розв'язку; вони відрізняються лише шляхом, пройденим через таблиці.

Джерела

Google Play App Store

x_i ↓	— вводимо змінну до базису;
x_i←	— виводимо змінну з базису;
x_i	— розв'язуючий елемент;
x_i	— базисний елемент;
B	— базис;
Cb	— коефіцієнт при базисній змінній;
P	— план;

Про калькулятор двоїстого симплекс-методу

Що таке двоїстий симплекс-метод?

Як розв'язати задачу лінійного програмування двоїстим симплекс-методом?

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

Часті запитання

Пов'язані калькулятори

Джерела