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

Якщо задачы:

Z = Σ Сj*xj / Σ dj * xj  max ( min) (3)

Σ aj*xj (<>=) bj, i = 1,m (4)

можна представити графічно, то її можна розв’язати графічним методом, тобто якщо задача (3-4) задана на площині або в двовимірному просторі, то для її розв’язання можна застосувати графічний метод!

Знайти Мах. (Мін.) значення функції при обмеженнях:

(5)

(6)

, (7)

(6) – допустима область нашої задачі, так як вона складається з лінійних нерівностей, то геометрично це є випуклий багатокутник.

Дослідимо функцію мети:

Z = c1x1 + c2x2 / d1x1 + d2x2  max ( min)

c1x1 + c2x2 = dzx1 + dzx2

( c1 – d1z) x1 + (c2 – d2z) x2 =0

x2= - (c1 – d1z) / (c2 – d2z) x1 (7)

(7) – представляє собою лінійну функцію з кутовим коефіцієнтом, який

К(z) = - (c1 – d1z) / (c2 – d2z) (8) і проходить через початок координат.

(8) – кутовий коефіцієнт є функція від z. Дослідимо спадання і зростання цієї функції: для цього нам потрібно знайти першу похідну:

К’(z) = (d1c2-c1d2) / (c2 – d2z)^2

Маємо слідуючі випадки:

а ) К’(z)>0, тому (d1c2-c1d2) >0

К(z) – є зростаючою, при збільшенні (z) – (К) збільшується, і навпаки.

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

А для задачі на Міn. Повертаємо за часовою стрілкою, до тих пір поки вона не перетне допустиму область останній раз.

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

б ) К’(z) <0 (d1c2-c1d2) <0

К(z) – є спадною функцією, при збільшенні (z) – (К) зменшується, і навпаки.

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

На Мах. – за часовою стрілкою, до тих пір доки останній раз не перетне область.

На Min. – проти часової стрілки до останнього перетину з областю.

Візуально визначаємо оптимальний розв’язок.

При розв’язуванні задачі дробово-лінійного програмування графічним методом можливі такі випадки:

- багатокутник розв’язків задачі обмежений і максимальне та мінімальне значення досягаються у його кутових точках;

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

- багатокутник розв’язків задачі необмежений і досягається лише один із екстремумів;

- багатокутник розв’язків задачі необмежений, точки екстремумів визначити неможливо.

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

(d1c2 – d2c1) >0

(d1c2 – d2c1) <0