7/24/2019 Mtodo Grfico e Problemas de PL(28-Abril)

1/17

Professora: Miriam Rocha

PESQUISA OPERACIONAL

7/24/2019 Mtodo Grfico e Problemas de PL(28-Abril)

2/17

Conceitos Bsicos

O conjunto C das solues

viveis de um modelo deprogramao linear um

conjunto convexo

7/24/2019 Mtodo Grfico e Problemas de PL(28-Abril)

3/17

Conceitos Bsicos

Poliedro convexo

7/24/2019 Mtodo Grfico e Problemas de PL(28-Abril)

4/17

Conceitos Bsicos

Toda soluo bsica vivel dosistema Ax=b

um ponto extremo do conjunto desolues viveis, ou seja, um extremo

do conjunto C

7/24/2019 Mtodo Grfico e Problemas de PL(28-Abril)

5/17

Conceitos Bsicos

Soluo tima

7/24/2019 Mtodo Grfico e Problemas de PL(28-Abril)

6/17

Conceitos Bsicos

Poliedro convexo

7/24/2019 Mtodo Grfico e Problemas de PL(28-Abril)

7/17

Conceitos Bsicos

Poliedro convexo

7/24/2019 Mtodo Grfico e Problemas de PL(28-Abril)

8/17

Conceitos Bsicos

O conjunto dos pontos

extremos de um conjunto desolues viveis finito e

limitado emm

nC

7/24/2019 Mtodo Grfico e Problemas de PL(28-Abril)

9/17

Conceitos Bsicos

Nmero Exponencialde Vrtices

7/24/2019 Mtodo Grfico e Problemas de PL(28-Abril)

10/17

Conceitos Bsicos

O Caminho do SIMPLEX

7/24/2019 Mtodo Grfico e Problemas de PL(28-Abril)

11/17

Exemplo Seleo Vendedores

Vendedor Regio

I II III IV

A 42 35 28 30

B 48 40 32 30

C 30 25 20 30

D 60 20 40 12

Uma empresa vende produtos em quatro regies e possui quatrovendedores para serem escalados, um para cada regio.

Como escalar os vendedores para que o volume de vendas sejao maior possvel.

Montante vendido por cada vendedor em cada regio, em milhares de $.

7/24/2019 Mtodo Grfico e Problemas de PL(28-Abril)

12/17

Exemplo Seleo Vendedores

Variveis de Deciso:

Funo Objetivo:

0

1

ijx

, caso o vendedor i seja escalado para a regio j, caso contrrio

4443424134333231

2423222114131211

1240206030202530

3032404830283542

xxxxxxxx

xxxxxxxxZMax

7/24/2019 Mtodo Grfico e Problemas de PL(28-Abril)

13/17

Exemplo Seleo Vendedores

1,0ijx

Restries:

1

1

1

1

44434241

34333231

24232221

14131211

xxxx

xxxx

xxxx

xxxx

1

1

1

1

44342414

43332313

42322212

41312111

xxxx

xxxx

xxxx

xxxx

Cada vendedor ser designadopara uma regio

Cada regio receber um

vendedor

7/24/2019 Mtodo Grfico e Problemas de PL(28-Abril)

14/17

Exerccio Transporte

CENTROS DESUPRIMENTO So Paulo Belo Horizonte Rio de Janeiro SUPRIMENTODISPONVEL

Araraquara 4 2 5 800

S.J. Campos 11 7 4 1000

DEMANDA DOSMERCADOS

500 400 900

2 centros de produo Araraquara e So Jos dos Campos 3 mercados consumidores principais SP, BH e RJ.

Companhia Distribuidora de Bebidas

OBJETIVO: Minimizar o Custo de Transporte

7/24/2019 Mtodo Grfico e Problemas de PL(28-Abril)

15/17

Exerccio Transporte

Varivel de Deciso:ijx

Quantidade a ser transportada do centro de suprimento ipara o mercado j

Funo Objetivo:232221131211

4711524 xxxxxxZMin

Restries:

0

900

400

500

1000

800

2313

2212

2111

232221

131211

ijx

xx

xx

xx

xxx

xxx

7/24/2019 Mtodo Grfico e Problemas de PL(28-Abril)

16/17

Exerccio Transporte

MERCADO (j) DEPSITOS (j)

CENTROS DESUPRIMENTO

(i)

SP

j=1

BH

j=2

RJ

j=3

Campinas

j=4

Barra Mansa

j=5

SUPRIMENTODISPONVEL

Araraquara

i=1

4 2 5 1 3 800

S.J. Campos

i=2

11 7 4 1 2 1000

Campinas

i=3

1 3 3

Barra Mansa

i=4

3 4 1

DEMANDA DOSMERCADOS 500 400 900

Companhia Distribuidora de BebidasMesmo problema, supondo agora que a empresa dispem de doisdepsitos para abastecer os mercados consumidores Campinas eBarra Mansa.

7/24/2019 Mtodo Grfico e Problemas de PL(28-Abril)

17/17

Exerccio Transporte

Funo Objetivo:

Restries:

0

900

400

500

1000

800

4342412515

3332312414

43332313

42322212

41312111

2524232221

1514131211

ijx

xxxxx

xxxxx

xxxx

xxxx

xxxx

xxxxx

xxxxx

434241333231

25242322211514131211

143331

21471131524

xxxxxx

xxxxxxxxxxZMin