Investigación de operaciones modelos y aplicaciones de programación lineal

I. LA INVESTIGACIÓN DE OPERACIONES, USO DE MODELOS Y METODOS DE OPTIMIZACION

I.1 INTRODUCCION A LA INVESTIGACIÓN DE OPERACIONES

1. Un poco de Historia

Se inicia desde la revolución industrial, en los libros se dice que fue a partir de la segunda Guerra Mundial. La investigación de operaciones se aplica a casi todos los problemas. En 1947, en EE.UU., George Datzing encuentra el método simplex para el problema de programación lineal. En la investigación de operaciones, las computadoras son la herramienta fundamental en la investigación de operaciones.

2. Definición

La Investigación de Operaciones, es la aplicación del método científico por un grupo multidisciplinario de personas a un problema, principalmente relacionado con la distribución eficaz de recursos limitados (dinero, materia prima, mano de obra, energía), que apoyados con el enfoque de sistemas (este enfoque, es aquel en el que un grupo de personas con distintas áreas de conocimiento, discuten sobre la manera de resolver un problema en grupo.). Puede considerarse tanto un arte como una ciencia. Como arte refleja los conceptos eficiente y limitado de un modelo matemático definido para una situación dada. Como ciencia comprende la deducción de métodos de cálculo para resolver los modelos.

2.1 Pasos del Método científico en IO

1. Definición del problema.- Desde el punto de vista de la Investigación de operaciones(IO),esto indica tres aspectos principales:(a)Una descripción de la meta o el objetivo del estudio,(b)Una Identificación de las alternativas de decisión y (c) Un reconocimiento de las limitaciones, restricciones y requisitos del sistema

2. Construcción del Modelo. Dependiendo de la definición del problema, el equipo de investigación de operaciones deberá decidir sobre el modelo mas adecuado para representar el sistema (modelo matemático, modelo de simulación; combinación de modelos matemáticos, de simulación y heurísticos)

3. Solución del Modelo.- En modelos matemáticos esto se logra usando técnicas de optimización bien definidas y se dice que el modelo proporciona una solución optima. Si se usan los modelos de simulación o heurísticos el concepto de optimalidad no esta bien definido, y la solución en estos casos se emplea para obtener evaluaciones aproximadas de las medidas del sistema

4.Validación del Modelo.- Un modelo es valido si, independientemente de sus inexactitudes al representar el sistema, puede dar una predicción confiable del funcionamiento del sistema

5. Implantación de los resultados Finales.-La tarea de aplicar los resultados probados del sistema recae principalmente en los investigadores de operaciones. Esto básicamente implicaría la traducción de estos resultados en instrucciones de operación detallada, emitidas en una forma comprensible a los individuos que administraran y operaran el sistema después. La interacción del equipo de investigación de operaciones y el personal de operación llegara a su máximo en esta fase.

I.2 TIPOS DE MODELOS DE INVESTIGACION DE OPERACIONES

Un modelo es una representación ideal de un sistema y la forma en que este opera. El objetivo es analizar el comportamiento del sistema o bien predecir su comportamiento futuro. Obviamente los modelos no son tan complejos como el sistema mismo, de tal manera que se hacen las suposiciones y restricciones necesarias para representar las porciones más relevantes del mismo. Claramente no habría ventaja alguna de utilizar modelos si estos no simplificaran la situación real. En muchos casos podemos utilizar modelos matemáticos que, mediante letras, números y operaciones, representan variables, magnitudes y sus relaciones.

Fig.1.2: Representación de un modelo

1. Modelos Matemáticos

Un modelo es producto de una abstracción de un sistema real: eliminando las complejidades y haciendo suposiciones pertinentes, se aplica una técnica matemática y se obtiene una representación simbólica del mismo.  Un modelo matemático consta al menos de tres conjuntos básicos de elementos:

• Variables de decisión y parámetros

Las variables de decisión son incógnitas que deben ser determinadas a partir de la solución del modelo. Los parámetros representan los valores conocidos del sistema o bien que se pueden controlar.

• Restricciones

Las restricciones son relaciones entre las variables de decisión y magnitudes que dan sentido a la solución del problema y las acotan a valores factibles. Por ejemplo si una de las variables de decisión representa el número de empleados de un taller, es evidente que el valor de esa variable no puede ser negativo.

• Función Objetivo

La función objetivo es una relación matemática entre las variables de decisión, parámetros y una magnitud que representa el objetivo o producto del sistema. Por ejemplo si el objetivo del sistema es minimizar los costos de operación, la función objetivo debe expresar la relación entre el costo y las variables de decisión. La solución ÓPTIMA se obtiene cuando el valor del costo sea mínimo para un conjunto de valores factibles de las variables. Es decir hay que determinar las variables x1, x2,…, xn que optimicen el valor de Z = f(x1, x2,…, xn) sujeto a restricciones de la forma g(x1, x2,…, xn) ? b. Donde x1, x2,…, xn son las variables de decisión Z es la función objetivo, f es una función matemática.

EJEMPLO 1.2.1: Sean X1 y X2 la cantidad a producirse de dos productos 1 y 2, los parámetros son los costos de producción de ambos productos, $3 para el producto 1 y $5 para el producto 2. Si el tiempo total de producción esta restringido a 500 horas y el tiempo de producción es de 8 horas por unidad para el producto 1 y de 7 horas por unidad para el producto 2, entonces podemos representar el modelo como: 

MinZ = 3X1 + 5X2 (Costo total de Producción)

Sujeto a (S.A):

8X1 + 7X2 ?  500 (Tiempo total de producción)

X1, X2>= 0 (Restricciones de no negatividad)

EJEMPLO 1.2.2: En una empresa se fabrican dos productos, cada producto debe pasar por una máquina de ensamblaje A y otra de terminado B,antes antes de salir a la venta.El producto 1 se vende a $60 y el otro a $50 por unidad. La siguiente tabla muestra el tiempo requerido por cada producto:

Para representar el modelo de este problema primero se debe determinar las variables de decisión: Sea Xi: La cantidad a fabricar del producto 1 y 2 (i=1,2), entonces X1: cantidad a fabricar del producto 1, X2: cantidad a fabricar del producto2, luego el modelo quedaría de la siguiente manera:

MaxZ = 60X1+ 50X2 (máximo ingreso por ventas)

S.A: 2X1+ 4X2 <= 48 (disponibilidad horas _maquina A)

3X1+ 2X2 <= 36 (disponibilidad horas _maquina B)

X1, X2 >= 0 (Restricciones de no negatividad)

2. Modelos de Simulación

La simulación es una técnica para crear modelos de sistemas grandes y complejos que incluyen incertidumbre. Se diseña un modelo para repetir el comportamiento del sistema. Este tipo de modelamiento se basa en la división del sistema en módulos básicos o elementales que se enlazan entre sí mediante relaciones lógicas bien definidas (de la forma SI / ENTONCES). El desarrollo de un modelo de simulación es muy costoso en tiempo y recursos.

II. PROGRAMACION LINEAL

II.1 INTRODUCCION A LA PROGRAMACION LINEAL

1. INTRODUCION

La programación Lineal (PL) es una técnica de modelado matemático, diseñada para optimizar el empleo de recursos limitados. La programación lineal se aplica exitosamente en el ejercito, en la agricultura, la industria, los transportes, la economía, los sistemas de salud, en el ejercito e incluso en los sistemas conductuales y sociales.

La utilidad de esta técnica se incrementa mediante el uso y disponibilidad de programas de computadora altamente eficientes. De hecho la PL, debido a su alto nivel de eficiencia computacional, es la base para el desarrollo de algoritmos de solución de otros tipos (más complejos) de modelos de IO, incluyendo la programación entera, no lineal y estocástica.

2. MODELOS DE PROGRAMACION LINEAL

Para formular un problema de programación lineal se debe tener presente que la función objetivo y todas las restricciones deben ser lineales y todas las variables deben ser continuas (pueden asumir valores fraccionales).

