Math
Simplexe dans le plan
Le domaine réalisable repose sur la table et une plaque est suspendue au-dessus, à la hauteur de l'objectif. L'objectif est linéaire, donc la plaque est plate et inclinée, et le meilleur point est littéralement son coin le plus haut.
Ce qui se passe
Deux variables et quelques contraintes : chacune est un mur sur la table, et ce qui reste à l'intérieur est le domaine réalisable. Au-dessus pend une plaque dont la hauteur en chaque point vaut l'objectif p·x + q·y. Comme il est linéaire, la plaque est un plan incliné et plat - pas de colline au milieu -, et le meilleur point est son coin le plus haut. Tout vient de là : la réponse est toujours en un sommet, et 60 000 sondages à l'intérieur n'en ont jamais battu un. Le simplexe monte cet escalier : de l'origine vers un coin voisin plus haut, un pivot à la fois, et s'arrête quand aucun voisin n'est plus haut. Sa réponse est comparée à une énumération de tous les sommets, qui ignore tout du tableau. Pousse un mur d'une unité et l'optimum croît exactement de son prix dual - sauf si trois murs se rejoignent au coin supérieur, où il n'y a plus de taux unique.
Équations du module
Équations maximiser p·x + q·y sous la contrainte a·x + b·y ≤ c pour chaque ligne, et x ≥ 0, y ≥ 0 la région admissible est l'intersection de demi-plans ; l'objectif est linéaire, donc son graphe au-dessus de la région est un plan incliné donc le maximum est atteint en un SOMMET - un point où deux des droites (les axes comptent) se croisent et où toutes les contraintes restent vérifiées simplexe : partir de l'origine (chaque c ≥ 0, donc elle est admissible), aller vers un sommet voisin qui augmente l'objectif, s'arrêter quand aucun ne le fait la règle de Bland - entrer sur le plus petit indice éligible, sortir sur le plus petit indice de base parmi les rapports à égalité - rend le cyclage impossible le prix fictif d'une ligne est la variable duale : repoussez son c de h et l'optimum augmente de h·y, sauf si le sommet du haut est DÉGÉNÉRÉ sommet dégénéré : plus de deux droites passent par le même point - la dérivée n'y existe pas, donc le prix fictif n'est pas défini
