Math
Símplex en el plano
La región factible descansa sobre la mesa y encima cuelga una placa a la altura del objetivo. El objetivo es lineal, así que la placa es plana e inclinada, y el mejor punto es literalmente su esquina más alta.
Qué ocurre
Dos variables y unas cuantas restricciones: cada una es un muro sobre la mesa, y lo que queda dentro es la región factible. Encima cuelga una placa cuya altura en cada punto es el objetivo p·x + q·y. Como es lineal, la placa es un plano inclinado y llano - no tiene colina en el medio -, y el mejor punto es su esquina más alta. De ahí sale todo: la respuesta siempre está en un vértice, y 60 000 sondeos dentro de la región no superaron ninguno. El símplex sube esa escalera: del origen a una esquina vecina más alta, una pivotada cada vez, y se detiene donde ninguna vecina es más alta. Su respuesta se compara con una enumeración de todos los vértices, que no sabe nada de la tabla. Empuja un muro una unidad y el óptimo crece exactamente su precio sombra - salvo que tres muros se encuentren en la esquina superior, y entonces no hay una única tasa de crecimiento.
Ecuaciones del módulo
Ecuaciones maximizar p·x + q·y sujeto a a·x + b·y ≤ c para cada fila, y x ≥ 0, y ≥ 0 la región factible es la intersección de semiplanos; el objetivo es lineal, así que su gráfica sobre la región es un plano inclinado por tanto el máximo está en un VÉRTICE - un punto donde se cruzan dos de las rectas (los ejes cuentan) y se siguen cumpliendo todas las restricciones símplex: se parte del origen (todo c ≥ 0, así que es factible), se pasa a un vértice vecino que aumente el objetivo, y se para cuando ninguno lo hace la regla de Bland - entra el índice elegible más pequeño, sale el índice básico más pequeño entre las razones empatadas - hace imposibles los ciclos el precio sombra de una fila es la variable dual: si se desplaza su c en h el óptimo crece en h·y, salvo que el vértice superior sea DEGENERADO vértice degenerado: más de dos rectas por el mismo punto - allí la derivada no existe, así que el precio sombra no está definido