2.1 SOLUCIÓN GRAFICA DE PL: Los modelos de PL que se resuelven por el método geométrico o grafico solo son apropiados para casos en que el número de variables son a lo más dos.

EJEMPLO 2.1.1: UN PROBLEMA DE MINIMIZACION (Contratación de Personal): El departamento de control de calidad de la empresa Gerconsa S.A que fabrica autopartes, desea contratar personal tanto senior como junior, para las inspecciones de sus productos.

El personal senior recibe por su jornada de 8hrs., $188y realiza su labor a una tasa promedio de 30 inspecciones por hora, con un rendimiento del 99%.en cambio el personal junior, recibe $150 por su jornada, realizando 25 inspecciones por hora, con un rendimiento del 95%.

La demanda diaria de inspecciones es de 1600 unidades y el personal senior a contratar, no debe ser mayor que el personal júnior.

Si las ensambladoras aplican una multa de $5 por cada unidad defectuosa, ¿cuánto de personal senior y júnior, se debe contratar?

SOLUCION:

La formulación del modelo al problema de minimización seria:

Sea Xi: Numero de personal a contratar (i = senior, j = junior o

i =1,2)

La función objetivo consistiría en minimizar los costos de salario y los de castigo por unidad defectuosa

Z = Salario + Multa

Salario = 118×1+ 150×2

Multa = (30*8*0.01X1+ 25*8*0.05X2)*5

Luego la función objetivo es:

MinZ = 200X1+ 200X2 y sujeta a las restricciones:

30(8) X1+25(8) X2>=1600 (Demanda diaria)

X1<= X2 (Relación personal)

Finalmente el modelo se reduce a:

MinZ = 200X1 + 200X2

S.A.: 6X1+ 5X2 >=40 (1)

X1 – X2 <=0 (2)

X1, X2 >=0

Gráficamente y después de haber utilizado el amigable software TORA el problema quedaría así:

Fig.2.1: Solución grafica (optima) al problema de contratación de personal

Este modelo pudo haberse resuelto fácilmente graficando en las coordenadas X1 y X2 y hallando el punto de intersección común a ambas rectas. Se puede ver que la intersección de recta de la función objetivo con las rectas 1 y 2 lo hace dentro de la región factible y en su punto mínimo (punto optimo), después de haber resuelto algebraicamente por sistemas de ecuaciones simultaneas las restricciones 1 y 2 tenemos finalmente el punto optimo mínimo para el problema:

X1=3.64

X2=3.64

Z*=1454.55

De los resultados puede verse que tenemos valores fraccionarios para un problema de contratación de personal lo cual es inapropiado dado que se trata del recurso humano, sin embargo solo se ha resuelto para efecto demostrativo grafico (además no olvidemos que en PL las variables son continuas), ya que la programación lineal entera se encarga de darle una solución Optima a este problema.

EJEMPLO 2.1.2: UN PROBLEMA DE MAXIMIZACION. Javier Cutipe es un exitoso vendedor de la distribuidora de gaseosas Gerconsa y tiene que decidir como asignar sus esfuerzos entre los diferentes tipos de clientes de las zonas de Moquegua que le han dado (san Antonio, san francisco, la villa los ángeles, samegua, y chen chen).Puede visitar comerciantes y clientes que compran al menudeo. Una visita a un comerciante usualmente le produce S/.400 en ventas, pero la visita en promedio dura 2horas y debe manejar también en promedio, 10 kilómetros. En una visita a un comprador al menudeo le vende S/.500 y requiere de unas 3horas y 20 kilómetros manejando el carro aproximadamente. Javier viaja trabajando como máximo, 600kilometros por semana en su propio carro y prefiere trabajar nomás de 36 horas por semana. Construya un modelo de programación lineal para Javier Cutipe Mamani

SOLUCION:

Sea: X1: Numero de comerciantes

X2: Numero de clientes al menudeo

El modelo resultante es:

