PROGRAMACAO LINEAR

MS428

Tuesday, 19 de novembro de 2013, 15:56

PROGRAMACAO LINEAR

➊ Introducao

➋ Modelos

➌ Otimalidade

➍ Metodo Simplex

➎ Metodo de Pontos Interiores

➏ PL na Pratica

♣ Informacao

♥ Exercıcios

♠ Provas

I - INTRODUCAO

➀ Matematica Aplicada e Pesquisa Operacional

➁ Etapas de Aplicacao

➂ Problema, Exemplar e Modelo

➃ Metodo, Algoritmo e Programa

➄ Problema de Carga de Maquina

➅ Hipoteses da Programacao Linear

➀ Matematica Aplicada e Pesquisa Operacional

Curso de Matematica Aplicada: Producao

• Calculo

• Fısica

• Probabilidade & Estatıstica

• Computacao

• Analise Numerica

• Pesquisa Operacional

◦ MS428 – Programacao Linear

◦ MS528 – Fluxos em Redes

◦ MS628 – Programacao Nao Linear

◦ MS728 – Otimizacao Combinatoria

◦ MS515 – Modelos Probabilısticos (Estoques & Filas)

◦ MS715 – Planejamento e Controle da Producao

Pesquisa Operacional: Ferramentas

• Programacao Linear

• Programacao Nao-Linear

• Fluxos em Redes

• Programacao Inteira

• Otimizacao Combinatoria

• Programacao Dinamica

• Teoria de Decisoes

• Teoria de Filas

• Teoria de Estoques

• Simulacao de Sistemas

• etc.

Aplicacoes em Planejamento

• transportes

• comunicacoes

• energia

• redes hidraulicas

• sequenciamento

• alocacao

• localizacao

• producao & distribuicao – supply-chain

• etc.

Aplicacoes em Manufatura

• avaliacao de capital para equipamentos

• reducao de estoque em processo (work-in-process)

• planejamento de manutencao

• manipulacao de material

• layout de fabrica

• just-in-time e tecnologia de grupo

• planejamento de capacidade

• programacao de chao de fabrica

• balanceamento de linhas

• avaliacao de tecnologias

• etc.

Aplicacoes em Supply Chain e Logıstica

• gerenciamento de inventario e materiais

• distribuicao e armazenamento

• planejamento de transporte

• processamento de pedidos

• empacotamento

• garantia de qualidade

• planejamento de munutencao

• nıveis de servico ao cliente

• confiabilidade e disponibilidade

• suporte de produtos

• etc.

➁ Etapas da Pesquisa Operacional

��

�✠

��

�✠

❅❅❅❘

❅❅❅❘

❄

Problema

Sistema

Modelo

Metodo

Solucao

Decisao

✻

REALIMENTAC~AO

Ambiente

Real

Espaço

Matemáti o

Equipamento

Computa ional

Etapas da Pesquisa Operacional

☛ estudar problema a resolver (mundo real)

☛ identificar sistema envolvido no problema

☛ construir modelo matematico que representa o sistema

☛ utilizar metodo computacional para obter solucao

☛ transformar solucao matematica em decisao

☛ implementar decisao no ambiente real

☛ usar realimentacao, quando necessario

➂ Problema, Exemplar e Modelo

Problema s.m.

1. Questao matematica proposta para que se lhe de solucao.

2. Questao nao solvida, ou de solucao difıcil.

Wikipedia: Questao proposta em busca de uma solucao.

Sistema – estrutura de subsistemas interconectados que operam

sob certas restricoes para atingir determinados objetivos.

Item – objeto importante processado por subsistemas:

produto, materia prima, peca, refugo, etc.

Componente – subsistema importante que desenvolve uma ativi-

dade propria, cujo nıvel define a quantidade de itens processados.

C1

C2

C3✲

✲

✲

✲✲

✲

I1

I2

I3

I4

I5

Sistema com 3 componentes e 5 itens

Modelo – representacao simplificada do sistema

(conjunto de equacoes e desigualdades matematicas)

Metodo – procedimento ou algoritmo utilizado para obter o

resultado desejado, compatıvel com o modelo

Solucao – meio matematico de resolver um problema

Decisao – operacionalizacao da solucao

Modelo

• concreto × abstrato (conceitual)

• fısico × matematico

• fechado × aberto (interacao com o meio ambiente)

• analıtico × numerico (nao fornece solucoes analıticas)

• estatico × dinamico (para observacoes ao longo do tempo)

• explicativo × preditivo

• determinıstico × estocastico (incertezas) × nebuloso

◦ discreto aperiodico (alteracoes instantaneas – eventos),

◦ discreto periodico (alteracoes a intervalos regulares),

◦ contınuo (alteracoes suaves) [comp. analogico]

Comecar com modelo simples e acrescentar detalhes necessarios.

Nıvel de detalhe no modelo depende dos objetivos do estudo.

Modelo deve replicar o comportamento do sistema.

‘Mandamentos’ – Ravindran, Phillips & Solberg

• Nao usar modelo complexo se basta um simples

• Ha benefıcios primarios na modelagem

• Validar modelo antes de implementar

◦ Nao forcar hipoteses simplificadoras

◦ Nao forcar metodo de solucao

• Nao sobrevalorizar modelo nem suas respostas

◦ Modelo nao melhora informacao que utiliza

◦ Modelo desconhece detalhe nao modelado

◦ Modelo nao substitui tomador de decisao

➃ Metodo, Algoritmo e Programa

Metodos para PL

Pontos Extremos ( convergencia finita )

– simplex primal, simplex dual

Pontos Interiores

– elipsoide, transformacao projetiva (polinomiais)

– seguidor de caminho, transformacao afim

Especializacoes e extensoes

– variaveis canalizadas e livres, restricoes canalizadas

– geracao de colunas, programacao fracionaria

– programacao em redes (fluxos)

– programacao convexa com objetivo quadratico

– etc.

➄ Problema de Carga de Maquina

Pecas P1,P2 sao fabricadas nos centros de producao C1,C2,C3

Centro Peca Disponibilidade

P1 P2 (horas)

C1 1 2 60

C2 2 1 60

C3 1 0 25

Lucro 20 22 (Maximizar)

Cada P1 tem $20 de lucro e gasta 1h,2h,1h de C1,C2,C3

Cada P2 tem $22 de lucro e gasta 2h,1h,0h de C1,C2,C3

Producao que maximiza o lucro total?

✬✫

✩✪C1

✬✫

✩✪C2

✬✫

✩✪C3

ProduzirP1 em C1

ProduzirP1 em C2

ProduzirP1 em C3

ProduzirP2 em C1

ProduzirP2 em C2

✛

✛ ✲

✛ ✲

✻✻ ✻ ✻✻$20 $22

2

2

1

1

1

60

60

20

Modelo com 5 variaveis em 6 restricoes: q11, q12, q13, q21, q22/ qij – qtde. a produzir de Pi em Cj, i = 1..2, j = 1..3

variaveis de decisao:

qij – qtde. a produzir de Pi em Cj, i = 1..2, j = 1..3

max 20q11 + 22q21suj q11 + 2q21 ≤ 60 (C1)

2q12 + q22 ≤ 60 (C2)q13 ≤ 25 (C3)q11 − q12 = 0q12 − q13 = 0q21 − q22 = 0

qij ≥ 0

Modelo mais simples

✬

✫

✩

✪C3

✬

✫

✩

✪C2

✬

✫

✩

✪C1

Produzir P1

Produzir P2

✲

✲

✲

✲

✲

✲ $

✲ $

variaveis de decisao:

x1 – quantidade da peca P1

x2 – quantidade da peca P2

max 20x1 + 22x2suj x1 + 2x2 ≤ 60 (C1)

2x1 + x2 ≤ 60 (C2)x1 + ≤ 25 (C3)x1 , x2 ≥ 0

0

20

40

60

0 20 40 60

x1

x2

(C1) : x1+2x2≤60

(C2) : 2x1+x2≤60

(C3) : x1≤25

20x1+22x2=440

ր

∗ x∗=(20,20)

Primal:

x=(20,20)$840

max 20x1 + 22x2suj x1 + 2x2 ≤ 60 (C1)

2x1 + x2 ≤ 60 (C2)x1 + ≤ 25 (C3)x1 , x2 ≥ 0

Dual:

y=(8,6,0)$840

min 60y1 + 60y2 + 25y3suj y1 + 2y2 + y3 ≥ 20 (P1)

2y1 + y2 ≥ 22 (P2)y1 , y2 , y3 ≥ 0

Folgas:

(60− x1 − 2x2) y1 = 0 (C1)(60− 2x1 − x2) y2 = 0 (C2)

(25− x1) y3 = 0 (C3)(y1 +2y2 + y3 − 20) x1 = 0 (P1)

(2y1 + y2 − 22) x2 = 0 (P2)

➅ Hipoteses da PL

Hipoteses da PL

• Modelo determinıstico aij, bi, cj ∈ ℜ

• Variaveis contınuas xj ∈ ℜ

• Proporcionalidade ( cjxj ), ( aijxj )

• Aditividade (∑

j cjxj ), (∑

j aijxj )

minx{ c′x : Ax = b, x≥0 }

II - MODELOS

➀ Racao (Dieta)

➁ Producao

➂ Multiproduto

➃ Estoque (Multiperıodo)

➄ Transporte

➅ Mistura

Etc

⊛ Questoes

Racao ( Dieta ) *

Racao de menor custo (Alimentos A1..A4 × Nutrientes N1..N2)

A = (aij) A1 A2 A3 A4 min.b

N1 2 3 1 2 7

N2 3 2 3 2 9

custo c 50 60 30 40

min 50x1 + 60x2 + 30x3 + 40x4suj 2x1 + 3x2 + x3 + 2x4 ≥ 7

3x1 + 2x2 + 3x3 + 2x4 ≥ 9x1 , x2 , x3 , x4 ≥ 0

x = (xj): qtde. de alimento na racao ( j = 1..4, i = 1..2 )

geral: min{ c′x : Ax≥b, x≥0 }

Producao *

Producao de maior lucro (Produtos P1..P2 × Insumos I1..I3)

A = (aij) P1 P2 max.b

I1 1 2 6000

I2 2 1 6000I3 1 0 2500

lucro c 22 20

max 22x1 + 20x2

suj x1 + 2x2 ≤ 60002x1 + x2 ≤ 6000x1 ≤ 2500x1 , x2 ≥ 0

x = (xj): qtde. de produto ( j = 1..2, i = 1..3 )

geral: max{ c′x : Ax≤b, x≥0 }

Multiproduto *

d : demanda

ck : lucro de producao da fabrica k

bk : disponibilidade de insumos na fabrica k

A : matriz de producao ( insumo×produto )

Producao de maior lucro (Produtos × Insumos × Fabricas)

xkj : qtde. do produto j na fabrica k

geral: max{

∑

k(ck)′xk : Axk≤bk, ∑

k xk≤d, xk≥0

}

A b1. . . ...

A bk

I · · · I d

x1

x2

...xk

Estoque ( Multiperıodo ) *

ck : custos de producao no perıodo k

dk : custos de estocagem no perıodo k

bk : demandas no perıodo k

Producao/estocagem de menor custo durante os perıodos

xk : qtdes. produzidas no perıodo k

sk : qtdes. estocadas p/ perıodo k (s0 fixo)

min{

∑(ck)′xk +

∑(dk)′sk : sk-1 + xk − sk = bk, xk, sk≥0

}

I I −I b1

I I −I b2. . . . . . . . . ...

I I −I bk

s0

x1

s1...xk

sk

Transporte *

Transporte de menor custo (Minas M1..M2 para Fabricas F1..F3)

c = (cij) F1 F2 F3 Qmax a

M1 11 12 13 301

M2 21 22 23 302

Qmin b 200 201 202

M1 F1

F2

M2 F3

xij : qtde. de minerio de mina para fabrica ( i = 1..2, j = 1..3 )

min 11x11 +12x12 +13x13 +21x21 +22x22 +23x23suj x11 +x12 +x13 ≤301

x21 +x22 +x23 ≤302x11 +x21 ≥200

x12 +x22 ≥201x13 +x23 ≥202

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

Transporte:

geral: min{

∑

ij cijxij :∑

j xij≤ai, ∀i;∑

i xij≥bj, ∀j; xij≥0, ∀i, j}

Mistura

Producao de menor custo: Minas M1..M2 × Pilhas P1..P3

c = (cij) P1 P2 P3 Qmax a teor

M1 11 12 13 301 60

M2 21 22 23 302 68

Qmin b 200 201 202

teor min 62 64 66

M1 F1

F2

M2 F3

xij : qtde. do minerio Mi na pilha Pj ( i = 1..3, j = 1..2 )

teor da pilha P1: −2x11 +6x12≥060x11+68x21

x11+x21≥62 ⇒ (60-62)x11 + (68-62)x21≥0

max 11x11 +12x12 +13x13 +21x21 +22x22 +23x23suj x11 +x12 +x13 ≤ 301

x21 +x22 +x23 ≤ 302x11 +x21 ≥ 200

x12 +x22 ≥ 201x13 +x23 ≥ 202

−2x11 +6x21 ≥ 0−4x12 +4x22 ≥ 0

−6x13 +2x23 ≥ 0x11, x12, x13, x21, x22, x23 ≥ 0

Mistura:

min{

∑

ij cijxij :∑

j xij≤ai,∑

i xij≥bj,∑

i dijxij≥0, xij≥0}

Alocacao

Alocar pedidos Pj as maquinas Mi (em paralelo).

αij: tempo de cada unidade de Pj em Mi

βj: quantidade pedida em Pj

δi: disponibilidade de Mi

γi: custo por unidade de tempo em Mi

α P1 P2 P3 P4 δ γ

M1 2 3 3 4 1200 22

M2 4 5 6 5 1500 45

β 110 120 130 140

xij: tempo da maquina Mi alocado para o pedido Pj.

min{ ∑

ij

γixij :∑

j

xij ≤ δi,∑

i

xij/αij = βj, x≥0}

ou© qij: qtde do pedido Pj alocado na maquina Mi.

min{ ∑

ij

γiαijqij :∑

i

qij = βj,∑

j

αijqij ≤ δi, q≥0}

Estrategia de E/S

A1

A2

A3✲

✲

✲✲ ✲

✲

R1

R2

R3

R4

R5

a11 0 00 a21 00 0 a330 a42 0a51 0 a53

[x1

x2

x3

]

= Ax = b =

b1b2b3b40

Listas completas de recursos Ri e de atividades Aj.

Modelo Ax=b, x≥0 com matriz A de recurso×atividade.

xj: nıvel que a atividade Aj devera ser desenvolvida (incogita)

aij=0: se o recurso Ri nao e utilizado pela atividade Aj

aij>0 (<0): Aj consome (produz) aijxj unidades de Ri

bi>0 (<0): atividades consomem (produzem) Ri

cj: contribuicao da atividade Aj na funcao objetivo

min/max [ c1 c2 c3 ]

[x1

x2

x3

]

= c′x

Artifıcios para Demanda Ax ≃ b

a) Ax≤b venda no varejo

b) Ax≥b venda sob encomenda e no varejo

c) Ax = b demanda exata (carteira de pedidos)

d) .9b≤Ax≤1.1b carteira com tolerancia de 10%

e) b-d≤Ax≤b+d media b e desvio padrao d (estoque)

Artifıcios para Estoque Perecıvel

a) 1 perıodo : sj-1≤dj sj-1 + xj − sj = djb) 2 perıodos: sj-1+tj-2≤dj sj-1+tj-2 + xj − sj-tj = dj

Artifıcios para Produtos Aj = Ak

a) combinados: xk = αxjb) alternativos e ilimitados: escolher melhor custo ou lucro

c) alternativos limitados: objetivo linear por partes

( propaganda, economia de escala, etc.)

d) mix de producao∑

xj = 1′x = 1

Propaganda s: aumento na demanda d com investimento f ′s

min{

c′x+f ′s : Ax≤b, Dx-s=d, x, s≥0 }

Mistura xj ⊕ xk vide Problema da Mistura

(nao-linear)h′x1′x≥η ⇒ (h− η)x≥0 (linear)

Estocastico II (Racao)

Racao de menor custo (Alimentos A1..A4 × Nutrientes N1..N2)

x = (xj): qtde. de alimento na racao ( j = 1..4, i = 1..2 )

classico: min{ c′x : Ax≥b, x≥0 }

c: custo de alimento

b, b, b: qtdes normais/mınimas/maximas de nutriente

A, B: matrizes nutriente×alimento (media/desvio padrao)

1 min{ c′x : (A−B/2)x≥b, x≥0 }

2 min{ c′x : (A− 3B)x≥b, (A+3B)x≤b, x≥0 }

Estocastico I *

Perıodo 1: prod/estoc s = (s1, s2) a custos c com demanda a

Perıodo 2: producao xk a custo dk com demanda bk

cenario k=1..3 (ensolarado,nublado,chuvoso) ocorre com probabilidade pk

c=(10,2), d=(15,15,15), a=50, b=(120,100,80), p = (1/3,1/3,1/3)

min 10s1 +2s2 + (1/3)15x1 + (1/3)15x2 + (1/3)15x3suj s1 − s2 = 50 (perıodo 1)

s2 + x1 = 120 (perıodo2 - ensolarado)

s2 + x2 = 100 (perıodo2 - nublado)

s2 + x3 = 80 (perıodo2 - chuvoso)

s1, s2, x1, x2, x3≥0

min

c′s+

∑

k

(pk) (dk)′xk : As = a, Bs+ Cxk = bk, s, xk≥0, ∀k

Questoes

Formular. ( variaveis! )

Obter plano de producao de custo mınimo para os produtos

P1..P3 nas maquinas similares M1..M4 (cada unidade de produto

pode ser fabricado em qualquer maquina). Uma unidade de

cada um dos produtos requer horas de maquina e tem cus-

tos de acordo com as tabelas abaixo. A demanda e d=[4000,

5000, 3000] unidades dos produtos e a ha a disponibilidade

b=[1500,1200,1500,2000] horas de maquinas.

custo unitario consumo unitarioc M1 M2 M3 M4 a M1 M2 M3 M4

P1 4 4 5 7 P1 .3 .25 .2 .2P2 6 7 5 6 P2 .2 .3 .2 .25P3 12 10 8 11 P3 .8 .6 .6 .5

☼ xij: qtde de produto Pi na maquina Mj

min{

∑

ij cijxij :∑

j aijxij≤bj ∀j,∑

j xij≥di ∀i, xij≥0 ∀ij}

Formular. ( variaveis! )

a) Obter plano de custo mınimo de producao e estoque para 12

meses de um produto a partir da materia prima. No mes i, os

custos unitarios sao ai de processamento, bi de materia prima

e ci de estoque (mes i para mes i+1); a demanda contratada

e di e a disponibilidade de materia prima e ei. Cada unidade

do produto requer α unidades de materia prima. A capacidade

mensal de producao e β e a capacidade mensal de estoque e γ.

A materia prima nao pode ser estocada. O estoque inicial do

produto e δ e deseja-se este mesmo estoque no final.

b) restringir o estoque a no maximo um mes.

c) restringir o estoque a no maximo dois meses.

☼ xi: producao do mes i; si: estoque de i para i+1.

Formular (var!) Produtos P1,P2 sao fabricados com I1,I2,I3:

Insumo P1 P2 disp. bI1 11 22 2100I2 12 22 2200I3 13 23 2200

venda max a 110 120lucro c $51 $52

a) Maximizar o lucro total.

b) Venda casada: vende P2 so com P1

c) Vendas adicionais com propaganda tem lucros d=[51-14,52-24]

d) Terceirizacao parcial da pintura: lucro reduz para c=[41,41]

e) Reposicao de 13% por defeito de fabricacao: a=1.13a

max{ c′x+ d′s : A(x+ s)≤b, x≤a, x, s≥0 }

☼ xj: qtde. de produto vendido sem propaganda

☼ sj: qtde. adicional de produto vendido com propaganda

!© solucao otima com x+s>a tem x=a pois c>d

Formular. ( var! ) Fabrica de queijos de minas padrao e meia-cura tem 60 empregados e vaicontratar mais 30 em 8 semanas. Cada 3 trainees sao treinados por 1 empregado experientedurante 2 semanas durante as quais os 4 nao participam da producao de queijo. A cada horaum empregado produz 10 pounds de padrao ou 6 pounds de meia-cura. A demanda (em1000pounds) nas proximas 8 semanas de 40 horas e [12,12,12,16,16,20,20,20] de padrao e[8,8,10,10,12,12,12,12] de meia-cura. Todos recebem o mesmo salario.

☼ xi: no. de grupos em treinamento nas semanas i, i+1 i = 1..8

min 8×60+ 3(8x1 +7x2 +6x3 +5x4 +4x5 +3x6 +2x7 + x8), suj x≥0,60− (x1)≥(12000/10+ 8000/6)/40

60− (x1 + x2)≥(12000/10+ 8000/6)/40

60− (x2 + x3) + 3(x1)≥(12000/10+ 10000/6)/40

60− (x3 + x4) + 3(x1 + x2)≥(16000/10+ 10000/6)/40

60− (x4 + x5) + 3(x1 + x2 + x3)≥(16000/10+ 12000/6)/40

60− (x5 + x6) + 3(x1 + x2 + x3 + x4)≥(20000/10+ 12000/6)/40

60− (x6 + x7) + 3(x1 + x2 + x3 + x4 + x5)≥(20000/10+ 12000/6)/40

60− (x7 + x8) + 3(x1 + x2 + x3 + x4 + x5 + x6)≥(20000/10+ 12000/6)/40

x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 = 30/3

Formular. (var!) Empresa tem 3 fabricas e 6 postos de vendas:

Fab\Posto c 1 2 3 4 5 6 Cap. b $Prod. c1 .26 .30 .54 .41 .20 .37 2.2 .852 .45 .35 .30 .50 .32 .41 3.4 .943 .53 .40 .41 .20 .35 .25 1.8 .72

