Розв'язок задачі лінійного програмування (стр. 1 из 4)
Розв’язати графічно задачу лінійного програмування
Розв’язання:
Розглянемо на площині х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):
Отже, розв’язок є точка
, причому 
.Розв’язати симплекс методом:
Розв’язання:
Графічний метод для визначення оптимального плану задачі лінійного програмування доцільно застосовувати лише для задач із двома змінними. За більшої кількості необхідно застосовувати загальний метод розв’язування задач лінійного програмування. З властивостей розв’язків задачі лінійного програмування відомо: оптимальний розв’язок задачі має знаходитись в одній з кутових точок багатогранника допустимих розв’язків. Тому найпростіший спосіб відшукання оптимального плану потребує перебору всіх кутових точок (можливих допустимих планів задачі). Кожний опорний план визначається системою m лінійно незалежних векторів, які містяться в системі обмежень задачі з n векторів
, отже загальна кількість опорних планів визначається кількістю комбінацій 
.Задачі, що описують реальні економічні процеси мають значну розмірність і простий перебір всіх можливих опорних планів таких задач є дуже складним, навіть за умови застосування сучасних ЕОМ. Отже необхідне використання методу, який дає можливість скоротити кількість обчислень. Такий метод запропоновано американським вченим Дж. Данцігом у 1949 році – так званий симплекс-метод.
Ідея методу полягає в здійсненні направленого перебору допустимих планів, таким чином, що на кожному кроці здійснюється перехід від одного опорного плану до наступного, який є хоча б не гіршим за попередній. Значення функціоналу при переході змінюється в потрібному напрямку: збільшується (для задачі на максимум) чи зменшується (для задачі на мінімум).
Процес розв’язування задачі симплекс-методом має ітераційний характер: однотипові обчислювальні процедури (ітерації) повторюються у певній послідовності доти, доки не буде отримано оптимальний план задачі або з’ясовано, що його не існує.
Отже, симплекс-метод — це поетапна обчислювальна процедура, яка дозволяє починаючи з відомого опорного плану за скінчену кількість кроків отримати оптимальний план задачі лінійного програмування.
Розглянемо задачу лінійного програмування подану в канонічній формі:
Не втрачаючи загальності припустимо, що система містить перші m одиничних векторів:
(1) (2) (3)Система (1) у векторній формі матиме вигляд:
(4)де
, 
,..., 
, 
, 
,..., 
, 
– лінійно незалежні одиничні вектори m-вимірного простору, що утворюють одиничну матрицю і складають базис цього простору. Тому в розкладі (4) базисними змінними будуть 
, інші – вільні змінні. Покладемо всі вільні змінні рівними нулю 
. Оскільки 
, а вектори – одиничні, отримаємо один із розв’язків системи (4), тобто допустимий план. 
(5)Такому плану відповідає розклад
(6)де
– лінійно незалежні і за властивістю 3 розв’язків задачі лінійного програмування план 
є кутовою точкою багатогранника розв’язків, а отже може бути початковим опорним планом.Розглянемо, як виходячи з початкового опорного плану (5) перейти до наступного опорного плану, що відповідає процесу перебору кутових точок багатогранника розв’язків.
Оскільки
є базисом m-вимірного простору, то кожен з векторів співвідношення (5) може бути розкладений за векторами базису причому єдиним чином: 
Розглянемо такий розклад для довільного не базисного вектора, наприклад, для
: 
(7)Припустимо, що у виразі (7) існує хоча б один додатній коефіцієнт
.Введемо до розгляду деяку поки що невідому величину
, помножимо на неї обидві частини рівності (3.34) і віднімемо результат з рівності (3.33), маємо: