Математичне програмування в економіці (стр. 2 из 6)

- “х_j” - кількість одиниць (прутків) первинного матеріалу, який буде розкроєно за “j” варіантом (способом);

- а_і – потрібна кількість деталей “і”-ого різновиду (l_і - довжини);

- с_j – залишок при розкрої одиниці первинного матеріалу (прутка) за “j”-тим способом (варіантом);

- b_ij – кількість деталей “і”-ого виду, яку отримують при виготовлені з одиниці первинного матеріалу (прутка) за “j”-тим варіантом (способом).

Залишок за “j”-тим способом від розкрою = c_j ´ x_j, загалом

n

Z = S C_j ´ X_j ® min,

j=1

за умов:

n

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

j=1

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

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

m

S 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”-тим способом; х – загальна кількість комплектів. Побудуємо таблицю варіантів розкрою заготовок.

Таблиця

Варіанти заготовок	Довжина заготов-ки, м	Спосіб розкрою	Розмір деталі		Кількість загото-вок, bi	План розкрою, xtj
			2 м (D1)	1,25 м (D2)
t = 1	5 м (А)	j = 1	1	2	b1=100	х11
		j = 2	2	0		х12
		j = 3	0	4		х13
t = 2	4 м (В)	j = 1	2	0	b2=175	х21
		j = 2	1	1		х21
		j = 3	0	3		х21
-	Комплект		l1 = 1	l2 = 2	-

Цільова функція: 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% речовини П₄. Для виготовлення суміші можливо використати три різновиди сировини М₁, М₂, М₃ з різними співвідношеннями речовин та різною вартістю. Потрібно скласти суміш з мінімальною вартістю та наданим складом речовин. Ісходні дані наведені у таблиці.

Таблиця

Речовини	Сировина			Кількість сировини у суміші
	М1	М2	М3
П1	0,3	0,1	0,6	0,3
П2	0,1	0,2	0,2	0,2
П3	0,5	0,6	0,1	0,4
П4	0,1	0,1	0,1	0,1
Вартість за одиницю сировини	4	2	3
-	х1	х2	х3

Розв’язок задачі. Позначимо “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 = 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₁ ,