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

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

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

Ідея симплексного методу ґрунтується на використанні властивос­тей багатокутника, що обмежує ОДР. Ця область має свої особливості, а саме:

вона обмежена прямими, бо функції обмежень є лінійними;

у точках перетину прямих хоча б дві змінні набувають нульового значення, а це означає, що оптимальні розв’язки лежать у вершинах багатокутника, що суттєво спрощує пошук оптимальних значень функ­ції мети, обмежених ОДР. Така вершина багатокутника називається опор­ною точкою, а розв’язок задачі в ній — опорним розв’язком.

Симплексний метод — це багатокроковий метод розв’язання задач математичного програмування, при якому на кожному кроці здійсню­ється перехід до сусідньої вершини багатокутника ОДР. Для розв’язан­ня задачі необхідно виконати декілька послідовних кроків. Розв’язання задачі на кожному кроці називається опорним, або базисним. На цьому кроці визначається функція мети і створюється базис для наступного опорного розв’язку. Змінні величини, які при даному базисному розв’яз­ку отримують нульові значення, називаються нульовими, або небазисними змінними, всі решта — базисні, або ненульові змінні.

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

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

Методику розв’язання задачі розглянемо на конкретному прикладі. Нехай необхідно знайти максимальне значення функції мети

за наявності таких обмежень,

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

при обмеженнях

Симплексний метод включатиме такі кроки:

Використовуючи лінійну модель оптимізаційної задачі в стандарт­ній формі, визначають початковий базисний розв’язок шляхом прирів­нювання до нуля небазисних змінних.

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

Серед базисних змінних вибирається та, яка повинна дорівнюва­ти нулеві, тобто стати небазисною при введенні до складу базисних нової змінної.

Знаходять новий базисний розв’язок. Переходять до п.2.

Для здійснення цих кроків розв’язання використовується симплекс - таблиця, яка містить запис лінійної оптимізаційної моделі в стандарт­ній формі у вигляді прямокутної таблиці.

Для знаходження початкового опорного розв’язку прирівняємо до нуля дві змінні функції мети, тобто X1 = X2 = 0, що дає такий розв’язок оптимізаційної задачі:

Значення функції мети в цій точці дорівнює нулю, тобто Y=0, оскільки X1 =X2 = 0. Перетворивши рівняння функції мети до стандартно­го вигляду

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

Ця таблиця описує початковий опорний розв’язок. Стовпчик “базисні змінні” містить змінні початкового базису, що не дорівнюють нулю, тобто   Дві небазисні змінні дорівнюють нулю, тобто х1 = х2 = 0. Значення функції мети також дорівнює нулю Y= 0.

Виберемо напрям переходу до наступного опорного розв’язку, який дасть змогу підвищити значення функції мети. Оскільки ми маємо справу із задачею максимізації, то аналіз рівняння функції мети показує, що значення Y може бути поліпшене при збільшенні х1 або х2, які при по­чатковому розв’язку були прийняті рівними нулеві. Для швидшого до­сягнення оптимуму вибирається змінна, яка має більше за абсолютною величиною значення коефіцієнта в рівнянні функції мети Y. У нашому прикладі такою змінною є х1. Замість неї одна з базисних змінних повин­на прирівнятися до нуля, тобто перейти в розряд небазисних змінних. Нею буде та із базисних змінних, яка першою перетвориться на нуль при зростанні вибраної нової базисної змінної, тобто при зростанні х1. Ця змінна характеризуватиметься найменшим відношенням правої ча­стини обмеження до відповідного додатного коефіцієнта нової базисної змінної.

Для зручності опису переходу до нового опорного розв’язку викори­стаємо табл. 4.1. Стовпчик симплекс-таблиці, що відповідає новій бази­сній змінній, назвемо ключовим. Рядок, що відповідає новій небазисній змінній, назвемо ключовим рядком, а елемент таблиці на їх перетині — генеруючим елементом.

Таким чином, у табл. 4.1 за найбільшим коефіцієнтом у рядку функ­ції мети вибираємо ключовий стовпчик, що відповідає новій базисній змінній — х1. Для знаходження ключового рядка розглядаємо тільки рядки обмежень із додатним коефіцієнтом при x1 (якщо коефіцієнт при х1 має від’ємне або нульове значення, то пряма, що описує відповідне обмеження, не перетинається з віссю х1 в області позитивних значень, тобто не утворює точку перетину, що утворює багатокутник ОДР). Тоді в ключовому стовпчику симплекс-таблиці можна викреслити від’ємні або нульові коефіцієнти при х1. Далі обчислюються відношення постій­них величин правих частин решти обмежень до додатних елементів клю­чового стовпчика х1. Ключовим рядком буде той, де значення цього від­ношення буде мінімальним. Цей ключовий рядок і визначить нову змін­ну, яка переведеться в розряд небазисної —z1  (табл. 4.2).

Після визначення нової базисної змінної х1 та нової небазисної змін­ної z1 знаходять новий опорний розв’язок, який відповідатиме розв’яз­ку оптимізаційної задачі в другій, найближчій до початкової, точці ба­гатокутника ОДР. Новий опорний розв’язок знаходять перетворенням симплексної таблиці методом Гаусса-Жордана. Алгоритм включає два етапи, за результатами яких отримують нову симплекс-таблицю (табл. 4.3).

 

Етап 1. Знаходимо новий ключовий рядок як результат ділення по­переднього ключового рядка на генеруючий елемент.

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

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

Нова симплекс-таблиця отримана при переході до нового опорного розв’язку (табл. 4.3).

Як бачимо, в точці 2 (х1 = 5; х2 = 0) значення функції мети зросло від 0 до 25. Це зумовлено тим, що зростання x1 на одиницю забезпечує зростання Y на 5 одиниць. Тому приріст функції мети становить:

Нова симплекс-таблиця має такі самі властивості, як попередня, тому перетворимо її аналогічно. Новою базисною змінною оберемо х2, оскі­льки коефіцієнт при ній у функції мети дорівнює -2/3. Ця нова базисна змінна визначить ключовий стовпчик. Ключовий рядок і нова небазисна змінна визначаться мінімальним відношенням — 6/5, z2.

Здійснимо перетворення Гаусса-Жордана і перейдемо до наступної симплекс-таблиці (табл. 4.4).

У новому розв’язку, в третій точці ОДР, значення функції мети зрос­ло від 25 до 25 + 4/5. Цей приріст є результатом зростання х2 від 0 до 6/5, унаслідок чого зростає функція мети

Остання симплекс-таблиця відповідає оптимальному розв’язку, оскі­льки в функції мети всі небазисні змінні мають невід’ємні коефіцієнти.

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

Правило 1. У задачі максимізації (мінімізації) новою базисною змін­ною обирається та з небазисних змінних, яка в рівнянні функції мети має найбільший від’ємний (додатний) коефіцієнт.

Правило 2. Коли всі коефіцієнти при небазисних змінних у рівнянні функції мети будуть додатними (при максимізації) або від’ємними (при мінімізації), то знайдений розв’язок буде оптимальним і подальше пе­ретворення симплекс-таблиці методом Гаусса-Жордана припиняється.

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