Pesquisa Operacional - Programação Matemática

8/10/2019 Pesquisa Operacional - Programao Matemtica

1/74


2/74

5.1 - Introduo

Desde a antiguidade vrios cientistas tais como Euclides, Newton, Lagrange,

Leontief, Von Neumann, dentre outros, tem dedicado seus estudos a pesquisa do

timo. A rea que estuda Problemas de Otimizao denominada ProgramaoMatemtica que engloba uma ampla classe de problemas. O termo programao

significa que existe um planejamento das atividades.

A Programao Matemtica vem se constituindo como uma das mais poderosas

ferramentas matemticas para diversos segmentos, propiciando melhorias

mensurveis nos processos e automatizao dos mesmos, analises operacionais,

de projetos, reengenharia e identicao de gargalos. Seus benefcios so

exatamente aqueles procurados por qualquer empresa: diminuio dos custos e

aumento dos lucros. Em algumas organizaes ela est, inclusive, embutida em

suas rotinas informatizadas de planejamento dirio dos processos de operao.

Segundo pesquisas efetuadas em empresas que tem utilizado esta ferramenta, a

reduo de custos se enquadra facilmente na faixa entre 1% e 5%, existindo

casos que chegam at a 15%. A magnitude do benefcio da Programao

Matemtica na performance das empresas pode ser avaliada nos casos listados a

seguir referentes a diferentes reas de atividade econmica.


3/74

3

1. A companhia de leos TEXACO utilizou a Programao Linear para obter

condies ideais de processamento do petrleo bruto para produzir quantidades

proporcionais s necessidades do mercado aos diversos derivados do petrleo:

gasolina, leos com diversas graduaes ou asfalto. A aplicao da metodologiaem sete das suas refinarias permitiu obter uma melhoria de 30% nos lucros,

atingindo 30 milhes de dlares.

2. A rede de fast food McDonald's nos Estados Unidos aplicou a ProgramaoMatemtica para otimizaao dos horrios de trabalho em quatro de seus

estabelecimentos, pertencentes a Al Boxley. Este tipo de atividade recorre

frequentemente a mo-de-obra em part-time, tendo como resultado uma grande

aleatoriedade na disponibilidade dos recursos humanos. A Programao Linear

proporcionou um melhor aproveitamento dos recursos disponveis, com aexigncia de cobertura durante todo periodo de funcionamento das unidades,

obtendo-se uma programao de horrios mais conveniente de acordo com as

preferncias de horrio de cada funcionrio.


4/74

4

Uma das caractersticas principais de Programao Matemtica e sua

extensibilidade, pode ser aplicada a diverso nmero de organizaes e sistemas:

indstrias, governos, agncias, hospitais, economia, sociologia, biologia, dentre

outros.

Algumas de suas aplicaes se tornaram clssicas:

Problema de transporte

Administrao da produo

Analise de investimentos

Problemas de distribuio de recursos, pessoal e tarefasProblemas de corte de materiais, etc.

Em um Problema de Otimizao pretende-se maximizar ou minimizar uma

quantidade especfica, designada objetivo, que depende de um numero finito de

variveis independentes ou interrelacionadas por limitaes ou restriestcnicas do sistema. Resolver o problema significa aplicar uma sequncia de

operaes matemticas para distribuir recursos limitados sobre operaes que

exigem a sua utilizao simultnea, de forma tima para o objetivo especfico.


5/74

5

Um Problema de Programao Matemtica (PPM) e um problema de

otimizao satisfazendo dois fatos principais:

A existncia de um objetivo que pode ser explicitado em termos das

variveis de deciso do problema;

A existncia de restries a aplicao dos recursos, tanto com relao as

quantidades disponveis quanto com relao a forma de emprego.


6/74

6

5.2Modelos de Otimizao com Programao Matemtica

Especificamente, o objetivo primordial de um PPM encontrar a melhor

soluo para problemas que podem ser representados por modelos

matemticos onde o objetivo pode ser expresso em funo das variveis e as

restries expressas como equaes ou inequaes.

Os modelos matemticos utilizados em PPM seguem, em geral, uma estrutura

padro composta por :

uma funo-objetivo,

um critrio de otimizao e

um conjunto de restries.


7/747

A forma geral de um modelo para um PPM com n variveis e m restries

apresentada a seguir:

onde as variveis do problema esto representadas por xjcom j = 1,...,n e bi, para

