• Author / Uploaded
• Jorge

Citation preview

4. 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 simplex; 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. 4.1. ALGORITMO SIMPLEX

4.2. PROBLEMAS DE MAXIMIZACIÓN 4.2.1. SOLUCIÓN ÚNICA Ejercicio 4.2.1. La compañía Sigma produce bibliotecas y escritorios para los cuales se ha establecido un

9000 y 10000 respectivamente. Para la producción de dichos artículos la compañía cuenta con una disponibilidad mensual de 700 metros de madera, 800 metros de tubo y 900 precio de venta por unidad de

pliegos de papel de lija. ¿Qué cantidad de bibliotecas y escritorios se debe fabricar mensualmente si se sabe que una biblioteca consume 7 metros de madera, 10 metros de tubo y 6 pliegos de papel de lija; mientras que para producir un escritorio se requieren 10 metros de madera, 8 metros de tubo y 15 pliegos de papel de lija? Solución Análisis de la información. Primero se organiza la información en la siguiente tabla.

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:

X1 : cantidad de bibliotecas a producir por mes. X2 : cantidad de escritorios a producir por mes. Modelo matemático completo. El modelo matemático de programación lineal para la compañía SIGMA queda de la siguiente manera:

max Z = 9000X1 + 10000X2 S.T.

7X1 + 10X2 10X1 + 8X2 6X1 + 15X2 X1 , X2

≤ 700 ≤ 800 ≤ 900 ≥ 0

(metros de madera) (metros de tubo) (pliegos papel lija) (no negatividad)

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:

max Z = 9000X1 + 10000X2 + 0H1 + 0H2 + 0H3 S.T.

7X1 + 10X2 + H1 = 700 10X1 + 8X2 + H2 = 800 6X1 + 15X2 + H3 = 900 X1 , X2 , H1 , H2 , H3 ≥ 0

(metros de madera) (metros de tubo) (pliegos papel lija) (no negatividad)

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:

4.2.2. SOLUCIÓN ÓPTIMA MÚLTIPLE Ejercicio 4.2.2. La compañía Hierro Colado dispone semanalmente para la fabricación de sus artículos de

350 metros de lámina y 360 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 70 y 50 pesos por unidad respectivamente. También, se sabe por medio de un estudio de consumo de materiales que una puerta requieren

7 metros de lámina y 4 metros de ángulo y que una ventana requieren 5 metros de

lámina y 9 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 40 puertas? Solución Análisis de la información. Primero se organiza la información en la siguiente tabla.

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:

X1 : cantidad de puertas a producir por semana. X2 : cantidad de ventanas a producir por semana.

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

max Z = 70X1 + 50X2 S.T.

7X1 + 5X2 ≤ 350 4X1 + 9X2 ≤ 360 X1 ≤ 40 X1 , X2 ≥ 0

(metros de lámina) (metros de ángulo) (venta máxima de puertas) (no negatividad)

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:

max Z = 70X1 + 70X2 + 0H1 + 0H2 + 0H3 S.T.

7X1 + 5X2 + H1 = 350 4X1 + 9X2 + H2 = 360 X1 + H3 = 40 X1 , X2 , H1 , H2 , H3 ≥ 0

(metros de lámina) (metros de ángulo) (venta máxima de puertas) (no negatividad)

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:

4.2.3. SOLUCIÓN ÓPTIMA NO ACOTADA Ejercicio 4.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 2000 y consume

5 horas de mano de obra; mientras que la venta de una chaqueta genera una utilidad de 3000 y

9 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 450 horas de mano de obra por consume

mes. ¿Qué cantidad de bolsos y chaquetas se debe fabricar, si por estudio de mercados se sabe que mínimo

se venderán 20 chaquetas y como máximo 30 bolsos por mes? Solución Análisis de la información. Primero se organiza la información en la siguiente tabla.

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:

X1 : cantidad de bolsos a producir por mes. X2 : cantidad de chaquetas a producir por mes. Modelo matemático completo. El modelo matemático de programación lineal para la compañía queda de la siguiente manera:

max Z = 2000X1 + 3000X2 S.T.

5X1 + 9X2 ≥ 450 X1 ≤ 30 X2 ≥ 20 X1 , X2 ≥ 0

(mano de obra) (ventas máxima de bolsos) (venta mínima de chaquetas) (no negatividad)

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

max Z = 2000X1 + 3000X2 + 0S1 + 0H1 + 0S2 S.T.

5X1 + 9X2 − S1 = 450 X1 + H1 = 30 X2 − S2 = 20 X1 , X2 , S1 , H1 , S2 ≥ 0

(mano de obra) (venta máxima de bolsos) (venta mínima de chaquetas) (no negatividad)

Como se sabe, el método simplex utiliza vectores unitarios para generar las diferentes soluciones. Las variables S1 y S2 (variables exceso o superfluo) tienen coeficientes negativos (−1 ) 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 1000):

max Z = 2X1 + 3X2 + 0S1 + 0S2 − M A1 + 0H1 − M A2 S.T.

5X1 + 9X2 − S1 + A1 X1 + H1 X2 − S2 + A2 X1 , X2 , S1 , S2 , A1 , H1 , A2

= 450 = 30 = 20 ≥ 0

(mano de obra) (venta máxima de bolsos) (venta mínima de chaquetas) (no negatividad)

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

4.2.4. PROBLEMA SIN SOLUCIÓN ÓPTIMA Ejercicio 4.2.4. La compañía Epsilon produce baldosas y tabletas, las cuales generan una contribución a las

5000 y 4000 por metro cuadrado respectivamente. Para la producción de dichos artículos se cuenta con una disponibilidad de 200 metros cuadrados de arena y 240 metros cuadrados de cemento por utilidades de

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 4 metros cuadrados de arena y 3 metros cuadrados de cemento; mientras

5 metros cuadrados de arena y 8 metros cuadrados de cemento? Suponga además, que el cliente garantiza comprar como mínimo 50 metros que para producir un metro cuadrado de tableta se requieren cuadrados de tableta. Solución Análisis de la información. Primero se organiza la información en la siguiente tabla.

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:

X1 : metros cuadrados de baldosas a producir por semana. X2 : metros cuadrados de tabletas a producir por semana. Modelo matemático completo. El modelo matemático de programación lineal para la compañía queda de la siguiente manera:

max Z = 5000X1 + 4000X2 S.T.

4X1 + 5X2 ≤ 200 3X1 + 8X2 ≤ 240 X2 ≥ 50 X1 , X2 ≥ 0

(arena disponible) (cemento disponible) (venta mínima de tabletas) (no negatividad)

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 1000):

max Z = 5X1 + 4X2 + 0S1 + 0H1 + 0H2 − M A1 S.T.

4X1 + 5X2 + H1 3X1 + 8X2 + H2 X2 − S1 + A1 X1 , X2 , S1 , H1 , H2 , A1

= 200 = 240 = 50 ≥ 0

(arena disponible) (cemento disponible) (venta mínima de tabletas) (no negatividad)

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