Relaciones primal-dual

Como el problema dual es de programación lineal, también tiene soluciones en los vértices. Aún más, empleando la forma de igualdades del problema, estas soluciones se pueden expresar como soluciones básicas. Puesto que las restricciones funcionales tiene la forma ≥, la forma de igualdades se obtiene al restar el superávit (en lugar de agregar la holgura) del lado izquierdo de cada restricción j (j= 1,2,....,n)^1. Este superávit es:

Así, (zj-cj) asume el papel de variable de superávit para la restricción j (o su variable de holgura si la restricción se multiplica por -1). Por tanto, cada solución en un vértice (y1, y2,...., ym) conduce a una solución básica (y1, y2, ....., ym, z1 - c1, z2 - c2, ....., zn - cn) al usar esta expresión para (zj - cj). Puesto que la forma de igualdades tiene n restricciones funcionales y (n+m) variables, cada solución básica tiene n variables básicas y m variables no básicas. (Nótese que los papeles de m y n se han invertido, como lo indica la tabla 6.3, porque las restricciones duales corresponden a las variables primales y las variables duales a las restricciones primales.).