Considere o PPL a seguir.
\begin{aligned} \max & c^{T} x \\\ & A x=b \\\ & x \geq 0 \end{aligned}
onde A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^{m}, c \in \mathbb{R}^{n} e x \in \mathbb{R}^{n}.
(1) Tomando A=\left[\begin{array}{ll}B & N\end{array}\right], tal que B \in \mathbb{R}^{m \times m} e B^{-1} exista, caracterize B como uma base primal viável e dual viável para o problema (5)-(7).
(2) Se B é uma base primal viável e dual viável o que podemos afirmar sobre B ?

Passo 1

O enunciado apresenta o problema de programação linear (PPL)
\begin{aligned} \max\;& c^{T}x\\\ \text{sujeito a}\;& Ax=b,\\\ & x\ge0, \end{aligned}
com A=[B\;N], onde B\in\mathbb{R}^{m\times m} é invertível. Queremos usar conceitos de teoria de bases em PPL para (1) caracterizar quando B é uma base primal viável e uma base dual viável e (2) entender o que isso implica sobre B.

Passo 2

Uma base B é primal viável se a solução básica associada
x_B = B^{-1}b, \qquad x_N = 0
satisfaz as restrições x_B\ge0. Logo, a condição de primal viabilidade é
B^{-1}b \;\ge\; 0.

Passo 3

Para formular a condição de dual viabilidade, escrevemos o problema dual. O vetor de preços dual é
y = c_B^T B^{-1}.
Esse y deve satisfazer as desigualdades do dual associadas às variáveis não-básicas x_N, isto é
c_j - a_j^T y \;\le\; 0 \quad\text{para todo }j\in N,
ou, em forma matricial,
c_N^T - c_B^T B^{-1}N \;\le\; 0.

Passo 4

Portanto, resumindo o item (1):
B é primal viável se \;B^{-1}b\ge0.
B é dual viável se \;c_N^T - c_B^T B^{-1}N \le0.

Passo 5

Para o item (2), quando uma base B é 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 B é uma base ótima e seu BFS resolve o PPL de forma ótima.

Resposta

(1)
– Base primal viável: \;B^{-1}b\ge0.
– Base dual viável: \;c_N^T - c_B^T B^{-1}N \le0.
(2) Se B é primal e dual viável, então B é uma base ótima e a solução básica x=(B^{-1}b,\,0) é ótima.

Exercícios relacionados