Un problema de programación lineal es un problema en cual debemos hallar el valor máximo o mínimo de una expresión lineal

ax + by + cz + . . .

Ax + By + Cz + . . .≤ N

Ax + By + Cz + . . .≥ N.

El siguiente es un ejemplo de un problema PL:

Determine el valor máximo de

p = 3x - 2y + 4z

sujeta a

4x + 3y - z ≥ 3
x + 2y + z ≤ 4
x ≥ 0, y ≥ 0, z ≥ 0

La función ojectiva es p = 3x - 2y + 4z. Las restricciones son

4x + 3y - z ≥ 3
x + 2y + z ≤ 4
x ≥ 0, y ≥ 0, z ≥ 0.

Para dibujar la región representada por una desigualdad en dos variables:

A. Dibuje la recta que se obtiene por sustituir una igualdad por la desigualdad.

B. Escoja un punto de prueba que no está en la recta ((0,0) es una elección conveniente si la recta no pasa por el origen. Si pasa por el origen, un punto en un eje sería suficiente).

C. Si el punto de prueba satisface la desigualdad, el conjunto de las soluciones es la región entera en el mismo lado de la recta. Si no, el conjunto solución es la región del otro lado de la recta. En cualquier de los dos casos, sombree la región opuesta para dejar claro el conjunto solución.

Para dibujar la desigualdad lineal:

3x - 4y ≤ 12,

3(0) - 4(0) ≤ 12,

La región factible determinada por un conjunto de desigualdades lineales es el conjunto de puntos que satisfacen a la vez todas las desigualdades.

Para dibujar la región factible determinada por un conjunto de desigualdades lineales: Dibuje las regiones determinadas por cada desigualdad recordando en cada caso sombrear la parte del plano que no quiere. La región que permanece sin sombreado es la región factible.

La región factible determinada por el siguiente conjunto de desigualdades es la región no sombreada mostrada más abajo (incluyendo su frontera).

3x - 4y ≤ 12,
x + 2y ≥ 4
x ≥ 1
y ≥ 0.

El método gráfico para solucionar a un problema de programación lineal es el siguiente:

1. Dibuje la región factible de los restricciones.
2. Calcule las coordenadas de los puntos extremos (puntos de esquina).
3. Sustituya las coordenadas de los puntos de esquina en la función objetiva para ver cual da el valor óptimo. Este punto da la solución del problema de programación lineal.
4. Si la región factible no es acotada, este método puede ser erróneo: soluciones óptimas siempre existen cuando la región factible está acotada, pero pueden no existir en el caso no acotado.
Si la región factible no es acotada, estamos minimizando una función ojectiva cuyas coeficientes son no negativos, entonces existe una solución dado por este método.

Para determinar si existe una solución en el caso general no acotado:

1. Acote la región por añadir una recta horizontal por encima del punto de esquina más arriba, y una recta vertical a la derecha del punto de esquina que esté mas hacia la derecha.
2. Calcule las coordenadas de los puntos nuevos de esquina que se obtiene.
3. Halle el punto de esquina donde ocurre el valor óptimo de la función ojectiva.
4. Si el valor óptimo se ocurre a un punto de esquina de la región original (no acotada) entonces existe la solución óptima a aquel punto. Si ocurra el valor óptimo solo a un punto nuevo de esquina, entonces el problema de programación lineal no tiene soluciones.

Si quieres ver una utilidad que automatiza el proceso entero, prueba el ¡Hacen todo automáticamente, incluyendo dibujar la región factible!

Minimizar C = 3x + 4y sujeta a

3x - 4y ≤ 12,
x + 2y ≥ 4
x ≥ 1,   y ≥ 0.

La región factible para este conjunto de restricciones fue mostrada más arriba. Aquí está otra vez con los puntos de esquinas indicados.

Aunque no es acotada la región factible, estamos minimizando C = 3x + 4y, cuyas coeficientes son no negativos. Entonces existe una solución obtenida por el método más arriba a la izquierda.

La siguiente tabla muestra el valor de C a cada punto de esquina:

Punto	C = 3x + 4y
(1, 1.5)	3(1)+4(1.5) = 9	mínimo
(4, 0)	3(4)+4(0) = 12

Un problema de maximización estándar con n incógnitas es un problema de programación lineal en lo que necesitamos maximizar (no minimizar) la función ojectiva, sujeta a restricciones de la forma

x ≥ 0, y ≥ 0, z ≥ 0, . . . ,

Ax + By + Cz + . . . ≤ N,

Observe que la desigualdad aquí debe ser una "≤," y no "=" o "≥."

La siguiente es una problema de maximización estándar:

Maximizar P = 2x - 3y + z sujeta a

4x - 3y + z ≤ 3
x + y + z ≤ 10
x ≥ 0, y ≥ 0, z ≥ 0.

La siguiente no es una problema de maximización estándar::

Maximizar P = 2x - 3y + z sujeta a

4x - 3y + z ≥ 3
x + y + z ≤ 10
x ≥ 0, y ≥ 0, z ≥ 0.

Para solucionar un problema de maximización estándar por el método simplex, seguimos los siguientes pasos:

Paso 1. Convierta las desigualdades en igualdades por introducir variables de holgura por cada una de las restricciones, para convertirlas en igualdades, y escriba las restricciones en forma estándar como muestra enfrente en el ejemplo.

