ProgramaçãoProgramação MatemáticaMatemática

Maristela SantosInstituto de Ciências Matemáticas e de Computação

Universidade de São Paulo

Forma geral de um PLg

• Em vários problemas que formulamos, obtivemos:– Um objetivo de otimização (maximizar ou

minimizar);minimizar);– Restrições de igualdade = ;

R t i õ d d i ld d d ti ≥– Restrições de desigualdade do tipo ≥ ;– Restrições de desigualdade do tipo ≤ .

Forma Padrão - Definição ç

Características da forma padrão:Características da forma padrão:

Problema de minimização

Todas as restrições são de igualdade

Todas as variáveis são não-negativasTodas as variáveis são não negativas

Considerar b ≥ 0.

Forma Padrão (matricial)( )

Matriz mXn chamada matriz dos coeficientes (matriz tecnológica)

Vetor de Custos

Vetor das Variáveis

Vetor dos termos Independentes ou de recursos

Solução Factível - Definiçãoç ç

• Definição 1: Uma solução (x1,x2,...xn) é factívelse atende a todas as restrições do problema(Ax=b) e as condições de não-negatividade(x≥0).

• Definição 2: O conjunto S={x tal que Ax=b, x≥0}Definição 2: O conjunto S {x tal que Ax b, x≥0}é denominado de conjunto de soluções factíveis(também chamado de região factível).(também chamado de região factível).

Solução Factível - exemploç p

xT = (1, 0, 2) é factível. f(1,0,2)=10.( ) ( )

xT = (0.25, 0.5, 1.75) é factível ? f ?

Solução Ótima - Definiçãoç ç

D fi i ã 3 U l ã f tí l f• Definição 3: Uma solução factível que fornece omenor valor à função objetivo f é chamadasolução ótima denotada por: (x* x* x* )solução ótima, denotada por: (x 1,x 2,...x n).

ou seja:

(x*1,x*2,...x*n) S é ótima se,∈

f(x*1,x*2,...x*n)≤ f(x1,x2,...xn) ∀ (x1,x2,...xn) S ,∈

Transformação para a forma d ãpadrão

• Problemas de maximizaçãoMax c1x1 + c

2x2 + ... + cn xn = Min -c1x1 - c2x2 - ... - cnxn2

Pois

Transformação para a forma d ãpadrão

R t i ã d d i ld d• Restrição de desigualdade:a11x1 + a12x2 + ... + a1n xn ≤ b1a11x1 a12x2 ... a1n xn ≤ b1

Variável de folga (xk)

xk= b1- a11x1 + a12x2 + ... + a1n xn ≥0

Restrição na forma de igualdade:Restrição na forma de igualdade:

a11x1 + a12x2 + ... + a1n xn + xk = b1

Transformação para a forma d ãpadrão

R t i ã d d i ld d• Restrição de desigualdade:a11x1 + a12x2 + ... + a1n xn ≥ b1a11x1 a12x2 ... a1n xn ≥ b1

Variável de folga (xk)

xk= a11x1 + a12x2 + ... + a1n xn -b1 ≥0

Restrição na forma de igualdade:

a11x1 + a12x2 + ... + a1n xn - xk = b1

Transformação para a forma d ãpadrão

V iá i li• Variáveis livresxi irrestrita.i

Resolução Gráficaç

• Resolver um PL consiste em determinar uma solução ótima.ç

• Resolução gráfica: Problemas com duas variáveisvariáveis.

• Visualização.

Resolução Gráfica - Exemploç p

Solução Gráfica - Região f tí lfactível

Solução Gráfica – Região f tí lfactível

Resolução Gráfica - Exemploç p

⎤⎡1xxx*** = = = ⎥⎦

⎤⎢⎣

⎡31

Resolução Gráfica – Conceitos básicos Região FactívelRegião Factível

• Considere uma reta qualquer:a1x1 + a2x2 = b1 1 2 2

• Afirmação: O vetor a=(a1 a2)T é perpendicular à retaperpendicular à reta.

X=X1+δa, δ>0

a

Y=X2- X1

X1

X2

a1X1+ a2X2=b

X

Resolução Gráfica – Conceitos básicosRegião FactívelRegião Factível

Prova:Com a notação matricial da reta: aTx=b, onde aT=(a1, a2) e xT=(x1, x2). Considerando x1 e x2 dois pontos da reta, isto é, aTx1 b aTx2 b e y x2 x1aTx1 =b aTx2 =b, e y=x2-x1. Então: aTy = aT(x2-x1) = aTx1 - aTx2 =b - b = 0.

Em geral, quando o espaço é o Rn, a equação aTx=b define um conjunto chamado hiperplano e o vetor a é perpendicular ao hiperplano.

Resolução Gráfica – Conceitos básicosRegião factívelRegião factível

Afirmação: O vetor a aponta para o lado do plano cujos pontos satisfazem: aTx>b.

