Exercício de Formulação - 2023-2

UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM EXERCÍCIOS DE FORMULAÇÃO 1) Um fabricante de brinquedos está planejando produzir dois novos brinquedos (1 e 2) em duas fábricas (A e B). O lucro unitário de cada brinquedo; os custos fixo para adaptar as fábricas e; os tempos de produção dos brinquedos em cada fábrica (em horas-h) são: Brinquedo Lucro (R$) Fábrica Custo da adaptação (R$) Brinquedo 1 (h) Brinquedo 2 (h) 1 12,00 A 45.000,00 R$ 1/52 1/38 2 16,00 B 76.000,00 R$ 1/42 1/23 As fábricas A e B, respectivamente, possuirão 480 e 720 horas de tempo disponíveis para a produção dos brinquedos. O fabricante quer saber quais fábricas adaptar, qual dos novos brinquedos produzir, onde e quantos de cada (se houver) devem ser produzidos para maximizar o lucro total. Variáveis : xij : qte do brinquedo i produzido na fábrica j, i ∈ {1,2}, j ∈ {A,B}, xij ≥ 0 yj: adaptar ou não a fábrica j, j ∈ {A,B}, yj ∈ {0,1} Equações Função Objetivo: maxZ=12(x1A + x1B) + 16(x2A + x2B) – (45.000yA + 76.000yB) Restrições: (1/52)x1A + (1/38)x2A ≤ 480 (1/42)x1B + (1/23)x2B ≤ 720 x1A + x2A ≤ MyA x1B + x2B ≤ MyB 2) Seja a função objetivo não linear do gráfico abaixo que deve ser maximizada restrita ao conjunto de restrições Ax ≤ b. Linearize a função f(x) usando 2 segmentos. Escreva a função objetivo linearizada e as restrições que deverão ser adicionadas ao conjunto original de restrições. Explique as restrições adicionadas considerando que a solução ótima do pl misto é x = 4/5. 𝑓 𝑥 ( ) = { 3 2 𝑥, 0≤𝑥≤ 1 2 1 2 𝑥 + 1 2 , 1 2 ≤𝑥≤1 Novas Variáveis: λ1, λ2, λ3: usado para gerar as combinações lineares convexas λ1, λ1, λ3 ≥ 0 yj: se usar o segmento j, j ∈ {1,2}, yj ∈ {0,1} Substituir a parte não linear na função objetivo (f(x)) por f(x) = λ1f(0) + λ2f(1/2) + λ3f(1), ou seja, f(x) = (3/4)λ2 + λ3 Acrescentar nas restrições x = (1/2)λ2 + λ3 1 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM λ1 ≤ y1 λ2 ≤ y1 + y2 λ3 ≤ y2 λ1 + λ2 + λ3 = 1 y1 + y2 = 1 Se x = 4/5 x = 4/5 cai no segundo segmento, então: 4/5 = (1/2)λ2 + λ3 f(4/5) = (3/4)λ2 + λ3 y1 = 0, y2 = 1 λ1 = 0 λ2 ≤ 1 λ3 ≤ 1 λ2 + λ3 = 1 3) Seja um problema de instalar 3 facilidades, dentre 10 possíveis. Estas 3 facilidades irão estocar um produto p(i) que será disponibilizado por 100 produtores. Para instalar cada facilidade o custo fixo é c(j), j=1,...,10 e a capacidade de estocagem é E(j). O custo de locomoção entre a facilidade j e o produtor i (ida e volta) é k(i,j), j=1,...,10, i=1,...,100. Formule um programa linear que indica quais facilidades deverão ser instaladas e quais produtores deverão ser atendidos pelas mesmas a um custo mínimo. Variáveis: yj: instalar ou não a facilidade j, j = 1,2,...,10, yj ∈ {0,1} xij: quantidade a ser transportada do produtor i para a facilidade j, xij ≥ 0 (na minha formulação estou considerando que a quantidade do produtor i pi a ser transportada pode ser fracionada) Equações F.Obj.: (minimize) 𝑍 = 𝑗=1 10 ∑ 𝑐𝑗𝑦𝑗 + 𝑗=1 10 ∑ 𝑖=1 100 ∑ 𝑘𝑖𝑗𝑥𝑖𝑗 Restrições 𝑖=𝑗 10 ∑ 𝑦𝑗 = 3 𝑥𝑖𝑗≤𝑀𝑦𝑗, 𝑗 = 1, …, 10, 𝑖 = 1, …, 100 𝑗=1 10 ∑ 𝑥𝑖𝑗 = 𝑝𝑖, 𝑖 = 1, 2, ..., 100 𝑗=1 100 ∑ 𝑥𝑖𝑗 ≤ 𝐸𝑗𝑦𝑗, 𝑗 = 1, 2, ..., 10 4) Sejam n itens com pesos w(i), i=1,...,n. Sejam m containers com limitações de carga W(j), j=1,...,m e custo fixo de uso de c(j). Selecione o menor número de containers a um custo mínimo para acondicionar os n itens respeitando a capacidade de peso. Os itens são indivisíveis. Variáveis: yj: usar ou não o container j, j = 1,2,...,m, yj ∈ {0,1} 2 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM xij: se o item i é acondicionado no container j, xij ∈ {0,1} Equações F.Obj.: (minimize) 𝑍 = 𝑗=1 𝑚 ∑ 𝑐𝑗𝑦𝑗 Restrições 𝑖=1 𝑛 ∑ 𝑤𝑖𝑥𝑖𝑗 ≤ 𝑊𝑗𝑦𝑗, 𝑗 = 1, …, 𝑚 𝑖=1 𝑚 ∑ 𝑥𝑖𝑗 = 1, 𝑖 = 1, …, 𝑛 𝑥𝑖𝑗 ≤ 𝑦𝑗, 𝑗 = 1, …, 𝑚 5) Um banco está aberto das 9:00 às 17:00. Durante cada hora do dia, o número de escriturários necessário é o seguinte: Período de tempo Número de escriturários 09:00 – 10:00 4 10:00 – 11:00 3 11:00 – 12:00 4 12:00 – 13:00 6 13:00 – 14:00 5 14:00 – 15:00 6 15:00 – 16:00 8 16:00 – 17:00 8 O banco pode contratar escriturários em período integral e em meio período. Os escriturários em tempo integral trabalham das 9:00 às 17:00, exceto durante a hora de almoço, que é ou das 12:00 às 13:00 ou das 13:00 às 14:00. O banco decide em qual horário cada escriturário faz sua pausa para o almoço. Estes escriturários recebem 20 USD por hora e recebem pagamento pelo intervalo de almoço. Os escriturários de meio período trabalham ininterruptamente por três horas e o banco especifica a hora de início de cada um deles. Estes escriturários recebem 15 USD por hora. Não podem ser contratados mais de cinco escriturários em meio período. Use programação linear/inteira para modelar o problema de encontrar uma política de contratação dos escriturários a um custo mínimo. Variáveis: xI1: escriturários em tempo integral que almoçam das 12:00 às 13:00 xI2: escriturários em tempo integral que almoçam das 13:00 às 14:00 xPi: escriturários em tempo parcial que ingressam no trabalho no horário i, i ∈ I, onde I = {9, 10, 11, 12, 13, 14} Equações F.Obj.: (minimize) 𝑍 = 8 × 20 × 𝑥𝐼1 + 𝑥𝐼2 ( ) + 𝑖=1 𝑛 ∑ 3 × 15 × 𝑥𝑃𝑖 Restrições xI1 + xI2 + xP9 ≥ 4 xI1 + xI2 + xP9 + xP10 ≥ 3 3 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM xI1 + xI2 + xP9 + xP10+ xP11 ≥ 4 xI2 + xP10+ xP11+ xP12 ≥ 6 xI1 + xP11+ xP12+ xP13 ≥ 5 xI1 + xI2 + xP12+ xP13+ xP14 ≥ 6 xI1 + xI2 + xP13+ xP14 ≥ 8 xI1 + xI2 + xP14 ≥ 8 𝑖∈𝐼 ∑ 𝑥𝑃𝑖 ≤5 + 𝑥𝐼1, 𝑥𝐼2, 𝑥𝑃𝑖 ∈ 𝑍 6) Suponha que estamos modelando um problema de localização de instalações que envolve a decisão sobre o tamanho de um armazém para construir. As opções de tamanhos e custos associados são mostrados abaixo: Tamanho 10 20 40 60 80 Custo 100 180 320 450 600 Suponha que temos outras restrições associadas a esta decisão. Como devo proceder para adicionar a informação acima (tamanho e custo) ao conjunto de restrições originais e a função objetivo original. Variáveis: yi∈{0,1} j=1,2,...,5 – definir o tamanho do armazém x - tamanho do armazém Equações F.Obj.: Adicionar na função objetivo f(x) original Z = f(x) + custo(x) Z = f(x) + 100y1 + 180y2 + 320y3 + 450y4 + 600y5 Restrições x = 10y1 + 20y2 + 40y3 + 60y4 + 80y5; y1 + y2 + y3 + y4 + y5 = 1 7) Temos a possibilidade de produzir três novos produtos. No máximo dois devem ser escolhidos para serem produzido. Temos duas plantas de produção. Apenas uma é escolhida para produzir os novos produtos e os tempos de produção são diferentes. Formular o PLI associado à decisão de qual planta escolher e de quanto de cada produto produzir. Variáveis: yj – escolher ou não a planta j, yj {0,1}, j=1,2 ∈ wi – produzir ou não produzir o produto i, wi {0,1}, i=1,2,3 ∈ xij – quanto produzir do produto i na planta j, i=1,2,3, j=1,2, xij 0 ≥ Equações F.Obj.: (maximize) Z =57(x11 + x12) + 7(x21 + x22) + 3(x31 + x32) 4 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM Restrições y1 + y2 = 1 w1 + w2 + w3 2 ≤ x11 + x12 7w1 ≤ x21 + x22 5w2 ≤ x31 + x32 9w2 ≤ 3x11 + 4x21 + 2x31 30 ≤ 4x11 + 6x21 + 2x31 40 ≤ 8) O O treinador Joaquim está tentando escolher uma escalação inicial para o time de basquete. A equipe é composta de sete jogadores que foram avaliados (numa escala de 1=ruim a 3=excelente) de acordo com suas habilidades de Manuseio de Bola, Arremesso, Rebote e Defesa. As Posições em que cada jogador pode jogar e as habilidades do jogador estão listadas na tabela abaixo. A escalação inicial de cinco jogadores deve cumprir os seguintes requisitos. (a) Em relação à Posição: pelo menos 2 membros do time devem ser capazes de jogar na retaguarda-G, pelo menos 2 membros devem ser capazes de jogar no ataque-A, e pelo menos 1 membro deve ser capaz de jogar no centro-C. (b) Em relação às habilidades: para cada habilidade (Manuseio de Bola, Arremesso e Rebote) a média deve ser de pelo menos 2. (c) Se o jogador 3 começar, então o jogador 6 não pode começar. (d) Se o jogador 1 começar, então os jogadores 4 e 5 devem começar ambos. (e) O jogador 2 ou o jogador 3 devem começar. Dadas as restrições, o treinador Joaquim quer maximizar a capacidade defensiva total do time inicial. Formule um problema de programação inteira que o ajude a escolher o time inicial formado por 5 jogadores. Variáveis: X1G, X2C, X3G, X3A, X4A, X4C, X5G, X5A, X6A, X6C, X7G, X7A {0,1} ∈ Equações F.Obj.: (maximize) Z = 3X1G+2X2C+3(X3G+X3A)+1(X4A+X4C)+3(X5G+X5A)+3(X6A+X6C)+1(X7G+X7A) Restrições (X3G + X3A) 1, (X4A + X4C) 1, (X5G + X5A) 1, (X6A + X6C) 1, (X7G + X7A) 1 ≤ ≤ ≤ ≤ ≤ X1G + X2C +(X3G + X3A) +(X4A + X4C)+(X5G + X5A) +(X6A + X6C) +(X7G + X7A) = 5 X1G + X3G + X5G + X7G 2 ≥ X3A + X4A + X5A + X6A + X7A 2 ≥ X2C + X4C + X6C 1 ≥ 3X1G + 2X2C + 2(X3G + X3A) + 1(X4A + X4C) + 3(X5G + X5A) + 3(X6A + X6C) + 2(X7G + X7A) 2x5 ≥ 3X1G + 1X2C + 3(X3G + X3A) + 3(X4A + X4C) + 3(X5G + X5A) + 1(X6A + X6C) + 2(X7G + X7A) 2x5 ≥ 5 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 1X1G + 3X2C + 2(X3G + X3A) + 3(X4A + X4C) + 3(X5G + X5A) + 2(X6A + X6C) + 1(X7G + X7A) 2x5 ≥ (X3G + X3A) + (X6A + X6C) 1 (restrição c) ≤ (X4A + X4C) X1G, (X5G + X5A) X1G ou (X4A + X4C) + (X5G + X5A) 2X1G ≥ ≥ ≥ (restrição d) X2C + (X3G + X3A) = 1 (restrição e) 9) Uma cidade está revendo a localização de seus quartéis de bombeiros. A cidade é composta por um número de bairros, conforme ilustrado na Figura. Da Figura, a matriz de vizinhança é: Um quartel de bombeiros pode ser instalado em qualquer bairro. Ele é capaz de lidar com os incêndios na sua vizinhança. Não tem problema se algum bairro for atendido por mais de um quartel. O objetivo é minimizar o número de quartéis de bombeiros a serem instalados. Faça apenas formulação. Variáveis: yj – instalar ou não o quartel no bairro j, yj ∈ {0,1}, j=1,2,...,11 Equações F.Obj.: (minimize) Z = y1 + y2 + y3 + y4 + y5 + y6 + y7 + y8 + y9 + y10 + y11 Restrições y1 + y2 + y3 + y4 1 ≥ y1 + y2 + y3 + y5 1 ≥ y1 + y2 + y3 + y4 + y5 + y6 1 ≥ y1 + y3 + y4 + y6 + y7 x1 + x3 + x4 + x6 + x7 1 ≥ y2 + y3 + y5 + y6 + y8 + y9 1 ≥ y3 + y4 + y5 + y6 + y7 + y8 1 ≥ y4 + y6 + y7 + y8 1 ≥ 6 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM y5 + y6 + y7 + y8 + y9 + y10 1 ≥ y5 + y8 + y9 + y10 + y11 1 ≥ y8 + y9 + y10 + y11 1 ≥ y9 + y10 + y11 1 ≥ 10) A Universidade UNI está planejando a construção de estacionamentos para aumentar o número de vagas para carros. Existem M possíveis locais para estacionamentos, cada um com um valor específico de custo fixo de manutenção fi, e um número projetado de vagas vi. Os alunos frequentam aulas em N blocos diferentes. A distância do estacionamento i ao bloco j é dij. A previsão mostra que o número de alunos que frequentam as aulas no bloco j a cada dia é de cerca de aj. Supondo que uma unidade de distância de caminhada custe R$ 0,50, ajude a universidade a decidir quais estacionamentos construir (a situação de estacionamento ideal) de forma que o custo total, incluindo caminhada e manutenção, seja minimizado. Variáveis: considere i=1,...,M (estacionamento i), j=1,...,N (bloco j) yi∈{0,1} construir ou não o estacionamento no local i xij∈Z+ quantidade da alunos do bloco j alocados no estacionamento do local i Equações F.Obj.: (minimize) Z = Σifixi + 0,5×ΣiΣjdij×xij Restrições Σixij = aj, j=1,...,N todos os alunos do bloco j devem ser vinculados a 1 estacionamento Σjxij ≤ viyi – vincular ou não alunos do bloco i ao estacionamento j 11) Uma operadora de telefone celular oferece opções de vários planos diferentes para os clientes. O plano A cobra R$ 0,10 por minuto de uso e não tem mensalidade. O plano B tem uma taxa mensal de R$ 30,00 e uma taxa extra de R$ 0,40 por minuto se o uso exceder 400 minutos. O plano C tem uma taxa mensal de R$ 40,00 e uma taxa extra de R$ 0,60 por minuto se o uso exceder 600 minutos. Encontre o plano de custo mínimo para o Luiz se seu uso mensal for de pelo menos 410 minutos. Formule como um PLI. Variáveis: considere i∈{A,B,C1,C2} (plano i) yi∈{0,1} usar ou não usar o plano i (o plano C foi subdividido em 2 planos devido o uso mínimo de 410min) xi∈Z+ quantidade de minutos usados por mês no plano i Equações F.Obj.: (minimize) Z = 0,1xA + 30yB + 0,4(xB – 400yB) + 40yC1 + 40yC2 + 0,6(xC2 – 600yC2) Restrições xi ≥ 410yi, a qte mínima de minuntos usados no plano i é de 410min Σiyi = 1, somente um plano é escolhido xA ≤ MyA xB ≤ MyB xC1 ≤ 600yC1 xC2 ≥ 600YC2 12) Suponha que Carlos fabrica 3 produtos (A, B e C). Ele faz os produtos a partir de 3 insumos (I, II e III). Carlos é incapaz de obter qualquer um dos produtos sem um custo fixo inicial caro. Os dados constam na tabela. 7 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM Produto A Produto B Produto C Disponibilidade Insumo I 1 3 4 99 Insumo II 1 1 1 33 Insumo III 8 4 1 200 Lucro R$ 50,00 R$ 28,00 R$ 18,00 Custo fixo R$ 400,00 R$ 300,00 R$ 200,00 Formule um PLI (talvez misto) para decidir quanto fabricar de cada produto maximizando o lucro total. Variáveis: considere i∈{1, 2, 3} (produto i) yi∈{0,1} produzir ou não o produto i xi∈Z+ quantidade a ser produzida do produto i Equações F.Obj.: (maximize) Z = 50x1 + 20x2 + 18x3 – (400y1 + 300y2 + 200y3) Restrições x1 + 3x2 + 4x3 ≤ 99 x1 + x2 + x3 ≤ 33 8x1 + 4x2 + x3 ≤ 200 xi ≥ Myi 13) Duas lanchonetes podem produzir risoles e pães de queijo para vender durante a feira de profissões da Universidade UNI, mas a PROGRAD só pode contratar uma única lanchonete. A receita é de R$ 2,00 para cada risoles e R$ 0,50 para cada pão de queijo. A lanchonete A gasta 3 minutos produzindo cada risoles e 30 segundos por pão de queijo, e tem um total de 3h de produção. A lanchonete B gasta 2 minutos produzindo cada risoles e 45 segundos por pão de queijo, e tem um total de 2h de produção. Formule um PLI que auxilia a escolher a lanchonete que atuará na feira e terá a maior receita. Variáveis: considere i∈{A, B} (lanchonete i) Ri∈Z+ quantidade de risoles a ser produzida na lanchonete i Pi∈Z+ quantidade de pães a ser produzida na lanchonete i yi∈{0,1} escolher ou não a lanchonete i Equações F.Obj.: (maximize) Z = 2(RA + RB) + 0,5(PA1 + PB) Restrições 180RA + 30PA ≤ 10.800yA 120RA + 45PA ≤ 7.200yB yA + yB = 1 14) O dono de uma grande empresa deseja construir M=4 novas montadoras em diferentes áreas. Todas as montadoras produzirão o mesmo produto. O proprietário tem C=10 clientes. O cliente exige di unidades do produto. O custo operacional da montadora j é oj ≥ 0 e o número máximo de unidades que ela pode produzir é kj. O custo de entrega de 1 unidade da montadora i para o cliente j é cij. Onde deve construir suas novas montadoras para minimizar o custo de entrega? Formule o problema como um PLI. Variáveis: considere i∈{1, 2, 3, 4} (montadora i), j∈{1, 2, ..., 10} (cliente j) xij∈Z+ quantidade do produto produzido na montadora i para o cliente j yi∈{0,1} construir ou não a montadora i Equações F.Obj.: (minimize) 8 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM Z = Σioiyi + ΣiΣjcijxij Restrições Σjxij ≤ kiyi, i=1,...,4 Σixij ≥ dj, j=1,...,10 15) Formule o seguinte problema como um problema de programação linear inteira. Uma empresa contrata funcionários de um grupo de 60 pessoas. Os funcionários são contratados diariamente. O grupo contém 20 pessoas experientes. Uma pessoa experiente pode fazer duas vezes mais trabalho do que uma pessoa inexperiente no mesmo tempo. A empresa tem N projetos para os quais precisa recrutar pessoas. Nos próximos D dias, os funcionários terão que ser divididos entre os projetos. Para o projeto n (n = 1, ..., N) tnd é a quantidade de trabalho necessário no dia d (d = 1, ..., D); um funcionário sem experiência pode realizar uma unidade de trabalho por dia. Se um funcionário é contratado em um determinado dia, ele trabalha no mesmo projeto o dia todo. O custo de contratação de um funcionário normal é de c1 por dia e o custo de contratação de um funcionário experiente é de c2 por dia. Finalmente, para cada dia, o número mínimo de funcionários experientes que precisam trabalhar no projeto n é igual a En. A empresa quer minimizar o custo de contratação de funcionários. Variáveis: considere n∈{1,2,3,...,N} (projeto n), d∈{1,2,3,...,D} (dia d) Exnd∈Z+ quantidade de pessoas experientes que atuarão no projeto n no dia d Innd∈Z+ quantidade de pessoas inexperientes que atuarão no projeto n no dia d Equações F.Obj.: (minimize) Z = ΣnΣd(c1×Exnd + c2×Innd) Restrições Σn Exnd ≤ 20, d=1,...,D Σn Ixnd ≤ 40, d=1,...,D Exnd ≥ En, d=1,...,D, n=1,...,N 2Exnd + Ixnd ≥ Tn, d=1,...,D, n=1,...,N 16) Um líder deve determinar a melhor seleção de K entre 9 possíveis projetos. Sejam os projetos p1, p2, ..., p9 e os lucros esperados associados a cada um como l1, l2, ..., l9: a) se o projeto p3 for selecionado, então o projeto p6 também deve ser selecionado; b) selecionar p1 e p5 impedirá a seleção de p9; c) selecionar os projetos p3 ou p4 impedirá que seja selecionado p8. Formule isso como um PLI. Variáveis: considere i∈{1, 2, ..., 9} (projeto i) yi∈{0,1} escolher ou não o projeto i Equações F.Obj.: (maximize) Z = Σiliyi Restrições Σiyi = K y3 – y6 ≤ 0 y1 + y5 + y9 ≤ 2 y3 + y4 +2y8 ≤ 2 17) Devemos escolher M entre 9 projetos p1, p2, ..., p9 cujos custos associados são c1, c2, ..., c9 respeitando as seguintes regras: a) se o projeto p3 for selecionado, então o projeto p6 não pode ser selecionado; b) selecionar p1 ou p8 implica na seleção de p5; c) selecionar o projeto p3 então 9 UNIVERSIDADE FEDERAL DO PARANA — DEPARTAMENTO DE ENGENHARIA DE PRODUGAO TECNOLOGIA DA DECISAO II - PRoF. VotmiR EuGénio WILHELM p4 deve ser selecionado. Sejam as variaveis binarias yi, i=1,...,9 referente a selegao ou nao do projeto i. a. Formule esta situagao como um programa linear inteiro-pli tal que o custo seja o menor possivel. Variaveis: considere i€ {1, 2, ..., 9} (projeto |) y,= {0,1} escolher ou nao o projeto i Equacées F.Obj.: (minimize) Z= IY; Restrigdes ay,=M ¥3+YeS1 ¥1-Y5<0 Ys -Y5 <0 V3 SY b. Suponha que foi incluida a restrigao y4 + y7 < y9 +1. Interprete esta restrigao. Se os projetos p4 e p7 forem selecionados, entao p9 deve ser selecionado. 18) A SO MOTORES monta motores a diesel para equipamentos de construgdo. Nos proximos 4 trimestres, a empresa espera despachar 40, 20, 60 e 15 unidades, respectivamente, mas nao mais do que 50 podem ser montados em qualquer trimestre. Ha um custo fixo de R$ 2.000,00 a cada trimestre que corresponde a configuragao da linha para produgaéo, mais R$ 200,00 por unidade montada. Os motores podem ser retidos em estoque na fabrica por R$ 100,00 por unidade por més. A SO MOTORES busca um plano de produgao de custo total minimo para os quatro trimestres, supondo que nao haja estoque inicial ou final. Formule um PLI associado. Varidveis: considere i€ {1,2,3,4} (trimestre i) x,=Z*> quantidade de motores produzidos no trimestre i w;€ Z* quantidade de motores estocados do trimestre (i-1) para o trimestre i y,= {0,1} produzir ou nao motores no trimestre i Equacdes F.Obj.: (minimize) Z = 2(2000y; + 200x; + 100w)) Restrigdes x, < 50y,; X,=40+w, X3+ WwW. = 60+ w; X,+w,= 15 19) Considere o problema de um fabricante de ragdes para animais que produz misturas de ragdoes para gado leiteiro. No caso as misturas contém: i) dois ingredientes ativos; e ii) um complemento para gerar volume. Um kg de mistura desta ragado deve conter uma quantidade minima (em gramas) de cada um dos quatro nutrientes (A, B, C, D) conforme: Nutriente (1 A|B;C{D Quantidade minima | 90 | 50 | 20 | 2 O kg de cada ingrediente (I e Il) possui as seguintes quantidades de nutrientes (em gramas/kg) e respectivos custos: Ingrediente | Ingrediente | I | Il 10 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM A 100 200 B 80 150 C 40 20 D 10 – Custo/k g 40 60 Suponha que temos as condições adicionais: i) se usarmos qualquer quantidade do ingrediente II, incorreremos em um custo fixo de 15; ii) não precisamos satisfazer as quatro restrições de nutrientes, mas precisamos satisfazer pelo menos três delas. Qual deve ser a quantidade de ingredientes e complemento em 1 kg de alimento misturar? Só formule o PLI. Variáveis: considere j∈{A,B,C,D} (nutriente j) iI∈Z+ quantidade do ingridiente I iII∈Z+ quantidade do ingridiente II iIII∈Z+ quantidade do ingridiente complementar yj∈{0,1} usar ou não o nutriente j wII∈{0,1} usar ou não o ingridiente II Equações F.Obj.: (minimize) Z = 40iI + 60iII + 15wII Restrições 100iI + 200iII ≥ 90yA 80iI + 150iII ≥ 50yB 40iI + 20iII ≥ 20yC 10iI ≥ 2yD yA + yB + yC + yD ≥ 3 iII ≤ MwII iI + iII + iIII = 1 20) Uma empresa deseja determinar o plano de investimentos para o próximo ano, e dispõe dos seguintes projetos: Possibilidade de Investimento Valor Presente Capital Líquido (R$) Requerido (R$) I. Construir um novo depósito 7.000.000,00 5.000.000,00 II. Recuperar o depósito antigo 4.500.000,00 3.000.000,00 III.Automatizar o depósito novo 5.500.000,00 4.200.000,00 IV.Comprar a fornecedora do produto A 12.000.000,00 9.300.000,00 V. Construir uma fábrica para produzir A 9.500.000,00 7.100.000,00 VI.Reformar o escritório da empresa 1.500.000,00 900.000,00 Entre os projetos acima apresentados, as alternativas I e II são mutuamente excludentes, assim como IV e V. O projeto III, por sua vez, depende da realização do projeto I. A empresa dispõe de R$ 20.000.000,00 para investir nestes projetos. Formule um modelo de programação inteira binária para determinação do portfólio ótimo de investimento (maximizando o valor presente). Variáveis: considere i∈{I, II, ..., VI} (projeto i) yi∈{0,1} investir ou não no projeto i Equações F.Obj.: (maximize) 11 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM Z = 7000yI + 4500yII + 5500yIII + 12000yIV + 9500yV + 1500yVI (×1.000) Restrições yI + yII ≤ 1 yIV + yV ≤ 1 yIII - yI ≤ 0 5000yI + 3000yII + 4200yIII + 9300yIV + 7100yV + 900yVI ≤ 20000 (×1.000) 21) Uma fábrica utiliza dois tipos de insumos: i) A, a um curso unitário CA e com uma quantidade máxima disponível DA; ii) B, a um custo unitário CB e com uma quantidade máxima disponível DB. Estes insumos podem ser processados pelos processos I, II e III a um custo operacional nulo. Serão produzidos os produtos α, β e γ, que alcançaram preços de venda Pα, Pβ e Pγ, respectivamente (preços unitários). a) uma unidade de A processada em I produz, simultaneamente, 5 α e 1γ; b) uma unidade de A junto com duas unidades de B conjuntamente processadas em II produz, simultaneamente 3α, 9β e 8γ; c) uma unidade de B processada em III produz simultaneamente 1α, 4β e 1γ. Formule o pli de modo a maximizar o lucro. Variáveis: considere i∈{I, II, III} (processo i) xi∈Z quantidade de vezes que o processo i for utilizado Equações F.Obj.: (maximize) Z = (5Pα + Pγ - cA)xI + (3Pα + 9Pβ + 8Pγ - cA - 2cB)xII + (Pα + 4Pβ + Pγ - cB)xIII Restrições xI + xII ≤ DA 2xII + xIII ≤ DB 22) Dutos tubulares ligam duas fábricas de tratamento de água e duas cidades. A produção diária da primeira fábrica é de 40 milhões de litros de água e da segunda fábrica é de 50 milhões de litros de água. A necessidade diária da cidade 1 é 30 milhões de litros e da cidade 2 é 60 milhões de litros. Cada fábrica tem uma ligação direta com a sua cidade respectiva. A água produzida nas fábricas 1 e 2 pode também ser transportada para uma estação de bombas especial que está ligada à cidade 2. Adicionalmente, a fábrica 1 está ligada por um duto unidirecional com a fábrica 2 e a cidade 1 está ligada por uma conduta unidirecional com a cidade 2. Os custos (em R$) de transporte de 1 milhão de litros de água por cada ligação existente e as capacidades (limites superiores) dos tubos (em milhões de litros) estão representados na tabela seguinte: Fábrica 1 Fábrica 2 Cidade 1 Cidade 2 Estação custo limite custo limite custo limite custo limite custo limite Fábrica 1 --- --- 3 ∞ 5 35 --- --- 7 10 Fábrica 2 --- --- --- --- --- --- 1 30 2 60 Cidade 1 --- --- --- --- --- --- 4 ∞ --- --- Cidade 2 --- --- --- --- --- --- --- --- --- --- Est. de bombas --- --- --- --- --- --- 8 ∞ --- --- Represente matematicamente (via um pl) o problema de minimização de custos. Temos 7 dutos. Sejam as seguintes variáveis associadas ao fluxo entre cada duto Duto Origem do duto Destino do duto Capacidade do duto Variável 1 Fábrica 1 Cidade 1 35 x1 2 Fábrica 1 Estação de bombas 10 x2 3 Fábrica 1 Fábrica 2 Infinito x3 4 Fábrica 2 Cidade 2 30 x4 5 Fábrica 2 Estação de bombas 60 x5 6 Cidade 1 Cidade 2 Infinito x6 7 Estação de Bombas Cidade 2 infinito x7 Variáveis: considere i∈{1,2,...,7} (duto i) 12 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM xi∈Z quantidade de água que flui pelo duto i Equações F.Obj.: (minimize) Z = 5x1 + 7x2 + 3x3 + 1x4 + 2x5 + 4x6 + 8x7 Restrições x1 ≤ 35; x2 ≤ 10; x4 ≤ 30; x5 ≤ 60 x1 + x2 + x3 ≤ 40 x4 + x5 ≤ 50 x1 ≥ 30 x4 + x6 + x7 ≥ 60 23) João e Maria pretendem dividir entre eles as tarefas domésticas de modo que cada um tenha duas tarefas e o tempo total que gastam nestas atividades seja mínimo. O tempo que cada um deles gasta desempenhando cada tarefa é dado na tabela: Horas por semana Compras Cozinhar Louça Roupa João 3,1 9,1 3,2 4,9 Maria 4,7 6,1 4,4 2,9 Formule um modelo de programação linear para este problema. Variáveis: considere i∈{C-Compras, Z-Cozinha, L-Louca, R-Roupa} (tarefa doméstica i) xJi∈Z quantidade de tempo gasto por João na atividade i xMi∈Z quantidade de tempo gasto por Maria na atividade i Equações F.Obj.: (minimize) Z = (3,1xJc + 9,1xJZ + 3,2xJL + 4,9xJR) + (4,7xMC + 6,1xMZ + 4,4xML + 2,9xMR) Restrições xJc + xMC = 1; xJz + xMz = 1; xjL + xML = 1; xjR + xMR = 1 xJc +xJZ + xJL + xJR = 2 xMC + xMZ + xML + xMR = 2 24) Uma companhia pode realizar 7 grandes investimentos. O lucro de longo prazo estimado (VPL) e o capital requerido são dados na tabela: 1 2 3 4 5 6 7 VPL estimado 15 8 12 17 5 11 8 Capital requerido 40 29 33 49 18 31 22 A empresa dispõe de 110 unidades monetárias para investir. As oportunidades de investimento 1 e 2 são mutuamente exclusivas, bem como as 3 e 4. Além disso, nem 3 nem 4 podem ser realizadas sem que ou 1 ou 2 também o sejam. Formule um modelo de programação inteira binária, considerando como objetivo selecionar a combinação de investimentos que maximize o VPL. Variáveis: considere i∈{1,2,...,7} (oportunidade de investimento i) yi∈{0,1} escolher ou não o investimento i Equações F.Obj.: (maximize) Z = 15y1 + 8y2 + 12y3 + 17y4 + 5y5 + 11y6 + 8y7 Restrições 40y1 + 29y2 + 33y3 + 49y4 + 18y5 + 31y6 + 22y7 ≤ 110 y1 + y2 ≤ 1 y3+ y4 ≤ 1 y3 ≤ y1 + y2 y4 ≤ y1 + y2 13 UNIVERSIDADE FEDERAL DO PARANA — DEPARTAMENTO DE ENGENHARIA DE PRODUGAO TECNOLOGIA DA DECISAO II - PRoF. VotmiR EuGénio WILHELM 25) Uma companhia aérea efetua 5 voos {1, 2, 3, 4, 5}, dispondo para isso de 6 tripulagoes. A tabela a seguir mostra quais os voos que cada tripulagao pode realizar bem como o custo de fazer voar essa tripulagao. Custo 2 3 3 3 2 2 Observacoes: i) As tripulagdes podem viajar como passageiros; ii) Em cada aviao deve haver apenas uma tripulagao trabalhando. Formule um modelo de programagao inteira para o problema de cobrir todos os voos com as tripulagoes disponiveis de modo a minimizar o custo total. Matriz de incidéncia Tripulacao 1 |A B C D E F Voo 1 1 1 1 1 Voo 2 1 1 Voo 3 1 1 Voo 4 1 $1 1 Voo 5 1 #171#71#é=1 Problema de cobertura Varidveis: considere i€ {A,B,C,D,E,F} (tripulagao i) y,= {0,1} escolher a tripulagao i Equacgées F.Obj.: (minimize) Z = 2X, + 3Xg + 3X + 3Xp + 2X + 2p Restrigdes Xa +Xgt+Xpt+xX-27 Xa +Xo271 Xp +Xp271 Xp tXot+X-27 Xo tKXp t+ Xe +X-27 26) A Grafitex imprime camisetas com desenhos. Para cada um de seus 4 contratos pendentes, a tabela a seguir mostra: i) o numero de dias de trabalho necessarios; ii) o dia mais cedo em que o trabalho pode comegar; e iii) o dia em que o pedido é devido (quando o pedido precisa ser entregue — data do vencimento do contrato): Po CCCC“‘(CC Goontrato 4 | Contrato 2 | Contrato 3 | Contrato 4 | | Tempo detrabalho(emdias) | 10, | = 3 | 16 S| 8 | Data de inicio mais cedo possivel|_ 0 | — 20 | 4 | 12 |Datadevencimentodocontrato | 12 | 30 | 20 | 21 | A empresa quer um cronograma que minimize a soma dos atrasos (atrasos) das conclusdes dos contratos. Defina: Di, o dia de inicio para execugao do trabalho do contrato i; Ai, o atraso da conclusao do trabalho do contrato i. Defina quaisquer variaveis adicionais que vocé deseja usar e formule um pli. Varidveis: considere i€ {1,2,3,4} (contrato i) D,€=Z* dia de inicio da execucao da impressao das camisetas do contrato i A;=Z* dias de atraso na entrega em relagao ao vencimento do contrato i Equacgoées F.Obj.: (minimize) Z=A,+A,+Azt+Ay, 14 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM Restrições D1 ≥ 0; D2 ≥ 20; D3 ≥ 1; D4 ≥ 12 A1 = D1 + 10 - 12 A2 = D2 + 3 - 30 A3 = D3 + 16 - 20 A4 = D4 + 8 - 21 27) Uma empresa produtora de alimentos está considerando a construção de cinco novas fábricas nos próximos 4 anos em terras de sua propriedade. A empresa poderia iniciar e terminar a construção de qualquer uma das plantas em qualquer um dos anos, mas os custos de construção que isso acarretaria variam de acordo com a tabela a seguir: Anos de construção Fábrica 1 2 3 4 A 100 125 110 130 B 150 125 175 140 C 125 110 100 170 D 175 200 220 250 E 140 105 155 135 A empresa também está restrita em seu plano de construção pelas seguintes condições: a) As fábricas A e B não podem ser construídas após a Fábrica C; b) A empresa não pode gastar mais de 500 unidades monetárias no total; c) As fábricas D e E devem ser construídas durante o mesmo ano. Formular como um problema de programação inteira. Variáveis: considere i∈{A,B,C,D} (fábrica i), j∈{1,2,3,4} (ano j) yij∈{0,1} a construção da fábrica i será iniciada no instante j Na formulação considere que os custos da tabela do enunciado são cij Equações F.Obj.: (minimize) Z = ΣiΣjcijyij Restrições Σjyij = 1, i∈{A,B,C,D} - todas as fábricas devem ser construídas yA1 ≥ yC1 yA1 + yA2 ≥ yC2 yA1 + yA2 + yA3 ≥ yC3 yA1 + yA2 + yA3 + yA4 ≥ yC4 yB1 ≥ yC1 yB1 + yB2 ≥ yC2 yB1 + yB2 + yB3 ≥ yC3 yB1 + yB2 + yB3 + yB4 ≥ yC4 Σcijyij ≤ 500 yDj = yEj, j∈{1,2,3,4} 28) Uma empresa quer planejar a produção agregada para os próximos 5 meses. As encomendas previstas estão listados na tabela. Ao longo do período de 5 meses, as unidades podem ser produzidas em um mês e estocadas/armazenadas para satisfazer a procura de meses mais tarde. Devido a fatores sazonais, o custo de produção não é constante, como mostrado na tabela. Mês Demanda (unidades ) Custo da Produção ($/unid) 15 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 1 1300 100 2 1400 105 3 1000 110 4 1700 110 5 1900 110 O custo de manter um item estocado por 1 mês é $ 4/unidade/mês. Itens produzidos e vendidos no mesmo mês não são colocados no estoque. O limite de produção mensal é de 103 unidades e o estoque inicial é de 5 unidades. A empresa deseja que no final do último mês tenha um estoque de 4 unidades. O problema é determinar a quantidade ideal para produzir em cada mês de modo que a demanda seja atendida enquanto minimiza o custo total de produção e de estocagem. Escassez não é permitida. Formule o problema como um problema de transporte. Variáveis: considere iÎ{A,B,C,D} (mês i) xiÎZ+ a quantidade a ser produzida no mês i yiÎZ+ a quantidade a ser estocada do mês i para o mês (i+1) Na formulação considere as demandas di e os custos ci da acima tabela acima Equações F.Obj.: (minimize) Z = Sicixi + Si4yi Restrições 5 + x1 = 1300 + y1 y(i-1) + xi = di + yi, i=2,...,4 y4 + x5 = 1900 + 5 xi £ 103 29) A seção de I&D de uma empresa desenvolveu 4 possíveis novas linhas de produtos. A direção da empresa deve agora pronunciar-se sobre quais dos produtos fabricar e em que quantidades, com base num modelo matemático para determinar a combinação mais lucrativa de produtos. A criação de uma nova linha de produção tem um elevado custo inicial, de acordo com a seguinte tabela, em que a terceira linha mostra a receita unitária de cada produto: Produto à 1 2 3 4 Custo inicial (x106) (ci) 50 40 70 60 Lucro unitário (li) 70 60 90 80 A direção impôs as seguintes restrições relativas aos níveis de produção de cada produto: i. No máximo só 2 novos produtos podem ser fabricados. ii. O produto 3 pode ser produzido apenas se os produtos 1 ou 2 o forem. iii. Ou 5x1 + 3x2 + 6x3 + 4x4 £ 6000 ou 4x1 + 6x2 + 3x3 + 5x4 £ 6000 deve ser satisfeita. Introduza as variáveis binárias necessárias para formular um modelo de programação inteira mista para este problema. Variáveis: considere iÎ{1, 2, 3, 4} (produto i) yiÎ{0,1} produzir ou não o produto i xiÎZ+ quanto produzir do produto i wÎ{0,1} ativar a restrição 5x1 + 3x2 + 6x3 + 4x4 £ 6000 ou a restrição 4x1 + 6x2 + 3x3 + 5x4 £ 6000 Equações 16 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM F.Obj.: (maximize) Z = Silixi – Siciyi Restrições Siyi = 2 y1 + y2 ³ y3 y1 - y5 £ 0 4x1 + 6x2 + 3x3 + 5x4 £ 6000 + Mw 5x1 + 3x2 + 6x3 + 4x4 £ 6000 + M(1 - w) 17