Aula 5

Prof. Tiago de Azevedo Santos

Enviei os slides de todas as aulas para ogrupo, incluindo a lista de exerccios.

Prova dia 07/04/2014.

Entrega da lista de exerccios at o dia daprova.

Na ultima aula vimos que...

J sabemos que em todo problema deprogramao linear (PPL) com soluo, asoluo tima est sempre em um vrtice;

Desse conhecimento podemos extrair duaspropriedades: Se um problema de otimizao linear tem uma

soluo tima, ento existe um vrtice timo.

Se uma soluo tima, ento ela um vrtice.

Sabendo dessas propriedades, se formoscapazes de pesquisar em todos os vrtices,iremos encontrar a soluo tima;

Podemos fazer melhor???

Se a partir de um vrtice, formos sempre paraoutro vrtice melhor iremos chegar nasoluo tima de forma mais rpida;

Basicamente essa a forma que o mtodosimplex funciona.

Este mtodo foi criado por George Dantzig e muito utilizado para a resoluo deproblemas de programao linear, servindode base inclusive para muitos softwaresresolvedores;

Podemos nos perguntar, porque no utilizaro mtodo grfico?;

Como ficaria um grfico com trs variveispor exemplo?

Max P = 20x1 + 10x2 + 15x3Sujeito a: 3x1 + 2x2 + 5x3 55

2x1 + x2 + x3 26x1 + x2 + 3x3 305x1 + 2x2 + 4x3 57x1 , x2 , x3 0

X2

X1

Noes de espao vetorial (2, 7) -> vetor do R

(7, -5, 8) -> vetor do R

(9, 3, ..., n) -> vetor do Rn

Combinao Linear de vetores Dados um grupo de vetores de um determinado

espao, podemos multiplicar cada um deles por umnmero qualquer e somar os resultados. O vetorobtido uma combinao linear dos vetores.

Exemplo

Mostrar que o vetor (11, 8) pode ser escrito comocombinao linear dos vetores (3, 4) e (1, 2);

Mostrar que o vetor (3, 4) no pode ser escritocomo combinao linear dos vetores (1, 2) e (4, 8);

Se um vetor no pode ser escrito comocombinao linear de um grupo de vetoresdizemos que este linearmenteindependente dos vetores do grupo.

A base de um espao vetorial um geradordo espao, isto , qualquer vetor do espaopode ser obtido como combinao linear dosvetores da base.

A combinao linear para gerar um vetor apartir da base resulta num sistema deequaes que tem soluo nica.

Outras formas de escrever um problema deprogramao linear:

Maximizar f = ctx

Sujeito a

Ax b ou

x 0

njx

bxa

xcMaximizar

j

jjj

jj

n

j

n

j

,...,1,0

1

1

Outras formas de escrever um problema deprogramao linear:

Maximizar Z = c1x1 + c2x2 + c3x3 + ... + cnxnSujeito a

a11x1 + a12x2 + a13x3 + ... + a1nxn b1a21x1 + a22x2 + a23x3 + ... + a2nxn b2a31x1 + a32x2 + a33x3 + ... + a3nxn b3x1, x2, x3 , ..., xn 0

Outras formas de escrever um problema deprogramao linear:

Maximizar Z = c1x1 + c2x2 + c3x3Sujeito a

a11 a12 a13 x1 b1a21 a22 a23 x2 b2a31 a32 a33 x3 b3

Outras formas de escrever um problema deprogramao linear:

Maximizar Z = c1x1 + c2x2 + c3x3Sujeito a

a11 a12 a13 x1 b1a21 a22 a23 x2 b2a31 a32 a33 x3 b3

Dizemos que essa uma matriz mxn. Isso significa que ela tem m

restries e n variveis. Essa matriz tambm conhecida como

matriz tecnolgica.

Forma padro (standard) de problemas deprogramao linear: Qualquer problema de programao linear pode ser

escrito na forma padro;

Para que um problema esteja na forma padro necessrio que:

todas as restries sejam de igualdade;

todas as variveis so no negativas ( 0);

Passos para a transformao do problemaem sua forma padro: Restries do tipo e so transformadas em

restries de igualdade por meio da introduo devariveis de folga;

Em restries do tipo , substitumos a desigualdade pelaigualdade e adicionamos uma varivel de folga positiva;

Em restries do tipo , substitumos a desigualdade pelaigualdade e adicionamos uma varivel de folga negativa;

Variveis livres de sinal so substitudas pela diferenaduas variveis no negativas.

Exemplo (maximizao)

Maximizar Z = c1x1 + c2x2 + c3x3 + ... + cnxnSujeito a

