Considere o PPL a seguir.
onde
e
.
(1) Tomando
, tal que
e
exista, caracterize
como uma base primal viável e dual viável para o problema (5)-(7).
(2) Se
é uma base primal viável e dual viável o que podemos afirmar sobre
?
(1) Tomando
(2) Se
Passo 1
O enunciado apresenta o problema de programação linear (PPL)
com
, onde
é invertível. Queremos usar conceitos de teoria de bases em PPL para (1) caracterizar quando
é uma base primal viável e uma base dual viável e (2) entender o que isso implica sobre
.
Passo 2
Uma base
é primal viável se a solução básica associada
satisfaz as restrições
. Logo, a condição de primal viabilidade é
Passo 3
Para formular a condição de dual viabilidade, escrevemos o problema dual. O vetor de preços dual é
Esse
deve satisfazer as desigualdades do dual associadas às variáveis não-básicas
, isto é
ou, em forma matricial,
Passo 4
Portanto, resumindo o item (1):
– é primal viável se
– é dual viável se
–
–
Passo 5
Para o item (2), quando uma base
é simultaneamente primal viável e dual viável, a solução básica associada é ótima por garantir que tanto primal quanto dual são factíveis e satisfazem a condição de complementaridade. Assim, podemos afirmar que
é uma base ótima e seu BFS resolve o PPL de forma ótima.
Resposta
(1)
– Base primal viável:
– Base dual viável:
– Base primal viável:
– Base dual viável:
(2) Se
é primal e dual viável, então
é uma base ótima e a solução básica
é ótima.