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.