Aula 3 Programação Linear - SIMPLEX Curso de Administração Prof: André Marques Cavalcanti

Aula 3

Programação Linear - SIMPLEX

Curso de Administração

Prof: André Marques Cavalcanti

3. MÉTODO SIMPLEX 3.1 Conceito e descrição do método para maximização 3.2 Solução de um modelo geral de programação linear pelo método simplex 3.2.1. o problema da minimização 3.2.2 o problema da variável livre 3.2.3 o problema da solução básica 3.3.4 Retorno ao modelo original 3.3 Aplicações Reais:Decisões do tipo fazer comprar, escolha da carteira de investimento, escala de funcionários 4. O problema do Dual e análise de sensibilidade

O problema do dual.Análise de sensibilidade: Alteração em um dos coeficientes da

função-objetivo, alteração do valor da constante da restrição

Fórmula Geral Fórmula Geral MAX (MIN) V = cMAX (MIN) V = c11XX11 + c + c22XX22 + ... + c + ... + cnnXXnn

Sujeito a:Sujeito a:

aa1111XX1 1 + a+ a1212XX2 2 + ... + a+ ... + a1n1nXXnn b b11

aak1k1XX1 1 + a+ ak2k2XX2 2 + ... + a+ ... + aknknXXnn b bkk

aam1m1XX1 1 + a+ am2m2XX2 2 + ... + a+ ... + amnmnXXnn == b bmm

...

...Onde:Onde:cc1, 1, cc22, ... , c, ... , cnn = margem de contribuição; medida de = margem de contribuição; medida de

custo; taxa de retorno, etc.custo; taxa de retorno, etc.

aaijij = quantidade do fator de restrição consumido em = quantidade do fator de restrição consumido em cada unidade produzida ou disponível para utilizar, cada unidade produzida ou disponível para utilizar, etc.etc.

bbi i = valor máximo ou mínimo do recurso escasso= valor máximo ou mínimo do recurso escasso

Método SimplexMétodo SimplexBaseia-se nas variáveis de FOLGABaseia-se nas variáveis de FOLGA

Base para os relatórios de SensibilidadeBase para os relatórios de Sensibilidade

Sistema com n variáveis e m equaçõesSistema com n variáveis e m equações Seleciona m variáveis (BÁSICAS)Seleciona m variáveis (BÁSICAS) As demais assumem valor = 0 (NÃO As demais assumem valor = 0 (NÃO

BÁSICAS)BÁSICAS) Calcula Função Objetivo para cada rodadaCalcula Função Objetivo para cada rodada Escolhe a de maior valorEscolhe a de maior valor

Solução Solução ComputacionalComputacional

Para Problemas mais ComplexosPara Problemas mais Complexos Solução via ExcelSolução via Excel

Ferramenta SolverFerramenta Solver

Condições EspeciaisCondições Especiais

1.1. Alternância de Soluções Ótimas Alternância de Soluções Ótimas

2.2. Restrições RedundantesRestrições Redundantes

3.3. Soluções IlimitadasSoluções Ilimitadas

4.4. Soluções de ImpossibilidadeSoluções de Impossibilidade

As duas primeiras não impossibilitam o modeloAs duas primeiras não impossibilitam o modelo As duas últimas impossibilitam o uso do As duas últimas impossibilitam o uso do

modelomodelo

Condições EspeciaisCondições Especiais

Alternância de Soluções Ótimas:Alternância de Soluções Ótimas:Ocorre quando há mais de um ponto que maximiza (ou Ocorre quando há mais de um ponto que maximiza (ou minimiza) o valor da função objetivominimiza) o valor da função objetivo

A existência de mais de uma solução possível não A existência de mais de uma solução possível não inviabiliza o uso da ferramenta Programação Linearinviabiliza o uso da ferramenta Programação Linear

Restrições Redundantes:Restrições Redundantes:Ocorre quando uma restrição não faz diferença na Ocorre quando uma restrição não faz diferença na determinação da área de soluções factíveisdeterminação da área de soluções factíveis

Soluções IlimitadasSoluções Ilimitadas

MAX: x1 + x2

Sujeito a: x1 + x2 400

- x1 + 2x2 400

x1 0

x2 0

Ocorre quando são encontradas soluções nas quais a Ocorre quando são encontradas soluções nas quais a função objetivo é infinitamente grande (maximização) ou função objetivo é infinitamente grande (maximização) ou infinitamente pequena (minimização)infinitamente pequena (minimização)

Exemplo:Exemplo:

Soluções IlimitadasSoluções Ilimitadas

x1

x2

Solução ImpossívelSolução Impossível

Exemplo:Exemplo:

MAX: x1 + x2

Sujeito a:

x1 + x2 150

x1 + 2x2 200

x1 0

x2 0

Programação LinearProgramação LinearO problema de programação linear consiste em maximizar ou minimizar uma O problema de programação linear consiste em maximizar ou minimizar uma

função linear de várias variáveis, designada de função objetivo, em que as função linear de várias variáveis, designada de função objetivo, em que as variáveis estão sujeitas a um conjunto de restrições, também lineares.variáveis estão sujeitas a um conjunto de restrições, também lineares.

As variáveis de decisão representam, em geral, níveis de atividades, as As variáveis de decisão representam, em geral, níveis de atividades, as restrições podem resultar de limitações de disponibilidade ou de recursos ou restrições podem resultar de limitações de disponibilidade ou de recursos ou requerimento mínimos que devem ser atendidos.requerimento mínimos que devem ser atendidos.

A função objetivo representa uma medida do desempenho do sistemaA função objetivo representa uma medida do desempenho do sistema

n1,...,j 0

m1,..., :a sujeito

max(min)

1

1

j

i

n

jjij

n

jjj

x

ibxa

xcz

Solução do PLSolução do PL

Um vetor X que satisfaça a todas as restrições Um vetor X que satisfaça a todas as restrições chama-se solução admissível. O conjunto de chama-se solução admissível. O conjunto de todas as soluções admissíveis é um poliedro todas as soluções admissíveis é um poliedro convexo e designa-se por região admissível. A convexo e designa-se por região admissível. A uma solução admissível que otimize a função uma solução admissível que otimize a função objetivo chama-se solução ótimaobjetivo chama-se solução ótima

Em PL toda solução que satisfaça a condição de Em PL toda solução que satisfaça a condição de ótimo local é uma solução ótima global do ótimo local é uma solução ótima global do problemaproblema

Resolução Por Método GráficoResolução Por Método Gráfico

É adequado apenas ao caso de duas variáveis

Exemplo de aplicação

Uma pequena oficina fabrica dois tipos diferentes: produto 1 e produto 2. O fabrico desse produtos requer três tipos diferentes de máquinas: A, B e C. Para cada unidade do produto 1 requer 1h nas máquinas do tipo A, 2h nas do tipo B e C. Cada unidade do produto 2 requer 1h na máquina do tipo A e B e 5horas nas máquinas do tipo C. A oficina possui várias máquinas dos 3 tipos com utilização máxima semanal de 50h para as do tipo A, 80h para os do tipo B e 220h nas do tipo C. Sabe-se que o lucro de uma unidade, de cada produto, é 25UM para o produto 1 e 20UM para o produto 2. Supõe-se que toda produção é vendida.

Qual deve ser a produção semanal de modo a maximizar o lucro resultante?

0

C maq- h/sem 022 52

B maq- h/sem 80 2

A maq- h/sem 50 :a sujeito

2025max

21

21

21

21

21

xx

xx

xx

xx

xxz

X2 80

50

44

0

0 40 50 80 110 X1

Fazendo z=0 tem-se por exemplo (-8, 10) e (10, -12,5)

Logo para esse valores Z=25x30+20x20=1150

(30,20)Z=0

O SIMPLEXO SIMPLEXCaracterística do Problema na Forma Padrão:Característica do Problema na Forma Padrão:

A função Objetivo é de MaximizaçãoA função Objetivo é de MaximizaçãoTodas as restrições são do tipo IgualdadeTodas as restrições são do tipo IgualdadeTodos os lados direitos (constantes) são não-negativasTodos os lados direitos (constantes) são não-negativasTodas as variáveis de decisão são não-negativasTodas as variáveis de decisão são não-negativas

Transformar um problema de Minimização em MaximizaçãoTransformar um problema de Minimização em Maximização

Minimizar Z = cMinimizar Z = c11xx11 + c + c22xx2 ......2 ......+ c+ cnnxxn n É equivalente a: É equivalente a:

Maximizar -Z = -cMaximizar -Z = -c11xx11 - c - c22xx2 ......2 ......- c- cnnxxnn

Transformar os lados direitos negativos em positivo bastando multiplicar tudo por (-1)Transformar os lados direitos negativos em positivo bastando multiplicar tudo por (-1)

Se aSe a1111xx11 + a + a1212xx2 ......2 ......+ a+ a1n1nxxn n ≤ -b≤ -b1 1 multiplica-se por -1multiplica-se por -1

--aa1111xx11 - a - a1212xx2 ......2 ......- a- a1n1nxxn n ≥ b≥ b1 1

Uma solução básica viável: é uma solução básica em que todas as m variáveis básicas Uma solução básica viável: é uma solução básica em que todas as m variáveis básicas são não-negativassão não-negativas

Forma padrão e Variáveis desvioForma padrão e Variáveis desvio

0s com

0s com

i11

i11

ji

n

jjiji

n

jjij

ji

n

jjiji

n

jjij

bsxabxa

bsxabxa

0,

C maq- h/sem 022 52

B maq- h/sem 80 2


2025max

21

21

21

21

21

xx

xx

xx

xx

xxz

Passando o exemplo anterior para a forma padrão

0,,,,

C maq- h/sem 022s 52

B maq- h/sem 80 2


0002025max

32121

321

221

121

32121

sssxx

xx

sxx

sxx

sssxxz

Interpretando a forma padrãoInterpretando a forma padrão

