Programación Lineal Método Simplex PDF

Preview

Summary

Download Programación Lineal Método Simplex PDF

Description

29/10/2020

PROGRAMACIÓN LINEAL: MÉTODO SIMPLEX

3.1. ALGORITMO SIMPLEX 3.2. PROBLEMAS DE MAXIMIZACIÓN 3.3. EJERCICIOS RESUELTOS EJERCICIO 3.3.1. EJERCICIO 3.3.2.

PROGRAMACIÓN LINEAL: MÉTODO SIMPLEX Taller de Modelamiento Matemático - ADVANCE - UNAB Marcelo Alid-Vaccarezza 2020-10-15

https://unab.blackboard.com/bbcswebdav/pid-3322063-dt-content-rid-22885796_1/courses/AICI3102.202025.1306.TR/Metodo_Simplex.html

1/14

29/10/2020

PROGRAMACIÓN LINEAL: MÉTODO SIMPLEX

PRESENTACIÓN En este capítulo se presenta el método simplex de solución de problemas de programación lineal incluyendo problemas de maximización y minimización.

OBJETIVO GENERAL Al finalizar el capítulo el estudiante debe estar en capacidad de solucionar un problema de programación lineal utilizando el método gráfico; así como interpretar correctamente la solución y analizar el consumo de recursos.

OBJETIVOS ESPECÍFICOS Manejar las reglas de equivalencia para llevar todas las desigualdades a igualdades. Dominar el procedimiento de avance hacai la optimalidad del método simplex. Determinar mediante el método simplex el momento en el que se llega a la solución óptima, tanto en problemas de maximización como de minimización. Identificar el tipo de solución del problema con el uso del tablero simplex. Interpretar soluciones obtenidas.

COMPETENCIAS El estudiante tendrá la capacidad de utilizar el método simplex en la solución de problemas de programación lineal; y con base en ésta interpretar el tipo de solución del provlema, así como el uso de variables de holgura, de exceso y artificiales.

INDICADORES DE LOGRO El estudiante deberá demostrar el manejo en el planteamiento de modelos de programación lineal, obtener la solución a través del método simplex e interpretar la solución.

CONOCIMIENTOS PREVIOS Gauss Jordan. Vectores y matrices. https://unab.blackboard.com/bbcswebdav/pid-3322063-dt-content-rid-22885796_1/courses/AICI3102.202025.1306.TR/Metodo_Simplex.html

2/14

29/10/2020

PROGRAMACIÓN LINEAL: MÉTODO SIMPLEX

3.1. ALGORITMO SIMPLEX Para la aplicación y solución de un problema mediante el método simplex se deben tener en cuenta los siguientes pasos: PASO 1. Lleve la función objetivo a maximización mediante la aplicación de la primera regla de la sección 1.6. PASO 2. Transforme todas las restricciones a igualdades de la siguiente manera (esto se realiza para formar los vectores unitarios que generan la primera solución básica factible): Restricción : sume una variable de holgura, tal como see realizó en la cuarta regla de equivalencia de la sección 1.6. Restricción : reste una variable sobrante y sume una variable artificial para generar el vector unitario. Penalice (restar) la función objetivo con la variable artificial, asignándole a ésta un coeficiente infinitamente grande. Por ejemplo , donde tiende al infinito. Restricción : sume una variable artificial para geneerar eel vector unitario y penalice la función objetivo (tal como en el caso anterior). PASO 3. LLeve todos los coeficientes al tablero simplex tal como se muestra en la tabla 4.1. En la fila

ubique todos los coeficientes de las variables de la función objetivo.

En la columna coloque los coeficientes de la función objetivo, pero sólo los correspondientes a las variables básicas. Ubique en la columna BASE las variables básicas, que son aquellas que generan dentro de las restricciones los vectores unitarios (siempre serán las variables de holgura y las variables artificales). En la columna se asignan los valores deel término independiente en cada una de las restricciones (en el tablero inicial). Debajo de cada variable ubique el vector de cada una de ellas en las restricciones (coeficientes de las variables en las restricciones).

Tabla 4.1.: Tablero Simplex

PASO 4. Evalúe si la solución actual es óptima. Para esto, calcule los

de la siguiente

manera: https://unab.blackboard.com/bbcswebdav/pid-3322063-dt-content-rid-22885796_1/courses/AICI3102.202025.1306.TR/Metodo_Simplex.html

3/14

29/10/2020

donde

PROGRAMACIÓN LINEAL: MÉTODO SIMPLEX

son los coeficientes de las variables básicas en la función objetivo,

de la función objetivo y soluciones. Los vectores óptima.

y