Demd. a .85 .75 .42 .58 1.02 .92$Oper. c .10 .13 .09 .12 .11 .08

☼ xij: qtde. de Fi para Pj, i = 1..3, j = 1..6

min∑

ij(cij + ci + cj)xij, suj x≥0,∑

j xij≤bi, ∀i∑

i xij≥aj, ∀j

Formular. (var!) Fabrica de 3 departamentos produz 4 moveis

hrs / custo mesa cadeira armario estante hrs disp.

Corte 3 / 15 1 / 8 2 / 12 2 / 12 800Montagem 10 / 30 6 / 18 8 / 24 7 / 21 1200Acabamento 10 / 35 8 / 28 8 / 25 7 / 21 800

$Venda 175 95 145 130

a) ☼ xj: producao (mesa,cadeira,armario,estante), (j = 1..4)

lucro:( 175-15-30-35, 95-8-18-28, 145-12-24-25, 130-12-21-21 )

= ( 95, 41, 84, 76 )

max ( 95, 41, 84, 76 ) x, suj x≥0,( 3, 1, 2, 2 ) x≤800( 10, 6, 8, 7 ) x≤1200( 10, 8, 8, 7 ) x≤800

b) 3: custo adicional para terceirizar parte do acabamento

hrs / custo mesa cadeira armario estante hrs disp.

Corte 3 / 15 1 / 8 2 / 12 2 / 12 800Montagem 10 / 30 6 / 18 8 / 24 7 / 21 1200

Acab. int. 10 / 35 8 / 28 8 / 25 7 / 21 800Acab. ext. 10 / — 8 / — 8 / — 7 / — —

$Venda 175 95 145 130

☼ xj: qtde. c/acab.int (j = 1..4), lucro = ( 95, 41, 84, 76 )

yj: qtde. c/acab.ext (j = 1..4), lucro = ( 92, 38, 81, 73 )

max ( 95, 41, 84, 76 ) x+ ( 95, 41, 84, 76 ) y, suj x, y≥0,( 3, 1, 2, 2 ) (x+ y)≤800( 10, 6, 8, 7 ) (x+ y)≤1200( 10, 8, 8, 7 ) x≤800

c) 13% das estantes sao de 2a. linha por defeito de fabricacao

hrs/cst mesa cadeira armario estante estante2 hrs disp.

Corte 3 / 15 1 / 8 2 / 12 2 / 12 2 / 12 800Monta 10 / 30 6 / 18 8 / 24 7 / 24 7 / 21 1200Acaba 10 / 35 8 / 28 8 / 25 7 / 25 7 / 21 800

$Venda 175 95 145 130 70

☼ xj: producao (mesa,cadeira,armario,estante,estante2), (j = 1..5)

lucro = ( 95, 41, 84, 76, 15 ) = (.. 130-12-21-21, 70-12-21-21 )

max ( 95, 41, 84, 76, 15 ) x, suj x≥0,( 3, 1, 2, 2, 2 ) (x+ y)≤800( 10, 6, 8, 7, 7 ) (x+ y)≤1200( 10, 8, 8, 7, 7 ) x≤800x5 = .13x4

d) cada mesa requer uma cadeira.

☼ xj: producao (mesa,cadeira,armario,estante), (j = 1..4)

max ( 95, 41, 84, 76 ) x, suj x≥0,( 3, 1, 2, 2 ) x≤800( 10, 6, 8, 7 ) x≤1200( 10, 8, 8, 7 ) x≤800x2≥x1

e) cada 3 mesas/cadeiras requer uma estante e um armario.

☼ xj: producao (mesa,cadeira,armario,estante), (j = 1..4)

max ( 95, 41, 84, 76 ) x, suj x≥0,( 3, 1, 2, 2 ) x≤800( 10, 6, 8, 7 ) x≤1200( 10, 8, 8, 7 ) x≤800x2≥x1x3, x4≥x1/3

III - OTIMALIDADE

➀ Dualidade

Otimalidade

Folgas Complementares

➁ Modelos:

Racao (Dieta)

Producao

Multiproduto

Estoque (Multiperıodo)

Transporte

➂ Questoes

Par Primal-Dual de PLs

min c1x1 + c2x2 + c3x3suj a11x1 + a12x2 + a13x3 ≥ b1 : y1≥0

a21x1 + a22x2 + a23x3 = b2 : y2

a31x1 + a32x2 + a33x3 ≤ b3 : y3≤0x1≥0 x3≤0

max b1y1 + b2y2 + b3y3suj a11y1 + a21y2 + a31y3 ≤ c1 : x1≥0

a12y1 + a22y2 + a32y3 = c2 : x2

a13y1 + a23y2 + a33y3 ≥ c3 : x3≤0y1≥0 y3≤0

≥restւ min

rest≤

maxր

DUALIDADE

PROBLEMA min ⇔ max PROBLEMA

≥ ≥0restric~ao = ⇔ livre variavel

≤ ≤0≥0 ≤

variavel livre ⇔ = restric~ao

≤0 ≥coef(res,var) ⇔ coef(var,res)

• min{

c′x : Ax≥b, x≥0}

× max{

b′y : A′y≤c, y≥0}

• min{

c′x : Ax=b, x≥0}

× max{

b′y : A′y≤c}

• max{

c′x : Ax=b, x≥0}

× min{

b′y : A′y≥c}

T. dual do dual e o primal.

solucao x: satisfaz Ax = b

solucao factıvel: satisfaz restricoes.

solucao otima: solucao factıvel de melhor valor (obj)

problemas equivalentes: ha relacao 1↔1 entre os conjuntos de

solucoes factıveis e entre os conjuntos de solucoes otimas.

T. duais de PLs equivalentes sao equivalentes.

max{ c′x : Ax≤b, x≥0 } × min{ b′y : A′y≥c, y≥0 }max{ c′x : Ax+Is=b, x, s≥0 } × min{ b′y : A′y≥c, Iy≥0 }• (x)↔ (x, s) com s=b-Ax • (y)↔ (y)

PL factıvel: possui solucao factıvel.

PL ilimitado: solucao otima e ilimitada (infinita).

T. Fraco da Dualidade. Par primal-dual de solucoes factıveis

tem valor da minimizacao maior ou igual ao da maximizacao.

, Seja (x, y) factıvel para o par primal-dual de PLs

min{ c′x : Ax≥b, x≥0 } ≥ max{ b′y : A′y≤c, y≥0 }

c′x =

x≥0 × c≥A′y︷ ︸︸ ︷

x′c≥x′A′y =

y≥0 × Ax≥b︷ ︸︸ ︷

y′Ax≥y′b = b′y ∴ c′x≥b′y

C. Par primal-dual de solucoes factıveis de mesmo valor e otimo.

C. PL com otimo ilimitado tem dual infactıvel.

T. Forte da Dualidade. PL com solucao otima (finita) tem

par primal-dual com otimos de mesmo valor.

D. Par primal-dual de solucoes factıveis complementares:

cada par folga-restricao × variavel-nao-livre tem produto nulo

T. Complementaridade. Par primal-dual de solucoes factıveis:

otimas sss de mesmo valor sss complementares

E. min { c′x : Ax≥b, x≥0 } × max { b′y : A′y≤c, y≥0 }X ( c-A′y ) = 0, Y ( Ax-b ) = 0, X=diag(x), Y =diag(y)

E. forma padrao: zjxj = 0 ∀j, onde z=c-A′ymin{ c′x : Ax=b, x≥0 } × max{ b′y : A′y≤c } ≡ max{ b′y : A′y+z=c, z≥0 }y: preco sombra, multiplicador de Lagrange, variavel dual

valor marginal de insumo (nao e valor medio)

z: custo reduzido, custo relativo, folga (de restricao) dual

E.

Primal

max 22x1 + 20x2suj 2x1 + x2 ≤ 60

x1 + 2x2 ≤ 60x2 ≤ 25

x1 , x2 ≥ 0

Dual

min 60y1 + 60y2 + 25y3suj 2y1 + y2 ≥ 22

y1 + 2y2 + y3 ≥ 20y1 , y2 , y3 ≥ 0

Folgas

( 2x1 + x2 − 60 ) y1 = 0( x1 + 2x2 − 60 ) y2 = 0( x2 − 25 ) y3 = 0

( 2y1 + y2 − 22 ) x1 = 0( y1 + 2y2 + y3 − 20 ) x2 = 0

E. x=(20,20)′ e uma solucao otima? [ SIM ]

1) x e factıvel (primal) pois Ax≤b, x≥0

2) (FC)

x2<25 → y3 = 0x1>0 → 2y1 + y2 − 22 = 0x2>0 → y1 +2y2 + y3 − 20 = 0

∴ y = (8,6,0)′

3) y e factıvel (dual) pois A′y≥c, y≥0

4) x, y sao complementares pois Y (b-Ax)=0, X(A′y-c)=0ou valor de x = valor de y : $840

Racao ( Dieta ) +

cj : custo de alimento

bi : qtde. mınima de nutriente

Aij : matriz nutriente×alimento

min{

c′x : Ax≥b, x≥0}

max{

b′y : A′y≤c, y≥0}

Y ( Ax-b ) = 0, Y =diag(y)

X ( A′y-c ) = 0, X=diag(x)

xj : qtde. de alimento

yi : valor de nutriente (pılula)

Producao +

cj : lucro de produto

bi : disponibilidade de insumo

Aij : matriz insumo×produto

max{

c′x : Ax≤b, x≥0}

min{

b′y : A′y≥c, y≥0}

Y ( Ax-b ) = 0, Y =diag(y)

X ( A′y-c ) = 0, X=diag(x)

xj : qtde. de produto

yi : valor de insumo

Multiproduto +

ckj : lucro de producao em fabrica

bkj : disponibilidade de insumo em fabrica

dj : demanda de produto

Aij : matriz insumo×produto

max{

∑

k(ck)′xk : Axk≤bk ∀k, ∑

k xk≤d, xk≥0 ∀k

}

min{

∑

k(bk)′yk+d′z : A′yk+z≥ck, yk≥0, z≥0 ∀k

}

Z(d-∑

k xk)=0, Y k(bk-Axk)=0, Xk(ck-A′yk-z)=0, ∀k, diag:Xk, Y k, Z

xkj : qtde. de produto em fabrica

yki : valor de recurso em fabrica

zj : valor de produto

Estoque ( Multiperıodo ) +

ckj : custo de producao em perıodo

dkj : custo de estoque em perıodo

bki : demanda em perıodo

min{

∑

k(ck)′xk+(dk)′sk : xk+sk-1-sk=bk, xk, sk≥0, ∀k

}

max{

∑

k(bk)′yk : yk≤ck, yk-1-yk≤dk, ∀k

}

Xk( ck-yk ) = 0, ∀k, Xk=diag(xk)

Sk( yk-1-yk ) = 0, ∀k, Sk=diag(sk)

xkj : qtde. de produto em perıodo

skj : qtde. de estoque de k para k+1

ykj : valor de produto em perıodo

Transporte +

ai : disponibilidade de minerio em mina

bj : demanda de minerio em fabrica

cj : custo de transporte de mina a fabrica

min{

c′x : -∑

i xij≥-ai, ∀i;∑

i xij≥bj, ∀j; x≥0}

max{

b′v-a′u : vj≤ui+cij, ∀ij; u, v≥0}

xij(cij+ui-vj)=0, ∀ij; ui(ai-∑

i xij)=0, ∀i; vj(bj-∑

i xij)=0, ∀j

xij : qtde. a transportar de mina a fabrica

ui: valor de minerio em mina

vj: valor de minerio em fabrica

vj-ui: valor de transporte de mina a fabrica

Estocastico +

pkℓ: probabilidade do cenario k ocorrer no perıodo ℓ

bkℓ: demandas/disponibilidades do cenario k do perıodo ℓ

ckℓ: custos de producao/estocagem do cenario k do perıodo ℓ

min{ ∑

kℓ

(pkℓ) (ckℓ)′xkℓ : Axkℓ-1 +Bxkℓ = bkℓ, xkℓ≥0, ∀k, ℓ}

max{ ∑

kℓ

(bkℓ)′ykℓ : A′ykℓ-1≤(pkℓ-1)ckℓ-1, B′ykℓ≤(pkℓ)c

kℓ, ∀k, ℓ}

Xkℓ-1(A′ykℓ-1 − (pkℓ-1)ckℓ-1) = 0 = Xkℓ(B′ykℓ − (pkℓ)c

kℓ)

xkℓ: qtdes a produzir/estocar no cenario k do perıodo ℓ

ykl: valor da dem/disp de item no cen. k / per. ℓ

Questoes

?© Se o dual e infactıvel entao o primal e ilimitado?

☼ Nao! Contra-exemplo:

Mostre que cada PL do par primal-dual abaixo e infactıvel.

max x1suj x1 − x2 = 1

− x1 + x2 = 0x1 , x2 ≥ 0

min y1suj y1 − y2 ≥ 1

− y1 + y2 ≥ 0

?© Primal: Dual? Folgas? x = (0,1, α)?

min

(3 4 3)xsuj

(1 2 2)x≥6(2 2 1)x≥2(1 2 1)x = 4x1, x2≥0

max

(6 2 4)ysuj

(1 2 1)y≤3(2 2 2)y≤4(2 1 1)y = 3y1, y2≥0

((1 2 2)x− 6)y1 = 0((2 2 1)x− 2)y2 = 0((1 2 1)y − 3)x1 = 0((2 2 2)y − 4)x2 = 0

P3: α = 2. x = (0,1,2)′ e primal factıvel (P1,P2,P3,P4).

F2 : y2 = 0D3 : (2,1,1)y = 3F4 : (2,2,2)y = 4

⇒ y = (1,0,1) e dual factıvel (D1,D2,D3,D4).

x,y complementares (F1..F4): x = (0,1, α) e otimo para α = 2.

?© Primal: Dual? Folgas? x = (0, α, β)?

min

(1 2 1)xsuj

(1 2 3)x = 8(1 1 1)x≥2(1 1 0)x = 1x1, x2≥0

max

(8 2 1)ysuj

(1 1 1)y≤1(2 1 1)y≤2(3 1 0)y = 1y2≥0

((1 1 1)x− 2)y2 = 0((1 1 1)y − 1)x1 = 0((2 1 1)y − 2)x2 = 0

P1,P3: α=1, β=2. x=(0,1,2)′ e primal factıvel (P1,P2,P3,P4).

F1 : y2=0D3 : (3,1,0)y=1F3 : (2,1,1)y=2

⇒ y=(1/3,0,4/3) nao e dual factıvel (D1..D4).

x, y complementares (F1..F4): x = (0, α, β) nao pode ser otimo.

?© Primal: Dual? Folgas? x = (0, α,2)?

max

(2 4 5)xsuj

(2 1 3)x≤7(1 3 2)x≤6(1 2 3)x = 8(3 2 2)x = 6x1, x2≥0

min

(7 6 8 6)ysuj

(2 1 1 3)y≥2(1 3 2 2)y≥4(3 2 3 2)y = 5y1, y2≥0

(( 2 1 3 )x− 7)y1 = 0(( 1 3 2 )x− 6)y2 = 0((2 1 1 3)y − 2)x1 = 0((1 3 2 2)y − 4)x2 = 0

P3: α=1. x=(0,1,2)′ nao e primal factıvel (×P2).

∴ x = (0, α,2) nao e otimo para nenhum α.

IV - METODO SIMPLEX

➀ Introducao

➁ Simplex

➂ Inıcio com 2 fases

➃ Simplex Dual

➄ Geometria dos PLs

➅ Pos-Otimizacao

➆ Variaveis Livres e Variaveis Canalizadas

➇ Analise Parametrica

➈ Questoes

1. Introducao

Forma Padrao min{

c′x : Ax=b, x≥0}

- max c′x ≡ min -c′x

- { Ax ≤ b } ≡ { Ax+s = b : s≥0 }

- { Ax ≥ b } ≡ { Ax−s = b : s≥0 }

- { [x] : x≤0 } ≡ { [-x] : x≥0 }

, { Ax = b (<0) } ≡ { -Ax = -b }

/ { [x] : x livre } ≈ { [x+-x-] : x+, x-≥0 }

-

{

[tij] : i ∈ 1..I, j ∈ 1..J

}

≡{

[xk] : k ∈ 1..K

}

k=(i-1)J+j, K=IJ

(i, j) ∈ { (1,1), (1,2), (1,3), (2,1), (2,2), (2,3) } ≡ k ∈ { 1, 2, 3, 4, 5, 6 }

E© Escrever na forma padrao

max − x1 + x2suj − x1 + 2x2 ≤ 6

2x1 − x2 = −6− x1 + x2 ≥ 1

x1 ≤ 0 (x2 livre)

min − x1 − (x+2-x-2)

suj x1 + 2(x+2-x-2) + x3 = 6

2x1 + (x+2-x-2) = 6

x1 + (x+2-x-2) − x4 = 1

x1 , x+2, x-2 , x3 , x4 ≥ 0

Metodos de Direcoes Factıveis min{ c′x : Ax=b, x≥0 }

x0, x1, x2, . . .→ x∗: soluc~oes factıveis de valor decrescente

Ax0=Ax1 . . . =b, x0, x1, . . .≥0, c′x0>c′x1> . . .

~x = x•-x◦: direc~ao de deslocamento entre duas solucoes:

dir.factıvel : A~x = A(x•-x◦) = 0

dir.descendente: c′~x = c′(x•-x◦) < 0

☼ Metodo Simplex: caminho de vertices entre arestas descendentes

· · · vertice x◦

x• vertice · · ·

aresta ~x

Solucoes / Direcoes min { c′x : Ax = b, x≥0 }

x, x•, x◦: ponto

Ax=b: soluc~ao, Ax=b, x≥0: sol.factıvel

~x=x•-x◦: direc~ao

A~x=0: dir.factıvel, c′~x<0: dir.descida

x+λ~x: deslocamento de passo λ reduz objetivo de λc′~x

{ x : Ax=b, x≥0 } = poliedro (⋂

semi-espacos)

☛ vertice, pt.extremo, sol.fac.basica x:

Ax=b, x≥0, { Aj : xj 6=0 } LI (linearmente independente)

☛ aresta de vertices x◦, x• (combinac~ao-convexa, seg.reta):

xλ = λx•+(1-λ)x◦ = x◦+λ(x•-x◦) = x+λ~x, λ∈[0,1]

Operacoes Elementares

Operacao O A OA O-1

➊ trocar duas equacoes

0 1 0 1 2 3 4 5 6

L1↔L2 1 0 0 4 5 6 1 2 3 O′0 0 1 7 8 9 7 8 9

➋ multiplicar uma equacao por uma constante nao-nula

1 0 0 1 2 3 1 2 3 1 0 0

L2←14L2 0 1

4 0 4 5 6 1 54

64 0 4 0

0 0 1 7 8 9 7 8 9 0 0 1

➌ somar a uma equacao, um multiplo de outra equacao

1 -14 0 1 2 3 0 34

32 1 4 0

L1←L1-14L2 0 1 0 4 5 6 4 5 6 0 1 0

0 0 1 7 8 9 7 8 9 0 0 1

☼ fazer ou desfazer operacao nao altera o conjunto de solucoes.

oper.elem︷ ︸︸ ︷

Om..O3O2O1 I | A | b ≡pivoteamentos︷ ︸︸ ︷

Pn .. P1 I | A | b ≡base inv.︷ ︸︸ ︷

B-1 I | A | b

Ax = B(B-1b) = b : B-1 I | A | b ≡ B-1 | B-1A | B-1b