Max Z= 400X1+500X2 (Ingreso por ventas brutas)

S.A: 2X1+3X2 <= 36 (restricción de horas semanales) (1)

10X1+20X2<=600 (restricción de distancia recorrida) (2)

X1,X2>=0 (Restricción de no negatividad)

Fig.2.2: Solución grafica (optima) al problema de Javier Cutipe

El modelo anterior se resuelve gráficamente aplicando Tora, también pudo haberse resuelto fácilmente graficando en las coordenadas X1 y X2 y hallando el punto de intersección común a la recta (1) con el eje X1, la recta de la función objetivo alcanza su nivel máximo (punto optimo) en la región factible para X1=18 y X2=0, esto algebraicamente es después de haber resuelto la restriccion1 (ecuacion1) y haciendo x2=0 en la misma ecuación

(nótese que la restricción 2 es redundante). Finalmente el punto óptimo mínimo para el problema es de:

X1=18

X2=0

Z*= S/.7200

Este resultado nos dice que Javier Cutipe deberá concentrar sus esfuerzos solo en la venta a 18 comerciantes dado que alli maximizara sus ingresos por ventas en S/.7200

2.2 SOLUCIÓN POR COMPUTADORA DE PROBLEMAS DE PL

En la practica, donde los modelos típicos de programación Lineal implican cientos, o incluso miles de variables y restricciones, la única forma de resolver estos problemas es utilizando un programa apropiado de computadora. En el mercado informático existen softwares que tienen módulos de programación lineal (PL) tal como el Tora, Storm, Programas como el lindo, lingo, etc. También se puede hacer uso de Solver en Excel para resolver problemas de PL.

EJEMPLO 2.2.1: La figura 2.3 presenta la solución de TORA para el problema de contratación de personal del ejemplo 2.1.1

Fig.2.3: Solución óptima usando TORA

La información de salida se divide en dos partes principales (1) resumen de la solución óptima (optimum solution sumary) que comprende los valores óptimos de las variables de decisión y el valor optimo de la función Objetivo y (2) Análisis de sensibilidad (Sensitivity análisis) referente a hacer cambios en el lado derecho(right-and sides) y en los coeficientes de la función objetivo

EJEMPLO 2.2.2: La figura 2.4 presenta la solución de LINDO para el problema de Javier Cutipe del ejemplo 2.1.2

LP OPTIMUM FOUND AT STEP 1

OBJECTIVE FUNCTION VALUE

1) 7200.000

VARIABLE VALUE REDUCED COST

X1 18.000000 0.000000

X2 0.000000 100.000000

ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 200.000000

3) 420.000000 0.000000

NO. ITERATIONS= 1

RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES

VARIABLE CURRENT ALLOWABLE ALLOWABLE

COEF INCREASE DECREASE

X1 400.000000 INFINITY 66.666664

X2 500.000000 100.000000 INFINITY

RIGHTHAND SIDE RANGES

ROW CURRENT ALLOWABLE ALLOWABLE

RHS INCREASE DECREASE

2 36.000000 84.000000 36.000000

3 600.000000 INFINITY 420.000000

Fig.2.4: Solución óptima usando LINDO

2.3 ANALISIS DE ALGUNOS MODELOS DE PL: Se presentan algunos modelos realistas de de PL, en los cuales las definición de variables y la construcción de la función objetivo y de las restricciones no son tan directas como en el caso de los modelos de dos variables. Además la salida de TORA de la computadora para cada modelo permitirá interpretaciones muy claras de las soluciones.

EJEMPLO 2.3.1: Un distribuidor de ferretería planea vender paquetes de tuercas y tornillos mezclados. Cada paquete pesa por lo menos 2 libras. Tres tamaños de tuercas y tornillos componen el paquete y se compran en lotes de 200 libras. Los tamaños 1 ,2 y 3 cuestan respectivamente $20, $80 y $12, además:

a. El peso combinado de los tamaños 1y 3 debe ser al menos la mitad del peso total del paquete

b. El peso de los tamaños 1 y 2 no debe ser mayor que 1,6 libras