Si todos los

son los coeficientes

es cada uno dee los vectores de las variables a través de las diferentes van cambiando cada iteración a medida que se avanza hacia la solución

son mayores o iguales que cero, la solución se hace óptima. De lo

contrario, continué con el paso 5. PASO 5. Seleccione la variable que entra a la base: entra a la base aquella variable que tenga el más negativo. En caso de haber empate entre dos o más variables, elija alguna de ellas. PASO 6. Seleccione la variable que sale de la base: para esto calcule sólo aquellos valores de que entra a la base.

mayores que cero (positivos).

teniendo en cuenta

es el vector columna de la variable

PASO 7. Seleccione el pivote: el pivote es aquella posición donde se intercepta la columna de la variable que entra ( ) y la fila de la variable que sale. PASO 8. Mediante operaciones matriciales entre filas convierta la posiciópn pivote a uno. PASO 9. Utilizando operaciones matriciales convierta las demás posiciones del vector

en ceros.

PASO 10. Determine nuevamente el vector y regrese al paso 4. Continúe con este ciclo hasta que se den las condiciones de optimalidad que pide el cuarto paso.

3.2. PROBLEMAS DE MAXIMIZACIÓN 3.2.1. SOLUCIÓN ÚNICA EJEMPLO 3.2.1. La compañía Sigma produce bibliotecas y escritorios para los cuales se ha establecido un precio de venta por unidad de y respectivamente. Para la producción de dichos artículos la compañía cuenta con una disponibilidad mensual de metros de madera, metros de tubo y pliegos de papel de lija. ¿Qué cantidad de bibliotecas y escritorios se debe fabricar mensualmente si se sabe que una biblioteca consume metros de madera, metros de tubo y pliegos de papel de lija; mientras que para producir un escritorio se requieren metros de madera, metros de tubo y pliegos de papel de lija?

SOLUCIÓN. Análisis de la información. Primero se organiza la información en la siguiente tabla.

https://unab.blackboard.com/bbcswebdav/pid-3322063-dt-content-rid-22885796_1/courses/AICI3102.202025.1306.TR/Metodo_Simplex.html

4/14

29/10/2020

PROGRAMACIÓN LINEAL: MÉTODO SIMPLEX

Figura 1: Tabla resumen con información relevante del problema

Definición de las variables. Se debe decidir cuántas bibliotecas y escritorios se deberán producir por mes para lograr un máximo de utilidad; por lo cual las variables de decisión son:

Modelo matemático completo. El modelo matemático de programación lineal para la compañía SIGMA queda de la siguiente manera:

Tablero Simplex. Para llevar este modelo al tablero simplex se requiere llevar a igualdad todas las restricciones; por lo cual, con base en las reglas de equivalencia a todas las restricciones menores o iguales se le agrega una variable de holgura. El problema queda como aparece a continuación:

Como se puede observar, las variables de holgura también entran a formar parte de la función objetivo sin alterarla, por eso aparecen con coeficiente cero. El primer tablero simplex para este problema aparece en la siguiente tabla:

https://unab.blackboard.com/bbcswebdav/pid-3322063-dt-content-rid-22885796_1/courses/AICI3102.202025.1306.TR/Metodo_Simplex.html

5/14

29/10/2020

PROGRAMACIÓN LINEAL: MÉTODO SIMPLEX

Figura 2: Tablero simplex del problema

3.2.2. SOLUCIÓN ÓPTIMA MÚLTIPLE EJEMPLO 3.2.2. La compañía Hierro Colado dispone semanalmente para la fabricación de sus artículos de metros de lámina y metros de ángulo. Además, se ha establecido que con esos recursos se fabrican puertas y ventanas para los cuales se ha determinado que rinden una contribución a las utilidades de y pesos por unidad respectivamente. También, se sabe por medio de un estudio de consumo de materiales que una puerta requieren metros de lámina y metros de ángulo y que una ventana requieren metros de lámina y metros de ángulo. ¿Qué cantidad de cada artículo se debe fabricar si se sabe que el departamento de mercados estableció que máximo se venderán puertas?

SOLUCIÓN. Análisis de la información. Primero se organiza la información en la siguiente tabla.

Figura 3: Tabla resumen con información relevante del problema

Definición de las variables. Se debe decidir cuántas puertas y ventanas se deberán producir por semana para lograr un máximo de utilidad; por lo cual las variables de decisión son:

Modelo matemático completo. El modelo matemático de programación lineal para la compañía queda de la siguiente manera:

https://unab.blackboard.com/bbcswebdav/pid-3322063-dt-content-rid-22885796_1/courses/AICI3102.202025.1306.TR/Metodo_Simplex.html