Qi←{

Ii, Bi=Bi

B-1Bi, Bi 6=Bi

: Q-1 B-1 | B-1A | B-1b ≡ B-1 | B-1A | B-1b

E© matriz de pivoteamento P entre bases adjacentes (1 coluna distinta)

B B-1 B B-1B=P -1 P B-1=PB-1

1 1 1 0 0 1 1 1 6 1 0 1 1 0 -1/3 -1/3 1/3 1

1 1 0 0 1 -1 1 1 3 0 1 2 0 1 -2/3 -2/3 5/3 -1

1 0 0 1 -1 0 1 0 1 0 0 3 0 0 1/3 1/3 -1/3 0

original original atual proximo

E0. Inversa B-1 com pivos ars: a11=1, a22=-31 2 0 L1 1 . .

B = 2 1 0 L2 . 1 . = I1 0 1 L3 . . 1

1 2 0 L1 1 0 0

P1B = . -3 0 L2 -2 1 0 = P1. -2 1 L3 -1 0 1

1 . . L1 -1/3 2/3 0

P2P1B = . 1 . L2 2/3 -1/3 0 = P2P1 = B-1

. . 1 L3 1/3 -2/3 1

➊ aij ← aij-(ais/ars)arj, i 6=r, arj ← arj/ars➋ Li ← Li-(ais/ars)Lr, i 6=r, Lr ← Lr/ars➌ T ← PT➍ T ← B-1[B|I]

P -11 =

1 0 0

-2 1 0-1 0 1

-1

=

1 0 0

2 1 01 0 1

P -12 =

1 2/3 0

0 -1/3 00 -2/3 1

-1

=

1 2 0

0 -3 00 -2 1

E1. Inversa B-1 com pivos ars: a11=1, a22=-31 2 0 L1 1 . .

B = 2 1 0 L2 . 1 . = I1 0 1 L3 . . 1

1 2 0 L1 1 0 0

P1B = . -3 0 L2 -2 1 0 = P1. -2 1 L3 -1 0 1

1 . . L1 -1/3 2/3 0

P2P1B = . 1 . L2 2/3 -1/3 0 = P2P1 = B-1

. . 1 L3 1/3 -2/3 1

a32: -2 = 0-(2×1)/1➊ aij ← aij-(ais/ars)arj, i 6=r, arj ← arj/ars➋ Li ← Li-(ais/ars)Lr, i 6=r, Lr ← Lr/ars➌ T ← PT➍ T ← B-1[B|I]

P -11 =

1 0 0

-2 1 0-1 0 1

-1

=

1 0 0

2 1 01 0 1

P -12 =

1 2/3 0

0 -1/3 00 -2/3 1

-1

=

1 2 0

0 -3 00 -2 1

E1. Inversa B-1 com pivos ars: a11=1, a22=-31 2 0 L1 1 . .

B = 2 1 0 L2 . 1 . = I1 0 1 L3 . . 1

1 2 0 L1 1 0 0

P1B = . -3 0 L2 -2 1 0 = P1. -2 1 L3 -1 0 1

1 . . L1 -1/3 2/3 0

P2P1B = . 1 . L2 2/3 -1/3 0 = P2P1 = B-1

. . 1 L3 1/3 -2/3 1

a22: -3 = 1-(2×2)/1➊ aij ← aij-(ais/ars)arj, i 6=r, arj ← arj/ars➋ Li ← Li-(ais/ars)Lr, i 6=r, Lr ← Lr/ars➌ T ← PT➍ T ← B-1[B|I]

P -11 =

1 0 0

-2 1 0-1 0 1

-1

=

1 0 0

2 1 01 0 1

P -12 =

1 2/3 0

0 -1/3 00 -2/3 1

-1

=

1 2 0

0 -3 00 -2 1

E1. Inversa B-1 com pivos ars: a11=1, a22=-31 2 0 L1 1 . .

B = 2 1 0 L2 . 1 . = I1 0 1 L3 . . 1

1 2 0 L1 1 0 0

P1B = . -3 0 L2 -2 1 0 = P1. -2 1 L3 -1 0 1

1 . . L1 -1/3 2/3 0

P2P1B = . 1 . L2 2/3 -1/3 0 = P2P1 = B-1

. . 1 L3 1/3 -2/3 1

a12: 2 = 2/1

➊ aij ← aij-(ais/ars)arj, i 6=r, arj ← arj/ars➋ Li ← Li-(ais/ars)Lr, i 6=r, Lr ← Lr/ars➌ T ← PT➍ T ← B-1[B|I]

P -11 =

1 0 0

-2 1 0-1 0 1

-1

=

1 0 0

2 1 01 0 1

P -12 =

1 2/3 0

0 -1/3 00 -2/3 1

-1

=

1 2 0

0 -3 00 -2 1

E2. Inversa B-1 com pivos ars: a11=1, a22=-31 2 0 L1 1 . .

B = 2 1 0 L2 . 1 . = I1 0 1 L3 . . 1

1 2 0 L1 1 0 0

P1B = . -3 0 L2 -2 1 0 = P1. -2 1 L3 -1 0 1

1 . . L1 -1/3 2/3 0

P2P1B = . 1 . L2 2/3 -1/3 0 = P2P1 = B-1

. . 1 L3 1/3 -2/3 1

L2←L2-(2/1)L1

➊ aij ← aij-(ais/ars)arj, i 6=r, arj ← arj/ars➋ Li ← Li-(ais/ars)Lr, i 6=r, Lr ← Lr/ars➌ T ← PT➍ T ← B-1[B|I]

P -11 =

1 0 0

-2 1 0-1 0 1

-1

=

1 0 0

2 1 01 0 1

P -12 =

1 2/3 0

0 -1/3 00 -2/3 1

-1

=

1 2 0

0 -3 00 -2 1

E2. Inversa B-1 com pivos ars: a11=1, a22=-31 2 0 L1 1 . .

B = 2 1 0 L2 . 1 . = I1 0 1 L3 . . 1

1 2 0 L1 1 0 0

P1B = . -3 0 L2 -2 1 0 = P1. -2 1 L3 -1 0 1

1 . . L1 -1/3 2/3 0

P2P1B = . 1 . L2 2/3 -1/3 0 = P2P1 = B-1

. . 1 L3 1/3 -2/3 1

L3←L3-(1/1)L1

➊ aij ← aij-(ais/ars)arj, i 6=r, arj ← arj/ars➋ Li ← Li-(ais/ars)Lr, i 6=r, Lr ← Lr/ars➌ T ← PT➍ T ← B-1[B|I]

P -11 =

1 0 0

-2 1 0-1 0 1

-1

=

1 0 0

2 1 01 0 1

P -12 =

1 2/3 0

0 -1/3 00 -2/3 1

-1

=

1 2 0

0 -3 00 -2 1

E2. Inversa B-1 com pivos ars: a11=1, a22=-31 2 0 L1 1 . .

B = 2 1 0 L2 . 1 . = I1 0 1 L3 . . 1

1 2 0 L1 1 0 0

P1B = . -3 0 L2 -2 1 0 = P1. -2 1 L3 -1 0 1

1 . . L1 -1/3 2/3 0

P2P1B = . 1 . L2 2/3 -1/3 0 = P2P1 = B-1

. . 1 L3 1/3 -2/3 1

L1←L1/1

➊ aij ← aij-(ais/ars)arj, i 6=r, arj ← arj/ars➋ Li ← Li-(ais/ars)Lr, i 6=r, Lr ← Lr/ars➌ T ← PT➍ T ← B-1[B|I]

P -11 =

1 0 0

-2 1 0-1 0 1

-1

=

1 0 0

2 1 01 0 1

P -12 =

1 2/3 0

0 -1/3 00 -2/3 1

-1

=

1 2 0

0 -3 00 -2 1

E3. Inversa B-1 com pivos ars: a11=1, a22=-31 2 0 L1 1 . .

B = 2 1 0 L2 . 1 . = I1 0 1 L3 . . 1

1 2 0 L1 1 0 0

P1B = . -3 0 L2 -2 1 0 = P1. -2 1 L3 -1 0 1

1 . . L1 -1/3 2/3 0

P2P1B = . 1 . L2 2/3 -1/3 0 = P2P1 = B-1

. . 1 L3 1/3 -2/3 1

T = [ B | I ]➊ aij ← aij-(ais/ars)arj, i 6=r, arj ← arj/ars➋ Li ← Li-(ais/ars)Lr, i 6=r, Lr ← Lr/ars➌ T ← PT➍ T ← B-1[B|I]

P -11 =

1 0 0

-2 1 0-1 0 1

-1

=

1 0 0

2 1 01 0 1

P -12 =

1 2/3 0

0 -1/3 00 -2/3 1

-1

=

1 2 0

0 -3 00 -2 1

E3. Inversa B-1 com pivos ars: a11=1, a22=-31 2 0 L1 1 . .

B = 2 1 0 L2 . 1 . = I1 0 1 L3 . . 1

1 2 0 L1 1 0 0

P1B = . -3 0 L2 -2 1 0 = P1. -2 1 L3 -1 0 1

1 . . L1 -1/3 2/3 0

P2P1B = . 1 . L2 2/3 -1/3 0 = P2P1 = B-1

. . 1 L3 1/3 -2/3 1

➊ aij ← aij-(ais/ars)arj, i 6=r, arj ← arj/ars➋ Li ← Li-(ais/ars)Lr, i 6=r, Lr ← Lr/ars➌ T ← PT➍ T ← B-1[B|I]

P -11 =

1 0 0

-2 1 0-1 0 1

-1

=

1 0 0

2 1 01 0 1

P -12 =

1 2/3 0

0 -1/3 00 -2/3 1

-1

=

1 2 0

0 -3 00 -2 1

E4. Inversa B-1 com pivos ars: a11=1, a22=-31 2 0 L1 1 . .

B = 2 1 0 L2 . 1 . = I1 0 1 L3 . . 1

1 2 0 L1 1 0 0

P1B = . -3 0 L2 -2 1 0 = P1. -2 1 L3 -1 0 1

1 . . L1 -1/3 2/3 0

P2P1B = . 1 . L2 2/3 -1/3 0 = P2P1 = B-1

. . 1 L3 1/3 -2/3 1

➊ aij ← aij-(ais/ars)arj, i 6=r, arj ← arj/ars➋ Li ← Li-(ais/ars)Lr, i 6=r, Lr ← Lr/ars➌ T ← PT➍ T ← B-1[B|I]

P -11 =

1 0 0

-2 1 0-1 0 1

-1

=

1 0 0

2 1 01 0 1

P -12 =

1 2/3 0

0 -1/3 00 -2/3 1

-1

=

1 2 0

0 -3 00 -2 1

E4. Inversa B-1 com pivos ars: a11=1, a22=-31 2 0 L1 1 . .

B = 2 1 0 L2 . 1 . = I1 0 1 L3 . . 1

1 2 0 L1 1 0 0

P1B = . -3 0 L2 -2 1 0 = P1. -2 1 L3 -1 0 1

1 . . L1 -1/3 2/3 0

P2P1B = . 1 . L2 2/3 -1/3 0 = P2P1 = B-1

. . 1 L3 1/3 -2/3 1

➊ aij ← aij-(ais/ars)arj, i 6=r, arj ← arj/ars➋ Li ← Li-(ais/ars)Lr, i 6=r, Lr ← Lr/ars➌ T ← PT➍ T ← B-1[B|I]

P -11 =

1 0 0

-2 1 0-1 0 1

-1

=

1 0 0

2 1 01 0 1

P -12 =

1 2/3 0

0 -1/3 00 -2/3 1

-1

=

1 2 0

0 -3 00 -2 1

E . Inversa B-1 com pivos ars: a11=1, a22=-31 2 0 L1 1 . .

B = 2 1 0 L2 . 1 . = I1 0 1 L3 . . 1

1 2 0 L1 1 0 0

P1B = . -3 0 L2 -2 1 0 = P1

. -2 1 L3 -1 0 1

1 . . L1 -1/3 2/3 0

P2P1B = . 1 . L2 2/3 -1/3 0 = P2P1 = B-1

. . 1 L3 1/3 -2/3 1

➊ aij ← aij-(ais/ars)arj, i 6=r, arj ← arj/ars➋ Li ← Li-(ais/ars)Lr, i 6=r, Lr ← Lr/ars➌ T ← PT➍ T ← B-1[B|I]

P -12 =

1 2/3 00 -1/3 0

0 -2/3 1

-1

=

1 2 00 -3 0

0 -2 1

P1-1=

1 0 0-2 1 0

-1 0 1

-1

=

1 0 02 1 0

1 0 1

E©

30

60

30 60◦

•∗

x1

x2

[x4]

[x3]

[x5]

x1 +2x2 ≤60 [x3]2x1 + x2 ≤60 [x4]x1 ≤25 [x5]x1, x2 ≥0

vertice: intercessao de 2 retas (fixar 2 folgas em zero)≡ resolver 3 equacoes com 2 vars. nulas

x1 +2x2 + x3 = 602x1 + x2 + x4 = 60x1 + x5 = 25x1, x2, x3, x4, x5 ≥0

. E©

xB A b◦ x1 x2 x3 x4 x5 =

x3 1 2 1 . . 60x4 2 1 . 1 . 60

x5 1 0 . . 1 25

x◦ =

00

60

6025

B =

A1 A2 A5

1 2 02 1 01 0 1

-1/3 2/3 02/3 -1/3 01/3 -2/3 1

= B-1

xB B-1A B-1b∗ x1 x2 x3 x4 x5 =

x1 1 . -1/3 2/3 . 20x2 . 1 2/3 -1/3 . 20

x5 . . 1/3 -2/3 1 5

x∗ =

2020

0

05

Ax=BxB+NxN=b : B-1 B|N |b ≡ I|B-1N |B-1b : xB+B-1NxN=B-1b

. E© vertices: Ax=b, arestas: A~x=0, pivos: 2, 3/2

xB inv(B) x1 x2 x3 x4 x5 = B

x3 1 . . 1 2 1 . . 60 1 . . pivo(1,2)=2

x4 . 1 . 2 1 . 1 . 60 . 1 .

x5 . . 1 1 0 . . 1 25 . . 1

◦ x=[0 0 60 60 25], ~x=[0 1 -2 -1 0], λ=30, B1←A2

x2 1/2 0 0 1/2 1 1/2 . . 30 2 0 0

x4 -1/2 1 0 3/2 . -1/2 1 . 30 1 1 0 pivo(2,1)=3/2

x5 0 0 1 1 . 0 . 1 25 0 0 1

• x=[0 30 0 30 25], ~x=[1 -1/2 0 -3/2 -1], λ=20, B2←A1

x2 2/3 -1/3 0 . 1 2/3 -1/3 . 20 2 1 0

x1 -1/3 2/3 0 1 . -1/3 2/3 . 20 1 2 0

x5 1/3 -2/3 1 . . 1/3 -2/3 1 5 0 1 1

∗ x=[20 20 0 0 5]

. E© teste da raz~ao: λ = min{ bi/ais : ais > 0 }xB inv(B) x1 x2 x3 x4 x5 = B bi/(ais)x2 1/2 0 0 1/2 1 1/2 . . 30 2 0 0 30/(1/2)

x4 -1/2 1 0 3/2 . -1/2 1 . 30 1 1 0 30/(3/2)

x5 0 0 1 1 . 0 . 1 25 0 0 1 25/(1)

• x=[0 30 0 30 25], ~x=[1 -1/2 0 -3/2 -1], λ=20 pivo=3/2

x2 2/3 -1/3 0 . 1 2/3 -1/3 . 20 2 1 0

x1 -1/3 2/3 0 1 . -1/3 2/3 . 20 1 2 0

x5 1/3 -2/3 1 . . 1/3 -2/3 1 5 0 1 1

∗ x=[20 20 0 0 5]

x3 ≡ 0, x1 = λ A(x+λ~x) = b+0 = b, x+λ~x≥0

x2 = 30− (1/2)λ → 20

x4 = 30− (3/2)λ → 0

x5 = 25− (1)λ → 5

x1 = λ → 20

λ→ 20

B•=[A2 A4 A5] sai x4, entra x1 B∗=[A2 A1 A5]

. E© criar a variavel x0 com coluna [1 0 0...0]’ e a equacao x0 + c′x = 0

A=[B N ] : xN=0, xB=b=B-1b, y′=c′BB-1, z=c=c-A′y

Q-1=

[

1 c′B0 B

]-1

=

[

1 -y′0 B-1

]

Q-1

[

Ic′ 0A b

]

=

[

Q-1 c′ -b′yA b

]

xB inv(Q) x1 x2 x3 x4 x5 = Q max x≥0x0 1 . . . 20 22 . . . 0 1 . . . z2=22

x3 . 1 . . 1 2 1 . . 60 . 1 . . pivo(1,2)=2

◦ x4 . . 1 . 2 1 . 1 . 60 . . 1 .x5 . . . 1 1 0 . . 1 25 . . . 1

x0 1 -11 0 0 9 . -11 . . -660 1 22 0 0 z1=9

x2 . 1/2 0 0 1/2 1 1/2 . . 30 . 2 0 0

• x4 . -1/2 1 0 3/2 . -1/2 1 . 30 . 1 1 0 pivo(2,1)=3/2

x5 . 0 0 1 1 . 0 . 1 25 . 0 0 1

x0 1 -8 -6 0 . . -8 -6 . -840 1 22 20 0 z≥0x2 . 2/3 -1/3 0 . 1 2/3 -1/3 . 20 . 2 1 0∗ x1 . -1/3 2/3 0 1 . -1/3 2/3 . 20 . 1 2 0

x5 . 1/3 -2/3 1 . . 1/3 -2/3 1 5 . 0 1 1

otimo ∗: B=[A2 A1 A5], y=[8 6 0], z=[0 0 -8 -6 0], x=[20 20 0 0 5], obj=840

2. Metodo Simplex

PL min{ c′x : Ax=b, x≥0 }, max{ b′y : A′y+z=c, z≥0 }, XZ=0

conjunto LI de colunas B: Bw=0 so tem solucao w=0

Amn (m<n) de posto completo: tem base Bmm e inversa B-1

b=B-1b ∴ b=∑

biBi=Bb As=a.s=B-1As ∴ As=∑

aisBi=BAs

Solucao basica A=[B|N ], c=(cB; cN), x=(xB;xN), z=(zB; zN)

fixar xN←0, zB←0 e resolver:

- Ax = BxB +NxN = b

[

BxB=b⇒

] {

xN ← 0

xB ← B-1b

- A′y + z = c:

{

B′y + zB = cBN ′y + zN = cN

[

B′y=cB⇒

] {

y′← c′BB-1

z ← c−A′y

!© zjxj = 0 ∀j ( [zB;xN]=0 ) ∴ c′x = c′BxB = c′Bb = c′BB-1b = y′b = b′y

☼ solucao basica primal-factıvel (x≥0) e dual-factıvel (z≥0) e otima

Quadros min{ c′x : Ax=b, x≥0 } ≡ min{ c′x : Ax=b, x≥0 }A = B-1A, b = B-1b, c′ = c′ − c′BB-1A

xN ← 0, xB← b, y′← c′BB-1, z ← c = c− A′y

0

1

B

c′B

:A

c′

b

-b′y

=0

1

B-1

−y′

×A

c′

b

0

︸ ︷︷ ︸

basico Q︸ ︷︷ ︸

corrente (canonico)

︸ ︷︷ ︸

inverso Q-1︸ ︷︷ ︸

original

‘cria’ a variavel x0 com coluna [1 0 0...0]’ e a equacao x0+c′x=0

Problema Canonico min{ c′x : Ax=b, x≥0 }A=B-1A, xB←b=B-1b, xN←0, y′←c′BB-1, z←c=c-A′y

☞ sol.basica primal-factıvel (x≥0) e dual-factıvel (z≥0) e otima

☞ escolher zs < 0

direc~ao primal ~x: ~xN←0, ~xs←1, ~xB←As ∴ A~x=0

teste da raz~ao λ← br/ars = min{ bi/ais : ais > 0 }direc~ao dual ~y, ~z: ~y′←-(B-1)r., ~z←-A′~y=(Ar.)′ ∴ A′~y+~z=0

pivo ars: xs substitui xBr na base B: Br ← As

!© passo λ: primal 6= dual

!© min × max: direcoes opostas para (~y, ~z)

Metodo Simplex Primal – Minimizar

base B: y′←c′BB-1, z←c-A′y, b←B-1b≥0repita

se z≥0 ent~ao pare: solucao otima.

escolha zs<0 (direcao de xs)

determine As←B-1As

se As≤0 ent~ao pare: solucao otima ilimitada.

escolha r←argmini{ bi/ais : ais>0 } (teste da razao)

faca Br←As e atualize B-1, b, y, z

Metodo Simplex Primal -- Maximizar . . .

repita

se z≤0 ent~ao pare: solucao otima.

escolha zs>0 . . .

E© Iniciar com a base B=[A3 A2 A1]

x1 x2 x3 x4 x5 min

20 22 0 0 0 0

1 2 1 0 0 602 1 0 1 0 601 0 0 0 1 25

30

60

30 60∗ •

◦x1

x2

[x4]

[x3]

[x5]

20x1 +22x2 minx1 +2x2 ≤60 [x3]2x1 + x2 ≤60 [x4]x1 ≤25 [x5]x1, x2 ≥0

x∗ = [00,00,60,60,25]x• = [25,00,35,10,00]x◦ = [25,10,15,00,00]

xB inv(Q) x1 x2 x3 x4 x5 = Q

20 22 0 0 0 01 2 1 0 0 60

2 1 0 1 0 60

1 0 0 0 1 25

◦ 1 0 -22 24 . . . -22 24 -720 1 0 22 20 z4=-22

x3 . 1 -2 3 . . 1 -2 3 15 . 1 2 1x2 . 0 1 -2 . 1 . ➀ -2 10 . 0 1 2 pivo(2,4)=1

x1 . 0 0 1 1 . . 0 1 25 . 0 0 1

• 1 0 0 -20 . 22 . . -20 -500 1 0 0 20 z5=-20

x3 . 1 0 -1 . 2 1 . -1 35 . 1 0 1x4 . 0 1 -2 . 1 . 1 -2 10 . 0 1 2

x1 . 0 0 1 1 0 . . ➀ 25 . 0 0 1 pivo(3,5)=1

∗ 1 0 0 0 20 22 . . . 0 1 0 0 0 z≥0x3 . 1 0 0 1 2 1 . . 60 . 1 0 0

x4 . 0 1 0 2 1 . 1 . 60 . 0 1 0x5 . 0 0 1 1 0 . . 1 25 . 0 0 1

◦ y=[00 22 -24] z=[00 00 00 -22 024] x=[25 10 15 00 00]~y=[00 -1 002] ~z=[00 01 00 001 -02] ~x=[00 -1 02 01 00] λd=22, λp=10

• y=[00 00 020] z=[00 22 00 000 -20] x=[25 00 35 10 00]~y=[00 00 -01] ~z=[01 00 00 000 001] ~x=[-1 00 01 02 01] λd=20, λp=25

∗ y=[00 00 000] z=[20 22 00 000 000] x=[00 00 60 60 25] z≥0 otimo obj=0

3. Simplex com 2 Fases

3. Simplex com 2 Fases ( b≥0 )

Fase II PL original: min { c′x : Ax = b, x≥0 }

Fase I PL artificial: min { 1′w : Ax+ w = b, x, w≥0 }

w: variaveis artificiais com base diagonal factıvel para fase I.

w = 0: x e factıvel para o PL original.

Fase I com otimo positivo: PL original e infactıvel

E© 2 fases (infactıvel)

Fase II (original)

x1 x2 x3 x4

1 1 0 0 0

1 -2 -1 0 6

2 -1 0 1 6

✲3 6x1

✻

-3

-6

x2

✁✁✁✁✁✁✁✁✁

✟✟✟✟✟✟

◦ •Fase I (artificial)

0 0 0 0 1 0

1 -2 -1 0 1 6

2 -1 0 1 0 6

xB inv(Q) x1 x2 x3 x4 x5 = Q Fase I

◦ 1 -1 0 -1 2 1 . . -6 1 1 0 z1=-1

x5 . 1 0 1 -2 -1 . 1 6 . 1 0x4 . 0 1 ➁ -1 0 1 . 6 . 0 1 pivo(2,1)=2

• 1 -1 1/2 . 3/2 1 1/2 . -3 1 1 0 z≥0x5 . 1 -1/2 . -3/2 -1 -1/2 1 3 . 1 1

x1 . 0 1/2 1 -1/2 0 1/2 . 3 . 0 2

PL original infactıvel:

• x5: -(3/2)x2-x3-(1/2)x4+x5=3 ∴ x5≥3

E© 2 fases (otimo ilimitado)

Fase II (original)

x1 x2 x3 x4 x5

+ 4 2 -1 -1 -1 0

- 1 2 -1 0 0 60

- 2 1 0 -1 0 60

- 1 0 0 0 -1 15

Fase I (artificial)

0 0 0 0 0 1 1 1 0

1 2 -1 0 0 1 0 0 60

2 1 0 -1 0 0 1 0 60

1 0 0 0 -1 0 0 1 15

30

60

30 60◦

•⋄ +∗

x1

x2

[x5] [x4] [x3]

xB inv(Q) x1 x2 x3 x4 x5 x6 x7 x8 = Q Fase I

0 0 0 0 0 1 1 1 0 min x≥01 2 -1 0 0 1 0 0 602 1 0 -1 0 0 1 0 601 0 0 0 -1 0 0 1 15

◦ 1 -1 -1 -1 -4 -3 1 1 1 . . . -135 1 1 1 1 z2=-3x6 . 1 0 0 1 2 -1 0 0 1 . . 60 . 1 0 0 pivo(1,2)=2x7 . 0 1 0 2 1 0 -1 0 . 1 . 60 . 0 1 0x8 . 0 0 1 1 0 0 0 -1 . . 1 15 . 0 0 1

• 1 1/2 -1 -1 -5/2 . -1/2 1 1 3/2 . . -45 1 0 1 1 z1=-5/2x2 . 1/2 0 0 1/2 1 -1/2 0 0 1/2 . . 30 . 2 0 0x7 . -1/2 1 0 3/2 . 1/2 -1 0 -1/2 1 . 30 . 1 1 0x8 . 0 0 1 1 . 0 0 -1 0 . 1 15 . 0 0 1 pivo(3,1)=1

⋄ 1 1/2 -1 3/2 . . -1/2 1 -3/2 3/2 . 5/2 -15/2 1 0 1 0 z5=-3/2x2 . 1/2 0 -1/2 . 1 -1/2 0 1/2 1/2 . -1/2 45/2 . 2 0 1x7 . -1/2 1 -3/2 . . 1/2 -1 3/2 -1/2 1 -3/2 15/2 . 1 1 2 pivo(2,5)=3/2x1 . 0 0 1 1 . 0 0 -1 0 . 1 15 . 0 0 1

+ 1 0 0 0 . . 0 0 . 1 1 1 0 1 0 0 0 z≥0x2 . 2/3 -1/3 0 . 1 -2/3 1/3 . 2/3 -1/3 0 20 . 2 0 1x5 . -1/3 2/3 -1 . . 1/3 -2/3 1 -1/3 2/3 -1 5 . 1 0 2x1 . -1/3 2/3 0 1 . 1/3 -2/3 . -1/3 2/3 0 20 . 0 -1 1

+: base primal-factıvel B=[A2 A5 A1]

xB inv(Q) x1 x2 x3 x4 x5 = Q Fase II

4 2 -1 -1 -1 0 min x≥01 2 -1 0 0 60

2 1 0 -1 0 601 0 0 0 -1 15

+ 1 -1/3 -4/3 -1 . . -2/3 1/3 . -115 1 2 -1 4 z3=-2/3x2 . 2/3 -1/3 0 . 1 -2/3 1/3 . 20 . 2 0 1

x5 . -1/3 2/3 -1 . . 1/3 -2/3 1 5 . 1 0 2 pivo(2,3)=1/3x1 . -1/3 2/3 0 1 . 1/3 -2/3 . 20 . 0 -1 1

× 1 -1 0 -3 . . . -1 2 -105 1 2 -1 4 z4=-1x2 . 0 1 -2 . 1 . -1 2 30 . 2 -1 1

x3 . -1 2 -3 . . 1 -2 3 15 . 1 0 2 A4≤0x1 . 0 0 1 1 . . 0 -1 15 . 0 0 1

otimo ilimitado c′(x+λ~x)→∞: x=(15,30,15,0,0), ~x=(0,1,2,1,0), ~y, ~z?dual infactıvel: y1,y2,y3≤0, -y1-2y2≤-1 (A4)

E© 2 fases.

Fase II (original)

0 0 1 1 1 2 0

0 1 1 0 1 1 7

3 3 1 1 0 1 12

1 0 0 1 1 1 7

Fase I (artificial)

0 0 0 0 0 0 1 1 1 0

0 1 1 0 1 1 1 0 0 7

3 3 1 1 0 1 0 1 0 12

1 0 0 1 1 1 0 0 1 7

3

6

3 6◦

•∗

x1

x2

[x3]

[x4]

[x5]

SFs formam tetradro: 5 vertices 8 arestas

2x1 +4x2 + x6 ≤12 2[x3]4x1 +2x2 + x6 ≤12 2[x4]2x1 +2x2 + x6 ≥-2 2[x5]x1, x2, x6 ≥0

FACETA DE x6=0

xB inv(Q) x1 x2 x3 x4 x5 x6 x7 x8 x9 = Q Fase I

-4 -4 -2 -2 -2 -3 0 0 0 00 1 1 0 1 1 1 0 0 73 3 1 1 0 1 0 1 0 121 0 0 1 1 1 0 0 1 7

1 -1 -1 -1 -4 -4 -2 -2 -2 -3 . . . -26 1 1 1 1 z3=-2x7 . 1 -0 -0 0 1 1 0 1 1 1 . . 7 . 1 0 0 pivo(1,3)=1x8 . 0 1 -0 3 3 1 1 0 1 . 1 . 12 . 0 1 0x9 . 0 0 1 1 0 0 1 1 1 . . 1 7 . 0 0 1

1 1 -1 -1 -4 -2 . -2 0 -1 2 . . -12 1 0 1 1 z4=-2x3 . 1 0 0 0 1 1 0 1 1 1 . . 7 . 1 0 0x8 . -1 1 0 3 2 . 1 -1 0 -1 1 . 5 . 1 1 0 pivo(2,4)=1x9 . 0 0 1 1 0 . 1 1 1 0 . 1 7 . 0 0 1

1 -1 1 -1 2 2 . . -2 -1 0 2 . -2 1 0 0 1 z5=-2x3 . 1 0 0 0 1 1 . 1 1 1 0 . 7 . 1 0 0x4 . -1 1 0 3 2 . 1 -1 0 -1 1 . 5 . 1 1 0x9 . 1 -1 1 -2 -2 . . 2 1 1 -1 1 2 . 0 1 1 pivo(3,5)=2

1 .0 .0 .0 0 0 . . . 0 1 1 1 0 1 0 0 0 z≥0x3 . .5 .5 -.5 1 2 1 . . .5 .5 .5 -.5 6 . 1 0 1x4 . -.5 .5 .5 2 1 . 1 . .5 -.5 .5 .5 6 . 1 1 0x5 . .5 -.5 .5 -1 -1 . . 1 .5 .5 -.5 .5 1 . 0 1 1

B=[A3 A4 A5] e uma base primal factıvel para o PL original

xB inv(Q) x1 x2 x3 x4 x5 x6 = Q Fase II

0 0 1 1 1 2 00 1 1 0 1 1 73 3 1 1 0 1 121 0 0 1 1 1 7

◦ 1 -1/2 -1/2 -1/2 -2 -2 . . . 1/2 -13 1 1 1 1 z2=-2x3 . 1/2 1/2 -1/2 1 2 1 . . 1/2 6 . 1 0 1 pivo(1,2)=2x4 . -1/2 1/2 1/2 2 1 . 1 . 1/2 6 . 1 1 0x5 . 1/2 -1/2 1/2 -1 -1 . . 1 1/2 1 . 0 1 1

• 1 0 0 -1 -1 . 1 . . 1 -7 1 0 1 1 z1=-1x2 . 1/4 1/4 -1/4 1/2 1 1/2 . . 1/4 3 . 1 0 1x4 . -3/4 1/4 3/4 3/2 . -1/2 1 . 1/4 3 . 3 1 0 pivo(2,1)=3/2x5 . 3/4 -1/4 1/4 -1/2 . 1/2 . 1 3/4 4 . 0 1 1

∗ 1 -1/2 1/6 -1/2 . . 2/3 2/3 . 10/6 -5 1 0 0 1 z≥0x2 . 1/2 1/6 -1/2 . 1 2/3 -1/3 . 1/6 2 . 1 0 1x1 . -1/2 1/6 1/2 1 . -1/3 2/3 . 1/6 2 . 3 3 0x5 . 1/2 -1/6 1/2 . . 1/3 1/3 1 5/6 5 . 0 1 1

∗ y=[1/2,-1/6,1/2] z=[0,0,2/3,2/3,0,10/6] x=[2,2,0,0,5,0] z≥0 otimo obj=5

Dados Essenciais: constantes A, b, c, correntes xB, b, y, B=LU

xB inv(Q) x1 x2 x3 x4 x5 x6 = Q Fase II

0 0 1 1 1 20 1 1 0 1 1 73 3 1 1 0 1 121 0 0 1 1 1 7

◦ -1/2 -1/2 -1/2 -2x3 1/2 1/2 -1/2 2 6x4 -1/2 1/2 1/2 1 6x5 1/2 -1/2 1/2 -1 1

• 0 0 -1 -1x2 1/4 1/4 -1/4 1/2 3x4 -3/4 1/4 3/4 3/2 3x5 3/4 -1/4 1/4 -1/2 4

∗ -1/2 1/6 -1/2 . . 2/3 2/3 . 10/6x2 1/2 1/6 -1/2 2x1 -1/2 1/6 1/2 2x5 1/2 -1/6 1/2 5

∗ y=[1/2,-1/6,1/2] z=[0,0,2/3,2/3,0,10/6] x=[2,2,0,0,5,0] z≥0 otimo obj=5

E© Simplex 2 fases ( !© {A1, A2} nao e LI ! )

Fase II: min{ x1 : x1+2x2=2, 2x1+4x2=4, x≥0 }Fase I : min{ x3+x4 : x1+2x2+x3=2, 2x1+4x2+x4=4, x≥0 }xB inv(Q) x1 x2 x3 x4 = Q

1 -1 -1 -3 -6 . . -3 1 1 1 z1=-3x3 . 1 -0 ➀ 2 1 . 2 . 1 0 pivo(1,1)=1

x4 . 0 1 2 4 . 1 4 . 0 1

1 2 -1 . 0 3 . 0 1 0 1 z≥0 otimo F1

x1 . 1 0 1 2 1 . 2 . 1 0x4 . -2 1 . 0 -2 1 0 . 2 1

xB=?: x4 nulo comp~oe a base! L(x4): [0 -2 1][A|b]=0

1 -1 0 . -2 0 1 1 0 z2=-2

x1 . 1 0 1 ➁ 2 . 1 0

x4 . -2 1 . 0 0 . 2 1

1 0 0 1 . 0 1 0 0 z≥0 otimo F2

x2 . 1/2 0 1/2 1 1 . 2 0x4 . -2 1 0 . 0 . 4 1

Complexidade

teste de otimalidade: O(n-m)

calculo de uma coluna atualizada: O(m2)

teste da razao: O(m)

atualizacao da inversa da base e da solucao: O(m2)

∴ cada iteracao tem complexidade O(m2+n)

Refinamentos

• escolha s : zs < 0

• escolha r : λ =br

ars= min

i

{

biais

: ais > 0

}

Refinamentos do Simplex ( zj < 0 )

mais candidata ( Dantzig ) min zjmaior decrescimo min λjzjmaior declive min zj/sqrt(

∑

i a2ij)

devex min zj/sqrt(∑

i a2ij : aij > 0)

menor custo/benefıcio min cj/y′Aj

menor ındice ( Bland ) min j

rodızio ( LRC - Least Recently Considered )

antiguidade ( LRB - Least Recently Basic )

4. Simplex Dual

Problema Canonico min{ c′x : Ax=b, x≥0 }A=B-1A, xB←b=B-1b, xN←0, y′←c′BB-1, z←c=c-A′y

☞ sol.basica primal-factıvel (x≥0) e dual-factıvel (z≥0) e otima

☞ escolher br < 0

direc~ao dual ~y, ~z: ~y′←-(B-1)r., ~z←-A′~y=(Ar.)′ ∴ A′~y+~z=0

teste da raz~ao λ← -cs/ars = min{ -cj/arj : arj < 0 }direc~ao primal ~x: ~xN←0, ~xs←1, ~xB←-As ∴ A~x=0

pivo ars: xs substitui xBr na base B: Br ← As

!© passo λ: primal 6= dual

Metodo Simplex Dual

base B: b←B-1b, y′←c′BB-1, z←c-A′y≥0repita

se b≥0 ent~ao pare: solucao otima.

escolha br<0 (restricao xBr 6 ≥0)determine ~y←-(B-1)r., ~z←A′~y [ ~zj=arj ]

se ~z≥0 ent~ao pare: problema primal infactıvel.

escolha s← argminj{ -zj/arj : arj<0 } (teste da razao)

faca Br←As e atualize B-1, b, y, z

E© Simplex dual

1 1 0 0 0 0

-1 -2 0 1 0 -60

-2 -1 0 0 1 -60

-1 0 1 0 0 -15 0

30

60

0 30 60◦

• ∗

xB inv(Q) x1 x2 x3 x4 x5 = Q

◦ 1 0 0 0 1 1 . . . 0 1 0 0 0 b1=-60x4 . 1 0 0 -1 -2 . 1 . -60 . 1 0 0 pivo(1,2)=-2

x5 . 0 1 0 -2 -1 . . 1 -60 . 0 1 0x3 . 0 0 1 -1 0 1 . . -15 . 0 0 1

• 1 1/2 0 0 1/2 . . 1/2 . -30 1 1 0 0 b2=-30x2 . -1/2 0 0 1/2 1 . -1/2 . 30 . -2 0 0

x5 . -1/2 1 0 -3/2 . . -1/2 1 -30 . -1 1 0 pivo(2,1)=-3/2x3 . 0 0 1 -1 . 1 0 . -15 . 0 0 1

∗ 1 1/3 1/3 0 . . . 1/3 1/3 -40 1 1 1 0 b≥0x2 . -2/3 1/3 0 . 1 . -2/3 1/3 20 . -2 -1 0

x1 . 1/3 -2/3 0 1 . . 1/3 -2/3 20 . -1 -2 0

x3 . 1/3 -2/3 1 . . 1 1/3 -2/3 5 . 0 -1 1

otimo: x=[20,20,5,0,0], y=[-1/3,-1/3,0], z=[0,0,0,1/3,1/3], obj=40

E© Simplex dual

x1 x2 x3 x4

1 1 0 0 0

1 -2 -1 0 62 -1 0 1 6

✲3 6

x1✻

-3

-6

x2

✁✁✁✁✁✁

✟✟✟✟

◦ + ✲1

y1✻

-1

y2❍❍❍❍❥

❆❆❆❆

◦ +

Dual: max{ (6,6)y : (1,2)y≤1, (-2,-1)y≤1, y1≥0, y2≤0 }xB inv(Q) x1 x2 x3 x4 = Q

◦ 1 0 0 1 1 . . 0 1 0 0 b1=-6

x3 . -1 0 -1 2 1 . -6 . -1 0 pivo(1,1)=-1x4 . 0 1 2 -1 . 1 6 . 0 1

+ 1 -1 0 . 3 1 . -6 1 1 0 b2=-6x1 . 1 0 1 -2 -1 . 6 . 1 0

x4 . -2 1 . 3 2 1 -6 . 2 1 ~z≥0otimo dual ilimitado, primal infactıvel

+ x4: 3x2+2x3+x4=-6

?© Simplex dual

1 1 0 0 0

-1 -2 1 0 -6

-2 -1 0 1 -6

✻

3 6 x1✲

3

6x2

❍❍❍❍❍❍❍❍

❆❆❆❆❆❆❆❆

◦

•❍❍❍∗

✲-1 y1✻

-1

y2

❍❍❍❍❍❆❆❆❆❆

◦•❆❆❆∗

Dual: min{ (6,6)y : (1,2)y≥-1, (2,1)y≥-1, y≤0 }xB inv(Q) x1 x2 x3 x4 = Q

◦ 1 0 0 1 1 . . 0 1 0 0 b1=-6x3 . 1 0 -1 -2 1 . -6 . 1 0 pivo(1,2)=-2

x4 . 0 1 -2 -1 . 1 -6 . 0 1

• 1 1/2 0 1/2 . 1/2 . -3 1 1 0 b2=-3

x2 . -1/2 0 1/2 1 -1/2 . 3 . -2 0x4 . -1/2 1 -3/2 . -1/2 1 -3 . -1 1 pivo(2,1)=-3/2

∗ 1 1/3 1/3 . . 1/3 1/3 -4 1 1 1 b≥0x2 . -2/3 1/3 . 1 -2/3 1/3 2 . -2 -1

x1 . 1/3 -2/3 1 . 1/3 -2/3 2 . -1 -2

otimo: x=[2,2,0,0,0], y=[-1/3,-1/3], z=[0,0,1,1], obj=4

5. Geometria dos PLs

Poliedro ≡ Politopo ⊕ Cone min { c′x : Ax=b, x≥0 }S (solucao) x : Ax=b

SF (factıvel) x : x≥0SO (otima) x∗ : c′x∗≤c′x, ∀x factıvel

SB (basica) x : {Aj : xj 6=0} e LI

SH (homogenea): SF de {Ax=0, x≥0} ( trivial: x=0 )

SHE (extrema): SFB de {Ax=0, x≥0, 1′x=1}

!© x e SH, λ≥0 ⇒ λx e SH

- SFs formam poliedro com SFBs nos vertices

- SFBs definem politopo

- SHEs definem cone poliedrico de SHs

T© Representacao. SF de { Ax=b, x≥0 } e a soma:

comb.convexa das SFBs + comb.nao-negativa das SHEs

SF = α′SBF+ β′SHE com 1′α=1, α≥0, β≥0

E©

x1-2x2≤ 6

2x1- x2≥-6x1, x2≥ 0

x1 x2 x3 x4 =

1 -2 1 0 6

2 -1 0 -1 6

SBFs: x1=[6 0 0 18], x2=[0 6 18 0], x3=[0 0 6 6]

vertices do poliedro de SFs

SHEs: ~x1=[2/6 1/6 0 3/6], ~x2=[1/6 2/6 3/6 0]

direcoes das arestas infinitas do poliedro de SFs

SF x = α1x1+α2x

2+α3x3 + β1~x

1+β2~x2,

α1+α2+α3=1, α1, α2, α3, β1, β2≥0

3

6

3 6• •

•

x1

x1~x1

x2

x2

~x2

x3

Vertice ≡ Solucao Basica Factıvel K = { x : Ax=b, x≥0 }ponto extremo ou vertice x:

nao existem x1 6=x2 ∈ K tais que x = αx1 + (1-α)x2, α∈(0,1)( vertice nao e interior a segmento de reta no poliedro )

T solucao factıvel basica (SFB) sss vertice (ponto extremo)

∃ SF ⇒ ∃ SFB ☼ ∃ SO ⇒ ∃ SOB

T© Forte da Dualidade

solucao otima ⇒ solucoes primal-dual otimas de igual valor

☼ Transformar solucao otima em otima basica.

Usar sua base para construir par primal-dual de SBFs de mesmo valor.

E© Obter Ponto Extremo a partir de Ponto Factıvel.

0 1 1 4 5 6

0 2 2 4 5 6

1 0 1 4 5 6

2 1 3 4 5 6

x =

48310

, x≥0

x=[2 3 1 0 0 0] e factıvel mas nao e basico pois A3 = A1 +A2

A x=b×λ A ~x=0A (x+λ~x)=b

∼2A1+ 3A2+ A3 = bA1+ A2− A3 = 0

(2+λ)A1+ (3+λ)A2+ (1-λ)A3 = b

x(λ)=[2+λ 3+λ 1-λ 0 0 0] e SF para λ∈[-2,1]1) x(-2)=[0 1 3 0 0 0] e SFB pois {A2, A3} e LI

2) x( 1)=[3 4 0 0 0 0] e SFB pois {A1, A2} e LI

E© Teste de Independencia Linear {A1, A2, A3} e LI?

xB A1 A2 A3 A4 A5 A6 Ax0 ➀ 1 4 5 6 4

A 0 2 2 4 5 6 8

➀ 0 1 4 5 6 3

2 1 3 4 5 6 10

x 2 3 1 0 0 0

· · ·x2 . 1 1 4

. . 0 0x1 1 . 1 3

. . 0 0

x 3 4 0 0 0 0

n~ao e LI: A3 = 1A2 + 1A1

x: [2 3 1 0 0 0] → [3 4 0 0 0 0]

?©Teste de

IndependenciaLinear II :

A1=

0012

, A2=

1201

, A3=

1213

A1 A2 A3

1 0 0 [ 0 0 1 2 ]

0 1 0 [ 1 2 0 1 ]

0 0 1 [ 1 2 1 3 ]

L1: 1A1 +0A2 +0A3 = [0,0,1,2]

L2: 0A1 +1A2 +0A3 = [1,2,0,1]

L3: 0A1 +0A2 +1A3 = [1,2,1,3]

A1 A2 A3

1 0 0 0 0 1 20 1 -1 0 0 -1 -20 0 1 1 2 1 3

1 1 -1 . 0 . 00 -1 1 . 0 1 20 1 0 1 2 . 1

pivos: (3,4), (2,6), L1 nula

{ A1, A2, A3 } nao e LI pois

L1: 1A1 +1A2 − 1A3 = [0,0,0,0]?© Identificar a inversa de B: MB = P ′ ∴ B-1 = PM

E© Obter Vertice Otimo a partir de Otimo.

c -1 3 2 2 5 8 7 b I➀ 1 0 0 1 1 2 3 1 0 0

A -2 0 1 ➁ 2 2 1 4 0 1 00 2 ➀ 0 2 1 2 6 0 0 1

x 1 1 2 1 1 0 0

z 0 0 0 0 0 4 2

x1 1 ➀ . . 1 3 1 0 0x4 . 0 . ➀ 1 2 1 1/2 -1/2

x3 . 2 1 . 2 6 0 0 1

~x -1 1 -2 0 0 0 0 A2=A1+2A3

x 0 2 0 1 1 0 0 x←x+~xz 0 0 0 0 0 4 2

x2 1 . 1 3 1 0 0

x4 . 1 1 2 0 1/2 0. . 0 0 -2 0 1

~x 0 1 0 1 -1 0 0 A5=A2+A4

x 0 3 0 2 0 0 0 x←x-~x

obj=13 e um vertice pois {A2, A4} e LI

?© Obter vertice a partir de solucao. Otimo?.

A1 A2 A3 A4 A5 A6 A7 =

x 1 2 0 1 0 2 0

c 3 1 4 1 4 1 4 b3 1 2 1 2 1 2 8

A 2 0 2 1 1 1 1 5

1 0 1 0 0 1 1 3

c 0 . 2 0 2 0 2 -8

x2 3 1 2 1 2 1 2 82 . 2 1 1 1 1 5

1 . 1 0 0 1 1 3

c 0 . 2 . 2 0 2 -8

x2 1 1 0 . 1 0 1 3x4 1 . 1 1 1 1 0 5

1 . 1 . 0 1 1 3

c 0 . 2 . 2 . 2 -8

x2 1 1 0 . 1 . 1 3

x4 1 . 1 1 1 . 0 2x6 1 . 1 . 0 1 1 3

c1 = 0

A1=A2 +A4 +A6

x = [ 1,2,0,1,0,2,0]

~x = [-1,1,0,1,0,1,0]

↓ c′(x+ λ~x) = 8

x = [ 0,3,0,2,0,3,0]

vertice otimo

Degenerescencia. A: m×n-matriz de posto completo.

min { c′x : Ax=b, x≥0 }, max { b′y : A′y+z=c, z≥0 }, XZ1=0

SB da base B: xN←0, xB←b=B-1b, y′←c′BB-1, z←c=c-A′y

SBF x: Ax=b, x≥0, {Aj : xj>0} e LI.

SBF y, z: A′y+z=c, z≥0, {Aj : zj=0} gera as colunas de A.

SBF degenerada x: |{xj>0}|<m: ha variaveis basicas nulas.

SBF degenerada y, z: |{zj=0}|>m: ha folgas nao-basicas nulas

Pivoteamento muda para base adjacente

dual degenerado: mantem y, z e objetivo (aresta horizontal)

primal degenerado: mantem x e objetivo (aresta nula)

∴ vertice de varias bases que pode ter mais de n-m arestas.

PL primal (dual) degenerado: ha x (y, z) degenerado.

PL n~ao-degenerado: cada vertice tem n-m arestas (nao-horizontais)

?© B=[A4|A1|A2]: obter otimo.

min [ 0 1 1 1 0 ] xsuj [-1 2 1 0 0 ] x = 4

[ 2 -1 0 1 0 ] x = 4

[ 0 1 0 0 1 ] x = 4

1

2

3

4

1 2 3 4

∗

x1

x2

[x4]

[x3]

[x5]

xB inv(Q) A b Q

+ 1 -2 -1 2 . . -1 . 2 -4 1 1 0 1

4 . 2 1 -3 . . 2 1 -3 0 . 0 -1 21 . -1 0 2 1 . -1 . 2 4 . 1 2 -1

2 . 0 0 1 . 1 0 . 1 4 . 0 0 1

+: x=[4;4;0;0;0] e otimo? B=312?

* 1 -1 -.5 .5 . . . .5 0.5 -4 1 1 0 1

3 . 1 .5 -1.5 . . 1 .5 -1.5 0 . 1 -1 21 . 0 .5 .5 1 . . .5 0.5 4 . 0 2 -1

2 . 0 0 1 . 1 . 0 1 4 . 0 0 1

*: x=[4;4;0;0;0] e otimo! B=512?

☼ multiplicar 1a. restric~ao por -1 ?

Convergencia Finita.

Numero de bases e limitado a(mn

)

se Amn e de posto completo.

Pivoteamentos nao-degenerados:

objetivo melhora estritamente,

nenhuma base e revisitada

formam sequencia decrescente de objetivos

numero de pivoteamentos e limitado por(mn

)

.

∴ Metodo Simplex e finito em PLs nao-degenerados.

Pivoteamentos degenerados mantem objetivo e

permite visitas a uma base infinitas vezes (ciclagem).

6. Pos-Otimizacao

POS-OTIMIZACAO

✌ estudo de variacao de coeficientes (ambos)

☛ nova variavel ou coluna xn+1 (simplex dual)

☛ nova restricao ou linha ym+1 (ambos)

☛ analise parametrica de rhs b+ λ~b (simplex primal)

☛ analise parametrica de custo c+ λ~c (simplex dual)

Coeficiente varia e base permanece otima

min{ c′x : Ax=b, x≥0 }, max{ b′y : z=c-A′y≥0 }, zjxj=0, ∀j

B otima: xN=0, xB=b=B-1b≥0, y′=c′BB-1, z=c=c-A′y≥0

☞ rhs br ← βB otima: xB(β) = B-1b(β)≥0

☞ custo n~ao-basico cs ← γB otima: zs(γ) = γ − y′As≥0

☞ custo basico cs ← γB otima: z(γ) = c(γ)−A′y(γ)≥0 onde y(γ)

′=cB(γ)′B-1

☞ coluna n~ao-basica ars ← αB otima: zs(α) = cs − y′As(α)≥0

✍ coluna basica ars ← α (B-1(α)?)

E© B = [A1, A2] e base otima de (min em x≥0):

x1 x2 x3 x4

c 6 6 -1 -1 b

A1 2 -1 0 6

2 1 0 -1 6

B-1=

[

1 2

2 1

]-1

=

[

-1/3 2/3

2/3 -1/3

]

x=[2,2,0,0], y=[2,2], z=[0,0,1,1]

?© b1 3≤b1≤12

xB = B-1b =

[

-1/3 2/3

2/3 -1/3

] [

b16

]

=

[

-b1/3+42b1/3-2

]

≥[

00

]

?© c3 c3≥− 2

z3 = c3 −A3′y = c3 − [-1,0]

[

22

]

= c3 +2≥0

?© c1 9/2≤c1≤9

y′ = c′BB-1 = [c1,6]

[

-1/3 2/32/3 -1/3

]

= [ 4− c1/3, 2c1/3− 2 ]

zN=cN-N ′y=[

-1-1

]

-

[

-1 00 -1

] [

4-c1/32c1/3-2

]

=

[

3-c1/32c1/3-3

]

≥[

00

]

?© a13 a13≤− 1/2

z3 = c3 − A3′y = −1− [a13,0]

[

22

]

= −1− 2a13≥0

?© a11 B=

[

a11 22 1

]

∴ B-1=1

a11-4

[

1 -2-2 a11

]

a11 6=4

xB = B-1b =1

a11-4

[

1 -2-2 a11

] [

66

]

=1

a11-4

[

-6-12+6a11

]

≥[

00

]

a11≤2

y = c′B-1 =1

a11-4[6,6]

[

1 -2-2 a11

]

=1

a11-4

[

-6-12+6a11

]

zN = cN −N ′y =1

a11-4

[

-a11 -25a11 -8

]

≥[

00

]

−2≤a11≤8/5

−2≤a11≤8/5

?© B=[A1, A2, A3] e base otima para α, β, γ, δ? min{c′x : Ax=b, x≥0}

c′ =(

α 1 0 γ 4)

A =

1 0 0 1 21 1 0 2 21 1 1 1 δ

β46

= b

B=

1 0 01 1 01 1 1

1 0 0-1 1 00 -1 1

=B-1

y′ = [α,1,0]B-1=[α-1,1,0], zN = cN-N ′y =

[

γ-(α-1+2)≥04-(2α-2+2)≥0

]

xB = B-1b =

β≥04-β≥0

2≥0

∴ β ∈ [0,4] ∀δ α≤2, γ-1

7. Extensoes

7a Variaveis Livres

7b Variaveis Canalizadas

7c Restricoes Canalizadas

7a. Variaveis Livres

min{ c′x+d′t : Ax+Dt=b, x≥0 } max{ b′y : A′y+z=c, D′y=d, z≥0 } XZ=0

☛ substituir var.livre pela diferenca de duas var.nao-negativas

☛ eliminar var.livre com pivoteamento

☞ manter var.livre na base sempre

!© Supor [D|A], D de posto completo

base [D|B]: Particao em b.livres, b.nao-neg, nb.nao-neg

[D|A]=[D|B|N ], c=[cB; cN], x=[xB;xN], z=[zB; zN]

xN ← 0, [t;xB]← [D|B]-1b, y′← [d; cB]′[D|B]-1, z ← c-A′y

otimo: xB≥0, z≥0 candidata: zs<0 [ xr<0 ]

Br←As teste da raz~ao mantem xB≥0 [ z≥0 ]

Metodo Simplex com Variaveis Livres

base [D|B] primal factıvel com (t, x, y, z)

repita

se z≥0 ent~ao pare: solucao otima

escolha zs<0

determine As← [D|B]-1As

determine xBr/ars = λ← mini{ xBi/ais : ais>0 }

se λ=∞ ent~ao pare: solucao otima ilimitada.

faca Br ← As e atualize [D|B]-1, x, t, y, z

xN ← 0, [t;xB]← [D|B]-1b, y′← [d; cB]′[D|B]-1, z ← c-A′y

E© min, x1,x2,x3,x4≥0, x5 livrexB inv(Q) x1 x2 x3 x4 x5 = Q

◦ 1 0 0 0 -1 -1 . . . 0 1 0 0 0x3 . 1 0 0 1 2 1 . . 6 . 1 0 0

x4 . 0 1 0 2 1 . 1 . 6 . 0 1 0x5 . 0 0 1 1 1 . . 1 1 . 0 0 1

• 1 0 1/2 0 . -1/2 . 1/2 . 3 1 0 -1 0x3 . 1 -1/2 0 . 3/2 1 -1/2 . 3 . 1 1 0

x1 . 0 1/2 0 1 1/2 . 1/2 . 3 . 0 2 0x5 . 0 -1/2 1 . 1/2 . -1/2 1 -2 . 0 1 1

∗ 1 1/3 1/3 0 . . 1/3 1/3 . 4 1 -1 -1 0x2 . 2/3 -1/3 0 . 1 2/3 -1/3 . 2 . 2 1 0

x1 . -1/3 2/3 0 1 . -1/3 2/3 . 2 . 1 2 0

x5 . -1/3 -1/3 1 . . -1/3 -1/3 1 -3 . 1 1 1

otimo *: x0=-4, B=[A2 A1 A5], x=[2 2 0 0 -3], y=[-1/3 -1/3 0], z=[0 0 1/3 1/3 0]

3

6

3 6◦

• ∗x1

x2

[x5]

[x4]

[x3]

x1 +2x2≤6 [x3]2x1 + x2≤6 [x4]x1 + x2 = 1− x5 (livre)

7b. Variaveis Canalizadas ( d-≤x≤d+ )

☛ Forma padrao min{ c′x : Ax=b, x+s=d+, x≥d−, s≥0 }

☞ Modelo que reduz esforco computacional

min{ c′x : Ax=b, d-≤x≤d+ }max{ b′y+d-z-+d+z+ : A′y+z-+z+=c, z-≥0, z+≤0 }z = c-A′y = z-+z+, z- = max{z,0}, z+ = max{-z,0}z-j=zj > 0 ⇒ xj=d

-j

z+j=zj < 0 ⇒ xj=d+j

d-j<xj<d+j ⇒ zj=z+j=z

-j=0

B: ( base de A ) base de trabalho de

[

A 0

I I

]

min{ c′x : Ax=b, d-≤x≤d+ }

A=[B|N-|N+]: particao em basicas, nb.inferiores, nb.superiores

c=(cB; cN-; cN+), d-=(), d+=(), x=(xB;xN-;xN+), z=()

soluc~ao basica: y′← c′BB-1, z ← c-A′y [A′y+z=c]

xN- ← d-N-, xN+ ← d+N+, xB ← B-1(b-N-xN--N+xN+) [Ax=b]

otima: d-≤x≤d+, zj>0⇒xj=d-j , zj<0⇒xj=d

+j , [d-j<xj<d+j⇒zj=0]

candidata: zs<0, xs=d-s ou zs>0, xs=d+sdirec~ao: ~x←0 ~xs←-sgn(zs), ~xB←sgn(zs)B-1As

teste da raz~ao mantem d-≤x≤d+: ‘sai’ xs ou xBr

pivo pode ser negativo!

Metodo Simplex Canalizadopartic~ao de trabalho [B|N-|N+] primal factıvel com (x, y, z)repita

escolha s tal que zs<0, xs=d-s ou zs>0, xs=d+sse nao existe tal s ent~ao pare: solucao otimafaca γ ← sgn(zs)determine As← B-1As

determine λ- ← mini{ (xBi-d-Bi

)/|ais| : γais>0 }determine λ+ ← mini{ (d+Bi

-xBi)/|ais| : γais<0 }

determine λ ← min { d+s-d-s, λ-, λ+ }

se λ=∞ ent~ao pare: solucao otima ilimitada.atualize a base de trabalho e a solucao basica

λ=d+s-d-s ⇒ xs ← d+s+d

-s-xs e mantem B, y, z

λ<d+s-d-s, γars > 0 ⇒ Br ← As (sai xBr=d

-Br

)λ<d+s-d

-s, γars < 0 ⇒ Br ← As (sai xBr=d

+Br

)y′←c′BB

-1, z←c-A′y, xN-←d-

N-, xN+←d+

N+, xB←B-1(b-N-xN--N+x

N+)

E© B=[A2, A4, A5], N-=[A3], N+=[A1]:

min[ 9 1 0 0 0 ] x

suj

1 2 2 0 0

2 1 0 -2 0

1 1 0 0 2

x =

14

6

6

,

0000

-∞

≤x≤

4∞4∞∞

B B-1

2 0 0 1/2 0 0

1 -2 0 1/4 -1/2 0

1 0 2 -1/4 1/2 22

4

6

2 4 6

◦

•⋄

∗

x1

x2

[x5][x4]

[x3]

6≤x1 +2x2≤14 [x3]2x1 + x2≥6 [x4]0≤x1≤4x2≥0

B inv(Q) x1 x2 x3 x4 x5 b xB xB Q

0 1 -1/2 0 0 17/2 . -1 . . -7 -41 -37 1 1 0 0

2 . 1/2 0 0 1/2 1 1 . . 7 5 1 . 2 0 0

4 . 1/4 -1/2 0 -3/4 . 1/2 1 . 1/2 7/2 3/2 . 1 -2 0

5 . -1/4 0 1/2 1/4 . -1/2 . 1 -1/2 -3/2 1/2 . 1 0 2

◦ obj=41 x=[4,5,0,7/2,-3/2], ~x=[0,-1,1,-1/2,1/2], s=3, r=s, λ=4

• obj=37 x=[4,1,4,3/2,1/2], ~x=[-1,1/2,0,-3/4,1/4], s=1, r=2, λ=2

0 1 7/3 -17/3 0 . . 14/3 34/3 . -4/3 -20 1 1 9 0

2 . 2/3 -1/3 0 . 1 4/3 2/3 . 22/3 2 . 2 1 0

1 . -1/3 2/3 0 1 . -2/3 -4/3 . -2/3 2 . 1 2 0

5 . -1/6 -1/6 1/2 . . -1/3 1/3 1 -1/3 1 . 1 1 2

⋄ obj=20 x=[2,2,4,0,1], ~x=[-2/3,4/3,-1,0,-1/3], s=3, r=2, λ=3

0 1 0 -1 0 7 . . 2 . -6 -6 1 1 0 0

2 . 0 1 0 2 1 . -2 . 6 6 . 2 2 0

3 . 1/2 -1 0 -3/2 . 1 2 . 1 1 . 1 0 0

5 . 0 -1/2 1/2 -1/2 . . 1 1 0 0 . 1 0 2

∗ obj=6 x=[0,6,1,0,0], y=[0,1,0], z=[7,0,0,2,0], otimo

7c. Restricoes Canalizadas ( b-≤Ax≤b+ )

☛ Forma padrao min{ c′x : Ax-s-=b-, Ax+s+=b+, x, s-, s+≥0 }

☞ Modelo que reduz esforco computacional

min{ c′x : Ax+s=b+, x≥0, 0≤s≤b+-b- } max{ }

E© Iniciar com x=[5,7/2,-3/2]. (min em x2, x4≥0, x5 livre).

x2 x4 x5

c -7/2 9 0 b- b+

1/2 -1 0 -1 3

A 3/4 1/2 0 1.5 5.5

1/4 1/2 1 1.5 1.5

Inserir variaveis de folga para obter PL do exemplo anterior.

Questoes

?© inversa B-1 de B ?

L B IL1: 1 2 0 1 0 0L2: 2 1 0 0 1 0L3: 1 0 1 0 0 1

L1 1 2 0 1 0 0L2-2L1 0 -3 0 -2 1 0L3-L1 0 -2 1 -1 0 1

1 0 0 -13

23

00 1 0 2

3-13

00 0 1 1

3-23

1

I B-1

?© Decomposicao LU: B = LU L (U) triangular inferior (superior)

pivoteamentos incompletos – zeros abaixo do pivo

I B1 . . 1 2 0

. 1 . 2 1 0

. . 1 1 0 1

1 . . 1 2 0

2 1 . . -3 0

1 . 1 . -2 1

1 . . 1 2 0

2 1 . . -3 0

1 23

1 . . 1

L U

k=1..n :

ukj ← bkj −k−1∑

m=1

ℓkmumj, j=k..n

ℓik ←

bik −k−1∑

m=1

ℓimumk

/ukk, i=k+1..n

Resolver Bw = LUw = d: (1) Lw = b, (2) Uw = w

d = [60; 60; 25] w = [60; -60; 5] w = [20; 20; 5]

?© vertice de B=[A3|A1|A5] ? factıvel?

L xB B-1 x1 x2 x3 x4 x5 bL1: x3 1 0 0 1 2 1 60L2: ◦ x4 0 1 0 2 1 1 60L3: x5 0 0 1 1 0 1 25

L1-L2/2 x3 1 -1/2 0 3/2 1 -1/2 30L2/2 ⋄ x1 0 1/2 0 1 1/2 1/2 30

L3-L2/2 x5 0 -1/2 1 -1/2 -1/2 1 -5

☼ x⋄ = (30,0,30,0, -5)′ 6 ≥0 nao e solucao factıvel

?© B=[A2|A6|A1]: Q-1? (x, y, z)? 3 (~x, ~y, ~z)? base?

x1 x2 x3 x4 x5 x6 bmin -1 -1 0 0 0 -2

suj 1 2 1 0 0 3 60x≥0 2 1 0 1 0 3 60

1 0 0 0 1 1 25

☼ B=[A2, A6, A1] nao e uma base pois tem colunas LI

?© B=[A4|A2|A3]: Q-1? (x, y, z)? 2 (~x, ~y, ~z)? base?

x1 x2 x3 x4 x5 = min

0 0 1 1 1 x≥01 2 1 0 0 6

2 1 0 1 0 6

1 0 0 0 1 3

?© B=[A5|A2|A1]: Q-1? (x, y, z)? 2 (~x, ~y, ~z)? otimo?

min x1 x2 x3 x4 x5 x≥0c 0 0 1 1 1 b

1 2 1 0 0 6

A 2 1 0 1 0 6

1 0 0 0 1 3

xB inv(Q) x1 x2 x3 x4 x5 = Q

∗ 1 -1/3 2/3 -1 0 0 2/3 5/3 0 -1 1 1 0 0

x5 0 1/3 -2/3 1 0 0 -1/3 -2/3 1 1 0 0 2 1x2 0 2/3 -1/3 0 0 1 2/3 -1/3 0 2 0 0 1 2

x1 0 -1/3 2/3 0 1 0 -1/3 2/3 0 2 0 1 0 1

obj=1, x=(2,2,0,0,1), y=(1/3,-2/3,1), z=(0,0,2/3,5/3,0), otimo

z3=2/3: ~x=(1/3,-2/3,1,0,2/3), ~y=(2/3,-1/3,0), ~z=(0,-1,-2/3,1/3,0)z4=5/3: ~x=(-2/3,1/3,0,1,2/3), ~y=(1/3,-2/3,0), ~z=(-1,0,1/3,-2/3,0)

?© B=[A2|A4|A1]: Q-1? (x, y, z)? 2 (~x, ~y, ~z)? otimo?

min x1 x2 x3 x4 x5 x≥0c 0 0 1 1 1 b

1 2 1 0 0 6

A 2 1 0 1 0 6

1 0 0 0 1 3

inv(Q)

1.0 0.5 -1.0 1.5

0.0 0.5 0.0 -0.5

0.0 -0.5 1.0 -1.5

0.0 0.0 0.0 1.0

xB inv(Q) x1 x2 x3 x4 x5 = Q

∗ 1 -1/3 2/3 -1 0 0 2/3 5/3 0 -1 1 1 0 0

x5 0 1/3 -2/3 1 0 0 -1/3 -2/3 1 1 0 0 2 1x2 0 2/3 -1/3 0 0 1 2/3 -1/3 0 2 0 0 1 2

x1 0 -1/3 2/3 0 1 0 -1/3 2/3 0 2 0 1 0 1

x=(2,2,0,0,1), y=(1/3,-2/3,1), z=(1,0,-1/3,2/3,0)

x3: ~x=(1/3,-2/3,1,0,2/3), ~y=(2/3,-1/3,0), ~z=(0,-1,-2/3,1/3,0), λ=3x4: ~x=(-2/3,1/3,0,1,2/3), ~y=(1/3,-2/3,0), ~z=(-1,0,1/3,-2/3,0), λ=3

?© B=[A5|A1|A4]: Q-1? (x, y, z)? 2 (~x, ~y, ~z)? factıvel?

x1 x2 x3 x4 x5 = min

0 0 1 1 1 x≥01 2 1 0 0 6

2 1 0 1 0 6

1 0 0 0 1 3

?© B=[A2|A4|A5], B=[A4|A2|A5]: vertices (x, y, z)? aresta?

xB inv(B) x1 x2 x3 x4 x5 = B

x2 1/2 0 0 1/2 1 1/2 0 0 30 2 0 0

• x4 -1/2 1 0 3/2 0 -1/2 1 0 30 1 1 0 piv(2,1)=3/2

x5 0 0 1 1 0 0 0 1 25 0 0 1

x=(0,30,0,30,25), ~x=(1,-1/2,0,-3/2,-1), λ=20x4 -1/2 1 0 3/2 0 -1/2 1 0 30 1 1 0 piv(1,1)=3/2

◦ x2 1/2 0 0 1/2 1 1/2 0 0 30 2 0 0

x5 0 0 1 1 0 0 0 1 25 0 0 1

x=(0,30,0,30,25), ~x=(1,-1/2,0,-3/2,-1), λ=20

?© B=[A2|A4|A5], B=[A2|A1|A5]: vertices (x, y, z)? aresta?

xB inv(B) x1 x2 x3 x4 x5 = B

x2 1/2 0 0 1/2 1 1/2 0 0 30 2 0 0

• x4 -1/2 1 0 3/2 0 -1/2 1 0 30 1 1 0 piv(2,1)=3/2

x5 0 0 1 1 0 0 0 1 25 0 0 1

x=(0,30,0,30,25), ~x=(1,-1/2,0,-3/2,-1), λ=20x2 2/3 -1/3 0 0 1 2/3 -1/3 0 20 2 1 0

∗ x1 -1/3 2/3 0 1 0 -1/3 2/3 0 20 1 2 0

x5 1/3 -2/3 1 0 0 1/3 -2/3 1 5 0 1 1

x=(20,20,0,0,5)

?© B=[A5|A1|A2], B=[A5|A3|A4]: : vertices (x, y, z)? aresta?

x1 x2 x3 x4 x5 x≥00 0 1 1 1 0

1 2 1 0 0 6

2 1 0 1 0 6

1 0 0 0 1 3

xB invQ x1 x2 x3 x4 x5 = Q

◦ 1 -1/3 2/3 -1 0 0 2/3 10/6 0 -1 1 1 0 0

x5 0 1/3 -2/3 1 0 0 1/3 -2/3 1 1 0 0 1 2x1 0 -1/3 2/3 0 1 0 -1/3 2/3 0 2 0 0 2 1

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

• 1 -1 -1 -1 -4 -3 0 0 0 -15 1 1 1 1

x5 0 0 0 1 1 0 0 0 1 3 0 0 1 0x3 0 1 0 0 1 2 1 0 0 6 0 0 0 1

x4 0 0 1 0 2 1 0 1 0 6 0 1 0 0

◦: x=(2,2,0,0,1), y=(1/3,-2/3,1), z=(0,0,2/3,10/6,0), obj=1

•: x=(0,0,6,6,3), y=(1,1,1), z=(-4,-3,0,0,0), obj=15seg.reta ◦--• n~ao e aresta pois bases n~ao s~ao adjacentes

?© Quadro Canonico de B=[A1|A4|A5]:? otimo?

B-1 x1 x2 x3 x4 x5 b y

1 0 0 0 20 22 0 0 0 0

0 1 0 0 x3 1 2 1 600 00 0 1 0 x4 2 1 1 600 00 0 0 1 x5 1 0 1 250 0

1 -8 -6 0 0 0 -8 -6 0 -8400

0 -1/3 2/3 0 x1 1 -1/3 2/3 200 80 2/3 -1/3 0 x2 1 2/3 -1/3 200 60 1/3 -2/3 1 x5 1/3 -2/3 1 50 0

1 -11 0 0 9 0 -11 0 0 -6600

0 1/2 0 0 x2 1/2 1 1/2 300 110 -1/2 1 0 x4 3/2 -1/2 1 300 00 0 0 1 x5 1 0 1 250 0

?© Verifique a equivalencia entre originais e transformados

(mesmos conjuntos de otimos e mesmos conjuntos de factıveis)

max{ x1 : x1+x2=0, x2≥0 } ≡ min{ -x1 : x1+x2=0, x2≥0 }

{ x1≤1, x1≥0 } ≡ { x1+x2=1, x1, x2≥0 }

{ x1≥1, x1≥0 } ≡ { x1-x2=1, x1, x2≥0 }

{ x1+x2=1, x1≥0, x2≤0 } ≡ { x1-x2=1, x1, x2≥0 }

{ x1-x2=-1, x1, x2≥0 } ≡ { x2-x1=1, x1, x2≥0 }

{ x1+x2=1 : x1≥0 } 6≡ { x1+x+2-x

-2=1 : x1, x

+2, x

-2≥0 }

min ( 1 1 3 4 4 ) xsuj ( 1 0 1 2 1 ) x = 1x≥0 ( 0 1 1 1 2 ) x = 1

Fase2 ( 1 1 2 3 3 ) x = 2

1

2

1 2◦ •∗

x1

x2

[x3+2x4+x5]

[x3+x4+2x5]

[2x3+3x4+3x5]

min ( 0 0 0 0 0 1 1 1 ) xsuj ( 1 0 1 2 1 1 ) x = 1x≥0 ( 0 1 1 1 2 1 ) x = 1

Fase1 ( 1 1 2 3 3 1 ) x = 2

xB B-1 b As y, zs, s, rF1 x6 1 1 ➀ y′=(1,1,1)B-1=(1,1,1)◦ x7 1 1 0 z1=-2F1 x8 1 2 1 s=1, λ=1, r=1

F1 x1 1 1 0 y′=(0,1,1)B-1=(-1,1,1)• x7 1 1 1 z2=-2F1 x8 -1 1 1 ➀ s=2, λ=1, r=3

F1 x1 1 1 y′=(0,1,0)B-1=(1,1,-1)⋆ x7 1 1 -1 0 z=(0,0,0,0,0,0,0,2)≥0F1 x2 -1 1 1 s=?, x=(1,1,0,0,0)

F2 x1 1 1 y′=(1, α,1)B-1=(α, α,1-α)∗ x7 1 1 -1 0 z=(0,0,1,1,1, ,0, )≥0F2 x2 -1 1 1 s=?, x∗7:(1,1,-1)[A|b]=0

min ( 0 0 0 -2 3 -1 ) xsuj ( 1 2 -1 -2 ) x = 4x≥0 ( 1 -1 2 -1 ) x = 3

( 1 3 -2 0 ) x = 51

2

1 2◦ ∗ x4

x6

[x1][x2]

[x3]

xB B-1 b As y, zs, s, rx1 1 0 0 4 2 y′=(0,0,0)B-1=(0,0,0)

◦ x2 0 1 0 3 -1 z4=-2x3 0 0 1 5 3 s=4, λ=5/3, r=3x1 1 0 -2/3 2/3 -2 y′=(0,0,-2)B-1=(0,0,-2/3)

• x2 0 1 1/3 14/3 -1 z6=-1x4 0 0 1/3 5/3 0 s=6, λ=?, r=?

y◦=(0,0,0)+µ(0,0,-1), z◦=(0,0,0,-2,3,-1)+µ(0,0,1,3,-2,0), µ ∈ [0,2/3]

x◦=(4,3,5,0,0,0)+λ(-2,1,-3,1,0,0), λ ∈ [0,5/3], c′x◦=b′y◦=0y•=(0,0,-2/3), z•=(0,0,2/3,0,5/3,-1), c′x•=b′y•=-10/3x•λ=(2/3,14/3,0,5/3,0,0)+λ(2,1,0,0,0,1), c′xλ=-10/3-1λ→ -∞

min ( 0 0 0 -2 3 0 ) xsuj ( 1 2 -1 -2 ) x = 4x≥0 ( 1 -1 2 -1 ) x = 3

( 1 3 -2 0 ) x = 51

2

1 2◦ ∗ x4

x6

[x1][x2]

[x3]

xB B-1 b As y, zs, s, rx1 1 0 0 4 2 y′=(0,0,0)B-1=(0,0,0)

◦ x2 0 1 0 3 -1 z4=-2x3 0 0 1 5 3 s=4, λ=5/3, r=3x1 1 0 -2/3 2/3 -2 y′=(0,0,-2)B-1=(0,0,-2/3)

• x2 0 1 1/3 14/3 -1 z6=0x4 0 0 1/3 5/3 0 s=6?, λ=?, r=?

y•=(0,0,-2/3), z•=(0,0,2/3,0,5/3,-1), c′x•=b′y•=-10/3x•λ=(2/3,14/3,0,5/3,0,0)+λ(2,1,0,0,0,1), c′xλ=-10/3

V - METODO DE PONTOS INTERIORES

1. INTRODUCAO

Metodos Polinomais para PL

⊲ elipsoide (Yudin, Nemirovski, Shor e Khachian, 76-79)

⊲ transformacao Projetiva (Karmakar 84)

⊲ transformacao afim (afim escala) (∼89)

⊲ seguidor de caminho (trajetoria central) (∼89)

• metodo simplex (Dantzig 47) nao e polinomial

2. TRAJETORIA CENTRAL

min{ c′x : Ax=b, x≥0 }, max{ b′y : A′y+z=c, z≥0 }, XZ 1=0

(x, y, z) −→ (x, y, z) + λ(~x, ~y, ~z) µ→ 0

A cada iteracao obtem solucao aproximada do sistema

Ax = bA′y + z = cXZ 1 = µ1

A~x = b ← b− AxA′~y + ~z = c ← c− A′y − z

Z~x+X~z = µ ← µ1−XZ 1

(AZ-1XA′) ~y = Ax− µAZ-11 + b+AZ-1Xc~z = −A′~y + c

Z ~x = µ1−X(z + ~z)

Metodo Primal Dual de Pontos Interiores

seja (x, y, z)repetir ate convergir

estimar µcalcular (~x, ~y, ~z)aplicar teste da razao atualizando (x, y, z)

Teste da Razao

λ← .999995 ∗min{ -xj/~xj : ~xj<0 }if( λ>1 )then λ← 1

x ← x+ λ~xλ← .999995 ∗min{ -zj/~zj : ~zj<0 }if( λ>1 )then λ← 1

z ← z + λ~zy ← y + λ~y

teorico: µ← µ(1− 1/√n) pratico: µ← z′x/n2

matriz diagonal de scalling

primal-dual: D2 = Z-1X

primal: D2 = X2

dual: D2 = Z-2

AD2A′ e definida positiva: Fatoracao de Choleski

(AD)′~y ≃ c⇒ (AD2A′)~y = (AD)c

c = c− (AD)′~y ⇒ (AD)c = 0

c: projecao (quadrados mınimos) de c

Trajetoria central: (x, y, z) com ZX1 = µ1, µ > 0

PREDICAO e CORRECAO

A cada iteracao obtem solucao aproximada do sistema

Ax = bA′y + z = c[x][z]1 = µ1

[ ] – matriz diagonal

1) predicao:

Aδx = 0A′δy + δz = 0

[z]δx + [x]δz = µ1− [x][z]1

2) correcao:

