Решение задачи размещения производства и переработки продукции

Бюллетень науки и практики / Bulletin of Science and Practice

Постановка задачи и математическая модель. Пусть имеется m пунктов производства однородной продукции A_i , c ограничением на объем производства x _;<  a _;, i = 1,2,..., m. Произведенная в этих пунктов продукция доставляется на n предприятий B_} , j = 1,2,... n , произведенной компании, где часть продукции в объеме bj >  0 не перерабатывается предприятием оставляется для своей нужды, а часть продукции в объеме у^ >  0 перерабатывается.

Объем перерабатываемой продукции yj0, j = 1,2,..., n на каждом предприятии Bj ограничен ее максимальной возможностью по переработке Q , т.е. 0 ^ yjо ^ Qj, J = 1,2,..., n.. Предполагается также известным величина b — объем перерабатываемой продукции всеми предприятиями.

Для каждого пункта производства   A_i , i = 1,2,..., m известна функция   щ ( x_i )

определяющая зависимость стоимости производимой продукции от объема производства x , а для каждого предприятия B_} , j = 1,2,..., n задана функция ^ ( у_{} 0}) , которая определяет затраты на переработку продукции y_{j 0}, j = 1,2,..., n. .Известна также матрица транспортных расходов c . Требуется определить объемы производства x i >  0, i = 1,2,..., m , переработки ij _{m , n}

У)о, j = 1,2,...,n, и перевозки xv > 0,i = 1,2,...m, j = 1,2,...n  минимизирующие суммарные затраты, т.е. требуется найти минимум.

mn      mn

L(x, y)=EE cjxj+E ?i(xi)+E^j(yjo) i =1 j=1              i=1

при условиях n

Ex„ = x, < a.,i = 1,2...m, ij          ii j=1

E x j = b j + y j o , j = ¹ ,2,.-., n , i = 1

E y , 0 = b o , j = 1

0 <  y j o <  Q j , j = 1,2,..., n

X: > 0,x„ > 0, i = 1,2,...m, j = 1,2,..., n, i               ij где x=IxjL • y=Ы n,, nm

Предполагается , что выполняется условия E ^bj + ^b 0 <  E ai , j = 1                    i = 1

n b 0

