Лекція 05. Симплекс-метод: логіка базису та перевірка чисельним розв’язувачем

Коротко про лекцію

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

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

Постановка та базові поняття

1. Яку проблему розв’язує симплекс-метод

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

Лінійна задача при цьому зберігає геометричну структуру, тому допустима множина залишається опуклою. Її кутові точки пов’язані з базисними допустимими планами.

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

Метод поєднує геометричну ідею та лінійну алгебру, тому графічна вершина отримує алгебраїчне подання через базис.

1.1. Звідки назва «симплекс» і що метод робить насправді

У геометрії симплекс — найпростіша фігура певної розмірності: у одному вимірі це відрізок, у двох — трикутник, у трьох — тетраедр. Назва «симплекс-метод» історично закріпилася за алгоритмом лінійного програмування. При цьому допустима область задачі не зобов’язана сама бути трикутником, тетраедром або іншим симплексом.

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

Операцію заміни однієї базисної змінної іншою часто називають опорний перехід. У студентському тексті далі використовуватимемо український вислів опорний перехід або поворотний крок, а назву pivot залишатимемо лише тоді, коли вона потрібна для API чи документації.

2. Наскрізна задача

Розглянемо просту задачу:

\[ \max Z=3x_1+2x_2 \]

за умов:

\[ x_1+x_2\le4 \]

\[ 2x_1+x_2\le5 \]

\[ x_1\ge0,\qquad x_2\ge0 \]

Змінна \(x_1\) описує перший вид діяльності. Змінна \(x_2\) описує другий.

Перше обмеження має запас 4 одиниці. Друге має запас 5 одиниць.

Задача маленька. Тому результат можна перевірити геометрично. Це робить її зручною для вивчення механіки симплекс-методу.

3. Чому нерівності переводять у рівності

Симплекс-метод працює із системою лінійних рівнянь. Тому введемо додаткові змінні.

Для першого обмеження:

\[ x_1+x_2+s_1=4 \]

Для другого:

\[ 2x_1+x_2+s_2=5 \]

Додаткові змінні мають умови:

\[ s_1\ge0,\qquad s_2\ge0 \]

Змінна \(s_1\) показує залишок першого ресурсу. Змінна \(s_2\) показує залишок другого.

Канонічна система має дві рівності та чотири невід’ємні змінні.

4. Матриця канонічної системи

Зберемо змінні в одному порядку:

\[ X= \begin{pmatrix} x_1 \\ x_2 \\ s_1 \\ s_2 \end{pmatrix} \]

Матриця системи:

\[ A= \begin{pmatrix} 1 & 1 & 1 & 0 \\ 2 & 1 & 0 & 1 \end{pmatrix} \]

Вектор правих частин:

\[ b= \begin{pmatrix} 4 \\ 5 \end{pmatrix} \]

Тому система записується компактно:

\[ AX=b \]

У матриці два рядки. Отже, базис міститиме дві змінні.

5. Що означає базис у цій задачі

Базис — набір змінних, стовпці яких утворюють невироджену квадратну матрицю розміру \(m\times m\).

У нашій системі:

\[ m=2 \]

Тому базис містить дві змінні.

Стовпці \(s_1\) і \(s_2\) утворюють одиничну матрицю.

\[ B= \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \]

Ця матриця легко обертається. Тому \(s_1\) і \(s_2\) створюють природний початковий базис.

6. Базисні та небазисні змінні

Базисні змінні обчислюються із системи рівнянь, а небазисні в поточній вершині покладають рівними нулю.

На початку небазисними є:

\[ x_1=0,\qquad x_2=0 \]

Тоді:

\[ s_1=4 \]

\[ s_2=5 \]

Початковий план:

\[ X^{(0)}= \begin{pmatrix} 0 \\ 0 \\ 4 \\ 5 \end{pmatrix} \]

Він допустимий, бо всі компоненти невід’ємні.

7. Геометричний зміст початкового базису

Для початкового плану:

\[ x_1=0,\qquad x_2=0 \]

На площині це точка:

\[ (0,0) \]

Отже, початковий базис відповідає одній вершині допустимої області.