A~x = 0A′~y + ~z = 0

[z]~x+ [x]~z = µ1− [x][z]1− [δx][δz]1

VARIAVEIS CANALIZADAS

min{ c′x : Ax = b, x+ s = d, x, s≥0 }

max{ b′y − d′w : A′y + z − w = c, z, w≥0 }

XZ1 = 0, SW1 = 0

A cada iteracao obtem solucao aproximada do sistema

Ax = bx+ s = d

A′y + z − w = cXZ1 = µ1SW1 = µ1

A~x = 0~x+ ~s = 0

A′~y + ~z − ~w = 0X~z + Z~x = µ1−XZ1S ~w +W~s = µ1− SW1

onde µ← (z′x+ w′s)/nmatriz escalada do sistema SPD em ∆y: A(X-1Z + S-1W )-1A′

VARIAVEIS LIVRES

variavel livre x ⇚ x+ − x-, x+, x-≥0

Mantem a estrutura de esparsidade dos dados

VI - PL NA PRATICA

Modelagem Algebrica

Forma padrao estendida:

• objetivo: minimizar ou maximizar

• variaveis: livres, nao-negativas ou canalizadas

• restricoes: equacoes, desigualdades ou canalizadas

• pos-otimizacao: variacao de coeficiente

• entrada: formato MPS

