Лекція 7. Задачі лінійного програмування

Предмет:

Математика

Тип роботи:

Лекція

К-сть сторінок:

Мова:

Українська

Оцінка:

Лекція 7. Задачі лінійного програмування

План

1. Системи лінійних нерівностей та графічний спосіб їх розв’язування.

2. Лінійна функція двох змінних. Найбільше та найменше значення лінійної функції на опуклому многокутнику.

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

4. Приклади складання економіко-математичних моделей задач лінійного програмування та розв'язування їх графічним методом.

1. Системи лінійних нерівностей та графічний спосіб їх розв’язування

Система, де — дійсні числа, називається системою лінійних нерівностей з двома змінними.

Замість знака « » в одній або кількох нерівностях можуть бути знаки « », « », « ».

Система нерівностей (1) називається сумісною або несуперечливою, якщо існує хоча б одна точка, для якої виконуються всі нерівності системи.

Система нерівностей (1) називається несумісною або суперечливою, якщо не існує жодної точки, для якої виконуються всі нерівності системи.

Кожна з нерівностей виконується тільки для точок із замкненої півплощини , утвореної при поділі площини на дві частини прямою . Усі нерівностей системи (1) виконуються тільки для тих точок , які належать усім замкненим півплощинам , , …, . Якщо таких точок немає, то система суперечлива.

Непустий перетин деякої кількості замкнених півплощин називається замкненим многокутником.

Непустий перетин деякої кількості відкритих півплощин називається відкритим многокутником.

Отже, розв’язком сумісної системи лінійних є многокутник розв’язків.

Найзручніше розв’язувати системи нерівностей графічно. Розглянемо кілька прикладів.

Приклад 1. Розв’язати графічно систему нерівностей

Розв’язання. В площині побудуємо прямі (пригадайте, що для побудови прямої достатньо двох точок).

Виразимо з рівняння прямої змінну через змінну:

Побудуємо відповідну пряму суцільною лінією, бо у відповідній нерівності системи маємо знак нестрогої нерівності « » (див. рисунок 1).

Виразимо з рівняння прямої змінну через змінну:

Побудуємо відповідну пряму штриховою лінією, бо у відповідній нерівності системи маємо знак строгої нерівності « » (див. рисунок 1).

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

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

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

Рис.1

Приклад 2. Розв’язати графічно систему нерівностей

Розв’язання. Побудуємо графіки прямих ліній, що відповідають рівнянням , , . Вибираючи для кожної із цих прямих «пробну» точку, переконуємося, що нерівності задовольняють точки, які лежать під прямою , нерівності задовольняють точки, які лежать над прямою , а нерівності — точки під прямою .

Отже, розв’язком системи є відкритий трикутник , який показано на рисунку 2.

Рис.2

Приклад 3. Розв’язати графічно систему нерівностей

Розв’язання. Побудуємо графіки прямих ліній, що відповідають рівнянням , , . Вибираючи для кожної із цих прямих «пробну» точку, переконуємося, що нерівності задовольняють точки, які лежать під прямою , нерівності задовольняють точки, які також лежать під прямою , нерівності — точки під прямою .

Отже, розв’язком системи є точки кута , який зображено на рисунку 3.

Рис.3

ЗАВДАННЯ ДЛЯ САМОСТІЙНОГО РОЗВ’ЯЗАННЯ

Завдання 1. Переконатися, що розв’язком запропонованої системи нерівностей є закритий чотирикутник , який зображено на рисунку.

Завдання 2. Розв’язати графічно систему лінійних нерівностей:

де 1) ;

2) − сума, яку отримаємо додавши цифри вашої дати народження.

Завдання 3. Побудувати область розв’язків системи лінійних нерівностей:

а) б) в) г)

2. Лінійна функція двох змінних. Найбільше та найменше значення лінійної функції на опуклому многокутнику

Вираз, де — дійсні числа, називається лінійною функцією двох змінних .

Прямі лінії на площині , паралельні прямій, що визначається рівнянням , називаються лініями рівнів лінійної функції (2).

Властивості лінійної функції двох змінних

1.У всіх точках кожної з прямих , де — стала, функція зберігає стале значення , а при переході від однієї прямої до іншої її значення змінюється (на деяке значення ).

2.Функція зростає у напрямі, що визначається нормальним вектором прямої .

3.Вектор показує напрям зменшення значень функції.

4.На довільному відрізку функція (2) досягає найбільшого (найменшого) значення на одному з кінців відрізка.

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

Множина точок площини називається опуклою, якщо разом з кожними її двома точками і вона містить весь відрізок, що сполучає ці точки.

На рисунку 4 наведено приклад опуклої множини точок площини.

Рис.4 Рис.5

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

На рисунку 5 наведено приклад неопуклої множини точок площини.

Теорема. Лінійна функція ,