сними змінними.
З вищевикладеного слід , що при реалізації симплекс-
методу алгебраїчне визначення базисних рішень відпо-
яття ідентифікації екстремальних точок , здійснюваної при
геометричному поданні простору рішень . Таким об-
разом , максимальне число ітерацій при використанні симплекс-
методу дорівнює максимальному числу базисних рішень задачі ЛП ,
представленої в стандартній формі . Це означає , що кількість
ітераційних процедур симплекс-методу не перевищує
C п т = n! /[(N - m)! M! ]
Друга з раніше відмічених закономірностей виявляється
досить корисною для побудови обчислювальних процедур симп-
лекс-методу , при реалізації якого здійснюється послідовно-
вальний перехід від однієї екстремальної точки до іншої, суміжної з ній . Так як суміжні екстремальні точки відрізняються тільки
однієї змінної, можна визначити кожну наступну (смеж-
ву) екстремальну точку шляхом заміни однієї з поточних НЕ-
базисних (нульових) змінних поточної базисної змінної.
У нашому випадку отримано рішення , відповідне точці А , звідки слід здійснити перехід в точку В. Для цього потрібно збільшувати небазисной змінну X 2 від вихідного нульового значення до значе-
ня , відповідного точці В (див. рис. 1 ). У точці B мінлива
S 1 (яка в точці А була базисної) автоматично звертається в
нуль і, отже, стає небазисной змінної . Таким
чином, між безліччю небазисних і безліччю базисних
змінних відбувається взаємообмін перемінними X 2 і S 1 . Цей
процес можна наочно представити у вигляді такої таблиці.
Екстремальна точка
Нульові змінні
Ненульові змінні
А
S 2 , X 2
S 1 , X 1
В
S 1 , X 2
S 2 , X 1
Застосовуючи аналогічну процедуру до всіх екстремальним точкам
рис. 1, можна переконатися в тому , що будь-яку подальшу екстра-
мальную точку завжди можна визначити шляхом взаємної заміни
по одній змінній у складі базисних і небазисних змінних
(Попередньої суміжною точки). Цей фактор істотно спрощує
реалізацію обчислювальних процедур симплекс-методу.
Розглянутий процес взаємної заміни змінних призводить
до необхідності введення двох нових термінів . Включаемой пе-
пасової називається небазисна в даний момент змінна,
яка буде включена в безліч базисних змінних на сле-
дующей ітерації (при переході до суміжною екстремальній точці).
Исключаемая змінна - це та базисна змінна, яка
на наступній ітерації підлягає виключенню з безлічі ба-
базисних змінних.
Обчислювальні процедури симплекс-методу.
В
з Імплекс-алгоритм складається з наступних кроків.
Крок 0. Використовуючи лінійну модель стандартної форми, визна-
ляють початкова дозволене базисне рішення шляхом прирівнюючи-
ня до нуля п - т (небазисних) змінних.
Крок 1. З числа поточних небазисних (рівних нулю) змін-
них вибирається включається в новий базис змінна, збільшення
якої забезпечує поліпшення значення цільової функції. Якщо
такої змінної немає, обчислення припиняються, так як поточне
базисне рішення оптимально. В іншому випадку здійснюється
перехід до кроку 2.
Крок 2. З числа змінних поточного базису вибирається исклю-
чаемая змінна, яка повинна прийняти нульове значення (стати
небазисной) при введенні до складу базисних нової змінної.
Крок 3. Знаходиться нове базисне рішення, відповідне
нових складів небазисних і базисних змінних. Здійснюється перехід до кроку 1.
Пояснимо процедури симплекс-методу на прикладі рішення нашої зада-