extras: pontos interiores, fluxo em redes, prog.quadratica (obj),

prog.nao-linear, prog.inteira/combinatoria

– permite construir o modelo em linguagem algebrica

MATLAB: MATrix LABoratory

[]=glpk(A,b,c)

>> ##### dados originais #####c = 0 0 0 0 0 0 0 0 1 1 1Ab= 1.00 0.00 0.00 -1.00 1.00 2.00 2.00 -0.20 1.00 0.00 0.00 3.20Ab= 0.00 1.00 0.00 1.00 -2.00 1.00 -2.00 0.40 0.00 1.00 0.00 5.60Ab= 0.00 0.00 1.00 -1.00 0.00 2.00 1.00 0.20 0.00 0.00 1.00 7.80e = 0 0 0 0 0 0 0 0 0 0 0d = 4 4 4 4 4 4 99 4 99 99 99##### solucao basica inicial (s=8) #####

xb y ------ B1 ------B1= 9 1.00 1.00 0.00 0.00B1= 10 1.00 0.00 1.00 0.00B1= 11 1.00 0.00 0.00 1.00z = -1.00 -1.00 -1.00 1.00 1.00 -5.00 -1.00 -0.40 0.00 0.00 0.00xb= -1 -1 -1 -1 -1 -1 -1 -1 0 0 0x = 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 3.20 5.60 7.80dx= 0.00 0.00 0.00 0.00 0.00 0.00 0.00 1.00 0.20 -0.40 -0.20##### entra x8=0 sai x8=4 (s=7) #####