Зміна базису переводить систему до іншої вершини, а симплекс-метод організовує такі переходи алгебраїчно.

Цей зв’язок з геометрією пояснює головну ідею методу.

Математична логіка

8. Чому потрібно обирати вхідну змінну

Початкове значення цілі:

\[ Z=0 \]

Цільова функція:

\[ Z=3x_1+2x_2 \]

Якщо збільшувати \(x_1\) від нуля, ціль зростає зі швидкістю 3 на одиницю.

Якщо збільшувати \(x_2\), ціль зростає зі швидкістю 2.

Для цього початкового словника \(x_1\) дає сильніше локальне поліпшення. Тому оберемо \(x_1\) вхідною змінною.

Вхідна змінна входить у базис, після чого її значення починає зростати з нуля.

9. Чому збільшувати змінну безмежно не можна

Збільшення \(x_1\) споживає обидва ресурси.

Покладемо:

\[ x_2=0 \]

Перше обмеження дає:

\[ x_1+s_1=4 \]

Оскільки \(s_1\ge0\):

\[ x_1\le4 \]

Друге обмеження:

\[ 2x_1+s_2=5 \]

Умова \(s_2\ge0\) дає:

\[ x_1\le2.5 \]

Друге обмеження зупиняє рух раніше.

10. Тест відношень

Попередній розрахунок можна записати через відношення правої частини до додатного коефіцієнта в стовпці вхідної змінної.

Для першого рядка:

\[ \frac{4}{1}=4 \]

Для другого:

\[ \frac{5}{2}=2.5 \]

Беремо найменше невід’ємне відношення.

\[ \theta=2.5 \]

Це максимальне допустиме збільшення \(x_1\) із поточної вершини.

Рядок із мінімальним відношенням визначає вихідну базисну змінну, тому в нашому випадку з базису виходить \(s_2\).

11. Чому тест відношень захищає допустимість

Поки:

\[ 0\le x_1\le2.5 \]

обидва залишки залишаються невід’ємними.

При:

\[ x_1=2.5 \]

маємо:

\[ s_2=0 \]

Друге обмеження стає активним.

Подальше збільшення \(x_1\) зробило б \(s_2\) від’ємним, тому друге обмеження було б порушене.

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

12. Перша нова вершина

Після першого переходу:

\[ x_1=2.5 \]

\[ x_2=0 \]

Перший залишок:

\[ s_1=4-2.5=1.5 \]

Другий залишок:

\[ s_2=0 \]

Отримуємо базисний план:

\[ X^{(1)}= \begin{pmatrix} 2.5 \\ 0 \\ 1.5 \\ 0 \end{pmatrix} \]

Ціль:

\[ Z=3\cdot2.5=7.5 \]

План залишається допустимим. Значення цілі зросло від 0 до 7.5.

13. Що таке опорний перехід

опорний перехід (ведуче перетворення) — алгебраїчна операція зміни базису.

У нашому переході \(x_1\) входить у базис. Змінна \(s_2\) виходить.

Потрібно переписати систему так, щоб \(x_1\) стала базисною змінною.

Другий рядок:

\[ 2x_1+x_2+s_2=5 \]

Ведучий коефіцієнт дорівнює 2.

Виразимо \(x_1\):

\[ x_1= 2.5- 0.5x_2- 0.5s_2 \]

Це центральний алгебраїчний крок першого опорний перехід.

14. Як опорний перехід пов’язаний із методом Жордана — Гаусса

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

Це та сама ідея, яка використовується у методі Жордана — Гаусса.

Мета перетворення — змінити систему координат усередині набору змінних. Новий базис повинен описувати ту саму систему рівнянь.

Тому опорний перехід не змінює допустиму множину. Він змінює спосіб подання поточної вершини.

15. Перепишемо перше рівняння

Перше рівняння:

\[ x_1+x_2+s_1=4 \]

Підставляємо вираз для \(x_1\).

\[ 2.5-0.5x_2-0.5s_2+x_2+s_1=4 \]

Збираємо члени.

\[ s_1= 1.5- 0.5x_2+ 0.5s_2 \]