i = 1,...,m, representa a quantidade disponvel de determinado recurso.

Utilizaremos a notao vetorial para representar as variveis de deciso, assimdefine-se:

f(x) denominada funo-objetivo e gi(x) so as funes restries do problema.


8/74

8

A soluo do modelo pode ser obtida por tcnicas matemticas e algortmos

especficos, e a construo do modelo deve levar em considerao a

disponibilidade de uma tcnica para o clculo da soluo. Para melhor estudar as

tcnicas disponveis para resoluo de PPM, a rea pode ser subdividida em duassubreas determinadas pelas propriedades das funes envolvidas no problema:

Programao Linear :Todas as funes do modelo so lineares em relao asvariveis.

Programao No-Linear : Pelo menos uma das funes envolvidas no linear.

A soluo de um PPM inicia-se pela modelagem, esta etapa to importantetanto quanto o desenvolvimento de mtodos de soluo, visto que a qualidade de

todo o processo consequncia direta do grau de representatividade do modelo.


9/74

9

A tarefa de construo do modelo a partir do enunciado do problema deve seguir

uma metodologia bsica, apresentada a seguir:

Identificao das variveis de deciso

Todas as grandezas envolvidas devem ser determinadas, explicitando as decisesque devem ser tomadas, nomeando-as xj , j = 1; : : : ; n.

Definio do critrio de otimizao

Critrios de avaliao capazes de indicar que uma deciso prefervel a outras

devem ser definidos. Deve-se identificar as metas que se pretendem alcanar coma resoluo do problema, expressando-as como funes matemticas. Em geral, o

objetivo aparece na forma de maximizao ou minimizao de quantidades.

Formulao das restries

Todos os requisitos, condicionalismos e limitaes do problema, tanto explcitascomo implcitas, devem ser identificados. Cada limitao imposta na descrio do

problema deve ser expressa como uma equao ou inequao em funo das

variveis de deciso.


10/74

10

Para melhor ilustrar os conceitos discutidos, sero apresentadas

algumas situaes que podem ser descritas com o auxlio de um modelode Programao Matemtica.

A seguir so propostos alguns PPM onde espera-se exemplicar e detalhar

o processo de modelagem, entretanto sera a experincia individualresponsvel pelo desenvolvimento de habilidades para a criao de bonsmodelos matemticos, eficientes e realistas.

Salienta-se que, ainda no h a preocupao com a soluo deproblemas que podero ser obtidas posteriormente.

5.3 - Problemas de Programao Matemtica


11/74

11

Exemp lo 5.1. Produo de balas

Considere que uma doceira deseja abrir um pequeno negcio paraproduo de balas. A princpio ela esta considerando produzir dois tipos

de balas: caramelo e nozes.

Na produo sao utilizados trs ingredientes: leite, acar e nozes. Adoceira tem em estoque 10kg de acar, 1kg de nozes e 6l de leite.

A composio da bala de caramelo : 40% de leite e 60% de acar, epara as balas de nozes os ingredientes devem ser misturados na seguinteproporo : 40% de leite, 50% de acucar e 10% de nozes.

Cada quilo de bala de caramelo pode ser vendido a R$10,00 enquanto umquilo de bala de nozes pode ser vendido por R$13,00.

Qual deve ser a produo de cada tipo de bala para obter a maior receita?


12/74

12

De acordo com a sistemtica estabelecida anteriormente para aconstruo de modelos de PPM, vamos elaborar o modelo para esteproblema em etapas.

Etapa 1 : Identificao das variveis de deciso

O objetivo do problema determinar as quantidades de cada tipo debala a ser produzida de forma a resultar na mxima receita. Portanto,este problema tem duas variveis de deciso :

x1: a quantidade (em kg) a ser produzida de bala de caramenlox2: a quantidade (em kg) a ser produzida de bala de nozes

Etapa 2: Formulao da funo objetivo

O critrio para a seleo da melhor combinao possvel a receita

maxima. Cada tipo de bala gera uma receita que o produto do preode venda pela quantidade vendida e a funo receita obtida pelasoma das contribuies de cada tipo de bala produzido.

Matematicamente, temos:max z = f(x1; x2) = 10x1 + 13x2


13/74

13

Etapa 3 : Formulao das restries

O problema impe restries na quantidade de matria prima parafabricao dos doces:

