A proposta do exercício é solucionar o Problema de Corte de Estoque utilizando programação linear. A abordagem de Programação Linear para Problema de Corte de Estoque foi estudada primeiramente por Gilmore e Gomory (1961) e consiste em produzir uma certa quantidade de itens gerados do corte de peças maiores disponíveis em estoque, a programação linear envolvida no problema está na otimização de uma função objetivo para minimizar o número total de peças em estoque a serem cortadas, ou as perdas, ou os custos de peças cortadas. A solução deste tipo de problema é muito importante no planejamento de produção de grandes indústrias . O problema de corte de estoque ainda podem ser classificados em unidimensionais, quando apenas uma dimensão é importante no processo do corte; bidimensionais, quando duas dimensões (comprimento e largura) são importantes no processo de corte; ou tridimensionais, em que as três dimensões são importantes no processo de corte. Para esse exercício, vamos considerar um problema de corte unidimensional.
A formulação matemática do problema é feita da seguinte forma:
Definição 1: Padrão de corte é a forma como o objeto em estoque é cortado para a produção dos itens em demanda
\(a = (a_{1}, a_{2}, …, a_{m})\) em que \(a_{i}\) é a quantidade de itens do tipo 1 no padrão de corte
No caso unidimensional, este vetor a só corresponde ao um padrão de corte se e somente se satisfazer o Problema de Mochila
\(l_1a_1 + .. + l_ma_m \le L \)
\(a_i \ge 0, i = 1… m \text{ e inteiro} \)
se o sistema acima tem n soluções, então \(a_{1}, a_{2}, …, a_{n}\)
No modelo matemático, será considerado que \(x_j\) é o numero de vezes que o objeto é cortado usando o padrão de corte \(j\)
O problema de corte de estoque unidimensional que em por objetivo minimizar o número de objetos em estoque a serem cortados é formulado da seguinte forma:
\(\text{minimizar} f(x) = x_1 + x_2 + ... x_n \)
\(\text{sujeito a} \ \textbf{a}_1x_1 + \textbf{a}_2x_2 + ... + \textbf{a}_nx_n = D \)
\(x_j \ge 0 , j = 1,... ,n \text{ e inteiro} \)
É possível notar que é um problema de otimização linear inteiro. O modelo matemático acima descreve uma função objetivo que minimiza o total de objetos que serão cortados, restrições de igualdade que garantem que a quantidade de itens produzidos seja igual à demanda do produtos e restrição de integridade que garante a repetição de cada padrão de corte j seja um número inteiro não-negativo.
O problema pode ainda ter várias interpretações, seja para minimizar a perda total ou os custos das peças que foram cortadas.
Para a resolução do exercício, será proposto a solução em Python de um problema muito comum de corte de estoque presente em inúmeras apostilas e livros da área de Pesquisa Operacional.
Certa empresa trabalha com a produção de etiquetas autocolantes. O papel usado para sua confecção encontra-se em bobinas de mesmo comprimento, todas com largura de 50 cm. As encomendas para a próxima semana impõem a necessidade de se cortarem 32 bobinas de 15 cm de largura, 17 bobinas de 17,5 cm de largura e 21 bobinas de 20 cm de largura. É política da empresa manter em estoque o excedente ao pedido em quantidade máxima de 10 bobinas cortadas de acordo com a encomenda. Esta ação evita a imobilização de capital, uma vez que são incertos os próximos pedidos. O objetivo do problema é a minimização das perdas.
Na imagem é possível ver, um exemplo de como é feito um tipo de corte nas bobinas.
O departamento técnico relacionou na tabela abaixo as possíveis programações de cortes, tendo em vista as encomendas.
Para o modelo matemático do problema, vamos considerar os seguintes dados
\(padroes\) : Conjunto de padrões de corte;
\(bobinas\) : Conjunto dos tipos de bobinas;
\(desp_i\) : Desperdício relativo aos cortes realizados de acordo com o padrão i;
\(demanda_j\) : Demanda por bobinas do tipo j;
\(a_{ij}\) : Quantidade de bobinas do tipo j produzidas no padrão de corte i;
\(estmax\) : Estoque máximo de bobinas permitido.
e a variável de decisão do problema de minimização de perdas, é
\(x_i\) : Número de cortes realizados segundo o padrão \(i\)
O modelo de programação matemática para esse problema de corte de estoque é:
\(min \sum_{i \in padroes} desp_ix_i \)
\(\text{sujeito a} \)
\(\sum_{i \in padroes} a_{ij}x_i \ge demanda_j, ∀j ∈ bobinas \)
\(\sum_{i \in padroes} a_{ij}x_i \le demanda_j + estmax, ∀j ∈ bobinas xi ∈ Z + ∀i ∈ padroes \)
O modelo, para este problema fica da seguinte forma:
\( \text{min } 5x_1 + 2.5x_2 + 0x_3 + 0x_4 + 12.5x_5 + 10x_6 \)
\(\text{sujeito a } \)
\(3x_1 + 2x_2 + 1x_3 + 2x_4 + 0x_5 + 0x_6 \ge 32 \)
\(0x_1 + 1x_2 + 2x_3 + 0x_4 + 1x_5 + 0x_6 \ge 17 \)
\(0x_1 + 0x_2 + 0x_3 + 1x_4 + 1x_5 + 2x_6 \ge 21\)
\(3x_1 + 2x_2 + 1x_3 + 2x_4 + 0x_5 + 0x_6 \le 42 \)
\(0x_1 + 1x_2 + 2x_3 + 0x_4 + 1x_5 + 0x_6 \le 27 \)
\(0x_1 + 0x_2 + 0x_3 + 1x_4 + 1x_5 + 2x_6 \le 31\)
\(x_1, ..., x_6 \ge 0\)
Para resolver o problema utilizando python, usaremos o método simplex com o pacote scipy e a função linprog
import numpy as np
from scipy.optimize import linprog
A = np.array([[-3,-2,-1,-2,0,0],
[0,-1,-2,0,-1,0],
[0,0,0,-1,-1,-2],
[3,2,1,2,0,0],
[0,1,2,0,1,0],
[0,0,0,1,1,2]])
b = np.array([-32,-17,-21, 42,27,31])
c = np.array([5,2.5,0,0,12.5,10])
res = linprog(c, A_ub=A, b_ub=b, bounds=(0, None))
print('Optimal value:', res.fun, '\nX:', res.x)
Optimal value: 21.25
X: [ 0. 0. 8.5 16.75 0. 2.125]
Os valores encontrados para a Solução ótima são:
\( x_1 = 0, x_2 = 0, x_3 = 8.5, x_4 = 16.75, x_5 = 0, x_6 = 2.125 \)
Com Solução ótima de valor \( 21.25\)