Рассмотрим задачу (1)-(6) в случае ,когда функции ^i(xt) и Wj (y^ 0) — линейные, т.е. ^i(xi) = cixi,  xi e[0,ai 1 i = 1,2,...,m, Wj(yj0) = Cj0yj0, yj0 e[0,Qj ] j = 1,2,...,n. Исключим из целевой функции (1) и ограничений (2) переменные xt, i = 1,2,..., m.,. После этого задачу (1)(6) запишем в виде:

найти минимум m n                                                                      (8)

L (x, y ) = EE (cj + ci) xij^{+ c}j0 yj 0

i=1 j =1

при условиях:

n

Exij< ai,i = 1,2,...,m, j=1

ixjj = bj + yj0 < QJ + bj, J = ^1,2,...^,n, i=1

Z.y- о=ьo,

J=1

x,, 0 0, j = 1,2,..., n, i = 1,2,..., n, yjо > 0, j = 1,2,...,n

Для решения экстремальной задачи (8)-(13) используем метод, изложенного в работе [1, 2]. Преобразуем задачу (8-13). Введем дополнительные переменные xin+1 00,i = 1,2,...,m, и mn xm+^ > 0, j = 1,2,..., n, обращаем неравенство(9), (10) в равенства. Определяем Z xin+l и Z xm+Xj . i=1

Они соответственно принимают значения: mmn

Zxn+1 = Zat- (Zbj+ b0) ,                      ( i =1                i =1

nnn

Z Xm+1j=Z Qj— (Z bj+ b 0) , j=1              j =1

где Qj = Qj + bj, j = 1,2,.., n .

После этого задачу можно представить в виде транспортной Таблицы 1, где коэффициенты при переменных x_in+1> 0, i = 1,2,.., m и x_m+>0, 0, j = 1,2,..n, соответственно полагаются равны нулю ,т.е. c_in+1= 0, i = 1,2,..., m, c_m+^ = 0, j = 1,2,.., n,

Таблица 1

Q1 Q2 ..            Qn b0 m Za i=1 I - (Zbj+ b0) j=1 a c11 c12 ..                 c1n M 0 • x 1 n+1 a2 c21 c22 ..               c2n M 0 • x 2 n +1 ……        ….            …         ..        …..           ….              ….. a m cm1 cm2 .. mn M 0 • xmn+1 Q1 - b1 0 ••• xm+11 M ..         M c10… y10 M Q2 - b 2 M 0 • x 2 n+1 ..         M c20… y20 M …..       …..          …..        ..       ……         ….            ……… Qn - bn M M ..       0 • x 2 n+1 cn0 …y10 M гдеM — достаточно большое положительное число(запрещающий тариф).

Пример. Для демонстрации способа решения задачи приведем небольшой пример тремя пунктами производства (m = 3) и четырьмя пунктами переработки (n = 4).

Имеется: три пункта производства однородной продукции Аг, i = 1,2,3 с максимальным объемом производства продукции 0 < x; < a;,i = 1,2,3, т.е 0 < x; < 150,0 < x2 < 150,0 < x3 < 100.

Продукция, произведенная в этих пунктах доставляется на четыре предприятия

Bj■, j = 1,2,3,4 произведенной компании, где часть продукции в объеме b ={50,60,40,40} без переработки оставляет для своей нужды, а часть продукции в объеме у^ > 0, j = 1,2,3,4 перерабатывается предприятием Bj, j = 1,2,.., n . Объем перерабатываемой продукции y_j0 > 0, j = 1,2,3,4 на каждом предприятии Bj ограничен ее максимальной возможностью по переработке, т.е. 0 < y₁₀< 50,0 < у₂₀< 90,0 < у₃₀< 60,0 < у₄₀< 80.

Предполагается, что известно объем перерабатываемой продукции всеми предприятиями этой компании за планируемый период времени, т.е. b₀= 170. Кроме этого, для каждого пункта производства A, i = 1,2,3 , и потребления (переработки) B_}, j = 1,2,3,4 , известны линейные непрерывные функции ^ (x_t), i = 1,2,3 и ^ (у_}0), j = 1,2,3,4 , которые имеют вид:

^ (Xj) = 2Xj, Xj е [0,150], ^ (x₂) = 2 x₂, x₂ е [0,150], ^(x3) = x3, x3 е [0,100], ^1⁽У10) = ³У10,У10 ^е[0,50], ^2⁽У20) = У20, У20 ^е[0,901 W3⁽У30) = ³У30,У30 ^е[0,60^], ¥4⁽У40) = ²У40, У40 ^е[0,80]-

Известна также матрица транспортных расходов c=ы

3,4

Требуется определить план производства продукции xi > 0, i = 1,2,3 , перевозки x_tj > 0, i = 1,2,3, j = 1,2,3,4 , переработки у_;o> 0, j = 1,2,3,4, доставляющие минимум целевой функции. Экономико-математическая модель задачи записывается в следующем виде:

найти минимум

