Xreferat.com » Рефераты по математике » Розв'язок задачі лінійного програмування

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

Задача 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 0 12 3 **
x5 -1 2 0 0 1 0 4 –
x6 1 -1 0 0 0 1 4 4
F -1 -1 0 0 0 0 0 0
Mf -4 -3 1 0 0 0 -12 0

**









1 1 0 -M 0 0



x1 x2 x3 x4 x5 x6 B T
x1 1 0,75 -0,25 0,25 0 0 3 4
x5 0 2,75 -0,25 0,25 1 0 7 2,545 **
x6 0 -1,75 0,25 -0,25 0 1 1 –
F 0 -0,25 -0,25 0,25 0 0 3 0
Mf 0 0 0 1 0 0 0 0


**








1 1 0 -M 0 0



x1 x2 x3 x4 x5 x6 B T
x1 1 0 -0,1818 0,1818 -0,2727 0 1,091 –
x2 0 1 -0,09091 0,09091 0,3636 0 2,545 –
x6 0 0 0,09091 -0,09091 0,6364 1 5,455 60 **
F 0 0 -0,2727 0,2727 0,09091 0 3,636 0
Mf 0 0 0 1 0 0 0 0



**







1 1 0 -M 0 0


x1 x2 x3 x4 x5 x6 B T
x1 1 0 0 0 1 2 12 –
x2 0 1 0 0 1 1 8 –
x3 0 0 1 -1 7 11 60 60
F 0 0 0 0 2 3 20 0
Mf 0 0 0 1 0 0 0 0

Отже, х* = (12, 8, 60), L(x*)max = 20.


Задача 3


Для задачі побудувати двоїсту, розв’язати і за розв’язком знайти розв’язок двоїстої:


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


Розв’язання:

Кожна задача лінійного програмування пов’язана з іншою, так званою двоїстою задачею.

Економічну інтерпретацію кожної з пари задач розглянемо на прикладі виробничої задачі.

Початкова задача:

max z = c1x1 + c2x2 + … + cnxn


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


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


Визначити, яку кількість продукції Розв'язок задачі лінійного програмування кожного j-го виду Розв'язок задачі лінійного програмування необхідно виготовляти в процесі виробництва, щоб максимізувати загальну виручку від реалізації продукції підприємства. Причому відомі: загальна кількість ресурсів – Розв'язок задачі лінійного програмування, нормативи використання кожного і-го виду ресурсу на кожен j-ий вид продукції – Розв'язок задачі лінійного програмування, а також Розв'язок задачі лінійного програмування – ціна реалізації одиниці продукції.

Розглянемо тепер ту саму задачу з іншої точки зору. Припустимо, що за певних умов доцільно продавати деяку частину чи всі наявні в господарстві ресурси. Необхідно визначити цінність ресурсів. Кожному ресурсу Розв'язок задачі лінійного програмування поставимо у відповідність його оцінку Розв'язок задачі лінійного програмування. Умовно вважатимемо, що Розв'язок задачі лінійного програмування – ціна одиниці і-го ресурсу.

На виготовлення одиниці j-го виду продукції Розв'язок задачі лінійного програмування витрачається згідно моделі всі m видів ресурсів у кількості відповідно Розв'язок задачі лінійного програмування. Оскільки ціни одиниці кожного виду ресурсів за припущенням дорівнюють Розв'язок задачі лінійного програмування, то загальна вартість ресурсів, що витрачені на виробництво одиниці j-го виду продукції обчислюється як


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


Продавати ресурси доцільно лише за умови, що кошти отримані в результаті продажу ресурсів будуть дорівнювати або

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: