PESQUISA OPERACIONAL  - Metodo Grafico

PESQUISA OPERACIONAL - Metodo Grafico

Professor: Dr. Edwin B. MitaccMeza edwin@engenharia-puro.com.br w .engenharia-puro.com.br/edwin/PO-I.html

Solução de Modelos de PL

Método Gráfico Método Simplex

Método Gráfico Método Gráfico

Pesquisa Operacional I 4

Interpretação Gráfica

A partir da modelag em mat emática de um PPL, pode ‐se enc ontr ar a sua solução atr avés da int erpr etação gr áfica da função objeti vo e das restriç ões oper acionais , desde que o pr oblema possua no máximo duas variá veis de decisão .

Est e tipo de solução não te m aplicação pr ática pois os pr oblemas do mundo real tem sempr e muit o mais variá veis (dez enas ,cent enas eat é milhar es).

No entant o, asolução gr áfica nos ajudar á a ent ender os princípios básic os do mét odo analític o, chamado de mét odo Simplex, usado par aresol veros modelos de P.Linear .

Pesquisa Operacional I 5

Interpretação Gráfica Porque somente até duas variaveis?

¾ No espaço de2 dimensões uma igualdade repr esenta uma reta.

¾ É important e per ceber que cada desigualdade repr esenta um semi ‐espaç o.

Pesquisa Operacional I 6

Definições Importantes

¾ RE GIÃ O VIA VÉL : É u m conjunt o desoluç ões que satisfaz em as restriç ões do pr oblema.

¾SOL UÇÃ O VIA VÉL : É u ma solução que pert enc e à região viá vel.

¾ VÉR TICES : São os pont os de int erseção das restriç ões do pr oblema.

¾ VÉR TICES DA RE GIÃ O VIA VÉL :Sãoo sp ontosd ei nterseção das restriç ões do problema que faz e m part e da região viá vel.

Pesquisa Operacional I 7

Método Gráfico

Vamos resolver o seguinte problema graficamente:

Um ae mpresafabrica2 pr odut os. Nafabricação dest es produt os, 3insumos são crític os: as quantidades de mat éria prima ea mão de obr a disponí veis.

Pr odut o1 Pr odut o 2 Disponibilidade

Mat éria Prima A 70 kg/unidade 70 kg/unidade 4900 kg Mat éria Prima B 90 kg/unidade 50 kg/unidade 4500 kg

Mão de Obra Especializada P12H‐h/unidade80H‐h Mão de Obra Especializada P23H‐h/unidade180H‐h Lucr o 20 R$/unidade 60 R$/unidade

Da da a gra nde pro cura, esti ma‐se que todas as unidades aser em pr oduzidas , dos 2 pr odut os, poder ão ser vendidas . O objeti vo da e mpr esa é obt er o maior lucr o possí velcom a produção eavenda das unidades dos pr odut os 1 e2.

Pesquisa Operacional I 8

Método Gráfico

Qual é o Modelo

Matemático para este pr oblema?

Pesquisa Operacional I 9

Método Gráfico

Vamos resolver o seguinte problema graficamente:

Um ae mpresafabrica2 pr odut os. Nafabricação dest es produt os, 3insumos são crític os: as quantidades de mat éria prima ea mão de obr a disponí veis.

Pr odut o1 Pr odut o 2 Disponibilidade

Mat éria Prima A 70 kg/unidade 70 kg/unidade 4900 kg Mat éria Prima B 90 kg/unidade 50 kg/unidade 4500 kg

Mão de Obra Especializada P12H‐h/unidade80H‐h Mão de Obra Especializada P23H‐h/unidade180H‐h Lucr o 20 R$/unidade 60 R$/unidade

Da da a gra nde pro cura, esti ma‐se que todas as unidades aser em pr oduzidas , dos 2 pr odut os, poder ão ser vendidas . O objeti vo da e mpr esa é obt er o maior lucr o possí velcom a produção eavenda das unidades dos pr odut os 1 e2.

Pesquisa Operacional I 10

Método Gráfico

O modelo de Programação Linear para o exemplo pode ser descrito como:

Pesquisa Operacional I 1

Método Gráfico Vamos resolver nosso problema graficamente

Pesquisa Operacional I 12

Método Gráfico

Pesquisa Operacional I 13

Método Gráfico

Pesquisa Operacional I 14

Método Gráfico

Pesquisa Operacional I 15

Método Gráfico

Pesquisa Operacional I 16

Método Gráfico

Co mo todas as restriç ões for am tr açadas te mos o chamado Espaç o Sol ução queéoco njunto deto dosos ponto scandidato sasere m o ponto óti mo, ou seja, todos os pont os que “obedec em ”atodas as restriç ões do modelo .

Espaço Solução

O ponto ótimo é um ponto do espaço solução, ou seja pertencente ao polígono hachurado.

Como encontrá‐lo gr aficament e?

Pesquisa Operacional I 17

Método Gráfico

Pesquisa Operacional I 18

Método Gráfico

Pesquisa Operacional I 19

Método Gráfico

O pont o ótimo ter sido um dos vértic es do espaç osol ução não é uma mer a coincidência. Na ver dade o pont o ótimo é sempr e um dos vértic es do espaç osolução .

Pesquisa Operacional I 20

Op ontoó ti moés e mpre u mdosv érticesd oe spaços oluçãoa não ser

Método Gráfico quando te mos múltiplas (inf initas) soluç ões ótimas , pois nest e caso , os pont os ótimos são todos os pert enc ent es a u m dos lados do espaç o solução .

Pesquisa Operacional I 21

Método Gráfico Z=4500

Pesquisa Operacional I 2

Método Gráfico

(0,0) ÆZ=0 (40,0) ÆZ=800 (40,18) ÆZ=1880 (25,45) ÆZ=3200 (10,60) ÆZ=3800 (0,60) ÆZ=3600

Pesquisa Operacional I 23

Método Gráfico

Aoresol ver um pr oblema de PL pode ocorr er uma das seguint es situaç ões:

O problema tem uma únicasolução ótima

Pesquisa Operacional I 24

Método Gráfico

O problema tem múltiplassoluções (uma infinidade)

Pesquisa Operacional I 25

Método Gráfico

O problema nãotem ótimo fi nito

Pesquisa Operacional I 26

Filosofia do Método Simplex

Pesquisa Operacional I 27

Exercícios 1

Pesquisa Operacional I 28

Exercícios 2

Pesquisa Operacional I 29

Exercícios 3

Pesquisa Operacional I 30

Exercícios 4

Comentários