Programação Linear Formulação de Modelos-2020-1

02 Programação Linear – Formulação de Modelos © 2020 Prof. Sérgio F. Mayerle 02 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 2 of 14  Problema do mix ótimo de produção  Problema de blending ótimo  Problema de corte unidimensional  Problema de corte bidimensional 02 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 3 of 14 Problema do mix ótimo de produção Uma pequena fábrica de papel toalha manufatura três tipos de produtos A, B e C. A fábrica recebe o papel em grandes rolos. O papel é cortado, dobrado e empacotado. Dada apequena escala da fábrica, o mercado absorverá qualquer produção a um preço constante. O lucro unitário de cada produto é respectivamente R$ 1,00, R$ 1,50, e R$ 2,00. O quadro abaixo identifica o tempo requerido para operação (em horas) em cada seção da fábrica, bem como a quantidade de máquinas disponíveis, que trabalham 40 horas por semana. Seção Produto A Produto B Produto C Núm. Máquinas Corte 8,0 5,0 2,0 3 Dobra 5,0 10,0 4,0 10 Embalagem 0,7 1,0 2,0 2 Planeje a produção semanal da fábrica. Variáveis de decisão , , A B C x x x quantidade dos produtos A, B e C, produzidas semanalmente; Z contribuição para a formação do lucro total semanal. Restrições  restrições de capacidade semanal de produção para cada seção;  não negatividade. Objetivo Maximizar a contribuição para a formação do lucro total semanal. 02 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 4 of 14 Modelo Matemático 1 1.5 2 . : 8 5 2 3 40 5 10 4 10 40 0.7 1 2 2 40 , , 0 A B C A B C A B C A B C A B C Max Z x x x s a x x x x x x x x x x x x                 Resultado Variable Value Reduced Cost XA 0.000000 0.6125000 XB 10.00000 0.000000 XC 35.00000 0.000000 Row Slack or Surplus Dual Price Z 85.00000 1.000000 CORTE 0.000000 0.1250000 DOBRA 160.0000 0.000000 EMPAC 0.000000 0.8750000 02 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 5 of 14 Problema de blending ótimo Consideremos o problema da metalurgia de alumínio, em que se deseja produzir 2.000 kg de uma liga de alumínio, a custo mínimo, pela mistura de diversas matérias-primas (minérios). Esta liga deve atender a requisitos de engenharia que especificam os máximos e mínimos de diversos elementos químicos que a compõe. Os custos das matérias-primas são: Materiais Mat1 Mat2 Mat3 Mat4 Mat5 Al-puro Si-puro Custo (R$/kg) 0,03 0,08 0,17 0,12 0,15 0,21 0,38 A composição dos minérios e a participação mínima/máxima de cada um dos elementos químicos nos 2.000 kg da liga são mostradas a seguir: Elemento Mat1 Mat2 Mat3 Mat4 Mat5 Al-puro Si-Puro Ferro 15% 4% 2% 4% 2% 1% 3% Cobre 3% 5% 8% 2% 6% 1% - Manganês 2% 4% 1% 2% 2% - - Magnésio 2% 3% - - 1% - - Alumínio 70% 75% 80% 75% 80% 97% - Silício 2% 6% 8% 12% 2% 1% 97% Na tabela anterior temos, por exemplo, que Mat1 contém 15% de Ferro, 3% de Cobre, etc. 02 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 6 of 14 Temos, ainda, que a liga a ser obtida (2.000 kg) deve conter, no máximo, 60 kg de Ferro, 100 kg de Cobre e que a quantidade de Silício deve estar entre 250 kg e 300 kg. Elemento Mínimo (kg) Máximo (kg) Ferro - 60 Cobre - 100 Manganês - 40 Magnésio - 30 Alumínio 1500 - Silício 250 300 Quanto à disponibilidade de matéria-prima, os dados estão indicados a seguir na linha “Disponibilidade Máxima”. A linha “Disponibilidade Mínima” refere-se a quantidade que se deseja forçar a entrar neste processo (por algum motivo, tal como liberação de espaço). Disponível Mat1 Mat2 Mat3 Mat4 Mat5 Al-puro Si-Puro Mínimo - - 400 100 - - - Máximo 200 750 800 700 1500 Infinito Infinito Formule o modelo para determinação da composição ótima da liga. 02 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 7 of 14 Parâmetros do modelo jc custo da materia-prima j 1,...,7 ; ij a percentual do elemento químico i 1,...,6 na composição da matéria-prima j 1,...,7 ; min max , i i R R requerimento mínimo e máximo do elemento químico i 1,...,6 na composição da liga, em kg; min max , j j U U necessidade de consumo mínimo e máximo da matéria-prima j 1,...,7 . Variáveis de decisão jx quantidade de materia-prima j 1,...,7 a ser usada na composição da liga, em kg; Z custo total da liga. Restrições  produção mínima de 2.000 kg da liga;  atendimento aos requisitos mínimo e máximo de cada elemento químico;  atendimento das necessidades de consumo mínimo e máximo de cada matéria-prima;  não negatividade. Objetivo Minimiza o custo total da liga a ser produzida. 02 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 8 of 14 Modelo matemático 7 1 7 1 7 min 1 7 max 1 min max . : 2.000 1,...,6 1,...,6 1,...,7 j j j j j ij j i j ij j i j j j j Min z c x s a x a x R i a x R i U x U j                     Resultado Variable Value Reduced Cost X1 0.000000 0.2553652 X2 618.9623 0.000000 X3 747.1147 0.000000 X4 388.5181 0.000000 X5 0.000000 0.1374923E-01 X6 151.2350 0.000000 X7 108.2047 0.000000 Row Slack or Surplus Dual Price Z 296.0258 -1.000000 PESOT 14.03479 0.000000 FERRO 0.000000 2.600898 COBRE 0.000000 0.1190160E-01 MANGA 0.000000 0.5655694 MAGNE 11.43113 0.000000 ALUMI 0.000000 -0.2385630 SILIC_MIN 0.000000 -0.4721927 SILIC_MAX 50.00000 0.000000 MIN_X3 347.1147 0.000000 MIN_X4 288.5181 0.000000 MAX_X1 200.0000 0.000000 MAX_X2 131.0377 0.000000 MAX_X3 52.88533 0.000000 MAX_X4 311.4819 0.000000 MAX_X5 1500.000 0.000000 02 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 9 of 14 Problema de corte unidimensional Uma fábrica necessita cortar uma fita de aço de 12 cm de largura em tiras de 2,4 cm, 3,4 cm e 4,5 cm de largura. As necessidades globais das tiras são: Tipo de Tira Largura (cm) Comprimento Mínimo (m) Tira 1 2,4 2.500 Tira 2 3,4 4.500 Tira 3 4,5 8.000 Formule o problema que permite otimizar o consumo da fita a ser cortada minimizando a perda de material. Discussão Supondo que as fitas de aço apresentam comprimento de 100 metros cada (arbitrado, pois seria muito difícil trabalhar com fitas muito longas), existem 8 distintos padrões eficientes de corte logitudinal que podem ser consideradas no atendimento das necessidades globais das tiras: Número de tiras de 100m de comprimento por corte Corte ( )j Tira 1 (2,4 cm) Tira 2 (3,4 cm) Tira 3 (4,5 cm) Sobra (cm) 1 1 0 2 0,6 2 0 2 1 0,7 3 1 1 1 1,7 4 3 0 1 0,3 5 0 3 0 1,8 6 2 2 0 0,4 7 3 1 0 1,4 8 5 0 0 0,0 02 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 10 of 14 Variável de decisão jx número de fitas de aço de 12 cm x 100 m cortadas segundo o padrão de corte j 1,...,8 ; Z número total de fitas de aço de 12 cm x 100 m utilizadas. Restrições  atender o comprimento mínimo do pedido;  não negatividade Objetivo Minimizar o número total de fitas de aço utilizadas Modelo matemático 8 1 8 min 1 . : 1,...,3 0 1,...,8 j j ij j i j j Min z x s a a x Q i x j            onde Qimin é o número de tiras de 100 metros que precisam ser produzidas para atender as necessidades globais de tiras do tipo i 1,...,3 . 02 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 11 of 14 Solução Variable Value Reduced Cost X1 28.75000 0.000000 X2 22.50000 0.000000 X3 0.000000 0.2500000 X4 0.000000 0.5000000 X5 0.000000 0.2500000 X6 0.000000 0.5000000 X7 0.000000 0.7500000 X8 0.000000 1.000000 Row Slack or Surplus Dual Price Z 51.25000 -1.000000 TIRA_1 3.750000 0.000000 TIRA_2 0.000000 -0.2500000 TIRA_3 0.000000 -0.5000000 02 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 12 of 14 Problema de corte bidimensional Considere a produção das latas que são estampadas em folhas planas de alumínio. Uma lata consiste em um corpo principal e em duas extremidades (topo e base). Existem 4 padrões de estampas possíveis (que envolvem 2 tamanhos diferentes de folha de metal), como mostrado ao lado.Considerando que deverão ser fabricadas 5.000 latas, qual é a forma mais econômica de produzí-las? Discussão Da descrição do problema pode-se montar a tabela abaixo, onde o custo é calculado considerando que a espessura da folha de alumínio é a mesma, independente do tipo de estampa: Estampa Custo Corpo Tampa 1 70 x 75 = 5250 3 3 2 70 x 75 = 5250 1 7 3 65 x 105 = 6825 4 5 4 70 x 75 = 5250 0 9 02 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 13 of 14 Variáveis de decisão jx número de cortes da estampa j 1,...,4 ; Z custo total do plano de corte. Restrições  produzir 50.00 corpos e 10.000 tampas  não negatividade Objetivo Minimizar o custo total do plano de corte Modelo matemático 1 2 3 4 1 2 3 1 2 3 4 1 2 3 5250 5250 6825 5250 . : 3 1 4 5.000 3 7 5 9 10.000 , , 0 Min z x x x x s a x x x x x x x x x x             Solução Variable Value Reduced Cost X1 0.000000 568.7500 X2 0.000000 189.5833 X3 1250.000 0.000000 X4 416.6667 0.000000 Row Slack or Surplus Dual Price Z 0.1071875E+08 -1.000000 CORPO 0.000000 -977.0833 TAMPA 0.000000 -583.3333 02 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 14 of 14 F I M (© 2020 Prof. Sérgio Mayerle)