xb y ------ B1 ------B1= 9 1.00 1.00 0.00 0.00B1= 10 1.00 0.00 1.00 0.00B1= 11 1.00 0.00 0.00 1.00

z = -1.00 -1.00 -1.00 1.00 1.00 -5.00 -1.00 -0.40 0.00 0.00 0.00xb= -1 -1 -1 -1 -1 -1 -1 1 0 0 0x = 0.00 0.00 0.00 0.00 0.00 0.00 0.00 4.00 4.00 4.00 7.00dx= 0.00 0.00 0.00 0.00 0.00 0.00 1.00 0.00 -2.00 2.00 -1.00##### entra x7=0 sai x9=0 (s=3) #####

xb y ------ B1 ------B1= 7 0.50 0.50 0.00 0.00B1= 10 1.00 1.00 1.00 0.00B1= 11 1.00 -0.50 0.00 1.00z = -0.50 -1.00 -1.00 0.50 1.50 -4.00 0.00 -0.50 0.50 0.00 0.00xb= -1 -1 -1 -1 -1 -1 0 1 -1 0 0x = 0.00 0.00 0.00 0.00 0.00 0.00 2.00 4.00 0.00 8.00 5.00dx= 0.00 0.00 1.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 -1.00##### entra x3=0 sai x3=4 (s=6) #####

xb y ------ B1 ------B1= 7 0.50 0.50 0.00 0.00B1= 10 1.00 1.00 1.00 0.00B1= 11 1.00 -0.50 0.00 1.00z = -0.50 -1.00 -1.00 0.50 1.50 -4.00 0.00 -0.50 0.50 0.00 0.00xb= -1 -1 1 -1 -1 -1 0 1 -1 0 0x = 0.00 0.00 4.00 0.00 0.00 0.00 2.00 4.00 0.00 8.00 1.00

dx= 0.00 0.00 0.00 0.00 0.00 1.00 -1.00 0.00 0.00 -3.00 -1.00##### entra x6=0 sai x11=0 (s=3) #####

xb y ------ B1 ------B1= 7 2.50 1.00 0.00 -1.00B1= 10 1.00 2.50 1.00 -3.00B1= 6 -3.00 -0.50 0.00 1.00z = -2.50 -1.00 3.00 -1.50 -0.50 0.00 0.00 0.70 -1.50 0.00 4.00xb= -1 -1 1 -1 -1 -1 0 1 -1 0 -1x = 0.00 0.00 4.00 0.00 0.00 1.00 1.00 4.00 0.00 5.00 0.00dx= 0.00 0.00 -1.00 0.00 0.00 1.00 -1.00 0.00 0.00 -3.00 0.00##### entra x3=4 sai x7=0 (s=4) #####

xb y ------ B1 ------B1= 3 -0.50 -1.00 0.00 1.00B1= 10 1.00 -0.50 1.00 0.00B1= 6 0.00 0.50 0.00 0.00z = 0.50 -1.00 0.00 -1.50 2.50 0.00 3.00 -0.50 1.50 0.00 1.00xb= -1 -1 0 -1 -1 0 -1 1 -1 0 -1x = 0.00 0.00 3.00 0.00 0.00 2.00 0.00 4.00 0.00 2.00 0.00dx= 0.00 0.00 0.00 1.00 0.00 0.50 0.00 0.00 0.00 -1.50 0.00##### entra x4=0 sai x10=0 (s=*) #####

xb y ------ B1 ------

B1= 3 0.00 -1.00 0.00 1.00B1= 4 0.00 -0.33 0.67 0.00B1= 6 0.00 0.33 0.33 0.00z = 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 1.00 1.00 1.00xb= -1 -1 0 0 -1 0 -1 1 -1 -1 -1x = 0.00 0.00 3.00 1.33 0.00 2.67 0.00 4.00 0.00 0.00 0.00dx= 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00>>

Fonte

Compilador Executavel

Entrada

Solucao

❄❄

✲✲

❄

❄

compilador: FORTRAN, C, PASCAL, etc.

editor de texto para Fonte e Entrada

MPS

Solver

Solucao

❄

❄

solver: CPLEX, MINOS, OSL, LINDO, etc.

editor de texto para MPS

Modelo Dados

Modelador

MPS

Solver

Solucao

❄ ❄

❄

❄

❄

modelador: GAMS, AMPL, LINGO, etc.

editor de texto para Modelo e Dados

ARQUIVOS: MPS

SOLVERS: CPLEX, MINOS, OSL, LINDO, PCx, MOMIP

MODELADORES: GAMS, AMPL, LINGO, MODLER

AMBIENTES: AIMMS, OPL Studio, XPRESS, MPL

Entrada MPS

NAME PRODROWS

N R00001

L R00002L R00003

L R00004COLUMNS

C00001 R00001 22.000000C00001 R00002 1.000000

C00001 R00003 2.000000

C00001 R00004 1.000000C00002 R00001 20.000000

C00002 R00002 2.000000C00002 R00003 1.000000

RHSRHSIDE R00002 600.000000

RHSIDE R00003 600.000000

RHSIDE R00004 250.000000ENDATA

Saıda MPS

SOLUTION FOR PROD

OBJECTIVE FUNCTION VALUE 8400.0000

VARIABLES:

COLUMN VALUE LOWER UPPER REDUCDED COST

C00001 200.0000 0.0000 INFINITY 0.0000

C00002 200.0000 0.0000 INFINITY 0.0000

CONSTRAINTS:

ROW LEVEL LOWER UPPER DUAL PRICE

R00002 600.0000 -INFINITY 600.00 8.000000

R00003 600.0000 -INFINITY 600.00 6.000000

R00004 200.0000 -INFINITY 250.00 0.000000

Quadro das Variaveis

coluna x d- d+ zX1 200 0 inf 0X2 200 0 inf 0

Quadro das Restricoes

linha Ax b- b+ yY 1 600 - inf 600 8Y 2 600 - inf 600 6Y 3 200 - inf 250 0

min{

c′x : b-≤Ax≤b+, d-≤x≤d+}

z=c-A′y

LINDO: Linear, INteractive, and Discrete Optimizer

MAX -100X + 20A + 12B

ST

A - 10X < 0

A + B < 11

B < 7

END

OPL: Optimization Programming Language

int+ m := 2, n := 3; File prod.dat

float c := [ 20, 22 ], b := [ 600, 600, 250 ];

float a := [ 1, 2; 2, 1; 1, 0 ];

int+ m, n; File prod.opl

float c[1..n], b[1..m], a[1..m,1..n];

var float+ x[1..n];

model prod

{ max sum( j:=1..n ) c[j]*x[j];

st{ forall( i:=1..m ) sum( j:=1..n ) a[i,j]*x[j]≤b[i]; }}solve prod;

MS428 PROGRAMACAO LINEAR

OBJETIVO

Apresentar a Teoria de Programacao Linear, os principais mode-

los e os metodos de solucao computacionalmente mais eficientes.

EMENTA

1. Introduc~ao – historico; resolucao grafica.

2. Formulac~ao – exemplos de modelos classicos: dieta, producao,

mistura, transporte, designacao, multiperıodo, multiproduto, etc.

3. Teoria basica – forma padrao; problema dual, condicoes de

complementaridade, teoremas basicos; propriedades de factibili-

dade e direcoes factıveis.

4. Metodo Simplex – solucoes basicas, metodo simplex primal,

inicializacao, metodo simplex dual, pos-otimizacao, analise pa-

rametrica, geometria.

5. Metodo de Pontos Interiores – definicoes, metodo seguidor

de caminho, metodo de predicao e correcao, variaveis canaliza-

das, variaveis livres.

