Реферат: Математичне програмування в економіці

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

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

a_i1 x₁ + a_i2 x₂ + . . . + a_in x_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_1n x_n + x_n+1 = b₁ ,

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

a_m1 x₁ + a_m2 x₂ + . . . + a_mn x_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;