Resumo

O método simplex possui complexidade exponencial o que pode sugerir que é um método muito ineficiente. Porém ao resover problemas reais o método se comporta muito bem, e não apresenta esse comportamento exponencial. Há resultados que tentam explicar esse fenômeno que mostram que o conjunto de problemas para os quais o Simplex apresenta comportamento exponencial é muito pequeno, tem medida nula. Um dos fatores mais importantes para entender a performance do Simples são as regras de pivotação que decidem qual variável entra e qual sai da base a cada iteração. Em particular é possível mostrar que para algumas classes importantes de problemas algumas regras de pivotação garantem que o Simplex seja fortemente polinomial.

O objetivo desse projeto é o estudo desses fenômenos, tendo como ponto de partida uma palestra recente de recente de Yijun Ye:

Recent Prograsses on Linear Programming and the Simples Method.