Paso 2. Escriba la tabla inicial simplex.

Paso 3. Escoja la columna pivote: Encuentre el número negativo mayor (en valor absoluto) en el último renglón (excluyendo la entrada más hacia la derecha). Su columna es la columna pivote. (Si hay más que una candidata, escoja alguna.) Si no hay números negativo en último renglón son cero (excluyendo la entrada más hacia la derecha), entonces está terminado: la corriente solución básica maximiza la función ojectiva (la solución básica está descrito más abajo).

Paso 4. Escoja el pivote en la columna pivote: El pivote debe ser una entrada positiva. Para cada entrada positiva b en la columna pivote, calcule la razón a/b, donde a es la entrada de la última columna (valores solución) del renglón. Entre estas razones de prueba, escoja la más pequeña. La entrada correspondiente b es el pivote.

Paso 5. Use el pivote para despejar la columna en la manera normal descrito en el tutorial del método Gauss Jordan, y sustituya la etiqueta de la columna pivote por la etiqueta del reglón pivote. La etiqueta original es la variable saliendo y la nueva etiqueta es la variable entrando.

Paso 6. Vaya a Paso 3.

Tutorial sobre el método simplex

Herramienta Gauss-Jordan y pivotador

Herramienta Excel Gauss-Jordan y pivotador

Herramienta método simplex

Para obtener la solución básica que corresponde a alguna tabla del método simplex, iguale a cero a todas las variables que no aparecen como etiquetas de renglones (estas son las variables inactivas).

El valor de una variable que no aparece como una etiqueta de renglón (es decir, una variable activa) es la razón a/b, en la que a es la entrada de la última columna del renglón y a es la entrada de aquel renglón cuya columna tiene la misma etiqueta.

En la siguiente tabla

x	y	z	s	t	u	p	Ans
-1	0	0	1	0	0	0	4
1	0	3	0	0	8	0	12
4	0	0	0	3	0	0	2
-5	2	0	0	0	6	0	4
6	0	0	0	0	0	5	-25

x = 0, y = 2, z = 4, s = 4, t = 2/3, u = 0, p = -5,

Para solucionar un problema PL con restricciones de la forma Ax + By + . . .≥ N con N positiva, sustraiga una variable de excedente del lado izquierdo en vez de añadir una variable de holgura. La solución básica que corresponde a la primera tabla no estará factible porque algunas de las variables activas serán negativas, entonces las reglas para pivotar son diferentes a las mostradas más arriba.

Estrellar cada renglón que da un valor negativo a la variable asociada activa (salvo la variable ojectiva, que puede ser negativa). Si hay algunos renglonges estrellados, tiene que empezar con Fase I:

Fase I: Llevándose a la región factible (Deshaciéndose de las estrellas)
En el primero renglón estrellado, encuentre la entrada positiva más grande. Use razones de prueba como más arriba para encontrar el pivote en su columna (excluyendo el último renglón como de costumbre), y pivote. Nota: Si la razón más pequeña ocurre en un renglón estrellado y también en un renglón no estrellado, escoja el pivote en un renglón estrellado. Después de pivotar, comprueba otra vez para ver cual renglones necesitan estrellas. Repita hasta que permanece no renglones estrellados, y después avance a Fase II.

Fase II: Use el método para problemas PL estándar.
Si permanece algunas entradas a la izquierda del último renglón después de Fase I, use el método descrito más arriba para solucionar problemas estándar de maximización.

Para algunos ejemplos interactivos, visita el tutorial para problemas general de programación lineal.

Para solucionar un problema de minimización por el método simplex, se convierte el problema en un problema de maximización por negar la función objetiva: En vez de minimizar c, se maximiza p = -c.

El problema PL de minimización:

Minimizar C = 3x + 4y - 8z sujeta a

3x - 4y ≤ 12,
x + 2y + z ≥ 4
4x - 2y + 5z ≤ 20
x ≥ 0,   y ≥ 0,   z ≥ 0

Maximizar P = -3x - 4y + 8z sujeta a

3x - 4y ≤ 12,
x + 2y + z ≥ 4
4x - 2y + 5z ≤ 20
x ≥ 0,   y ≥ 0,   z ≥ 0.

Para solucionar un juego por el método simplex:

Antes de empezar, busque a puntos de silla. Si encuentra uno, ha ya solucionado al juego; las estrategias óptimas son las estrategias puras que pasan por un punto de silla. Si no, siga los siguientes pasos:

1. Reduzca a la matriz del pagos por predominio.
2. Añada un número fijado k a cada pago para que todos se vuelven no negativos.
3. Configura y solucione al asociado problema de programación lineal pos el método simplex.
4. Obtenga las estrategias óptimas y el valor esperado como sigue:

Estrategia columna
1. Escriba la solución del problema PL como un vector columna.
2. Normalice por dividir cada entrada del vector solución por la suma de las entradas, o, igualmente, por el valor de la variable objetiva p.
3. Introduzca ceros en posiciones que corresponden a columnas borradas durante reducción.

Estrategia renglón
1. Escriba el vector renglón cuyas entradas son los números que aparecen in el último renglón de abajo de las variables de holgura en la tabla final del método simplex.
2. Normalice por dividir cada entrada del vector solución por la suma de las entradas.
3. Introduzca ceros en posiciones que corresponden a renglones borrados durante reducción.

Valor del juego

e = ¹/_p - k.