Розв'язок задачі лінійного програмування

Графічний метод для визначення оптимального плану задачі лінійного програмування доцільно застосовувати лише для задач із двома змінними. За більшої кількості

Розвязок задачі лінійного програмування

Контрольная работа

Математика и статистика

Другие контрольные работы по предмету

Математика и статистика

Сдать работу со 100% гаранией

Задача 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) отримуємо, що для шуканого має виконуватися умова . Отже вектор буде планом задачі для будь-якого , що задовольняє умову

,

 

де мінімум знаходимо по тих i, для яких .

Опорний план не може містити більш ніж m додатних компонент, тому в плані необхідно перетворити в нуль хоча б одну з компонент. Припустимо, що

 

 

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

 

.

 

Підставимо значення у вираз:

 

,

 

якщо позначити

 

, ,

то рівняння можна подати у вигляді розкладу:

 

,

 

якому відповідає наступний опорний план:

 

.

 

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

Узагальнюючи розглянутий процес, маємо визначення нових опорних планів полягає у виборі вектора, який має ввійти в базис і вектора, що має вийти з базису. Така процедура відповідає переходу від одного базису до іншого за допомогою методу Жордана-Гауса.

Необхідно відмітити, що для випадку коли вектор підлягає включенню в базис, а в його розкладі всі , то, очевидно, не існує такого , який виключав би один з векторів розкладу (3.35). В такому випадку план містить m+1 додатних компонент, отже система векторів буде лінійно залежною і визначає не кутову точку багатогранника розвязків, а функціонал не може в ній досягати свого максимального значення. Це означає, що функціонал є необмеженим на багатограннику розвязків.

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

Теорема 1. Якщо для деякого вектора виконується умова , то план не є оптимальним і можливо побудувати такий план Х, для якого виконуватиметься нерівність .

Доведення. Помножимо (3.39) і (3.40) на і віднімемо результати відповідно з (3.37) та (3.38), отримаємо:

 

(*)

 

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

Похожие работы

1 2 >