a11x1 + a12x2 + a13x3 + ... + a1nxn b1a21x1 + a22x2 + a23x3 + ... + a2nxn b2a31x1 + a32x2 + a33x3 + ... + a3nxn b3x1, x2, x3 , ..., xn 0

Exemplo (maximizao)

Maximizar Z = c1x1 + c2x2 + c3x3 + ... + cnxnSujeito a

a11x1 + a12x2 + a13x3 + ... + a1nxn + f1 = b1a21x1 + a22x2 + a23x3 + ... + a2nxn + f2 = b2a31x1 + a32x2 + a33x3 + ... + a3nxn + f3 = b3x1, x2, x3 , ..., xn, f1, f2, f3 0

Exemplo (maximizao):

Formato Cannico

Max Z = 2X1 + 5X2Sujeito a:

3X1 + 5X2 62X1 + 6X2 10X1 0X2 0

Formato Padro

Max Z = 2X1 + 5X2Sujeito a:

3X1 + 5X2 + X3 = 6

2X1 + 6X2 +X4 = 10

X1, X2, X3, X4 0

Exemplo (minimizao)

Minimizar Z = c1x1 + c2x2 + c3x3 + ... + cnxnSujeito a

a11x1 + a12x2 + a13x3 + ... + a1nxn b1a21x1 + a22x2 + a23x3 + ... + a2nxn b2a31x1 + a32x2 + a33x3 + ... + a3nxn b3x1, x2, x3 , ..., xn 0

Exemplo (minimizao)

Maximizar Z = - c1x1 - c2x2 - c3x3 - ... - cnxnSujeito a

a11x1 + a12x2 + a13x3 + ... + a1nxn - f1 = b1a21x1 + a22x2 + a23x3 + ... + a2nxn - f2 = b2a31x1 + a32x2 + a33x3 + ... + a3nxn - f3 = b3x1, x2, x3 , ..., xn, f1, f2, f3 0

Exemplo (minimizao):

Formato Cannico

Min Z = 3X1 + 6X2Sujeito a:

2X1 + 4X2 84X1 + 7X2 12X1 0X2 0

Formato Padro

Max - Z = - 3X1 - 6X2Sujeito a:

2X1 + 4X2 X3 = 84X1 + 7X2 X4 = 12X1, X2, X3, X4 0

Mas como o simplex funciona?

Vejamos um exemplo.

Exemplo:

Max Z = 120X1 + 150X2

Sujeito a:

2X1 + 4X2 1005X1 + 3X2 120X1 0X2 0

X2

X1

2X1 + 4X2 100

5X1 + 3X2 120

Max Z = 120X1 + 150X2

Sujeito a:

2X1 + 4X2 1005X1 + 3X2 120X1 0X2 0

Primeiro passo colocar o problema de

programao linear no formato padro.

Max Z = 120X1 + 150X2

Sujeito a:

2X1 + 4X2 + X3 = 100

5X1 + 3X2 + X4 = 120

O problema passa a ter 4 variveis em vez das 2

primeiras.

Max Z = 120X1 + 150X2

Sujeito a:

2X1 + 4X2 + X3 = 100

5X1 + 3X2 + X4 = 120

Porm, qualquer ponto em R determina

unicamente essas 4 variveis, ou seja, qualquer

par X1 e X2, podemos determinar os valores das

variveis restantes.

Max Z = 120X1 + 150X2

Sujeito a:

2X1 + 4X2 + X3 = 100

5X1 + 3X2 + X4 = 120

Reescrevendo o sistema em forma matricial

temos:

Max Z = 120X1 + 150X2

Sujeito a:

2 4 1 0 X1 = 100

5 3 0 1 X2 = 120

X3

X4

Reescrevendo o sistema em forma matricial

temos:

Max Z = 120X1 + 150X2

Sujeito a:

2 4 1 0 X1 = 100

5 3 0 1 X2 = 120

X3

X4

Os vetores que

aparecem nas colunas

so vetores do R. Uma

base do R constituda

de 2 vetores linearmente

independentes.

Reescrevendo o sistema em forma matricial

temos:

Max Z = 120X1 + 150X2

Sujeito a:

2 4 1 0 X1 = 100

5 3 0 1 X2 = 120

X3

X4

Uma soluo bsica do

sistema pode ser obtida

zerando-se 2 variveis,

reduzindo o sistema a

uma base de 2 vetores.

Os vetores que

aparecem nas colunas

so vetores do R. Uma

base do R constituda

de 2 vetores linearmente

independentes.

Exemplo:

Max Z = 120X1 + 150X2

Sujeito a:

2X1 + 4X2 + X3 = 100

5X1 + 3X2 + X4 = 120

X2

X1

2X1 + 4X2 100

5X1 + 3X2 120

AB

CD

E

F