Тепер базисними є \(x_1\) та \(s_1\).

Небазисні змінні:

\[ x_2=0,\qquad s_2=0 \]

Вони дають поточну вершину \((2.5,0)\).

16. Перепишемо цільову функцію

Початкова ціль:

\[ Z=3x_1+2x_2 \]

Підставляємо:

\[ x_1= 2.5- 0.5x_2- 0.5s_2 \]

Отримуємо:

\[ Z=3\left(2.5-0.5x_2-0.5s_2\right)+2x_2 \]

Після спрощення:

\[ Z= 7.5+ 0.5x_2- 1.5s_2 \]

Коефіцієнт при \(x_2\) додатний. Тому збільшення \(x_2\) здатне ще поліпшити ціль.

17. Другий вибір вхідної змінної

У поточному словнику небазисні змінні — \(x_2\) та \(s_2\).

Збільшення \(s_2\) зменшує ціль, бо його коефіцієнт дорівнює \(-1.5\).

Збільшення \(x_2\) підвищує ціль, бо коефіцієнт дорівнює \(0.5\).

Тому в базис входить \(x_2\).

Тепер потрібно визначити, яка базисна змінна першою досягне нуля.

18. Тест допустимості для другого переходу

Покладемо:

\[ s_2=0 \]

Маємо:

\[ s_1= 1.5- 0.5x_2 \]

Умова:

\[ s_1\ge0 \]

дає:

\[ x_2\le3 \]

Також:

\[ x_1= 2.5- 0.5x_2 \]

Умова \(x_1\ge0\) дає:

\[ x_2\le5 \]

Найжорсткіша межа:

\[ x_2\le3 \]

Тому першою до нуля доходить \(s_1\).

19. Друга нова вершина

При:

\[ x_2=3 \]

отримуємо:

\[ s_1=0 \]

Для \(x_1\):

\[ x_1= 2.5- 0.5\cdot3 \]

Тому:

\[ x_1=1 \]

Новий план:

\[ X^{(2)}= \begin{pmatrix} 1 \\ 3 \\ 0 \\ 0 \end{pmatrix} \]

Ціль:

\[ Z=3\cdot1+2\cdot3=9 \]

Обидва ресурсні обмеження стали активними.

19.1. Геометричний шлях двох опорних переходів

Початковий базис відповідає точці \((0,0)\). Перший опорний перехід переводить план у \((2.5,0)\), а другий — у \((1,3)\).

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

20. Другий опорний перехід у словниковій формі

Перед другим опорний перехід маємо:

\[ s_1= 1.5- 0.5x_2+ 0.5s_2 \]

Виразимо \(x_2\).

\[ 0.5x_2= 1.5+ 0.5s_2- s_1 \]

Тому:

\[ x_2= 3+ s_2- 2s_1 \]

Підставляємо цей вираз у формулу для \(x_1\).

\[ x_1= 2.5- 0.5x_2- 0.5s_2 \]

Отримуємо:

\[ x_1= 1+ s_1- s_2 \]

Новий базис складається з \(x_1\) та \(x_2\).

21. Фінальна форма цільової функції

Підставимо:

\[ x_2= 3+ s_2- 2s_1 \]

у попередню ціль:

\[ Z= 7.5+ 0.5x_2- 1.5s_2 \]

Після спрощення:

\[ Z= 9- s_1- s_2 \]

Ця формула дає сильну перевірку оптимальності.

Оскільки:

\[ s_1\ge0,\qquad s_2\ge0 \]

маємо:

\[ Z\le9 \]

Найбільше значення 9 досягається при:

\[ s_1=0,\qquad s_2=0 \]

Тому план \((1,3)\) є оптимальним.

22. Чому фінальний словник доводить оптимальність

Формула:

\[ Z= 9- s_1- s_2 \]

показує, що будь-яке збільшення небазисної змінної \(s_1\) або \(s_2\) зменшує ціль.

Невід’ємність цих змінних не дозволяє отримати значення \(Z>9\) у цьому представленні допустимих планів.

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

Для лінійної задачі ця умова відповідає глобальному оптимуму.