Prova:Os pontos do lado que aponta o vetor a são dados por:Os pontos do lado que aponta o vetor a são dados por: x=x1+δa, δ>0Portanto, aTx = aT(x1+δa) = aTx1 + δ aTa = b +δ||a||2 > b, pois δ>0 e ||a||2 = >0 (considerando a≠0.).

Resolução Gráfica – Conceitos básicos Região FactívelRegião Factível

Afirmação: O vetor a aponta para o lado do plano cujos pontos satisfazem: aTx>b.

Prova:Os pontos do lado que aponta o vetor a são dados por:Os pontos do lado que aponta o vetor a são dados por: x=x1+δa, δ>0Portanto, aTx = aT(x1+δa) = aTx1 + δ aTa = b +δ||a||2 > b, pois δ>0 e ||a||2 = >0 (considerando a≠0.).

Pode-se utilizar deste resultado para desenhar a região factível S={x tal que Ax<=b, x≥0}.factível S {x tal que Ax b, x≥0}.

Resolução Gráfica - Exemploç p

A solução ótima x* é chamada de ponto extremo ou vértice...

Vértices sãoVértices são determinados pela intersecção de pelo menos duas retasmenos duas retas (plano).

Pontos extremos

• Se um problema de otimização linear tem uma solução ótima, então existe um vértice ótimo.

e para outras funções objetivo ???ç j

minimização

Região factível ilimitadag

Região factível ilimitada e solução ótima única (Minimização)

Região factível ilimitada e não existe solução ótima

13 mar 2009 . 17:48minimização

Múltiplos ótimosp

Múltiplas soluções ótimas

(max)))

Região factível ilimitadae infinitas soluções ótimas(conjunto ilimitado de soluções

13 mar 2009 . 17:48

( j çÓtimas).

Região infactívelg

Solução degeneradaç g

Exemplo: sol. degeneradap g

13 mar 2009 . 17:48

Método simplex (e met. de t i t i )pontos interiores)

Exercícios1) Considere o seguinte problema:Minimizar f(x1, x2) = -x1 – x2Sujeito a: -x1 + x2 ≤ 22x1 – x2 ≤ 6

0 0x1 ≥ 0, x2 ≥ 0

a) Resolva o problema graficamente (isto é, desenhe a região factível e a(s) solução(ões) ótima(s) )a(s) solução(ões) ótima(s) ).b) A solução x1 = x2 = 0 é um vértice da região factível?Identifique todos os vértices da região factível. c) Desenhe as soluções x1=( )=(1 1) e x2=( )=(5 1)c) Desenhe as soluções x1=( )=(1 1) e x2=( )=(5, 1).Estas soluções são factíveis? Por que?e) Considere agora uma outra função objetivo: Minimizar f(x1, x2) = x1 - x2.Verifique se a solução ótima obtida no item a é tambémVerifique se a solução ótima obtida no item a. é tambémótima considerando esta nova função objetivo. Há múltiplas soluções ótimas? Identifique no gráfico.

Exercícios2. Considere o seguinte problema:Minimizar f(x1, x2) = x1 + x2Sujeito a: -x1 + x2 ≥ 22x1 – x2 ≤ 6

0 0x1 ≥ 0, x2 ≥ 0.

Resolva o problema graficamente.Considere agora: Maximizar f(x x ) = x + x sujeito às mesmas restrições O queConsidere agora: Maximizar f(x1, x2) = x1 + x2 sujeito às mesmas restrições. O que mudou?Construa uma nova função objetivo de modo que o problema tenha: i) um segmento de soluções ótimas; ii) uma semi reta de solução ótimasde soluções ótimas; ii) uma semi-reta de solução ótimas.d) considere o problema do item b) e inclua a terceira restrição X1 + X2 ≤ 1. Resolva o problema resultante

Conceitos básicos

• Consideramos sempre o problema na forma padrão:p

Dimensões:A (m x n)A (m x n)b (m x 1)

Soluções básicasç

• Considere a seguinte região factível no R2

iá i d f lvariáveis de folga

Forma padrãoForma padrão

Exemplop

Alguns pontosg p

Factíveis (Por quê ?) (((construção e nãoconstrução e não--negatividadenegatividade)))

Alguns pontosg p

No interior da região factível (todas as variáveis de folga são positivas)folga são positivas).

Alguns pontosg p

Na fronteira (alguma variável se anula)!Na fronteira (alguma variável se anula)!

Variáveis nulas indicam restrições ativas!Variáveis nulas indicam restrições ativas!Variáveis nulas indicam restrições ativas!Variáveis nulas indicam restrições ativas!Mais de uma variável se anula: vértice (mais de uma Mais de uma variável se anula: vértice (mais de uma restrição ativa)!restrição ativa)!restrição ativa)!restrição ativa)!

Outros pontosp