6. Programac~ao Linear na pratica – pacotes, protocolos de en-

trada, protocolos de saıda, modelagem algebrica.

BIBLIOGRAFIA

• Bazaara, Jarvis & Sherali, Linear Programming and Network Flows, Wiley

• Murty, Linear and Combinatorial Programming, Wiley

• Bregalda, Oliveira & Bornstein, Introducao a Programacao Linear, Campus

• Puccini & Pizzolato, Programacao Linear, Livros Tecnicos

• Hadley, Programacao Linear, Guanabara Dois

• Schrijver, Theory of Linear and Integer Programming, Wiley

• Chvatal, Linear Programming

• Gonzaga, Algoritmos de Pontos Interiores para Programacao Linear, 17o.

Coloquio Brasileiro de Matematica - IMPA/CNPq

MS428 AVALIACAO 1s13

3as. 14-16h CB09 × 5as. 14-16h CB06

inıcio: 01/08, fim: 30/11+17/12,

sem aulas: 07/09, 10,12,28/10, 2,15,16,20/11

Criterio:

P1: 31/10/13, P2: 14/11/13, E: 12/12/13

MP = ( P1 + P2 ) / 2

se MP≥5, aprovado

se MP<5, faz exame E e MF=(MP+E)/2

se MF≥5, aprovado

se MF<5, reprovado

obs. Alunos aprovados com MP≥5 podem ter acrescimo de ate

um ponto na media final baseado na media de testes de 15min.

EXERCICIOS

SKU: Stock Keeping Unit

?© Fabricar produtos P1,P2 com insumos I1,I2,I3:

Ins \ Prod P1 P2 disponıvel

I1 11 21 210I2 A 12 22 220 bI3 13 23 230

demanda d 110 120 ≤lucro c $51 $52

a) Formular (variaveis): Maximizar o lucro total.

b) Venda casada: forcar venda de P1 que tem demanda menor

c) Vendas com propaganda em regiao nova: lucro c=[40,40]

d) Terceirizacao parcial da pintura: lucro c=[41,42]

e) Defeito de fabricacao causa ι=13% de reposicao

. ?© Formular (variaveis): Maximizar o lucro total.

☼ xj: qtde. de produto vendido

max{ c′x : Ax≤b, x≤d, x≥0 }

. ?© Venda casada: forcar venda de P1 que tem demanda menor

☼ xj: qtde. de produto vendido

max{ c′x : Ax≤b, x≤d, x1-x2≥0, x≥0 }

. ?© Vendas adicionais com propaganda em regiao nova: lucro c=[40,40]

☼ xj: qtde. de produto vendido sem propaganda

☼ sj: qtde. adicional de produto vendido com propaganda

max{ c′x+c′s : A(x+s)≤b, x≤d, x, s≥0 }

!© solucao otima com xj+sj>dj tem xj=dj pois cj>cj

. ?© Terceirizacao parcial da pintura:

lucro reduz para c=[41,42] na producao acima de x1+x2>f=200

☼ uj: qtde. de produto pintado na empresa

☼ vj: qtde. de produto pintado fora

max{ c′u+c′v : A(u+v)≤b, (u+v)≤d, u1+u2≤f, u, v≥0 }

. ?© Defeito de fabricacao causa ι=13% de reposicao

☼ wj: qtde. de produto fabricado

max{ (1-ι)c′w : Aw≤b, w≤(1+ι)d, w≥0 }

?© min{c′x : Ax = b, x≥0} tem base B=[A1|A4|A5]:

c 2 6 5 3 2 1 b-1 -1 0 0 1 1 1

A 2 1 1 -1 -1 0 2

0 1 0 1 0 -1 3

B=

-1 0 1

2 -1 -1

0 1 0

=

1 1 1

0 0 1

2 1 1

-1

a) problema artificial e solucao inicial para o metodo das 2 fases.

b) problema canonico de B e a sua solucao basica.

c) base B e otima?

d) valores de b1(=1) com B otima.

e) valores de c4(=3) com B otima.

f) valores de a22(=1) com B otima.

g) valores de c2(=6) com B otima.

h) obter solucao otima para c2=2 (atual 6).

i) obter solucao otima para b1=-3 (atual 1).

. ?© min{c′x : Ax = b, x≥0} tem base B=[A1|A4|A5]:

c 2 6 5 3 2 1 b-1 -1 0 0 1 1 1

A 2 1 1 -1 -1 0 2

0 1 0 1 0 -1 3

B=

-1 0 1

2 -1 -1

0 1 0

=

1 1 1

0 0 1

2 1 1

-1

a) problema artificial e solucao inicial para o metodo das 2 fases.

F1: min{ 1′w : Ax+ w = b, x, w≥0 }, Base B=I=B-1:

w=b=[1;2;3], x=0 y′=1′B-1=[1,1,1], z=c-A′y=[-1;-1;-1;0;0;0;0;0]

c 0 0 0 0 0 0 1 1 1 b-1 -1 0 0 1 1 1 0 0 1

A 2 1 1 -1 -1 0 0 1 0 2

0 1 0 1 0 -1 0 0 1 3

x x1 x2 x3 x4 x5 x6 w1 w2 w3

. ?© min{c′x : Ax = b, x≥0} tem base B=[A1|A4|A5]:

c 2 6 5 3 2 1 b-1 -1 0 0 1 1 1

A 2 1 1 -1 -1 0 2

0 1 0 1 0 -1 3

B=

-1 0 1

2 -1 -1

0 1 0

=

1 1 1

0 0 1

2 1 1

-1

b) problema canonico de B e a sua solucao basica.

min{ c′x : Ax = b, x≥0 }, A = B-1A =

1 1 1 0

1 0 1 -1

0 1 1 1

xB=b=B-1b=[6;3;7], x=[6;0;0;3;7;0], c′x=b′y=35

y′=[2,3,2]B-1=[6,4,7], z=c=c-A′y=[0;1;1;0;0;2]

. ?© base B e otima? Sim, b≥0, c≥0

. ?© min{c′x : Ax = b, x≥0} tem base B=[A1|A4|A5]:

c 2 6 5 3 2 1 b-1 -1 0 0 1 1 1

A 2 1 1 -1 -1 0 2

0 1 0 1 0 -1 3

B=

-1 0 1

2 -1 -1

0 1 0

=

1 1 1

0 0 1

2 1 1

-1

d) valores de b1(=1) com B otima.

b = [b1; 2; 3]

b = B-1b = [ b1+5; 3; 2b1+5 ]≥0: b1≥− 5/2

. ?© min{c′x : Ax = b, x≥0} tem base B=[A1|A4|A5]:

c 2 6 5 3 2 1 b-1 -1 0 0 1 1 1

A 2 1 1 -1 -1 0 2

0 1 0 1 0 -1 3

B=

-1 0 1

2 -1 -1

0 1 0

=

1 1 1

0 0 1

2 1 1

-1

e) valores de c4(=3) com B otima.

cB = [2; c4; 2]

y′ = [2, c4,2]B-1 = [ 6, 4, c4+4 ]

c = c-A′y = [ 0; 4-c4; 1; 0; 0; c4-1 ]≥0: c4 ∈ [1,4]

. ?© min{c′x : Ax = b, x≥0} tem base B=[A1|A4|A5]:

c 2 6 5 3 2 1 b-1 -1 0 0 1 1 1

A 2 1 1 -1 -1 0 2

0 1 0 1 0 -1 3

B=

-1 0 1

2 -1 -1

0 1 0

=

1 1 1

0 0 1

2 1 1

-1

f) valores de a22(=1) com B otima.

A2 = [−1; a22; 1]

c2 = c2-y′A2 = 6-[6,4,7][-1; a22; 1] = 5-4a22≥0: a22≤5/4

. ?© min{c′x : Ax = b, x≥0} tem base B=[A1|A4|A5]:

c 2 6 5 3 2 1 b-1 -1 0 0 1 1 1

A 2 1 1 -1 -1 0 2

0 1 0 1 0 -1 3

B=

-1 0 1

2 -1 -1

0 1 0

=

1 1 1

0 0 1

2 1 1

-1

g) valores de c2(=6) com B otima.

c2

c2 = c2 − y′A2 = c2 − [6,4,7][−1; 1; 1] = c2 − 5≥0: c2≥5

. ?© min{c′x : Ax = b, x≥0} tem base B=[A1|A4|A5]:c 2 2 5 3 2 1 b

-1 -1 0 0 1 1 1

A 2 1 1 -1 -1 0 2

0 1 0 1 0 -1 3

B=

-1 0 12 -1 -1

0 1 0

=

1 1 10 0 1

2 1 1

-1

h) obter solucao otima para c2=2 (atual 6).xB inv(B) x1 x2 x3 x4 x5 x6 b

◦ 1 -6 -4 -7 -3x1 0 1 1 1 1 6

x4 0 0 0 1 ➀ 3x5 0 2 1 1 0 7

• 1 -6 -4 -4 -1

x1 0 1 1 0 ➀ 3x2 0 0 0 1 -1 3

x5 0 2 1 1 1 7

∗ 1 -5 -3 -4 1 0 2 2 0 0

x6 0 1 1 0 3x2 0 1 1 1 6

x5 0 1 0 1 4

otimo 23:x=[0 6 0 0 4 3]

y=[5 3 4]z=[1 0 2 2 0 0]

. ?© min{c′x : Ax = b, x≥0} tem base B=[A1|A4|A5]:c 2 6 5 3 2 1 b

-1 -1 0 0 1 1 -3A 2 1 1 -1 -1 0 2

0 1 0 1 0 -1 3

B=

-1 0 12 -1 -1

0 1 0

=

1 1 10 0 1

2 1 1

-1

i) obter solucao otima para b1 = -3 (atual 1)

simplex dualxB inv(Q) x1 x2 x3 x4 x5 x6 = Q

1 -6 -4 -7 . 1 1 . . 2 -11 1 2 3 2

1 0 1 1 1 1 1 1 . . 0 2 0 -1 0 1

4 0 0 0 1 . 1 0 1 . -1 3 0 2 -1 -1

5 0 2 1 1 . 0 1 . 1 1 -1 0 0 1 0

Problema infactıvel L3: x3+x5+x6=-1

Dir.inf. yλ=[6 4 7]+λ[2 1 1] zλ=[0 1 1 0 0 2]+λ[0 0 1 0 1 1] b′yλ=11+λ

?© Primal: Dual? Folgas? x=[0, α, β]?

min x1 + 2x2 + x3suj x1 + 2x2 + 3x3 = 8

x1 + x2 + x3 ≥ 2x1 + x2 = 1x1 , x2 ≥ 0

?© Primal: Dual? Folgas? x=[0, α, β]?

min x1 + 2x2 + x3suj x1 + 2x2 + 3x3 = 8

x1 + x2 + x3 ≥ 2x1 + x2 = 1x1 , x2 ≥ 0

min[1 2 1]x[1 2 3]x = 8[1 1 1]x≥2[1 1 0]x = 1x1, x2≥0

max[8 2 1]y[1 1 1]y≤1[2 1 1]y≤2[3 1 0]y = 1y2≥0

([1 1 1]x-2)y2 = 0([1 1 1]y-1)x1 = 0([2 1 1]y-2)x2 = 0

P1,P3: α=1, β=2, ∴ x=[0,1,2] e factıvel

D3,C1,C3: y=[1/3,0,4/3] e complementar mas nao e factıvel

Portanto, x=[0, α, β] nao e otimo para nenhum par de valores α, β

?© Obter Vertice Otimo a partir de Otimo II.

c -1 3 2 2 5 8 7 b1 1 0 0 1 1 2 3

A -2 0 1 2 2 2 1 40 2 1 0 2 1 2 6

x 1 1 2 1 1 0 0

c -1 3 2 2 5 8 7 b B-1

1 1 0 0 1 1 2 3A -2 0 1 2 2 2 1 4

0 2 1 0 2 1 2 6x 1 1 2 1 1 0 0

c . 0 . . 0 4 2x1 1 1 . . 1 1 2 3 1 0 0x4 . 0 . 1 1 3/2 3/2 2 1 1/2 -1/2

x3 . 2 1 . 2 1 2 6 0 0 1

A2=A1+2A3 A5=A1+A4+2A3

x =[ 1 1 2 1 1 0 0 ]

λ× ~x =[ 1 -1 2 0 0 0 0 ]

µ× ~x =[ 1 0 2 1 -1 0 0 ]

xλµ=[1+λ+µ,1-λ,2+2λ+2µ,1+µ,1-µ]≥0vertice x=[3,0,6,2,0,0,0] para λ=µ=1

intercessao de λ≤1 × µ≤1 (x2=x5=0)

1

−11−1−2λ

µ

?© Alocar pedidos P1:P6 a maquinas similares M1:M5.c: custos de producao de Pi em Mj,

a: tempos de maquina de Pi em Mj,b: disponibilidade da maquina de Mj,d: quantidade pedida de de Pi,

v: preco cobrado de Pia c d v

M1 M2 M3 M4 M5 M1 M2 M3 M4 M5 dmnd vendaP1 0.50 0.75 0.90 0.80 0.60 2.00 2.50 2.75 2.45 2.30 50 5.00P2 0.75 1.13 1.35 1.20 0.90 3.25 3.50 3.75 3.50 2.85 100 10.00P3 0.40 0.60 0.72 0.64 0.48 1.85 2.00 2.25 2.00 1.75 150 8.00P4 0.50 0.45 0.54 0.48 0.36 2.10 2.30 2.50 2.25 2.00 200 6.50P5 1.25 1.88 2.25 2.00 1.50 5.20 6.00 7.50 8.00 7.00 125 14.00P6 0.60 0.90 1.08 0.96 0.72 9.10 9.50 11.20 10.00 9.80 75 20.00

b 120 140 120 110 150

a) Maximizar lucro totalb) Nao alocar P1,P2 em M1,M2

c) Alocar P1,P2 em M1,M2

d) Alocar M1,M2 para P1,P2

e) Alocar M1,M2 para P1,P2 e P1,P2 em M1,M2

. ?© Maximizar lucro total

☼ xij: quantidade de Pi alocado em Mj

max

∑

ij

(vi-cij)xij :∑

i

aijxij≤bj,∑

j

xij=di, x≥0

. ?© Nao alocar P1,P2 em M1,M2

xij=0, i=1:2, j=1:2

. ?© Alocar P1,P2 em M1,M2

xij=0, i∈1:2, j /∈1:2. ?© Alocar M1,M2 para P1,P2

xij=0, i/∈1:2, j∈1:2. ?© Alocar M1,M2 para P1,P2 e P1,P2 em M1,M2

xij=0, i∈1:2, j /∈1:2; xij=0, i/∈1:2, j∈1:2

?© B=[A3, A4, A5] e otima com α, β, γ, λ, µ? min{c′x : Ax=b, x≥0}min [ 1 γ µ 0 1 ] x

suj

1 2 1 0 0

2 1 0 1 0

α 1 0 0 λ

x=

β6

2

B=

1 0 0

0 1 0

0 0 λ

=

1 0 0

0 1 0

0 0 1λ

-1

λ6=0

y′=[µ,0,1]B-1=[µ,0, 1λ], zN=cN-N ′y=[

1-µ-αλ≥0γ-2µ-1λ≥0

]

xB=B-1b=

β≥06≥02λ≥0

∴

β≥0 λ(1-µ)≥α

λ>0 λ(γ-2µ)≥1

. ?© Resolver com simplex dual em x≥0

min [ 0 0 0 0 1 ] xsuj [ 1 2 -1 0 0 ] x = 6

[ 2 1 0 -1 0 ] x = 6[ 1 1 0 0 -1 ] x = 5

. ?©

min [ 0 0 0 0 1 ] xsuj [ 1 2 -1 0 0 ] x = 6

[ 2 1 0 -1 0 ] x = 6

[ 1 1 0 0 -1 ] x = 5

xB inv(Q) x1 x2 x3 x4 x5 = Q

1 0 0 1 1 1 . . . 5 1 0 0 1

3 . -1 0 0 -1 -2 1 . . -6 . -1 0 0

4 . 0 -1 0 -2 -1 . 1 . -6 . 0 -1 05 . 0 0 -1 -1 -1 . . 1 -5 . 0 0 -1

1 0 0 0 . 0 . . 1 0 1 0 0 0

3 . -1 0 1 . -1 1 . -1 -1 . -1 0 1

4 . 0 -1 2 . 1 . 1 -2 4 . 0 -1 21 . 0 0 1 1 1 . . -1 5 . 0 0 1

1 0 0 0 . . 0 . 1 0 1 0 0 0

2 . 1 0 -1 . 1 -1 . 1 1 . 2 0 1

4 . -1 -1 3 . . 1 1 -3 3 . 1 -1 21 . -1 0 2 1 . 1 . -2 4 . 1 0 1

otimo 0: x=[4;1;0;3;0], y=[0;0;0], z=[0;0;0;0;1]

?© Resolver com simplex primal 2 fases em x≥0

min [ 0 0 0 0 1 ] xsuj [ 1 2 -1 0 0 ] x = 6

[ 2 1 0 -1 0 ] x = 6[ 1 1 0 0 -1 ] x = 5

min [ 0 0 0 0 0 1 1 1 ] xsuj [ 1 2 -1 0 0 1 ] x = 6x≥0 [ 2 1 0 -1 0 1 ] x = 6

Fase1 [ 1 1 0 0 0 1 ] x = 5

xB inv(Q) = As

◦ 1 -1 -1 -1 -17 -4x6 . 1 0 0 6 1

x7 . 0 1 0 6 2x8 . 0 0 1 5 1

• 1 -1 1 -1 -5 -2

x6 . 1 -1/2 0 3 3/2x1 . 0 1/2 0 3 1/2

x8 . 0 -1/2 1 2 1/2

⋄ 1 1/3 1/3 -1 -1 -1/2

x2 . 2/3 -1/3 0 2 -2/3x1 . -1/3 2/3 0 2 1/3

x8 . -1/3 -1/3 1 1 1/3

+ 1 0 0 0 0x2 . 0 -1 2 4

x1 . 0 1 -1 1x3 . -1 -1 3 3

z=[0,0,0,0,0,1,1,1]≥0 FIM DE F1B=[A2|A1|A3] e factıvel

BASE B = [A2|A1|A3]

xB B-1 b A4

∗ 1 0 0 0 0 0x2 . 0 -1 2 4 1

x1 . 0 1 -1 1 -1

x3 . -1 -1 3 3 1

⋆ 1 0 0 0 0

x2 . 1 0 -1 1x1 . -1 0 2 4

x4 . -1 -1 3 3

otimos ∗, ⋆: z=[0,0,0,0,1]≥0αx∗+(1-α)x⋆: α∈[0,1]x∗=[1;4;3;0;0], x⋆=[4;1;0;3;0]

min[ 0 0 0 0 1 ] xsuj[ 1 2 -1 0 0 ] x = 6

x≥0 [ 2 1 0 -1 0 ] x = 6[ 1 1 0 0 -1 ] x = 5

min[ 1 1 0 0 0 ] x1

2

3

4

5

6

7

1 2 3 4 5 6 7◦ •⋄∗

⋆x1

x2

[x3]

[x4]

[x5]

. ?© Obter Vertice Otimo a partir de Otimo: min{c′x : Ax=b, x≥0}c 3 1 4 1 4 1 4 b

3 1 2 1 2 1 2 8A 2 0 2 1 1 1 1 5

1 0 1 0 0 1 1 3x 1 2 0 1 0 2 0

A1 A2 A4 A6

1 . . . 3 2 1. 1 . . 1 0 0 -. . 1 . 1 1 0 -. . . 1 1 1 1 -1 -1 -1 -1 . . .0 1 0 0 1 . . -0 -1 1 0 . 1 . -0 0 -1 1 . . 1 -

Teste de LI~x=[1; -1; 0; -1; 0; -1; 0], c′~x=0

pivos em (4,7), (3,6), (2,5){A6, A4, A2} sao LI

1 1 1

0 1 10 0 1

-1

=

1 -1 0

0 1 -10 0 1

x(λ) = [1;2;0;1;0;2;0]+ λ[1;-1;0;-1;0;-1;0]≥0, λ∈[-1, +1]

x(-1)=[0;3;0;2;0;3;0] x(+1)=[2;1;0;0;0;1;0] c′x(λ) = 8, ∀λ

?© Primal: Dual? Folgas? x=(0,1,2, α)?

min 10x1 + 8x2 + 6x3 + 5x4suj 2x1 + 2x2 + x3 + x4 ≥ 5

3x1 + 2x2 + 2x3 + x4 ≥ 93x1 + 3x2 + 2x3 + 2x4 = 13x1 , x2 ≥ 0

. ?© Primal: Dual? Folgas? x=(0,1,2, α)?

min 10x1 + 8x2 + 6x3 + 5x4suj 2x1 + 2x2 + x3 + x4 ≥ 5

3x1 + 2x2 + 2x3 + x4 ≥ 93x1 + 3x2 + 2x3 + 2x4 = 13x1 , x2 ≥ 0

min[10 8 6 5]x[2 2 1 1]x≥5[3 2 2 1]x≥9[3 3 2 2]x = 13x1, x2≥0

max[5 9 13]y[2 3 3]y≤10[2 2 3]y≤8[1 2 2]y = 6[1 1 2]y = 5y1, y2≥0

([2 2 1 1]x-5) y1 = 0([3 2 2 1]x-9) y2 = 0([2 3 3]y-10) x1 = 0([2 2 3]y-8) x2 = 0

P3: α=3 ∴ x=[0,1,2,3] e factıvel (P1..P4)

D3,D4,C4: y=[0,1,2] e complementar C1..C4 e e factıvel D1..D4

Portanto, x=[0; 1; 2;α] e otimo (obj=35) para α=3

. ?© Formular: ( variaveis! )

bk microcomputadores Mk, vendidos por vk, tem aik componentes

Ci (processador, disco rıgido, monitor, etc.) montados por cik, obtidos por