22.1. Що таке оцінка небазисної змінної

У словниковій формі ціль записують через небазисні змінні.

Після першого опорний перехід:

\[ Z= 7.5+ 0.5x_2- 1.5s_2 \]

Коефіцієнт 0.5 показує локальний вплив збільшення \(x_2\) на ціль, коли поточний базис зберігається.

Коефіцієнт \(-1.5\) показує, що збільшення \(s_2\) погіршує ціль.

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

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

22.2. Базис як квадратна підматриця

У загальній канонічній системі:

\[ AX=b \]

матриця \(A\) має \(m\) рядків.

Базис утворюють \(m\) лінійно незалежних стовпців \(A\).

Позначимо відповідну квадратну матрицю через \(B\).

Базисні змінні задовольняють:

\[ Bx_B=b \]

Якщо \(B\) невироджена, система має єдиний базисний розв’язок.

Небазисні змінні на поточній вершині дорівнюють нулю.

опорний перехід замінює один стовпець у \(B\). Тому симплекс-метод можна розглядати як послідовність пов’язаних систем лінійних рівнянь.

Алгоритм і покроковий розбір

23. Структура однієї симплекс-ітерації

Одна ітерація має чітку логіку.

1. Записати поточний базисний допустимий план.
2. Проаналізувати цільову функцію у поточному базисі.
3. Обрати небазисну змінну, яка поліпшує ціль.
4. Визначити максимальний допустимий крок.
5. Обрати вихідну базисну змінну.
6. Виконати опорний перехід.
7. Оновити ціль і базис.
8. Перевірити критерій оптимальності.

Кроки повторюються, поки існує напрям поліпшення.

23.1. Цикл симплекс-ітерації

flowchart TD
    A[Поточний базисний план] --> B[Оцінити небазисні змінні]
    B --> C{Є напрям поліпшення?}
    C -->|ні| D[Оптимальний базис]
    C -->|так| E[Обрати вхідну змінну]
    E --> F[Виконати тест відношень]
    F --> G[Обрати вихідну змінну]
    G --> H[Виконати pivot]
    H --> I[Перевірити допустимість і ціль]
    I --> A

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

24. Геометричне значення вхідної та вихідної змінних

Вхідна змінна задає напрям руху від поточної вершини.

Вихідна змінна визначає границю, яку ми досягаємо першою.

Тому ці два вибори виконують різні функції.

Вхідна змінна відповідає за поліпшення цілі. Вихідна змінна відповідає за збереження допустимості.

У геометричній картині це рух уздовж ребра до сусідньої вершини.

25. Що зберігає симплекс-таблиця

Симплекс-таблиця — компактна форма запису поточного словника.

У ній зберігаються:

1. назви базисних змінних;
2. коефіцієнти рівнянь;
3. праві частини;
4. коефіцієнти цільової функції;
5. дані для вибору опорний перехід.

Таблична форма може використовувати різні знакові домовленості для цільового рядка.

Тому під час ручного розрахунку потрібно зафіксувати одну форму й дотримуватися її до кінця.

26. Чому ручний словник корисний для навчання

Словникова форма показує причинний зміст кожного кроку.

Наприклад:

\[ s_1= 1.5- 0.5x_2+ 0.5s_2 \]

одразу показує, як збільшення \(x_2\) зменшує перший залишок.

Формула:

\[ Z= 7.5+ 0.5x_2- 1.5s_2 \]

одразу показує, яка небазисна змінна поліпшує ціль.

Таблиця стискає ці самі залежності. Для першого знайомства словник полегшує читання.

27. Як виявити необмеженість

Уявімо, що в цільовій функції є небазисна змінна з корисним коефіцієнтом.

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

Якщо жодне обмеження не створює верхньої межі для кроку, змінну можна збільшувати безмежно.

Тоді цільова функція теж поліпшується безмежно.

Це ознака необмеженої задачі.

28. Що таке виродження

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

Тоді опорний перехід може змінити базис без зміни точки на геометричному рисунку.

Значення цілі під час такого переходу теж може не змінитися.

