Fundamentos da Álgebra Linear e Programação Linear

Prévia do material em texto

logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Fundamentos alge´bricos da Programac¸a˜o Linear
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG
Departamento de Engenharia de Produc¸a˜o EE UFMG
carlos@dep.ufmg.br
16 de junho de 2011
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 1
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
1 Fundamentos da a´lgebra linear
Convexidade
Matrizes
Resultados
2 Programac¸a˜o Linear
Definic¸o˜es
Teoremas
Otimalidade
Exemplo
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 2
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Convexidade
Matrizes
Resultados
Combinac¸a˜o Convexa e Conjunto Convexo
Definic¸a˜o: Combinac¸a˜o convexa
Dados p pontos de IRn, (x1, x2, . . . , xp), o ponto x ⊂ IRn e´ uma combinac¸a˜o convexa
desses p pontos se existem os coeficientes
µ1, µ2, . . . , µp (µi ≥ 0, ∀ i = 1, 2, . . . , p) tais que
pX
i=1
µi = 1 e x =
pX
i=1
µixi
Definic¸a˜o: Conjunto Convexo
Um conjunto S ⊂ IRn e´ convexo se e somente se:
∀ x ∈ S
∀ y ∈ S
∀ λ (0 ≤ λ ≤ 1)
9=; =⇒ λx + (1− λ)y ∈ S
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 3
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Convexidade
Matrizes
Resultados
Combinac¸a˜o Convexa e Conjunto Convexo
Definic¸a˜o: Combinac¸a˜o convexa
Dados p pontos de IRn, (x1, x2, . . . , xp), o ponto x ⊂ IRn e´ uma combinac¸a˜o convexa
desses p pontos se existem os coeficientes
µ1, µ2, . . . , µp (µi ≥ 0, ∀ i = 1, 2, . . . , p) tais que
pX
i=1
µi = 1 e x =
pX
i=1
µixi
Definic¸a˜o: Conjunto Convexo
Um conjunto S ⊂ IRn e´ convexo se e somente se:
∀ x ∈ S
∀ y ∈ S
∀ λ (0 ≤ λ ≤ 1)
9=; =⇒ λx + (1− λ)y ∈ S
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 3
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Convexidade
Matrizes
Resultados
Politopo Convexo, Poliedro Convexo e Ponto Extremo
Definic¸a˜o: Politopo Convexo
Um politopo convexo e´ um conjunto convexo na forma
X = {x : Ax = b, x ≥ 0}
Definic¸a˜o: Poliedro Convexo
Um polie´dro convexo e´ um politopo convexo limitado.
Definic¸a˜o: Ponto Extremo
Ponto extremo de um politopo convexo X e´ todo ponto x ∈ X que
na˜o pode ser escrito como combinac¸a˜o convexa de outros pontos
y ∈ X (y 6= x)
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 4
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Convexidade
Matrizes
Resultados
Politopo Convexo, Poliedro Convexo e Ponto Extremo
Definic¸a˜o: Politopo Convexo
Um politopo convexo e´ um conjunto convexo na forma
X = {x : Ax = b, x ≥ 0}
Definic¸a˜o: Poliedro Convexo
Um polie´dro convexo e´ um politopo convexo limitado.
Definic¸a˜o: Ponto Extremo
Ponto extremo de um politopo convexo X e´ todo ponto x ∈ X que
na˜o pode ser escrito como combinac¸a˜o convexa de outros pontos
y ∈ X (y 6= x)
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 4
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Convexidade
Matrizes
Resultados
Politopo Convexo, Poliedro Convexo e Ponto Extremo
Definic¸a˜o: Politopo Convexo
Um politopo convexo e´ um conjunto convexo na forma
X = {x : Ax = b, x ≥ 0}
Definic¸a˜o: Poliedro Convexo
Um polie´dro convexo e´ um politopo convexo limitado.
Definic¸a˜o: Ponto Extremo
Ponto extremo de um politopo convexo X e´ todo ponto x ∈ X que
na˜o pode ser escrito como combinac¸a˜o convexa de outros pontos
y ∈ X (y 6= x)
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 4
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Convexidade
Matrizes
Resultados
Matriz, Matriz Quadrada e Submatriz
Definic¸a˜o: Matriz
Uma matriz e´ um arranjo retangular de nu´meros (elementos). O
termo matriz aqui refere a` matriz de duas dimenso˜es (m linhas e n
colunas).
Definic¸a˜o: Matriz Quadrada
Uma matriz quadrada e´ uma matriz que o nu´mero de linhas e´ igual
ao nu´mero de colunas. A ordem de uma matriz quadrada e´ igual
ao nu´mero de linhas (ou nu´mero de colunas).
Definic¸a˜o: Submatriz
Ao retirar um conjunto de linhas e/ou colunas de uma matriz,
obte´m-se uma submatriz.
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 5
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Convexidade
Matrizes
Resultados
Matriz, Matriz Quadrada e Submatriz
Definic¸a˜o: Matriz
Uma matriz e´ um arranjo retangular de nu´meros (elementos). O
termo matriz aqui refere a` matriz de duas dimenso˜es (m linhas e n
colunas).
Definic¸a˜o: Matriz Quadrada
Uma matriz quadrada e´ uma matriz que o nu´mero de linhas e´ igual
ao nu´mero de colunas. A ordem de uma matriz quadrada e´ igual
ao nu´mero de linhas (ou nu´mero de colunas).
Definic¸a˜o: Submatriz
Ao retirar um conjunto de linhas e/ou colunas de uma matriz,
obte´m-se uma submatriz.
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 5
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Convexidade
Matrizes
Resultados
Matriz, Matriz Quadrada e Submatriz
Definic¸a˜o: Matriz
Uma matriz e´ um arranjo retangular de nu´meros (elementos). O
termo matriz aqui refere a` matriz de duas dimenso˜es (m linhas e n
colunas).
Definic¸a˜o: Matriz Quadrada
Uma matriz quadrada e´ uma matriz que o nu´mero de linhas e´ igual
ao nu´mero de colunas. A ordem de uma matriz quadrada e´ igual
ao nu´mero de linhas (ou nu´mero de colunas).
Definic¸a˜o: Submatriz
Ao retirar um conjunto de linhas e/ou colunas de uma matriz,
obte´m-se uma submatriz.
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 5
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Convexidade
Matrizes
Resultados
Matrizes Quadrada Regular, Identidade e Inversa
Definic¸a˜o: Matriz Quadrada Regular
matriz regular e´ aquela que nenhuma linha ou coluna pode ser
escrita como combinac¸a˜o linear de outras linhas ou colunas.
Definic¸a˜o: Matriz Identidade
Matriz identidade e´ uma matriz quadrada I onde os elementos da
diagonal principal sa˜o iguais a unidade e os demais elementos sa˜o
nulos.
Definic¸a˜o: Matriz Inversa
A matriz inversa da matriz A e´ a matriz A−1 tal que
A× A−1 = A−1 × A = I
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 6
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Convexidade
Matrizes
Resultados
Matrizes Quadrada Regular, Identidade e Inversa
Definic¸a˜o: Matriz Quadrada Regular
matriz regular e´ aquela que nenhuma linha ou coluna pode ser
escrita como combinac¸a˜o linear de outras linhas ou colunas.
Definic¸a˜o: Matriz Identidade
Matriz identidade e´ uma matriz quadrada I onde os elementos da
diagonal principal sa˜o iguais a unidade e os demais elementos sa˜o
nulos.
Definic¸a˜o: Matriz Inversa
A matriz inversa da matriz A e´ a matriz A−1 tal que
A× A−1 = A−1 × A = I
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 6
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Convexidade
Matrizes
Resultados
Matrizes Quadrada Regular, Identidade e Inversa
Definic¸a˜o: Matriz Quadrada Regular
matriz regular e´ aquela que nenhuma linha ou coluna pode ser
escrita como combinac¸a˜o linear de outras linhas ou colunas.
Definic¸a˜o: Matriz Identidade
Matriz identidade e´ uma matriz quadrada I onde os elementos da
diagonal principal sa˜o iguais a unidade e os demais elementos sa˜o
nulos.
Definic¸a˜o: Matriz Inversa
A matriz inversa da matriz A e´ a matrizA−1 tal que
A× A−1 = A−1 × A = I
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 6
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Convexidade
Matrizes
Resultados
Posto e Base de uma matriz
Definic¸a˜o: Posto de uma matriz
O posto de uma matriz e´ a ordem da sua maior submatriz
quadrada regular.
Definic¸a˜o: Base
Uma base da matriz Am×n (com posto(A) = m) e´ toda submatriz
Bm de A quadrada regular.
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 7
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Convexidade
Matrizes
Resultados
Posto e Base de uma matriz
Definic¸a˜o: Posto de uma matriz
O posto de uma matriz e´ a ordem da sua maior submatriz
quadrada regular.
Definic¸a˜o: Base
Uma base da matriz Am×n (com posto(A) = m) e´ toda submatriz
Bm de A quadrada regular.
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 7
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Convexidade
Matrizes
Resultados
Consequ¨eˆncias
Uma matriz regular possui determinante diferente de zero.
Uma matriz possui inversa se, e somente se, ela for quadrada
regular.
A matriz inversa A−1 pode ser obtida atrave´s de operac¸o˜es de
linhas que transformam [A|I ] em [I |A−1].
A matriz inversa da matriz identidade e´ a pro´pria matriz
identidade, ou seja, I−1 = I .
A matriz identidade e´ quadrada regular, portanto possui
inversa, ela pode ser uma base.
A matriz identidade de ordem m e´ uma base canoˆnica para o
espac¸o de dimensa˜o m (geometria anal´ıtica).
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 8
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Convexidade
Matrizes
Resultados
Consequ¨eˆncias
Uma matriz regular possui determinante diferente de zero.
Uma matriz possui inversa se, e somente se, ela for quadrada
regular.
A matriz inversa A−1 pode ser obtida atrave´s de operac¸o˜es de
linhas que transformam [A|I ] em [I |A−1].
A matriz inversa da matriz identidade e´ a pro´pria matriz
identidade, ou seja, I−1 = I .
A matriz identidade e´ quadrada regular, portanto possui
inversa, ela pode ser uma base.
A matriz identidade de ordem m e´ uma base canoˆnica para o
espac¸o de dimensa˜o m (geometria anal´ıtica).
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 8
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Convexidade
Matrizes
Resultados
Consequ¨eˆncias
Uma matriz regular possui determinante diferente de zero.
Uma matriz possui inversa se, e somente se, ela for quadrada
regular.
A matriz inversa A−1 pode ser obtida atrave´s de operac¸o˜es de
linhas que transformam [A|I ] em [I |A−1].
A matriz inversa da matriz identidade e´ a pro´pria matriz
identidade, ou seja, I−1 = I .
A matriz identidade e´ quadrada regular, portanto possui
inversa, ela pode ser uma base.
A matriz identidade de ordem m e´ uma base canoˆnica para o
espac¸o de dimensa˜o m (geometria anal´ıtica).
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 8
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Convexidade
Matrizes
Resultados
Consequ¨eˆncias
Uma matriz regular possui determinante diferente de zero.
Uma matriz possui inversa se, e somente se, ela for quadrada
regular.
A matriz inversa A−1 pode ser obtida atrave´s de operac¸o˜es de
linhas que transformam [A|I ] em [I |A−1].
A matriz inversa da matriz identidade e´ a pro´pria matriz
identidade, ou seja, I−1 = I .
A matriz identidade e´ quadrada regular, portanto possui
inversa, ela pode ser uma base.
A matriz identidade de ordem m e´ uma base canoˆnica para o
espac¸o de dimensa˜o m (geometria anal´ıtica).
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 8
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Convexidade
Matrizes
Resultados
Consequ¨eˆncias
Uma matriz regular possui determinante diferente de zero.
Uma matriz possui inversa se, e somente se, ela for quadrada
regular.
A matriz inversa A−1 pode ser obtida atrave´s de operac¸o˜es de
linhas que transformam [A|I ] em [I |A−1].
A matriz inversa da matriz identidade e´ a pro´pria matriz
identidade, ou seja, I−1 = I .
A matriz identidade e´ quadrada regular, portanto possui
inversa, ela pode ser uma base.
A matriz identidade de ordem m e´ uma base canoˆnica para o
espac¸o de dimensa˜o m (geometria anal´ıtica).
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 8
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Convexidade
Matrizes
Resultados
Consequ¨eˆncias
Uma matriz regular possui determinante diferente de zero.
Uma matriz possui inversa se, e somente se, ela for quadrada
regular.
A matriz inversa A−1 pode ser obtida atrave´s de operac¸o˜es de
linhas que transformam [A|I ] em [I |A−1].
A matriz inversa da matriz identidade e´ a pro´pria matriz
identidade, ou seja, I−1 = I .
A matriz identidade e´ quadrada regular, portanto possui
inversa, ela pode ser uma base.
A matriz identidade de ordem m e´ uma base canoˆnica para o
espac¸o de dimensa˜o m (geometria anal´ıtica).
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 8
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Definic¸o˜es
Teoremas
Otimalidade
Exemplo
Programa Linear
Definic¸a˜o: Programa Linear
Um programa linear (PL) e´ todo problema escrito sob a forma:
maximizar z = cx
sujeito a Ax = b
x ≥ 0
Permutando as colunas da matriz A pode-se obter A = [B,N]
onde B e´ uma base.
Pode-se escrever tambe´m c = [cB , cN ] e x =
[
xB
xN
]
.
Toda soluc¸a˜o de (P) verifica BxB + NxN = b.
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 9
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Definic¸o˜es
Teoremas
Otimalidade
Exemplo
Programa Linear
Definic¸a˜o: Programa Linear
Um programa linear (PL) e´ todo problema escrito sob a forma:
maximizar z = cx
sujeito a Ax = b
x ≥ 0
Permutando as colunas da matriz A pode-se obter A = [B,N]
onde B e´ uma base.
Pode-se escrever tambe´m c = [cB , cN ] e x =
[
xB
xN
]
.
Toda soluc¸a˜o de (P) verifica BxB + NxN = b.
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 9
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Definic¸o˜es
Teoremas
Otimalidade
Exemplo
Programa Linear
Definic¸a˜o: Programa Linear
Um programa linear (PL) e´ todo problema escrito sob a forma:
maximizar z = cx
sujeito a Ax = b
x ≥ 0
Permutando as colunas da matriz A pode-se obter A = [B,N]
onde B e´ uma base.
Pode-se escrever tambe´m c = [cB , cN ] e x =
[
xB
xN
]
.
Toda soluc¸a˜o de (P) verifica BxB + NxN = b.
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 9
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Definic¸o˜es
Teoremas
Otimalidade
Exemplo
Programa Linear
Definic¸a˜o: Programa Linear
Um programa linear (PL) e´ todo problema escrito sob a forma:
maximizar z = cx
sujeito a Ax = b
x ≥ 0
Permutando as colunas da matriz A pode-se obter A = [B,N]
onde B e´ uma base.
Pode-se escrever tambe´m c = [cB , cN ] e x =
[
xB
xN
]
.
Toda soluc¸a˜o de (P) verifica BxB + NxN = b.
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 9
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Definic¸o˜es
Teoremas
Otimalidade
Exemplo
Soluc¸a˜o Ba´sica e Soluc¸a˜o Ba´sica Via´vel
Definic¸a˜o: Soluc¸a˜o Ba´sicaA soluc¸a˜o ba´sica associada a` base B e´ uma soluc¸a˜o particular
obtida fazendo xN = 0. O valor de xB pode ser enta˜o obtida
resolvendo o sistema (resoluc¸a˜o de Cramer):
BxB = b : xB = B
−1b
Definic¸a˜o: Soluc¸a˜o Ba´sica Via´vel
Uma soluc¸a˜o ba´sica e´ dita via´vel (realiza´vel) se x ≥ 0 (ou
B−1b ≥ 0)
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 10
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Definic¸o˜es
Teoremas
Otimalidade
Exemplo
Soluc¸a˜o Ba´sica e Soluc¸a˜o Ba´sica Via´vel
Definic¸a˜o: Soluc¸a˜o Ba´sica
A soluc¸a˜o ba´sica associada a` base B e´ uma soluc¸a˜o particular
obtida fazendo xN = 0. O valor de xB pode ser enta˜o obtida
resolvendo o sistema (resoluc¸a˜o de Cramer):
BxB = b : xB = B
−1b
Definic¸a˜o: Soluc¸a˜o Ba´sica Via´vel
Uma soluc¸a˜o ba´sica e´ dita via´vel (realiza´vel) se x ≥ 0 (ou
B−1b ≥ 0)
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 10
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Definic¸o˜es
Teoremas
Otimalidade
Exemplo
Propriedades dos pontos extremos
Teorema (a ser demonstrado)
O conjunto de pontos extremos de um politopo
X = {x ∈ IRn : Ax = b; x ≥ 0} corresponde ao conjunto de
soluc¸o˜es ba´sicas via´veis.
Colora´rio (a ser demonstrado)
O conjunto (politopo) convexo X = {X ∈ IRn : Ax = b; x ≥ 0}
possui um nu´mero finito v(x) de pontos extremos e v(x) ≤ Cmn ,
onde m e´ a dimensa˜o do vetor b.
Colora´rio (A ser demonstrado)
Todos os pontos de um polie´dro convexo X ⊂ IRn e´ combinac¸a˜o
convexa dos pontos extremos de X .
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 11
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Definic¸o˜es
Teoremas
Otimalidade
Exemplo
Propriedades dos pontos extremos
Teorema (a ser demonstrado)
O conjunto de pontos extremos de um politopo
X = {x ∈ IRn : Ax = b; x ≥ 0} corresponde ao conjunto de
soluc¸o˜es ba´sicas via´veis.
Colora´rio (a ser demonstrado)
O conjunto (politopo) convexo X = {X ∈ IRn : Ax = b; x ≥ 0}
possui um nu´mero finito v(x) de pontos extremos e v(x) ≤ Cmn ,
onde m e´ a dimensa˜o do vetor b.
Colora´rio (A ser demonstrado)
Todos os pontos de um polie´dro convexo X ⊂ IRn e´ combinac¸a˜o
convexa dos pontos extremos de X .
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 11
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Definic¸o˜es
Teoremas
Otimalidade
Exemplo
Propriedades dos pontos extremos
Teorema (a ser demonstrado)
O conjunto de pontos extremos de um politopo
X = {x ∈ IRn : Ax = b; x ≥ 0} corresponde ao conjunto de
soluc¸o˜es ba´sicas via´veis.
Colora´rio (a ser demonstrado)
O conjunto (politopo) convexo X = {X ∈ IRn : Ax = b; x ≥ 0}
possui um nu´mero finito v(x) de pontos extremos e v(x) ≤ Cmn ,
onde m e´ a dimensa˜o do vetor b.
Colora´rio (A ser demonstrado)
Todos os pontos de um polie´dro convexo X ⊂ IRn e´ combinac¸a˜o
convexa dos pontos extremos de X .
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 11
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Definic¸o˜es
Teoremas
Otimalidade
Exemplo
Condic¸o˜es de otimalidade
Teorema (a ser demonstrado)
O ponto o´timo se encontra em ao menos um ponto extremo do
politopo X = {X ∈ IRn : Ax = b; x ≥ 0}. Se ele se encontra em
va´rios pontos extremos, ele tambe´m se encontra em todos os
pontos formados pelas combinac¸o˜es convexas destes pontos
extremos.
Teorema
Condic¸o˜es necessa´ria e suficiente para a otimalidade de uma
soluc¸a˜o ba´sica:
c¯N = cBB
−1N − cN ≥ 0
onde c¯N e´ o vetor de coeficitentes das varia´veis na˜o ba´sicas na
func¸a˜o objetivo.
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 12
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Definic¸o˜es
Teoremas
Otimalidade
Exemplo
Condic¸o˜es de otimalidade
Teorema (a ser demonstrado)
O ponto o´timo se encontra em ao menos um ponto extremo do
politopo X = {X ∈ IRn : Ax = b; x ≥ 0}. Se ele se encontra em
va´rios pontos extremos, ele tambe´m se encontra em todos os
pontos formados pelas combinac¸o˜es convexas destes pontos
extremos.
Teorema
Condic¸o˜es necessa´ria e suficiente para a otimalidade de uma
soluc¸a˜o ba´sica:
c¯N = cBB
−1N − cN ≥ 0
onde c¯N e´ o vetor de coeficitentes das varia´veis na˜o ba´sicas na
func¸a˜o objetivo.
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 12
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Definic¸o˜es
Teoremas
Otimalidade
Exemplo
Otimalidade e Soluc¸a˜o Ba´sica
Teorema (a ser demonstrado)
Se um programa linear possui uma soluc¸a˜o o´tima, enta˜o ao menos
uma soluc¸a˜o ba´sica e´ o´tima.
Colora´rio
Seja IN o conjunto de indices das varia´veis na˜o ba´sicas. Se, x¯B ≥ 0
e c¯N = cBB
−1N − cN ≥ 0,∀ j ∈ IN , enta˜o o vetor x∗, onde
x∗B = x¯B , i = 1, 2, . . . ,m e x
∗
N = 0, ∀j ∈ IN , sera´ uma soluc¸a˜o
o´tima.
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 13
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Definic¸o˜es
Teoremas
Otimalidade
Exemplo
Otimalidade e Soluc¸a˜o Ba´sica
Teorema (a ser demonstrado)
Se um programa linear possui uma soluc¸a˜o o´tima, enta˜o ao menos
uma soluc¸a˜o ba´sica e´ o´tima.
Colora´rio
Seja IN o conjunto de indices das varia´veis na˜o ba´sicas. Se, x¯B ≥ 0
e c¯N = cBB
−1N − cN ≥ 0,∀ j ∈ IN , enta˜o o vetor x∗, onde
x∗B = x¯B , i = 1, 2, . . . ,m e x
∗
N = 0, ∀j ∈ IN , sera´ uma soluc¸a˜o
o´tima.
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 13
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Definic¸o˜es
Teoremas
Otimalidade
Exemplo
Um exemplo nume´rico
Quadro inicial do simplex
base z x1 x2 x3 x4 x5 LD
z 1 - 3 - 5 0 0 0 0
x3 0 1 0 1 0 0 4
x4 0 0 2 0 1 0 12
x5 0 3 2 0 0 1 18
Quadro final do simplex
base z x1 x2 x3 x4 x5 LD
z 1 0 0 0 3/2 1 36
x3 0 0 0 1 1/3 -1/3 2
x2 0 0 1 0 1/2 0 6
x1 0 1 0 0 -1/3 1/3 2
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 14
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Definic¸o˜es
Teoremas
Otimalidade
Exemplo
Um exemplo nume´rico
Quadro inicial do simplex
base z x1 x2 x3 x4 x5 LD
z 1 - 3 - 5 0 0 0 0
x3 0 1 0 1 0 0 4
x4 0 0 2 0 1 0 12
x5 0 3 2 0 0 1 18
Quadro final do simplex
base z x1 x2 x3 x4 x5 LD
z 1 0 0 0 3/2 1 36
x3 0 0 0 1 1/3 -1/3 2
x2 0 0 1 0 1/2 0 6
x1 0 1 0 0 -1/3 1/3 2
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 14
logo
Fundamentos da a´lgebra linear
Programac¸a˜o Linear
Definic¸o˜es
Teoremas
Otimalidade
Exemplo
Um exemplo nume´rico
Quadro inicial do simplex
base z x1 x2 x3 x4 x5 LD
z 1 - 3 - 5 0 0 0 0
x3 0 1 0 1 0 0 4
x4 0 0 2 0 1 0 12
x5 0 3 2 0 0 1 18
Quadro final do simplex
base z x1 x2 x3 x4 x5 LD
z 1 0 0 0 3/2 1 36
x3 0 0 0 1 1/3 -1/3 2
x2 0 0 1 0 1/2 0 6
x1 0 1 0 0 -1/3 1/3 2
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG (DEP EE UFMG)Fundamentos alge´bricos da Programac¸a˜o Linear 14
	Fundamentos da álgebra linear
	Convexidade
	Matrizes
	Resultados
	Programação Linear
	Definições
	Teoremas
	Otimalidade
	Exemplo