Matemáticas finitas resumen del
tema: programación lineal
Herramientas: Gráficador programación lineal | Consigue el app: App graficador programación lineal
(Android)
| Herramienta Gauss-Jordan y pivotador | Herramienta Excel Gauss-Jordan y pivotador | Herramienta método
simplex
Tópicos: Problema de programación lineal | Dibujar el conjunto solución de una desigualdad lineal | La región
factible | Método gráfico | Problema de maximización estándar | Método simplex para problemas de
maximización estándar | Solución básica | Restricciones no estándar | Método simplex para problemas de
minimización | Solucionar un juego matriz por el método simplex
Problema de Ejemplo
programación lineal (PL)
El siguiente es un ejemplo de un problema PL:
Un problema de programación
lineal es un problema en cual Determine el valor máximo de
debemos hallar el valor máximo
o mínimo de una expresión lineal p = 3x - 2y + 4z
sujeta a
ax + by + cz + . . . 4x + 3y - z ≥ 3
(llamada la función ojectiva), x + 2y + z ≤ 4
sujeta a unas restricciones x ≥ 0, y ≥ 0, z ≥ 0
lineales de la forma
Ax + By + Cz + . . .≤ N
o La función ojectiva es p = 3x - 2y + 4z. Las restricciones son
Ax + By + Cz + . . .≥ N.
El valor más grande o más 4x + 3y - z ≥ 3
pequeño de la función objetiva se x + 2y + z ≤ 4
llama el valor óptimo, y un x ≥ 0, y ≥ 0, z ≥ 0.
conjunto de valores de x, y, z, . . .
que se resultan en el valor P ¡Espera! ¿Porqué no puedo sencillamente escoger, por ejemplo, que
óptimo es la solución óptima.
tenga z un valor muy grande (como z = 1,000,000) y así hacer que p sea
Las variables x, y, z, . . . se
como grande que quiero?
llaman las variables decisión.
Inicio de página C No se puede
porque:
Escoja una
Inicio de página
Dibujar el conjunto Ejemplo
solución de una
desigualdad lineal
Para dibujar la región Para dibujar la desigualdad lineal:
representada por una desigualdad
en dos variables: 3x - 4y ≤ 12,
Primero dibuje la recta 3x - 4y = 12.
A. Dibuje la recta que se obtiene
por sustituir una igualdad por la
desigualdad. Después, elije el origen (0, 0) como el punto de prueba (pues no está en
la recta). Sustituyendo x = 0, y = 0 en la desigualdad, obtenemos
B. Escoja un punto de prueba 3(0) - 4(0) ≤ 12,
que no está en la recta ((0,0) es una declaración verdadera. Entonces, (0, 0) sí está en el conjunto
una elección conveniente si la solución, que se consiste entonces de todos los puntos en el mismo lado
recta no pasa por el origen. Si que (0, 0). Dejamos claro esta región, mientras sombreamos la región no
pasa por el origen, un punto en solución para ocultarla.
un eje sería suficiente).
C. Si el punto de prueba satisface Inicio de página
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.
Inicio de página
Región factible Ejemplo
La región factible determinada La región factible determinada por el siguiente conjunto de
por un conjunto de desigualdades desigualdades es la región no sombreada mostrada más abajo
lineales es el conjunto de puntos (incluyendo su frontera).
que satisfacen a la vez todas las
desigualdades. 3x - 4y ≤ 12,
x + 2y ≥ 4
Para dibujar la región factible x≥1
determinada por un conjunto de y ≥ 0.
desigualdades lineales: Dibuje
las regiones determinadas por
cada desigualdad recordando en Inicio de página
cada caso sombrear la parte del
plano que no quiere. La región
que permanece sin sombreado es
la región factible.
Inicio de página
Método gráfico Ejemplo
El método gráfico para Minimizar C = 3x + 4y sujeta a
solucionar a un problema de
programación lineal es el 3x - 4y ≤ 12,
siguiente: x + 2y ≥ 4
x ≥ 1, y ≥ 0.
A. Dibuje la región factible
de los restricciones. La región factible para este conjunto de restricciones fue mostrada más
B. Calcule las coordenadas arriba. Aquí está otra vez con los puntos de esquinas indicados.
de los puntos extremos
(puntos de esquina).
C. Sustituya las
coordenadas de los
puntos de esquina en la
función objetiva para Aunque no es acotada la región factible, estamos minimizando C = 3x +
ver cual da el valor 4y, cuyas coeficientes son no negativos. Entonces existe una solución
óptimo. Este punto da la obtenida por el método más arriba a la izquierda.
solución del problema
de programación lineal. La siguiente tabla muestra el valor de C a cada punto de esquina:
D. Si la región factible no
es acotada, este método Punto C = 3x + 4y
puede ser erróneo:
soluciones óptimas (1, 1.5) 3(1)+4(1.5) = 9
siempre existen cuando mínimo
la región factible está (4, 0) 3(4)+4(0) = 12
acotada, pero pueden no Entonces, la solución es x = 1, y = 1.5, que da C = 9 como el valor
existir en el caso no mínimo.
acotado. Inicio de página
Si la región factible no
es acotada,
estamos minimizando u
na 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 Gráficador
programación lineal or consigue
el app: App graficador
programación lineal
(Android) ¡Hacen todo
automáticamente, incluyendo
dibujar la región factible!
Inicio de página
Problema de Ejemplos
maximización estándar
La siguiente es una problema de maximización estándar:
Un problema de maximización
estándar con n incógnitas es un Maximizar P = 2x - 3y + z sujeta a
problema de programación lineal
en lo que necesitamos maximizar
4x - 3y + z ≤ 3
(no minimizar) la función
x + y + z ≤ 10
ojectiva, sujeta a restricciones de
x ≥ 0, y ≥ 0, z ≥ 0.
la forma
La siguiente no es una problema de maximización estándar::
x ≥ 0, y ≥ 0, z ≥ 0, . . . ,
y restricciones adicionales de la
forma Maximizar P = 2x - 3y + z sujeta a
Ax + By + Cz + . . . ≤ N,
donde A, B, C, . . . y N son 4x - 3y + z ≥ 3
números con N no negativa. x + y + z ≤ 10
x ≥ 0, y ≥ 0, z ≥ 0.
Observe que la desigualdad aquí
debe ser una "≤," y no "=" o "≥." Inicio de página
Inicio de página
Método simplex para Unos enlaces útiles
problemas de
maximización estándar Tutorial sobre el método simplex
Herramienta Gauss-Jordan y pivotador
Para solucionar un problema de
maximización estándar por Herramienta Excel Gauss-Jordan y pivotador
el método simplex, seguimos los
siguientes pasos: Herramienta método simplex
Paso 1. Convierta las
desigualdades en igualdades por
introducir variables de Inicio de página
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.
Inicio de página
Solución básica Ejemplo
Para obtener la solución En la siguiente tabla
básica que corresponde a alguna
tabla del método simplex, iguale x y z s t u p Ans
a cero a todas las variables que
no aparecen como etiquetas de
renglones (estas son -1 0 0 1 0 0 0 4
las variables inactivas). 1 0 3 0 0 8 0 12
4 0 0 0 3 0 0 2
El valor de una variable que no
aparece como una etiqueta de -5 2 0 0 0 6 0 4
renglón (es decir, una variable
activa) es la razón a/b, en la 6 0 0 0 0 0 5 -25
que a es la entrada de la última
la solución básica es
columna del renglón y a es la
x = 0, y = 2, z = 4, s = 4, t = 2/3, u = 0, p = -5,
entrada de aquel renglón cuya
y las variables activas son y, z, s, t, y p.
columna tiene la misma etiqueta.
Inicio de página
Inicio de página
Restricciones no estándar
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 .
Inicio de página
Método Simplex para Ejemplo
problemas de
minimización El problema PL de minimización:
Para solucionar un problema de Minimizar C = 3x + 4y - 8z sujeta a
minimización por el método 3x - 4y ≤ 12,
simplex, se convierte el x + 2y + z ≥ 4
problema en un problema de 4x - 2y + 5z ≤ 20
maximización por negar la x ≥ 0, y ≥ 0, z ≥ 0
función objetiva: En vez de
minimizar c, se maximiza p = - puede ser reemplazar por el siguiente problema de maximización:
c. Maximizar P = -3x - 4y + 8z sujeta a
3x - 4y ≤ 12,
Inicio de página x + 2y + z ≥ 4
4x - 2y + 5z ≤ 20
x ≥ 0, y ≥ 0, z ≥ 0.
Inicio de página
Solucionar un juego matriz por el método simplex
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
a. Escriba la solución del problema PL como un vector columna.
b. 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.
c. Introduzca ceros en posiciones que corresponden a columnas borradas durante reducción.
Estrategia renglón
d. 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.
e. Normalice por dividir cada entrada del vector solución por la suma de las entradas.
f. Introduzca ceros en posiciones que corresponden a renglones borrados durante reducción.
Valor del juego
e = 1/p - k.