Questão de Algoritmos e Estrutura de Dados — Algoritmos — CESGRANRIO 2012

Considere que um problema de programação linear gerou uma solução gráfica limitada pelos pontos extremos viáveis que coincidem com os vértices de um cubo definido pelos vértices Pi (X1, X2, X3), tais que P1 (0,0,0); P2 (1,0,0); P3 (0,1,0) e P4 (0,0,1); o vértice P5 está no plano X1X2, o P6 no plano X2X3, e o P7 no plano X1X3.Se as iterações do método simplex começarem em P1 e terminarem em P8 (solução ótima), qual dos caminhos é legítimo para o algoritmo simplex?

1. ADe P1 para P8
2. BDe P1 para P4 e de P4 para P8
3. CDe P1 para P2, de P2 para P3 e de P3 para P8
4. DDe P1 para P3, de P3 para P5 e de P5 para P8
5. EDe P1 para P2, de P2 para P1, de P1 para P6 e de P6 para P8