Загальна задача ЛП.

Практична робота № 3

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

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

Хід роботи

1. Побудувати область допустимих рішень задачі лінійного програмування згідно з системою обмежень (Таблиця 1).

2. Побудувати лінію рівня.

3. Побудувати нормальний вектор.

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

Методичні вказівки до виконання практичної роботи

Стандартна задача ЛП.

Знайти мінімум цільової функції Z.

Загальна задача ЛП.

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

Тут . Ясно, що стандартна задача виходить як окремий випадок загальної при .

Цільова функція – обов’язковий критерій оптимальності в методах лінійного програмування.

План – допустиме рішення задачі.

План X називається опорним якщо вектори

…

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

Оптимальним планом задачі ЛП називається план, який доставляє найбільше або найменше значення лінійної функції.

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

Система лінійних обмежень задачі ЛП завдає в просторі багатокутник і оскільки цільова функція є лінійною, то вона не має максимума в середині багатокутника, тобто екстремум Z досягається на границі області допустимих розв’язків. Тому якщо задача залежить від двох змінних, то її можна розв’язати графічно. Багатокутник допустимих розв’язків будується за системою обмежень, як область перетину прямих, що задається нерівностями a_i1x₁+a_i2x₂≤ b_i().

Лінії на яких значення цільової функції Z=c₁x₁+c₂x₂ є постійні, називаються лініями рівня. А напрям зростання Z визначається вектором . Таким чином, для знаходження вершини, що дістає max значення функції Z потрібно побудувати яку-небудь лінію рівня. Наприклад c₁x₁+c₂x₂=0. Переміщуючи її паралельно самій собі в напрямку вектору , в першій вершині багатокутника розв’язків, що зустрілася є мінімум. А в останній вершині, що зустрілася максимум Z.

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

z = 5x1+4x2+15

2x1+3x2 7; 2x1+2x2≤ 9; - 2x1+x2 6.

Приклад 2. Побудувати лінію рівня.

Приклад 3. Побудувати нормальний вектор.

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

Першою точкою, що зустрічається на шляху лінії рівня є точка, що є перетином прямих f1 та f3.

Це буде точка min. Знайдемо її координати.

Значення цільової функції в цій точці становитиме:

Z_min=

Останньою точкою, що зустрічається на шляху лінії рівня є точка, що є перетином прямих f2 та f3.

Це буде точка max. Знайдемо її координати.

Значення цільової функції в цій точці становитиме:

Z_max=