85767 (597827), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Z = C_j X_j min,

j=1

за умов:

n

b_ij x_j a_j, i = 1,2,3…m;

j=1

x_j 0, j = 1,2,3…n.

Найбільш трудомістка частина задачі – визначення способів (варіантів) розкрою, яка здійснюється за формулою:

m

l_i bij + C_j l, j = 1,2,3…n;

і=1

0 C_j min (l_i).

Цільова функція:

Z = 50 х₁ + 10 х₂ + 0 х₃ + 70 х₄ + 60 х₅ + 50 х₆ + +40 х₇ + 30 х₈ + 20 х₉ + 10 х₁₀ + 0 х₁₁; min;

обмеження:

3 х₁ + 2х₂ + 3х₃ + 1х₄ + х₅ + х₆ 150;

х₂ + 2х₄ + х₅ + 4х₇ + 3х₈ + 2х₉ + х₁₀ 140;

х₂ + 3х₃ + х₄ + 3х₅ + 5х₆ + 2х₈ + 4х₉ + 6х₁₀ + 8х₁₁ 48;

x_j 0, j = 1,2,3…11.

Розв’язок задачі складає:

Z* = 2300, x* = (8; 48; 0; 0; 0; 0; 23; 0; 0; 0; 0;).

Приклад 4. Задача комплектного розкрою деталей.

На розкрій поступають варіанти заготовок (t = 2) у обсязі “b_i” (i = 1,2,3…m) кожного. Потрібно виготовити комплекти деталей, які налічують по “l_k” штук (l₁ = 1 деталь, l₂ = 2 деталі) деталей кожного різновиду деталей. Кожна одиниця “і”-ого (одного з двох) різновидів заготовки може бути розкроєна n_i (j = 1,2…n_i) різними способами. При розкрої одиниці “t”-ого матеріалу заготовки “j”-тим способом отримаємо “a_tjk” одиниць “k” – а деталі. Потрібно скласти програму виготовлення якомога більше комплектів деталей, маючи вказані заготовки та задану комплектацію. Дамо конкретні дані: заготовки (t = 1) “А” мають довжину 5 м, кількість b₁ = 100 штук; заготовки (t = 2) “В” мають довжину 4 м, кількість b₂ = 175 штук; деталі D₁ мають довжину 2,0 м, деталі D₂ - довжину 1,25 м; до одного комплекту залучають одну (l₁ = 1) деталь D₁ та дві (l₂ = 2) деталі D₂. Треба виготовити якомога більше комплектів деталей.

Розв’язок задачі. Позначимо: x_tj - кількість одиниць “t”-ого різновиду заготовок, які розкроюваються “j”-тим способом; х – загальна кількість комплектів. Побудуємо таблицю варіантів розкрою заготовок.

Таблиця

Цільова функція: Z = x max;

обмеження:

по кількості заготовок:

х₁₁ + х₁₂ + х₁₃ 100;

х₂₁ + х₂₂ + х₂₃ 175;

по комплектності:

х₁₁ + 2х₁₂ + 0х₁₃ + 2х₂₁ + х₂₂ + 0х₂₃ х;

2х₁₁ + 0х₁₂ + 4х₁₃ + 0х₂₁ + х₂₂ + 3х₂₃ 2х;

х_ij 0; х 0.

Оптимальний план складає:

Z* = 264; х* = (0; 0; 100; 132; 0; 43)

Приклад 5. Задача про складання суміші.

На підприємстві потрібно виготовити суміш, які містить 30% речовини П₁, 20% речовини П₂, 40% речовини П₃ та 10% речовини П₄. Для виготовлення суміші можливо використати три різновиди сировини М₁, М₂, М₃ з різними співвідношеннями речовин та різною вартістю. Потрібно скласти суміш з мінімальною вартістю та наданим складом речовин. Ісходні дані наведені у таблиці.

Таблиця

Розв’язок задачі. Позначимо “x_i” - кількість використаної сировини “M_i”.

Цільова функція:

Z = 4 x₁ + 2x₂ + 3x₃ min;

обмеження:

0 ,3х₁ + 0,1х₂ + 0,6х₃ 0,3;

0,1х₁ + 0,2х₂ + 0,2х₃ 0,2;

0,5х₁ + 0,6х₂ + 0,1х₃ 0,4;

0,1х₁ + 0,1х₂ + 0,1х₃ 0,1;

х_і 0.

Оптимальний план х* = (0; 0,6; 0,4); Z* = 2,4.

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

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

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

n

Z = C_j X_j ,

j=1

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

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

n

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

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

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.

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

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

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

Характеристики

Список файлов книги