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

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

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

 

n

Z = S C_j ´ X_j,

j=1

(Z = С₀ + С₁Х₁ + С₂Х₂ +... + С_nХ_n);

 

За умов функціональних обмежень:

 

n

S a_ij x_j £ b_i, де і = 1,2,..., k;

j=1

а₁₁х₁ + а₁₂х₂ +... + a_1nx_n £ b₁ ,

а₂₁х₁ + а₂₂х₂ +... + a_2nx_n £ b_{2 ,}

а_k1х₁ + а_k2х₂ +... + a_knx_n £ b_k,

n

S a_ij x_j = b_i, де і = k +1, k + 2,..., m;

j=1

a_k+1;1x₁ + a_k+1;2x₂ +... + a_k+1;nx_n = b_k+1 ,

a_k+2;1x₁ + a_k+2;2x₂ +... + a_k+2;nx_n = b_k+2 ,

a_m;1x₁ + a_m;2x₂ +... + a_m;nx_n = b_m

 

нефункціональних обмежень:

x_j ³ 0, де j = 1,2,3,... n;

а також a_ij; b_i; c_j – задані постійні величини, а ще k £ m.

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

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

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

x_j = - (x_j)^-, де (x_j)^- - від’ємне.

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

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

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

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

 

a_i1x₁ + a_i2x₂ + ... + a_inx_n + y_i = b_i;

 

де y_i ³ 0; новим невідомим дають назви відповідно x_n+1; x_n+2; ...; х_n+m; та відповідно x_j ³ 0, де j = 1,2,3 ... n; n + 1 ... n + m;

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

 

n

S a_ij x_j + y_i = b_i, де і = 1, 2, 3 ..., m;

j=1

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n + x_n+1 = b₁,

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n + x_n+2 = b₂,

a_m1x₁ + a_m2x₂ + ... + a_mnx_n + x_n+m = b_m,

 

кількість невідомих моделі x_j ³ 0 збільшилась до n + m.

Слушне зауваження у підручнику – якщо знак нерівності ³, так додаткові невідомі треба віднімати від лівої частини нерівності.

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

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

x_i = u_i – v_i.

 

Система обмежень у вигляді рівностей сумісна, якщо є хоча б одно рішення; несумісна, якщо ранг матриці ½a_ij, i = 1,2, ... n равен (r), а ранг розширеної матриці (додан стовбець “b_i”) більше ніж (r); надмірна, якщо одне з рівнянь можливо отримати як лінійну комбінацію інших. У системі: n – кількість невідомих,

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

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

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

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

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

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

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

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

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

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

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

 

Z = 10 x₁ + 20 x₂ ; Z ® max;

 

х₁ + 3,5 х₂ £ 350;

2 х₁ + 0,5 х₂ £ 240;

х₁ + х₂ £ 150;

х₁ + х₂ ³ 110;

10 х₁ + 20 х₂ ³ 1400;

х₁ ³ 0;

х₂ ³ 0.

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

l₁ ® x₁ + 3,5x₂ = 350;

x₁ = 0, x₂ = 350 / 3,5 = 100; x₂ = 0, x₁ = 350.

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

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

l₂ ® 2x₁ + 0,5x₂ = 240;

x₁ = 0, x₂ = 240 / 0,5 = 480; x₂ = 0, x₁ = 240 / 2 = 120;

l₃ ® x₁ + x₂ = 150; x₁ = 0; x₂ = 150; x₂ = 0, x₁ = 150;

l₄ ® x₁ + x₂ = 110; x₁ = 0; x₂ = 110; x₂ = 0, x₁ = 110;

l₅ ® 10x₁ + 20x₂ = 1400;

x₁ = 0, x₂ = 1400 / 20 = 70; x₂ = 0, x₁ = 1400 / 10 = 140;

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

Таким чином отриманий многокутник розв’язків, до речі – опуклий, як завжди.

З метою знаходження максимуму цільової функції

Z = 10 x₁ + 20 x₂ побудуємо лінію рівня цільової функції, поклавши Z = 0,

10 x₁ + 20 x₂ = 10; x₁ = 0, x₂ = 40; x₂ = 0; x₁ = 80;

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

Ця точка відповідає перетину прямих

х₁ + 3,5 х₂ = 350; - l₁ (×) C (70; 80)

х₁ + х₂ = 250; - l₃

х₁ = 70, х₂ = 80,

Z_max (x) = 10 × x₁ + 20 × x₂ = 10 × 70 + 20 × 80 = 23000 грн.

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

У розглянутому випадку многокутник розв’язків не тільки опуклий, а ще і є замкненим. Можливі варіанти опуклого многокутника розв’язків, який є необмеженим.

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

 

 

Малюнок. Многокутник розв’язків несумісної системи обмежень

задачі лінійного програмування