Приклад задачі

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

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

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

Цільова функція: 30х₁+15х₂ ® max.

Нерівняння-обмеження:	Рівняння-обмеження:
3х₁+2х₂ £ 24,	3х₁+2х₂+х₃=24,	(1.3)
х₁ £ 6,	х₁+х₄=6,	(1.4)
х₂ £ 8,	х₂+х₅=8.	(1.5)
х₁ ³ 0, х₂ ³ 0.

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

Зазначимо, що коли б між обмеженнями задачі було нерівняння типу хi³а, то йому відповідало б рівняння хi - хj=a, де хj - додаткова змінна.

2. Вибираємо базисні змінні (базис) і рівняння-обмеження зводимо до канонічної (ступеневої) форми.

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

По-перше, у результаті розв’язання задачі потрібно, як правило, визначити основні змінні, що забезпечують оптимум цільової функції. Тому за інших рівних умов до базису включають, в першу чергу, основні змінні. Але, по-друге, далі необхідно рівняння-обмеження зводити до канонічної форми, яку також називають ступеневою формою. При такій формі рівнянь кожна базисна змінна присутня тільки в одному з них і з коефіцієнтом, рівним одиниці. Рівняння зводять до канонічної форми шляхом їх лінійних перетворень, тобто множенням (діленням) рівняння на певне число, відніманням одного рівняння від іншого (складанням двох рівнянь). Тому бажано вибрати такий базис, щоб процес зведення рівнянь-обмежень до канонічної форми потребував виконання якнайменшого обсягу обчислень. Більше того, при розв’язанні задач з використанням електронної обчислювальної машини іноді з цією метою вводять так званий штучний базис, тобто до рівнянь-обмежень включають додаткові змінні, кожна з яких напевно дорівнює нулю. Такий базис використовують з метою “запуску” машинної програми розв’язання задачі.

В задачі-прикладі, що наведена вище, вимогам до базисних змінних (наявність тільки в одному рівнянні з одиничним коефіцієнтом) відповідають змінні х3, х4, х5, які можна прийняти як перший базис. Але, з іншого боку, в задачі потрібно визначити змінні х1 і х2, що входять до цільової функції. Враховуючи сказане, базисними приймаємо змінні х1, х3, х5.

Тоді для зведення рівнянь до канонічної форми потрібно з (1.3) виключити змінну х1. З цією метою помножимо (1.4) на число 3 і одержане рівняння віднімемо від (1.3). В результаті маємо рівняння 2х2 + х3 - 3х4 = 6, яке у подальшому використовується як рівняння-обмеження замість (1.3). Тепер маємо систему рівнянь:

х₃+2х₂+3х₄=6, (1.6)

х₁+х₄=6, (1.7)

х₅+х₂=8 (1.8)

3. З метою отримання першого базисного розв’язку задачі в (1.6), (1.7), (1.8) прирівнюємо небазисні змінні х2, х4 нулю. При цьому, перший базисний розв’язок буде: х1=6, х3=6, х5=8.

4. Перевіряємо, чи є допустимим перший базисний розв’язок: у допустимому розв’язку значення змінних невід’ємні, це передбачено у формулюванні задачі.

У наведеному прикладі перший базисний розв’язок є допустимим.

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

5. Перевіряємо, чи не є перший базисний розв’язок оптимальним:

- для одержаних значень базисних змінних х1=6, х3=6, х5=8 обчислюємо значення цільової функції, яке дорівнює 180;

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

В прикладі, що розглядається, при х2=1 з (1.6) маємо х3=4, а згідно з (1.8) х5=7 (як і раніше, х4=0). При цьому цільова функція приймає значення: 30´6+15´1=195.

Аналогічна підстановка х4=1 дає значення цільової функції 150.

Порівнюючи значення цільової функції 195 і 150 з тим, яке забезпечується першим базисним розв’язком (180), приходимо до висновку, що до базису доцільно включити змінну х2, тому що тільки вона забезпечує бажану зміну значення цільової функції.

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

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

Змінну, яку належить виключити з базису, визначаємо з рівнянь (1.6), (1.7) і (1.8), керуючись наступним.

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

Підставивши в (1.6), (1.8) х2 і зрівнявши х3 і х5 з нулем (згідно з (1.7) х1 не залежить від х2), визначимо, що при х3=0 х2=3, а при х5=0 х2=8. Отже, до базису треба включити х2=3, а з базису виключити х3. Як наслідок, матимемо наступну систему рівнянь-обмежень з базисом х1, х2, х5:

х₃+2х₂=6, (1.9)

х₁+х₄=6, (1.10)

х₅+х₂=8 (1.11)

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

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

2 х₅ - х₃=10 або х₅ - 0,5 х₃=5

Тепер з базисом х1, х2, х5 маємо систему рівнянь-обмежень (перше з них одержане діленням (1.9) на 2):

х₂ - 0,5х₃=3, (1.12)

х₁+х₄=6, (1.13)

х₅ - 0,5 х₃=5 (1.14)

Зрівнявши небазисні змінні х3, х4 з нулем, одержуємо другий базисний розв’язок задачі: х1=6, х2 =3 , х5=5. При цьому значення цільової функції дорівнює 225.

З усіх змінних задачі нами не включалась до базису тільки змінна х4, тому перевіряємо доцільність її включення до базису. З цією метою підставляємо х4=1 в (1.13) і визначаємо нове значення х1=5, тоді як залишаються х2=3, х5=5, тому що, як і раніше, х3=0. При цьому цільова функція дорівнює 195, тобто її значення зменшилось порівняно з тим, яке відповідає другому базисному розв’язку задачі. Отже, розв’язок х1=6, х2=3, х3=0, х4=0, х5=5 є оптимальним, а йому відповідає значення цільової функції 225. Таким чином, для перевезення всього вантажу і одержання при цьому максимального прибутку належить використати шість суден першого і три судна другого типів.

На закінчення відзначимо, що хоч симплекс-методом можна розв’язати будь-яку задачу лінійного програмування з обмеженою кількістю змінних, існують також табличні методи розв’язання таких задач, наприклад, так звані методи північно-західного кута, угорський та ін. Крім того, створено табличний симплекс-метод, адаптований для розв’язання задач лінійного програмування з використанням ЕОМ.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Основні положення, на яких базується симплекс-метод розв’язання задач лінійного програмування	\|	Основні відомості про способи розв’язання задач нелінійного програмування

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.007 сек.