Slide Programação Linear Formulação de Modelos Pt 2-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. Ajude-o 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 encontra-se 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 0.000000 0.5000000 P2 75.00000 0.000000 P3 275.0000 0.000000 P4 0.000000 0.000000 P5 175.0000 0.000000 T3 250.0000 0.000000 T1 100.0000 0.000000 T2 225.0000 0.000000 T4 200.0000 0.000000 Row Slack or Surplus Dual Price Z 525.0000 1.000000 FVS 0.000000 0.000000 FVI 0.000000 1.000000 MBS 0.000000 0.5000000 MBI 0.000000 0.000000 RC1 0.000000 2.000000 RC2 75.00000 0.000000 RC3 0.000000 0.5000000 RC4 0.000000 1.000000 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$ 100.000,00 por unidade. Caso algum barco seja construído em um mês, um custo fixo adicional de R$ 200.000,00 deve ser considerado. Para manter um barco em estoque durante o período de um mês, o construtor gasta R$ 10.000,00. 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 40 . : 0 1,...,6 0 40 1,...,6 0 30 1,...,6 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                       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 11.00000 0.000000 X2 31.00000 0.000000 X3 40.00000 0.000000 X4 31.00000 0.000000 X5 33.00000 0.000000 X6 0.000000 0.000000 S1 0.000000 10.00000 S2 12.00000 0.000000 S3 0.000000 20.00000 S4 0.000000 10.00000 S5 15.00000 0.000000 S6 0.000000 120.0000 D1 1.000000 200.0000 D2 1.000000 200.0000 D3 1.000000 -200.0000 D4 1.000000 200.0000 D5 1.000000 200.0000 D6 0.000000 -200.0000 S0 0.000000 0.000000 Row Slack or Surplus Dual Price Z 15870.00 -1.000000 EI 0.000000 100.0000 B1 0.000000 100.0000 B2 0.000000 100.0000 B3 0.000000 110.0000 B4 0.000000 100.0000 B5 0.000000 100.0000 B6 0.000000 110.0000 04 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 10 of 25 E1 30.00000 0.000000 E2 18.00000 0.000000 E3 30.00000 0.000000 E4 30.00000 0.000000 E5 15.00000 0.000000 E6 30.00000 0.000000 C1 29.00000 0.000000 C2 9.000000 0.000000 C3 0.000000 10.00000 C4 9.000000 0.000000 C5 7.000000 0.000000 C6 0.000000 10.00000 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 distribuem-se segundo a tabela abaixo: Turno Horário Número Mínimo de Enfermeiros 1 00:00 – 02:00 705 2 02:00 – 04:00 557 3 04:00 – 06:00 386 4 06:00 – 08:00 674 5 08:00 – 10:00 972 6 10:00 – 12:00 1120 7 12:00 – 14:00 940 8 14:00 – 16:00 1142 9 16:00 – 18:00 915 10 18:00 – 20:00 987 11 20:00 – 22:00 1021 12 22:00 – 2:00 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$ 8.000,00 para o caso dele trabalhar 8 horas e R$ 6.000,00 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 00-02 02-04 04-06 06-08 08-10 10-12 12-14 14-16 16-18 18-20 20-22 22-24 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 (4+4) 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 277.0000 0.000000 X02 54.50000 0.000000 X04 331.5000 0.000000 X06 65.50000 0.000000 X08 575.0000 0.000000 X10 159.0000 0.000000 X12 384.0000 0.000000 X14 117.5000 0.000000 X16 63.50000 0.000000 X18 0.000000 0.000000 X20 0.000000 0.000000 X22 0.000000 0.000000 Y00 0.000000 0.000000 Y02 0.000000 0.000000 Y04 0.000000 0.000000 Y06 0.000000 0.000000 Y08 0.000000 0.000000 Y10 0.000000 0.000000 Y12 0.000000 0.000000 Y14 0.000000 0.000000 Y16 0.000000 0.000000 Y18 380.5000 0.000000 Y20 139.0000 0.000000 Y22 225.5000 0.000000 Row Slack or Surplus Dual Price Z 0.2069000E+08 -1.000000 Z = 20.690.000,00 H00 0.000000 -2000.000 H02 0.000000 -2000.000 04 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 16 of 25 H04 0.000000 -2000.000 H06 0.000000 -2000.000 H08 0.000000 -2000.000 H10 0.000000 -2000.000 H12 0.000000 -2000.000 H14 0.000000 -2000.000 H16 0.000000 -2000.000 H18 0.000000 -2000.000 H20 0.000000 -2000.000 H22 0.000000 -2000.000 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 encontram-se no esquema abaixo. Os custos unitários de transporte da matéria prima e do concreto são os seguintes:  Cimento: 0,45 R$/ton.km  Brita e Areia: 0,75 R$/m3.km  Concreto: 2,86 R$/m3.km Considerando que a composição do concreto é de:  Cimento: 300 kg  Brita: 0,705 m3  Areia: 0,350 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 m3/dia; ixCIM quantidade de cimento transportada da fábrica de cimento até a usina i, em ton/dia; BRIT xki quantidade de brita transportada da jazida k até a usina i, em m3/dia; ixAREIA quantidade de areia transportada da jazida de areia até a usina i, em m3/dia; z Custo mensal total de transporte, em R$/dia; 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 2,86 0,75 0,75 0,45 . : 1,...,3 1,2 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 1,...,6 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 0,35 1,2 0,3 1,2 0,705 1,2 , 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 = 2.86 * (12 * XCON11 + 45 * XCON12 + 36 * XCON13 + 28 * XCON14 + 5 * XCON15 + 27 * XCON16) + 2.86 * (18 * XCON21 + 23 * XCON22 + 27 * XCON23 + 23 * XCON24 + 10 * XCON25 + 33 * XCON26) + 0.75 * (70 * XBRT11 + 120 * XBRT12 + 30 * XBRT21 + 20 * XBRT22 + 165 * XBRT31 + 115 * XBRT32) + 0.75 * (75 * XAREIA1 + 65 * XAREIA2) + 0.45 * (350 * XCIM1 + 380 * XCIM2)+ 215.5 * (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) + 43.2 * (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] 0.35 * (XCON11 + XCON12 + XCON13 + XCON14 + XCON15 + XCON16) = XAREIA1; [NecAreia2] 0.35 * (XCON21 + XCON22 + XCON23 + XCON24 + XCON25 + XCON26) = XAREIA2; [NecCim1] 0.30 * (XCON11 + XCON12 + XCON13 + XCON14 + XCON15 + XCON16) = XCIM1; [NecCim2] 0.30 * (XCON21 + XCON22 + XCON23 + XCON24 + XCON25 + XCON26) = XCIM2; [NecBri1] 0.705 * (XCON11 + XCON12 + XCON13 + XCON14 + XCON15 + XCON16) = (XBRT11 + XBRT21 + XBRT31); [NecBri2] 0.705 * (XCON22 + XCON22 + XCON23 + XCON24 + XCON25 + XCON26) = (XBRT12 + XBRT22 + XBRT32); END Resultado LINGO Variable Value Reduced Cost XCON11 0.000000 48.08750 XCON12 98.00000 0.000000 XCON13 0.000000 22.60250 XCON14 0.000000 11.16250 XCON15 145.0000 0.000000 XCON16 85.00000 0.000000 XCON21 130.0000 0.000000 XCON22 0.000000 8.602500 XCON23 115.0000 0.000000 XCON24 230.0000 0.000000 XCON25 0.000000 17.43750 XCON26 0.000000 20.29750 XBRT11 74.46500 0.000000 XBRT12 0.000000 45.00000 04 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 24 of 25 XBRT21 156.7750 0.000000 XBRT22 243.2250 0.000000 XBRT31 0.000000 62.45000 XBRT32 0.000000 32.45000 XAREIA1 114.8000 0.000000 XAREIA2 166.2500 0.000000 XCIM1 98.40000 0.000000 XCIM2 142.5000 0.000000 Row Slack or Surplus Dual Price Z 235328.2 -1.000000 CAPJAZ1 225.5350 0.000000 CAPJAZ2 0.000000 37.00000 CAPJAZ3 250.0000 0.000000 CAPUS1 272.0000 0.000000 CAPUS2 225.0000 0.000000 CAPCIM 9.100000 0.000000 CAPAREIA 218.9500 0.000000 DEMOBR1 0.000000 -242.2425 DEMOBR2 0.000000 -384.7100 DEMOBR3 0.000000 -336.3675 DEMOBR4 0.000000 -324.9275 DEMOBR5 0.000000 -270.3100 DEMOBR6 0.000000 -333.2300 NECAREIA1 0.000000 121.2500 NECAREIA2 0.000000 113.7500 NECCIM1 0.000000 373.0000 NECCIM2 0.000000 386.5000 NECBRI1 0.000000 104.5000 NECBRI2 0.000000 97.00000 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)