0,6 x1+ 0,5 x2 10 (quantidade utilizada de acar)0,4 x1+ 0,4 x2 6 (quantidade utilizada de leite)

0,1 x2 1 (quantidade utilizada de nozes)

Ainda h uma condio implcita ao problema que devemos considerar,

quais os valores que as variveis de deciso podem assumir?Nesta situao estamos interessados em valores no-negativos quesatisfaam as limitaes de matria-prima.Devemos tambm considerar o tipo de varivel, neste problemapodemos admitir que a varivel xjpode receber qualquer valor real.

Assim temos definido o domnio da funo objetivo e o criterio de no-negatividade:

xj 0 ; xjR


14/74

14

O modelo completo para o problema da produo de balasrepresentado no formato (5.2) :

mx : z = 10 x1+ 13 x2

Observe que a condio xjR foi omitida do modelo final, isto deve-

se ao fato que em modelos de Programao Matemtica, porconveno, esta condio considerada implcita ao modelo. Ainformao sobre o domnio da funo constar no modelo caso odomnio seja outro conjunto numrico.

0,6 x1+ 0,5 x2 10 (quantidade utilizada de acar)0,4 x1+ 0,4 x2 6 (quantidade utilizada de leite)

0,1 x2 1 (quantidade utilizada de nozes)

x1, x2 0 (condio de no-negatividade)

s.a :


15/74

15

Exemplo 5.2. Prob lema da Dieta

Um indivduo deve seguir uma dieta balanceada por recomendaomdica baseada no consumo de diversos tipos de alimentos de forma a

suprir suas necessidades dirias de energia, que pode variar de 3100 a3300 kcal, e nutrientes essenciais para a boa saude.

Uma poro de cada alimento fornece uma porcentagem da QuantidadeDiria Recomentada (QDR) de diferentes nutrientes de acordo com a

tabela.

Preo e quantidade calrica de cada poro tambem so informados natabela.

Deseja-se saber qual a combinao ideal de alimentos com customnimo e que satisfaa as necessidades nutricionais.


16/74

16

tabela


17/74


18/74

18


O critrio para a seleo da melhor combinao possvel o customnimo. Cada tipo de alimento gera um custo que o produto do preo

da poro pelo nmero de pores consumidas e a funo custo obtida pela soma das contribuies de cada alimento consumido.

Matematicamente, temos:


19/74


20/74

20

(c) Ainda h uma condio implcita ao problema que devemosconsiderar. Quais os valores que as variveis de deciso podemassumir?

Nesta situao estamos interessados em valores no-negativos quesatisfaam os nveis mnimos de nutrientes.

Devemos tambm considerar o tipo de varivel, neste problemapodemos adimitir que a varivel xj pode receber qualquer valor real.

Assim temos definido o domnio da funo objetivo e o critrio de no-negatividade:


21/74

21

O modelo para o problema da dieta representado no formato padro :


22/74

22

Exemp lo 5.3. Dis tr ib u io da Produo

Uma empresa montadora de eletrnicos produz radio, toca-CD eaparelhos de DVD em trs fbricas localizadas em Diadema, Ribeiro

Preto e Campinas. As quantidades despendidas na produo de cadaproduto, em peas por hora, em cada uma das fbricas so asseguintes:

Os custos de operao por hora das fbricas so R$ 10.000,00,

R$ 8.000,00 e R$ 11.000,00 para Diadema, Ribeiro Preto eCampinas, respectivamente.A empresa recebeu um pedido de 300 unidades de radio, 500unidades de toca-CD e 600 unidades de aparelho de DVD.Como deve distribuir a produo entre suas trs fbricas para

cumprir o pedido ao menor custo possvel?


23/74

Et 2 F l d f bj ti


24/74

24


O objetivo primordial determinar quantas horas cada uma das fbricasdeve dispor para o pedido com o menor custo possvel.

O custo dado por :z = f(x; y; z) = 10:000x + 8:000y + 11000z , onde :

x o total de horas que a fbrica de Diadema funciona para atender o pedido,y e o numero total de horas da fbrica de Ribeiroz corresponde ao total de horas da fbrica de Campinas.

De acordo com a tabela fornecida podemos determinar :xem funo das variveis de deciso x1d; x2d e x3d,yem funco de x1r; x2r e x3rzem funco de x1c; x2c e x3c:


25/74

25

Etapa 3: Formulao das restries

