Programación Lineal
La PL es un método matemático de resolución de problemas donde el objetivo es optimizar (maximizar o minimizar) un resultado a partir de seleccionar los valores de un conjunto de variables de decisión, respetando restricciones correspondientes a disponibilidad de recursos, especificaciones técnicas, u otras condicionantes que limiten la libertad de elección.
La maximización de beneficios nos llevará a problemas en los que tengamos que determinar la producción: qué se debe fabricar y en qué cantidades para que se obtenga el máximo beneficio teniendo en cuenta las limitaciones técnicas y humanas. En el campo agrícola la adecuada utilización de los terrenos, los cupos de producción, ..., etc.
En los problemas de mínimos podremos calcular los costes mínimos para alimentar a los animales de una granja condicionado a los requerimientos nutricionales. Minimización de la contaminación atmosférica, optimización de recursos humanos, ..., etc.
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 + . . .
(llamada la función ojectiva), sujeta a unas restricciones lineales de la forma
Ax + By + Cz + . . .≤ N
o
Ax + By + Cz + . . .≥ N.
El valor más grande o más pequeño de la función objetiva se llama el valor óptimo, y un conjunto de valores de x, y, z, . . . que se resultan en el valor óptimo es la solución óptima. Las variables x, y, z, . . . se llaman las variables decisión.
Método gráfico
El método gráfico para solucionar a un problema de programación lineal es el siguiente:
Dibuje la región factible de los restricciones.
Calcule las coordenadas de los puntos extremos (puntos de esquina).
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.
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:
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.
Calcule las coordenadas de los puntos nuevos de esquina que se obtiene.
Halle el punto de esquina donde ocurre el valor óptimo de la función ojectiva.
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.
Problema de maximización estándar
Una 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, . . . ,
y restricciones adicionales de la forma
Ax + By + Cz + . . . ≤ N,
donde A, B, C, . . . y N son números con N no negativa.
Observe que la desigualdad aquí debe ser una "≤," y no "=" o "≥."
Método simplex para problemas de maximización estándar
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.
Solución básica
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.
Método Simplex para problemas de minimización
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.
Ejemplo
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.
La PL es un método matemático de resolución de problemas donde el objetivo es optimizar (maximizar o minimizar) un resultado a partir de seleccionar los valores de un conjunto de variables de decisión, respetando restricciones correspondientes a disponibilidad de recursos, especificaciones técnicas, u otras condicionantes que limiten la libertad de elección.
La maximización de beneficios nos llevará a problemas en los que tengamos que determinar la producción: qué se debe fabricar y en qué cantidades para que se obtenga el máximo beneficio teniendo en cuenta las limitaciones técnicas y humanas. En el campo agrícola la adecuada utilización de los terrenos, los cupos de producción, ..., etc.
En los problemas de mínimos podremos calcular los costes mínimos para alimentar a los animales de una granja condicionado a los requerimientos nutricionales. Minimización de la contaminación atmosférica, optimización de recursos humanos, ..., etc.
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 + . . .
(llamada la función ojectiva), sujeta a unas restricciones lineales de la forma
Ax + By + Cz + . . .≤ N
o
Ax + By + Cz + . . .≥ N.
El valor más grande o más pequeño de la función objetiva se llama el valor óptimo, y un conjunto de valores de x, y, z, . . . que se resultan en el valor óptimo es la solución óptima. Las variables x, y, z, . . . se llaman las variables decisión.
Método gráfico
El método gráfico para solucionar a un problema de programación lineal es el siguiente:
Dibuje la región factible de los restricciones.
Calcule las coordenadas de los puntos extremos (puntos de esquina).
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.
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:
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.
Calcule las coordenadas de los puntos nuevos de esquina que se obtiene.
Halle el punto de esquina donde ocurre el valor óptimo de la función ojectiva.
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.
Problema de maximización estándar
Una 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, . . . ,
y restricciones adicionales de la forma
Ax + By + Cz + . . . ≤ N,
donde A, B, C, . . . y N son números con N no negativa.
Observe que la desigualdad aquí debe ser una "≤," y no "=" o "≥."
Método simplex para problemas de maximización estándar
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.
Solución básica
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.
Método Simplex para problemas de minimización
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.
Ejemplo
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.
Programación Lineal
La PL es un método matemático de resolución de problemas donde el objetivo es optimizar (maximizar o minimizar) un resultado a partir de seleccionar los valores de un conjunto de variables de decisión, respetando restricciones correspondientes a disponibilidad de recursos, especificaciones técnicas, u otras condicionantes que limiten la libertad de elección.
La maximización de beneficios nos llevará a problemas en los que tengamos que determinar la producción: qué se debe fabricar y en qué cantidades para que se obtenga el máximo beneficio teniendo en cuenta las limitaciones técnicas y humanas. En el campo agrícola la adecuada utilización de los terrenos, los cupos de producción, ..., etc.
En los problemas de mínimos podremos calcular los costes mínimos para alimentar a los animales de una granja condicionado a los requerimientos nutricionales. Minimización de la contaminación atmosférica, optimización de recursos humanos, ..., etc.
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 + . . .
(llamada la función objetiva), sujeta a unas restricciones lineales de la forma
Ax + By + Cz + . . .≤ N
o
Ax + By + Cz + . . .≥ N.
Función Objetivo
La función objetivo puede ser:
ó
Donde:
f = coeficientes conocidos.
Ejemplo: Que es la función objetivo por maximizar.
Maíz
Trigo
Elementos disponibles
Horas
2
1
Hectáreas
1
1
800
Utilidad por unidad
$40
$30
480
La cantidad total de tiempo par hectáreas para sembrar maíz y trigo está dada por 2x+y horas que no debe exceder las 800 horas disponibles para el trabajo. Así se tiene la desigualdad:
2x+y<800>0
y>0
En resumen, el problema en cuestión consiste en maximizar la función objetivo P=40x+30y
sujeta a las desigualdades
2x+y<800>0
y>0
Solución Gráfica
Los problemas de programación lineal en dos variables tienen interpretaciones geométricas relativamente sencillas; por ejemplo, el sistema de restricciones lineales asociado con un problema de programación lineal bidimensional- si no es inconsistente- define una región plana cuya frontera está formada por segmentos de recta o semirrectas, por lo tanto es posible analizar tales problemas en forma gráfica.
Si consideremos el problema del granjero López, es decir, de maximizar P = 40x+ 30y sujeta a
2x+y<800>0, y>0 (7)
El sistema de desigualdades (7) define la región plana S que aparece en la figura 5. Cada punto de S es un candidato para resolver este problema y se conoce
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 + . . .
(llamada la función ojectiva), sujeta a unas restricciones lineales de la forma
Ax + By + Cz + . . .≤ N
o
Ax + By + Cz + . . .≥ N.
El valor más grande o más pequeño de la función objetiva se llama el valor óptimo, y un conjunto de valores de x, y, z, . . . que se resultan en el valor óptimo es la solución óptima. Las variables x, y, z, . . . se llaman las variables decisión.
Método gráfico
El método gráfico para solucionar a un problema de programación lineal es el siguiente:
Dibuje la región factible de los restricciones.
Calcule las coordenadas de los puntos extremos (puntos de esquina).
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.
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 objetiva cuyos 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:
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.
Calcule las coordenadas de los puntos nuevos de esquina que se obtiene.
Halle el punto de esquina donde ocurre el valor óptimo de la función ojectiva.
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.
Problema de maximización estándar
Una 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, . . . ,
y restricciones adicionales de la forma
Ax + By + Cz + . . . ≤ N,
donde A, B, C, . . . y N son números con N no negativa.
Observe que la desigualdad aquí debe ser una "≤," y no "=" o "≥."
Método simplex para problemas de maximización estándar
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.
No hay comentarios:
Publicar un comentario