6/14

29/10/2020

PROGRAMACIÓN LINEAL: MÉTODO SIMPLEX

á á á

Tablero Simplex. Para llevar este modelo al tablero simplex se requiere llevar a igualdad todas las restricciones; por lo cual, con base en las reglas de equivalencia a todas las restricciones menores o iguales se le agrega una variable de holgura. El problema queda como aparece a continuación:

á á á

Como se puede observar, las variables de holgura también entran a formar parte de la función objetivo sin alterarla, por eso aparecen con coeficiente cero. El primer tablero simplex para este problema aparece en la siguiente tabla:

Figura 4: Tablero simplex del problema

3.2.3. SOLUCIÓN ÓPTIMA NO ACOTADA EJEMPLO 3.2.3. Una fábrica de artesanías se dedica a la producción de bolsos y chaquetas los cuales comercializa directamente a los clientes en la plaza España. La venta de un bolso genera una utilidad de y consume horas de mano de obra; mientras que la venta de una chaqueta genera una utilidad de y consume horas de mano de obra. Por políticas de la compañía se requiere de no mantener en ocio a sus trabajadores y por lo tanto se debe consumir en la producción un mínimo de horas de mano de obra por mes. ¿Qué cantidad de bolsos y chaquetas se debe fabricar, si por estudio de mercados se sabe que mínimo se venderán chaquetas y como máximo bolsos por mes?

SOLUCIÓN. Análisis de la información. Primero se organiza la información en la siguiente tabla.

https://unab.blackboard.com/bbcswebdav/pid-3322063-dt-content-rid-22885796_1/courses/AICI3102.202025.1306.TR/Metodo_Simplex.html

7/14

29/10/2020

PROGRAMACIÓN LINEAL: MÉTODO SIMPLEX

Figura 5: Tabla resumen con información relevante del problema

Definición de las variables. Se debe decidir cuántos bolsos y chaquetas se deberán producir por mes para lograr un máximo de utilidad; por lo cual las variables de decisión son:

Modelo matemático completo. El modelo matemático de programación lineal para la compañía queda de la siguiente manera:

á í

Tablero Simplex. Siguiendo el procedimiento de transformar todas las restricciones en restricciones de igualdad, utilizando las reglas de equivalencia tenemos lo siguiente:

á í

Como se sabe, el método simplex utiliza vectores unitarios para generar las diferentes soluciones. Las variables y (variables exceso o superfluo) tienen coeficientes negativos ( ) en las restricciones, lo cual no genera vectores unitarios. Para generar el vector unitario en estos casos se debe sumar una variable artifial a estas restricciones consevando la misma igualdad. Estas variables artificiales para que la igualdad se siga cumpliendo deben tomar valor cero; por lo tanto hay que penalizar la función objetivo; con un coeficiente infinitamente grande para estas variables en la función objetivo (en algunos textos a este método se le denomina Metodo de Penalizacion o de la Gran M). El modelo a llevar al tablero simplex que da como aparece a continuación (por simplicidad, la función objetivo se ha dividido por ):

https://unab.blackboard.com/bbcswebdav/pid-3322063-dt-content-rid-22885796_1/courses/AICI3102.202025.1306.TR/Metodo_Simplex.html

8/14

29/10/2020

PROGRAMACIÓN LINEAL: MÉTODO SIMPLEX

á í

El primer tablero simplex para este problema aparece en la siguiente tabla:

Figura 6: Tablero simplex del problema

3.2.4. PROBLEMA SIN SOLUCIÓN ÓPTIMA EJEMPLO 3.2.4. La compañía Epsilon produce baldosas y tabletas, las cuales generan una contribución a las utilidades de y por metro cuadrado respectivamente. Para la producción de dichos artículos se cuenta con una disponibilidad de metros cuadrados de arena y metros cuadrados de cemento por semana. ¿Qué cantidad de cada uno de los artículos se debe fabricar si se sabe que para producir un metro cuadrado de baldosas se requieren metros cuadrados de arena y metros cuadrados de cemento; mientras que para producir un metro cuadrado de tableta se requieren metros cuadrados de arena y metros cuadrados de cemento? Suponga además, que el cliente garantiza comprar como mínimo metros cuadrados de tableta.

SOLUCIÓN. Análisis de la información. Primero se organiza la información en la siguiente tabla.

Figura 7: Tabla resumen con información relevante del problema

https://unab.blackboard.com/bbcswebdav/pid-3322063-dt-content-rid-22885796_1/courses/AICI3102.202025.1306.TR/Metodo_Simplex.html

9/14

29/10/2020

