Programación Lineal Flashcards
Formulación de problemas (problema de asignación, problema de mezclas, etc.)
¿En que se basa la investigación de operaciones (IO)?
Determina la opción optima respecto a un problema de decisión que tiene restricción de recursos
¿Cuáles son algunos modelos matemáticos que existen en la investigación de operaciones (IO)?
programación lineal, programación dinámica, programación entera, programación no lineal
¿Qué se requiere para plantear un problema general de un modelo lineal?
1- Tener las variables de decisión, ¿Qué hacer?
2-Se requiere una función objetivo (Función lineal con variable)
3-Se necesitan conocer las restricciones (ecuaciones de desigualdad que limitan el valor de la función objetivo)
¿Qué es la proporcionalidad? (supuesto en la programación lineal)
Se refiere a cuando la contribución de la variable en la función objetivo es proporcional al nivel (valor) de esta variable
¿Qué es la aditividad? (supuesto en la programación lineal)
La función objetivo es la suma directa de las contribuciones individuales de las
variables. El lado izquierdo de cada restricción debe ser la suma de los usos
individuales de cada variable
¿Qué es la divisibilidad? (supuesto en la programación lineal)
Las variables de decisión pueden dividirse en cualquier nivel fraccional (entran valores no enteros)
¿Qué es la Certidumbre? (supuesto en la programación lineal)
Los coeficientes de costo, los coeficientes tecnológicos y los
recursos son todos conocidos de manera determinística.
¿Cuál es la funación objetivo del siguiente problema y las restricciones?
La Electrocomp Corporation fabrica dos productos eléctricos: acondicionadores de aire y grandes
ventiladores. El proceso de ensamble de cada uno es similar en el sentido que ambos requieren una
cierta cantidad de alambrado y taladrado. Cada acondicionador de aire requiere 3 horas de
alambrado y 2 de taladrado. Cada ventilador debe pasar por 2 horas de alambrado y 1 hora de
taladrado. Durante el siguiente periodo de producción, están disponibles 240 horas de tiempo de
alambrado y se pueden utilizar hasta 140 horas de tiempo de taladrado. Cada acondicionador de aire
vendido produce una ganancia de $25. Cada ventilador ensamblado puede ser vendido con una
ganancia de $15.
La administración de Electrocomp se percata de que no incluyó dos restricciones críticas. En
particular, la administración decide que para garantizar un suministro adecuado de acondicionadores
de aire de un contrato, se deben fabricar, por lo menos, 10 de estos aparatos. Como Electrocomp
incurrió en una sobreoferta de ventiladores en el periodo precedente, la administración también
insiste que no produzcan más de 80 ventiladores durante este periodo de producción.
Formule esta situación de mezcla de producción de programación lineal para encontrar la mejor
combinación de acondicionadores de aire y ventiladores que produzcan la ganancia máxima.
Max z
25 x + 15 y
s.a
3 xa + 2 xv ≤ 240
2 xa + xv ≤ 140
xa ≥ 10
xv ≤ 80
xa , xv ≥ 0
¿Qué es y como surgen los problemas de mezcla?
Surge cuando se debe decidir como mezclar dos o más recursos para producir productos. Se debe de decidir cuanto comprar para satisfacer el producto y demanda con un costo minimo.
¿Cuáles son algunas aplicaciones para la programación lineal?
-Planeación de capacidad
-Inventarios
-Administración de personal
-Administración de horarios
¿Qué es una programación de producción?
Es un problema de mezcla pero para periodos. Pues estos problemas se repiten (hay que hacerlos periódicamente). Aunque la demanda cambie las restricciones siguen constantes
¿En que consiste el problema del agente viajero?
Consiste en encontrar la ruta CERRADA más corta entre ciudades, la ciudad se visita solo una vez.
Método gráfico
Se refiere a un proceso gráfico cuando se tiene 2 a 3 variables, con el objetivo de encontrar una solución a una ecuación
Cuales son los pasos generales del método gráfico?
1-Graficar las restricciones
2-gráficar función objetivo y desplazar para maximizar o minimizar.
3-Encontrar valores óptimos para xi, y, z
Link para ver un ejercicio de método gráfico rápido
https://www.youtube.com/watch?v=ivOoBgSwdhA
Tipos de soluciones en el método gráfico
- Solución óptima única
- Solución óptima múltiple
- Solución no acotada
- Solución no factible
Características del formato estándar en modelo de programación lineal
Formato estándar.
1. Todas las restricciones son ecuaciones (igualdades)
2. Todas las variables son no negativas
3. La función objetivo puede ser la maximización o la
minimización.
Características del formato canónico en modelo de programación lineal
- Las restricciones son desigualdades (≥ en
minimización y ≤ en maximización). - Todas las variables son no negativas
- La función objetivo puede ser la
maximización o la minimización
Cuál es el paso indispensable para pasar de desigualdad (≥, ≤) a ecuación (=)
Si la restricción es:
x1 + 2x2 ≤ 6 Sumamos la variable de holgura s1 ≥ 0 al primer miembro para obtener
x1 + 2x2 + s1 = 6, s1 ≥ 0
Si la restricción es:
3x1 + 2x2 -3x3 ≥ 5 Restamos una variable de exceso s2 ≥ 0 al primer miembro para obtener
3x1 + 2x2 -3x3 – s2 = 5, s2 ≥ 0
Cuál es el paso indispensable para pasar de ecuación (=) a desigualdad (≥, ≤)
Cada ecuación se convierte en dos desigualdades (una con ≥, la otra con ≤)
Posteriormente, multiplicar una de esas ecuaciones por -1 para cambiar el sentido de la
desigualdad, de manera que si el problema es de minimización tenga restricciones de
tipo ≥, y si es un problema de maximización tenga restricciones de tipo ≤
Pasos para realizar el método simplex matricial
- Pasar a formato estándar (y posteriormente expresar en notación matricial).
- Dar una solución inicial básica factible (usualmente, con las holguras).
- ¿Es óptima? (Si sí, parar; si no, pasar al paso 4).
- Escoger la variable de entrada (¿Cuál entra a la base?)
- Escoger la variable de salida (¿Cuál sale de la base?)
- Con la nueva base, calcular XB y z.
- Regresar al paso 3: ¿Es óptima?
https://youtu.be/ktZzkXssxAo?si=9mZXlID3QBsMhCtM
Método simplex tabular (caracteristicas)
1- Pasar las ecuaciones a formato estandar
2-Crear una tabla de x, z y s (condiciones). Los valores de la función objetivo pasan en la tabla al signo contrario.
3-Seleccionar el coeficiente que sale depende si queremos maximizar o minimizar.
4-dividir los valores de las ecuaciones entre la fila donde se encuentra el coeficiente que sale.
5-Pasar los valores cuidando siempre hacer 0 los valores de la pibote hasta que queden o otros positivos o neg
Si es minimizar la funcion cambia signos
https://youtu.be/CCud7rAIi8A?si=9JeJKbT0gvO_1ltn
¿Cuál es la definición de grafo en asignación y transporte?
Conjunto de Nodos o vértices unidos por aristas
¿Cuál es la definición de subgrafo en asignación y transporte?
subconjunto de Nodos y aristas de grafo final
¿Qué es un Grafo dirigido?
Aristas que describen sentido direccional
Tipos de clasificación sencilla en rutas
Caminos
Cadena
Circuito
Ciclo
Árbol
¿Cuál es el método de la gran M?
Inicia cuando una programación lineal está en forma canónica, al pasar las funciones a formato estándar si tenemos = o => se deben de agregar variables artificiales (A) y existe una regla de penalización -M en minimización y M en maximización.
https://youtu.be/bsBWhOPVcdg?si=AcZhyzGu4oweUj9Q