A limitaes explcitas do problema so o atendimento da quantidadedemandada no pedido, isto , a soma das produes das trs fbricas deum determinado produto no deve ser inferior a quantidadeencomendada:

x1d + x1r + x1c 300 (encomenda de radios)x2d + x2r + x2c 500 (encomenda de toca-CD)

x3d + x3r + x3c 600 (encomenda de DVD)

As condies implcitas do problema so a no-negatividade e odomnio da funo objetivo restrito ao conjunto dos nmeros inteiros Z.


26/74

E l 5 4 O C d L j d Q i j


27/74

27

Exemp lo 5.4. O Caso da Lo ja do s Quei jos

A Loja dos Queijos produz e comercializa dois tipos de queijos (Delux eStandard), muito procurados na poca do Natal. Estes queijos soproduzidos a partir de uma mistura de frutas da poca e de um queijo

especial muito caro. A Loja dos Queijos pode dispor de 20 kg de mistura de frutas e 60 kg

do queijo especial utilizado. Cada kg de Delux consiste em 0,2 kg da mistura de frutas e 0,8 kg do

queijo especial, enquanto que 1 kg de Standard consiste em 0,2 kg da

mistura de frutas, 0,3 kg do queijo especial e 0,5 kg de um queijocomum, disponvel em grande quantidade.

De acordo com a experincia da Loja dos Queijos, foi possveldescobrir que a procura de cada um dos dois queijos depende dopreo adotado: d1 = 190 + 25.p1 e d2 = 250 + 50.p2onde d representa a procura (kg), p denota o preco (u.m./kg), e osndices 1 e 2 designam os tipos Delux e Standard, respectivamente.

Que quantidade de cada tipo de queijo dever a Loja dos Queijospreparar, e que preos devero ser adotados para maximizar a receita egarantir que, apos a poca do Natal, nada reste dos dois queijos em

estoque?


28/74


29/74

29

O modelo ainda no est completo pois necessrio garantir que toda a

produo seja vendida, para tanto a produo xi no deve ultrapassar a

demanda di, isto ,xi di ; i = 1; 2

Considerando as equaes de demanda, temos:

x1 19025.p1

x2 25050.p2

Reescrevendo as inequaes, obtemos as seguintes restries de

demanda:

x1 + 25.p1 190

x2 + 50.p2 250


30/74

30

Para simplicar o problema, o objetivo tambm deve ser reescrito somente em

funo das variveis de deciso. Observe que para quaisquer valores fixos

de x1 e x2 a funo z = p1.x1 + p2.x2 aumenta conforme aumentarem os

preos p1 e p2, assim para maximizar z, p1 e p2 devem assumir valores

mximos, isto , assumir valores tais que as inequaes referente asrestries de demanda se tornem equaes. Desta forma, os preos podem

ser assumidos como:

Substituindo os valores dos preos na funo objetivo temos:


31/74

31

O modelo completo e apresentado a seguir e deve-se notar que asrestries de demanda foram incorporadas na construo da funoobjetivo e no sero incorporadas s restries do problema.

Exemp lo 5 5 Um Problema de Transp orte


32/74

32

Exemp lo 5.5. Um Problema de Transp orte

Uma companhia de panificao pode produzir po de forma em duasfbricas, de acordo com a tabela:

Quatro redes de restaurantes pretendem comprar pes de forma, suasnecessidades e os preos que esto dispostos a pagar so os seguintes:


33/74

33

O custo (em u.m.) de transporte de uma unidade de po de forma decada padaria para cada rede de restaurantes dado na tabela seguinte.

Determine o plano timo de fornecimento de pes de forma a maximizaro lucro total da empresa de panificao.


34/74

34

Variveis de deciso:

xij: quantidade a ser transportada (em unidades)da origem i = A;B para o destino j = 1; 2; 3; 4

De acordo com tabela de preos, a funo receita ser :

r = 3,9.xi1 + 3,7.xi2 + 4,0.xi3 + 3,6.xi4 para i = A;B

A seguir apresentado o modelo para maximizao da funo lucroobtida subtraindo-se dos preos unitrios os custos de produo e detransporte.

Objetivo:

max z = xA1 + 0,2.xB1 + 0,6.xA2 + 0,6.xB2 + 0,6.xA3 + 0,7.xB3 + 0,4x.A4 + 0,6.xB4

