Навігація
Главная
Авторизация/Регистрация
 
Головна arrow Природознавство arrow ПРИКЛАДНА МАТЕМАТИКА: ТЕХНОЛОГІЇ ЗАСТОСУВАННЯ
Переглянути оригінал

СИМПЛЕКС-МЕТОД ВИРІШЕННЯ ОСНОВНОГО ЗАВДАННЯ ЛІНІЙНОГО ПРОГРАМУВАННЯ

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

Послідовність основних етапів симплекс-методу наступна:

  • 1) відшукується одна з вершин багатогранника, що задовольняє умовам типу (14.6). Зауважимо, що при цьому не всі умови (14.7) можуть бути виконані;
  • 2) послідовними переходами в так звані сусідні вершини знаходять вершину, що належить ОДР, тобто забезпечується виконання і всіх умов (14.7). Це означає, що отримано опорний (допустимий) рішення;
  • 3) якщо допустиме рішення не є оптимальним, то, продовжуючи послідовний перехід в сусідні вершини і весь час перебуваючи в ОДР, знаходять вершину, що задовольняє умові (14.1), якій відповідає шукане рішення задачі.

Ефективним механізмом реалізації всіх перерахованих етапів є формалізована схема, на кожному кроці якої проводиться заміна однієї вільної змінної на одну базисну. Ця схема отримала назву схема модифікованих Жорданових винятків.

Розглянемо механізм реалізації кожного з перерахованих етапів. Почнемо з відшукання однієї з вершин багатогранника, що задовольняє умовам (14.6). Система обмежень (14.6) являє собою систему т лінійних алгебраїчних рівнянь з п невідомими, яких більше, ніж число рівнянь. Отже, вирішуючи систему, можна визначити рівно т (будь-яких!) Невідомих, які будуть виражені через інші (п - т) невідомих. Тим самим проводиться поділ змінних на вільні та базисні. Ця операція реалізується за т кроків Жорданових винятків. Потім переходять до знаходження опорного плану.

Алгоритм знаходження опорного плану. Нехай проведено до кроків модифікованих Жорданових винятків і результат записаний у вигляді табл. 14.1.

Таблиця 14.1

Результат Жорданових винятків

-

- * 1

~ X 2

~ X r

~ X k

P

х до + 1

«fcri.1

a fc + l, 2

a Jfc + l, r

a k +, k

P,

х до +: 2

a k + 2, l

a k + 2,2

a k + 2, r

a k + 2, k

P 2

x s

a sl

a s2

a sr

a sk

Pp

х п

«" 1

«" 2

a nr

a nk

P ",

L

Yi

Y 2

Y r

Y до

Yo