c. Cualquier tamaño de tornillo debe ser al menos 10 porciento del paquete total

¿Cuál será la composición del paquete que ocasionara un costo mínimo? (formule solamente el modelo de pl.)

SOLUCION:

Formulación

Sea : X1 = peso de las unidades de tamaño 1

X2 = peso de las unidades de tamaño 2

X3 = peso de las unidades de tamaño 3

De este modo se tendrán las siguientes Restricciones:

X1+ X2+ X3 >=2 peso mínimo de cada paquete

X1 +X3 >= (X1+ X2+ X3)/2 Peso combinado d e l os tamaños 1 y 3

X1+ X2 <=1.6 Peso combinado de 1 y 2

X1>=0.10(X1+ X2+ X3) Condición de peso para cualquier tamaño

X2>=0.10(X1+ X2+ X3)

X3>=0.10(X1+ X2+ X3)

Siendo la función MinZ = 20X1+ 80X2+ 12X3)/200, en resumen se tiene el siguiente modelo:

MinZ = 0.1X1+0.04X2+0.06X3

S.A: X1+ X2+ X3 >= 2

X1 – X2+ X3 >=0

X1+ X2 <=1.6

0.9X1-0.1X2-0.1X3 >=0

-0.1X1+0.9X2-0.1X3 >=0

-0.1X1-0.1X2+0.9X3 >=0

X1, X2, X3 >=0

Fig.2.5: Solución óptima usando TORA

Del resultado del sotware Tora se puede ver que la solución optima es :

X1* = 0.20

X2* = 1.00

X3* = 0.80

Z*= 0.11

EJEMPLO 2.3.2: Al mezclar diferentes hidrocarburos se obtiene gasolina de diferentes grados. En este ejemplo se supone que una refinería dispone sólo de dos tipos de gasolina cuyas características se presentan en la siguiente tabla:

 Con la combinación de estos productos se pueden producir dos tipos de gasolina: para automóvil y aviación. Las cualidades de estos productos aparecen en la siguiente tabla:

El octanaje y la presión de vapor del producto resultante es proporcional a la cantidad de cada gasolina utilizada en la mezcla.

Por ejemplo para partes iguales de ambas gasolinas:

Octanaje: 0.5*104 + 0.5*94 = 99

Presión de vapor: 0.5*5 + 0.5*9 = 7

La empresa desea maximizar los ingresos por la venta de gasolina como producto final

Formulación

Sean x1 el número de barriles de gasolina del tipo 1 para aviación.

X2 el número de barriles de gasolina del tipo 2 para aviación.

X3 el número de barriles de gasolina del tipo 1 para automóvil.

X4 el número de barriles de gasolina del tipo 2 para automóvil.

La venta correspondiente a gasolina para aviación es 45.10*(x1 + x2) y la venta correspondiente a gasolina para automóvil es 32.40(x3 + x4) entonces la función objetivo es:

Maximizar:

Z = 45.10×1 + 45.10×2 + 32.40×3 + 32.40×4

Existen varias restricciones:

Demanda de gasolina para aviación:

X1 + x2 ? 20,000

Cantidad disponible por tipo de gasolina:

X1 + x3 ? 30,000

X2 + x4 ? 70,000

Restricción de octanaje:

Aviación: (104×1 + 94×2)/(x1 + x2) ? 102 ? 2×1 – 8×2 ? 0

Automóvil: (104×3 + 94×4)/(x3 + x4) ? 96 ? 8×3 – 2×4 ? 0

Restricción de presión de vapor:

Aviación: (5×1 + 9×2)/(x1 + x2) ? 6 ? -x1 + 3×2 ? 0

Automóvil: (5×3 + 9×4)/(x3 + x4) ? 8 ? -3×3 + x4 ? 0

No negatividad:

X1, x2, x3, x4 ? 0

En Resumen el modelo se presenta de la siguiente manera:

MaxZ = 45.10×1 + 45.10×2 + 32.40×3 + 32.40×4