PROGRAMACIÓN LINEAL: MÉTODO SIMPLEX

Definición de las variables. Se debe decidir cuántos metros cuadrados de baldosas y tabletas se deberán producir por semana para lograr un máximo de utilidad; por lo cual las variables de decisión son:

Modelo matemático completo. El modelo matemático de programación lineal para la compañía queda de la siguiente manera:

í

Tablero Simplex. Llevando todas las restricciones a igualdades, generando todos los vectores unitarios a que haya lugar y penalizando la función objetivo; el ejercicio se establece así (por simplicidad la función objetivo se ha dividido por ):

í

El primer tablero simplex para este problema aparece en la siguiente tabla:

Figura 8: Tablero simplex del problema

3.3. EJERCICIOS RESUELTOS EJERCICIO 3.3.1. Un herrero con de acero y que quiere vender, respectivamente a beneficio. Para la de paseo empleará

de aluminio quiere hacer bicicletas de paseo y de montaña y pesos cada una para sacar el máximo de acero y de aluminio, y para la de montaña de

https://unab.blackboard.com/bbcswebdav/pid-3322063-dt-content-rid-22885796_1/courses/AICI3102.202025.1306.TR/Metodo_Simplex.html

10/14

29/10/2020

PROGRAMACIÓN LINEAL: MÉTODO SIMPLEX

ambos metales. ¿Cuántas bicicletas de paseo y de montaña deberá fabricar para maximizar las utilidades?

SOLUCIÓN. Análisis de la información. Primero se organiza la información en la siguiente tabla.

Figura 9: Análisis de la información del ejemplo 1

Definición de las variables. Se debe decidir cuántas bicicletas de paseo y de montaña se deberán producir para lograr un máximo de utilidad; por lo cual las variables de decisión son:

ñ

Modelo matemático completo. El modelo matemático de programación lineal queda de la siguiente manera:

Tablero Simplex. Llevando todas las restricciones a igualdades, generando todos los vectores unitarios a que haya lugar y penalizando la función objetivo; el ejercicio se establece así (por simplicidad la función objetivo se ha dividido por ):

El primer tablero simplex para este problema aparece en la siguiente tabla:

https://unab.blackboard.com/bbcswebdav/pid-3322063-dt-content-rid-22885796_1/courses/AICI3102.202025.1306.TR/Metodo_Simplex.html

11/14

29/10/2020

PROGRAMACIÓN LINEAL: MÉTODO SIMPLEX

Figura 10: Tableau Simplex Inicial del ejemplo 1

EJERCICIO 3.3.2. Un autobús que hace el recorrido Concepción-Santiago, ofrece asientos para fumadores al precio de pesos y a no fumadores al precio de pesos. Al no fumador se le deja llevar de peso y al fumador . Si el autobús tiene asientos y admite un equipaje de hasta . ¿Cuál ha de ser la oferta de asientos de la compañía para cada tipo de pasajeros, con la finalidad de optimizar el beneficio? Además, debe considerarse que por políticas de la empresa, deben ofrecerse cómo mínimo asientos para pasajeros no fumadores.

SOLUCIÓN. Análisis de la información. Primero se organiza la información en la siguiente tabla.

Figura 11: Análisis de la información del ejemplo 2

Definición de las variables. Se debe decidir cuántos acientos para fumadores y no-fumadores se deberán disponer para lograr un máximo de utilidad; por lo cual las variables de decisión son:

Modelo matemático completo. El modelo matemático de programación lineal queda de la siguiente manera: https://unab.blackboard.com/bbcswebdav/pid-3322063-dt-content-rid-22885796_1/courses/AICI3102.202025.1306.TR/Metodo_Simplex.html

12/14

29/10/2020

PROGRAMACIÓN LINEAL: MÉTODO SIMPLEX

í

Tablero Simplex. Llevando todas las restricciones a igualdades, generando todos los vectores unitarios a que haya lugar y penalizando la función objetivo; el ejercicio se establece así (por simplicidad la función objetivo se ha dividido por ):

í

El primer tablero simplex para este problema aparece en la siguiente tabla:

Figura 12: Tableau Simplex Inicial del ejemplo 2

https://unab.blackboard.com/bbcswebdav/pid-3322063-dt-content-rid-22885796_1/courses/AICI3102.202025.1306.TR/Metodo_Simplex.html

13/14

29/10/2020

PROGRAMACIÓN LINEAL: MÉTODO SIMPLEX

https://unab.blackboard.com/bbcswebdav/pid-3322063-dt-content-rid-22885796_1/courses/AICI3102.202025.1306.TR/Metodo_Simplex.html

14/14...