Infactíveis:Infactíveis:Infactíveis:Infactíveis:

Respeitam o sistema Ax = bRespeitam o sistema Ax = bRespeitam o sistema Ax = bRespeitam o sistema Ax = bmas não respeitam as restrições de nãomas não respeitam as restrições de não--negatividade!negatividade!

Região factível e vércticesg– Teorema 1: A região factível S={x Rn tal que Ax=b, ∈eo e a eg ão act e S { ta que b,

x≥0} é convexa.

Vértices

• Vimos que sempre que existe uma solução ótima, existe um vértice ótimo.

• Também intuímos que uma maneira de achar a solução ótima seria visitar os vértices factíveis sucessivamente

• Como determinar vértices sem o auxílio doComo determinar vértices sem o auxílio do gráfico?

Vértices

• Duas restrições ativas*:duas variáveis nulas!

3 equações 3 incógnitas!!!3 equações, 3 incógnitas!!!* Caso geral: n-m variáveis nulas.

Vértices

• Factíveis:– Ao fixar (n-m) variáveis em zero, a resolução do o a ( ) a á e s e e o, a eso ução do

sistema resulta em valores positivos para as variáveis restantes. (Ex. ponto D)

• Infactíveis– Ao fixar (n-m) variáveis em zero, a resolução do

sistema resulta em ao menos um valor negativopara as variáveis restantes. (Ex. ponto F)

Escrevendo o sistema

Apesar de fixarmos (n-m) variáveis em zero (no exemplo, x3 e x4), continuamos as escrevendo (embora de maneira isolada):

Escrevendo o sistema

E t ã t i i lEm notação matricial

Índices:

18 mar 2009 . 08:41

Referenciando

colunas associadas

ÍndicesÍndices:

Resumindo

• Temos um problema de otimização e o escrevemos na forma padrão.

• Escrevemos o sistema Ax=b na forma:Escrevemos o sistema Ax b na forma:

Resumindo

• Escolhendo (n-m) variáveis para xN e o restante para XB.

• xN=0 (e colunas de B invertível)

• BXB = b é um sistema com o mesmo número de i ó i ( ) S iá i lequações e incógnitas (m). Se as variáveis solução

desse sistema são ≥ 0, vértice factível. Caso contrário, vértice Infactívelvértice Infactível.

Resolvendo o sistema

• E se B não for invertível ?

Sempre escolhemos para B, m variáveis cujas colunas constituem uma matriz invertível.colunas constituem uma matriz invertível.

Supor que posto(A) m (implica m≤n) Se m n o• Supor que posto(A)=m (implica m≤n). Se m=n, o sistema tem solução única (não tem problema), na forma padrão admitimos m<n Ax=b temna forma padrão admitimos m<n. Ax=b tem infinitas soluções.

Partição básica (Matriz bá i )básica)

• Bmxm - matriz básica - formada por m colunas li t i d d t d Alinearmente independentes de A.

• B pode ser escrita como:

Onde B1, B2,..., Bm são os índices das colunas escolhidas da matriz A (índices básicos)

Partição básica (Matriz não-bá i )básica)

• Nmx (n-m) - matriz não-básica - formada pelas n-ml t t d Acolunas restantes de A.

• N pode ser escrita como:

Onde N1, N2,..., Nm são os índices das colunas da matriz A que pertencem a N (índices não-básicos)

Partição básica (partição das variáveis)

• Consequentemente, a partição de A em [B N] i ti ã d iá icria uma partição das variáveis:

variáveis básicasvariáveis básicas

variáveis não básicas

Solução geral do sistemaç g

• A última expressão de xB é conhecida como solução geral do sistema.solução geral do sistema.

Solução básicaç

• Considere uma partição básica A=[B,N]. Uma solução é dita básica quando:

^̂̂

• Se todas as componentes de xB são não-negativas, então temos uma solução básica factível. Caso contrário, temos uma solução básica não-factível.

Voltando ao exemplop

• Ponto D:

Solução básica factível...

Voltando ao exemplop

• Ponto F:

Solução básica não-factível...

Propriedade básica Ip• Considere região factível g

S={x Rn | Ax=b, x ≥0}.∈

Um ponto x S é um vértice de S se e somente f l ã bá i f tí l

∈se x for uma solução básica factível.

Propriedade básica IIp

Se um problema de otimização linear tem uma l ã óti tã i t é ti ótisolução ótima, então existe um vértice ótimo

Método possívelp

• Enumerar todas as soluções básicas (vértices)x1, x2, ... xK1 2 K

• Escolher aquela com melhor função objetivo.j

• Problema:• Problema:K pode ser muito grande!

Simplexp

Idéia:

•Partir de uma solução básica factível•Visitar apenas as soluções básicas factíveis•Visitar apenas as soluções básicas factíveis melhores que ela.

Mét d Si lMétodo Simplex