1. 2.2 Método gráfico.
1.1. El método gráfico es un procedimiento de solución de problemas de programación lineal
1.1.1. Consiste en representar cada una de las restricciones y encontrar en la medida de lo posible el polígono (poliedro) factible
1.2. Muy limitado en cuanto al número de variables
1.3. Muy rico en materia de interpretación de resultados e incluso análisis de sensibilidad
1.4. El método gráfico se emplea para resolver problemas que presentan sólo 2 variables de decisión. El procedimiento consiste en trazar las ecuaciones de las restricciones en un eje de coordenadas X1, X2 para tratar de identificar el área de soluciones factibles (soluciones que cumplen con todas las restricciones).
1.4.1. La solución óptima del problema se encuentra en uno de los vértices de esta área de soluciones creada, por lo que se buscará en estos datos el valor mínimo o máximo del problema
2. 2.1 Formulación y aplicación de modelos de programación lineal.
2.1. Variables de decisión y parámetros
2.1.1. x1 , x2
2.2. Función Objetivo
2.2.1. relación matemática
2.2.1.1. Entre las variables de decisión, parámetros y una magnitud que representa el objetivo o producto del sistema
2.3. Restricciones
2.3.1. Relaciones entre las variables de decisión y los recursos disponibles
2.4. Maximización
2.4.1. Utilidades, producción, ventas, beneficios, rentabilidad
2.5. Minimización
2.5.1. Costos, pérdidas, paradas, desperdicios, distancias
3. 2.5 Método dual-simplex
3.1. En particular este método se puede utilizar cuando luego de llevar a la forma estándar un modelo de Programación Lineal no se dispone de una solución básica factible inicial con la cual se pueda dar inicio a las iteraciones del algoritmo.
3.1.1. Alternativamente podríamos definir el modelo dual al problema propuesto y resolverlo por el Método Simplex para posteriormente utilizar las condiciones del Teorema de Holguras Complementarias.
3.2. Para llevar el problema anterior a la forma estándar se requiere agregar 2 variables de exceso no negativas para la restricción 1 y 2, que llamaremos respectivamente X4 y X5
3.2.1. Cabe destacar que el Método Simplex Dual que no es la única alternativa algorítmica a la cual podemos recurrir para resolver el problema propuesto. Por ejemplo, podríamos haber alcanzado idénticos resultados aplicando el Método Simplex de 2 Fases con algo más de trabajo.
3.3. Antes de ello es necesario disponer de una solución básica factible inicial.
3.3.1. En este contexto si quisiéramos usar X4 y X5 como variables básicas (y en consecuencia X1, X2 y X3 como variables no básicas) se requiere que X4 y X5 sean mayores o iguales a cero, sin embargo, sus coeficientes en las respectivas filas son negativos y por tanto no se dispone de la identidad (matriz con “1” como diagonal y el resto de coeficientes igual a cero).
3.3.2. Sin embargo, en esta instancia podemos aplicar el Método Simplex Dual como alternativa de resolución. Para ello seleccionaremos una variable que deje la base y adoptaremos como criterio de selección aquella variable básica asociada al lado derecho “más negativo” (con esto se busca favorecer la rapidez de convergencia).
3.4. En resumen ante un modelo de optimización contamos con varias alternativas de resolución y es deber de quien resuelve evaluar los distintos caminos en términos de su complejidad y representación.
4. 2.4 Método dual.
4.1. Consiste en una instancia alternativa de modelamiento matemático que nos permite rescatar la información del problema original conocido comúnmente como modelo primal
4.1.1. Primal Minimización – Dual Maximización
4.1.2. Si el problema primal es de minimización, entonces su correspondiente dual será uno de maximización.
4.1.3. Si el problema primal tiene una restricción del tipo >=, la variable dual asociada a dicha restricción debe ser >=0.
4.1.4. Si el problema primal tiene una restricción del tipo <=, la variable dual asociada a dicha restricción debe ser <=0.
4.1.5. Si el problema primal tiene una restricción del tipo =, la variable dual asociada a dicha restricción debe ser irrestricta (libre de signo)
4.2. En consecuencia es suficiente con resolver uno de ellos (primal o dual) para poder obtener la solución óptima y valor óptimo del problema equivalente (primal o dual según sea el caso). Para ello se puede utilizar, por ejemplo, las condiciones establecidas en el Teorema de Holguras Complementarias.
4.2.1. Primal Maximización – Dual Minimización
4.2.2. De forma análoga, interpretando la tabla desde derecha a izquierda, es decir, pasar de un problema primal de maximización a un problema dual de minimización, tenemos:
4.2.2.1. Si el problema primal es de maximización, entonces su correspondiente dual será uno de minimización.
4.2.2.2. Si el problema primal tiene una restricción del tipo <=, la variable dual asociada a dicha restricción debe ser >=0
4.2.2.3. Si el problema primal tiene una restricción del tipo >=, la variable dual asociada a dicha restricción debe ser <=0.
4.2.2.4. Si el problema primal tiene una restricción del tipo =, la variable dual asociada a dicha restricción debe ser irrestricta (libre de signo)
4.2.2.5. Si el problema primal tiene una variable >=0, la correspondiente restricción asociada en el dual debe ser >=
5. 2.3.2 La tabla simplex.
5.1. Es un procedimiento iterativo que permite ir mejorando la solución a cada paso.
5.1.1. El método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución
5.2. El proceso concluye cuando no es posible seguir mejorando más dicha solución
5.2.1. El método del simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta
5.3. Escribir la tabla inicial simplex
5.3.1. En las columnas aparecerán todas las variables del problema y, en las filas, los coeficientes de las igualdades obtenidas, una fila para cada restricción y la última fila con los coeficientes de la función objetivo
5.3.1.1. Para escoger la variable de decisión que entra en la base, nos fijamos en la última fila, la de los coeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor (en valor absoluto)
5.3.1.1.1. Para encontrar la variable de holgura que tiene que salir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero
6. 2.3 Método simplex.
6.1. Método analítico de solución de problemas de programación lineal
6.1.1. Capaz de resolver modelos más complejos que los resueltos mediante el método gráfico sin restricción en el número de variables
6.2. Es un método iterativo que permite ir mejorando la solución en cada paso
6.2.1. el método consiste en caminar del vértice de un poliedro a un vértice vecino de manera que aumente o disminuya (según el contexto de la función objetivo, sea maximizar o minimizar), dado que el número de vértices que presenta un poliedro solución es finito siempre se hallará solución
6.3. Trabaja basándose en ecuaciones y las restricciones iniciales que se modelan mediante programación lineal no lo son
6.3.1. Para ello hay que convertir estas inecuaciones en ecuaciones utilizando unas variables denominadas de holgura y exceso relacionadas con el recurso al cual hace referencia la restricción y que en el tabulado final representa el «Slack or surplus» al que hacen referencia los famosos programas de resolución de investigación de operaciones
6.4. Estas variables suelen estar representadas por la letra «S», se suman si la restricción es de signo «<= » y se restan si la restricción es de signo «>=»
7. 2.3.1 Método algebraico.
7.1. Procedimiento con el que hemos estado relacionados antes que conociéramos siquiera las implicaciones del término optimización en la vida de todo ingeniero industrial
7.2. Con el método algebraico se va a hacer uso de todas las herramientas que utilizaste para resolver sistemas de ecuaciones lineales
7.3. Pasos para desarrollar el método algebraico según Chediak:
7.3.1. * Hallar una solución básica y factible (solución inicial)
7.3.2. * Expresar las inecuaciones como ecuaciones
7.3.3. * Hallar una variable básica para cada ecuación
7.3.4. * Organizar el sistema de ecuaciones lineales
7.3.5. * Escoger la variable que entra
7.3.6. * Escoger la variable que sale
7.3.7. * Reorganizar el sistema de ecuaciones
7.3.8. * Repetir los pasos 2,3, y 4 hasta encontrar la solución