Виродження ускладнює траєкторію методу. У спеціальних випадках можливе циклічне повторення базисів.

Промислові чисельні розв’язувачі використовують правила, які враховують такі ситуації.

29. Коли початковий базис очевидний

У ресурсній задачі виду:

\[ Ax\le b \]

з додатними правими частинами часто вводяться додаткові змінні:

\[ Ax+s=b \]

Їхні стовпці утворюють одиничну матрицю. Тому вони створюють простий початковий базис.

Початковий план тоді задається:

\[ x=0 \]

\[ s=b \]

Цей план допустимий, якщо:

\[ b\ge0 \]

Для складніших систем початковий базис може потребувати окремої процедури.

30. Чому канонічна форма важлива

Канонічна форма переводить задачу до системи рівнянь.

У ній базисні змінні можна визначати через лінійну алгебру.

У загальному випадку базисна матриця \(B\) складається з \(m\) лінійно незалежних стовпців матриці обмежень.

Базисні значення задовольняють:

\[ Bx_B=b \]

Тому:

\[ x_B=B^{-1}b \]

У чисельному коді обернену матрицю явно зазвичай не обчислюють. Розв’язують систему:

\[ Bx_B=b \]

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

30.1. Початковий базис у нашому прикладі

Матриця канонічної системи:

\[ A= \begin{pmatrix} 1 & 1 & 1 & 0 \\ 2 & 1 & 0 & 1 \end{pmatrix} \]

Стовпці додаткових змінних:

\[ A_{s_1}= \begin{pmatrix} 1 \\ 0 \end{pmatrix} \]

\[ A_{s_2}= \begin{pmatrix} 0 \\ 1 \end{pmatrix} \]

Разом вони утворюють:

\[ B_0= \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \]

Тому:

\[ B_0x_B=b \]

дає:

\[ x_B= \begin{pmatrix} 4 \\ 5 \end{pmatrix} \]

Це значення \(s_1\) та \(s_2\) у початковій вершині.

30.2. Базис після першого опорного переходу

Після входу \(x_1\) і виходу \(s_2\) базис утворюють стовпці \(s_1\) та \(x_1\).

\[ B_1= \begin{pmatrix} 1 & 1 \\ 0 & 2 \end{pmatrix} \]

Базисні значення задовольняють:

\[ \begin{aligned} B_1 \begin{pmatrix} s_1\\ x_1 \end{pmatrix} &= \begin{pmatrix} 4\\ 5 \end{pmatrix} \end{aligned} \]

З другого рівняння:

\[ 2x_1=5 \]

Тому:

\[ x_1=2.5 \]

З першого:

\[ s_1+x_1=4 \]

Отже:

\[ s_1=1.5 \]

Матричний і словниковий підходи дають ту саму вершину.

30.3. Базис у фінальній вершині

Після другого опорного переходу базисними стають \(x_1\) та \(x_2\).

\[ B_2= \begin{pmatrix} 1 & 1 \\ 2 & 1 \end{pmatrix} \]

Система:

\[ \begin{aligned} B_2 \begin{pmatrix} x_1\\ x_2 \end{pmatrix} &= \begin{pmatrix} 4\\ 5 \end{pmatrix} \end{aligned} \]

дає:

\[ x_1=1 \]

\[ x_2=3 \]

Геометрично це перетин двох активних ресурсних меж.

Програмна реалізація та перевірка

31. Що передаємо чисельний розв’язувач-у

Початкова задача має форму:

\[ \max Z=3x_1+2x_2 \]

за умов:

\[ \begin{aligned} \begin{pmatrix} 1 & 1\\ 2 & 1 \end{pmatrix} \begin{pmatrix} x_1\\ x_2 \end{pmatrix} &\le \begin{pmatrix} 4\\ 5 \end{pmatrix} \end{aligned} \]

Для scipy.optimize.linprog максимізацію перетворюємо на мінімізацію від’ємної цілі.

\[ \max Z \quad\Longleftrightarrow\quad \min(-Z) \]

32. Відповідність математики та Python

