Смекни!
smekni.com

Розв'язок задачі лінійного програмування (стр. 1 из 4)

Задача 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), маємо: