Lista Formulação-2023 1

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. 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) 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. 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. 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 1 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 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. 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. 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. 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. 2 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 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. 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. 3 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 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. (Função linear por partes? talvez!!!) 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. 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. 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. 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. 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 ln. A empresa quer minimizar o custo de contratação de funcionários. 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. 4 UNIVERSIDADE FEDERAL DO PARANA — DEPARTAMENTO DE ENGENHARIA DE PRODUGAO TECNOLOGIA DA DECISAO II - PRoF. VotmiR EuGénio WILHELM 17) Devemos escolher M entre 9 projetos p1, p2, ..., p9 cujos custos associados sao c1, C2, ..., c9 respeitando as seguintes regras: a) se o projeto p3 for selecionado, entao o projeto p6 nao pode ser selecionado; b) selecionar p1 ou p8 implica na selegao de p5; c) selecionar o projeto p3 entao 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. b. Suponha que foi incluida a restrigao y4 + y7 < y9 +1. Interprete esta restrigao. 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. 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|Bj;]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 II A 100 200 B 80 150 Cc 40 20 D 10 - Suponha que temos as condigoes adicionais: i) se usarmos qualquer quantidade do ingrediente Il, incorreremos em um custo fixo de 15; ii) nao precisamos satisfazer as quatro restrigdes 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? So formule o PLI. 20) Uma empresa deseja determinar o plano de investimentos para o préximo ano, e dispde dos seguintes projetos: spats : Valor Presente Capital Possibilidade de Investimento Liquido (R$ Requerido (R$ I. Construir um novo depdosito 7.000.000,00 5.000.000,00 Il. Recuperar o deposito antigo 4.500.000,00 3.000.000,00 Ill. Automatizar o depdsito 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 fabrica para produzir A 9.500.000,00 7.100.000,00 VI.Reformar o escritorio da empresa 1.500.000,00 900.000,00 5 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 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). 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. 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. 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. 24) Uma companhia pode realizar 7 grandes investimentos. O lucro de longo prazo estimado (VPL) e o capital requerido são dados na tabela: Oportunidade de investimento 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. 6 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 25) Uma companhia aérea efetua 5 voos {1, 2, 3, 4, 5}, dispondo para isso de 6 tripulações. A tabela a seguir mostra quais os voos que cada tripulação pode realizar bem como o custo de fazer voar essa tripulação. Tripulação A B C E D F Pode fazer os voos 1,2 1,3,4 2,4,5 1,3,5 4,5 1,5 Custo 2 3 3 3 2 2 Observações: i) As tripulações podem viajar como passageiros; ii) Em cada avião deve haver apenas uma tripulação trabalhando. Formule um modelo de programação inteira para o problema de cobrir todos os voos com as tripulações disponíveis de modo a minimizar o custo total. 26) A Grafitex imprime camisetas com desenhos. Para cada um de seus 4 contratos pendentes, a tabela a seguir mostra: i) o número de dias de trabalho necessários; ii) o dia mais cedo em que o trabalho pode começar; e iii) o dia em que o pedido é devido (quando o pedido precisa ser entregue – data do vencimento do contrato): Contrato 1 Contrato 2 Contrato 3 Contrato 4 Tempo de trabalho (em dias) 10 3 16 8 Data de início mais cedo possível 0 20 1 12 Data de vencimento do contrato 12 30 20 21 A empresa quer um cronograma que minimize a soma dos atrasos (atrasos) das conclusões dos contratos. Defina: Di, o dia de início para execução do trabalho do contrato i; Ai, o atraso da conclusão do trabalho do contrato i. Defina quaisquer variáveis adicionais que você deseja usar e formule um pli. 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. 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) 1 1300 100 2 1400 105 3 1000 110 4 1700 110 5 1900 110 7 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 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. 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. 8