PesquisaOperacional& - Luciana Assis · Problemadadieta • Um& nutricionista precisa estabelecer& uma dieta contendo,& pelo& menos,&10&unidades&de&vitaminaA,&30&unidades&de&vitaminaB&e&18&

UFVJM DECOM Luciana Assis www.dcc.ufmg.br/~lpassis

Pesquisa Operacional

Modelos de Programação Linear

15/10/13 1


Introdução

•  Modelos de Programação Linear é básico para compreensão de todos os outros modelos de Programação MatemáMca.

•  Existe algoritmos muito eficientes para solução dos modelos.

15/10/13 2


CaracterísMcas

•  Proporcionalidade

•  Não NegaMvidade

•  AdiMvidade

•  Separabilidade

15/10/13 3

Sempre é possível desenvolver dada

aMvidade e qualquer proporção de um dado recurso deve sempre poder ser uMlizado.

A solução do modelo se altera de um valor constante dada

variação constante das variáveis de decisão.

Pode-‐se idenMficar de forma separada o custo

específico das operações de cada

aMvidade.

O custo total é a soma das parcelas associadas

a cada aMvidade.


Programação Linear •  Consiste na maximização ou minimização de uma função linear denominada: FUNÇÃO OBJETIVO

•  Respeitando um sistema linear de igualdades e desigualdades denominadas: RESTRIÇÕES

•  Restrições determinam uma região denominada: CONJUNTO DE SOLUÇÕES VIÁVEIS

•  A melhor solução viável, aquela que maximiza ou minimiza a FO é denominada: SOLUÇÃO ÓTIMA

15/10/13 4

Exemplo

A WINDOR GLASS Inc. dispõe de capacidade extra para produzir dois novos produtos. A demanda é muito maior que a capacidade disponível (toda produção poderá ser vendida). Pergunta-‐se: (a) o que produzir? (b) quanto produzir? (c) qual será o lucro? (d) qual o valor, em $/hora, da capacidade disponível em cada setor produMvo? Os dados estão na tabela abaixo.

Setor Produtivo Produto

Capacidade Disponível Janelas Portas

Montagem 1 hora/unid. - 4.000 horas/mês Laminação - 2 hora/unid. 12.000 horas/mês

Corte 3 hora/unid. 2 hora/unid. 18.000 horas/mês

Lucro Unitário $ 3,00 $ 5,00

Modelagem Conceitual e MatemáMca

•  Variáveis –  X1 = qtde. de janelas, em milhares de unidades; –  X2 = qtde. de portas, em milhares de unidades; –  Z = lucro total obMdo com novos produtos.

•  Restrições –  a) disponibilidade do setor de montagem; –  b) disponibilidade do setor de laminação; –  c) disponibilidade do setor de corte; –  d) quanMdades não negaMvas.

•  ObjeMvo – Maximizar o lucro total da empresa

Setor Produtivo Produto

Capacidade Disponível Janelas Portas

Montagem 1 hora/unid. - 4.000 horas/mês Laminação - 2 hora/unid. 12.000 horas/mês

Corte 3 hora/unid. 2 hora/unid. 18.000 horas/mês

Lucro Unitário $ 3,00 $ 5,00

Exemplos de Modelos de Programação Linear

1.  Problema da dieta

3.  Problema das Ligas Metálicas

5.  Problema do SíMo

15/10/13 7

Problema da dieta

•  Um nutricionista precisa estabelecer uma dieta contendo, pelo menos, 10 unidades de vitamina A, 30 unidades de vitamina B e 18 unidades de vitamina C. Essas vitaminas estão conMdas em quanMdades variadas em cinco alimentos que vamos chamar de s1, s2, s3, s4 e s5. O quadro seguinte dá o número de unidades das vitaminas A, B e C em cada unidade desses cinco alimentos bem como o custo, em reais, por unidade. Calcular as quanMdades dos 5 alimentos que devem ser incluídas na dieta diária, a fim de encontrarmos esses teores de vitaminas com o menor custo.

10/05/16 8

Alimentos >Vitaminas v

S1 S2 S3 S4 S5

A 0 1 5 4 3B 2 1 0 3 2C 3 1 0 9 0

CUSTO 4 2 1 10 5

Problema da dieta •  Iden%ficar variáveis, restrições e FO. 1.  Variáveis: “Calcular quanMdade dos cinco alimentos”.

LOGO: x1, x2, x3, x4 e x5 2.  Restrições:

