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

⇐ ПредыдущаяСтр 6 из 6

Геометричний метод розв’язування задач лінійного програмування іноді можна застосовувати і у випадку, коли число змінних більше двох. Наприклад, якщо задача задана в канонічній формі і система обмежень дозволяє виразити всі змінні через які-небудь дві з них. Тоді підставляючи ці вирази в цільову функцію, одержимо функцію двох змінних. Виключаючи виражені змінні в обмеженнях, переходимо від обмежень-рівностей до обмежень-нерівностей виду (2).

Приклад 4. Знайти найбільше значення функції при обмеженнях:

Розв’язання. Виражаємо з обмежень задачі всі змінні через і . Спочатку з третього рівняння системи знаходимо : . Підставивши цей вираз в перше і друге рівняння, одержимо:

Тепер з другого рівняння можна визначити : . Підставивши вираз в перше рівняння, одержимо: , звідки . За умовою задачі змінні , невід’ємні, тому одержимо таку систему обмежень:

або

Нарешті, вирази для , підставимо в цільову функцію і одержимо:

Таким чином, ми одержали задачу для функції двох змінних: знайти найбільше значення функції при таких обмеженнях:

Побудуємо тепер многокутник , обумовлений останньою системою обмежень, і пряму , задану рівнянням :

Паралельним переносом прямої в напрямку вектора , визначимо точку A многокутника , яка відповідає найбільшому значенню z (точку “виходу”). Координати цієї точки знаходимо з умови перетину прямих ( ) і ( ):

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

, , .

Відповідь: .

Приклад 5. Знайти мінімум цільової функції при таких обмеженнях:

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

Тепер задачу можна розв’язати графічно. Побудуємо многокутник допустимих планів .

Легко бачити, що цільова функція досягає мінімуму в точці :

Відповідь: .

Геометричне розв’язання задач нелінійного програмування.

Загальних методів розв’язання задач нелінійного програмування не існує, тому майже завжди такі задачі вимагають творчого підходу. Іноді геометричний метод дозволяє розв’язати і задачі нелінійного програмування. Деякі випадки такого типу розглянемо на прикладах.

Приклад 6. Знайти найбільше значення функції при обмеженнях:

Розв’язання. Спочатку побудуємо графічно множину допустимих планів. Це буде множина точок чверті кола радіуса 6 з центром в початку координат, яка лежить у першому квадранті:

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

Пригадаємо, що дотична до кола в точці дотику перпендикулярна до радіуса. А це означає, що радіус буде перпендикулярним і до прямої . Кутовий коефіцієнт k₁ цієї прямої легко знайти: . Відомо, що кутові коефіцієнти двох взаємно перпендикулярних прямих задовольняють умові: , звідки , а рівняння прямої має вид: .

Тепер координати точки знаходимо з системи двох рівнянь:

Остаточно одержуємо: .

Відповідь:, .

Приклад 7. Знайти найбільше і найменше значення функції при обмеженнях:

Розв’язання. Спочатку визначимо графічно множину допустимих планів. Це буде множина точок у першому квадранті, задана трикутником :

Тепер перетворимо цільову функцію до такого виду: .

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

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

Точка : .

Відповідь: , .

Приклад 8. Знайти найбільше і найменше значення функції при обмеженнях:

Розв’язання. Визначаємо графічно множину допустимих планів. Це буде множина точок у першому квадранті, яка задана трикутником :

Перетворимо тепер цільову функцію до такого виду:

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

Тепер легко бачити, що мінімальне значення цільова функція набуває в точці : , . В точці : , . В точці : , . І нарешті в точці цільова функція досягає максимуму: , .

Відповідь: , .

Приклад 9. Знайти найбільше і найменше значення функції при обмеженнях:

Розв’язання. Побудуємо спочатку множину допустимих планів задачі. Це буде перетин півплощин, яки визначаються нерівностями системи обмежень задачі. Це буде многокутник .

Побудуємо лінію рівня цільової функції. Ця лінія визначається рівнянням

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

Отже, , , , .

Відповідь: , .

Дата добавления: 2018-05-13; просмотров: 301; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 2 3 4 56

Мы поможем в написании ваших работ!