Problème de LP avec plus de 2 variables de décision

Question

Considérons un problème de programmation linéaire avec plus de 2 variables de décision. Je suis tombé sur une déclaration selon laquelle - une solution optimale peut être obtenue en créant des sous-problèmes avec au maximum 2 variables de décision (tout en définissant les variables de décision restantes sur$0$) et sélectionner l'optimum parmi tous ces sous-problèmes.

C'est une approche pour résoudre un problème de LP. Mais comment la solution optimale de ces sous-problèmes est-elle la même que l'optimum global du problème d'origine? J'ai du mal à croire que seules deux variables de décision peuvent générer la solution optimale globale.

Answer 1

Ce n'est manifestement pas vrai.

Pour construire un contre-exemple, considérons le cas où aucun des éléments de la région réalisable ne prend $0$ valeurs.

Par exemple $\min x+y+z$ sujet à $x \ge 1, y \ge 1, z \ge 1$.

---

Pour le message lié, notez qu'il est de la forme

$$\min c^Tx$$

sujet à $Ax \ge b, x \ge 0$

où $A$ consiste en $2$Lignes. Nous savons que pour la programmation linéaire, si une solution optimale existe, elle se produit à une solution basique faisable. Puisqu'il y a$4$ variables, $4$ des contraintes doivent être actives sur un BFS, dont au moins $2$ proviennent des contraintes de signe.