Na forma padrão as variáveis S são conhecidas por Slacks (folga) para as Na forma padrão as variáveis S são conhecidas por Slacks (folga) para as restrições do tipo <=, e para >= Surplus (excedente). restrições do tipo <=, e para >= Surplus (excedente).

No exemplo apresentado para x*No exemplo apresentado para x*11 =30 e x* =30 e x*22 = 20 obtém-se S = 20 obtém-se S3= 60 Há uma = 60 Há uma

sobra de 60 horas na máquina C.sobra de 60 horas na máquina C.

0,,,,


B maq- h/sem 80 2


0002025max

32121

321

221

121

32121

sssxx

xx

sxx

sxx

sssxxz

O Método Simplex

Usando a forma padrão do problema anterior tem-se

0,,,,


B maq- h/sem 80 2


0002025max

32121

321

221

121

32121

sssxx

xx

sxx

sxx

sssxxz

0 x

bx :a sujeito

.max

A

XCz

32121

,0002025 e ,

220

80

50

,

1

0

0

0

1

0

052

012

111

com

sssxxX

cbA

A sua resolução conduz a uma solução que será admissível se os valores resultantes para s1, s2 e s3 forem não negativos, ou não admissível, se

surgir algum valor negativo

Resolvendo o SimplexAtribui-se o valor zero as variáveis de não-básicas (x1 e x2 no exemplo) se obtendo como solução s1=50, s2 = 80 e s3 = 220 representando a quantidade não usada do

recurso.

Se deseja encontrar a solução ótima (quando ela existe) neste caso a maximização do lucro. Se ele existe e é finito está presente em pelo menos uma solução básica.

Assim o simplex opera obtendo as soluções básicas

Va BVa B Coeficiente das Variáveis Lado direito L

0

Z x1 x2 s1 s2 s3 b

1

1 -25 -20 0 0 0 0

2

S1=50 0 1 1 1 0 0 50

3

S2=80 0 2 1 0 1 0 80

4

S3=220 0 2 5 0 0 1 220

Escolhe-se o menor elemento da linha 1 para indicar a coluna pivô

Escolhe-se a linha com o menor valor de b positivo

Resolução do simplex


0

Z x1 x2 s1 s2 s3 b

1

1 0 -7,5 0 12,5 0 1000

2

x2=20 0 0 0,5 1 -0,5 0 10

3

X1=40 0 1 0,5 0 0,5 0 40

4

S3=220 0 0 4 0 -1 1 140

Substitui na linha 3 S2 por X1=40

Divide a linha 3 por 2 e multiplica por 25 e soma a linha 1 (25-25, 12,5-20, 0+0, 12,5+0, 0+0, 1000+0)

Divide a linha 3 por 2, subtraia linha 2 pela linha 3 (1-1, 1-0,5, 1-0, 0-0,5, 0-0, 50-40)

Subritai a linha 4 da 3 (2-2, 5-1, 0-0, 0-1, 1-0, 220-80)



0

Z x1 x2 s1 s2 s3 b

1

1 0 0 15 5 0 1150

2

x2=20 0 0 0,5 1 -0,5 0 10

3

X1=30 0 1 0 -1 1 0 30

4

S3=60 0 0 0 -8 3 1 60

Escolhe-se a linha 1 a coluna do menor coeficiente (-7,5) e a linha do menor b

Substitui S1 por x2 = 20 (10/0,5)

Divide a linha 2 por 0,5 e multiplica por 7,5 e soma a linha 1 (0+0,-7,5+7,5, 0+15, 12,5-7,5, 0+0, 1000+150)

subtraia linha 3 pela linha 2 (1-0, 0,5-0,5, 0-1, 0,5+0,5, 0-0, 40-10)

Multiplica a linha 2 por 8 e subtrai a linha 4 da 2 (0-0, 4-4, 0-8, -1+4, 1-0, 140-80)


Outro ExemploOutro Exemplo

A brinquedos S/A fabrica dois tipos de brinquedos de madeira: Soldados e A brinquedos S/A fabrica dois tipos de brinquedos de madeira: Soldados e Trens. Um soldado é vendido pro R$ 27,00 e usa R$ 10,00 de materia Trens. Um soldado é vendido pro R$ 27,00 e usa R$ 10,00 de materia prima. Cada sosldado fabricado aumenta os custos diretos e indiretos em prima. Cada sosldado fabricado aumenta os custos diretos e indiretos em R$ 14,00. Um term é vendido R$ 21,00 e usa R$ 9,00 de matéria prima. R$ 14,00. Um term é vendido R$ 21,00 e usa R$ 9,00 de matéria prima. Cada trem aumenta o custo de mão de obra e indiretos em R$ 10,00. A Cada trem aumenta o custo de mão de obra e indiretos em R$ 10,00. A fabricação requer dois tipo de mão de obra: carpinteiro e pintor. A fabricação requer dois tipo de mão de obra: carpinteiro e pintor. A fabricação de um soldado requer 2 horas de um pintor e 1 hora de um fabricação de um soldado requer 2 horas de um pintor e 1 hora de um carpinteiro. Um trem 1 hora de pintor e de carpinteiro. Para cada semana a carpinteiro. Um trem 1 hora de pintor e de carpinteiro. Para cada semana a brinquedos pode conseguir toda a matéria prima, mas apenas 100h de brinquedos pode conseguir toda a matéria prima, mas apenas 100h de pintura e 80 horas de carpintaria. A demanda de trens é ilimitada, mas a de pintura e 80 horas de carpintaria. A demanda de trens é ilimitada, mas a de soldado é no máximo 40 por semana. A brinquedos quer o máximo lucrosoldado é no máximo 40 por semana. A brinquedos quer o máximo lucro

