Parte 4 - Pesquisa Operacional 1 - Lásara Rodrigues UFOP

8/9/2019 Parte 4 - Pesquisa Operacional 1 - Lsara Rodrigues UFOP

1/39

1

Exemplos de Problemas de

Pesquisa Operacional -Continuao

Disciplina: PRO706 - Pesquisa Operacional I

Prof: Lsara Rodrigues

Departamento de Engenharia de Produo, Administrao e EconomiaEscola de Minas

Universidade Federal de Ouro Preto

2010/1

4 Parte


2/39

2

Fbrica de Mveis

Uma grande fbrica de mveis normalmenteoferece uma linha de mveis composta por ummodelo de escrivaninha, uma mesa de reunio,um armrio e uma prateleira.

Cada tipo de mvel consome uma certaquantidade de matria-prima e apresenta umvalor de revenda, conforme a tabela abaixo.

Exibir um modelo de programao linear quemaximize a receita com a venda dos mveis.


3/39


4/39

4

Fbrica de Mveis

Variveis de decisoxi = quantidade em unidades a serem produzidas

do produto i;x1 = quantidade em unidades a serem produzidas

de escrivaninha (i = 1);x2 = quantidade em unidades a serem produzidas

de mesa (i = 2);x3 = quantidade em unidades a serem produzidas

de armrios (i = 3);

x4 = quantidade em unidades a serem produzidasde prateleira (i = 4);


5/39

5

Fbrica de Mveis

Funo Objetivo

maximizar receita

max Z = 100x1 + 80x2 + 120x3 + 20x4


6/39

6

Fbrica de Mveis

Restries Disponibilidade de tbua

x1 + x2 + x3 + 4x4 250

Disponibilidade de pranchasx2 + x3 + 2x4 600

Disponibilidade de painis

3x1 + 2x2 + 4x3 500

No-negatividadex1 0, x2 0, x3, 0, x4 0


7/39


8/39

8

Escala de Funcionrios

Uma empresa necessita da quantidade mnima defuncionrios/dia mostrada na tabela abaixo.

30251010152020Func. Requeridos

SabSexQuiQuaTerSegDomDia

Cada funcionrio trabalha 5 dias consecutivos e tem 2dias de folga e pode comear em qualquer dia dasemana.

Cada funcionrio recebe $300/semana. Se trabalhar

aos sbados, recebe um extra de $30 e se for aosdomingos um extra de $40.

Faa uma escala de funcionrios de forma a minimizaro gasto com pessoal.


9/39

9


Variveis de decisoxi = nmero de funcionrios necessrios para iniciar o trabalho

no dia i;x1 = nmero de funcionrios necessrios para iniciar o trabalho

no domingo;

x2 = nmero de funcionrios necessrios para iniciar o trabalhona segunda;x3 = nmero de funcionrios necessrios para iniciar o trabalho

no tera;x4 = nmero de funcionrios necessrios para iniciar o trabalho

no quarta;

x5 = nmero de funcionrios necessrios para iniciar o trabalhono quinta;x6 = nmero de funcionrios necessrios para iniciar o trabalho

no sexta;x7 = nmero de funcionrios necessrios para iniciar o trabalho

no sbado;


10/39

10


370XXXXXSab

370XXXXXSex370XXXXXQui

370XXXXXQua

330XXXXXTer

300XXXXXSeg

340XXXXXDom

CustoSabSexQuiQuaTerSegDom

Dia de Incio Dias de trabalho


11/39

11


Funo Objetivo

Minimizar gasto com pessoal

min f(x) =340x1 + 300x2 + 330x3 +370x4 + 370x5+ 370x6 + 370x7


12/39

12


Restries Quantidade mnima de funcionrios para trabalhar no

domingox1 + x4 + x5 + x6 + x7 20

Quantidade mnima de funcionrios para trabalhar nasegunda

