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

04 Programação Linear Formulação de Modelos 2020 Prof Sérgio F Mayerle 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 2 of 25 Otimização de sistemas estruturais Problema de planejamento da produção Problema de geração de escalas de trabalho Problema de logística 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 3 of 25 Otimização de sistemas estruturais O Eng Pompermayer está estudando o sistema estrutural abaixo composto por duas barras rígidas e quatro cabos Ajudeo a determinar a carga total máxima permitida para ser carregada nos pontos P1 P2 P3 P4 e P5 considerando as resistências admissíveis dos cabos e as dimensões das barras conforme mostra a figura abaixo Formule o modelo de PL 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 4 of 25 Variáveis de decisão Como o sistema encontrase em equilíbrio segundo as leis da física a a força resultante verticais que atua sobre cada barra deve ser nula b o momento resultante sobre cada barra é nulo jP peso alocado no ponto j em kgf iT Tensão do cabo i z Peso total alocado no sistema Restrições o somatório das forças que atuam sobre cada barra é nulo o somatório dos momentos que atuam sobre cada barra é nulo a resistência dos cabos deve ser observada não negatividade Objetivo Maximizar a soma dos pesos alocados nas barras Modelo Matemático 1 2 3 4 5 1 2 3 1 2 3 4 5 3 4 1 2 3 1 3 4 5 3 1 2 3 4 5 1 2 3 4 3 2 4 3 2 4 0 0 100 0 300 0 250 0 200 Max z P P P P P s a P P T T T P P P T T P P T T P P P T P P P P P T T T T 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 5 of 25 Entrada LINGO MODEL Z MAX P1 P2 P3 P4 P5 FVS P1 P2 T3 T1 T2 FVI P3 P4 P5 T3 T4 MBS 3 P1 2 P2 T3 4 T1 MBI 3 P3 2 P4 P5 4 T3 RC1 T1 100 RC2 T2 300 RC3 T3 250 RC4 T4 200 END Resultado LINGO Variable Value Reduced Cost P1 0000000 05000000 P2 7500000 0000000 P3 2750000 0000000 P4 0000000 0000000 P5 1750000 0000000 T3 2500000 0000000 T1 1000000 0000000 T2 2250000 0000000 T4 2000000 0000000 Row Slack or Surplus Dual Price Z 5250000 1000000 FVS 0000000 0000000 FVI 0000000 1000000 MBS 0000000 05000000 MBI 0000000 0000000 RC1 0000000 2000000 RC2 7500000 0000000 RC3 0000000 05000000 RC4 0000000 1000000 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 6 of 25 Problema de planejamento da produção Um construtor produz barcos por encomenda e tem os seguintes pedidos para serem entregues no final dos próximos 6 meses Mês Fev Mar Abr Mai Jun Jul No Barcos 11 19 52 31 18 15 Ele pode contruir até 40 barcos em qualquer mês e pode guardar até 30 barcos em estoque O custo de construção de cada barco barcos é de R 10000000 por unidade Caso algum barco seja construído em um mês um custo fixo adicional de R 20000000 deve ser considerado Para manter um barco em estoque durante o período de um mês o construtor gasta R 1000000 Qual deve ser o plano ótimo de construção de modo a minimizar o custo total do construtor Formule o modelo para obter a solução Variáveis de decisão tx número de barcos contruídos no mês t t 1 t indica fábrica em operação t 0 em caso contrário tS número do barcos em estoque ao final do período t z custo total do construtor de barcos Restrições atendimento aos pedidos capacidade de produção mensal capacidade do estoque não negatividade Objetivo Minimizar o custo total do construtor de barcos 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 7 of 25 Modelo Matemático 6 1 0 1 100 10 200 0 16 0 40 16 0 30 16 01 16 t t t t t t t t t t t t Min z x S s a S S S x D t x t S t t 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 8 of 25 Entrada LINGO MODEL Z MIN 100 X1 X2 X3 X4 X5 X6 10 S1 S2 S3 S4 S5 S6 200 D1 D2 D3 D4 D5 D6 EI S0 0 B1 S1 S0 X1 11 B2 S2 S1 X2 19 B3 S3 S2 X3 52 B4 S4 S3 X4 31 B5 S5 S4 X5 18 B6 S6 S5 X6 15 E1 S1 30 E2 S2 30 E3 S3 30 E4 S4 30 E5 S5 30 E6 S6 30 C1 X1 40 D1 C2 X2 40 D2 C3 X3 40 D3 C4 X4 40 D4 C5 X5 40 D5 C6 X6 40 D6 BIN D1 BIN D2 BIN D3 BIN D4 BIN D5 BIN D6 END 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 9 of 25 Resultado LINGO Variable Value Reduced Cost X1 1100000 0000000 X2 3100000 0000000 X3 4000000 0000000 X4 3100000 0000000 X5 3300000 0000000 X6 0000000 0000000 S1 0000000 1000000 S2 1200000 0000000 S3 0000000 2000000 S4 0000000 1000000 S5 1500000 0000000 S6 0000000 1200000 D1 1000000 2000000 D2 1000000 2000000 D3 1000000 2000000 D4 1000000 2000000 D5 1000000 2000000 D6 0000000 2000000 S0 0000000 0000000 Row Slack or Surplus Dual Price Z 1587000 1000000 EI 0000000 1000000 B1 0000000 1000000 B2 0000000 1000000 B3 0000000 1100000 B4 0000000 1000000 B5 0000000 1000000 B6 0000000 1100000 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 10 of 25 E1 3000000 0000000 E2 1800000 0000000 E3 3000000 0000000 E4 3000000 0000000 E5 1500000 0000000 E6 3000000 0000000 C1 2900000 0000000 C2 9000000 0000000 C3 0000000 1000000 C4 9000000 0000000 C5 7000000 0000000 C6 0000000 1000000 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 11 of 25 Problema de geração de escalas de trabalho O principal hospital da cidade atende a demanda durante as 24 horas do dia tanto para casos de emergência ambulatório e UTI As necessidades do pessoal de enfermagem distribuemse segundo a tabela abaixo Turno Horário Número Mínimo de Enfermeiros 1 0000 0200 705 2 0200 0400 557 3 0400 0600 386 4 0600 0800 674 5 0800 1000 972 6 1000 1200 1120 7 1200 1400 940 8 1400 1600 1142 9 1600 1800 915 10 1800 2000 987 11 2000 2200 1021 12 2200 200 926 O horário de trabalho de um enfermeiro pode ser de oito horas intercaladas por um período de 2 horas para descanso 4 4 ou seis horas contínuas O salário pago para cada enfermeiro é de R 800000 para o caso dele trabalhar 8 horas e R 600000 para o caso de trabalhar apenas 6 horas Formule o modelo para determinar a escala ótima de trabalho dos enfermeiros 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 12 of 25 Variáveis de decisão Segue na tabela abaixo o esquema de cobertura de horários para as diversas alternativas de contratação definidas pelas variáveis X contratação 4h 4h e Y contratação 6h Cobertura de Horários Var 0002 0204 0406 0608 0810 1012 1214 1416 1618 1820 2022 2224 X00 1 1 1 1 X02 1 1 1 1 X04 1 1 1 1 X06 1 1 1 1 X08 1 1 1 1 X10 1 1 1 1 X12 1 1 1 1 X14 1 1 1 1 X16 1 1 1 1 X18 1 1 1 1 X20 1 1 1 1 X22 1 1 1 1 Y00 1 1 1 Y02 1 1 1 Y04 1 1 1 Y06 1 1 1 Y08 1 1 1 Y10 1 1 1 Y12 1 1 1 Y14 1 1 1 Y16 1 1 1 Y18 1 1 1 Y20 1 1 1 Y22 1 1 1 Necessidade 705 557 386 674 972 1120 940 1142 915 987 1021 926 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 13 of 25 hx número de enfermeiros contratados para trabalhar 44 horas com duas de descanso com entrada prevista na hora h hy número de enfermeiros contratados para trabalhar 6 horas contínuas com entrada prevista na hora h z Custo total da folha de pagamento Restrições Satisfazer o número mínimo de enfermeiros de cada período Não negatividade Modelo matemático 1 2 1 2 0 0 T T x Min z c c y x s a A A N y x y onde a matriz 1 T A é a matriz dos contratados pelo padrão X e 2 T A é a matriz dos contratados pelo padrão Y 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 14 of 25 Entrada LINGO MODEL Z Min 8000 X00 X02 X04 X06 X08 X10 X12 X14 X16 X18 X20 X22 6000 Y00 Y02 Y04 Y06 Y08 Y10 Y12 Y14 Y16 Y18 Y20 Y22 H00 X00 X16 X18 X22 Y00 Y20 Y22 705 H02 X00 X02 X18 X20 Y00 Y02 Y22 557 H04 X02 X04 X20 X22 Y00 Y02 Y04 386 H06 X00 X04 X06 X22 Y02 Y04 Y06 674 H08 X00 X02 X06 X08 Y04 Y06 Y08 972 H10 X02 X04 X08 X10 Y06 Y08 Y10 1120 H12 X04 X06 X10 X12 Y08 Y10 Y12 940 H14 X06 X08 X12 X14 Y10 Y12 Y14 1142 H16 X08 X10 X14 X16 Y12 Y14 Y16 915 H18 X10 X12 X16 X18 Y14 Y16 Y18 987 H20 X12 X14 X18 X20 Y16 Y18 Y20 1021 H22 X14 X16 X20 X22 Y18 Y20 Y22 926 END 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 15 of 25 Resultado LINGO Variable Value Reduced Cost X00 2770000 0000000 X02 5450000 0000000 X04 3315000 0000000 X06 6550000 0000000 X08 5750000 0000000 X10 1590000 0000000 X12 3840000 0000000 X14 1175000 0000000 X16 6350000 0000000 X18 0000000 0000000 X20 0000000 0000000 X22 0000000 0000000 Y00 0000000 0000000 Y02 0000000 0000000 Y04 0000000 0000000 Y06 0000000 0000000 Y08 0000000 0000000 Y10 0000000 0000000 Y12 0000000 0000000 Y14 0000000 0000000 Y16 0000000 0000000 Y18 3805000 0000000 Y20 1390000 0000000 Y22 2255000 0000000 Row Slack or Surplus Dual Price Z 02069000E08 1000000 Z 2069000000 H00 0000000 2000000 H02 0000000 2000000 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 16 of 25 H04 0000000 2000000 H06 0000000 2000000 H08 0000000 2000000 H10 0000000 2000000 H12 0000000 2000000 H14 0000000 2000000 H16 0000000 2000000 H18 0000000 2000000 H20 0000000 2000000 H22 0000000 2000000 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 17 of 25 Problema de logística Uma construtora está planejando a produção concreto para seis obras distintas cujas necessidades e possibilidade de abastecimento encontramse no esquema abaixo Os custos unitários de transporte da matéria prima e do concreto são os seguintes Cimento 045 Rtonkm Brita e Areia 075 Rm3km Concreto 286 Rm3km Considerando que a composição do concreto é de Cimento 300 kg Brita 0705 m3 Areia 0350 m3 e que as distâncias em km entre as usinas de concreto e as obra constam do quadro abaixo determine a forma como deverão ser atendidas as necessidades diárias da empresa nos vários projetos em execução Obra 01 Obra 02 Obra 03 Obra 04 Obra 05 Obra 06 Usina 01 12 km 45 km 36 km 28 km 5 km 27 km Usina 02 18 km 23 km 27 km 23 km 10 km 33 km 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 18 of 25 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 19 of 25 Variáveis de decisão ijxCON quantidade de concreto transportada da usina i para a obra j em m3dia ixCIM quantidade de cimento transportada da fábrica de cimento até a usina i em tondia BRIT xki quantidade de brita transportada da jazida k até a usina i em m3dia ixAREIA quantidade de areia transportada da jazida de areia até a usina i em m3dia z Custo mensal total de transporte em Rdia Restrições Satisfazer a restrições de capacidade da fábrica de cimento Satisfazer a restrição de capacidade da jazida de areia Satisfazer as restrições de capacidade das jazidas de brita Satisfazer as restrições de composição do traço do concreto Não negatividade Objetivo Minimizar o custo total de produção e logística 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 20 of 25 Modelo matemático 2 6 2 3 1 1 1 1 2 2 1 1 2 1 6 1 286 075 075 045 13 12 CONC CONC CONC BRIT BRIT BRIT ij i ij ki k ki i j i k AREIA AREIA AREIA CIM CIM CIM i i i i i i BRIT BRIT ki k i CONC USINA ij i j CIM i Min z d C x d C x d C x d C x s a x Cap k x Cap i x 2 1 2 1 2 1 16 CIM i AREIA AREIA i i CONC CONC ij j i Cap x Cap x Dem j 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 21 of 25 6 1 6 1 6 3 1 1 035 12 03 12 0705 12 0 0 0 CONC AREIA ij i j CONC CIM ij i j CONC BRIT ij ki j k AREIA CIM i i BRIT ki CONC ij x x i x x i x x i x x i x i k x i j 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 22 of 25 Entrada LINGO MODEL Z Min 286 12 XCON11 45 XCON12 36 XCON13 28 XCON14 5 XCON15 27 XCON16 286 18 XCON21 23 XCON22 27 XCON23 23 XCON24 10 XCON25 33 XCON26 075 70 XBRT11 120 XBRT12 30 XBRT21 20 XBRT22 165 XBRT31 115 XBRT32 075 75 XAREIA1 65 XAREIA2 045 350 XCIM1 380 XCIM2 2155 XCIM1 XCIM2 65 XAREIA1 XAREIA2 28 XCON11 XCON12 XCON13 XCON14 XCON15 XCON16 35 XCON21 XCON22 XCON23 XCON24 XCON25 XCON26 52 XBRT11 XBRT12 45 XBRT21 XBRT22 432 XBRT31 XBRT32 CapJaz1 XBRT11 XBRT12 300 CapJaz2 XBRT21 XBRT22 400 CapJaz3 XBRT31 XBRT32 250 CapUs1 XCON11 XCON12 XCON13 XCON14 XCON15 XCON16 600 CapUs2 XCON21 XCON22 XCON23 XCON24 XCON25 XCON26 700 CapCim XCIM1 XCIM2 250 CapAreia XAREIA1 XAREIA2 500 DemObr1 XCON11 XCON21 130 DemObr2 XCON12 XCON22 98 DemObr3 XCON13 XCON23 115 DemObr4 XCON14 XCON24 230 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 23 of 25 DemObr5 XCON15 XCON25 145 DemObr6 XCON16 XCON26 85 NecAreia1 035 XCON11 XCON12 XCON13 XCON14 XCON15 XCON16 XAREIA1 NecAreia2 035 XCON21 XCON22 XCON23 XCON24 XCON25 XCON26 XAREIA2 NecCim1 030 XCON11 XCON12 XCON13 XCON14 XCON15 XCON16 XCIM1 NecCim2 030 XCON21 XCON22 XCON23 XCON24 XCON25 XCON26 XCIM2 NecBri1 0705 XCON11 XCON12 XCON13 XCON14 XCON15 XCON16 XBRT11 XBRT21 XBRT31 NecBri2 0705 XCON21 XCON22 XCON23 XCON24 XCON25 XCON26 XBRT12 XBRT22 XBRT32 END Resultado LINGO Variable Value Reduced Cost XCON11 1300000 0000000 XCON12 0000000 5978250 XCON13 0000000 2260250 XCON14 0000000 1116250 XCON15 1450000 0000000 XCON16 8500000 0000000 XCON21 0000000 2029750 XCON22 9800000 0000000 XCON23 1150000 0000000 XCON24 2300000 0000000 XCON25 0000000 1743750 XCON26 0000000 2029750 XBRT11 1661150 0000000 XBRT12 0000000 4500000 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 24 of 25 XBRT21 8768500 0000000 XBRT22 3123150 0000000 XBRT31 0000000 6245000 XBRT32 0000000 3245000 XAREIA1 1260000 0000000 XAREIA2 1550500 0000000 XCIM1 1080000 0000000 XCIM2 1329000 0000000 Row Slack or Surplus Dual Price Z 2357209 1000000 CAPJAZ1 1338850 0000000 CAPJAZ2 0000000 3700000 CAPJAZ3 2500000 0000000 CAPUS1 2400000 0000000 CAPUS2 2570000 0000000 CAPCIM 9100000 0000000 CAPAREIA 2189500 0000000 DEMOBR1 0000000 2903300 DEMOBR2 0000000 3249275 DEMOBR3 0000000 3363675 DEMOBR4 0000000 3249275 DEMOBR5 0000000 2703100 DEMOBR6 0000000 3332300 NECAREIA1 0000000 1212500 NECAREIA2 0000000 1137500 NECCIM1 0000000 3730000 NECCIM2 0000000 3865000 NECBRI1 0000000 1045000 NECBRI2 0000000 9700000 04 Programação Linear Formulação de Modelos EPS7005 Pesquisa Operacional 2020 Prof Sérgio F Mayerle Page 25 of 25 F I M 2020 Prof Sérgio Mayerle