Definindo o modelo

Usando a forma padrão do problema anterior tem-se

0,

40

acarpintari- h/sem 80

pintor- h/sem 001 2 :a sujeito

10149102127max

21

1

21

21

212121

xx

x

xx

xx

xxxxxxz

A sua resolução conduz a uma solução que será admissível se os valores resultantes para s1, s2 e s3 forem não negativos, ou não admissível, se

surgir algum valor negativo

0,,,,

tremde produção h/sem 40 s

acarpintari- h/sem 80

pintor- h/sem 001 2 :a sujeito

00023max

32121

31

221

121

32121

sssxx

x

sxx

sxx

sssxxz


0

Z x1 x2 s1 s2 s3 b

1

1 -3 -2 0 0 0 0

2

S1=50 0 2 1 1 0 0 100

3

S2=80 0 1 1 0 1 0 80

4

S3=40 0 1 0 0 0 1 40

Escolhe-se o menor elemento da linha 1 para indicar a coluna pivô

Escolhe-se a linha com o menor valor de b positivo, linha 4



0

Z x1 x2 s1 s2 s3 b

1

1 0 -2 0 0 3 120

2

S1=50 0 0 1 1 0 -2 20

3

S2=80 0 0 1 0 1 -1 40

4

X1=40 0 1 0 0 0 1 40

Substitui Va B S3 por X1 = 40

Multiplica a linha 4 por 3 e soma com a linha 1 (3-3, 0-2, 0+0, 0+0, 3+0, 120+0)

Multiplica a linha 4 por 2, subtrai a linha 2 da linha 4 (2-2, 1-0,1-0, 0-0,0-2,100-80)

Subitrai a linha 3 da 4 (1-1, 1-0, 0-0, 1-0, 0-1, 80-40)



0

Z x1 x2 s1 s2 s3 b

1

Z=120 1 0 -2 0 0 3 120

2

X2=20 0 0 1 1 0 -2 20

3

S2=40 0 0 1 0 1 -1 40

4

X1=40 0 1 0 0 0 1 40

Escolhe-se x2 da linha 2

Multiplica a linha 2 por 2 e soma com a linha 1 (0-0, 2-2, 2+0, 0+0, -6+3, 120+40)

Multiplica a linha 2 por -1, soma a linha 2 da linha 3 (0-0, 1-1,0-1, 1-0,-1+2,40-20)

Multiplica a linha 2 por 0, soma 2 da 4 (1+0, 0+0, 0+0, 0+0, 1+0, 40+0)



0

Z x1 x2 s1 s2 s3 b

1

1 0 0 2 0 -1 160

2

x2=20 0 0 1 1 0 -2 20

3

S3=20 0 0 0 -1 1 1 20

4

X1=40 0 1 0 0 0 1 40

Escolhe-se a coluna da linha 1 com o menor coeficiente, escolhe-se a linha da coluna com o menor valor de b

No caso s3 da linha 3, substitui-se a VB de S2 por S3

soma a linha 3 da linha 1 (0+0, 0+0, -1+2, 1+0, 1-1, 20+160) substitui linha 1

Multiplica a linha 3 por 2 e soma com a linha 2 (0+0, 1+0, 1-2, 0+2, -2+2, 40+20) substitui linha 2

Subtrai a Linha 4 da linha 3 (1-0, 0-0, 0+1, 0-1, 1-1, 40-20) substitui linha 4



0

Z x1 x2 s1 s2 s3 b

1

Z=180 1 0 0 1 1 0 180

2

x2=60 0 0 1 -1 2 0 60

3

S3=20 0 0 0 -1 1 1 20

4

X1=20 0 1 0 1 -1 0 20

Escolhe-se a coluna da linha 1 com o menor coeficiente, escolhe-se a linha da coluna com o menor valor de b

No caso s3 da linha 3, substitui-se a VB de S2 por S3

soma a linha 3 da linha 1 (0+0, 0+0, -1+2, 1+0, 1-1, 20+160) substitui linha 1

Multiplica a linha 3 por 2 e soma com a linha 2 (0+0, 1+0, 1-2, 0+2, -2+2, 40+20) substitui linha 2

Subtrai a Linha 4 da linha 3 (1-0, 0-0, 0+1, 0-1, 1-1, 40-20) substitui linha 4