Portanto a funo objetivo (max z) e as funes restries :


35/74

35

max z = xA1 + 0,2.xB1 + 0,6.xA2 + 0,6.xB2 + 0,6.xA3 + 0,7.xB3 + 0,4x.A4 + 0,6.xB4

Portanto, a funo objetivo (max z) e as funes restries :

Exemp lo 5 6 Empresa de Rao Max im izao dos Lucro s


36/74

36

"Uma empresa de comida canina produz dois tipos de raes: Tobi eRex. Para a manufatura das raes so utilizados cereais e carne.

Sabe-se que:

a rao Tobi utiliza 5 kg de cereais e 1 kg de carne, e a rao Rexutiliza 4 kg de carne e 2 kg de cereais;

o pacote de rao Tobi custa $ 20 e o pacote de rao Rex custa $

30; o kg de carne custa $ 4 e o kg de cereais custa $ 1; esto disponveis por ms 10 000 kg de carne e 30 000 kg de cereais.

Deseja-se saber qual a quantidade de cada rao a produzir de modo a

maximizar o lucro."

Exemp lo 5.6. Empresa de Rao, Max im izao dos Lucro s

( )


37/74

37

Nosso modelo deseja maximizar o lucro (Z) a partir da quantidade derao Tobi (x1) e de rao Rex (x2). A Tabela abaixo apresenta oclculo do lucro unitrio de cada rao.

A funo objetivo pode ser escrita como : max Z = 11.x1 + 12.x2

As restries sero :

1.x1 + 4.x2 10000 (restrio de carne)5.x1 + 2.x2 30000 (restrio de cereais)

Positividade das variveis :x1, x2 0

Exemp lo 5 7 Mar cenar ia Prog ramao de Produo


38/74

38

Exemp lo 5.7. Mar cenar ia , Prog ramao de Produo

"Uma marcenaria deseja estabelecer uma programao diria deproduo. Atualmente, a oficina faz apenas dois produtos: mesa earmrio, ambos de um s modelo. Para efeito de simplificao, vamos

considerar que a marcenaria tem limitaes em somente doisrecursos: madeira e mo-de-obra, cujas disponibilidades dirias somostradas na tabela a seguir.

O processo de produo tal que, para fazer uma mesa a fbricagasta 2 m2 de madeira e 2 H.h de mo-de-obra. Para fazer um armrio,a fbrica gasta 3 m2 de madeira e 1 H.h de mo de obra.

Alm disso, o fabricante sabe que cada mesa d uma margem decontribuio para o lucro de $ 4 e cada armrio de $ 1.

O problema encontrar o programa de produo que maximiza amargem de contribuio total para o lucro."

As variveis de deciso envolvidas no problema so:


39/74

39

As variveis de deciso envolvidas no problema so:x1: quantidade a produzir de mesasx2: quantidade a produzir de armrios

A funo objetivo :

Lucro: z = 4.x1 + x2

Para as restries, a relao lgica existente :Utilizao de recurso DisponibilidadeAssim temos :

Madeira: 2.x1 + 3.x2 12Mo-de-obra: 2.x1 + x2 8

Pos itiv idade das v ariveis : x1, x2 0

Desta forma, o modelo completo :max: z = 4 x1 + x2

2.x1 + 3.x2 122 x1 + x2 8x1, x2 0

Restr.

Exemp lo 5.8. Determ in ao do Mix de Pro duo


40/74

40

Uma companhia deseja programar a produo de um utenslio decozinha que requer o uso de dois tipos de recursosmo-de-obra

e material. A companhia est considerando a fabricao de trsmodelos e o seu departamento de engenharia forneceu os dados aseguir:

Modelo

A B C

Mo-de-obra

(horas por unidade)7 3 6

Material

(kg por unidade)

4 4 5

Lucro

($ por unidade)4 2 3

O suprimento de material

de 200 kg por dia. Adisponibilidade diria demo-de-obra 150 horas.

Formule um modelo deProgramao Linear para

determinar a produo diriade cada um dos modelos demodo a maximizar o lucrototal da companhia.

Exemp lo 5.8. Determ in ao do Mix de Pro duo


41/74

41

Formulao do modelo

1. Identificao das variveis de deciso:

XA

produo diria do modelo AXBproduo diria do modelo B

XCproduo diria do modelo C

2. Identificao das restries:

(Limitao de material) 4XA+ 4XB+5XC 200

