Programación lineal y dualidad

Cada fila de A representa una condición, b sus límites y c los valores de las decisiones. Las desigualdades vectoriales se leen componente a componente. En nuestros ejemplos de dos decisiones las llamaremos u, v; reservaremos α, β para multiplicadores del dual.

Objetivo y restricciones deben ser afines en las decisiones; una constante del objetivo puede separarse sin cambiar el plan óptimo. Exigir integridad produce programación entera, otra tarea. Primero comprobamos factibilidad: el primer punto que cumple las condiciones no es necesariamente óptimo.

Los niveles cᵀx=K son rectas paralelas en dos dimensiones e hiperplanos en general. Maximizar los desplaza hacia valores mayores hasta el último contacto posible. En un politopo no vacío, todo punto es combinación convexa de vértices; su objetivo lineal es la misma combinación de sus valores.

Así algún vértice alcanza el máximo.

Puede haber más de un óptimo: si dos vértices tienen el mismo valor máximo, todo el segmento entre ellos también lo tiene. En regiones generales no acotadas revisamos existencia y estructura antes de prometer un vértice óptimo. Símplex recorre bases; punto interior usa otra estrategia. La geometría no exime de comprobar las restricciones.

Si y≥0 y Ax≤b, sumar filas multiplicadas por sus componentes conserva el sentido: yᵀAx≤yᵀb.

La cadena completa cᵀx≤yᵀAx≤bᵀy es válida para cualquier par factible de este tipo.

Tiene un multiplicador por restricción primal. Puede interpretarse como precios de recursos en algunos modelos, pero su función matemática es construir cotas. El signo no negativo evita invertir una desigualdad; la condición sobre columnas permite cubrir el objetivo con esa combinación.

La dualidad débil asegura objetivo primal ≤objetivo dual para todo par factible. Si un plan alcanza una cota dual, ningún primal puede superarlo y ningún dual puede rebajar la cota. Quedan demostrados ambos óptimos sin enumerar todas las decisiones.

Hay que verificar factibilidad de los dos lados y calcular ambos valores con el mismo problema y sus escalas. Una coincidencia de cifras obtenidas con signos o restricciones equivocados no certifica nada. El certificado es la cadena de desigualdades y el punto donde se alcanza.

El teorema de dualidad fuerte lineal afirma que si el primal de la forma fijada es factible y tiene valor óptimo finito, el dual tiene óptimo alcanzado y el mismo valor. Es un teorema de programación lineal; no se deduce solo de dibujar un caso. No exige estricta factibilidad como condición general del resultado lineal.

Por dualidad débil, si el primal es no acotado por arriba, el dual no puede ser factible: cualquier punto dual daría una cota finita contradictoria. La inversa no se usa automáticamente. Si un lado es infactible, el otro puede ser infactible o no acotado; hay que estudiar las condiciones concretas.

Si ambos lados son factibles, todos los sumandos son no negativos. La brecha es cero exactamente cuando cada yᵢ(bᵢ−(Ax)ᵢ)=0 y cada xⱼ((Aᵀy)ⱼ−cⱼ)=0.

Una capacidad con holgura positiva obliga a precio dual cero en un par óptimo. Una decisión primal positiva obliga a igualdad en su condición dual. La inversa de estas frases no siempre vale: una capacidad activa puede tener precio cero. Las igualdades complementarias ayudan a construir candidatos, pero no sustituyen comprobar factibilidad.

Una desigualdad de tipo ≤ necesita multiplicador no negativo para conservar ese sentido en una cota superior. Una igualdad puede multiplicarse por cualquier número real sin perder la igualdad. Si cambiamos de forma el primal, cambian las reglas duales correspondientes; fijamos primero la convención.

Una variable primal libre puede tener cualquier signo. Para eliminar su contribución al construir la cota lineal, sus coeficientes deben coincidir, en vez de usar solo una desigualdad válida para variables no negativas. También puede representarse como diferencia de dos variables no negativas y deducir ambas condiciones.

Explicar la comparación evita memorizar signos fuera de contexto.

Al quitar integridad, el conjunto factible crece. En un máximo, el óptimo continuo da una cota superior del entero; en un mínimo da una cota inferior. Una respuesta fraccionaria no es por sí sola una decisión entera. Las cotas válidas permiten medir la brecha con la mejor decisión encontrada.

Si el valor objetivo entero debe ser un número entero, podemos redondear una cota en la dirección que conserva su validez. Esto no equivale a redondear las variables. La igualdad entre una cota válida y el valor de un plan entero factible certifica optimalidad; si queda brecha no se anuncia una garantía que aún no tenemos.