Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como resolver Problema de Corte de Estoque Com Programação Linear utilizando Python?

0 votos
86 visitas
perguntada Dez 4, 2019 em Administração por Fernanda Amorim (11 pontos)  

Considere os seguintes problemas apresentados abaixo. Enuncie,
explique e ressalte a importância do problema. Apresente a solução
do problema usando programação linear. Dê um exemplo e use
uma biblioteca de programação linear do python para resolvê-lo
computacionalmente:

Problema de Corte de Estoque.

Compartilhe

1 Resposta

0 votos
respondida Dez 4, 2019 por Fernanda Amorim (11 pontos)  

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.

A imagem será apresentada aqui.

O departamento técnico relacionou na tabela abaixo as possíveis programações de cortes, tendo em vista as encomendas.

A imagem será apresentada aqui.

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\)

comentou Dez 9, 2019 por Luiz Filippe (6 pontos)  
Fernanda, sua resposta me parece exata. Consegui reproduzir o código no Python e entender bem seu passo a passo. Está bem explicada. A questão é bastante interessante por apresentar a programação linear sendo resolvida computacionalmente e como ela pode ser aplicada na solução de problemas práticos de firmas. Enfim, eu sugeria apenas uma alteração na forma como você apresentou o código; mera questão estética. Ao invés de iniciar dando espaço, você poderia colocar o comando "\(\quad\)" para espaço ou "\(\qquad\)" para espaço maior. Isso evita que apareça essa janela cinza no meio da resposta. Apenas uma opinião, nada que comprometa a resposta ou que deva ser obrigatoriamente acatado.
...