Файл: 5.pdf

Тема 2 Загальна задача лінійного програмування

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

Загальною задачею лінійного програмування є задача знаходження максимального (мінімального) значення функції

де aij; bi; Cj – задані постійні величини, k m.

Цільову функцію можливо оптимізувати на “max” або на “min” – це не є принципово, бо у точці Х* функція Z = f (x*) – досягає мінімуму, а функція Z = –f (x*) – досягає максимуму. Таким чином, є завжди можливість мінімізувати цільову функцію, не втрачаючи загальності підходу.

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

Невідомі, які присутні у лінійній моделі, відповідно до нефункціональних обмежень невід’ємні, що теж не обмежує загальності підходу, бо є можливість завжди записати в іншому вигляді Xj = – (Xj)– , де (Xj)–

–від’ємне значення.

Узалежності від вигляду функціональних обмежень (нерівності або рівності) загальну задачу лінійного програмування поділяють:

на канонічну, якщо k = 0; l = n, де всі функціональні обмеження мають вигляд рівностей;

стандартну (симетричну), якщо k = m; l = n, де всі функціональні обмеження мають вигляд нерівностей.

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

тей у обмеження рівності додаванням до нерівностей невідомих невід’ємних величин:

ai1x1 ai2 x2 ... ain xn yi bi ;

де yi ≥ 0; новим невідомим додають назви відповідно xn+1; xn+2; …; xn+m та відповідно Xj ≥ 0, j = 1, 2, 3, …, n; n + 1, …, n + m;

функціональні обмеження набувають вигляду:

Кількість невідомих моделі Xj ≥ 0 збільшилась до n + m. Будь-яку задачу лінійного програмування можна звести до стан-

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

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

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

xi = Ui – Vi.

Система обмежень у вигляді рівностей сумісна, якщо є хоча б одне

рішення; несумісна, якщо ранг матриці

aij , i 1, 2, ..., m; j 1, 2, 3, ..., n

дорівнює (r), а ранг розширеної матриці (доданий стовпець “bi”) більш ніж (r); надмірна, якщо одне з рівнянь можна отримати як лінійну комбінацію інших. У системі:

n – кількість невідомих;

m – кількість рівнянь.

Якщо система сумісна та не є надмірною, будемо вважати, що ранг її дорівнює (m); тоді:

m – базисні змінні;

(n – m) – вільні змінні, m < n.

Система у даному випадку має нескінченну кількість розв’язків, тому що ми маємо можливість надавати вільним змінним будь-які значення.

Рішення системи рівнянь (обмежень) має назву базисного рішення, якщо всі вільні змінні дорівнюють нулю. Сукупність значень невідомих (чисел) задачі математичного програмування, які задовольняють усім обмеженням задачі, має назву – припустимого рішення, або плану.

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

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

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

Геометричну інтерпретацію множини допустимих розв’язків задачі лінійного програмування та графічний метод її розв’язання приведено у прикладі 6.

Приклад 6

Розглянемо задачу лінійного програмування у формі стандартної

задачі – з обмеженнями у вигляді нерівностей. З метою наочності розглянемо простий випадок з двома невідомими змінними. Пригадаємо задачу про планування випуску продукції малим підприємством.

20 Дослідження операцій

Нерівність – обмеження графічно відображається півплощиною, а границя – граничною прямою, рівняння якої утворюється перетворенням нерівності на рівняння l1 x1 + 3,5x2 = 350; x1 = 0, x2 = 350/3,5 = 100; x1 = 350, x2 = 0 (рис. 1).

Щоб з’ясувати, яка півплощина задовольняє нерівності, перевіримо, наприклад, чи включає точку (0,0) x1 + 3,5x2 350; напівплощина нижче граничної прямої – нерівність виконується – напівплощина нижче границі.

Таким чином перевіримо та побудуємо інші нерівності:

l2 2x1 + 0,5x2 = 240;

x1 = 0, x2 = 240/0,5 = 480; x2 = 0, x1 = 240/2 = 120;

l3 x1 + x2 = 150;

x1 = 0, x2 = 150; x2 = 0, x1 = 150;

l4 x1 + x2 = 110;

x1 = 0, x2 = 110; x2 = 0, x1 = 110;

l5 10x1 + 20x2 = 1400;

x1 = 0, x2 = 1400/20 = 70; x2 = 0, x1 = 1400/10 = 40.

Але точка (0,0) 10 ∙ 0 + 20 ∙ 0 = 0 ≥ 1400 не відповідає нерівності, тому нам потрібна півплощина вище граничної прямої.

Таким чином отримано багатокутник розв’язків, який є опуклим. З метою знаходження максимуму цільової функції z = 10x1 + 20x2 побудуємо лінію рівняння цільової функції, поклавши z = 0, 10x1 +