Adaptação para outros casoAdaptação para outros casoVariáveis artificiais e Método do Grande MVariáveis artificiais e Método do Grande M

n

pk

akpp xMxcxcxcz

12211 .....

Exemplo

0,

73

52 : s.a.

3max

21

21

21

21

xx

xx

xx

xxzUsando o método

0,,,,

73

52 : s.a.

3max

51121

421

321

521

a

a

xefxx

fxx

exx

Mxxxz

Va BVa B Coeficiente das Variáveis Lado direito

L

0 Z x1 x2 e3 f4 x5a b

1 1 -3 1 0 0 M 0

2 x5a=5 0 2 1 -1 0 1 5

3 f4=7 0 3 1 0 1 0 7

Busca-se eliminar o M da variável fazendo

Multiplica a linha 2 por -M e soma de L1 – substitui L1(-3-2M, 1-1M,M+0, 0+0, M-M, -5M)

Mantém-se as demais


ax5

ExemploExemploVa BVa B Coeficiente das Variáveis Lado direito

L

0

Z x1 x2 e3 f4 x5a b

1

Z=-5M 1 -3-2M 1-M M 0 0 -5M

2

x5a=5 0 2 1 -1 0 1 5

3

f4=7 0 3 1 0 1 0 7

Escolhe o pivô da mesma forma que anteriormente: o menor coeficiente da linha 1 (define a coluna) e na coluna o menor valor de b

Substitui f4 por x1=7

Multiplica a linha 3 por 1+2/3M soma com a linha 1: (3+2M-3-2M; 1+2/3M+1-M; M+1+2/3M; 1+2/3M, 0+0, 1+2/3M-5M) substitui linha 1

ExemploExemploVa BVa B Coeficiente das Variáveis Lado direito L

0 Z x1 x2 e3 f4 x5a b

1 Z=-5M 1 0 2-1/3M M 1+2/3M 0 7-M/3

2 x5a=5 0 2 1 -1 0 1 5

3 f4=7 0 3 1 0 1 0 7




Divide a linha 3 e multiplica por 2; subtrai a linha 2 da linha 3; (2-2; 1-2/3; -1-0, 0-2/3; 5-7*2/3) substitui a linha 2


0 Z x1 x2 e3 f4 x5a b

1 Z=7-M/3 1 0 2-1/3M M 1+2/3M 0 7-M/3

2 x5a=1/3 0 0 1/3 -1 -2/3 1 1/3

3 x1=7/3 0 1 1/3 0 1/3 0 7/3




Divide a linha 3 e multiplica por 2; subtrai a linha 2 da linha 3; (2-2; 1-2/3; -1-0, 0-2/3; 5-7*2/3) substitui a linha 2


0 Z x1 x2 e3 f4 x5a b

1 Z=7-M/3 1 0 2-1/3M M 1+2/3M 0 7-M/3

2 x2=1 0 0 1/3 -1 -2/3 1 1/3

3 x1=7 0 1 1/3 0 1/3 0 7/3


Substitui x5a por 1

Multiplica a linha 2 por -6+M soma com a linha 1: (0-0; -2+1/3M+2-1/3M; 6-M+M; 1+2/3M-4-2/3M; -6+M+0; -2+1/3M+7-M/3) substitui linha 1

subtrai a linha 3 da linha 2; (1-0; 1/3-1/3; 0+1, 1/3+2/3; 0-1, 7/3-1/3) substitui a linha 3


0 Z x1 x2 e3 f4 x5a b

1 Z=5 1 0 0 6 5 M-6 5

2 x2=1 0 0 1 -3 -2 3 1

3 x1=2 0 1 0 1 1 -1 2

Como não há coeficientes negativos na linha 1, não há mais espaço para melhorias e a solução básica é a ótima

GeneralizaçãoGeneralizaçãoSeja um problema de PL escrito na forma padrão com n variáveis (incluindo as variáveis de decisão e as desvio) e m restrições funcionaisSeja um problema de PL escrito na forma padrão com n variáveis (incluindo as variáveis de decisão e as desvio) e m restrições funcionais

0 x

0b bx :a sujeito

.max

A

XCz

O método simplex opera do seguinte modo : determina uma solução básica admissível inicial

Enquanto a solução atual não for ótima:

-Seleciona a variável não básica que se tornará básica;

- Determina a variável básica que se tornará não básica;

- atualiza o quadro simplex usando a eliminação de Gauss

bx a b' x'' AA

Em cada rodada constroe um sistema equivalente

0 x

0b bx :a sujeito

.max

A

XCz

Dualidade em PLDualidade em PLTodo problema de PL tem um outro problema associado chamado de Dual ( original o Primal). Um pode ser tranformado no outro embora tenham características diferentes apresentam a mesma solução ótima

Como é mais fácil resolver um problema com mais restrições do que variáveis a dualidade lea a dois resultados importantes:

facilita a solução do problema

Permite um melhor entendimento do problema

No primalNo primalMIN Z = cMIN Z = c11XX11 + c + c22XX22 + ... + c + ... + cnnXXnn

