1. Introducción a la Programación Lineal
Flashcards
- ¿Qué significa el término 'programación' en 'programación lineal'?
- Elegir un curso de acción.
- ¿Qué es una solución óptima en programación lineal?
- Una solución viable que da el mayor valor posible al maximizar (o el menor al minimizar) la función objetivo.
- Menciona dos directrices para la formulación de modelos de programación lineal.
- Comprender el problema a fondo y describir el objetivo.
- ¿Qué representan las variables de holgura y excedente?
- La diferencia entre los lados izquierdo y derecho de las restricciones.
Preguntas tipo test
- ¿Cuál es el objetivo principal de los problemas de programación lineal?
- a) Maximizar o minimizar una cantidad.
- b) Encontrar la solución más compleja.
- c) Ignorar las restricciones del problema.
- d) Utilizar el método gráfico solamente.
Respuesta: a) Maximizar o minimizar una cantidad.. El objetivo principal de los problemas de programación lineal es maximizar o minimizar una cantidad, respetando las restricciones dadas.
- En programación lineal, ¿qué define una solución viable?
- a) Una solución que maximiza la función objetivo.
- b) Una solución que minimiza la función objetivo.
- c) Una solución que satisface todas las restricciones del problema.
- d) Cualquier solución, sin importar las restricciones.
Respuesta: c) Una solución que satisface todas las restricciones del problema.. Una solución viable es aquella que cumple con todas las restricciones establecidas en el problema de programación lineal.
- ¿Qué tipo de funciones se utilizan en un problema de programación lineal?
- a) Funciones exponenciales.
- b) Funciones cuadráticas.
- c) Funciones lineales.
- d) Funciones logarítmicas.
Respuesta: c) Funciones lineales.. En programación lineal, tanto la función objetivo como las restricciones deben ser funciones lineales.
2. Problema de Programación Lineal (LP)
Flashcards
- ¿Qué significa el término 'programación' en 'programación lineal'?
- Elegir un curso de acción.
- ¿Qué tipo de funciones se utilizan en el modelo matemático de un problema de programación lineal?
- Funciones lineales.
- ¿Qué es una solución óptima en programación lineal?
- Una solución viable que da como resultado el mayor valor posible de la función objetivo al maximizarla (o el menor al minimizarla).
- ¿Cómo se denominan las esquinas o vértices de la región factible en un problema de programación lineal?
- Puntos extremos.
Preguntas tipo test
- ¿Cuál es el objetivo principal de cualquier problema de Programación Lineal (PL)?
- a) Encontrar una solución que satisfaga algunas de las restricciones.
- b) Maximizar o minimizar una cantidad.
- c) Ignorar las restricciones para simplificar el problema.
- d) Encontrar una solución que no sea viable.
Respuesta: b) Maximizar o minimizar una cantidad.. El objetivo de todos los problemas de programación lineal es maximizar o minimizar alguna cantidad, sujeto a las restricciones dadas.
- ¿Qué característica deben tener tanto la función objetivo como las restricciones para que un problema se considere de Programación Lineal?
- a) Deben ser exponenciales.
- b) Deben ser lineales.
- c) Deben ser cuadráticas.
- d) Deben ser logarítmicas.
Respuesta: b) Deben ser lineales.. Para que un problema se considere de programación lineal, tanto la función objetivo como las restricciones deben ser lineales.
- ¿Qué representa una solución viable en un problema de Programación Lineal?
- a) Una solución que maximiza la función objetivo sin considerar las restricciones.
- b) Una solución que satisface todas las restricciones del problema.
- c) Una solución que minimiza la función objetivo sin considerar las restricciones.
- d) Una solución que viola al menos una de las restricciones.
Respuesta: b) Una solución que satisface todas las restricciones del problema.. Una solución viable es aquella que cumple con todas las restricciones establecidas en el problema de Programación Lineal.
3. Formulación del Problema
Flashcards
- ¿Qué significa el término 'programación' en 'programación lineal'?
- Elegir un curso de acción.
- ¿Qué tipo de funciones se utilizan en la programación lineal?
- Funciones lineales.
- ¿Qué es una solución viable en programación lineal?
- Una solución que satisface todas las restricciones del problema.
- ¿Qué es una solución óptima en programación lineal?
- Una solución viable que da como resultado el mayor (o menor) valor posible de la función objetivo.
Preguntas tipo test
- ¿Cuál es el objetivo principal de los problemas de programación lineal?
- a) Maximizar o minimizar alguna cantidad.
- b) Encontrar soluciones informáticas complejas.
- c) Crear modelos gráficos precisos.
- d) Definir restricciones no lineales.
Respuesta: a) Maximizar o minimizar alguna cantidad.. El objetivo de la programación lineal es optimizar (maximizar o minimizar) una función objetivo, que representa la cantidad que se desea optimizar.
- ¿Qué se necesita para dominar la formulación de modelos de programación lineal?
- a) Conocimientos avanzados de informática.
- b) Experiencia y práctica constante.
- c) Software especializado de modelización.
- d) Comprensión de algoritmos complejos.
Respuesta: b) Experiencia y práctica constante.. La formulación de modelos es un arte que se perfecciona con la práctica y la experiencia, ya que cada problema tiene sus particularidades.
- Según las directrices para la formulación de modelos, ¿qué se debe hacer después de comprender el problema a fondo?
- a) Definir las variables de decisión.
- b) Describir cada restricción.
- c) Describir el objetivo.
- d) Escribir el objetivo en términos de las variables de decisión.
Respuesta: c) Describir el objetivo.. Después de comprender el problema, el siguiente paso lógico es definir claramente el objetivo que se busca alcanzar.
4. Ejemplo 1: Un Problema de Maximización Simple
Flashcards
- ¿Qué es la programación lineal?
- Es un método para elegir un curso de acción cuando el modelo matemático contiene solo funciones lineales.
- ¿Qué es una solución viable en programación lineal?
- Una solución que satisface todas las restricciones del problema.
- ¿Qué es una solución óptima en programación lineal?
- Una solución viable que resulta en el mayor valor posible de la función objetivo al maximizarla (o el menor al minimizarla).
- ¿Qué tipo de funciones se utilizan en programación lineal?
- Funciones lineales, donde cada variable aparece en un término separado elevado a la primera potencia.
Preguntas tipo test
- ¿Cuál es el objetivo principal de los problemas de programación lineal?
- a) Maximizar o minimizar alguna cantidad.
- b) Encontrar soluciones informáticas.
- c) Formular problemas matemáticos complejos.
- d) Resolver ecuaciones no lineales.
Respuesta: a) Maximizar o minimizar alguna cantidad.. El objetivo de la programación lineal es encontrar el valor máximo o mínimo de una función, sujeto a una serie de restricciones lineales. Esto se traduce en maximizar o minimizar alguna cantidad.
- ¿Qué se necesita para que una solución sea considerada 'viable' en un problema de programación lineal?
- a) Satisfacer solo la función objetivo.
- b) Satisfacer solo algunas de las restricciones.
- c) Satisfacer todas las restricciones del problema.
- d) Maximizar la función objetivo sin restricciones.
Respuesta: c) Satisfacer todas las restricciones del problema.. Una solución viable es aquella que cumple con todas las condiciones y limitaciones impuestas por las restricciones del problema. Es decir, debe satisfacer todas las restricciones.
- En la formulación de un problema de programación lineal, ¿qué representan las variables de decisión?
- a) Los coeficientes de la función objetivo.
- b) Las cantidades que se pueden elegir para optimizar el objetivo.
- c) Las restricciones del problema.
- d) Los valores constantes en las restricciones.
Respuesta: b) Las cantidades que se pueden elegir para optimizar el objetivo.. Las variables de decisión son los elementos sobre los cuales tenemos control y que podemos ajustar para alcanzar el mejor valor posible para la función objetivo. Representan las cantidades que se pueden elegir.
5. Ejemplo 1: Solución Gráfica (Restricciones)
Flashcards
- ¿Qué es una solución factible?
- Una solución que satisface todas las restricciones del problema.
- ¿Qué es la región factible?
- El conjunto de todos los puntos que satisfacen todas las restricciones del problema.
- ¿Qué son los puntos extremos en la solución gráfica?
- Las esquinas o vértices de la región factible.
- ¿Qué tipo de funciones se utilizan en un problema de programación lineal?
- Funciones lineales.
Preguntas tipo test
- ¿Cuál es el objetivo principal de los problemas de programación lineal?
- a) Maximizar o minimizar una cantidad.
- b) Encontrar soluciones informáticas.
- c) Dibujar gráficos de restricciones.
- d) Formular modelos matemáticos complejos.
Respuesta: a) Maximizar o minimizar una cantidad.. El objetivo de la programación lineal es encontrar el valor máximo o mínimo de una función objetivo, sujeta a ciertas restricciones.
- ¿Qué es una solución viable en programación lineal?
- a) Una solución que maximiza la función objetivo.
- b) Una solución que minimiza la función objetivo.
- c) Una solución que satisface todas las restricciones del problema.
- d) Una solución que no cumple ninguna restricción.
Respuesta: c) Una solución que satisface todas las restricciones del problema.. Una solución viable es aquella que cumple con todas las condiciones impuestas por las restricciones del problema, lo que la hace posible dentro del contexto definido.
- ¿Qué tipo de funciones se utilizan en un problema de programación lineal?
- a) Funciones exponenciales.
- b) Funciones cuadráticas.
- c) Funciones lineales.
- d) Funciones logarítmicas.
Respuesta: c) Funciones lineales.. La programación lineal se basa en el uso de funciones lineales, donde las variables están elevadas a la primera potencia y multiplicadas por constantes.
6. Ejemplo 1: Solución Gráfica (Función Objetivo)
Flashcards
- ¿Qué significa 'programación' en el contexto de la programación lineal?
- Elegir un curso de acción.
- ¿Qué tipo de funciones contiene el modelo matemático en la programación lineal?
- Funciones lineales.
- ¿Qué es una solución óptima en programación lineal?
- Una solución viable que da como resultado el mayor o menor valor posible de la función objetivo.
- ¿Qué se necesita para dominar la formulación de modelos de programación lineal?
- Práctica y experiencia.
Preguntas tipo test
- ¿Cuál es el objetivo principal de cualquier problema de programación lineal?
- a) Maximizar una función exponencial.
- b) Minimizar una función logarítmica.
- c) Maximizar o minimizar una cantidad.
- d) Encontrar el punto medio de un conjunto de datos.
Respuesta: c) Maximizar o minimizar una cantidad.. El objetivo principal de cualquier problema de programación lineal es encontrar el valor máximo o mínimo de una función objetivo, que representa una cantidad que se desea optimizar.
- ¿Qué tipo de funciones se utilizan en un problema de programación lineal?
- a) Funciones cuadráticas.
- b) Funciones exponenciales.
- c) Funciones logarítmicas.
- d) Funciones lineales.
Respuesta: d) Funciones lineales.. En un problema de programación lineal, tanto la función objetivo como las restricciones deben ser funciones lineales. Esto significa que las variables aparecen en términos separados elevados a la primera potencia y multiplicados por constantes.
- En la solución gráfica de un problema de programación lineal, ¿qué representa la región factible?
- a) El conjunto de puntos que maximizan la función objetivo.
- b) El conjunto de puntos que minimizan la función objetivo.
- c) El conjunto de puntos que satisfacen todas las restricciones del problema.
- d) El conjunto de puntos que no cumplen ninguna de las restricciones.
Respuesta: c) El conjunto de puntos que satisfacen todas las restricciones del problema.. La región factible es el área en el gráfico donde todos los puntos cumplen con todas las restricciones del problema simultáneamente. Cualquier solución dentro de esta región es una solución viable.
7. Ejemplo 1: Solución Óptima
Flashcards
- ¿Qué significa 'programación' en programación lineal?
- Elegir un curso de acción.
- ¿Qué es una solución óptima?
- Una solución viable que da el mayor valor posible de la función objetivo (o el menor al minimizarla).
- ¿Cuál es el primer paso en la formulación de un modelo de programación lineal?
- Comprender el problema a fondo.
- ¿Qué representan las variables de holgura y excedente?
- La diferencia entre los lados izquierdo y derecho de las restricciones.
Preguntas tipo test
- ¿Cuál es el objetivo principal de los problemas de programación lineal?
- a) Maximizar o minimizar una cantidad.
- b) Encontrar la solución más rápida.
- c) Optimizar el uso de la memoria en computadoras.
- d) Crear interfaces gráficas atractivas.
Respuesta: a) Maximizar o minimizar una cantidad.. Los problemas de programación lineal buscan maximizar o minimizar una cantidad, que es el objetivo central de este tipo de problemas.
- ¿Qué es una solución viable en programación lineal?
- a) Una solución que maximiza la función objetivo.
- b) Una solución que satisface todas las restricciones del problema.
- c) Una solución que minimiza la función objetivo.
- d) Cualquier solución, independientemente de las restricciones.
Respuesta: b) Una solución que satisface todas las restricciones del problema.. Una solución viable es aquella que cumple con todas las restricciones establecidas en el problema de programación lineal.
- ¿Qué tipo de funciones se utilizan en un problema de programación lineal?
- a) Funciones exponenciales.
- b) Funciones cuadráticas.
- c) Funciones logarítmicas.
- d) Funciones lineales.
Respuesta: d) Funciones lineales.. La programación lineal se basa en el uso de funciones lineales tanto en la función objetivo como en las restricciones.
8. Variables de Holgura y Excedente
Flashcards
- ¿Qué son las variables de holgura?
- Variables añadidas a restricciones '≤' para convertirlas en '='.
- ¿Qué son las variables de excedente?
- Variables restadas de restricciones '≥' para convertirlas en '='.
- ¿Cuál es el coeficiente de las variables de holgura en la función objetivo?
- Cero.
- ¿Cuál es el coeficiente de las variables de excedente en la función objetivo?
- Cero.
Preguntas tipo test
- ¿Qué se añade a las restricciones 'menor o igual que' para obtener la forma estándar en programación lineal?
- a) Variables de holgura
- b) Variables de excedente
- c) Variables artificiales
- d) Variables básicas
Respuesta: a) Variables de holgura. Las variables de holgura se añaden a las restricciones 'menor o igual que' para convertir las desigualdades en igualdades, facilitando la resolución del problema en su forma estándar.
- ¿Qué valor tienen los coeficientes de función objetivo para las variables de holgura y excedente?
- a) 1
- b) -1
- c) 0
- d) Depende del problema
Respuesta: c) 0. Las variables de holgura y excedente no contribuyen directamente al valor de la función objetivo, por lo que sus coeficientes se establecen en 0.
- ¿Cuál es el propósito de las variables de excedente en programación lineal?
- a) Convertir restricciones 'menor o igual que' en igualdades
- b) Convertir restricciones 'mayor o igual que' en igualdades
- c) Asegurar que todas las variables sean no negativas
- d) Maximizar la función objetivo
Respuesta: b) Convertir restricciones 'mayor o igual que' en igualdades. Las variables de excedente se restan de las restricciones 'mayor o igual que' para transformarlas en igualdades, permitiendo que el problema se exprese en forma estándar.
9. Puntos Extremos y la Solución Óptima
Flashcards
- ¿Qué son los puntos extremos?
- Las esquinas o vértices de la región factible.
- ¿Dónde se encuentra la solución óptima en un problema de programación lineal?
- En un punto extremo de la región factible.
- ¿Es necesario evaluar todos los puntos factibles para encontrar la solución óptima?
- No, solo los puntos extremos.
- ¿Qué representan las variables de holgura?
- La diferencia entre los lados izquierdo y derecho de las restricciones 'menor o igual que'.
Preguntas tipo test
- ¿Qué son los puntos extremos en la programación lineal?
- a) Puntos que maximizan la función objetivo.
- b) Las esquinas o vértices de la región factible.
- c) Puntos que minimizan la función objetivo.
- d) El centro de la región factible.
Respuesta: b) Las esquinas o vértices de la región factible.. Los puntos extremos son las esquinas o vértices de la región factible, donde las restricciones se intersectan.
- ¿Dónde se puede encontrar una solución óptima en un problema de programación lineal?
- a) En cualquier punto dentro de la región factible.
- b) En el punto medio de la región factible.
- c) En un punto extremo de la región factible.
- d) Fuera de la región factible.
Respuesta: c) En un punto extremo de la región factible.. Una solución óptima en un problema de programación lineal se encuentra en un punto extremo de la región factible.
- Al buscar la solución óptima, ¿es necesario evaluar todos los puntos factibles?
- a) Sí, siempre es necesario evaluar todos los puntos.
- b) No, solo es necesario evaluar los puntos extremos.
- c) Depende del tamaño de la región factible.
- d) Solo es necesario evaluar los puntos en los ejes.
Respuesta: b) No, solo es necesario evaluar los puntos extremos.. No es necesario evaluar todos los puntos factibles, solo los puntos extremos de la región factible.
10. Soluciones Informáticas
Flashcards
- ¿Qué tipo de problemas se pueden resolver usando paquetes informáticos en optimización lineal?
- Problemas con miles de variables y restricciones.
- ¿Qué paquete de hoja de cálculo comúnmente incluye solucionadores de programación lineal?
- Microsoft Excel.
- Nombra al menos tres paquetes comerciales destacados para la optimización lineal.
- CPLEX, LINGO, MOSEK, Xpress-MP, Premium Solver for Excel.
- ¿Qué resultados se analizan al interpretar los resultados del ordenador en programación lineal?
- Valor de la función objetivo, valores de las variables de decisión, costes reducidos, holgura y excedente.
Preguntas tipo test
- ¿Qué tipo de problemas se resuelven rutinariamente con paquetes informáticos en la optimización lineal?
- a) Problemas con pocas variables y restricciones
- b) Problemas con miles de variables y restricciones
- c) Problemas que requieren cálculo manual extenso
- d) Problemas que no involucran optimización
Respuesta: b) Problemas con miles de variables y restricciones. Los problemas de optimización lineal que involucran miles de variables y miles de restricciones ahora se resuelven de forma rutinaria con paquetes informáticos.
- ¿Qué software de hoja de cálculo incluye solucionadores de programación lineal?
- a) Microsoft Word
- b) Microsoft PowerPoint
- c) Microsoft Excel
- d) Adobe Photoshop
Respuesta: c) Microsoft Excel. Los solucionadores de programación lineal forman parte ahora de muchos paquetes de hojas de cálculo, como Microsoft Excel.
- ¿Cuál de los siguientes NO es un paquete comercial destacado para la optimización lineal?
- a) CPLEX
- b) LINGO
- c) MOSEK
- d) PowerPoint
Respuesta: d) PowerPoint. Entre los paquetes comerciales más destacados se incluyen CPLEX, LINGO, MOSEK, Xpress-MP y Premium Solver for Excel.
11. Ejemplo 1: Solución con Hoja de Cálculo
Flashcards
- ¿Qué significa 'programación' en la programación lineal?
- Elegir un curso de acción.
- ¿Qué es una solución óptima?
- Una solución viable que da el mayor valor posible a la función objetivo (o el menor al minimizarla).
- ¿Qué son las variables de decisión?
- Variables que representan las cantidades que se pueden controlar para optimizar la función objetivo.
- ¿Qué representan las variables de holgura?
- La diferencia entre los lados izquierdo y derecho de las restricciones 'menor o igual que'.
Preguntas tipo test
- ¿Cuál es el objetivo principal de los problemas de programación lineal?
- a) Maximizar o minimizar una cantidad.
- b) Encontrar soluciones informáticas.
- c) Formular problemas matemáticos complejos.
- d) Crear modelos gráficos de restricciones.
Respuesta: a) Maximizar o minimizar una cantidad.. El objetivo de la programación lineal es optimizar, ya sea maximizando o minimizando, una función objetivo sujeta a ciertas restricciones.
- ¿Qué tipo de funciones se utilizan en un problema de programación lineal?
- a) Funciones exponenciales.
- b) Funciones logarítmicas.
- c) Funciones lineales.
- d) Funciones cuadráticas.
Respuesta: c) Funciones lineales.. La programación lineal se basa en el uso de funciones lineales tanto en la función objetivo como en las restricciones.
- ¿Qué representa una solución viable en programación lineal?
- a) Una solución que maximiza la función objetivo.
- b) Una solución que minimiza la función objetivo.
- c) Una solución que satisface todas las restricciones del problema.
- d) Una solución que viola al menos una restricción.
Respuesta: c) Una solución que satisface todas las restricciones del problema.. Una solución viable es aquella que cumple con todas las condiciones y limitaciones establecidas en las restricciones del problema.
12. Reducción de Costes
Flashcards
- ¿Qué indica el 'coste reducido' de una variable en programación lineal?
- Cuánto debe mejorar el coeficiente de la función objetivo para que la variable entre en la solución óptima.
- ¿Qué representa la 'holgura' en una restricción de tipo '≤' en programación lineal?
- La cantidad de recurso no utilizado en esa restricción.
- ¿Qué representa la variable de 'excedente' en una restricción de tipo '≥' en programación lineal?
- La cantidad en que se excede el mínimo requerido en esa restricción.
- ¿Qué significa que una restricción tenga una holgura de cero?
- Que el recurso correspondiente a esa restricción está completamente utilizado.
Preguntas tipo test
- ¿Qué representa el coste reducido de una variable de decisión con valor 0 en la solución óptima?
- a) El valor actual del coeficiente de la función objetivo.
- b) La cantidad en que debe mejorar el coeficiente de la función objetivo para que la variable asuma un valor positivo.
- c) El coste de producción de la variable.
- d) La diferencia entre el coste máximo y mínimo de la variable.
Respuesta: b) La cantidad en que debe mejorar el coeficiente de la función objetivo para que la variable asuma un valor positivo.. El coste reducido indica cuánto debe mejorar el coeficiente de la función objetivo para que la variable, actualmente con valor 0, pueda tener un valor positivo en la solución óptima.
- En un problema de programación lineal, ¿qué ocurre con el coste reducido de una variable de decisión si su valor es mayor que 0 en la solución óptima?
- a) Siempre es positivo.
- b) Siempre es negativo.
- c) Siempre es igual a 1.
- d) Siempre es igual a 0.
Respuesta: d) Siempre es igual a 0.. Si una variable de decisión tiene un valor mayor que 0 en la solución óptima, su coste reducido es 0, lo que indica que ya está contribuyendo de manera óptima a la función objetivo.
- ¿Cuál de las siguientes opciones describe mejor el concepto de 'holgura' en programación lineal?
- a) La cantidad de recurso no utilizado en una restricción de 'mayor o igual que'.
- b) La cantidad en que la función objetivo puede ser mejorada.
- c) La diferencia entre el lado izquierdo y el lado derecho de una restricción de 'menor o igual que'.
- d) El número de variables en el problema de programación lineal.
Respuesta: c) La diferencia entre el lado izquierdo y el lado derecho de una restricción de 'menor o igual que'.. La holgura representa la diferencia entre los lados izquierdo y derecho en una restricción de 'menor o igual que', indicando la cantidad de recurso que no se está utilizando completamente.
13. Ejemplo 2: Un Problema de Minimización Simple
Flashcards
- ¿Qué se busca en un problema de minimización simple?
- Encontrar la solución que minimice una cantidad, respetando ciertas restricciones.
- ¿Qué son las restricciones en un problema de minimización?
- Son limitaciones que definen los valores mínimos que deben satisfacer las variables de decisión.
- ¿Qué tipo de funciones se utilizan en la programación lineal?
- Funciones lineales.
- ¿Qué significa que una solución sea 'viable' en un problema de minimización?
- Que satisface todas las restricciones del problema.
Preguntas tipo test
- ¿Cuál es el objetivo principal en un problema de minimización simple dentro de la programación lineal?
- a) Maximizar los costos de producción.
- b) Minimizar los recursos utilizados.
- c) Encontrar el punto de equilibrio.
- d) Aumentar la demanda del producto.
Respuesta: b) Minimizar los recursos utilizados.. En un problema de minimización simple, el objetivo principal es encontrar la solución que utilice la menor cantidad de recursos posible, cumpliendo con todas las restricciones dadas.
- En un problema de minimización, ¿qué representan las restricciones?
- a) Los costos máximos permitidos.
- b) Los límites mínimos que deben cumplirse.
- c) Las ganancias esperadas.
- d) La cantidad de productos a vender.
Respuesta: b) Los límites mínimos que deben cumplirse.. Las restricciones en un problema de minimización representan los límites mínimos que deben satisfacerse para que la solución sea viable. Estas aseguran que se cumplan ciertos requisitos mínimos.
- ¿Qué tipo de funciones se utilizan en un problema de programación lineal?
- a) Funciones exponenciales.
- b) Funciones logarítmicas.
- c) Funciones cuadráticas.
- d) Funciones lineales.
Respuesta: d) Funciones lineales.. La programación lineal se basa en el uso de funciones lineales tanto para la función objetivo como para las restricciones. Estas funciones permiten modelar relaciones proporcionales entre las variables.
14. Ejemplo 2: Solución Gráfica
Flashcards
- ¿Qué significa 'programación' en programación lineal?
- Elegir un curso de acción.
- ¿Qué es una solución viable en programación lineal?
- Una solución que satisface todas las restricciones del problema.
- ¿Qué son las restricciones lineales?
- Funciones lineales restringidas a ser 'menores o iguales', 'iguales' o 'mayores o iguales' a una constante.
- ¿Qué representan los puntos extremos de la región factible?
- Las esquinas o vértices de la región factible.
Preguntas tipo test
- ¿Cuál es el objetivo principal de los problemas de programación lineal?
- a) Maximizar o minimizar una cantidad.
- b) Encontrar soluciones informáticas.
- c) Formular problemas matemáticos complejos.
- d) Dibujar gráficos de restricciones.
Respuesta: a) Maximizar o minimizar una cantidad.. El objetivo principal de la programación lineal es encontrar el valor máximo o mínimo de una función objetivo, lo cual implica maximizar ganancias o minimizar costos, respectivamente.
- ¿Qué tipo de funciones se utilizan en un problema de programación lineal?
- a) Funciones exponenciales.
- b) Funciones cuadráticas.
- c) Funciones lineales.
- d) Funciones logarítmicas.
Respuesta: c) Funciones lineales.. La programación lineal se basa en el uso de funciones lineales, donde las variables aparecen en términos separados elevados a la primera potencia y multiplicados por constantes.
- ¿Qué representa una solución viable en un problema de programación lineal?
- a) Una solución que maximiza la función objetivo.
- b) Una solución que minimiza la función objetivo.
- c) Una solución que satisface todas las restricciones del problema.
- d) Una solución que viola al menos una restricción.
Respuesta: c) Una solución que satisface todas las restricciones del problema.. Una solución viable es aquella que cumple con todas las condiciones y limitaciones establecidas por las restricciones del problema, asegurando que sea factible.
15. Ejemplo 2: Variables Excedentes
Flashcards
- ¿Qué son las variables excedentes?
- Variables que se restan de las restricciones 'mayor o igual que' para convertirlas en igualdades.
- ¿Cuál es el coeficiente de las variables excedentes en la función objetivo?
- Cero.
- ¿Qué tipo de restricciones usan variables excedentes?
- Restricciones del tipo 'mayor o igual que'.
- ¿Qué indica un valor positivo de una variable excedente en la solución óptima?
- Que la restricción se cumple holgadamente.
Preguntas tipo test
- ¿Qué representan las variables excedentes en programación lineal?
- a) La cantidad en que se excede una restricción de 'menor o igual que'.
- b) La diferencia entre el lado izquierdo y derecho de una restricción de 'mayor o igual que'.
- c) La cantidad de recursos no utilizados en una solución.
- d) Un ajuste en la función objetivo para optimizar la solución.
Respuesta: b) La diferencia entre el lado izquierdo y derecho de una restricción de 'mayor o igual que'.. Las variables excedentes representan la diferencia entre los lados izquierdo y derecho de las restricciones de 'mayor o igual que', indicando cuánto se excede el mínimo requerido.
- En un problema de minimización, ¿cómo se incorporan las variables excedentes en la función objetivo?
- a) Se suman con un coeficiente positivo.
- b) Se restan con un coeficiente positivo.
- c) Se suman con un coeficiente de cero.
- d) Se restan con un coeficiente de cero.
Respuesta: c) Se suman con un coeficiente de cero.. Las variables excedentes se añaden a la función objetivo con un coeficiente de cero, lo que significa que no contribuyen al valor de la función objetivo, pero ayudan a convertir la desigualdad en una igualdad.
- Al convertir un problema de programación lineal a su forma estándar, ¿cuál es el propósito de restar variables excedentes?
- a) Asegurar que todas las variables sean no negativas.
- b) Convertir las desigualdades 'mayor o igual que' en igualdades.
- c) Simplificar la función objetivo.
- d) Encontrar una solución factible inicial.
Respuesta: b) Convertir las desigualdades 'mayor o igual que' en igualdades.. Restar variables excedentes de las restricciones 'mayor o igual que' permite transformar estas desigualdades en igualdades, lo cual es un requisito para que el problema esté en su forma estándar.
16. Región Factible
Flashcards
- ¿Qué es una región factible?
- El conjunto de todos los puntos que satisfacen todas las restricciones de un problema de programación lineal.
- ¿Dónde se encuentra la solución óptima en un problema de programación lineal?
- En un punto extremo de la región factible.
- ¿Qué significa que un problema de programación lineal sea inviable?
- Que no existe ninguna solución que satisfaga todas las restricciones.
- ¿Qué tipo de funciones se utilizan en un problema de programación lineal?
- Funciones lineales.
Preguntas tipo test
- ¿Qué define una solución factible en programación lineal?
- a) Una solución que maximiza la función objetivo.
- b) Una solución que minimiza la función objetivo.
- c) Una solución que satisface todas las restricciones del problema.
- d) Una solución que viola al menos una restricción.
Respuesta: c) Una solución que satisface todas las restricciones del problema.. Una solución factible es aquella que cumple con todas las restricciones establecidas en el problema de programación lineal, representando un punto válido dentro del espacio de soluciones posibles.
- ¿Qué término describe las esquinas o vértices de la región factible en programación lineal?
- a) Puntos de inflexión.
- b) Puntos extremos.
- c) Puntos críticos.
- d) Puntos de Lagrange.
Respuesta: b) Puntos extremos.. Los puntos extremos son las esquinas o vértices de la región factible, y son importantes porque la solución óptima se encuentra en uno de estos puntos.
- En la formulación de un problema de programación lineal, ¿qué rol juegan las variables de decisión?
- a) Representan las restricciones del problema.
- b) Definen el objetivo que se busca optimizar.
- c) Son los parámetros que no se pueden cambiar.
- d) Representan las cantidades que se pueden controlar para alcanzar el objetivo.
Respuesta: d) Representan las cantidades que se pueden controlar para alcanzar el objetivo.. Las variables de decisión representan las cantidades que la persona que toma las decisiones puede controlar y ajustar para alcanzar el objetivo deseado, respetando las restricciones del problema.
17. Casos Especiales
Flashcards
- ¿Qué son las soluciones óptimas alternativas?
- Múltiples soluciones que dan el mismo valor óptimo para la función objetivo.
- ¿Qué es la inviabilidad en programación lineal?
- Situación donde no existe una solución que satisfaga todas las restricciones.
- ¿Qué es un problema ilimitado en programación lineal?
- Un problema donde la función objetivo puede crecer indefinidamente sin violar las restricciones.
- ¿Qué indica una región factible ilimitada?
- La región factible se extiende sin límite en alguna dirección.
Preguntas tipo test
- ¿Qué ocurre si la línea de la función objetivo es paralela a una restricción límite en la dirección de la optimización?
- a) No existen soluciones óptimas.
- b) Existe una única solución óptima.
- c) Existen soluciones óptimas alternativas.
- d) El problema es inviable.
Respuesta: c) Existen soluciones óptimas alternativas.. Cuando la línea de la función objetivo es paralela a una restricción límite, todos los puntos en ese segmento de línea son soluciones óptimas alternativas.
- ¿Cuál de las siguientes NO es una causa común de inviabilidad en un problema de programación lineal?
- a) Un error en la formulación del problema.
- b) Expectativas demasiado altas.
- c) Demasiadas restricciones impuestas al problema.
- d) Una función objetivo mal definida.
Respuesta: d) Una función objetivo mal definida.. Las causas comunes de inviabilidad incluyen errores de formulación, expectativas poco realistas y un problema sobreconstraído. Una función objetivo mal definida no causa inviabilidad, sino que dificulta la optimización.
- ¿Qué significa que un problema de programación lineal sea 'ilimitado'?
- a) El problema tiene infinitas restricciones.
- b) El valor de la solución puede hacerse indefinidamente grande sin violar las restricciones.
- c) El problema no tiene solución factible.
- d) El problema tiene múltiples soluciones óptimas.
Respuesta: b) El valor de la solución puede hacerse indefinidamente grande sin violar las restricciones.. Un problema ilimitado significa que la función objetivo puede crecer indefinidamente sin violar las restricciones, lo que indica una formulación inadecuada del problema.
Y 17 flashcards y 34 preguntas más en el documento.
Texto del documento
Diapositivas de John Loucks Universidad de St. Edward © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados. Queda Queda prohibido prohibido escanear, escanear, copiar copiar o o duplicar duplicar estas estas diapositivas, diapositivas, así así como como publicarlas publicarlas en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 1 1 Suscríbete a DeepL Pro para poder traducir archivos de mayor tamaño. Más información disponible en www.DeepL.com/pro.
Capítulo Capítulo 2 2 Introducción Introducción a a l la a p pr ro og gr ra am ma ac ci ió ón n lineal lineal n n P Pr ro ob bl le em ma a de de programación programación lineal lineal n n F Fo or rm mu ul la ac ci ió ón n del del problema problema n n Un Un p pr ro ob bl le em ma a simple simple de de maximización maximización n n P Pr ro oc ce ed di im mi ie en nt to o d de e solución solución gráfica gráfica n n Puntos Puntos extremos extremos y y s so ol lu uc ci ió ón n óptima óptima n n S So ol lu uc ci io on ne es s informáticas informáticas n n Un Un p pr ro ob bl le em ma a d de e minimización minimización simple simple n n C Ca as so os s especiales especiales © © 2011 2011 Cengage Cengage Learning.
Learning. Todos Todos los los derechos derechos reservados. reservados. No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 2 2 P Pr ro og gr ra am ma ac ci ió ón n lineal lineal n n La La programación programación lineal lineal no no tiene tiene nada nada que que ver ver con con la la programación programación informática. informática.
n n El El uso uso de de la la palabra palabra «programación» «programación» aquí aquí significa significa «elegir «elegir un un curso curso de de acción». acción». n n La La programación programación lineal lineal implica implica elegir elegir un un curso curso de de acción acción cuando cuando el el modelo modelo matemático matemático del del problema problema contiene contiene solo solo funciones funciones lineales. lineales. © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 3 3 P Pr ro ob bl le em ma a de de programación programación lineal lineal (LP) (LP) n n La La maximización maximización o o minimización minimización de de alguna alguna cantidad cantidad es es el el objetivo objetivo de de todos todos los los problemas problemas de de programación programación lineal. lineal.
n n Todos Todos los los problemas problemas de de PL PL tienen tienen restricciones restricciones que que limitan limitan el el grado grado en en que que se se puede puede perseguir perseguir el el objetivo. objetivo. n n Una Una solución solución viable viable satisface satisface todas todas las las r re es st tr ri ic cc ci io on ne es s del del problema problema. . n n Una Una solución solución óptima óptima es es una una solución solución viable viable que que da da como como resultado resultado el el mayor mayor valor valor posible posible de de la la función función objetivo objetivo al al maximizarla maximizarla (o (o el el menor menor al al minimizarla). minimizarla).
n n Se Se puede puede utilizar utilizar un un método método de de solución solución gráfica gráfica para para resolver resolver un un programa programa lineal lineal con con dos dos variables. variables. © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados. No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 4 4 P Pr ro ob bl le em ma a de de programación programación lineal lineal (LP) (LP) n n Si Si tanto tanto la la función función objetivo objetivo como como las las restricciones restricciones son son lineales, lineales, el el problema problema se se denomina denomina problema problema de de programación programación lineal. lineal.
n n Las Las funciones funciones lineales lineales son son funciones funciones en en las las que que cada cada variable variable aparece aparece en en un un término término separado separado elevado elevado a a la la primera primera potencia potencia y y se se multiplica multiplica por por una una constante constante (que (que podría podría ser ser 0). 0). n n Las Las restricciones restricciones lineales lineales son son funciones funciones lineales lineales que que están están restringidas restringidas a a ser ser «menores «menores o o iguales», iguales», «iguales» «iguales» o o «mayores «mayores o o iguales» iguales» a a una una constante. constante. © © 2011 2011 Cengage Cengage Learning.
Learning. Todos Todos los los derechos derechos reservados. reservados. No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 5 5 F Fo or rm mu ul la ac ci ió ón n del del problema problema n n La La formulación formulación o o modelización modelización de de problemas problemas es es el el proceso proceso de de traducir traducir una una expresión expresión verbal verbal de de un un problema problema en en una una expresión expresión matemática. matemática.
n n La La formulación formulación de de modelos modelos es es un un arte arte que que solo solo se se puede puede dominar dominar con con la la práctica práctica y y la la experiencia. experiencia. n n Todos Todos los los problemas problemas de de LP LP tienen tienen algunas algunas características características únicas, únicas, pero pero la la mayoría mayoría de de ellos ellos también también tienen tienen características características comunes. comunes. n n Las Las pautas pautas generales generales para para la la formulación formulación de de modelos modelos LP LP se se ilustran ilustran en en las las diapositivas diapositivas siguientes. siguientes.
© © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados. No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en un sitio sitio web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 6 6 Directrices Directrices para para l la a f fo or rm mu ul la ac ci ió ón n de de modelos modelos n n Comprender Comprender el el problema problema a a f fo on nd do o. . n n Describir Describir el el o ob bj je et ti iv vo o. . n n Describa Describa cada cada r re es st tr ri ic cc ci ió ón n. .
n n Defina Defina las las v va ar ri ia ab bl le es s de de decisión decisión. . n n Escriba Escriba el el objetivo objetivo en en términos términos de de las las v va ar ri ia ab bl le es s de de decisión decisión. . n n Escriba Escriba las las restricciones restricciones en en términos términos de de las las v va ar ri ia ab bl le es s de de decisión decisión. . © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en un sitio sitio web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 7 7 Ejemplo Ejemplo 1: 1: un un p pr ro ob bl le em ma a de de maximización maximización simple simple n n F Fo or rm mu ul la ac ci ió ón n LP LP M Ma ax x 5 5x x1 1 + + 7 7x x( (2 2) ) F Fu un nc ci ió ón n o ob bj je et ti iv vo o s s. .t t. .
x x1 1 < < 6 2x 2x( (1) 1) + + 3x 3x( (2) 2) < < 19 19 x( (1) 1) + + x ( (2) 2) < < 8 8 x x1 1 > > 0 0 y y x x2 2 > > 0 0 R Re es st tr ri ic cc ci io on ne es s « «n no or rm ma al le es s» » R Re es st tr ri ic cc ci io on ne es s d de e n no o n ne eg ga at ti iv vi id da ad d © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados. No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en un sitio sitio web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 8 8 Ejemplo Ejemplo 1: 1: S So ol lu uc ci ió ón n gráfica gráfica n n Primera Primera restricción restricción r re ep pr re es se en nt ta ad da a g gr rá áf fi ic ca am me en nt te e x x2 2 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 x x1 1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados. Queda Queda prohibido prohibido escanear, escanear, copiar copiar o o duplicar duplicar este este material, material, así así como como publicarlo publicarlo en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte.
parte. Diapositiva Diapositiva 9 9 x1 = 6 La zona sombreada contiene todos los puntos factibles para esta restricción (6, 0) Ejemplo Ejemplo 1: 1: S So ol lu uc ci ió ón n gráfica gráfica n n Segunda Segunda restricción restricción r re ep pr re es se en nt ta ad da a g gr rá áf fi ic ca am me en nt te e x x2 2 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 (9 (9 1/2 1/2, , 0 0) ) x x1 1 © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
Queda Queda prohibido prohibido escanear, escanear, copiar copiar o o duplicar duplicar este este material, material, así así como como publicarlo publicarlo en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 1 10 0 (0, 6 1/3) 2x1+ 3x2= 19 La zona sombreada contiene todos los puntos factibles para esta restricción Ejemplo Ejemplo 1: 1: S So ol lu uc ci ió ón n gráfica gráfica n n Tercera Tercera restricción restricción r re ep pr re es se en nt ta ad da a g gr rá áf fi ic ca am me en nt te e x x2 2 (0, (0, 8 8) ) 8 8 7 7 6 6 5 5 4 4 3 3 L La a r re eg gi ió ón n s so om mb br re ea ad da a región región c co on nt ti ie en ne e x x1 1+ + x x2 2 = = 8 8 2 2 todos todos l lo os s p pu un nt to os s factibles factibles 1 1 para para esta esta r re es st tr ri ic cc ci ió ón n (8, (8, 0 0) ) x x1 1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 © © 2011 2011 Cengage Cengage Learning.
Learning. Todos Todos los los derechos derechos reservados. reservados. Queda Queda prohibido prohibido escanear, escanear, copiar copiar o o duplicar duplicar este este material, material, así así como como publicarlo publicarlo en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 1 11 1 8 7 6 5 4 3 2 1 x1+ x2 = 8 x1 = 6 Región factible 2x + 3x 1 2 Ejemplo Ejemplo 1: 1: S So ol lu uc ci ió ón n gráfica gráfica n n Gráfico Gráfico de de restricciones restricciones combinadas combinadas que que muestra muestra l la a r re eg gi ió ón n factible factible x x2 2 = = 1 19 9 x x1 1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
Queda Queda prohibido prohibido escanear, escanear, copiar copiar o o duplicar duplicar este este material, material, así así como como publicarlo publicarlo en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 1 12 2 Ejemplo Ejemplo 1: 1: S So ol lu uc ci ió ón n gráfica gráfica n n Función Función objetivo objetivo L Lí ín ne ea a x x2 2 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 x x1 1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
Queda Queda prohibido prohibido escanear, escanear, copiar copiar o o duplicar duplicar este este material, material, así así como como publicarlo publicarlo en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 1 13 3 (0, 5) Función objetivo 5x1+ 7x2= 35 (7, 0) Ejemplo Ejemplo 1: 1: S So ol lu uc ci ió ón n gráfica gráfica n n L Lí ín ne ea as s de de función función objetivo objetivo seleccionadas seleccionadas x x2 2 8 8 7 7 5 5x x 6 6 5 5 4 4 3 3 2 2 1 1 + + 7 7x x( (2 2) ) = = 3 35 5 5x 5x1 1 + + 7x 7x2 2 = = 3 39 9 5x 5x1 1 + + 7x 7x2 2 = = 4 42 2 x x1 1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
Queda Queda prohibido prohibido escanear, escanear, copiar copiar o o duplicar duplicar este este material, material, así así como como publicarlo publicarlo en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 1 14 4 1 Ejemplo Ejemplo 1: 1: S So ol lu uc ci ió ón n gráfica gráfica n n S So ol lu uc ci ió ón n óptima óptima x x 2 2 M Má áx xi im mo o 8 8 Función Función objetivo objetivo Línea Línea 5x 5x1 1 + + 7x 7x2 2 = = 46 46 7 7 6 6 S So ol lu uc ci ió ón n óptima óptima 5 5 ( (x x1 1= = 5, 5, x x2 2= = 3 3) ) 4 4 3 3 2 2 1 1 x x1 1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
Queda Queda prohibido prohibido escanear, escanear, copiar copiar o o duplicar duplicar este este material, material, así así como como publicarlo publicarlo en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 1 15 5 Resumen Resumen del del procedimiento procedimiento de de solución solución gráfica gráfica para para problemas problemas de de maximización maximización n n Prepare Prepare un un gráfico gráfico de de las las soluciones soluciones viables viables para para cada cada una una de de las las restricciones. restricciones.
n n Determine Determine la la región región factible factible que que satisfaga satisfaga todas todas las las restricciones restricciones simultáneamente. simultáneamente. n n Dibuje Dibuje una una l lí ín ne ea a de de función función objetivo objetivo. . n n Mueva Mueva las las líneas líneas de de función función objetivo objetivo paralelas paralelas hacia hacia valores valores de de función función objetivo objetivo más más grandes grandes sin sin salir salir completamente completamente de de la la región región factible. factible.
n n Cualquier Cualquier solución solución factible factible en en la la línea línea de de la la función función objetivo objetivo con con el el valor valor más más grande grande es es una una solución solución óptima. óptima. © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados. No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en un sitio sitio web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 1 16 6 V Va ar ri ia ab bl le es s de de holgura holgura y y excedente excedente n n Un Un programa programa lineal lineal en en el el que que todas todas las las variables variables son son no no negativas negativas y y todas todas las las restricciones restricciones son son igualdades igualdades se se dice dice que que está está en en forma forma estándar. estándar.
n n La La forma forma estándar estándar se se obtiene obtiene añadiendo añadiendo variables variables de de holgura holgura a a las las restricciones restricciones «menor «menor o o igual igual que» que» y y restando restando variables variables excedentes excedentes de de l la as s r re es st tr ri ic cc ci io on ne es s «mayor «mayor o o igual igual que que» ». . n n Las Las variables variables de de holgura holgura y y excedentes excedentes representan representan la la diferencia diferencia entre entre los los lados lados izquierdo izquierdo y y derecho derecho de de las las restricciones. restricciones.
n n Las Las variables variables de de holgura holgura y y excedente excedente tienen tienen coeficientes coeficientes de de función función objetivo objetivo iguales iguales a a 0. 0. © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados. Queda Queda prohibido prohibido escanear, escanear, copiar copiar o o duplicar duplicar este este material, material, así así como como publicarlo publicarlo en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 1 17 7 Variables Variables de de holgura holgura (para (para r re es st tr ri ic cc ci io on ne es s d de e «< < ») ) n n Ejemplo Ejemplo 1 1 en en f fo or rm ma a estándar estándar máximo máximo 5x 5x1 1+ + 7x 7x2 2+ + 0s 0s1 1+ + 0s 0s2 2+ + 0 0s s3 3 s s. .t t. . x x1 1 + + s ( (1) 1) = = 6 2x 2x( (1) 1)+ + 3x 3x( (2) 2) + + s ( (2) 2) = = 19 19 x( (1) 1) + + x ( (2) 2) + + s ( (3) 3) = = 8 8 s s1 1 , , s s2 2 y y s s3 3 son son v va ar ri ia ab bl le es s de de holgura holgura x x1 1 , , x x2 2 , , s s1 1 , , s s2 2 , , s s3 3 > > 0 0 © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
Queda Queda prohibido prohibido escanear, escanear, copiar copiar o o duplicar duplicar este este material, material, así así como como publicarlo publicarlo en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 1 18 8 V Va ar ri ia ab bl le es s de de holgura holgura n n S So ol lu uc ci ió ón n óptima óptima x x2 2 T Te er rc ce er ro o R Re es st tr ri ic cc ci ió ón n: : 8 8 x x1 1+ + x x2 2 = = 8 8 P Pr ri im me er ra a r re es st tr ri ic cc ci ió ón n: : 7 7 s s3 3 = = 0 0 6 6 5 5 4 4 x x1 1 = = 6 6 s s1 1 = = 1 1 S Se eg gu un nd do o 3 3 Ó Óp pt ti im mo o 2 2 S So ol lu uc ci ió ón n 1 1 ( (x x1 1= = 5, 5, x x2 2= = 3 3) ) R Re es st tr ri ic cc ci ió ón n: : 2x 2x1 1 + + 3x 3x2 2 = = 19 19 s s2 2 = = 0 0 x x1 1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
Queda Queda prohibido prohibido escanear, escanear, copiar copiar o o duplicar duplicar este este material, material, así así como como publicarlo publicarlo en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 1 19 9 Puntos Puntos extremos extremos y y la la s so ol lu uc ci ió ón n óptima óptima n n Las Las esquinas esquinas o o vértices vértices de de la la región región factible factible se se denominan denominan puntos puntos extremos. extremos.
n n Una Una solución solución óptima óptima a a un un problema problema LP LP se se puede puede encontrar encontrar en en un un punto punto extremo extremo de de la la región región factible. factible. n n Al Al buscar buscar la la solución solución óptima, óptima, no no es es necesario necesario evaluar evaluar todos todos los los puntos puntos de de solución solución factibles. factibles. n n Solo Solo hay hay que que tener tener en en cuenta cuenta los los puntos puntos extremos extremos de de la la región región factible. factible. © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
Queda Queda prohibido prohibido escanear, escanear, copiar copiar o o duplicar duplicar este este material, material, así así como como publicarlo publicarlo en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 2 20 0 Ejemplo Ejemplo 1: 1: P Pu un nt to os s extremos extremos x x2 2 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 x x1 1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
Queda Queda prohibido prohibido escanear, escanear, copiar copiar o o duplicar duplicar este este material, material, así así como como publicarlo publicarlo en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 2 21 1 5 (0, 6 1/3) 4 (5, 3) 1 Región factible (0, 0) 3 (6, 2) 2 (6, 0) S So ol lu uc ci io on ne es s informáticas informáticas n n Los Los problemas problemas de de optimización optimización lineal lineal que que implican implican miles miles de de variables variables y y miles miles de de restricciones restricciones ahora ahora se se resuelven resuelven de de forma forma rutinaria rutinaria con con p pa aq qu ue et te es s informáticos informáticos. .
n n Los Los solucionadores solucionadores de de programación programación lineal lineal forman forman parte parte ahora ahora de de muchos muchos paquetes paquetes de de hojas hojas de de cálculo, cálculo, como como Microsoft Microsoft Excel. Excel. n n Entre Entre los los paquetes paquetes comerciales comerciales más más destacados destacados se se incluyen incluyen CPLEX, CPLEX, LINGO, LINGO, MOSEK, MOSEK, Xpress-MP Xpress-MP y y Premium Premium Solver Solver for for E Ex xc ce el l. . © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
Queda Queda prohibido prohibido escanear, escanear, copiar copiar o o duplicar duplicar este este material, material, así así como como publicarlo publicarlo en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 2 22 2 Interpretación Interpretación de de l lo os s r re es su ul lt ta ad do os s del del ordenador ordenador n n En En este este capítulo capítulo analizaremos analizaremos los los siguientes siguientes r re es su ul lt ta ad do os s: : v va al lo or r d de e l la a f fu un nc ci ió ón n o ob bj je et ti iv vo o valores valores de de las las v va ar ri ia ab bl le es s de de decisión decisión c co os st te es s reducidos reducidos holgura holgura y y e ex xc ce ed de en nt te e n n En En el el siguiente siguiente capítulo capítulo analizaremos analizaremos cómo cómo una una solución solución óptima óptima se se ve ve afectada afectada por por un un cambio cambio en: en: un un coeficiente coeficiente de de la la f fu un nc ci ió ón n objetivo objetivo el el valor valor del del lado lado derecho derecho de de una una r re es st tr ri ic cc ci ió ón n © © 2011 2011 Cengage Cengage Learning.
Learning. Todos Todos los los derechos derechos reservados. reservados. No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en un sitio sitio web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 2 23 3 Ejemplo Ejemplo 1: 1: S So ol lu uc ci ió ón n con con hoja hoja de de cálculo cálculo n n Hoja Hoja de de cálculo cálculo parcial parcial que que muestra muestra l lo os s d da at to os s del del problema problema A B C D 1 Coeficientes LHS 2 Restricciones X1 X2 Valores RHS 3 #1 1 0 6 4 N.º 2 2 3 19 5 N.º 3 1 1 8 6 Coeficiente de función objetiva 5 7 © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
Queda Queda prohibido prohibido escanear, escanear, copiar copiar o o duplicar duplicar este este documento, documento, así así como como publicarlo publicarlo en en un sitio sitio web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 2 24 4 Ejemplo Ejemplo 1: 1: S So ol lu uc ci ió ón n con con hoja hoja de de cálculo cálculo n n Hoja Hoja de de cálculo cálculo parcial parcial que que muestra muestra l la a s so ol lu uc ci ió ón n A B C D 8 Valores óptimos de las variables de decisión 9 X1 X2 10 5,0 3,0 11 12 Función objetivo maximizada 46,0 13 14 Restricciones Cantidad utilizada Límites RHS 15 N.º 1 5 <= 6 16 N.º 2 19 <= 19 17 N.º 3 8 <= 8 © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 2 25 5 Ejemplo Ejemplo 1: 1: S So ol lu uc ci ió ón n con con hoja hoja de de cálculo cálculo n n Interpretación Interpretación de de los los resultados resultados del del ordenador ordenador En En la la diapositiva diapositiva anterior anterior vemos vemos que: que: © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 2 26 6 Valor de la función objetivo = 46 Variable de decisión n.º 1 (x1 ) = 5 Variable de decisión n.º 2 (x2 ) = 3 Holgura en la restricción n.º 1 = 6 – 5= 1 Holgura en la restricción n.º 2 = 19 – 19= 0 Holgura en la restricción n.º 3 = 8 – 8= 0 Reducción Reducción d de e c co os st te es s n n El El coste coste reducido reducido de de una una variable variable de de decisión decisión cuyo cuyo valor valor es es 0 0 en en la la solución solución óptima óptima es: es: La La cantidad cantidad en en que que tendría tendría que que mejorar mejorar el el coeficiente coeficiente de de la la función función objetivo objetivo de de la la variable variable (aumentar (aumentar para para los los problemas problemas de de maximización, maximización, disminuir disminuir para para los los problemas problemas de de minimización) minimización) antes antes de de que que esta esta variable variable pudiera pudiera asumir asumir un un valor valor positivo.
positivo. n n El El coste coste reducido reducido de de una una variable variable de de decisión decisión cuyo cuyo valor valor es> es> 0 0 en en la la solución solución óptima óptima es es 0. 0. © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados. No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en un sitio sitio web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 2 27 7 Ejemplo Ejemplo 1: 1: S So ol lu uc ci ió ón n con con hoja hoja de de cálculo cálculo n n Reducción Reducción d de e c co os st te es s Celdas ajustables Celda Nombre Final Valor Reducido Coste Objetivo Coeficiente Admisible Aumento Admisible disminución $B$8 X1 5,0 0,0 5 2 0,333333333 $C$8 X2 3,0 0 7 0,5 2 Restricciones Celda Final Nombre Valor Sombra Precio Restricción Lado derecho Permitido Aumento Permitido disminución $B$13 $B$14 $B$15 N.º 1 N.º 2 N.º 3 5 19 8 0 2 1 6 19 8 1E+30 5 0,333333333 1 1 1,666666667 © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 2 28 8 Min s.t. 5x1+ 2x2 2x1 + 5x2 4x(1) x(1) + x2 x2 > 10 > 12 > > 0 4 x1 , x2 Ejemplo Ejemplo 2: 2: Un Un p pr ro ob bl le em ma a de de minimización minimización simple simple n n F Fo or rm mu ul la ac ci ió ón n LP LP © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 2 29 9 Ejemplo Ejemplo 2: 2: S So ol lu uc ci ió ón n gráfica gráfica n n Representar Representar gráficamente gráficamente las las r re es st tr ri ic cc ci io on ne es s Restricción Restricción 1: 1: Cuando Cuando x x1 1= = 0, 0, entonces entonces x x2 2= = 2; 2; cuando cuando x x2 2= = 0, 0, entonces entonces x x1 1= = 5. 5. Conecta Conecta (5,0) (5,0) y y (0,2). (0,2).
El El lado lado «>» «>» está está por por encima encima de de esta esta línea. línea. Restricción Restricción 2: 2: Cuando Cuando x x2 2= = 0, 0, entonces entonces x x1 1= = 3. 3. Pero Pero si si se se establece establece x x1 1 en en 0, 0, se se obtendrá obtendrá x x2 2 = = -12, -12, que que no no está está en en la la gráfica. gráfica. Por Por lo lo tanto, tanto, para para obtener obtener un un segundo segundo punto punto en en esta esta línea, línea, establezca establezca x x1 1 en en cualquier cualquier número número mayor mayor que que 3 3 y y resuelva resuelva para para x x2 2 : : cuando cuando x x1 1 = = 5, 5, entonces entonces x x2 2 = = 8. 8. Conecta Conecta (3,0) (3,0) y y (5,8).
(5,8). El El lado lado «>» «>» está está a a la la derecha. derecha. © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados. No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en un sitio sitio web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 3 30 0 Ejemplo Ejemplo 2: 2: S So ol lu uc ci ió ón n gráfica gráfica n n Representación Representación gráfica gráfica de de las las restricciones restricciones ( (c co on nt ti in nu ua ac ci ió ón n) ) Restricción Restricción 3: 3: Cuando Cuando x x1 1= = 0, 0, entonces entonces x x2 2= = 4; 4; cuando cuando x x2 2= = 0, 0, entonces entonces x x1 1= = 4. 4. Conecta Conecta (4,0) (4,0) y y (0,4). (0,4). El El lado lado «>» «>» está está por por encima encima de de esta esta línea. línea. © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en un sitio sitio web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 3 31 1 Ejemplo Ejemplo 2: 2: S So ol lu uc ci ió ón n gráfica gráfica n n Restricciones Restricciones r re ep pr re es se en nt ta ad da as s g gr rá áf fi ic ca am me en nt te e x x2 2 6 6 5 5 4 4 3 3 2 2 1 1 1 1 2 2 3 3 4 4 5 5 6 6 R Re eg gi ió ón n factible factible 4x 4x1 1 x x2 2 > > 1 12 2 x x1 1 + + x x2 2 > > 4 2x 2x( (1) 1) + + 5x 5x( (2) 2) > > 10 10 x x1 1 © © 2011 2011 Cengage Cengage Learning. Learning.
Todos Todos los los derechos derechos reservados. reservados. No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 3 32 2 Ejemplo Ejemplo 2: 2: S So ol lu uc ci ió ón n gráfica gráfica n n Representar Representar gráficamente gráficamente la la f fu un nc ci ió ón n objetivo objetivo Establezca Establezca la la función función objetivo objetivo igual igual a a una una constante constante arbitraria arbitraria e e e e (por (por ejemplo, ejemplo, 20) 20) y y represéntela represéntela gráficamente. gráficamente. Para Para 5x 5x1 1 + + 2x 2x2 2 = = 20, 20, cuando cuando x x1 1 = = 0, 0, entonces entonces x x2 2 = = 10; 10; cuando cuando x x2 2= = 0, 0, entonces entonces x x1 1 = = 4. 4. Conecta Conecta (4,0) (4,0) y y ( (0 0, ,1 10 0) ). .
n n Mover Mover la la línea línea de de la la función función objetivo objetivo hacia hacia la la optimización. optimización. Moverla Moverla en en la la dirección dirección que que reduzca reduzca su su valor valor (hacia (hacia abajo), abajo), ya ya que que estamos estamos minimizando, minimizando, hasta hasta que que toque toque l la a último último punto punto de de la la región región factible, factible, determinado determinado por por las las dos dos últimas últimas restricciones. restricciones. © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en un sitio sitio web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 3 33 3 Ejemplo Ejemplo 2: 2: S So ol lu uc ci ió ón n gráfica gráfica n n Función Función objetivo objetivo r re ep pr re es se en nt ta ad da a g gr rá áf fi ic ca am me en nt te e x x2 2 Min Min 5x 5x1 1+ + 2 2x x2 2 6 6 5 5 4x 4x1 1 x x2 2 > > 1 12 2 4 4 3 3 x x1 1 + + x x2 2 > > 4 4 2 2 2x 2x1 1 + + 5x 5x2 2 > > 1 10 0 1 1 x x1 1 1 1 2 2 3 3 4 4 5 5 6 6 © © 2011 2011 Cengage Cengage Learning. Learning.
Todos Todos los los derechos derechos reservados. reservados. No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 3 34 4 88/5 Ejemplo Ejemplo 2: 2: S So ol lu uc ci ió ón n gráfica gráfica n n Resuelva Resuelva el el punto punto extremo extremo en en la la intersección intersección de de las las dos dos restricciones restricciones vinculantes vinculantes 4x 4x1 1 - - x x2 2 = = 1 12 2 x x1 1+ + x x2 2 = = 4 4 Al Al sumar sumar estas estas dos dos ecuaciones ecuaciones s se e o ob bt ti ie en ne e: : 5x 5x1 1 = = 16 16 o o Sustituyendo Sustituyendo esto esto en en x x1 1 + + x x2 2 = = 4 4 se se obtiene: obtiene: n n Resuelve Resuelve el el valor valor óptimo óptimo de de la la función función objetivo objetivo 5x 5x1 1 + + 2x 2x2 2 = = 5(16/5)+ (16/5)+ 2(4/5) (4/5) = = © © 2011 2011 Cengage Cengage Learning.
Learning. Todos Todos los los derechos derechos reservados. reservados. No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 3 35 5 x2 = 4/5 x1 = 16/5 4x1 x2 > 12 x1 + x2 > 4 Solución óptima: x1 = 16/5, x2 = 4/5, 5x1 + 2x2 = 17,6 2x1 + 5x2 > 10 x1 Ejemplo Ejemplo 2: 2: S So ol lu uc ci ió ón n gráfica gráfica n n S So ol lu uc ci ió ón n óptima óptima x x2 2 6 6 5 5 4 4 3 3 2 2 1 1 1 1 2 2 3 3 4 4 5 5 6 6 © © 2011 2011 Cengage Cengage Learning. Learning.
Todos Todos los los derechos derechos reservados. reservados. No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 3 36 6 Resumen Resumen del del procedimiento procedimiento de de solución solución gráfica gráfica para para problemas problemas de de minimización minimización n n Prepare Prepare un un gráfico gráfico de de las las soluciones soluciones viables viables para para cada cada una una de de las las restricciones. restricciones.
n n Determine Determine la la región región factible factible que que satisfaga satisfaga todas todas las las restricciones restricciones simultáneamente. simultáneamente. n n Dibuje Dibuje una una l lí ín ne ea a de de función función objetivo objetivo. . n n Mueva Mueva las las líneas líneas de de la la función función objetivo objetivo paralelas paralelas hacia hacia valores valores más más pequeños pequeños de de la la función función objetivo objetivo sin sin salir salir completamente completamente de de la la región región factible. factible.
n n Cualquier Cualquier solución solución factible factible en en la la línea línea de de la la función función objetivo objetivo con con el el valor valor más más pequeño pequeño es es una una solución solución óptima. óptima. © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados. No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en un sitio sitio web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 3 37 7 V Va ar ri ia ab bl le es s excedentes excedentes n n Ejemplo Ejemplo 2 2 en en f fo or rm ma a estándar estándar M Mi in n 5x 5x1 1+ + 2x 2x2 2+ + 0s 0s1 1+ + 0s 0s2 2+ + 0 0s s3 3 s s. .t t. . 2x 2x1 1 + + 5x 5x2 2 s s1 1 = = 10 10 4x 4x( (1) 1) x x( (2 2) ) s ( (2 2) ) = = 1 12 2 x x1 1 + + x x2 2 s( (3 3) ) = = 4 4 s s1 1 , , s s2 2 y y s s3 3 son son variables variables excedentes excedentes x x1 1 , , x x2 2 , , s s1 1 , , s s2 2 , , s s3 3 > > 0 0 © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 3 38 8 Ejemplo Ejemplo 2: 2: S So ol lu uc ci ió ón n con con hoja hoja de de cálculo cálculo n n Hoja Hoja de de cálculo cálculo parcial parcial que que muestra muestra l la a s so ol lu uc ci ió ón n A B C D 9 Variables de decisión 10 X1 X2 11 Valores de variación 3,20 0,800 12 13 Función objetivo minimizada 17,600 14 15 Restricciones Cantidad utilizada Importe disponible 16 N.º 1 10,4 >= 10 17 N.º 2 12 >= 12 18 N.º 3 4 >= 4 © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 3 39 9 Ejemplo Ejemplo 2: 2: S So ol lu uc ci ió ón n con con hoja hoja de de cálculo cálculo n n Interpretación Interpretación de de los los resultados resultados del del ordenador ordenador En En la la diapositiva diapositiva anterior anterior vemos vemos que: que: V Va al lo or r d de e l la a f fu un nc ci ió ón n o ob bj je et ti iv vo o = = 1 17 7, ,6 6 Variable Variable de de decisión decisión n.º n.º 1 1 ( (x x1 1 ) ) = = 3 3, ,2 2 Variable Variable de de decisión decisión n.º n.º 2 2 ( (x x2 2 ) ) = = 0 0, ,8 8 Excedente Excedente en en la la restricción restricción n.
n.º º 1 1 = = 10, 10,4 10= = 0, ,4 4 Excedente Excedente en en la la restricción restricción n. n.º º 2 2 = = 12,0 12,0 12= 12= 0 0, ,0 0 Excedente Excedente en en la la restricción restricción n. n.º º 3 3 = = 4,0 4,0 4= 4= 0 0, ,0 0 © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados. Queda Queda prohibido prohibido escanear, escanear, copiar copiar o o duplicar duplicar este este documento, documento, así así como como publicarlo publicarlo en en un sitio sitio web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 4 40 0 R Re eg gi ió ón n factible factible n n La La región región factible factible para para un un problema problema LP LP de de dos dos variables variables puede puede ser ser inexistente, inexistente, un un punto punto único, único, una una línea, línea, un un polígono polígono o o un un área área ilimitada. ilimitada.
n n Cualquier Cualquier programa programa lineal lineal se se clasifica clasifica en en una una de de estas estas cuatro cuatro c ca at te eg go or rí ía as s: : es es i in nv vi ia ab bl le e tiene tiene una una s so ol lu uc ci ió ón n óptima óptima única única tiene tiene s so ol lu uc ci io on ne es s óptimas óptimas alternativas alternativas tiene tiene una una función función objetivo objetivo que que puede puede aumentarse aumentarse sin sin límite límite n n Una Una región región factible factible puede puede ser ser ilimitada ilimitada y, y, sin sin embargo, embargo, puede puede haber haber soluciones soluciones óptimas. óptimas.
Esto Esto es es habitual habitual en en los los problemas problemas de de minimización minimización y y es es posible posible en en los los problemas problemas de de maximización. maximización. © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados. No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en un sitio sitio web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 4 41 1 C Ca as so os s especiales especiales n n S So ol lu uc ci io on ne es s óptimas óptimas alternativas alternativas En En el el método método gráfico, gráfico, si si la la línea línea de de la la función función objetivo objetivo es es paralela paralela a a una una restricción restricción límite límite en en la la dirección dirección de de la la optimización, optimización, existen existen soluciones soluciones óptimas óptimas alternativas, alternativas, siendo siendo óptimos óptimos todos todos los los puntos puntos de de este este segmento segmento de de línea. línea. © © 2011 2011 Cengage Cengage Learning. Learning.
Todos Todos los los derechos derechos reservados. reservados. No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en un sitio sitio web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 4 42 2 Max s.t. 4x1 + 6x2 x1 2x1 + 3x2 < 6 x1 + x2 x1 > 0 y x2 < 18 < 7 > 0 Ejemplo: Ejemplo: S So ol lu uc ci io on ne es s óptimas óptimas alternativas alternativas n n Consideremos Consideremos el el siguiente siguiente p pr ro ob bl le em ma a LP LP. . © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 4 43 3 Ejemplo: Ejemplo: S So ol lu uc ci io on ne es s óptimas óptimas alternativas alternativas n n Restricción Restricción límite límite 2x 2x1 1 + + 3x 3x2 2 < < 18 18 y y la la función función objetivo objetivo Max Max 4x 4x1 1 + + 6x 6x2 2 son son paralelas. paralelas. Todos Todos los los puntos puntos del del segmento segmento de de línea línea A A – – B B son son soluciones soluciones óptimas. óptimas.
x x2 2 x x1 1 + + x x2 2 < < 7 7 7 7 6 6 A A Máximo Máximo 4x 4x1 1+ + 6 6x x2 2 5 5 4 4 B B x x1 1 < < 6 6 3 3 2x 2x1 1 + + 3x 3x2 2 < < 1 18 8 2 2 1 1 x x1 1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados. Queda Queda prohibido prohibido escanear, escanear, copiar copiar o o duplicar duplicar este este material, material, así así como como publicarlo publicarlo en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 4 44 4 C Ca as so os s especiales especiales n n I In nv vi ia ab bi il li id da ad d Ninguna Ninguna solución solución al al problema problema LP LP satisface satisface todas todas las las restricciones, restricciones, incluidas incluidas las las c co on nd di ic ci io on ne es s de de no no negatividad negatividad. . Gráficamente, Gráficamente, esto esto significa significa que que no no e ex xi is st te e una una región región factible factible. . Las Las causas causas i in nc cl lu uy ye en n: : Se Se ha ha c co om me et ti id do o un un error error de de formulación formulación. .
Las Las expectativas expectativas de de la la dirección dirección son son demasiado demasiado a al lt ta as s. . Se Se han han impuesto impuesto demasiadas demasiadas restricciones restricciones al al problema problema (es (es decir, decir, el el problema problema está está sobreconstraído). sobreconstraído). © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
Queda Queda prohibido prohibido escanear, escanear, copiar copiar o o duplicar duplicar este este material, material, así así como como publicarlo publicarlo en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 4 45 5 Max s.t. 2x1+ 6x2 4x1 + 3x2 < 12 2x1 + x2 x1 , x2 > 8 > 0 E Ej je em mp pl lo o: : P Pr ro ob bl le em ma a i in nv vi ia ab bl le e n n Consideremos Consideremos el el siguiente siguiente p pr ro ob bl le em ma a LP LP. . © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 4 46 6 E Ej je em mp pl lo o: : P Pr ro ob bl le em ma a i in nv vi ia ab bl le e n n No No hay hay puntos puntos que que satisfagan satisfagan ambas ambas restricciones, restricciones, por por lo lo que que no no hay hay región región factible factible (ni (ni solución solución factible). factible). x x2 2 1 10 0 8 8 6 6 4 4 2 2 x x1 1 2 2 4 4 6 6 8 8 1 10 0 © © 2011 2011 Cengage Cengage Learning. Learning.
Todos Todos los los derechos derechos reservados. reservados. No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 4 47 7 2x1+ x2 > 8 4x1 + 3x2 < 12 C Ca as so os s especiales especiales n n S Si in n l lí ím mi it te es s La La solución solución a a un un problema problema LP LP de de maximización maximización es es ilimitada ilimitada si si el el valor valor de de la la solución solución puede puede hacerse hacerse indefinidamente indefinidamente grande grande sin sin violar violar ninguna ninguna de de las las restricciones. restricciones. En En problemas problemas reales, reales, esto esto es es el el resultado resultado de de una una formulación formulación inadecuada. inadecuada.
(Es (Es muy muy probable probable que que se se haya haya omitido omitido inadvertidamente inadvertidamente una una restricción). restricción). © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados. No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en un sitio sitio web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 4 48 8 Max s.t.
4x1 + 5x2 x1 , x2 > 0 Ejemplo: Ejemplo: S So ol lu uc ci ió ón n sin sin límites límites n n Consideremos Consideremos el el siguiente siguiente p pr ro ob bl le em ma a LP LP. . x x(1 (1) + + x x2 2 > > 5 5 3x 3x(1 (1) + + x x2 2 > > 8 8 © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados. Queda Queda prohibido prohibido escanear, escanear, copiar copiar o o duplicar duplicar este este material, material, así así como como publicarlo publicarlo en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte.
Diapositiva Diapositiva 4 49 9 Ejemplo: Ejemplo: S So ol lu uc ci ió ón n ilimitada ilimitada n n La La región región factible factible es es ilimitada ilimitada y y la la línea línea de de la la función función objetivo objetivo se se puede puede desplazar desplazar hacia hacia fuera fuera desde desde el el origen origen sin sin límite, límite, aumentando aumentando infinitamente infinitamente la la f fu un nc ci ió ón n objetivo objetivo. . x x2 2 1 10 0 3x 3x1 1+ + x x2 2 > > 8 8 8 8 6 6 4 4 2 2 x x1 1+ + x x2 2 > > 5 5 x x1 1 2 2 4 4 6 6 8 8 1 10 0 © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
No No se se permite permite escanear, escanear, copiar, copiar, duplicar duplicar ni ni publicar publicar en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 5 50 0 M áx 4x1 + 5x 2 Fin Fin del del capítulo capítulo 2 2 © © 2011 2011 Cengage Cengage Learning. Learning. Todos Todos los los derechos derechos reservados. reservados.
Queda Queda prohibido prohibido escanear, escanear, copiar copiar o o duplicar duplicar este este material, material, así así como como publicarlo publicarlo en en sitios sitios web web de de acceso acceso público, público, ya ya sea sea en en su su totalidad totalidad o o en en parte. parte. Diapositiva Diapositiva 5 51 1