Математика	Python	Зміст
\((-3,-2)^T\)	objective	ціль для linprog
\(A\)	constraint_matrix	коефіцієнти обмежень
\(b\)	constraint_limits	праві частини
\(x^*\)	result.x	знайдений план
\(Z^*\)	-result.fun	максимум початкової цілі

33. Чисельний розв’язувач-перевірка через SciPy

# Імпортуємо NumPy, SciPy для обчислень, розв’язання моделі та її перевірки.
import numpy as np
from scipy.optimize import linprog


# Початкова модель максимізує 3*x1 + 2*x2.
# linprog розв'язує мінімізацію,
# тому коефіцієнти цілі отримують знак мінус.
objective = np.array([
    -3.0,
    -2.0,
])

# Рядки відповідають двом
# ресурсним обмеженням.
constraint_matrix = np.array([
    [1.0, 1.0],
    [2.0, 1.0],
])

# Задаємо праві частини, запаси або спостереження у порядку, узгодженому з рядками матриці.
constraint_limits = np.array([
    4.0,
    5.0,
])

# Запускаємо linprog: ціль, матрицю нерівностей, праві частини та межі передаємо у фіксованому порядку.
result = linprog(
    c=objective,
    A_ub=constraint_matrix,
    b_ub=constraint_limits,
    bounds=(0.0, None),
    method="highs",
)

# Перевіряємо статус розв’язувача до читання числового плану; невдалий запуск не є розв’язком.
if not result.success:
    raise RuntimeError(result.message)

# Зчитуємо числовий результат розв’язувача, але ще не вважаємо його перевіреним розв’язком.
optimal_plan = result.x
maximum_value = -result.fun

# Виконуємо матричний або скалярний добуток, який прямо відповідає формулі математичної моделі.
used_resources = (
    constraint_matrix
    @ optimal_plan
)

# Обчислюємо нев’язку або запас безпосередньо з початкових формул для незалежної перевірки.
resource_slack = (
    constraint_limits
    - used_resources
)

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print("Оптимальний план:", optimal_plan)
print("Максимум:", maximum_value)
print("Використано ресурсів:", used_resources)
print("Залишки ресурсів:", resource_slack)
print("Статус:", result.status)

Очікуваний результат:

Оптимальний план: [1. 3.]
Максимум: 9.0
Використано ресурсів: [4. 5.]
Залишки ресурсів: [0. 0.]
Статус: 0

34. Математична перевірка знайденого плану

Перевіримо перше обмеження.

\[ 1+3=4 \]

Маємо:

\[ 4\le4 \]

Друге обмеження:

\[ 2\cdot1+3=5 \]

Тому:

\[ 5\le5 \]

Обидва обмеження активні.

Ціль:

\[ Z=3\cdot1+2\cdot3=9 \]

Результат чисельного розв’язувача збігається з ручними опорний перехід-переходами.

35. Перевірка через фінальний словник

Ручний розрахунок дав:

\[ Z= 9- s_1- s_2 \]

Оскільки залишки невід’ємні:

\[ s_1\ge0,\qquad s_2\ge0 \]

маємо:

\[ Z\le9 \]

Чисельний розв’язувач повернув план із:

\[ s_1=0,\qquad s_2=0 \]

Тому його значення цілі досягає верхньої межі 9.

Це незалежна математична перевірка оптимальності для навчального прикладу.

35.0. Як змінювалася ціль під час ітерацій

На початковій вершині маємо \(Z=0\). Після першого опорного переходу значення зростає до \(7.5\), а після другого — до \(9\).

Графік показує прогрес ітерацій, але доказ оптимальності дає фінальний словник \(Z=9-s_1-s_2\) разом із невід’ємністю залишків.

35.1. Як перевірити базисний план програмно

Для навчальної задачі можна окремо перевірити фінальний базис через np.linalg.solve.

# Імпортуємо NumPy для обчислень, розв’язання моделі та її перевірки.
import numpy as np


# Обчислюємо величину, пов’язану з базисом або перевіркою симплекс-розв’язку.
basis_matrix = np.array([
    [1.0, 1.0],
    [2.0, 1.0],
])

# Задаємо праві частини, запаси або спостереження у порядку, узгодженому з рядками матриці.
right_side = np.array([
    4.0,
    5.0,
])