Sujeito a: Sujeito a: aa1111XX1 1 + a+ a1212XX2 2 + ... + a+ ... + a1n1nXXnn b b11

aak1k1XX1 1 + a+ ak2k2XX2 2 + ... + a+ ... + aknknXXnn b bkk

aam1m1XX1 1 + a+ am2m2XX2 2 + ... + a+ ... + amnmnXXnn b bmm

inviável terádual o ilimitada solução tiver Primal um Se

...

...

... :a Sujeito

.... oMazimizaçã de Dual

2211

22222112

11221111

1 1

nmmnnn

mm

mm

mm

cyayaya

cyayaya

cyayaya

ybybw

Transformação do dual em primalTransformação do dual em primal

0,, 42

121 3

211- 1 :a Sujeito

43min 2max

dualseu em or Transforma

32121

32121

32121

32121

xxxyy

xxxyy

xxxyy

xxxZyy w

0, 0,

312 2

613 123 :a Sujeito

2min 36min

dualseu em or Transforma

2121

2121

2121

2121

yyxx

yyxx

yyxx

yywxxZ

Aplicações reais

Para facilitar o processo de modelagem devemos responder as seguintes perguntas:

Quem decide ?

O que decide ?

Para que decide ?

Com que restrições ?

Decisão do tipo fazer ou comprarDecisão do tipo fazer ou comprarCaso LCL Motores LTDACaso LCL Motores LTDAA LCL Motores Ltda, uma fábrica de motores especiais, recebeu recentemente R$ A LCL Motores Ltda, uma fábrica de motores especiais, recebeu recentemente R$

900.000,00 em pedidos de seus três tipos de motores. Cada motor necessita de 900.000,00 em pedidos de seus três tipos de motores. Cada motor necessita de determinado número de horas de trabalho no setor de montagem e de acabamento. A determinado número de horas de trabalho no setor de montagem e de acabamento. A LCL pode terceirizar parte da sua produção. A tabela abaixo resume esses dados. A LCL pode terceirizar parte da sua produção. A tabela abaixo resume esses dados. A fábrica deseja determinar quantos motores ela deve produzir e quantos devem ser fábrica deseja determinar quantos motores ela deve produzir e quantos devem ser produzidos de forma terceirizada para atender a demanda de pedidosproduzidos de forma terceirizada para atender a demanda de pedidos

ModeloModelo 11 22 33 totaltotal

demandademanda 3.000 u3.000 u 2.500 u2.500 u 500 u500 u 6.000 u6.000 u

MontagemMontagem 1h/u1h/u 2h/u2h/u 0,5h/u0,5h/u 6.000 horas6.000 horas

AcabamentoAcabamento 2,5 h/u2,5 h/u 1h/u1h/u 4h/u4h/u 10.000 horas10.000 horas

Custo Prod.Custo Prod. R$ 50,00R$ 50,00 R$ 90,00R$ 90,00 R$ 120,00R$ 120,00

TerceirizaçãoTerceirização R$ 65,00R$ 65,00 R$ 92,00R$ 92,00 R$ 140,00R$ 140,00

SoluçãoSoluçãoQuem decide? O tomador de decisão – o gerente de fábricaQuem decide? O tomador de decisão – o gerente de fábricaO que decide? A quantidade de motores de cada tipo que deve ser fabricado e quantos devem ser a O que decide? A quantidade de motores de cada tipo que deve ser fabricado e quantos devem ser a produção terceirizada. Logo as variáveis de decisão são:produção terceirizada. Logo as variáveis de decisão são:F1 unidades de motores do modelo 1 fabricado pela LCLF1 unidades de motores do modelo 1 fabricado pela LCLF2 unidades de motores do modelo 2 fabricado pela LCLF2 unidades de motores do modelo 2 fabricado pela LCL

F3 unidades de motores do modelo 3 fabricado pela LCLF3 unidades de motores do modelo 3 fabricado pela LCL T1 unidades de motores do modelo 1 terceirizadoT1 unidades de motores do modelo 1 terceirizado T2 unidades de motores do modelo 2 terceirizadoT2 unidades de motores do modelo 2 terceirizado T3 unidades de motores do modelo 3 terceirizadoT3 unidades de motores do modelo 3 terceirizadoPara que decide? Maximizar o lucro da LCL, ou seja,Para que decide? Maximizar o lucro da LCL, ou seja,Max Lucro 900000 – (50F1+ 90F2 + 120 F3 + 65 T1 + 92 T2 + 140 T3) que equivale a obter o mínimo Max Lucro 900000 – (50F1+ 90F2 + 120 F3 + 65 T1 + 92 T2 + 140 T3) que equivale a obter o mínimo

