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

03 Programação Linear – Formulação de Modelos © 2020 Prof. Sérgio F. Mayerle 03 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 2 of 20  Problema de transportes  Problema de contratação e treinamento de pessoal  Problema de gestão financeira  Problema de carregamento de veículos 03 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 3 of 20 Problema de transportes Uma empresa produz televisores em 3 fábricas: São Paulo, João Pessoa e Manaus. Os pontos principais de revenda, com as respectivas encomendas mensais, a produção máxima mensal em cada fábrica, e os custos de transportes das fábricas até as revendas, para cada aparelho, são apresentados no quadro abaixo: Rio de Janeiro Salvador Aracajú Maceió Recife Capacidade (unid/mês) São Paulo R$ 1,00 R$ 2,00 R$ 3,00 R$ 3,50 R$ 4,00 10.000 João Pessoa R$ 4,00 R$ 2,00 R$ 1,50 R$ 1,20 R$ 1,00 5.000 Manaus R$ 6,00 R$ 4,00 R$ 3,50 R$ 3,00 R$ 2,00 6.000 Encomendas (unid/mês) 6.000 5.000 2.000 1.000 3.000 Determinar o número de unidades produzidas em cada fábrica e entregues a cada revenda, a fim de minimizar o custo de transporte. 03 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 4 of 20 Variáveis de decisão ijx quantidade mensal produzida na fábrica i e transportada para a revenda em j; z Custo mensal total de transporte. Restrições  restrições de capacidade das fábricas;  restrição de atendimento das encomendas;  não negatividade. Objetivo Minimizar o custo mensal total de transporte. Modelo Matemático 3 5 1 1 5 1 3 1 . : 1,...,3 1,...,5 0 , ij ij i j ij i j ij j i ij Min z c x s a x Q i x D j x i j                 03 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 5 of 20 Entrada LINGO MODEL: [Z] MIN = 1 * X11 + 2 * X12 + 3 * X13 + 3.5 * X14 + 4 * X15 + 4 * X21 + 2 * X22 + 1.5 * X23 + 1.2 * X24 + 1 * X25 + 6 * X31 + 4 * X32 + 3.5 * X33 + 3 * X34 + 2 * X35; [PROD_SP] x11 + X12 + X13 + X14 + X15 < 10000; [PROD_JP] x21 + X22 + X23 + X24 + X25 < 5000; [PROD_MA] x31 + X32 + X33 + X34 + X35 < 6000; [DEM_RJ] X11 + X21 + X31 > 6000; [DEM_SV] X12 + X22 + X32 > 5000; [DEM_AR] X13 + X23 + X33 > 2000; [DEM_MA] X14 + X24 + X34 > 1000; [DEM_RE] X15 + X25 + X35 > 3000; END 03 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 6 of 20 Resultado LINGO Variable Value Reduced Cost X11 6000.000 0.000000 X12 4000.000 0.000000 X13 0.000000 1.500000 X14 0.000000 2.300000 X15 0.000000 3.000000 X21 0.000000 3.000000 X22 1000.000 0.000000 X23 2000.000 0.000000 X24 1000.000 0.000000 X25 1000.000 0.000000 X31 0.000000 4.000000 X32 0.000000 1.000000 X33 0.000000 1.000000 X34 0.000000 0.8000000 X35 2000.000 0.000000 Row Slack or Surplus Dual Price Z 25200.00 -1.000000 PROD_SP 0.000000 1.000000 PROD_JP 0.000000 1.000000 PROD_MA 4000.000 0.000000 DEM_RJ 0.000000 -2.000000 DEM_SV 0.000000 -3.000000 DEM_AR 0.000000 -2.500000 DEM_MA 0.000000 -2.200000 DEM_RE 0.000000 -2.000000 03 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 7 of 20 Problema de contratação e treinamento de pessoal A diretora de pessoal de uma empresa de aviação comercial deve decidir quantas aeromoças deverão ser treinadas e contratadas nos próximos seis meses. As necessidades, expressas pelo número de aeromoças-horas-de-vôo são as seguintes: 80.000 em janeiro; 90.000 em fevereiro; 70.000 em março; 100.000 em abril; 90.000 em maio; e 110.000 em junho. Leva um mês de treinamento antes que uma aeromoça possa ser posta em um vôo regular; assim, uma garota deve ser contratada pelo menos 1 mês antes que ela seja realmente necessária. Cada moça treinada requer requer 100 horas de supervisão de uma aeromoça experiente durante o mês de treinamento, de modo que são disponíveis 100 horas a menos para o serviço de vôo por aeromoças regulares. Cada aeromoça experiente pode trabalhar até 150 horas em um mês, e a empresa dispõe de 605 aeromoças no começo de janeiro. A política da empresa é não demitir ninguém. Porém, no fim de cada mês, aproximadamente 10% das aeromoças pedem demissão para se dedicarem a outras atividades e para se casarem. Uma aeromoça experiente custa a empresa R$ 15.000,00 por mês, enquanto que na fase de treinamento o custo é de somente R$ 9.000,00 (já incluindo os encargos legais). Formule um modelo de programação linear para determinar a política ótima de contratação e treinamento da empresa, e utilize um pacote de programação linear para obter a solução ótima. Interprete a solução encontrada. 03 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 8 of 20 Variáveis de decisão tx Quantidade de aeromoças treinadas no mês t ; ty Quantidade de aeromoças experiente no início do mês t ; Z Custo total de pessoal no período de planejamento. Restrições  Atendimento das necessidades de horas de vôo de cada mês;  Número inicial de aeromoças experientes;  Não negatividade na contratação de aeromoças; Objetivo Minimizar o custo total de pessoal no período de planejamento. Modelo Matemático   6 1 1 1 15000 9000 . : 605 0,9 1,...,5 150 100 1,...,6 0 1,...,6 t t t t t t t t t t Min z y x s a y y y x t y x H t x t                  03 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 9 of 20 Entrada LINGO MODEL: [Z] MIN = 15000 * Y1 + 15000 * Y2 + 15000 * Y3 + 15000 * Y4 + 15000 * Y5 + 15000 * Y6 + 9000 * X1 + 9000 * X2 + 9000 * X3 + 9000 * X4 + 9000 * X5 + 9000 * X6; [N_01] Y1 = 605; [N_02] Y2 = 0.9 * Y1 + X1; [N_03] Y3 = 0.9 * Y2 + X2; [N_04] Y4 = 0.9 * Y3 + X3; [N_05] Y5 = 0.9 * Y4 + X4; [N_06] Y6 = 0.9 * Y5 + X5; [H_01] 150 * Y1 - 100 * X1 > 80000; [H_02] 150 * Y2 - 100 * X2 > 90000; [H_03] 150 * Y3 - 100 * X3 > 70000; [H_04] 150 * Y4 - 100 * X4 > 100000; [H_05] 150 * Y5 - 100 * X5 > 90000; [H_06] 150 * Y6 - 100 * X6 > 110000; END Resultado LINGO Variable Value Reduced Cost Y1 605.0000 0.000000 Y2 618.0957 0.000000 Y3 583.4298 0.000000 Y4 700.2315 0.000000 Y5 680.5556 0.000000 Y6 733.3333 0.000000 X1 73.59574 0.000000 X2 27.14361 0.000000 X3 175.1447 0.000000 X4 50.34722 0.000000 X5 120.8333 0.000000 X6 0.000000 32343.22 Row Slack or Surplus Dual Price Z 0.6283327E+08 -1.000000 N_01 0.000000 -6900.000 N_02 0.000000 9000.000 N_03 0.000000 15625.00 N_04 0.000000 18385.42 N_05 0.000000 19535.59 N_06 0.000000 20014.83 H_01 3390.426 0.000000 H_02 0.000000 -66.25000 H_03 0.000000 -93.85417 H_04 0.000000 -105.3559 H_05 0.000000 -110.1483 H_06 0.000000 -233.4322 03 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 10 of 20 Problema de gestão financeira No início de cada mês, depois de receber o salário do mês anterior, o Sr. McMoney aplica parte do que ganhou (R$ 10.000,00) em investimentos. Excepcionalmente, no dia 1° de janeiro de 2021 ele poderá aplicar uma quantia maior (R$ 30.000,00), que irá obter do resgate de outros investimentos e remunerações extras de final de ano. Ele dispõe de três alternativas: (a) Alternativa 1: aplicação (sempre no início do mês), com prazo mensal, e rendimento de 1,00 % ao mês, já descontados os impostos; (b) Alternativa 2: aplicação (sempre no início do mês), com prazo bimestral, e rendimento de 2,21 % ao bimestre, já descontados os impostos; (c) Alternativa 3: aplicação (sempre no início do mês), com prazo trimestral, e rendimento de 3,64 % ao trimestre, já descontados os impostos. Se for interessante, o Sr. McMoney poderá utilizar um empréstimo bancário mensal com juros de 1,5 % ao mês. Sabe-se que parte do dinheiro aplicado deverá ser utilizado para pagar dívidas contraídas pelo Sr. McMoney durante anos anteriores, conforme mostra o quadro abaixo: Data Pagamento de Dívidas 01/02/2021 R$ 25.000,00 01/05/2021 R$ 31.000,00 01/09/2021 R$ 17.000,00 01/11/2021 R$ 10.000,00 Determine o melhor plano de investimento ao longo do ano de 2008, e responda o que se pede:  construa e apresente o plano de investimentos.  quanto o Sr. McMoney terá e, 1º de janeiro de 2022 ?  o empréstimo bancário é interessante ? Por que ? 03 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 11 of 20 Variáveis de decisão Os empréstimos pagam taxas efetiva de 1,5% ao mês. Considerando as três alternativas de aplicação, tem-se: Alternativa Meses de Aplicação Taxa de Aplicação Taxa de Empréstimo 1 1 1,00% 1,50% 2 2 2,21% 3,02% 3 3 3,64% 4,57% Assim, nenhuma alternativa de aplicação paga a taxa efetiva de um eventual empréstimo, e o fluxo de caixa positivo não exige que se faça empréstimos. Assim, esta variável não será considerada no modelo. Sejam as variáveis: x ,t k Quantia aplicada na alternativa k no início do mês t ; tS Quantia disponível no início do mês t , após o resgate e aplicações. Restrições  Balanço de capital em cada mês;  Não negatividade; Objetivo Maximizar a disponibilidade de capital ao final do período de planejamento. 03 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 12 of 20 Modelo Matemático 12 12,1 11,2 10,3 1 1,1 1,2 1,3 2 1 1,1 2,1 2,2 2,3 3 2 2,1 1,2 3,1 3,2 3,3 4 3 3,1 2,2 1,3 4,1 1.01 1.0221 1.0364 . : 30000 15000 1.01 10000 1.01 1.0221 10000 1.01 1.0221 1.0364 Max z S x x x s a S x x x S S x x x x S S x x x x x S S x x x x                               4,2 4,3 5 4 4,1 3,2 2,3 5,1 5,2 5,3 6 5 5,1 4,2 3,3 6,1 6,2 6,3 7 6 6,1 5,2 4,3 7,1 7,2 7,3 8 7 7, 21000 1.01 1.0221 1.0364 10000 1.01 1.0221 1.0364 10000 1.01 1.0221 1.0364 10000 1.01 x x S S x x x x x x S S x x x x x x S S x x x x x x S S x                              1 6,2 5,3 8,1 8,2 8,3 9 8 8,1 7,2 6,3 9,1 9,2 9,3 10 9 9,1 8,2 7,3 10,1 10,2 10,3 11 10 10,1 9,2 8,3 11, 1.0221 1.0364 7000 1.01 1.0221 1.0364 10000 1.01 1.0221 1.0364 1.01 1.0221 1.0364 x x x x x S S x x x x x x S S x x x x x x S S x x x x                            1 11,2 11,3 12 11 11,1 10,2 9,3 12,1 12,2 12,3 1,1 1,2 1,3 12,1 12,2 12,3 1 12 10000 1.01 1.0221 1.0364 , , ,..., , , 0 ,..., 0 x x S S x x x x x x x x x x x x S S             03 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 13 of 20 Entrada LINGO MODEL: [Z] MAX = S12 + 1.01 * X121 + 1.0221 * X112 + 1.0364 * X103; [M01] S01 = 30000 - X011 - X012 - X013; [M02] S02 = -15000 + S01 + 1.01 * X011 - X021 - X022 - X023; [M03] S03 = 10000 + S02 + 1.01 * X021 + 1.0221 * X012 - X031 - X032 - X033; [M04] S04 = 10000 + S03 + 1.01 * X031 + 1.0221 * X022 + 1.0364 * X013 - X041 - X042 - X043; [M05] S05 = -21000 + S04 + 1.01 * X041 + 1.0221 * X032 + 1.0364 * X023 - X051 - X052 - X053; [M06] S06 = 10000 + S05 + 1.01 * X051 + 1.0221 * X042 + 1.0364 * X033 - X061 - X062 - X063; [M07] S07 = 10000 + S06 + 1.01 * X061 + 1.0221 * X052 + 1.0364 * X043 - X071 - X072 - X073; [M08] S08 = 10000 + S07 + 1.01 * X071 + 1.0221 * X062 + 1.0364 * X053 - X081 - X082 - X083; [M09] S09 = -7000 + S08 + 1.01 * X081 + 1.0221 * X072 + 1.0364 * X063 - X091 - X092 - X093; [M10] S10 = 10000 + S09 + 1.01 * X091 + 1.0221 * X082 + 1.0364 * X073 - X101 - X102 - X103; [M11] S11 = + S10 + 1.01 * X101 + 1.0221 * X092 + 1.0364 * X083 - X111 - X112 - X113; [M12] S12 = 10000 + S11 + 1.01 * X111 + 1.0221 * X102 + 1.0364 * X093 - X121 - X122 - X123; END Resultado LINGO Variable Value Reduced Cost S12 0.000000 0.1000000E-01 X121 10000.00 0.000000 X112 10364.00 0.000000 X103 39903.21 0.000000 S01 0.000000 0.1142321E-01 X011 25148.94 0.000000 X012 0.000000 0.2287718E-02 X013 4851.065 0.000000 S02 0.000000 0.1576148E-01 X021 0.000000 0.4495878E-02 03 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 14 of 20 X022 0.000000 0.4495878E-02 X023 10400.42 0.000000 S03 0.000000 0.1333663E-01 X031 0.000000 0.2204402E-02 X032 10000.00 0.000000 X033 0.000000 0.2204402E-02 S04 0.000000 0.1102201E-01 X041 0.000000 0.000000 X042 0.000000 0.4381356E-02 X043 15027.64 0.000000 S05 0.000000 0.1733489E-01 X051 0.000000 0.6486226E-02 X052 0.000000 0.4337976E-02 X053 0.000000 0.4337976E-02 S06 0.000000 0.1074125E-01 X061 3245.851 0.000000 X062 0.000000 0.2151141E-02 X063 6754.149 0.000000 S07 0.000000 0.1482052E-01 X071 0.000000 0.4227476E-02 X072 0.000000 0.4227476E-02 X073 28852.96 0.000000 S08 0.000000 0.1254044E-01 X081 0.000000 0.2072800E-02 X082 0.000000 0.000000 X083 10000.00 0.000000 S09 0.000000 0.1036400E-01 X091 0.000000 0.000000 X092 0.000000 0.2075590E-02 X093 0.000000 0.000000 S10 0.000000 0.1430000E-01 X101 0.000000 0.4079000E-02 03 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 15 of 20 X102 0.000000 0.4079000E-02 S11 0.000000 0.1210000E-01 X111 0.000000 0.2000000E-02 X113 0.000000 1.022100 X122 0.000000 1.010000 X123 0.000000 1.010000 Row Slack or Surplus Dual Price Z 62048.73 1.000000 M01 0.000000 1.153744 M02 0.000000 1.142321 M03 0.000000 1.126560 M04 0.000000 1.113223 M05 0.000000 1.102201 M06 0.000000 1.084866 M07 0.000000 1.074125 M08 0.000000 1.059304 M09 0.000000 1.046764 M10 0.000000 1.036400 M11 0.000000 1.022100 M12 0.000000 1.010000 03 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 16 of 20 Problema de carregamento de veículos Um navio tem três compartimentos de carga: proa, centro e popa. As capacidades limites são: Compartimento Capacidade (ton) Volume (m3) Proa 20.000 30.000 Centro 30.000 40.000 Popa 15.000 20.000 A empresa de navegação, proprietária do navio pode aceitar toda ou parte das seguintes cargas: Carga Quantidade (ton) Densidade (ton/m3) Receita (R$/ton) A 60.000 0,80 6.000,00 B 40.000 1,10 8.000,00 C 20.000 0,70 5.000,00 Para preservar o equilíbrio do navio, o peso em cada compartimento deve ser proporcional a sua capacidade em toneladas. Formule um modelo para determinar como carregar o navio de modo a maximizar a receita total ? Variáveis de decisão ijx quantidade de produto i alocado no compartimento j, em ton;  fator de proporcionalidade no carregamento do navio; z Receita total com o transporte. Restrições  restrições de capacidade do compartimento, em ton;  restrições de capacidade do compartimento, em m3;  restrição de disponibilidade de cargas;  restrição de proporcionalidade de carga nos compartimentos;  não negatividade. Objetivo Maximizar a receita total com o transporte. 03 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 17 of 20 Modelo Matemático 3 1 3 1 . : 1,...,3 1,...,3 ,..., 0 ,..., 1,...,3 0 1 C i ij i A j C ij j i A C i ij j i A ij i j ij Max z R x s a x P j d x V j x Q i A C x i A C j                             03 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 18 of 20 Entrada LINGO MODEL: [Z] MAX = 6000 * XA1 + 6000 * XA2 + 6000 * XA3 + 8000 * XB1 + 8000 * XB2 + 9000 * XB3 + 5000 * XC1 + 5000 * XC2 + 5000 * XC3; [RP01] XA1 + XB1 + XC1 = 20000 * Alfa; [RP02] XA2 + XB2 + XC2 = 30000 * Alfa; [RP03] XA3 + XB3 + XC3 = 15000 * Alfa; [RV01] 0.80 * XA1 + 1.10 * XB1 + 0.70 * XC1 < 30000; [RV02] 0.80 * XA2 + 1.10 * XB2 + 0.70 * XC2 < 40000; [RV03] 0.80 * XA3 + 1.10 * XB3 + 0.70 * XC3 < 20000; [RQA] XA1 + XA2 + XA3 < 60000; [RQB] XB1 + XB2 + XB3 < 40000; [RQC] XC1 + XC2 + XC3 < 20000; [RALF] Alfa < 1; END 03 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 19 of 20 Resultado LINGO Variable Value Reduced Cost XA1 0.000000 0.000000 XA2 25000.00 0.000000 XA3 0.000000 1000.000 XB1 20000.00 0.000000 XB2 5000.000 0.000000 XB3 15000.00 0.000000 XC1 0.000000 1000.000 XC2 0.000000 1000.000 XC3 0.000000 2000.000 ALFA 1.000000 0.000000 Row Slack or Surplus Dual Price Z 0.4850000E+09 1.000000 RP01 0.000000 6000.000 RP02 0.000000 6000.000 RP03 0.000000 7000.000 RV01 8000.000 0.000000 RV02 14500.00 0.000000 RV03 3500.000 0.000000 RQA 35000.00 0.000000 RQB 0.000000 2000.000 RQC 20000.00 0.000000 RALF 0.000000 0.4050000E+09 03 Programação Linear – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 20 of 20 F I M (© 2020 Prof. Sérgio Mayerle)