x1 + x2 + x5 + x6 + x7 20 Quantidade mnima de funcionrios para trabalhar na

terax3 + x4 + x5 + x6 + x7 15

Quantidade mnima de funcionrios para trabalhar naquartax1 + x2 + x3 + x4 + x7 10


13/39

13


Quantidade mnima de funcionrios paratrabalhar na quintax1 + x2 + x3 + x4 + x5 10

Quantidade mnima de funcionrios para

trabalhar na sextax2 + x3 + x4 + x5 + x6 25

Quantidade mnima de funcionrios paratrabalhar na sbadox3 + x4 + x5 + x6 + x7 35

No-negatividadex1 0, x2 0, x3, 0, x4 0, x5 0, x6 0, x7, 0


14/39

14


min 340x1 + 300x2 + 330x3 +370x4 + 370x5 + 370x6 + 370x7Sujeito a:

x1 + x4 + x5 + x6 + x7 20

x1 + x2 + x5 + x6 + x7 20

x3 + x4 + x5 + x6 + x7 15

x1 + x2 + x3 + x4 + x7 10

x1 + x2 + x3 + x4 + x5 10

x2 + x3 + x4 + x5 + x6 25

x3 + x4 + x5 + x6 + x7 35x1 0, x2 0, x3 0, x4 0, x5 0, x6 0, x7 0


15/39

15

Problema da Mistura

Uma agroindstria deve produzir um tipo de raopara determinado animal.

Essa rao produzida de farinhas de trsingrediente bsicos: osso, soja e resto de peixe.

Cada um desses trs ingredientes contmdiferentes quantidades de dois nutrientesnecessrios a uma dieta nutricional balanceada:protena e clcio.

O nutricionista especifica as necessidades mnimas

desses nutrientes em 1Kg de rao. Cada ingrediente adquirido no mercado com um

certo custo unitrio ($/Kg).


16/39


17/39

17

Problema da Mistura

Variveis de deciso

xi quantidade (em Kg) do ingrediente i que deveser utilizada em uma unidade de (1Kg) darao.

x1 quantidade (em Kg) de osso que deve serutilizada em uma unidade de (1Kg) da rao.

x2 quantidade (em Kg) de soja que deve serutilizada em uma unidade de (1Kg) da rao.

x3 quantidade (em Kg) de peixe que deve serutilizada em uma unidade de (1Kg) da rao.


18/39

18

Problema da Mistura

Funo Objetivo

Minimizar custo

min 0,56x1 + 0,81x2 + 0,46x3


19/39


20/39

20

Problema da Mistura

min 0,56x1 + 0,81x2 + 0,46x3Sujeito a:

0,2x1 + 0,5x2 + 0,4x3

0,30,6x1 + 0,4x2 + 0,4x3 0,5

x1 + x2 + x3 = 1

x1

0, x2

0, x3

0


21/39

21

Transporte de agregados para aconstruo civil

Suponha que, para a construo de umarodovia, no estejam disponveis na regio

jazidas de rochas adequadas obteno depedra britada.

Faz-se necessrio, portanto, o transporte dessematerial de jazidas mais prximas para algunspontos convenientes preestabelecidos ao longodo caminho de jazidas mais prximas paraalguns pontos convenientes preestabelecidos

ao longo do caminho onde ser implantada aestrada ao menor custo.


22/39

22


Caminhos possveis que ligam cada pedreira (P)aos pontos de depsito (D).


23/39

23


Neste problema, temos m = 4 jazidascorrespondentes s origens e n = 3 depsitoscorrespondentes aos destinos, cujos dados estona tabela.

As quantidades ofertadas (ai ltima coluna) edemandadas (bj ltima linha), em toneladas, somostradas na tabela.

Custos de transportar 1 tonelada de pedra dapedreira i para o depsito j (cij que funo de

vrios fatores, como tempo de viagem, condiesdas estradas de acesso, condies dos veculosque servem a trajetria em questo etc.) somostrados na tabela.