(No-negatividade) XA0, XB0, XC0.

3. Identificao do objetivo: maximizao do lucro total

Lucro Total = L = 4XA+ 2XB+3XCMax : L = 4XA+ 2XB+3XC


42/74

42

Modelo

Encontrar nmeros XA, XB, XCtais que:

Max L= 4XA+ 2XB+3XC

Sujeito as restries: 7XA+ 3XB+6XC 150

4XA+ 4XB+5XC 200

XA0, XB0, XC0

Exemp lo 5.9. Seleo de Mdia para Propaganda


43/74

43

Exemp lo 5.9. Seleo de Mdia para Propaganda

Uma companhia de propaganda deseja planejar umacampanha em 03 diferentes meios: TV, rdio e revistas.

Pretende-se alcanar o maior nmero de clientes possvel.Um estudo de mercado resultou em:

TV

horrio

TV

horrio

Rdio Revistas

normal nobre

Custo 40.000 75.000 30.000 15.000

Clientes

Atingidos400.000 900.000 500.000 200.000

MulheresAtingidas

300.000 400.000 200.000 100.000

0bs: valores vlidos para cada veiculao da propaganda.


44/74


45/74

45

Variveis de deciso:

X1= n. de exposies em horrio normal na tv.

X3= n. de exposies feitas utilizando rdio

X4= n. de exposies feitas utilizando revistas.

Funo-objetivo:

Maximizar n. de clientes atingidos

Max Z = 400.000X1+ 900.000X2+ 500.000X3+ 200.000X4

X2= n. de exposies em horrio nobre na tv.


46/74

46

Restries:

Oramento:

40.000X1+ 75.000X2 + 30.000X3+ 15.000X4 800.000

Gasto com TV

40.000X1+ 75.000X2 500.000

N. de veiculaes em TV, rdio e revistasX13X225 X3 105 X4 10

No-negatividadeX1, X2, X3,X40.


47/74

47

Max Z = 400.000X1+ 900.000X2+ 500.000X3+ 200.000X4

Resumindo, o modelo :

40.000X1+ 75.000X2 + 30.000X3+ 15.000X4 800.000

40.000X1+ 75.000X2 500.000

X13

X225 X3 105 X4 10

X1, X2, X3,X40.

Restr.


48/74


49/74

49

Encontrar um modelo de PL que fornea um programa detreinamento de custo mnimo e satisfaa os requisitos da empresaem termos de n. de operadores treinados disponveis a cada ms.

Observao: acordo firmado com o sindicato probe demisses de

operadores treinados no perodo.

Os custos associados a cada situao so:

Trainees...........................................................................$ 400.

Operador treinado trabalhando ........................................$ 700.Operador treinado ocioso..................................................$ 500.


50/74

50

Variveis de deciso:

X6= operadores ociosos em maroX5= operadores trabalhando como instrutores em maro

X4= operadores ociosos em fevereiro

X3= operadores trabalhando como instrutores em fevereiro

X2= operadores ociosos em janeiro

Resoluo do exemplo: Um problema de treinamento

Observe que a cada ms um operador treinado est: operandomquina, trabalhando como instrutor, ou est ocioso. Alm disto, o

n. de operadores treinados trabalhando nas mquinas fixo econhecido: 100 em janeiro, 150 em fevereiro, 200 em maro e 250 emabril.

X1= operadores trabalhando como instrutores em janeiro


51/74

51

Funo-objetivo:

Min C = 400(10X1 + 10X3+ 10X5) + 700(X1+ X3+ X5) ++ 500

(X2+ X4+ X6) + 700(100 + 150 + 200)

Min C = 4700X1+500X2+ 4700X3 +500X4+4700X5+500X6+ 315.000

Custo total = custo trainees+ custo instrutores + custo ociosos +custo operadores trabalhando em mquinas.


52/74

52

Restries: X1, X2, X3, X4, X5, X6 0 (no-negatividade)

Abril: 250 = 130 + 7X1+ 7X3+ 7X57X1+ 7X3 + 7X5= 120

operadores treinados no incio do ms = operadores nasmquinas + instrutores + operadores ociosos.

Equao de balano mensal:

Janeiro: 130 = 100 + X1+ X2X1+ X2= 30

Fevereiro: 130 + 7X1= 150 + X3+ X47X1- X3- X4 = 20