custo: custo: Min Z = 50F1+ 90F2 + 120 F3 + 65 T1 + 92 T2 + 140 T3Min Z = 50F1+ 90F2 + 120 F3 + 65 T1 + 92 T2 + 140 T3Com que restrições:Com que restrições:De montagem F1+ 2F2 + 0,5F3 De montagem F1+ 2F2 + 0,5F3 ≤ 6.000≤ 6.000De acabamento 2,5F1 +1F2 + 4F4 ≤ 10.000De acabamento 2,5F1 +1F2 + 4F4 ≤ 10.000De demanda F1 + T1 = 3.000 motor tipo 1De demanda F1 + T1 = 3.000 motor tipo 1 F2 + T2 = 2.500 motor tipo 2F2 + T2 = 2.500 motor tipo 2 F3 + T3 = 500 motor tipo 3F3 + T3 = 500 motor tipo 3

0 são T e F os todosonde 50011

500.211

000.311

000.1041,52

000.65,021 s.a.

14092651209050

33

22

11

321

321

321321

TF

TF

TF

FFF

FFF

TTTFFFMin

Escolha de carteira de investimentoEscolha de carteira de investimentoA LCL Investimentos gerencia recursos de terceiros por meio da escolha de carteiras de A LCL Investimentos gerencia recursos de terceiros por meio da escolha de carteiras de

investimento para diversos clientes, com base em bonds de diversas empresas. Um investimento para diversos clientes, com base em bonds de diversas empresas. Um dos seus clientes exige que:dos seus clientes exige que:

Não mais de 25% aplicado deve ser investido em um único investimentoNão mais de 25% aplicado deve ser investido em um único investimentoUm valor superior a 50% do total aplicado deve ser investido em títulos de maturidade Um valor superior a 50% do total aplicado deve ser investido em títulos de maturidade

maiores que dez anosmaiores que dez anosO total aplicado em títulos de alto risco deve ser no máximo de 50% de total investido. A O total aplicado em títulos de alto risco deve ser no máximo de 50% de total investido. A

tabela abaixo mostra os dados dos títulos selecionados e mostra o % do total deve ser tabela abaixo mostra os dados dos títulos selecionados e mostra o % do total deve ser aplicado em cada tipo de tituloaplicado em cada tipo de titulo

Retorno anualRetorno anual Anos de vencAnos de venc RiscoRisco

Titulo1Titulo1 8,7%8,7% 1515 1-muito baixo1-muito baixo

Titulo2Titulo2 9,5%9,5% 1212 3-regular3-regular

Titulo3Titulo3 12,0%12,0% 88 4-alto4-alto

Titulo4Titulo4 9,0%9,0% 77 2-baixo2-baixo

titulo5titulo5 13,0%13,0% 1111 4-alto4-alto

Titulo6Titulo6 20,0%20,0% 55 5-muito alto5-muito alto

SoluçãoSolução

Variáveis de decisãoVariáveis de decisãoP1 – percentual de participação do total aplicado no titulo tipo 1P1 – percentual de participação do total aplicado no titulo tipo 1P2 – percentual de participação do total aplicado no titulo tipo 2P2 – percentual de participação do total aplicado no titulo tipo 2P3 – percentual de participação do total aplicado no titulo tipo 3P3 – percentual de participação do total aplicado no titulo tipo 3P4 – percentual de participação do total aplicado no titulo tipo 4P4 – percentual de participação do total aplicado no titulo tipo 4P5 – percentual de participação do total aplicado no titulo tipo 5P5 – percentual de participação do total aplicado no titulo tipo 5P6 – percentual de participação do total aplicado no titulo tipo 6P6 – percentual de participação do total aplicado no titulo tipo 6

Para que decide? O objetivo é fornecer o maior retorno anual possível, considerando Para que decide? O objetivo é fornecer o maior retorno anual possível, considerando as restrições impostas logo:as restrições impostas logo:

Max Lucro= 0,087*P1/100 + 0,095*P2/100 + 0,12*P3/100 + 0,09*P4/100 + Max Lucro= 0,087*P1/100 + 0,095*P2/100 + 0,12*P3/100 + 0,09*P4/100 + 0,13*P5/100 + 0,20*P6/1000,13*P5/100 + 0,20*P6/100

Restrições:Restrições:P1 + P2 + P3 + P4 + P5 + P6P1 + P2 + P3 + P4 + P5 + P6 = 100 E = 100 E P1, P2, P3, P4, P5, P6P1, P2, P3, P4, P5, P6 ≤ 25 ≤ 25P1 + P2 + P5 ≥ 50 E P3 + P5 + P6 ≤ 50 P1 + P2 + P5 ≥ 50 E P3 + P5 + P6 ≤ 50

0,,,,,

50

50

25,,,,,

100 s.a.100

02,0100

13,0100

90,0100

12,0100

095,0100

,0870

654321

653

521

654321

654321

654321

PPPPPP

PPP

PPP

PPPPPP

PPPPPP

PPPPPPMAX

Escala de funcionáriosEscala de funcionáriosA LCL Correios e Molotes deseja determinar o número de funcionários de A LCL Correios e Molotes deseja determinar o número de funcionários de

