Programação linear

Modelo e formas

$$\max c^Tx,\quad Ax\le b,\quad x\ge0.$$

Slack acrescenta folgas para igualdades. Forma standard separa restrições e não negatividade. Manter equivalência em cada conversão.

Simplex e viabilidade

• Em cada pivô, entra a variável com custo reduzido que melhora o objetivo e sai a restrição que primeiro limita essa entrada, escolhida pela menor razão válida; depois substitui a variável base em todas as equações.
• Se a variável que melhora o objetivo não tem limite em nenhuma restrição, o problema é ilimitado.
• Uma base inicial com folga negativa exige a fase I para procurar uma base admissível; por si só, não prova que o problema é inviável.
• Região ilimitada pode ter ótimo finito.
• Degenerescência pode ciclar; regra de Bland evita.

Dual como certificado

$$\min b^Ty,\quad A^Ty\ge c,\quad y\ge0.$$

Admissíveis primal e dual com objetivos iguais certificam ótimo. Folgas complementares ligam variáveis positivas a restrições ativas.

Modelação e pivôs.