Maro: 130 + 7X1 + 7X3= 200 + X5+ X67X1+ 7X3- X5- X6= 70


53/74

53

Min C = 400

(10X1 + 10X3+ 10X5) + 700(X1+ X3+ X5) +

+ 500(X2+ X4+ X6) + 700(100 + 150 + 200)

Min C = 4700X1+500X2+ 4700X3 +500X4+4700X5+500X6+ 315.000


Abril: 250 = 130 + 7X1+ 7X3+ 7X57X1+ 7X3 + 7X5= 120

Janeiro: 130 = 100 + X1+ X2X1+ X2= 30

Fevereiro: 130 + 7X1= 150 + X3+ X47X1- X3- X4 = 20

Maro: 130 + 7X1 + 7X3= 200 + X5+ X67X1+ 7X3- X5- X6= 70

X1, X2, X3, X4, X5, X6 0

Restr.

Exemp lo 5.11. Uma Indstr ia Qum ica


54/74

54

Dois produtos, A e B, so feitos a partir de duas operaesqumicas. Cada unidade do produto A requer 02 horas da operao 1

e 03 horas da operao 2. Cada unidade do produto B requer 03horas da operao 1 e 04 horas da operao 2. O tempo totaldisponvel para a realizao da operao 1 de 16 horas, e o tempototal para a operao 2 de 24 horas.

A produo do produto B resulta, tambm, num subproduto C semcustos adicionais. Sabe-se que parte do produto Cpode ser vendidocom lucro, mas o restante deve ser destrudo. Previses mostramque no mximo 05 unidades do produto Csero vendidas, e sabe-seque cada unidade do produto B fabricada gera 02 unidades do

produto C.


55/74

R l d l U i d t i i d t A


56/74

56

Observe que o lucro da venda do produto A uma funo linear,

mas com respeito ao produto C isto no ocorre.

Resoluo do exemplo: Uma indstria qumica - produto A

Quantidade

Lucro

Produto A

4

Produto B

10

Quantidade

Produto C

-2

Lucro

3

5


57/74

57

2 X1+ 3 X2 16 (disponibilidade de tempo para operao 1)3 X1+ 4 X2 24 (disponibilidade de tempo para operao 2)

X3+ X4= 2 X2 (produo do produto C a partir do produto B)X3 5 (previso de produto C que pode ser vendido)X1, X2, X3, X40 (no-negatividade)

Restries:

Artifcio: considerar as variveis de deciso como sendoX1= quantidade produto A produzidaX2 = quantidade produto B produzida

X3= quantidade produto C vendidaX4= quantidade produto C destruda

Funo-objetivo:

Max Z = 4 X1+ 10 X2+ 3 X32 X4MODEL

O

Exemplo 5.12. O Caso da Ofic ina Mecnic a


58/74

58

p

Uma oficina mecnica tem 01 furadeira vertical e 05 fresas, que so

usadas para a produo de conjuntos formados de 2 partes. Sabe-sequal a produtividade de cada mquina na fabricao destas partesdo conjunto:

Furadeira Fresa

Parte 1 03 20

Parte 2 05 15

Obs: tempo para produzir as partes dado em minutos.


59/74

59

O encarregado pela oficina deseja manter uma carga balanceadanas mquinas de modo que nenhuma delas seja usada mais que

30 minutos por dia que qualquer outra, sendo o carregamento defresamento dividido igualmente entre as 05 fresas.

Achar um modelo de PL para dividir o tempo de trabalho entre asmquinas de modo a obter o mximo de conjuntos completos ao

final de um dia, num total de 08 horas de trabalho.

Variveis de deciso:X1= nmero de partes 1 produzidas por diaX

2

= nmero de partes 2 produzidas por dia

Resoluo do exemplo: Oficina mecnica


60/74

60

Restries:

3X1+ 5X2 480(minutos por dia disponveis para a furadeira)

(20X1+ 15X2)/5 = 4X1+ 3X2 480(minutos por dia disponveis para cada fresa)

Observe que esta ltima restrio no linear, mas equivalentea duas equaes lineares que podem substitu-la:

X1- 2X2 30 e -X1+ 2X2 30

X1, X20 (no-negatividade).

|(4X1+ 3X2) - (3X1+ 5X2)| = |X1-2X2| 30(Balanceamento de carga entre as mquinas)


61/74

61

maximizao do nmero de conjuntos completos por dia