Нагадаємо: опорне рішення лежить завжди в одній з вершин області припустимих рішень і містить не менше до нульових компонентів. Таким чином, поклавши всі змінні, розташовані у верхній точці таблиці (вільні змінні), нулю, завжди можна опинитися в кутовій точці, тобто X = (0, 0, О, (З х , (3 2 , ..., Р т ). Тому якщо в табл. 14.1 все (3, невід'ємні, то маємо допустиме рішення X * = (0, ... , 0 , x ^ +1, jc ^ +2, ..., x ") і можна переходити до другого етапу розв'язання задачі - поліпшення опорного плану.

Якщо ж існує хоча б один негативний вільний член, наприклад Р р <0, то рішення, відповідне табл. 14.1, неприпустимо. При цьому можливі дві ситуації.

  • 1. У 5-му рядку табл. 14.1 все коефіцієнти a s j> 0. Вільні змінні, що задовольняють умові (14.7), можна тільки збільшувати, так як обраний нами їх початковий стан нульове. Оскільки в модифікованих Жорданових винятки вони стоять зі знаком «мінус» і все a s; > 0, то їх твір непозитивним і ніяке збільшення значень вільних змінних не може компенсувати отріцательності (L. Це означає, що відповідна базова змінна x s ніколи не може бути зроблена неотрицательной. Отже, допустимий план не може бути отриманий. Робимо висновок, що система обмежень в ОЗЛП несовместна і завдання не має рішення (кінець рішення задачі).
  • 2. В s-му рядку табл. 14.1 існує хоча б один негативний коефіцієнт a sr < 0. Тоді член x s може бути зроблений позитивним за рахунок збільшення вільної змінної х,., Щоб компенсувати неотрицательность (З р . Проте збільшення х г позначиться на обчисленні значень всіх базових змінних. Якщо в r-м стовпці є позитивні a jr , то при поступовому збільшенні х, одна з базових змінних звернеться в нуль першої. Яка? Та, для якої виконується співвідношення

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

Алгоритм поліпшення опорного плану (власне оптимізації). Нехай отримано допустиме рішення, тобто Vp Р р > 0. Розглянемо рядок коефіцієнтів цільової функції. Якщо все у г > 0, то опорне рішення є оптимальним. Дійсно, збільшення будь-якої вільної змінної може лише зменшити значення L. Значить, при нульових значеннях вільних змінних L найбільше. Завдання вирішена.

Якщо ж існує у г <0, то збільшення відповідної вільної змінної х г збільшує значення цільової функції, так як у гг )> 0. Розглянемо можливі при цьому дві ситуації.

  • 1. Всі коефіцієнти в стовпці г непозитивні (звичайно, крім рядка L). Це означає, що безмежне збільшення вільної змінної х п збільшуючи L, не звертає базисні змінні в негативні числа і є допустимим. У цьому випадку говорять, що завдання (14.1), (14.6), (14.7) не має кінцевого рішення.
  • 2. Існує якийсь a sr > 0. Тоді збільшення х г може привести до появи негативної базової змінної. Першою звернеться в нуль та базова змінна, для якої виконується умова (14.11). Саме це співвідношення і визначає базову змінну х *, яку необхідно обміняти на вільну х г . Покажемо, що значення цільової функції при цьому не зменшиться (може зрости або залишиться незмінним).

Дійсно, відповідно до алгоритму проведення Жорданових винятків нове значення у 0 (саме йому дорівнює L при нульових значеннях всіх вільних змінних) обчислюється за формулою

тобто нове значення цільової функції не менше, ніж раніше.

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

приклад 14.4

Знайти максимум функції при обмеженнях

Рішення. Запишемо задачу у вигляді жорданової таблиці:

-

~ Х 1

- * 2

- * з

- * 4

- * 5

1

0

-1

4

-2

1

0

6

0

1

1

2

0

-1

6

0

2

-1

2

0

0

4

L

-1

-2

1

0

0

0

Для поділу невідомих на вільні та базисні послідовно проведемо три кроки модифікованих Жорданових винятків.

Після першого кроку маємо

-

- * i

- * 2

- * з

0

- * 5

1

* 4

-1

4

-2

1

0

6

0

1

1

2

0

-1

6

0

2

-1

2

0

0

4

L

-1

-2

1

0

0

0

Після другого кроку отримуємо наступну таблицю:

-

- * 2

- * 3

- * 5

1

* 4

5

0

-1

12

* 1

1

2

-1

6

-

- * 2

- * 3

- * 5

1

0

-3

-2

2

-8

L

-1

3

-1

6

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

-

"* 2

- * з

1

х 4

7/2

-1

8

* 1

-1/2

1

2

* 5

-3/2

-1

-4

L

-5/2

2

2

Рішення Х = (2,0,0, 8, -4), що отримується безпосередньо з останньої таблиці, не є допустимим, оскільки одна змінна має від'ємне значення (х 5 = -4).

Проведемо ще один крок Жорданових винятків. Використовуючи правило (14.11), замінимо х : нах 3 . отримаємо

-

х 2

- * 1

1

х 4

3

1

0

* 3

-1/2

1

2

* 5

-2

1

-2

L

-3/2

-2

-2

Отримане рішення (2, 0, -2, 0, 0) також неприпустимо, так як х 3 = -2. Проведемо відповідно до правил алгоритму ще один крок модифікованих Жорданових винятків, замінивши тепер х 5 нах 2 :

-

~ Х 5

- * i

1

х 4

3/2

5/2

7

* 3

-1/4

3/4

5/2

х 2

-1/2

-1/2

1

L

-3/4

-11/4

-1/2

Отримане рішення (0,1, 5/2, 7, 0) допустимо, але не оптимально, так як коефіцієнти цільової функції негативні. Зробивши заміну х 4 на х 1; отримаємо

-

~ Х ь

х 4

1

* 1

3/5

2/5

14/5

* 3

-7/10

-3/10

2/5

х 2

-1/5

1/5

12/5

L

9/10

11/10

72/10

Тепер рішення X * = (xj = 14/5, х * 2 = 2/5, Хз = 2/5) оптимально, при цьому найбільше значення цільової функції V = 7,2. Змінні х 4 і х 5 не входять до відповідь завдання, оскільки були введені в процесі рішення як додаткові.

 
Переглянути оригінал
< Попередня   ЗМІСТ   Наступна >
 
Дисципліни
Агропромисловість
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Нерухомість
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Природознавство
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Техніка
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук