UNIVERSIDAD TECNOLÓGICA METROPOLITANA

FACULTAD DE INGENIERIA

DEPARTAMENTO DE INFORMATICA Y COMPUTACION

INGENIERIA CIVIL EN COMPUTACIÓN MENCION INFORMATICA

APUNTE NUMERO 2

ASIGNATURA

OPTIMIZACION DE SISTEMAS

TEMA 2

FORMULACION DE MODELOS LINEALES

INTRODUCCIÓN Sin duda alguna , los Modelos de Optimización Lineal son una de las aplicaciones comerciales que tienen más éxito en la Administración de Operaciones; de hecho, hay pruebas de que son las de mayor impacto económico.

HARVEY WAGNER El reto de las Operaciones : “ Actualmente la empresas se concentran en determinar lo que realmente valen los clientes. Este es un buen paso pero no basta: Los clientes no pagan a las empresas para que descubran lo que ellos valen, sino para que les entreguen ese valor menor que la competencia “ .

ARUM N. MAIRA Los Administradores tomamos decisiones en cada momento de nuestra actividad empresarial, por esta razón utilizamos herramientas para analizar y elegir la mejor entre las muchas opciones que se presentan para una misma situación.

La Programación Lineal se considera como un método determinístico que busca captar todas las actividades intervinientes en una situación de decisión y formular un modelo cuantitativo que genere criterios de decisión.

Seleccionar una alternativa conlleva a analizar diferentes criterios al mismo tiempo. Por ejemplo, cuando se compra un apartamento se tiene el criterio de espacio, distribución, área, ubicación, decoración y costo. Estos criterios se pueden dividir en dos categorías : Restricciones y Función Objetivo.

En pocas palabras, podemos decir que existen muchas situaciones de decisión que se ajustan al modelo de Programación Lineal, pero la situación más común de aplicación incluye el problema general de

asignar recursos restringidos entre actividades competitivas en forma óptima, es decir, de modo que se cumplan las restricciones y se alcance la meta de la función objetivo.

Un ejemplo a nivel general, sería el caso de una empresa que planea producir un artículo para el mercado de Bucaramanga. La función objetivo, es minimizar el costo. Las restricciones , pueden ser : gustos y preferencias del mercado meta, tecnología, capacidad de producción, entre otras.

Un ejemplo a nivel específico, podría ser que el director de producción desea agilizar un proceso. La función objetivo, minimizar el tiempo de producción. Las restricciones pueden ser : número o nivel del personal, capacidad de producción, diseño de productos, entre otros.

Como Administradores no debemos preocuparnos por las complejidades matemáticas que implican el desarrollo de un método de Programación Lineal para

solucionar un problema, puesto que, existen diversidad de programas de computador que facilitan la tarea.

No obstante, los Administradores debemos conocer el procedimiento manual de la solución de los problemas de Programación Lineal, con el fin de adquirir los conocimientos básicos sobre el lenguaje matemático de ésta, y así poder trabajar conjuntamente con analistas especializados en la formulación, análisis e interpretación de los problemas más complejos.

Pero lo que realmente nos debe interesar es la interpretación de los resultados y la toma de decisiones. Siendo los resultados básicos para obtener el objetivo trazado; De manera que podemos analizar el efecto que tendría sobre la solución óptima el hacer variaciones razonables a los valores de los parámetros.

Tales variaciones pueden generar datos importantes para evaluar alternativas que no son formuladas en el planteamiento inicial.

Por otra parte, debemos reconocer las características de los problemas propios de los negocios para los cuales los métodos de Programación Lineal sean aplicables.

Los problemas típicos Programación Lineal son aquellos que implican la asignación de recursos restringidos a demandas que compitan entre sí.

PLANTEAMIENTO DE PROBLEMAS

Programación Lineal, se refiere a una técnica matemática que permite asignar recursos limitados. Es un método de resolución de problemas que se ha desarrollado para ayudarnos como Administradores de Empresas en la toma de decisiones.

La Programación Lineal puede enfrentarse al siguiente problema : “ ¿ Como obtengo el mayor valor por los bienes y servicios que produzco, con los recursos que tengo ? Si todas las relaciones fuesen lineales podriamos utilizar la Programación Lineal para resolver este problema “ .

Podemos utilizar la Programación Lineal cuando hay que maximizar ( utilidades ) o minimizar ( costos ) con un solo objetivo. Cuando se trata de varios objetivos se usa la Programación de Metas si la mejor solución para un problema se logra por etapas o períodos, se recomienda la Programación Dinámica . Es muy tedioso resolver manualmente un problema de Programación Lineal, incluso de unas cuantas ecuaciones, por lo que requerimos un computador para resolver un problema de manera práctica. Emplearemos uno de los software utilizados para tal efecto, denominado el QSB + 3.0 .

A continuación describiremos algunas aplicaciones clásicas de la Programación Lineal :

A) Un fabricante desea elaborar un programa de producción y una política de inventarios que satisfaga la demanda de ventas en períodos futuros. Idealmente, el programa y la política le permitirán a la compañía satisfacer la demanda y al mismo tiempo , minimizar los costos totales de producción e inventarios.

B) Un analista financiero debe seleccionar una cartera de inversiones a partir de diversas opciones de inversión. Al analista le gustaría establecer la cartera que maximice el rendimiento sobre ésta.

C) Un gerente de mercadotecnia desea determinar la mejor forma de asignar un presupuesto de publicidad fijo entre diversos medios publicitarios tales como radio, televisión, periódicos y revistas. Al gerente le gustaría determinar la combinación de medios que maximiza la eficacia de la publicidad.

D) Una compañía tiene almacenes en diferentes lugares del país. Considerando las demandas específicas de un conjunto de clientes para sus productos , la compañía querría determinar que almacén debe enviar, que cantidad de producto a que clientes, de manera que minimicen los costos totales de transporte.

E) Una empresa tiene ejecutivos, los cuales necesita desplazar a sus diferentes plantas ubicadas en el territorio nacional. La compañía desea ubicar a los ejecutivos en cada una de las plantas de tal manera que se minimicen los costos de traslado.

El modelo de Programación Lineal comprende un proceso de optimización donde se seleccionan valores no reactivos para un conjunto de variables de decisión X1, X2, ... Xn, de forma que se maximice ( o minimice ) una función objetivo de la forma:

Maximizar ( minimizar )

Z = C1X1 + C2X2+ ... + CnXn

Sujeta a restricciones de recursos de la forma :

A11X1 + A12X2 + ... + A1nX1 <= B1 A21X1 + A22X2 + ... + A2nXn <= B2

Am1X1 + Am2X2 + ... + AmnXn <= Bm

donde Cj, Aij y Bi son constantes

Dependiendo del problema, también pueden plantearse las restricciones con signos de igualdad (=) o signos de mayor o igual ( >= ).

Las Xi son variables de decisión, llamadas también acciones.

Las restricciones pueden ser de un solo tipo.

Las Cj son coeficientes que representan la contribución por unidad de la variable Xj al valor de la función objetivo Z.

Las aij son los coeficientes tecnológicos, representan la cantidad del recurso i que es “ consumido “ por una unidad de la variable Xj.

Las bi representan la disponibilidad total de los recursos, es cualquier valor numérico en el lado derecho de las restricciones.

bi >= 0 , para toda i.

xj >= 0, para toda j.

En esencia deben existir cinco condiciones principales para que pueda aplicarse la Programación Lineal a un problema :

1. Los recursos deben ser limitados (por ejemplo : los trabajadores, el equipo, el capital, la materia prima, los terrenos ), de lo contrario no habría problema.

2. Debe existir un objetivo que se pueda especificar ( maximizar utilidades, minimizar costos).

3. Debe existir una relación lineal en las restricciones y en la función objetivo (por ejemplo : si fabricar un artículo requiere 3 horas, fabricar 10 artículos requiere 30 horas; si el costo de fabricación de 1 es de $ 1000 el de 10 es de $ 10000 ).

4. Los recursos y los productos deben se homogéneos ( Los productos que se obtienen de una máquina deben ser de idénticas características ; todas las horas de un trabajador deben ser igualmente productivas ) .

5. En la Programación Lineal normal los productos y los recursos deben ser fraccionarios y no negativos, si no es posible realizar esta subdivisión debe utilizarse la Programación Entera, (por ejemplo : el número de operarios no puede ser de 4,3 en cuanto a recursos o volar medio avión ).

SOLUCION GRAFICA

Aunque la Programación Lineal gráfica se limita a problemas con 2 variables de decisión o 3 en 3 dimensiones, es una manera rápida de conocer la naturaleza de la Programación Lineal e ilustra lo que sucede con el Método Simplex que describiremos más adelante.

Los pasos que comprende el método gráfico los explicaremos en el contexto del siguiente ejemplo.

Ejemplo No. 1 Manufacturas “SOLO CUERO” ha decidido entrar en el negocio de billeteras para hombre y billeteras para mujer.

Una investigación cuidadosa de las etapas necesarias para fabricar estos productos determina que se requieren de 4 operaciones.

Corte y teñido para dar un color especial al cuero. Cosido de las partes. Ensamble de los herrajes. Inspección y embalaje.

El jefe de manufactura ha analizado cada una de las operaciones y concluye que por cada modelo de billetera para hombre se requieren 42 minutos en el taller de corte y teñido, 30 minutos en el taller de costura, 60 minutos en la sección de terminado y 6 minutos en inspección y embalaje.

Mientras que cada billetera para mujer necesita 60 minutos en corte y teñido, 50 minutos para costura, 40 minutos para terminado y 15 minutos para inspección y ensamble.

El salario de cada operario es de $ 1200 por hora, el costo de la materia prima y equipo es de $ 4240 para cada billetera para hombre y $ 4700 para cada billetera para mujer. El precio de venta tanto de la billetera para hombre como para mujer es de $ 17000.

Después de estudiar las cargas de trabajo de las diferentes secciones se estima que para la producción de estos 2 artículos en los 3 meses siguientes, habrá disponibles 37800 minutos de tiempo de corte y teñido, 36000 minutos de costura, 42480 minutos de acabado y 8100 minutos de inspección y embalaje.

Tabla Resumen No. 3.1

Producto Etapa 1 Etapa 2 Etapa 3 Etapa 4 Salario Costo MP Precio

Billetera H 42 min 30 min 60 min 6 min $ 1.200 /h $ 4.240 $ 17.000 Billetera M 60 min 50 min 40 min 15 min $ 1.200/h $ 4.240 $ 17.000

Tabla Resumen No. 3.2

Etapas Tiempo disponible

Etapa 1 37.800 min

Etapa 2 36.000 min Etapa 3 42.480 min

Etapa 4 8.100 min

El problema para “SOLO CUERO“ es determinar cuántas billeteras para hombre y para mujer deben fabricarse para maximizar la contribución a las utilidades.

LA FUNCIÓN OBJETIVO

Todo problema de Programación Lineal cuenta con un objetivo de maximización o minimización. En este problema nuestro objetivo será maximizar las utilidades. Para plantear este objetivo en forma matemática se tiene en cuenta :

X1 = Número de billeteras para hombre

X2 = Número de billeteras para mujer

Supongamos que C1 es la contribución a las utilidades por cada billetera para hombre, luego la contribución total será C1X1 y C2 la contribución por cada billetera para mujer, lo cual daría una utilidad de C2X2.

Denotando como Z la contribución total a las utilidades, tenemos :

Contribución a las utilidades totales =

Z = C1X1 + C2X2

Para calcular C1 debemos tener en cuenta lo siguiente :

Costo de Mano de Obra :

Costo de operación de corte y teñido 42 x 20 =$ 840

Costo de operación costura 30 x 20 = $ 600

Costo de operación de ensamble de herrajes 60 x 20 =$1.200

Costo de operación inspección y embalaje 6 x 20 = $ 120

Costo unitario de materia prima y herramienta $ 4.240

COSTO TOTAL DE FABRICACIÓN BILLETERA PARA HOMBRE

$ 7.000

Como el precio de venta por cada billetera para hombre es de $ 17.000 la contribución a la utilidad es $17.000 - $ 7.000 = $10.000 / unidad. De la misma forma podemos calcular C2 :

Costo de Mano de Obra :

Costo de operación de corte y teñido 60 x 20 =$ 1.200

Costo de operación costura 50 x 20 =$ 1.000

Costo de operación de ensamble de herrajes 40 x 20 = $ 800

Costo de operación inspección y embalaje 15 x 20 = $ 300

Costo unitario de materia prima y herramienta $ 4.700 COSTO TOTAL DE FABRICACIÓN BILLETERA PARA MUJER

$ 8.000

Como el precio de venta por cada billetera para mujer es de $ 17.000 la contribución a la utilidad es $ 17.000 - $ 8.000 = $ 9.000 / unidad.

La función objetivo es :

Z = 10.000 X1 + 9.000 X2

donde X1 es el número de billeteras para hombre y X2 es el número de billeteras para mujer.

El problema de la empresa “ SOLO CUERO“ es como elegir los valores de las variables X1 y X2 que producen el mayor valor posible de Z. En términos de Programación Lineal a X1 y X2 las denominamos Variables de Decisión. Como el objetivo, maximizar la contribución total a las utilidades, es función de esas variables decisorias, a 10.000 X1 + 9.000 X2 la denominamos Función Objetivo.

Max Z = 10.000 X1 + 9.000 X2

En este problema a cualquier combinación específica de fabricación de billeteras para hombre y de billeteras para mujer las designamos Solución del Problema. Cabe anotar, que únicamente a las soluciones que satisfacen todas las restricciones las llamamos Soluciones Factibles .

La combinación factible específica (solución factible) que da como resultado la mayor aportación a las utilidades la llamamos Combinación óptima de producción,

es decir, Solución Optima. Claro está, que hasta este momento no conocemos cuál será la solución óptima. Es más ni siquiera hemos desarrollado un procedimiento para identificar las soluciones factibles; para determinarlas requerimos identificar las restricciones del problema.

LAS RESTRICCIONES

Cada una de las billeteras para hombre y para mujer que se fabrican deben pasar por cuatro operaciones de producción. Existe una cantidad limitada de tiempo de producción disponible para cada una de las operaciones, por lo cual puede esperarse que haya cuatro restricciones limitando el número total de billeteras que la empresa puede fabricar.

A partir de la información de manufactura (Tabla No. 3.1) sabemos que cada billetera para hombre que la empresa fabrique utilizará 42 minutos en corte y teñido. Por ello, el número total de minutos para la primera operación que se utiliza en la fabricación de X1 billeteras para hombre será 42 X1. De otra parte, cada billetera para mujer que se fabrique requerirá de 60 minutos para corte y teñido; por consiguiente las billeteras para mujer utilizarán 60 X2 de tal operación. El tiempo total de corte y teñido que se requiere para la fabricación de X1 billeteras para hombre y X2 billeteras para mujer esta dado por :

Tiempo total de corte y teñido que se requiere = 42 X1 + 60 X2

Como el jefe de manufactura ha planteado que se dispone de cuando mucho 37.800 minutos para el corte y teñido, concluimos que la combinación de productos que se seleccione debe satisfacer el requisito.

42 X1 + 60 X2 <= 37.800

A esta relación denominamos desigualdad y denota que el número total de minutos que se utilizan para las operaciones de corte y teñido en la fabricación de X1 billeteras para hombre y X2 billeteras para mujer, debe ser menor que o igual a la cantidad máxima de tiempo disponible para corte y teñido.

En la tabla No. 3.1 se observamos que cada billetera para hombre que se fabrique requerirá de 30 minutos de costura, y que cada billetera para mujer necesita de 50 minutos de costura.

Como hay disponibles 36.000 minutos de tiempo de corte, tenemos :

30 X1 + 50 X2 <= 36.000

La restricción para la capacidad de terminado es:

60 X1 + 40 X2 <= 42.480

y que la restricción para la capacidad de inspección y embalaje es:

6 X1 + 15X2 <= 8.100

Después de especificar las relaciones matemáticas de las restricciones para las cuatro operaciones de producción debemos añadir 2 restricciones más con el objeto de evitar que las variables de decisión X1 y X2 asuman valores negativos así :

X1 >= 0 ; X2 >= 0

Estas restricciones las denominamos Restricciones de No Negatividad y son una característica general de todos los problemas de Programación Lineal escribiéndose en forma abreviada así :

X1 , X2 >= 0

PLANTEAMIENTO MATEMÁTICO

Hasta este punto hemos traducido el objetivo y las restricciones del problema “Real“ en un conjunto de relaciones matemáticas denominadas Modelo Matemático. El Modelo Matemático para el problema es :

Max 10.000 X1 + 9.000 X2

Sujeto a:

42 X1 + 60 X2 <= 37.800 Corte y teñido 30 X1 + 50 X2 <= 36.000 Costura

60 X1 + 40 X2 <= 42.480 Terminado 6 X1 + 15 X2 <= 8.100 Inspección y embalaje

A partir de esto necesitamos encontrar la combinación de productos (X1 y X2 ) que satisfaga todas las restricciones y al mismo tiempo, dé un valor de la función objetivo que sea mayor que o igual a un valor dado para cualquier otra solución factible y de esta manera se encuentre la solución al problema.

El modelo matemático para el problema es un Programa Lineal para lo cual debe cumplir con la característica primordial como lo es que la función objetivo y todas las funciones de restricción son funciones lineales de las variables decisorias.

Las funciones matemáticas en las que todas las variables aparecen en un término a parte y están elevadas a la primera potencia, reciben el nombre de Funciones Lineales. La función objetivo ( 10.000 X1 + 9.000 X2 ) es lineal porque todas las variables de decisión aparecen en un término diferente y tienen exponente de uno.

El tiempo de producción requerido en el taller de corte y teñido ( 42 X1 + 60 X2 ? 37.800 ) es también una función lineal de las variables de decisión por el mismo motivo, ocurriendo de igual forma con las funciones de las restantes restricciones.

De esta manera podemos afirmar que la palabra Programación significa “ elegir un curso de acción “. La Programación Lineal implica seleccionar un camino de acción cuando el modelo matemático del problema contiene solo funciones lineales.

SOLUCIÓN GRÁFICA

Podemos resolver un problema de Programación Lineal con 2 variables de decisión utilizando el programa gráfico de solución.

Como deben ser tenidas en cuenta las restricciones de no negatividad, en el gráfico se utilizaremos el primer cuadrante del plano cartesiano, llamado X1 en eje horizontal ( o vertical ) y X2 el vertical ( u horizontal ).

Cada punto ( X1, X2 ) corresponde a una posible solución al cual llamaremos Punto Solución. Para determinar que puntos solución corresponden a soluciones factibles debemos graficar las restricciones del problema, empezando por localizar los puntos que satisfacen la igualdad de cada restricción que denominamos Línea o Recta de Restricción.

Para graficar la primera restricción correspondiente al taller de corte y teñido, tenemos :

42 X1 + 60 X2 <= 37.800

Para X1 igual a cero, X2 es 630 Para X2 igual a cero, X1 es 900

Para la restricción correspondiente al taller de costura, tenemos :

30 X1 + 50 X2 <= 36.000

Para X1 igual a cero, X2 es 720 Para X2 igual a cero, X1 es 1.200

Para la restricción correspondiente al taller de terminado, tenemos :

60 X1 + 40 X2 <= 42.480

Para X1 igual a cero, X2 es 1.072 Para X2 igual a cero, X1 es 708

Para la restricción correspondiente al taller de inspección y embalaje, tenemos:

6 X1 + 15 X2 <= 8.100

Para X1 igual a cero, X2 es 540 Para X2 igual a cero, X1 es 1.350

Como las desigualdades representan regiones debemos determinar que región de la recta incluye los puntos que satisfacen la desigualdad, utilizando la siguiente regla : “ Se toma un punto cualquiera del plano del primer cuadrante que no esté sobre la recta ; si al reemplazar este punto sobre la desigualdad, la satisface, el punto pertenece a la región indicada por la desigualdad. En caso contrario la región es la del lado contrario de la línea. Al final la región factible será aquella, que contenga los puntos que satisfagan simultáneamente a todas las desigualdades.

