|
Графічний метод розв’язування задач лінійного програмування
Для розв’язування двовимірних задач лінійного програмування, тобто задач із двома змінними, а також деяких тривимірних задач застосовують графічний метод, що ґрунтується на геометричній інтерпретації та аналітичних властивостях задач лінійного програмування. Обмежене використання графічного методу зумовлене складністю побудови багатогранника розв’язків у тривимірному просторі (для задач з трьома змінними), а графічне зображення задачі з кількістю змінних більше трьох взагалі неможливе. Розглянемо задачу. Знайти (1.1) за умов: (1.2) . (1.3) Припустимо, що система(1.1) за умов (1.2) сумісна і багатокутник її розв’язків обмежений. Згідно з геометричною інтерпретацією задачі лінійного програмування (п.3.3) кожне і -те обмеження-нерівність у (1.2) визначає півплощину з граничною прямою (і = 1, 2, …, т). Системою обмежень (1.2) графічно можна зобразити спільну частину, або переріз усіх зазначених півплощин, тобто множину точок, координати яких задовольняють всі обмеження задачі – багатокутник розв’язків. Умова (1.3) невід’ємності змінних означає, що область допустимих розв’язків задачі належить першому квадранту системи координат двовимірного простору. Цільова функція задачі лінійного програмування геометрично інтерпретується як сім’я паралельних прямих с 1 х 1+ с 2 х 2 = const. Скористаємося для графічного розв’язання задачі лінійного програмування властивостями,:якщо задача лінійного програмування має оптимальний план, то екстремального значення цільова функція набуває в одній із вершин її багатокутника розв’язків. Якщо ж цільова функція досягає екстремального значення більш як в одній вершині багатокутника, то вона досягає його і в будь-якій точці, що є лінійною комбінацією цих вершин. Отже, розв’язати задачу лінійного програмування графічно означає знайти таку вершину багатокутника розв’язків, у результаті підстановки координат якої в (1.1) лінійна цільова функція набуває найбільшого (найменшого) значення. Алгоритм графічного методу розв’язування задачі лінійного програмування складається з таких кроків: 1.Будуємо прямі, рівняння яких дістаємо заміною в обмеженнях задачі (1.2) знаків нерівностей на знаки рівностей. 2.Визначаємо півплощини, що відповідають кожному обмеженню задачі. 3.Знаходимо багатокутник розв’язків задачі лінійного програмування. 4.Будуємо вектор , що задає напрям зростання значення цільової функції задачі. 5.Будуємо пряму с 1 х 1+ с 2 х 2=const, перпендикулярну до вектора . 6.Рухаючи пряму с 1 х 1+ с 2 х 2=const в напрямку вектора 7. Визначаємо координати точки, в якій цільова функція набирає максимального (мінімального) значення, і обчислюємо екстремальне значення цільової функції в цій точці. У разі застосування графічного методу для розв’язування задач лінійного програмування можливі такі випадки: 1. Цільова функція набирає максимального значення в єдиній вершині А багатокутника розв’язків (рис.3.3). 2. Максимального значення цільова функція досягає в будь-якій точці відрізка АВ (рис.3.4). Тоді задача лінійного програмування має альтернативні оптимальні плани. 3. Задача лінійного програмування не має оптимальних планів: якщо цільова функція необмежена згори (рис.3.5) або система обмежень задачі несумісна (рисунок 3.6). Рисунок3.3 Рисунок3.4 Рисунок3.5 Рисунок3.6 4. Задача лінійного програмування має оптимальний план за необмеженої області допустимих розв’язків (рис.3.7 і 3.8). На рис.3.7 у точці В маємо максимум, на рис.3.8 у точці А – мінімум, на рис.3.9 зображено, як у разі необмеженої області допустимих планів цільова функція може набирати максимального чи мінімального значення у будь-якій точці променя. Рисунок3.7 Рисунок3.8 Рисунок3.9 Розв’язувати графічним методом можна також задачі лінійного програмування n -вимірного простору, де , якщо при зведенні системи нерівностей задачі до системи рівнянь шляхом введення додаткових змінних кількість змінних n на дві більша, ніж число обмежень m, тобто . Тоді, як відомо з курсу вищої математики, можна дві з n змінних, наприклад х 1 та х 2, вибрати як вільні, а інші m зробити базисними і виразити через вільні. Припустимо, що це зроблено. Отримаємо рівнянь вигляду: Оскільки всі значення , то мають виконуватись умови: , (1.4) Розглянемо, як можна зобразити ці умови геометрично. Візьмемо, наприклад, першу з них: Узявши величину х 3 рівною своєму крайньому значенню — нулю, отримаємо рівняння: . Це рівняння прямої. Для такої прямої , по одну сторону від неї , а по другу – . Відмітимо ту сторону прямої , де . В аналогічний спосіб побудуємо і всі інші обмежуючі прямі: ; ;...; і відмітимо для кожної з них півплощину, де відповідна змінна більше нуля. У такий спосіб отримують n– 2 прямі та дві осі координат(, ). Кожна з них визначає півплощину, де виконується умова . Частина площини в належить водночас всім півплощинам, утворюючи багатокутник допустимих розв’язків. Припустимо, що в задачі необхідно знайти максимальне значення функціонала: . Підставивши вирази для , , ,...; з (3.18) у цей функціонал, зведемо подібні доданки і отримаємо вираз лінійної функції F всіх n змінних лише через дві вільні змінні та : , де — вільний член, якого в початковому вигляді функціонала не було. Очевидно, що лінійна функція досягає свого максимального значення за тих самих значень та , що й . Отже, процедура відшукання оптимального плану з множини допустимих далі здійснюється за алгоритмом для випадку двох змінних.
Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все... ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования... ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между... ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|