L (x, у) = 3 x{ j + 5 xx 2 + 3x13 + 4x14 + 4 x2 x + 8 x22 + 6 x23 + 3 x24 + 7 x3 j + 4 x32 + 6 x33 +

+ 6 x 34 + 2 x1 + 2 x 2 + x 3 + 3 у 10 + у 20 + 3 у 30 + 2 у 40

при условиях 444

^xtj = xx < 150, ^x2 = x2 < 150, У x3j = x3 < 100, j=1                         j=1

У xi 1 = 50 + У10, У xi2 = 60 + У20, У xi3 = 40 + У30, У xi4 = 40 + У40, i=1                              i=1                               i=1

У У, 0 = 170, =1

0 < У10 < 50,0 < у20 < 90,0 < у30 < 60,0 < у40 < 80, xl > 0, i = 1,2,3,                                                           (19)

• x, > 0, i = 1,2,3, j = 1,2,3,4,

где ^x = |^x,|₃₄, y = |y 1, y 2, y 3, y 4^

Преобразуем задачу (14-19). Исключим переменные x_i, i = 1,2,3, из целевой функции (14) и ограничений (15). Определяем значения Q,, j = 1,2,3,4, по формуле Q_f = Qj + b_:, j = 1,2,3,4, т.е. Qi = 100, Q₂= 150, Q₃= 100, Q₄= 120. Тогда задача (14)-(19) принимает следующий вид: найти минимум

L (x, y) = 5 x j + 7 x12 + 5 x13 + 6 x14 + 6 x2 j +10x22 + 8x23 + 5x24 + 8x3 3 + 5 x32 + 7 x33 + 7 x34 +(20)

^{+ 3}y 10 ⁺y 20 ^{+ 3}y 30 ^{+ 2}y 40

при условиях:

£x,j < 150, £x2j < 150, £x3j < 100, j=1                  j=1

£x„ = 50 + y 10 < 100, £xi2 = 60 + y20 < 150, £xi3 = 40 + y30 < 100, £xi4 = 40 + y40 < 120, (22)

i=1                                           i=1                                            i =1

£ Ую = 170, j=1

x_y > 0, i = 1,2,3. j = 1,2,3,4.

Введем дополнительные переменные x_in+1, i = 1,2,3 , и x_m+XJ, j = 1,2,3,4. Определяем 34                                                                             3                    4

величины £ xn+1 ^и£ ^xm+1 j согласно формулам (*) . Имеем £ xin+1 = 4^0,£ xm+1 j = ¹¹⁰ . i=1                  j=1                                                                                  i=1                    j =1

Решение задачи (20)-(24) будем искать методом потенциалов [3]. Получим оптимальное решение задачи. Заметим в Таблице 2, отличными от нуля переменными оптимального плана является:

x * = {x_n = 100, x₁₃= 40, x₂₄ = 120, x₃₂ = 100}, y ’ = ^{y 10 = ^50,y 20 = ⁴⁰, y 30 = ⁰, y40 = ^80} x3 = 140, x ’ = 120, x₃' = 100.

Минимальное значение целевой функции задачи L(x³,y³) = 2150 у.е. Из оптимального решения можно сделать вывод, что предприятие B получает продукцию из пункта производства A_t в объеме b₃= 100 для своей потребности. Предприятие В_х получает продукцию в объеме 100 единиц из А^, часть из них в объеме bj = 50 оставляется для своей потребности, а остальные y₁₀ = 50 продукцию перерабатывает. А предприятие В₂ получает продукцию в объеме 100 единиц из A , из них оставляет себе 60 единиц для своей потребности, а остальные y₂₀ = 40 единиц продукции перерабатывает. Предприятие В₄ получает из A 120 единиц продукции, оставляет для своей нужды 40 единиц, остальные y₄₀ = 80 единиц направляет для переработки.

При этом суммарные затраты на производство продукции ее перевозки и переработки составляет 2150 у.е.

Таблица 2

	Q1 =100	Q 2 = 150	Q3 = 100	Q4 = 120	b0=170	3 Z a. i =1	- (Zbj + b.) j=1
a =150	5 … 100	7	5 … 40	6	100		0 … 10
a2= 150	6	10	8	5 … 120	100		0 … 30
a3 = 100	8	5 … 100	7	7	100		0
Q1 - ^=50	0				3 … 50		100
Q2 - b2 = 90		0 … 50			1 … 40		100
Q3 - Ьз = 60			0 … 6		3 … 0		100
Q4 - b4 = 80				0	2 … 80		100