a)  “Pelo menos 10 unidades de vitamina A” 0x1 + 1x2 + 5x3+ 4x4 + 3x5 ≥ 10

c)  “Pelo menos 30 unidades de vitamina B” 2x1 + 1x2 + 0x3+ 3x4 + 2x5 ≥ 30

e)  “Pelo menos 18 unidades de vitamina C” 3x1 + 1x2 + 0x3+ 9x4 + 0x5 ≥ 18

15/10/13 9

Problema da dieta 2.  Restrições:

a)  Não se pode consumir quanMdade negaMva dos alimentos. (“Não podemos comer -‐1 pão). LOGO: retrição de não-‐nega%vidade. x1 ≥ 0; x2 ≥ 0; x3 ≥ 0; x4 ≥ 0; x5 ≥ 0

4.  Função ObjeMvo: O custo por dia desta dieta será expresso pela função linear: Q(x) = 4x1 + 2x2 + 1x3+ 10x4 + 5x5 LOGO: FO à MIN Q(x)

15/10/13 10

Problema da dieta •  RESUMINDO...

Min Q(x) = 4x1 + 2x2 + 1x3+ 10x4 + 5x5 SA: x2 + 5x3+ 4x4 + 3x5 ≥ 10 2x1 + x2 + 3x4 + 2x5 ≥ 3 3x1 + x2 + 9x4 ≥ 18 x1, x2, x3, x4, x5 ≥ 0

15/10/13 11

Problema das Ligas Metálicas •  Uma metalúrgica deseja maximizar sua receita bruta. A tabela ilustra a proporção de cada material na mistura para obtenção das ligas passíveis de fabricação. O preço está cotado em Reais por tonelada da liga fabricada. Também em toneladas estão expressas as retrições de disponibilidade de matéria-‐prima.

10/05/16 12

Liga Baixa Resistência

Liga Alta Resistência

Disponibilidade

Cobre 0,5 0,2 16Zinco 0,25 0,3 11

Chumbo

0,25 0,5 15

Preço 3000 5000


Problema das Ligas Metálicas •  Iden%ficar variáveis, restrições e FO. 1.  Variáveis: QuanMdade produzida das ligas de baixa e alta resistência.

LOGO: x1, x2 2.  Restrições:

a)  Disponibilidade de cobre 0,5x1 + 0,2x2 ≤ 16

c)  Disponibilidade de zinco 0,25x1 + 0,3x2 ≤ 11 c)  Disponibilidade de chumbo 0,25x1 + 0,5x2 ≤ 15 d)  Não NegaMvidade x1 ≥ 0; x2 ≥ 0

5.  Função ObjeMvo: MAX Q(x) = 3.000x1 + 5.000x2

15/10/13 13


Problema das Ligas Metálicas •  RESUMINDO...

MAX Q(x) = 3.000x1 + 5.000x2 SA: 0,5x1 + 0,2x2 ≤ 16 0,25x1 + 0,3x2 ≤ 11 0,25x1 + 0,5x2 ≤ 15 x1, x2 ≥ 0

15/10/13 14

Problema do SíMo •  Um siMante está planejando sua estratégia de planMo para o próximo ano. Por informações obMdas nos órgãos governamentais, sabe que as culturas de trigo, arroz e milho serão as mais rentáveis na próxima safra. Por experiência, sabe que a produMvidade de sua terra para as culturas é dada na tabela abaixo. Por falta de um local de armazenamento próprio, a produção máxima, em toneladas, está limitada a 60. A área culMvável do síMo é de 200.000m2. Para atender às demandas de seu próprio síMo, é imperaMvo que se plante 400m2 de trigo, 800m2 de arroz e 10.000m2 de milho.

10/05/16 15

Produtividade (kg por m2) Lucro (kg de produção)

Trigo 0,2 10,8Arroz 0,3 4,2Milho 0,4 2,03


Problema do SíMo •  Iden%ficar variáveis, restrições e FO. 1.  Variáveis: área em m2 a ser plantada de Trigo, Arroz e Milho.

x1, x2, x3 2.  Restrições:

a)  Demanda do síMo x1 ≥ 400; x2 ≥ 800; x3 ≥ 10.000

c)  Área total disponível x1 + x2 + x3 ≤ 200.000 c)  Armazenamento (kg) 0,2x1 + 0,3x2 + 0,4x3 ≤ 60000 a)  Não NegaMvidade x1 ≥ 0; x2 ≥ 0 ; x3 ≥ 0