# У фінальному базисі змінними є x1 та x2.
basic_variables = np.linalg.solve(
    basis_matrix,
    right_side,
)

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print("Базисні змінні:", basic_variables)

Очікувано:

Базисні змінні: [1. 3.]

Цей код не виконує симплекс-пошук. Він перевіряє конкретний базис, знайдений ручними опорними кроками.

35.2. Множинний оптимум у симплекс-логіці

У фінальному словнику інколи небазисна змінна має нульову оцінку.

Тоді її збільшення може зберігати те саме значення цілі.

Геометрично це відповідає оптимальному ребру.

У такій ситуації існують різні оптимальні базисні плани з однаковим значенням цільової функції.

Цей випадок узгоджується з геометричною картиною попередньої лекції.

35.3. Коли потрібен окремий пошук початкового базису

Додаткові змінні дають очевидний початковий базис для ресурсних нерівностей із невід’ємними правими частинами.

Загальна LP може містити рівності або обмеження іншого напрямку. Тоді природної одиничної підматриці може не бути.

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

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

Інтерпретація, межі та підсумок

36. Що означає результат предметно

Оптимальний план:

\[ x^*= \begin{pmatrix} 1 \\ 3 \end{pmatrix} \]

означає одну одиницю першої діяльності та три одиниці другої.

Обидва ресурси використані повністю.

\[ s_1=0 \]

\[ s_2=0 \]

Цільова функція дорівнює 9.

Такий висновок повинен завершувати математичний і програмний розрахунок.

37. Чому сучасний курс не потребує десятків ручних таблиць

Дві ручні ітерації показують основну логіку методу.

Студент бачить:

1. початковий базис;
2. вибір вхідної змінної;
3. тест відношень;
4. вихідну змінну;
5. опорний перехід;
6. оновлення цілі;
7. критерій зупинки.

Подальше повторення тієї самої арифметики дає менше нового змісту.

Для великих задач практично важливі формулювання моделі, статус чисельного розв’язувача і математична перевірка.

38. Які сигнали потрібно перевіряти після чисельного розв’язувача

Числовий вектор потрібно читати разом із діагностикою.

Для базової LP достатньо перевірити:

1. успішний статус;
2. невід’ємність змінних;
3. виконання обмежень;
4. повторне значення цілі;
5. залишки ресурсів.

У наступній лекції двоїстість додасть ще один сильний критерій перевірки.

39. Типові помилки під час ручного опорний перехід

Перша помилка — вибір змінної, яка не поліпшує ціль у прийнятій формі словника.

Друга помилка — використання неправильного відношення під час тесту допустимості.

Третя помилка — часткове опорне перетворення. Ведучий стовпець повинен відповідати новій базисній змінній.

Четверта помилка — зміна знакової домовленості посеред розрахунку.

П’ята помилка — відсутність перевірки кінцевого плану в початковій задачі.

39.1. Симплекс-метод як повторюваний контракт

Кожна ітерація повинна зберігати три властивості.

Перша властивість — еквівалентність системи. Опорний перехід переписує ті самі рівняння в новому базисі.

Друга властивість — допустимість поточного плану. Тест відношень контролює невід’ємність базисних змінних.

Третя властивість — напрям цільового поліпшення. Вхідна змінна вибирається за оцінкою поточного словника.

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

39.2. Що студент повинен перевіряти вручну під час опорного переходу

Після кожного переходу корисно виконати коротку самоперевірку.

1. Нова базисна змінна має правильний ведучий стовпець.
2. Значення базисних змінних залишаються невід’ємними.
3. Новий словник описує ту саму систему обмежень.
4. Значення цілі відповідає новому плану.
5. Вхідна та вихідна змінні справді помінялися ролями.

Ці п’ять перевірок ловлять більшість арифметичних помилок у навчальній симплекс-ітерації.

Інтерактивна самоперевірка лекції

Пройдіть 10 коротких питань. Після кожної відповіді ви побачите пояснення, а за потреби — підказку й повний розбір.

40. Підсумок

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

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

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