Max Z = min (X1, X2)

Observe que esta funo no linear, mas pode ser linearizadautilizando-se uma nova varivel, da forma:

Seja Y = min (X1, X2), Y 0, naturalmente tem-se duas novasrestries

Dadas por: Y X1 e Y X2.

A funo-objetivo linear fica sendo: Max Z = Y

Funo-objetivo:



62/74

62

,

Max Z = Y , Y = min (X1, X2), Y 0 sendo : Y X1 e Y X2

3X1+ 5X2 480

4X1+ 3X2 480

X1- 2X2 30

-X1+ 2X2 30

X1, X20

Restr.

Exemp lo 5.13. Dimens ionamento de Uma Equ ipe de Ins petores


63/74

63

Uma companhia deseja determinar quantos inspetores alocar umadada tarefa do controle da qualidade. As informaes disponveisso:

H 08 inspetores do nvel 1 que podem checar as peas a uma taxade 25 peas por hora, com uma acuracidade de 98%, sendo o custo

de cada inspetor deste nvel $4 por hora;

H 10 inspetores do nvel 2 que podem checar as peas a uma taxade 15 peas por hora, com uma acuracidade de 95%, sendo o custode cada inspetor deste nvel $3 por hora.


64/74

64

A companhia deseja que no mnimo 1800 peas sejam

inspecionadas por dia (= 08 horas).

Sabe-se, ainda, que cada erro cometido por inspetores no controleda qualidade das peas acarreta um prejuzo companhia de $2 porpea mal inspecionada.

Formular um modelo de PL para possibilitar a designao tima don. de inspetores de cada nvel de modo a otimizar o custo dainspeo diria da companhia.

R l d l Di i t d i d i


65/74

65

Funo objetivo:

Minimizar C = custo total dirio de inspeo ($/dia)onde : custo total = custo do salrio dos inspetores + custo dos erros

Min C = 8 *[(4X1+ 3X2) + 2 * (25*0,02X1+ 15*0,05X2)]Min C = 40X1+ 36X2

Resoluo do exemplo: Dimensionamento de equipes de inspeo

Variveis de deciso:

Xi= n. de inspetores do nvel i (= 1, 2) alocados inspeo.


66/74

66

1. Quanto ao n. de inspetores disponveis:X1 8 (inspetores do nvel 1)X2 10 (inspetores do nvel 2)

2. Quanto ao n. de peas inspecionadas por dia:8 * (25X1+ 15X2) 1800 5X1+ 3X245

3. Restries implcitas de no negatividade:X

10

X20.

Restries:



67/74

67

Min C = 40X1+ 36X2

X1 8X2 105X1+ 3X245X10

X20.

Restr.


68/74

Variveis de Deciso :


69/74

69

Unidade produzida do Produto P1: x

Unidade produzida do Produto P2: y

Funo Objetivo:

Maximizar: 1000x + 1.800y

Restries:

- Tempo de Produo: 1.200h

20x + 30y 1.200

- Demanda Esperada do Produto P1: 40 unidades

x 40

- Demanda Esperada do Produto P2: 30 unidadesy 30



70/74

70

Maximizar Lucro

Max Z = 1000x + 1.800y

Restries:20x + 30y 1.200x 40

y 30x , y 0

Exemp lo 5.15. Min im izar o cu sto com alim entao


71/74

71

A necessidade mnima de vitaminas na alimentao de 32 unidadespor dia e a de protenas de 36 unidades por dia. Uma pessoa tem

disponvel carne e ovo para se alimentar.Cada unidade de carne contm 4 unidades de vitaminas e 6 unidadesde protenas.Cada unidade de ovo contm 8 unidades de vitaminas e 6 unidades deprotenas.Cada unidade de carne custa R$ 3,00 e cada unidade de ovo custa R$

2,5.Qual a quantidade de carne e ovo que deve ser consumida de forma ater o menor custo possvel.

Necessidade mnima de Vitamina: 32 unidades / dia

Necessidade mmima de Protenas: 36 unidades / dia

Variveis de Deciso :


72/74

72

Unidade consumida de carne: x

Unidade consumida de carne: y

Funo Objetivo :

Minimizar Custo: Min Z = 3x + 2,5y

Restries:

4x + 8y 32

6x + 6y 36

x, y 0


73/74

73


74/74

Documents

Pesquisa Operacional - Programação Matemática