(1,0) Diferencie solução padrão e solução padrão primário e dê um exemplo de cada caso.
Passo 1
O enunciado pede duas coisas: (a) explicar a diferença entre “solução padrão” e “solução padrão primário” e (b) dar um exemplo de cada uma. Não há outros dados numéricos fornecidos; portanto vou explicar os conceitos em geral e ilustrar com um exemplo concreto que costuma aparecer em provas.
Passo 2
Primeiro vamos fixar um contexto claro (isso é só para definir palavras, não é um exercício extra): considere um problema de programação linear escrito na forma padrão (standard form)
\text{minimizar } c^{T}x \quad\text{sujeito a}\quad A x = b,\quad x \ge 0,
onde A é uma matriz m\times n, b\in\mathbb{R}^m, c\in\mathbb{R}^n e x\in\mathbb{R}^n. Aqui explico o que cada símbolo significa: x é o vetor das variáveis (o que queremos encontrar), A é a matriz das restrições lineares, b é o lado direito das igualdades e x\ge0 significa que cada componente de x é não-negativa.
Passo 3
Definição de “solução padrão” (uso a expressão no sentido usual em LP): uma “solução padrão” é qualquer vetor x\) que satisfaça as condições do problema na forma padrão, ou seja
\[A x = b\quad\text{e}\quad x\ge 0.
Em palavras: é qualquer solução viável (factível) do problema escrito na forma padrão. Não exige nenhuma estrutura extra: pode ter muitos componentes positivos, não há restrição de quantos são não nulos.
Exemplo simples de “solução padrão”: considere as restrições
que é uma forma padrão obtida a partir de desigualdades por adição de folgas s_1,s_2\]. Um exemplo de solução padrão (qualquer solução factível) é
\[x = (x_1,x_2,s_1,s_2) = (0,0,4,2),\]
porque substituindo nas igualdades obtém-se \(0+0+4=4 e 0+2=2, e todas as componentes são não-negativas.]
Passo 4
Agora a definição de “solução padrão primário” — aqui vou interpretar essa expressão como a que é usualmente chamada de “solução básica primária” ou “solução primária básica” (primal basic feasible solution). Essa é uma solução especial obtida escolhendo um conjunto de m variáveis — as variáveis básicas — cujas colunas em A formam uma matriz inversível A_B. Definição técnica: se B é um índice de m colunas de A com A_B invertível, a solução básica associada tem
x_B = A_B^{-1} b,\qquad x_N = 0,
onde x_B são as variáveis básicas (as m escolhidas) e x_N são as não-básicas (as outras n-m) definidas como zero. Essa solução é chamada “primária” porque é a solução básica do problema primal; é factível somente se x_B \ge 0, caso em que é uma solução básica viável (basic feasible solution). Intuitivamente, soluções básicas correspondem aos vértices (extremos) do politopo viável — por isso são centrais no método Simplex.
Vou explicar passo a passo cada peça da fórmula x_B = A_B^{-1} b:
B é o conjunto de índices das variáveis básicas (tem tamanho m).
A_B é a submatriz de A formada pelas colunas com índices em B.
A_B^{-1} é a matriz inversa de A_B (existe porque escolhemos colunas lin. independentes).
x_B é o vetor das componentes de x correspondentes a B.
As demais componentes x_N são colocadas igual a zero.
Passo 5
Exemplo concreto de “solução padrão primário” usando o mesmo sistema do Passo 3. Reescrevendo as equações na ordem das variáveis (x_1,x_2,s_1,s_2), a matriz A e b são
que é a matriz identidade (portanto invertível). Aplicando a fórmula x_B=A_B^{-1}b obtemos x_2=4 e s_2=2. As variáveis não-básicas x_1 e s_1 ficam 0. Logo a solução básica primária é
x=(x_1,x_2,s_1,s_2)=(0,4,0,2).
Verifique: substituindo nas equações dá 0+4+0=4 e 0+2=2, e todas as componentes são não-negativas, logo é uma solução básica viável do primal — isto é uma “solução padrão primário” no sentido explicado.]
Passo 6
Comparação resumida (intuição prática para a prova):
Uma “solução padrão” é qualquer solução factível de A x=b,\;x\ge0. Pode ter muitos componentes não nulos e não precisa obedecer à forma de “básica”.
Uma “solução padrão primário” (solução básica primária) é uma solução factível com a estrutura de solução básica: exatamente m variáveis básicas obtidas pela inversão de uma submatriz A_B e as outras n-m variáveis iguais a zero. Essas soluções correspondem a vértices do conjunto viável e são as candidatas que o Simplex visita.
Resposta
Solução padrão: qualquer x que satisfaça A x=b e x\ge0. Exemplo: (x_1,x_2,s_1,s_2)=(0,0,4,2) para o sistema dado.
Solução padrão primário (solução básica primária): uma solução obtida escolhendo um conjunto B de m colunas de A com A_B invertível e definindo x_B=A_B^{-1}b,\;x_N=0; é factível se x_B\ge0. Exemplo: com B=\{x_2,s_2\} acima temos (x_1,x_2,s_1,s_2)=(0,4,0,2).