Gráfico

La región sombreada incluyendo el contorno es la Solución Factible, es decir, cualquier punto ( X1, X2 ) de esta región satisface las restricciones.

Teóricamente tendríamos un número infinito de puntos solución. Nuestra tarea ahora es determinar cual o cuales al ser reemplazados en la función objetivo, nos produce el máximo valor UTILIDAD . Para lograr esto tomemos una utilidad cualquiera (arbitrariamente, por ejemplo $2.160.000) y con ello graficamos la función de la utilidad :

2.160.000 = 10.000 X1 + 9.000 X2

Para X1 igual a cero, X2 es igual a 240 Para X2 igual a cero, X1 es igual a 216

Esta recta obtenida la llamamos de Isoutilidad lo cual nos quiere decir que cualquier punto sobre esta línea tendrá la misma utilidad. De manera similar ocurriría con cualquier recta paralela a ésta, la cual nos permite concluir que la mayor utilidad se produciría en los puntos (vértices) o líneas ( aristas ) de la región factible.

La figura formada por estas aristas y vértices se denomina Polígono de Soluciones Factibles. De esta manera el conjunto infinito de soluciones de las que hablábamos anteriormente se resume a los vértices del polígono o a una arista completa, en caso de que esta arista sea paralela a la línea de Isoutilidad.

El siguiente paso es encontrar los vértices del polígono para ser reemplazados en la función objetivo y de esta forma determinar la solución óptima.

El vértice V0 corresponde al origen donde X1 y X2 son cero, lo cual se refiere a no producir.

El vértice V1, es la intersección de la línea de inspección y embalaje con el eje X2 ( 0 ; 540 ).

El vértice V2 corresponde a la intersección de las líneas de inspección con corte y teñido :

6 X1 + 15 X2 <= 8.100 Inspección y embalaje 42 X1+ 60 X2 <= 37.800 Corte y Teñido

Resolviendo estas dos ecuaciones, obtenemos : Multiplicando la (primera) por 7 y restándola de la (segunda) :

42 X1 + 105 X2 = 56.700 42 X1 + 60X2 = 37.800 45 X2 = 18.900 X2 = 420

Reemplazando 420 tenemos :

42 X1 + 60 (420) = 37.800 42 X1 = 12.600 X1 = 300

V2 ( 300 ; 420 )

De la misma manera podemos encontrar V3 que es el punto de intersección de la línea de corte y teñido con terminado, dando como resultado V3 ( 540 ; 252 )

El vértice V4 es la intersección de la línea terminado con el eje X1 donde V4 (708 ; 0 ) Reemplazando los vértices en la función objetivo obtenemos :

X1 X2 Z

0 0 0 0 540 4.860.000

300 420 6.780.000

540 252 7.668.000 708 0 7.080.000

La mayor Utilidad es de $ 7.668.000 por lo tanto la solución factible óptima es producir 540 billeteras para hombre y 252 billeteras para mujer.

RESUMEN DEL PROCEDIMIENTO GRÁFICO DE SOLUCIÓN PARA PROBLEMAS DE MAXIMIZACIÓN Como hemos visto, el procedimiento gráfico de solución es un método para resolver problemas de Programación Lineal con dos variables, a continuación resumimos los pasos del procedimiento gráfico de solución para problemas de maximización.

Elaborar una gráfica de los puntos solución factible para cada una de las restricciones.

Determinar la región factible identificando los puntos solución que satisfacen todas las restricciones.

Trazar una recta de la función objetivo que muestre los valores de las variables X1 y X2 las cuales proporcionan un valor específico para la función objetivo.

Desplazar rectas de función objetivo paralelas en dirección de los valores más altos de ésta hasta que llegue el momento en que un mayor alejamiento haga que la recta quede por completo fuera de la región factible.

Un punto solución factible que se encuentra sobre la recta de la función objetivo y que tenga el mayor valor es una solución óptima.

SOLUCION POR COMPUTADOR A continuación se presentan las tablas de introducción de datos y despliegue de resultados, utilizando la herramienta computacional WinQSB.

Introducción de Datos

Solución Grafica

Solución Tabular