4.  Função ObjeMvo: MAX Q(x) = (0,2*10,8)x1 + (0,3*4,2)x2 + (0,4*2,03)x3

15/10/13 16


Problema do SíMo •  RESUMINDO...

MAX Q(x) = 2,16x1 + 1,26x2 + 0,812x3 SA: x1 ≥ 400 x2 ≥ 800 x3 ≥ 10.000 x1 + x2 + x3 ≤ 200.000 0,2x1 + 0,3x2 + 0,4x3 ≤ 60000 x1 ≥ 0; x2 ≥ 0 ; x3 ≥ 0

15/10/13 17


EXERCÍCIOS

15/10/13 18

•  Um jovem estava saindo com duas namoradas: Maria e Luísa. Sabe, por experiência, que: –  Maria, elegante, gosta de frequentar lugares sofisMcados, mais caros, de modo que uma saída de três horas custará R$240,00.

–  Luísa, mais simples, prefere um diverMmento mais popular, de modo que uma saída de três horas custará R$160,00.

–  Seu orçamento permite dispor de R$960,00 mensais para diversão. Seus afazeres escolares lhe dão liberdade de, no máximo, 18 horas e 40.000 calorias de sua energia para aMvidades sociais.

–  Cada saída com Maria consome 5.000 calorias, mas com Luísa, mais alegre e extroverMda, gasta o dobro.

–  Ele gosta das duas com a mesma intensidade. •  Como ele deve planejar sua vida social para obter o número máximo de saídas?

•  Um fazendeiro tem 200 unidades de área de terra , onde planeja culMvar trigo, arroz e milho. A produção esperada é de 1800 kg por unidade de área plantada de trigo, 2100 kg por unidade de área plantada de arroz e 2900 kg por unidade de área plantada de milho. Para atender ao consumo interno de sua fazenda, ele deverá plantar pelo menos 12 unidades de área de trigo, 16 unidades de área de arroz e 20 unidades de área de milho. Ele tem condições de armazenar no máximo 700 000 kg. Sabendo que o trigo dá um lucro de $ 1,20 por kg, o arroz $ 0,6 por kg e o milho $ 0,28 por kg, quantas unidades de área de cada produto ele deve plantar para que o seu lucro seja o maior possível?

•  Considere o problema de encontrar a produção de duas ligas metálicas A e B, que são feitas de quatro metais disMntos, I, II, III, IV, de acordo com a especificação apresentada na tabela a seguir:

• Os quatro metais são extraídos de três minérios diferentes, cujas porcentagens em peso destes metais, quanMdades máximas dos minérios e custos por toneladas são fornecidas a seguir:

•  Considere que os preços de venda das ligas A e B sejam $ 200,00 e $ 300,00 por tonelada, respecMvamente.

•  Devido ao número inconstante de passageiros, uma companhia de ônibus necessita de um número variado de motoristas de pendendo do horário considerado. A tabela a seguir especifica a quanMdade de motoristas necessários:

•  Considere que cada motorista trabalha 8 horas seguidas e que o serviço pode ser iniciado as 1, 5, 9, 13, 17, ou 21h. Formule este problema como um PL de modo que as demandas sejam atendidas e o número de motoristas seja o menor possível.

10/05/16 UFVJM DECOM Luciana Assis www.dcc.ufmg.br/~lpassis

23

•  Problema de Alocação de Recursos: Um fundo de invesMmentos tem até R$ 300.000,00 para aplicar em duas ações. A empresa D é diversificada (tem 40% do seu capital aplicado em cerveja e o restante aplicado em refrigerantes) e espera-‐se que forneça bonificações de 12%. A empresa N não é diversifica (produz apenas cerveja) e espera-‐se que distribua bonificações de 20%. Para este invesMmento, considerando a legislação governamental aplicável, o fundo está sujeito às seguintes restrições: –  O invesMmento na empresa diversifica pode aMngir R$ 270.000,00.

–  O invesMmento na empresa não-‐diversificada pode aMngir R$ 150.000,00.

–  O invesMmento em cada produto (cerveja ou refrigerante) pode aMngir R$ 180.000,00.

–  Pede-‐se: Qual o esquema de invesMmento que maximiza o lucro?