horários integral que deve contratar para iniciar as suas atividades. Para horários integral que deve contratar para iniciar as suas atividades. Para fazê-lo, recebeu uma tabela da ECT com o número mínimo de funcionários fazê-lo, recebeu uma tabela da ECT com o número mínimo de funcionários para o dia da semana. Essa informação encontra-se na tabela a seguirpara o dia da semana. Essa informação encontra-se na tabela a seguir

Dia da semanaDia da semana N de funcionáriosN de funcionários

DomingoDomingo 1111

SegundaSegunda 1818

TerçaTerça 1212

QuartaQuarta 1515

QuintaQuinta 1919

SextaSexta 1414

SábadoSábado 1616

O sindicato dos funcionários mantém um acordo sindical que determina que cada empregado deve trabalhar 5 dias consecutivos e folgar em seguida 2 dias.

E que só deve ter funcionários de horário integral

O que decide?O que decide?Deve-se determinar quantas pessoas devem trabalhar cada dia e quantas devem ser Deve-se determinar quantas pessoas devem trabalhar cada dia e quantas devem ser contratadas no total. Considere a variável de decisão Ni o número de empregados que contratadas no total. Considere a variável de decisão Ni o número de empregados que irá iniciar o trabalho no dia i. Logo deseja-se:irá iniciar o trabalho no dia i. Logo deseja-se:

0,,,,

15

12

18

11

16

14

19 s.a.

in

54321

43217

32176

21765

17654

76543

65432

54321

7654321

NNNNN

NNNNN

NNNNN

NNNNN

NNNNN

NNNNN

NNNNN

NNNNN

NNNNNNNM

Análise de sensibilidade de PLAnálise de sensibilidade de PL

Após a aplicação de qualquer modelo, é sempre recomendado que se faça Após a aplicação de qualquer modelo, é sempre recomendado que se faça uma análise de sensibilidade do modelo aplicado.uma análise de sensibilidade do modelo aplicado.

Avalia-se quão sensível é o modelo em relação a variação em seus Avalia-se quão sensível é o modelo em relação a variação em seus parâmetros – avalia-se a robustez do modeloparâmetros – avalia-se a robustez do modelo

Nos modelos de PL nem sempre os coeficientes ci, aij, bj são conhecidos com Nos modelos de PL nem sempre os coeficientes ci, aij, bj são conhecidos com certeza.certeza.

Em algumas situações é preciso fazer alterações dos valores de determinados Em algumas situações é preciso fazer alterações dos valores de determinados coeficientes iniciais, e um estudo de análise de sensibilidade pode mostrar coeficientes iniciais, e um estudo de análise de sensibilidade pode mostrar se após tais alterações a solução ótima encontrada para o modelo original se após tais alterações a solução ótima encontrada para o modelo original se mantém.se mantém.

Casos estudados: Casos estudados: Nos coeficientes das variáveis na função objetivoNos coeficientes das variáveis na função objetivoMudanças nas constantes (preços sombra)Mudanças nas constantes (preços sombra)Mudanças nas restrições (incluir novas variáveis, mudar coeficientes, incluir Mudanças nas restrições (incluir novas variáveis, mudar coeficientes, incluir novas restrições, retirar variáveis, retirar restrições)novas restrições, retirar variáveis, retirar restrições)

Caso de duas variáveisCaso de duas variáveis

Mudança de cjMudança de cj

0,

92

104 s.a.

25

21

21

21

21

xx

xx

xx

xxMaxZ

Z=0X1=11/7

X2=26/7

1212

12

2/12/9 (b) de e 410 : se- tiraa de2

5

2: tirarpodemos objetivo Dafunção

xxxx

xz

x

Declividade Declividade da linha Bda linha B

Declividade Declividade da F.O da F.O

Declividade Declividade da linha Ada linha A

-4-4 =<-c1/c2=<=<-c1/c2=< -1/5-1/5

Esta análise deve ser feita variando apenas um dos coeficientes de cada vez

Mudança nas constantes bjMudança nas constantes bjEsta mudança geralmente acarreta um alteração no conjunto das soluções viáveis. A Esta mudança geralmente acarreta um alteração no conjunto das soluções viáveis. A

alteração resultante no valor da função objetivo é chamado de Preço SOMBRA.alteração resultante no valor da função objetivo é chamado de Preço SOMBRA.

Economicamente eles representam o quanto a função objetivo poderia ser Economicamente eles representam o quanto a função objetivo poderia ser melhorada, caso a quantidade de recurso/ representada por bj fosse aumentada melhorada, caso a quantidade de recurso/ representada por bj fosse aumentada em uma unidadeem uma unidade

0,

92

104 s.a.

25

21

21

21

21

xx

xx

xx

xxMaxZ

sombra preçopreço o vezes5 a ecorrespond valor novo o

ótima solução a muda valor esse 154 para (a) restição a Alterando

ótima solução a limita não

restrição a pois, ótimo, do valor o altera não mudança essa 152

:para (b) restrição a Alterando

21

21

xx

xx

Documents

Aula 3 Programação Linear - SIMPLEX Curso de Administração Prof: André Marques Cavalcanti