24/39

24


612421697Demanda bj

3001925374

7823515273

2152640122

4332113301

Oferta ai321Pedreiras

Depsitos


25/39

25


Varivel de deciso

xij = quantidade transportada de rochas da jazida ipara o ponto de depsito j (em toneladas).

i = 1 Pedreira 1 (P1)




j = 1 Depsito 1 (D1)




26/39

26


Funo Objetivo

Minimizar o custo de transporte

min 30x11 + 13x12 + 21x13 + 12x21 + 40x22 + 26x23 +

27x31 + 15x32 + 35x33 + 37x41 + 25x42 + 19x43


27/39

27


Restries

Oferta na Pedreira 1

x11 + x12 + x13 433


x21 + x22 + x23 215


x31 + x32 + x33 782


x41 + x42 + x43 300


28/39

28


Demanda no Depsito 1

x11 + x21 + x31 + x41 = 697


x12

+ x22

+ x32

+ x42

= 421


x13 + x23 + x33 + x43 = 612

No-Negatividade

x11

0, x12 0, x

13 0, x

21 0, x

22 0, x

23 0,

x31 0, x32 0, x33 0, x41 0, x42 0, x43 0


29/39

29


min 30x11 + 13x12 + 21x13 + 12x21 + 40x22 + 26x23 + 27x31+ 15x32 + 35x33 + 37x41 + 25x42 + 19x43

Sujeito a:

x11 + x12 + x13 433

x21 + x22 + x23 215x31 + x32 + x33 782

x41 + x42 + x43 300

x11 + x21 + x31 + x41 = 697

x12 + x22 + x32 + x42 = 421

x13 + x23 + x33 + x43 = 612

x11 0, x12 0, x13 0, x21 0, x22 0, x23 0,

x31 0, x32 0, x33 0, x41 0, x42 0, x43 0


30/39

30

Dimensionamento de lotes

Uma fbrica de pr-moldados que produz doistipos de vigas, cujas demandas para asprximas 3 semanas so mostradas na tabelaabaixo.

805040Item 212090100Item 1

Perodo 3Perodo 2Perodo 1Demandade vigas

Demanda de vigas


31/39

31


Os produtos utilizam os mesmo tipos derecursos, porm em quantidades diferentes.

Suponha, por simplicidade, que apenas umcentro de trabalho esteja disponvel para aproduo dos dois itens, cuja disponibilidade de 40 horas por perodo e que a produo deuma unidade do item 1 consuma 15 minutos euma unidade do item 2 consuma 20 minutos.


32/39

32


302020Item 2

302020Item 1

Perodo 3Perodo 2Perodo 1Custos deproduo

Custos de produo


33/39


34/39

34


Deseja-se definir um plano de produode modo que os pedidos sejam atendidosao menor custo de produo e

estocagem. Os estoques iniciais dos dois produtos so

nulos e deseja-se que seus estoques aofinal do horizonte de planejamento

tambm sejam nulos.


35/39

35


Variveis de deciso:

xit = quantidade da viga tipo i produzida no

perodo t.

Iit = quantidade da viga tipo i estocada no

final do perodo t.


36/39

36


Funo Objetivo

Minimizar custo (produo e estocagem)

min 20x11 + 20x12 + 30x13 + 20x21 + 20x22 +30x23 + 2I11 + 3I12 + 2,5I21 + 3,5I22


37/39


38/39


39/39

39


min 20x11 + 20x12 + 30x13 + 20x21 + 20x22 + 30x23 + 2I11 + 3I12+ 2,5I21 + 3,5I22

Sujeito a:x11 + I11 = 100x12 + I11 I12 = 90

x13 + I12 = 120x21 - I21 = 40x22 + I21 - I22 = 70x23 + I22 = 80

1/4 x11 + 1/3 x21

Documents

Parte 4 - Pesquisa Operacional 1 - Lásara Rodrigues UFOP