Deseja&se' determinar' as' misturas' de' 4' derivados' do' petróleo,' que' serão' os'constituintes' de' três' tipos' de' gasolina' (extra,' super' e' comum).' O' objetivo' é'maximizar'o'lucro.'

Constituintes' Máximo'disponível'(barris/dia)'

Custo/barril'($)'1' 3.000' 3'2' 2.000' 6'3' 4.000' 4'4' 1.000' 5'

A' fim' de'manter' a' qualidade' de' cada' tipo' de' gasolina,' é' preciso'manter' as'porcentagens' dos' diversos' constituintes' dentro' dos' limites' especificados.' Os'preços'de'venda'de'cada'tipo'de'gasolina'por'barril'também'estão'indicados'na'tabela'abaixo:'

Tipo'de'Gasolina' Especificações' Preço'de'venda'($)'' não'mais'''que'30%'de'1' 'A' não'mais'''que'50%'de'3' 5,50'' não'menos'que'40%'de'2' 'B' não'mais'''que'50%'de'1' 4,50'' não'menos'que'10%'de'2' 'C' não'mais'''que'70%'de'1' 3,50'

'

•  Uma refinaria deseja produzir com mínimo custo a gasolina “Premium” que contenha, no mínimo, as seguintes porcentagens dos componentes A, B e C, a saber: 10% de A, 20% de B e 12% de C. Ela dispõe de três diferentes Mpos de óleo cru – do Texas, custa $2/barril e tem 15% de A, 10% de B e 9% de C;

– da Pensilvânia, custa $2,5 o barril e tem 18% de A, 25% de B e 3% de C;

– da Califórnia, custa $1,30/barril e tem 10% de A, 15% de B e 30% de C.

Num$ laboratório$ químico,$ querem$ produzir$ um$ ácido$ com$ as$ seguintes$características:$$a)$O$ ácido$deve$ conter$ no$mínimo$20%$do$ componente$B1,$ no$máximo$20%$do$componente$B2$e$no$mínimo$35%$do$componente$B3;$b)$O$peso$específico$deve$ser$menor$ou$igual$a$1.$$O$ácido$deverá$ser$produzido$a$partir$de$uma$mistura$de$três$matériasJprimas,$R1,$R2,$ R3.$A$ percentagem$na$qual$ os$ componentes$B1,$ B2$ e$B3,$ encontramJse$nas$matériasJprimas$ bem$ como$ o$ peso$ específico$ e$ o$ preço$ por$ unidade$ são$ dados$pela$tabela$apresentada$a$seguir:$

$ B1$ B2$ B3$ Peso$Específico$

Preço$por$unidade$($)$

R1$ 15$ 10$ 40$ 1,04$ 140$R2$ 20$ 15$ 30$ 0,95$ 120$R3$ 25$ 30$ 35$ 1,00$ 130$

$

Considere$que$o$peso$específico$do$ácido$será$dado$levandoJse$em$conta$a$proporção$em$que$as$matériasJprimas$se$encontram$na$mistura$determinar$esta$proporção,$que$minimize$o$custo$da$produção$do$ácido.$

•  Uma indústria produz sucos de laranja e de tomate. O processo consiste na fabricação da lata, extração do suco e enlatamento. O mercado fornecedor pode fornecer tomate para 20.000 latas por semana, e laranjas para 30.000 latas por semana. Cada lata de suco de tomate dá um lucro de R$0,20 e de laranja de R$0,30. As latas são idênMcas, diferindo apenas no rótulo. As seções de fabricação de latas têm capacidade para produzirem 40.000 latas por semana. A seção de extração trabalha 40 horas por semana e pode produzir 1.000 latas de suco de laranja por hora ou 2.000 latas de suco de tomate por hora (ou qualquer outra combinação entre essas produções, ou seja, se produzir 1.000 latas de suco de laranja por hora, esgota toda sua capacidade e não pode produzir sucos de tomate; se dedicar metade de sua capacidade à produção de cada Mpo de suco, produzirá 500 latas de suco de laranja por hora e ainda 1.000 latas de suco de tomate por hora). A seção de enlatamento pode enlatar até 35.000 latas por semana, de um Mpo ou de outro, pois as latas são idênMcas. –  Determinar a programação semanal de produção que leva a máximo lucro

Documents

PesquisaOperacional& - Luciana Assis · Problemadadieta • Um& nutricionista precisa estabelecer& uma dieta contendo,& pelo& menos,&10&unidades&de&vitaminaA,&30&unidades&de&vitaminaB&e&18&