Задача 1
Розв’язати графічно задачу лінійного програмування
Розв’язання:
Розглянемо на площині х1Оx2 сумісну систему лінійних нерівностей
(1)
Кожна нерівність цієї системи геометрично визначає півплощину з граничною прямою (i = 1, 2,...,т). Умови невід’ємності визначають півплощини відповідно з граничними прямими . Система сумісна, тому півплощини, як опуклі множини, перетинаючись, утворюють спільну частину, що є опуклою множиною і являє собою сукупність точок, координати кожній із який є розв’язком даної системи (рис. 1.).
Рис. 1.
Сукупність цих точок (розв’язків) називають багатокутником розв’язків Він може бути точкою, відрізком, променем, багатокутником, необмеженою багатокутною областю.
Якщо в системі обмежень (1) п = 3, то кожна нерівність геометрично представляє півпростір тривимірного простору, гранична площина котрого (i = 1, 2,...,т), а умови невід’ємності – півпростори з граничними площинами відповідно хі = 0 (і = 1,2,3). Якщо система обмежень сумісна, то ці півпростори, як опуклі множини, перетинаючись, утворять у тривимірному просторі спільну частину, що називається багатогранником розв’язків. Багатогранник розв’язків може бути точкою, відрізком, променем, багатокутником, багатогранником, багатогранною необмеженою областю.
Нехай у системі обмежень (1) п > 3; тоді кожна нерівність визначає півпростір n-вимірного простору з граничною гіперплощиною (i = 1, 2,...,т),. Кожному обмеженню виду (3.7) відповідають гіперплощина та напівпростір, який лежить по один бік цієї гіперплощини, а умови невід’ємності – півпростори з граничними гіперплощинами хі = 0 (і = 1,2,3,...,n).
Якщо система обмежень сумісна, то по аналогії з тривимірним простором вона утворює спільну частину в n-вимірному просторі – опуклий багатогранник допустимих розв’язків.
Таким чином, геометрично задача лінійного програмування являє собою відшукання такої точки багатогранника розв’язків, координати, якої надають лінійній функції максимальне (мінімальне) значення, причому допустимими розв’язками є усі точки багатогранника розв’язків.
Цільову функцію в п-вимірному просторі основних змінних можна геометрично інтерпретувати як сім’ю паралельних гіперплощин, положення кожної з яких визначається значенням параметра Z.
Запишемо систему нерівностей у вигляді:
Розв’яжемо задачу графічно.
Побудуємо систему обмежень (1), (2), (3).
Побудуємо також лінії рівня: х1 + х2 = С. С = const.
Розв’язок на перетині Ох2 та (3):
Отже, розв’язок є точка , причому .
Задача 2
Розв’язати симплекс методом:
Розв’язання:
Графічний метод для визначення оптимального плану задачі лінійного програмування доцільно застосовувати лише для задач із двома змінними. За більшої кількості необхідно застосовувати загальний метод розв’язування задач лінійного програмування. З властивостей розв’язків задачі лінійного програмування відомо: оптимальний розв’язок задачі має знаходитись в одній з кутових точок багатогранника допустимих розв’язків. Тому найпростіший спосіб відшукання оптимального плану потребує перебору всіх кутових точок (можливих допустимих планів задачі). Кожний опорний план визначається системою m лінійно незалежних векторів, які містяться в системі обмежень задачі з n векторів , отже загальна кількість опорних планів визначається кількістю комбінацій
.
Задачі, що описують реальні економічні процеси мають значну розмірність і простий перебір всіх можливих опорних планів таких задач є дуже складним, навіть за умови застосування сучасних ЕОМ. Отже необхідне використання методу, який дає можливість скоротити кількість обчислень. Такий метод запропоновано американським вченим Дж. Данцігом у 1949 році – так званий симплекс-метод.
Ідея методу полягає в здійсненні направленого перебору допустимих планів, таким чином, що на кожному кроці здійснюється перехід від одного опорного плану до наступного, який є хоча б не гіршим за попередній. Значення функціоналу при переході змінюється в потрібному напрямку: збільшується (для задачі на максимум) чи зменшується (для задачі на мінімум).
Процес розв’язування задачі симплекс-методом має ітераційний характер: однотипові обчислювальні процедури (ітерації) повторюються у певній послідовності доти, доки не буде отримано оптимальний план задачі або з’ясовано, що його не існує.
Отже, симплекс-метод — це поетапна обчислювальна процедура, яка дозволяє починаючи з відомого опорного плану за скінчену кількість кроків отримати оптимальний план задачі лінійного програмування.
Розглянемо задачу лінійного програмування подану в канонічній формі:
Не втрачаючи загальності припустимо, що система містить перші m одиничних векторів:
(1)
(2)
(3)
Система (1) у векторній формі матиме вигляд:
(4)
де
, ,..., ,
, ,..., ,
– лінійно незалежні одиничні вектори m-вимірного простору, що утворюють одиничну матрицю і складають базис цього простору. Тому в розкладі (4) базисними змінними будуть , інші – вільні змінні. Покладемо всі вільні змінні рівними нулю . Оскільки , а вектори – одиничні, отримаємо один із розв’язків системи (4), тобто допустимий план.
(5)
Такому плану відповідає розклад
(6)
де – лінійно незалежні і за властивістю 3 розв’язків задачі лінійного програмування план є кутовою точкою багатогранника розв’язків, а отже може бути початковим опорним планом.
Розглянемо, як виходячи з початкового опорного плану (5) перейти до наступного опорного плану, що відповідає процесу перебору кутових точок багатогранника розв’язків.
Оскільки є базисом m-вимірного простору, то кожен з векторів співвідношення (5) може бути розкладений за векторами базису причому єдиним чином:
Розглянемо такий розклад для довільного не базисного вектора, наприклад, для :
(7)
Припустимо, що у виразі (7) існує хоча б один додатній коефіцієнт .
Введемо до розгляду деяку поки що невідому величину , помножимо на неї обидві частини рівності (3.34) і віднімемо результат з рівності (3.33), маємо:
(8)
Таким чином вектор
є планом у тому випадку, коли його компоненти невід’ємні. За припущенням , отже ті компоненти вектора в які входять будуть невід’ємними, тому необхідно розглядати лише ті компоненти, які містять додатні . Отже необхідно знайти таке значення , при якому для всіх буде виконуватися умова невід’ємності плану задачі:
(9)
З (3.36) отримуємо, що для шуканого має виконуватися умова . Отже вектор буде планом задачі для будь-якого q, що задовольняє умову
,
де мінімум знаходимо по тих i, для яких .
Опорний план не може містити більш ніж m додатних компонент, тому в плані необхідно перетворити в нуль хоча б одну з компонент. Припустимо, що
для деякого значення і, тоді відповідна компонента плану перетвориться в нуль. Нехай це буде перша компонента плану, тобто
.
Підставимо значення у вираз:
,
якщо позначити
, ,
то рівняння можна подати у вигляді розкладу:
,
якому відповідає наступний опорний план:
.
Для визначення наступного плану необхідно аналогічно продовжити процес: будь-який вектор, що не входить в базис розкласти за базисними векторами, а потім визначити таке , для якого один з векторів виключається з базису.
Узагальнюючи розглянутий процес, маємо – визначення нових опорних планів полягає у виборі вектора, який має ввійти в базис і вектора, що має вийти з базису. Така процедура відповідає переходу від одного базису до іншого за допомогою методу Жордана-Гауса.
Необхідно відмітити, що для випадку коли вектор підлягає включенню в базис, а в його розкладі всі , то, очевидно, не існує такого , який виключав би один з векторів розкладу (3.35). В такому випадку план містить m+1 додатних компонент, отже система векторів буде лінійно залежною і визначає не кутову точку багатогранника розв’язків, а функціонал не може в ній досягати свого максимального значення. Це означає, що функціонал є необмеженим на багатограннику розв’язків.
Симплексний метод здійснює направлений перебір опорних планів, що дозволяє переходити від одного плану до іншого, який є хоча б не гіршим від попереднього за значенням, що він надає функціоналу. Отже окремим питанням постає вибір вектору, який необхідно вводити в базис при здійсненні ітераційної процедури симплексного методу.
Теорема 1. Якщо для деякого вектора виконується умова , то план не є оптимальним і можливо побудувати такий план Х, для якого виконуватиметься нерівність .
Доведення. Помножимо (3.39) і (3.40) на і віднімемо результати відповідно з (3.37) та (3.38), отримаємо:
(*)
У співвідношенні до обох частин додається величина для , додатні, тому завжди можливо знайти таке , що всі коефіцієнти при векторах були невід’ємними, іншими словами отримати новий план задачі виду:
,
якому згідно відповідає значення функціоналу
Так як за умовою теореми
і , то .
Що і потрібно було довести.
Теорема 2. Якщо для деякого вектора виконується умова , то план не є оптимальним і можливо побудувати такий план Х, для якого виконуватиметься нерівність .
Запишемо канонічну задачу:
Розв’яжемо симплекс-методом:
| 1 | 1 | 0 | -M | 0 | 0 |
|
| |
| x1 | x2 | x3 | x4 | x5 | x6 | B | T | |
x4 | 4 | 3 | -1 | 1 | 0 |