X1 + x2 ? 20,000 Demanda de gasolina para aviación:

X1 + x3 ? 30,000 Cantidad disponible por tipo de gasolina

X2 + x4 ? 70,000 Cantidad disponible por tipo de gasolina

2×1 – 8×2 ? 0 Restricción de octanaje aviación

8×3 – 2×4 ? 0 Restricción de octanaje automóvil

-x1 + 3×2 ? 0 Restricción de presión de vapor aviación

-3×3 + x4 ? 0 Restricción de presión de vapor automóvil:

X1, x2, x3, x4 ? 0 Restricción de no negatividad

Una vez Formulado el modelo matemático hacemos uso del TORA para encontrar una solución óptima:

X1*=16000.00

X2*=4000.00

X3*=4666.67

X4*=14000.00

Z*= 1506800.00

Fig.2.6: Solución óptima usando TORA

III. EL METODO SIMPLEX

La idea general del método Simplex es comenzar en un punto extremo y desplazarse hacia un punto extremo adyacente con el objeto de mejorar el valor de la función objetivo, manteniendo la factibilidad. La manera más sencilla de seleccionar un punto extremo inicial es usar la base B constituida por variables de holgura y/o artificiales. De esta forma la base B inicial es la matriz identidad I que obviamente es una base. Los puntos extremos adyacentes se determinan intercambiando un vector de B con un vector no básico que moverá la solución hacia la optimalidad.

 Tabla Simplex en forma matricial

Expresemos el programa lineal en forma matricial: 

Max z = CX

Sujeto a: (AI)X = b

X >= 0

Subdividamos el vector X en XI y XII, entonces el problema estándar se puede escribir de la siguiente manera: (I)

En una iteración cualquiera, sea XB La representación de las variables básicas y B su base asociada, entonces XB representa a m elementos de X y B representa los vectores de (AI) correspondientes a XB, y sea CB el vector de elementos de C asociado a XB.

Entonces:

B XB = b y z = CBXB

o bien:

La solución se puede expresar:

Por lo tanto, aplicando este resultado, premultiplicando a (I) se obtiene

Esta ecuación matricial se resuelve mediante la iteración simplex general (II):

Esta tabla muestra los detalles del cálculo del método simplex, es decir, si se conoce B se puede encontrar en cada paso B-1, por lo tanto XB y z.

 Por ejemplo consideremos el método simplex con variables de holgura, en este caso, CII = 0 la solución básica inicial se identifica como:

XB = XII, CB = CII = 0, B = I, B-1 = I

Sustituyendo en (II) se obtiene el método simplex general con variables de holgura (III):

 Si utilizamos simplex con variables artificiales (variables utilizadas como variables de holgura para las restricciones que no cumplen la forma estándar). En este caso CII = (-M,-M,…, -M) (coeficientes de penalización para la función objetivo). La solución básica inicial se puede expresar como:

XB = XII, CB = CII, B = I, B-1 = I

Sustituyendo en (II) se obtiene el método simplex general con variables artificiales y de holgura (IV):

 EJEMPLO 3.1:

Max z = 3×1 + 10×2

Sujeto a:

X1 + 4×2 <= 8

X1 + 2×2 <= 4

X1, x2 >= 0

Forma típica:

Z -3×1 – 10×2 = 0

X1 + 4×2 + h1 = 8

X1 + 2×2 + h2 = 4

X1, x2, h1, h2 >=0

Por inspección entra x2 y puede salir tanto h1 como h2, escojamos arbitrariamente h1 y cambiemos x2 por h1.

Primera iteración:

La solución básica después de la primera iteración es

X1 = 0, x2 = 2, h1 = 0, h2 = 0

• Al ser h2, variable básica, h2 = 0, se dice que es solución degenerada, es posible que el método itere sin llegar a la solución optima.

Segunda iteración:

De la tabla anterior, entra x1 y sale h2:

La función objetivo no se ha incrementado, un problema puede ser temporalmente degenerado y luego encontrar la solución óptima.