dij de fornecedores Fj com estoque qij.

. ?© Formular: ( variaveis! )

bk microcomputadores Mk, vendidos por vk, tem aik componentes

Ci (processador, disco rıgido, monitor, etc.) montados por cik, obtidos por

dij de fornecedores Fj com estoque qij.

☼ xijk – qtde de Ci fornecido por Fj em micro Mk (max. lucro)

max

∑

ijk

(vk-cik-dij)xijk :∑

j

xijk=aikbk ∀ik,∑

k

xijk≤qij ∀ij, x≥0

+© Ci i∈I: fontes com potencia wi que alimentam Ci de consumo ωi

∑

ij

ωixijk ≤∑

i∈Iwiaik

. ?©

+© Rℓ: fabricas com capacidade rℓ:∑

ijk xijkℓ≤rℓ☼ xijkℓ – qtde de Ci fornecido por Fj em micro Mk da fabrica Rℓ

• custo de transporte fornecedor-fabrica e fabrica-cliente

+© Hn: horizonte do plano (demanda bkn):∑

j xijkℓn=aikbkn☼ xijkℓn – qtde de Ci de Fj em micro Mk da fabrica Rℓ no mes n

• estoques de Ci, de micros e custos ao longo do horizonte.

?© Primal: Dual? Folgas? x=[α; 1; 2]?

max 3x1 + 4x2 + 3x3suj x1 + 2x2 + 2x3 ≤ 6

2x1 + 2x2 + x3 ≤ 2x1 + 2x2 + x3 = 4x1 , x2 ≥ 0

. ?© Primal: Dual? Folgas? x=[α; 1; 2]?

max 3x1 + 4x2 + 3x3suj x1 + 2x2 + 2x3 ≤ 6

2x1 + 2x2 + x3 ≤ 2x1 + 2x2 + x3 = 4x1 , x2 ≥ 0

max[3 4 3]x[1 2 2]x≤6[2 2 1]x≤2[1 2 1]x = 4x1, x2≥0

min[5 9 13]y[1 2 1]y≥3[2 2 2]y≥4[2 1 1]y = 3y1, y2≥0

([1 2 2]x-6) y1 = 0([2 2 1]x-2) y2 = 0([1 2 1]y-3) x1 = 0([2 2 2]y-4) x2 = 0

P3: α=0 ⇒ x=[0;1;2] nao e factıvel (P1..P4)

Portanto, x=[α; 1; 2] nao e otimo para nenhum α

?© min{c′x : Ax=b, x≥0}: α, β, γ, λ, µ para base otima B=[A1|A2|A3]?

c 0 µ 0 1 1 γ 1 b

1 0 0 1 1 1 0 βA 1 1 0 0 1 0 α 3

1 1 λ 1 0 0 0 6

B=

1 0 01 1 01 1 λ

=

1 0 0-1 1 0

0 -1λ1λ

-1

. ?© min{c′x : Ax=b, x≥0}: α, β, γ, λ, µ para base otima B=[A1|A2|A3]?

c 0 µ 0 1 1 γ 1 b

1 0 0 1 1 1 0 βA 1 1 0 0 1 0 α 3

1 1 λ 1 0 0 0 6

B=

1 0 01 1 01 1 λ

=

1 0 0-1 1 0

0 -1λ1λ

-1

y′=c′BB-1=[0, µ,0]B-1=[-µ, µ,0] λ6=0

cN=cN-N ′y=[1+µ; 1; γ+µ; 1-αµ]≥0 ∴

µ≥-1 µ+γ≥0 αµ≤1

b=B-1b=

β3-β3/λ

≥0 ∴ 0≤β≤3 λ>0

. ?© FASE 1 para min{c′x : Ax=b, x≥0}?

c 0 0 0 1 1 1 1 b1 0 0 1 1 1 0 1

A 1 1 0 0 1 0 1 31 1 1 1 0 0 0 6

max{ 1′w : Ax+ w = b, x≥0, w≥0 }

x w bc 0 0 0 0 0 0 0 1 1 1

1 0 0 1 1 1 1 1 0 0 1A 1 1 0 0 1 0 1 0 1 0 3

1 1 1 1 0 0 0 0 0 1 6

?© min{c′x : Ax=b, x≥0} tem base otima B=[A1|A2|A3]?

c 0 0 0 1 1 1 1 b1 0 0 1 1 1 0 1

A 1 1 0 0 1 0 1 31 1 1 1 0 0 0 6

B=

1 0 01 1 01 1 1

=

1 0 0-1 1 00 -1 1

-1

xB = b = B-1b = [1; 2; 3] x = [1; 2; 3; 0; 0; 0; 0]≥0

y′ = cBB-1 = [0,0,0] z = c = c− A′y = [0; 0; 0; 1; 1; 1; 1]≥0

Portanto, x e primal factıvel, (y, z) e dual factıvel e B e otima.

?© min{c′x : Ax=b, x≥0}: iniciar simplex primal com B=[A1|A2|A3]

c 0 0 0 -1 1 1 1 b1 0 0 1 1 1 0 1

A 1 1 0 0 1 0 1 31 1 1 1 0 0 0 6

B=

1 0 01 1 01 1 1

=

1 0 0-1 1 00 -1 1

-1

. ?© min{c′x : Ax=b, x≥0}: iniciar simplex primal com B=[A1|A2|A3]

c 0 0 0 -1 1 1 1 b1 0 0 1 1 1 0 1

A 1 1 0 0 1 0 1 31 1 1 1 0 0 0 6

B=

1 0 01 1 01 1 1

=

1 0 0-1 1 00 -1 1

-1

xB inv(Q) x b Q

x0 1 0 0 0 . . . -1 1 1 1 0 1 0 0 0

x1 . 1 0 0 1 . . 1 1 1 0 1 . 1 0 0

x2 . -1 1 0 . 1 . -1 0 1 1 2 . 1 1 0

x3 . 0 -1 1 . . 1 1 -1 0 -1 3 . 1 1 1

x0 1 1 0 0 1 . . . 2 2 1 1 1 -1 0 0

x4 . 1 0 0 1 . . 1 1 1 0 1 . 1 0 0

x2 . 0 1 0 1 1 . . 1 0 1 3 . 0 1 0

x3 . -1 -1 1 -1 . 1 . -2 -1 -1 2 . 1 1 1

otimo -1: x=[0;3;2;1;0;0;0], y=[-1;0;0], z=[1;0;0;0;2;2;1]

?© min{c′x : Ax=b, x≥0}: iniciar simplex dual com B=[A1|A2|A3]

c 0 0 0 1 1 1 1 b1 0 0 1 1 1 0 4

A 1 1 0 0 1 0 1 31 1 1 1 0 0 0 6

B=

1 0 01 1 01 1 1

=

1 0 0-1 1 00 -1 1

-1

. ?© min{c′x : Ax=b, x≥0}: iniciar simplex dual com B=[A1|A2|A3]

c 0 0 0 1 1 1 1 b1 0 0 1 1 1 0 4

A 1 1 0 0 1 0 1 31 1 1 1 0 0 0 6

B=

1 0 01 1 01 1 1

=

1 0 0-1 1 00 -1 1

-1

xB inv(Q) x b Q

x0 1 0 0 0 . . . 1 1 1 1 0 1 0 0 0

x1 . 1 0 0 1 . . 1 1 1 0 4 . 1 0 0

x2 . -1 1 0 . 1 . -1 0 -1 1 -1 . 1 1 0

x3 . 0 -1 1 . . 1 1 -1 0 -1 3 . 1 1 1

x0 1 -1 1 0 . 1 . . 1 0 2 -1 1 0 1 0

x1 . 0 1 0 1 1 . . 1 0 1 3 . 1 1 0

x4 . 1 -1 0 . -1 . 1 0 1 -1 1 . 1 0 0

x3 . -1 0 1 . 1 1 . -1 -1 0 2 . 1 1 1

otimo 1: x=[3;0;2;1;0;0;0], y=[1;-1;0], z=[0;1;0;0;1;0;2]

?© Obter Vertice

c 0 0 0 1 1 1 1 b1 0 0 1 1 1 0 1

A 1 1 0 0 1 0 1 31 1 1 1 0 0 0 6

x 13

43

133 0 1

313 1

xB -2 -1 . 0 -1 . . bx6 1 0 . 1 1 1 . 1x7 1 1 . 0 1 . 1 3x3 1 1 1 1 0 . . 6

x . . 6 . . 1 3x=[0;0;6;0;0;1;3]: Vertice da base B=[A6|A7|A3]

~x=[1;0;-1;0;0;-1;-1]: Direcao de λ ( A1=A6+A7+A3 )

~x=[0;1;-1;0;0;0;-1]: Direcao de µ ( A2=A7+A3 )

~x=[0;0;0;0;1;-1;-1]: Direcao de ν ( A5=A6+A7 )

xλµν=x+λ~x+µ~x+ν~x≥0 ∴ λ, µ, ν≥0, λ+µ≤6, λ+ν≤1, λ+µ+ν≤3

PROVAS

PROBLEMA min ⇐ | ⇒ max PROBLEMA

≥ | ≥0restricao = ⇐ | ⇒ livre variavel

≤ | ≤0≥0 | ≤

variavel livre ⇐ | ⇒ = restricao≤0 | ≥

A=[ B | N ] : A=B-1A, xB=b=B-1b, xN=0, y′=c′BB

-1, z=c=c-A′y

solucao factıvel basica (vertice) x : Ax=b, x≥0, { Aj : xj>0 } e LI

MS428 PROVA I 2s13

Considere o PL abaixo:a) Escreva o problema dual.b) Escreva as condicoes de folgas complementares.c) Verifique se x=[2;α;β; 2] pode ser uma solucao otima.

P0: [6 4 3 4]x max

P1: [1 1 0 1]x ≤ 6P2: [1 1 1 0]x = 4P3: [1 0 1 1]x = 4P4: x3, x4 ≥ 0

D0: [6 4 4]y min

D1: [1 1 1]y = 6D2: [1 1 0]y = 4D3: [0 1 1]y ≥ 3D4: [1 0 1]y ≥ 4D5: y1 ≥ 0

F1: ([0 1 1]y − 3)x3 = 0F2: ([1 0 1]y − 4)x4 = 0F3: ([1 1 0 1]x− 6)y1 = 0

• P2,P3: α=2, β=0. x=[2;2;0;2] e factıvel (P1,P2,P3,P4)

• D1,D2,F2: y=[2;2;2] e dual factıvel (D1,D2,D3,D4)

• x, y sao complementares (F1,F2,F3)

∴ x=[2;2;0;2] e otimo com α=2, β=0

!© y=[3,2,1] nao e factıvel (✟✟✟❍❍❍D2)!

Considere o PL min{ c′x : Ax=b, x≥0 }:c 1 0 1 0 1 µ γ b

1 -1 1 1 1 0 0 βA 1 1 -1 0 1 -1 1 2

0 0 0 0 1 λ α 1

x 1 1 1 1 1 0 0

B=

1 -1 00 1 -10 0 λ

=

1 1 1λ

0 1 1λ

0 0 1λ

-1

a) B=[A4|A2|A6] e base otima para quais α, β, γ, µ, λ?

b) Com β=3, obter vertice a partir da solucao x=[1; 1; 1; 1; 1; 0; 0].

a) detB 6=0: λ6=0

b = B-1b = [β+2+1λ; 2+1λ;

1λ] ≥ 0: β+2+1λ≥0 λ>0

y′ = c′BB = [0,0, µ]B-1 = [0,0, µ/λ]

z = [1; 0; 1; 0; 1-µ/λ; 0; γ-αµ/λ] ≥ 0: γλ≥αµ λ≥µ

b) A1=2A4+A5, A3=-A2, vertices x=[0;1;0;3;1;0;0], x=[1;0;0;1;1;0;0]

xB inv(Q) x1 x2 x3 x4 x5 x6 x7 = Q

x0 1 0 0 0 1 . 1 . 1 . 1 0 1 0 0 0

x4 . 1 1 -0 2 . 0 1 2 . 1 5 . 1 -1 1

x2 . 0 1 1 1 1 -1 . 2 . 2 3 . 0 1 -1

x6 . 0 0 1 0 . 0 . 1 1 1 1 . 0 0 1

x0 1 0 0 -1 1 . 1 . . -1 0 -1 1 0 0 1

x4 . 1 1 -2 2 . 0 1 . -2 -1 3 . 1 -1 1

x2 . 0 1 -1 1 1 -1 . . -2 0 1 . 0 1 1

x5 . 0 0 1 0 . 0 . 1 1 1 1 . 0 0 1

Considere o PL min{ c′x : Ax=b, x≥0 }c 1 0 1 0 1 0 -1 b

1 -1 1 1 1 1 0 3A 1 1 -1 0 1 -1 1 2

0 0 0 0 1 1 1 1

B-1=

1 -1 00 1 -10 0 1

-1

=

1 1 10 1 10 0 1

a) PL canonico A, b, c e solucao basica (x, y, z) de B=[A4|A2|A6]

b) Obtenha solucao otima (x, y, z) com o simplex.

c) Equacao da aresta xλ=x+λ~x do primeiro pivoteamento em (b).

b) x=[0;3;0;6;0;1;0], y=[0;0;0], z=[1;0;1;0;1;0;-1], obj=0

xB inv(Q) c / A b Q

c 1 0 1 0 1 0 -1 0

1 -1 1 1 1 1 0 3

A 1 1 -1 0 1 -1 1 2

0 0 0 0 1 1 1 1

x0 1 0 0 0 1 . 1 . 1 . -1 0 1 0 0 0

x4 . 1 1 1 2 . 0 1 3 . 2 6 . 1 -1 0

x2 . 0 1 1 1 1 -1 . 2 . 2 3 . 0 1 -1

x6 . 0 0 1 0 . 0 . 1 1 1 1 . 0 0 1

x0 1 0 0 1 1 . 1 . 2 1 . 1 1 0 0 -1

x4 . 1 1 -1 2 . 0 1 1 -2 . 4 . 1 -1 0

x2 . 0 1 -1 1 1 -1 . 0 -2 . 1 . 0 1 1

x7 . 0 0 1 0 . 0 . 1 1 1 1 . 0 0 1

otimo=-1: x=[0;1;0;4;0;0;1], y=[0;0;-1], z=[1;0;1;0;2;1;0]c) xλ = x+ λ~x =[0;3;0;6;0;1;0]+λ[0;-2;0;-2;0;-1;1]ou xλ = x+ λ~x =[0;1;0;4;0;0;1]−λ[0;-2;0;-2;0;-1;1]

Minimizar o custo de alocacao dos pedidos P1,P2,P3,P4 as maquinas M1,M2 (em paralelo).

αij - tempo de cada unidade de Pi em Mj,βi - quantidade pedida em Pi,δj - disponibilidade de Mj,γj - custo unitario de producao em Mj.

α P1 P2 P3 P4 δ γM1 2 3 3 4 1200 22M2 4 5 6 5 1500 45

β 110 120 130 140

Formule 2 PL’s identificando as variaveis de decisao:

a) Sem condicoes adicionais.

b) P2 requer urgencia (mostre como abordar esta exigencia).

a) xij: tempo da maquina Mj alocado para o pedido Pi.

min{ ∑

ij

γjxij :∑

i

xij ≤ δj,∑

j

xij/αij = βi, x≥0}

b) fazer x21=x22 e alocar P2 no inıcio em ambas as maquinas.

min{ ∑

ij γjxij :∑

i xij≤δj,∑

j xij/αij = βi, x21-x22 = 0, x≥0 }Comparar otimos de (a),(b) para estimar custo de urgencia.

ou©

a) qij: qtde do pedido Pi alocado na maquina Mj.

min{ ∑

ij

γjαijqij :∑

j

qij = βi,∑

i

αijqij ≤ δj, q≥0}

b) fazer α21q21=α22q22 e alocar P2 no inıcio nas maquinas.

min{ ∑

ij γjαijqij :∑

j qij=βi,∑

i αijqij≤δj, α21q21-α22q22=0, q≥0 }

MS428 PROVA II 2s13

Considere o PL abaixo:Escreva o problema dual.Escreva as condicoes de folgas complementares.Verifique se x=[1; 1; 1;α] pode ser uma solucao otima.

P0: [2 1 1 3]x min

P1: [1 1 0 1]x = 2P2: [1 1 1 0]x ≥ 2P3: [1 0 1 1]x ≥ 2P4: x3, x4≥0

D0: [2 2 2]y max

D1: [1 1 1]y = 2D2: [1 1 0]y = 1D3: [0 1 1]y ≤ 1D4: [1 0 1]y ≤ 3D5: y2, y3≥0

F1: ([0 1 1]y − 1)x3 = 0F2: ([1 0 1]y − 3)x4 = 0

F3: ([1 1 1 0]x− 2)y2 = 0F4: ([1 0 1 1]x− 2)y3 = 0

• P1: α=0. x=[1;1;1;0] e factıvel (P1,P2,P3,P4X)

• D1,D2,F1: y=[1;0;1] e dual factıvel (D1,D2,D3,D4,D5X)

• x, y sao complementares (F1,F2,F3,F4X)

∴ x=[1;1;1;0] e otimo com α=0

Considere o PL padrao min{ c′x : Ax=b, x≥0 }c δ 0 0 1 1 γ 1 b

1 1 1 0 0 0 0 3A 1 0 1 0 -1 1 -1 β

1 0 0 -1 0 1 α 0

x 1 1 1 1 1 0 0

B=

1 1 10 1 10 0 1

=

1 -1 00 1 -10 0 1

-1

Obtenha condicoes entre α, β, γ, δ para que B=[A2|A3|A1] seja base otima.

Faca β=1 e obtenha um vertice com x6=x7=0 a partir de x=[1; 1; 1; 1; 1; 0; 0].

detB 6=0:

b=[3-β;β;0]≥0: 0≤β≤3y′=[0,0,δ]B-1=[0,0,δ]

z=[0;0;0;1+δ;1;γ-δ;1-αδ]≥0: αδ≤1 -1≤δ≤γ

!© ✘✘✘✘✘✘❳❳❳❳❳❳α≤1/δ, ✘✘✘✘✘✘❳❳❳❳❳❳δ≤1/α s~ao incorretas pois pressup~oem denominador n~ao-nulo

A4=A3-A1, A5=A2-A3: vertice x=[0;2;1;0;0;0;0;0]

xB inv(Q) x1 x2 x3 x4 x5 x6 x7 = Q

0 1 0 0 -1 0 0 0 2 1 -2 2 0 1 0 0 1

2 0 1 -1 0 0 1 0 0 1 -1 1 2 0 1 1 1

3 0 0 1 -1 0 0 1 1 -1 0 0 1 0 0 1 1

1 0 0 0 1 1 0 0 -1 0 1 -1 0 0 0 0 1

x 1 1 1 1 1 0 0

ou© x=[1;2;0;1;0;0;0]

!©✭✭✭✭✭✭✭✭✭✭✭✭✭✭✭✭✭✭✭❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤x=[0;1;2;0;1;0;0] nao e vertice pois {A2|A3|A5} nao e LI

Considere o PL padrao min{ c′x : Ax=b, x≥0 }c 1 0 0 1 1 -1 1 b

1 1 1 0 0 0 0 3A 1 0 1 0 -1 1 -1 1

1 0 0 -1 0 1 -1 0

B-1=

1 -1 00 1 -10 0 1

=

1 1 10 1 10 0 1

-1

Escreva o PL canonico e a solucao basica (x, y, z) da base B=[A2|A3|A1]

Obtenha solucao otima (x, y, z) com o simplex.

Escreva a equacao da aresta xλ=x+λ~x do primeiro pivoteamento em (b).

x=[0;2;1;0;0;0;0], y=[0;0;1], z=[0;0;0;2;1;-2;2], obj=0

xB inv(Q) c / A b Q

1 0 0 1 1 -1 1 0

1 1 1 0 0 0 0 3

1 0 1 0 -1 1 -1 1

1 0 0 -1 0 1 -1 0

0 1 0 0 -1 0 0 0 2 1 -2 2 0 1 0 0 1

2 0 1 -1 0 0 1 0 0 1 -1 1 2 0 1 1 1

3 0 0 1 -1 0 0 1 1 -1 0 0 1 0 0 1 1

1 0 0 0 1 1 0 0 -1 0 1 -1 0 0 0 0 1

0 1 0 0 1 2 0 0 0 1 0 0 0 1 0 0 -1

2 0 1 -1 1 1 1 0 -1 1 0 0 2 0 1 1 0

3 0 0 1 -1 0 0 1 1 -1 0 0 1 0 0 1 1

6 0 0 0 1 1 0 0 -1 0 1 -1 0 0 0 0 1

x=[0;2;1;0;0;0;0], y=[0;0;-1], z=[2;0;0;0;1;0;0], obj=0

xλ = x+ λ~x =[0;2;1;0;0;0;0]+λ[-1;1;0;0;0;1;0]

Fabrica de 3 departamentos D1..D3 produz 4 moveis M1..M4.

αij: horas de producao de cada unidade de movel nos deptosγj: lucro de cada unidade de movel Mjδi: disponibilidade de horas de cada departamento Di

α mesa cadeira armario estante δCorte 6 2 4 4 500

Montagem 10 6 8 7 1200Acabamento 10 8 8 7 800

γ 175 95 145 130

Formular PL para maximizar o lucro.

Estimar o ganho de terceirizar parte do corte para aumentar a disponibili-

dade dos departamentos para δ+ = [700,1200,800]

xj: producao do movel Mj.

obj⋆ = max{

∑

j γjxj :∑

j αijxj≤δi, x≥0}

(x⋆, y⋆, z⋆)

ganho = obj+-obj⋆ onde

obj+ = max{

∑

j γjxj :∑

j αijxj≤δ+i , x≥0}

(x+, y+, z+)

!© y⋆1: ganho de 1h extra de corte, enqto base otima se mantem: B-1

[β

1200800

]

≥0