El modelo de transporte busca determinar un plan de transporte de una mercancía de varias fuentes a varios destinos. Los datos del modelo son:
1. Nivel de oferta en cada fuente y la cantidad de demanda en cada destino.
2. El costo de transporte unitario de la mercancía a cada destino.
Como solo hay una mercancía un destino puede recibir su demanda de una o más fuentes. El objetivo del modelo es el de determinar la cantidad que se enviará de cada fuente a cada destino, tal que se minimice el costo del transporte total.
La suposición básica del modelo es que el costo del transporte en una ruta es directamente proporcional al numero de unidades transportadas. La definición de “unidad de transporte” variará dependiendo de la “mercancía” que se transporte.
El esquema siguiente representa el modelo de transporte como una red con m fuentes y n destinos. Una fuente o un destino esta representado por un nodo, el arco que une fuente y un destino representa la ruta por la cual se transporta la mercancía. La cantidad de la oferta en la fuente i es ai, y la demanda en el destino j es bj. El costo de transporte unitario entre la fuente i y el destino j es Cij.
Si Xi j representa la cantidad transportada desde la fuente i al destino j, entonces, el modelo general de PL que representa el modelo de transporte es:
Minimiza Z= S i=1 m S j=1n C i j X i j
Sujeta a:
S j=1n X i j <= ai , i=1,2,…, m
S i=1m X I j >= bj , j=1,2,…, n
X i j >=0 para todas las i y j
El primer conjunto de restricciones estipula que la suma de los envíos desde una fuente no puede ser mayor que su oferta; en forma análoga, el segundo conjunto requiere que la suma de los envios a un destino satisfaga su demanda.
El modelo que se acaba de escribir implica que la oferta total Si=1m ai debe ser cuando menos igual a la demanda total Sj=1n bj. Cuando la oferta total es igual a la demanda total, la formulación resultante recibe el nombre de modelo de transporte equilibrado. Este difiere del modelo solo en el hecho de que todas las restricciones son ecuaciones, es decir:
SX i j = ai, i=1,2,…, m
SX i j = bj, j=1,2,…, n
En el mundo real, no necesariamente la oferta debe ser igual a la demanda o mayor que ella. Sin embargo, un modelo de transporte siempre puede equilibrarse. El equilibrio, además de su utilidad en la representación a través de modelos de ciertas situaciones prácticas, es importante para el desarrollo del método de solución que explote completamente la estructura especial del modelo de transporte. Los dos ejemplos que siguen presentan la idea del equilibrio y también sus implicaciones prácticas.
Ejemplo 1 (Modelo de transporte estándar)
MG Auto Company tiene plantas en Los Ángeles, Detroit y Nueva Orleáns. Sus centros de distribución principales son Denver y Miami. Las capacidades de las plantas durante el trimestre próximo son 1 000, 1 500, y 1 200 automóviles. Las demandas trimestrales en los dos centros de distribución son de 2 300 y 1 400 vehículos. El costo del transporte de un automóvil por tren es de 8 centavos por milla. El diagrama de las distancias recorridas entre las plantas y los centro de distribución son:
Denver
Miami
Los Ángeles
1 000
1 690
Detroit
1 250
1 350
Nueva Orleans
1 275
850
Esto produce en costo por automóvil a razón de 8 centavos por milla recorrida. Produce los costos siguientes (redondeados a enteros), que representan a C i j del modelo original:
Denver
Miami
Los Ángeles
80
215
Detroit
100
108
Nueva Orleans
102
68
Mediante el uso de códigos numéricos que representan las plantas y centros de distribución, hacemos que X i j represente el número de automóviles transportados de la fuente i al destino j. Como la oferta total ( = 1 000 + 1 500 + 1 200 = 3 700) es igual a la demanda ( = 2 300 + 1 400 = 3 700), el modelo de transporte resultante esta equilibrado. Por lo tanto, el siguiente modelo de PL que representa el problema tiene todas las restricciones de igualdad.
Un método mas resumido para representar el modelo de transporte consiste en utilizar lo que se llama tabla de transporte. Esta es una forma de matriz donde sus renglones representan las fuentes y sus columnas los destinos. Los elementos de costo C i j se resumen en la esquina noroeste de la celda de la matriz (i, j). Por lo tanto, el modelo de MG se puede resumir en la tabla siguiente:
Ejemplo 2 (Modelo de transporte con equilibrio)
En el ejemplo anterior suponga que la capacidad de la planta de Detroit es de 1 300 automóviles (en vez de 1 500). Se dice que la situación esta desequilibrada debido a que la oferta total (=3 500) no es igual a la demanda total (=3 700).Nuestro objetivo consiste en volver a formular el modelo de transporte de manera que distribuya la cantidad faltante(=3 700 – 3 500 = 200) en forma optima entre los centros de distribución.
Como la demanda es mayor que la oferta se puede agregar una planta ficticia con una capacidad de 200. Se permite que dicha planta, en condiciones normales, envíe su “producción“ a todos los centros de distribución. Físicamente, la cantidad de unidades enviadas a un destino desde una planta ficticia representará la cantidad faltante en ese destino.
La única información que falta para completar el modelo son los “costos de transporte” unitarios de la planta ficticia a los destinos. Como la planta no existe, no habrá ningún envío físico y el costo de transporte unitario es cero. Sin embargo, podemos enfocar la situación desde otro ángulo diciendo que se incurre en un costo de penalización por cada unidad de demanda insatisfecha en los centros de distribución. En este caso los costos de transporte unitarios serán iguales a los costos de penalización unitarios en los diversos destinos.
Denver
Miami
Los Ángeles
80
215
1 000
Detroit
100
108
1 300
Nueva Orleáns
102
68
1 200
Planta ficticia
0
0
200
De manera análoga, si la oferta en mayor que la demanda podemos añadir un destino ficticio que absolverá la diferencia. Por ejemplo, suponga que la demanda en Denver disminuye a 1 900cualquier automóvil enviado de una planta a un centro de distribución ficticio representa un excedente en la planta.
Denver
Miami
Destino
Ficticio
Los Ángeles
80
215
0
1 000
Detroit
100
108
0
1 500
Nueva Orleans
102
68
0
1 200
La aplicación del modelo de transporte no se limita al problema de “transporte”.
El siguiente ejemplo ilustra el uso del modelo del transporte en otros campos.
Ejemplo 3 (Modelo de inventario de producción)
Una compañía construye una planta maestra para la producción de un articulo en un periodo de cuatro meses. Las demandas en los cuatro meses son: 100, 200, 180 y 300 unidades. Una demanda para el mes en curso puede satisfacerse a través de:
1. Producción excesiva en un mes anterior almacenada para su consumo posterior.
2. Producción en el mes actual.
3. Producción excesiva en un mes posterior para cubrir pedidos de meses anteriores.
El costo de producción variable por unidad en un mes cualquiera es de $4.00. una unidad producida para consumo posterior incurrirá en un costo de almacenamiento razón de $0.50 por unidad por mes. Por otra parte, los artículos ordenados en meses anteriores incurren en un costo de penalización de $2.00 por unidad por mes. La capacidad de producción para elaborar el producto varía cada mes. Los cálculos de los cuatro meses siguientes son 50, 180, 280 y 270 unidades, respectivamente.
El objetivo es el de formular el plan de inventario de producción a costo mínimo. Este problema se puede formular como un modelo de “transporte”. La equivalencia entre los elementos de los sistemas de producción y transporte se establece de la manera siguiente:
Sistema de Transporte
Sistema de Producción
1. Fuente i
1. Periodo de producción i
2. Destino j
2. Periodo de demanda j
3. Oferta en la fuente i
3. Capacidad de producción del periodo i
4. Demanda en el destino j
4. Demanda del periodo j
5. Costo de transporte de la fuente i al destino j
5. Costo de producto e inventario del periodo i al j
En tabla de abajo se presenta un resumen del problema como un modelo de transporte:
Periodo
1
2
3
4
Capacidad
Demanda
1
4
4.5
5
5.5
50
2
6
4
4.5
5
180
3
8
6
4
4.5
280
4
10
8
6
4
270
Demanda:
100
200
180
300
El costo de “transporte” unitario del periodo i al j es:
Costo de producción en i, i=j
C i j = Costo de producción en i / costo de almacenamiento en i a j i<j
Costo de producción en i / costo de penalización en i a j i>j
La definición de C i j indica que la producción en el periodo i para el mismo periodo (i = j) sólo iguala el costo unitario de producción. Si el periodo i se produce para periodos futuros j (i < j), se incurre en un costo de almacenamiento adicional. De la misma manera, la producción en i para cubrir j pedidos hechos con anterioridad (i > j) incurre en un costo de penalización adicional.
PROBLEMAS DE ASIGNACIÓN (Método Hungaro)
Un problema de asignación es un problema de transporte balanceado, en el cual todas las ofertas y todas las demandas son iguales a uno. Se puede resolver eficientemente un problema de asignación m x m mediante el método Húngaro:
o Paso 1.– Empiece por encontrar el elemento mas pequeño en cada renglón de la matriz de costos. Construya una nueva matriz, al restar de cada costo, el costo mínimo de su renglón. Encuentre, para esta nueva matriz el costo mínimo en cada columna. Construya una nueva matriz ( la matriz de costos reducidos ) al restar de cada costo el costo mínimo de su columna.
o Paso 2.– Dibuje el mínimo numero de líneas (horizontales o verticales ) que se necesitan para cubrir todos los ceros en la matriz de costos reducidos. Si se requieren m líneas para cubrir todos los ceros, siga con el paso 3.
o Paso 3.– Encuentre el menor elemento no cero (llame su valor k en la matriz de costos reducidos, que no esta cubiertos por las líneas dibujadas en el paso 2. Ahora reste k de cada elemento no cubierto de la matriz de costos reducidos y sume k a cada elemento de la matriz de costos reducidos cubierto por dos líneas. Regrese al paso 2.
Un problema de asignación es un problema de transporte balanceado en el que todas las ofertas y demandas son iguales a 1; así se caracteriza por el conocimiento del costo de asignación de cada punto de oferta a cada punto de demanda. La matriz de costos del problema de asignación se llama: matriz de costos.
Como todas las ofertas y demandas para el problema de asignación son números enteros, todas las variables en la solución óptima deben ser valores enteros.
EJEMPLOS DE PROBLEMAS DE ASIGNACION
1. Una empresa ha contratado a 4 individuos para 4 trabajos, los 4 individuos y 4 trabajos pueden mostrarse en una tabla que indique las clasificaciones obtenidas, analizando al individuo para cada trabajo. Los renglones se refieren a los hombres, mientras que las columnas se refieren a los trabajos; el problema consiste en maximizar las calificaciones para asignar los 4 trabajos.
Se supone que las calificaciones de un individuo es directamente proporcional a la ganancia que obtendría la compañía si ese individuo se encargara del trabajo.
2. Otro problema que utiliza la misma estructura del modelo de transporte, es la asignación de camiones para reducir al mínimo los costos de un problema de asignación.
3. Una empresa cubre el territorio nacional con dos camiones especialmente equipados para funcionar en condiciones climatológicas específicas. La empresa ha dividido en cinco regiones geográficas. Se compra el camión A y se modifica para que funcione eficientemente en las regiones uno y dos, y para que funcione bastante bien en las regiones tres y cuatro. El mismo camión no funciona bien en la región cinco. Los gastos de gasolina, mantenimiento y otros costos directos de operación, serían mínimos en las regiones uno y dos, promedio en las regiones tres y cuatro, y altos en la región cinco. Se tiene esa misma información con respecto a los demás camiones de la compañía, o sea, los tipos B, C y D.
SOLUCION DEL PROBLEMA DE TRANSPORTE.
En esta sección presentamos los detalles para resolver el modelo de transporte.
TECNICA DE TRANSPORTE.
Los pasos básicos de la técnica de transporte son:
Paso 1: determínese una solución factible.
Paso 2: determínese la variable que entra, que se elige entre las variables no básicas. Si todas estas variables satisfacen la condición de optimidad (del método simplex), deténgase; de lo contrario, diríjase al paso 3.
Paso 3: determínese la variable que sale (mediante el uso de la condición de factibilidad) de entre las variables de la solución básica actual; después obténgase la nueva solución básica. Regrese al paso 2.
OBTENCIÓN DE SOLUCIONES BÁSICAS FACTIBLES PARA PROBLEMAS DE TRANSPORTES
Podemos obtener una solución básica factible (sbf) para un problema de transporte balanceado mediante el método de la esquina Noroeste, el método de costo mínimo, o el método de Vogel.
Para obtener una sbf mediante el método de la esquina noroeste, empiece en la esquina superior izquierda del cuadro del transporte y haga a X11 lo más grande posible.
Naturalmente, X11 no puede ser mayor que el menor valor Si y así X11 S1 tache el primer renglón del cuadro de transporte; Esto indica que si habrá más variables básicas del renglón 1 del cuadro. También d1-S1 . Si X11=d1, tache la primera la columna del cuadro de transporte y cambie S1 – d1.
Si X11= S1 = d1, tache o el renglón 1, o la columna 1 (pero no ambos), del cuadro de transporte. Si tacha el renglón 1, cambie d1 por cero; si tacha columna 1, cambie S 1 por 0.
Continúe aplicando este procedimiento a la celda mas noroeste del cuadro que no cae en un renglón eliminado o en una columna eliminada.
Finalmente, llegara un momento en el cual solo queda una celda a la cual se puede asignar un valor.
Asigne a esta celda un valor igual a la oferta de su renglón o a la demanda de su columna, y tache el renglón y la columna de la celda. Se obtiene de esta manera una solución básica factible.
OBTENER LA SOLUCIÓN ÓPTIMA PARA UN PROBLEMA DE TRANSPORTE
q Paso 1: Si el problema no está balanceado, balancéelo.
q Paso 2: Utilice uno de los métodos descritos anteriormente para obtener una solución básica factible.
q Paso 3: Utilice el hecho de que U1=0, y Ui+Vj=Cij en todas las variables básicas para encontrar (U1,U2…Um V1,V2…Vn) para la sbf actual.
q Paso 4: Si Ui + Vj – Cij es menor o igual a cero, para todas las variables no básicas, entonces la sbf actual es óptima. Si no es así se introduce la variable con valor más positivo de Ui + Vj –Cij en la base. Para hacer esto, encuentre un circuito cerrado (se puede demostrar que solamente existe un circuito cerrado) que contiene la variable que entra y algunas de las variables básicas. Después, tomando en cuenta solamente las celdas en el circuito cerrado marque las que se encuentren alejadas en número par (0,2,4,6,…) de celdas de la variable que entra como celdas pares. También marque las celdas en el circuito cerrado, que se encuentra un número impar de celdas de la variable que entra como celdas impares. Ahora encuentre la celda impar cuya variable toma el menor valor. Llame este valor teta. La variable correspondiente a esta celda impar saldrá de la base. Para realizar el pivoteo, disminuye el valor de cada celda impar en teta y aumenta el valor de cada celda par en teta. Los valores de las variables que no se encuentran en el circuito cerrado permanecen sin cambio. Ahora se completó el bloqueo.
Sí teta es igual a cero, la variable que entra será igual a cero, y una variable impar que tiene un valor actual de cero, saldrá de la base. En este caso, existía un sbf degenerada antes del pivoteo y resultará después del pivoteo.
Si más de una celda impar en el circuito cerrado es igual a teta. Puede escoger arbitrariamente una de estas celdas impares para que salga de la base; se obtendrá una vez más una sbf degenerada. El pivoteo produce una nueva sbf.
q Paso 5: Regrese a los pasos 3 y 4, utilizando la nueva sbf. Para un problema de maximización, proceda como se especificó, pero cambie el paso 4 por el paso 4’.
q Paso 6: Si Ui + Vj –Cij es mayor o igual a cero, para todas las variables no básicas, entonces, la sbf actual es óptima. De otra manera, coloque la variable con el valor más negativo de Ui + Vj – Cij en la base mediante el procedimiento de pivoteo.
METODO DE ESQUINA NOROESTE
Determinación general del modelo de transporte requiere que:
m n
å ai = å bj
i=1 j = 1
Este requisito da origen a una ecuación dependiente, lo que significa que el modelo de transporte tiene sólo m + n –1 ecuaciones independientes. Por lo tanto, como en el método simplex, una solución factible básica inicial debe incluir m + n – 1 variables básicas.
Normalmente, si el modelo de transporte se formula como una tabla simplex, sería necesario utilizar variables artificiales para asegurar una solución básica inicial. Sin embargo, cuando se utiliza la tabla de transporte, una solución factible básica inicial se puede obtener fácil y directamente. Presentamos un procedimiento llamado regla de la esquina noroeste para este fin.
Destino
1
2
3
4
Oferta
Fuente
1
10
0
20
11
15
X11
X12
X13
X14
2
12
7
9
20
25
X21
X22
X23
X24
3
0
14
16
18
5
X31
X32
X33
X34
Demanda
5
15
15
10
El método de la esquina noroeste comienza con la asignación de la máxima cantidad admisible através de la oferta y la demanda de la variable x11 (la de la esquina noroeste de la tabla). Después se tacha la columna (renglón) satisfecha, lo que indica que las variables restantes de la columna (renglón) tachada son iguales a cero. Si se satisfacen una columna y un renglón al mismo tiempo, sólo una (una u otro) puede ser tachado. (Esta condición garantiza la ubicación automática de variables básicas cero, si las hay). Después de ajustar las cantidades de oferta y demanda de todos los renglones y columnas no tachados, la cantidad factible máxima se asigna al primer elemento no tachado de la nueva columna (renglón). El proceso se completa cuando se deja sin tachar exactamente un renglón o una columna.
El procedimiento que se acaba de describir se aplica ahora en el ejemplo:
1. x11 = 5, se tacha la columna 1. Por lo tanto, no se puede hacer otra asignación en la columna 1. La cantidad que falta en el renglón 1 son 10 unidades.
2. x12 = 10, se tacha el renglón 1 y faltan 5 unidades en la columna 2.
3. x22 = 5, se tacha la columna 2 y faltan 20 unidades en el renglón 2.
4. x23 = 15, se tacha la columna 3 y faltan 5 unidades en el renglon 2.
5. x24 = 5, se tacha el renglón 2 y faltan 5 unidades en la columna 4.
6. x34 = 5, se tacha el renglón 3 o la columna 4. Como sólo un renglón ouna columna se mantiene sin tachar, el proceso llega a su fin.
La solución básica inicial resultante se presenta a continuación.
Las variables básicas son x11 = 5, x22 =10, x23 =15, x24 =5 y x34 = 5. Las variables restantes son no básicas en el nivel cero. El costo de transporte asociado es:
5 x 10 +10 x 0 + 5 x 7+ 15 x 9 + 5 x 20 +5 x 18 = $410.
1
2
3
4
1
5
10
15
2
5
15
5
25
3
5
5
5
15
15
10
Cuando se satisfacen al mismo tiempo una columna y un renglón, la siguiente variable que se agregará a la solución básica estará necesariamente en el nivel cero. La siguiente tabla ilustra este aspecto. La columna 2 y el renglón 2 se satisfacen simultáneamente.
1
2
3
4
1
5
5
10
5
2
5
0
5
0
3
8
7
15
5
10
8
7
15
5
Si se tacha la columna 2, x23 se vuelve básica en el nivel cero en el paso siguiente, ya que la demanda restante del renglón 2 vale ahora cero.(Este caso se presenta en la tabla anterior). Si en cambio se cruza el renglón 2, x32 sería la variable básica cero.
Las soluciones iniciales de las dos últimas tablas incluyen el número adecuado de variables básicas, o sea, m + n-1 = 6. La regla de la esquina noroeste produce siempre el número adecuado de variables básicas.
DETERMINACION DE LA VARIABLE DE ENTRADA
(METODO DE MULTIPLICADORES)
La variable que entra se determina mediante el uso de la condición de optimalidad del método simplex. Los cálculos de los coeficientes de la función objetivo están basados en las relaciones primales-duales. Primero presentamos la mecánica del método y después damos una explicación con base en la teoría de la dualidad. Otro método, llamado procedimiento Saltando Piedras, también sirve para determinar la variable que entra.
En el método de multiplicadores asociamos los multiplicadores ui y vj con el renglon i y la columna j de la tabla de transporte. Para cada variable basica xij ed la solucion actual, los multiplicadores ui y vj deben satisfacer la ecuacion que sigue:
ui + vj = cij , para cada variable basica xij
Estas ecuaciones producen m+n-1 ecuaciones con m+n incognitas. Los valores de los multilicadores se pueden determinar a partir de estas ecuaciones suponiendo un valor arbitrario para cualquiera de los multiplicadores y resolviendo las m+n-1 multipilicadores desconocidos restantes.
Al hacer esto, la evaluacion de cada variable no basica Xpq esta dada por:
Cpq = up – vq – cpq
Después se selecciona la variable que entra como la variable no basica con la variable no basica con la variable cpq mas positiva.
Si aplicamos este procedimiento a las variables no basicas estan dadas como:
X11:
U1
+
V1
=
C11
=
10
X12:
U1
+
V2
=
C12
=
0
X22:
U2
+
V2
=
C22
=
7
X23:
U2
+
V3
=
C23
=
9
X24:
U2
+
V4
=
C24
=
20
X34:
U3
+
V4
=
C34
=
18
Haciendo u1= 0 los valores de los multiplicadores se determinan sucesivamente como V1=10, V2=0, U2=7, V3=2, V4=13, y U3=5. Las evaluaciones de las variables no basicas estan dadas de la manera siguiente:
X13: c13 = u1 + v3 – c13 = 0+2-20 = -18
X14: c14 = u1+ v4 – c14 = 0+13-11 = 2
X21: c21 = u2 + v1 – c21 = 7+10-12 = 5
X31: c31 = u3+v1 – c3 = 5+10-0 = 15
X32: c32 = u3+v2 – c32 = 5+0-14 = -9
X33: c33 = u3 +v3 – c33 = 5+2-16 = -9
Como x31 tiene la variable cpq mas positiva, esta se selecciona como la variable que entra.
Las ecuaciones ui+vj = cij que utilizamos para determinar los multiplicadores, tienen una estructura tan sencilla que es necesario escribirlos en forma explicita. DETERMINACION DE LA VARIABLE QUE SALE
(Construccion de un ciclo)
Este paso es equivalente a aplicar la condicion de factibilidad del metodo simplex.Sin embargo, como todos los coeficientes de restriccion del modelo de transportes original son cero o uno, las razones de condicion de factibilidad tendran siempre su denominador igual a uno .Por lo tanto los valores de las variables basicas producuran dirfectamente las razones asociadas.
Para el fin de determinar la razon minima, construimos un ciclo cerrado para la variable actual que entra. El ciclo empieza y termina en la variable no basica designada. Este consta de los segmentos sucesivos horizontales y verticales cuyos puntos extremos deben de ser variables basicas salvo para los puntos extremos que estan asociados con la variable que entra. Esto significa que todo elemento de esquina del ciclo debe ser una celda que contenga una variable basica. La tabla 6-10 ilustra un ciclo para la variable que entra dada en la solucion basica de la tabla 6-8.Observese que para la solucion basica dada solo se puede construir un ciclo unico para cada variable no basica.
La variable que sale se selecciona de entre las variables de esquina del ciclo que disminuiran cuando las variables del ciclo que entra aumente arriba del nivel cero. Estas situaciones se indican en la tabla siguiente a travez de las variables contenidas en el cuadro etiquetado con los signos menos.
1
2
3
4
10
0
20
11
15
5 –
10 +
12
7
9
20
25
5 –
15
5 +
0
14
16
18
5
X 31 0
5 –
5
15
15
10
La solucion basica de la tabla de abajo es degenerada, ya que las variables basicas x11 y x22 son cero.Ahora se revisa la optimidad de la nueva solucion basica de la tabla 6-11 calculando los nuevos multiplicadores como se indica en la tabla 6-12. Los valores de cpq estan dados por los numeros de la esquina de cada celda no basicaLa variable no basica x21 con la variable cpq positiva mayor entra en la solucion. El ciclo cerrado asociado con x21 muestra que x21 o x22 pueden ser la variable que sale. Seleccionamos arbitrariamente x11 como la que sale de la solucion.
1
2
3
4
1
10
0
20
11
15
0
15
2
12
7
9
20
25
0
15
10
3
0
14
16
18
5
5
5
15
15
10
V1=10
V2=0
V3=2
V4=13
U1=0
10
0
20
11
15
0 –
15 +
-18
+2
U2=7
12
7
9
20
25
+5
X 21 +
0 –
15
10
U3=-10
0
14
16
18
5
5
-24
-24
-15
5
15
15
10
La tabla de arriba muestra la nueva solucion basica que sigue de la tabla siguiente. Los nuevos valores de ui, vj y cpq se vuelven a calcular. La tabla muestra la variable que entra y la que sale como x14 y x24, respectivamente.
Al efectuar este cambio en la tabla de abajo obtenemos la nueba solucion de la tabla final. Como todas las variables cpq de la tabla final son no positivas se ha llegado a la solucion optima.
V1=5
V2=0
V3=2
V4=13
U1=0
10
0
20
11
15
-5
15 –
-18
+2
X 14 +
U2=7
12
7
9
20
25
0
0 +
15
10 –
U3=-5
0
14
16
18
5
5
-19
-19
-10
5
15
15
10
V1=5
V2=0
V3=2
V4=11
U1=0
10
0
20
11
15
-5
5
-18
10
U2=7
12
7
9
20
25
0
10
15
-2
U3=-5
0
14
16
18
5
5
-19
-19
-12
5
15
15
10
EXPLICACION DEL METODO DE MULPIPLICADORES CON UN METODO SIMPLEX
La relecion que existe entre el metodo multiplicadores y el metodo simplex se puede establecer demostrando que cpq según se define, es igual directamente a los coeficientes de la funcion objetivo de la tabla simplex asociada con la iteracion actual.
Para mostrar como se obtiene el problema dual para el metodo de transporte, considerese primero el caso especial de ,=2 y n=3 que se indica en la tabla 6-15. Sean las variables duales u1 y u2 para las restricciones de las fuentes y v1,v2, y v3 para las restricciones de los destinos. El problema dual se convierte en:
Maximizar w = (a1u1+a2u2) + (b1v1+b2v2+b3v3)
Sujeto a:
U1 +v1 <= c11
U1 +v2 <=c12
U1 +v3 <=c13
U2+v1 <=c21
U2+v1 <=c22
U2 +v3 <=c23
Ui, U2, v1, v2, v3, irrestrictas
El problema dual correspondiente esta dado por:
Maximizar w = åm i-1 a1 u1 + ån bi vj
sujeto a:
ui + vj <=cij para todas las i y j
ui y vj irrestrictas
La evaluacion de las variables no basicas se determinan mediante la sustitucion de los valores actuales de las variables duales en las restricciones duales y despues tomando la diferencia entre sus miembros primero y segundo. Los valores de las variables duales se pueden determinar observando que las restricciones deuales correspondientes a una variable basica se deben satisfacer como ecuaciones escritas.
En realidad en la iteracion optima los multiplicadores producen los valores duales optimos directamente.
En lo antes expuesto se asigna un valor arbitrario a una de las variables duales que indica que los multiplicadores simplex asociados con una solucion basica dada no son unicos. Esto puede parecer inconsistente con los resultados donde los multiplicadores deben ser unicos.
SOLUCION INICIAL MEJORADA
En esta seccion presentamos dos procedimientos que determinan la solucion inicial a travez de la seleccion de las rutas “economicas”del modelo.
A. MODELO DEL COSTO MINIMO
Asignese el mas grande valor posible a la variable con el menor costo unitario de toda la tabla. Tachese el renglon o columna satisfecho.Despues de ajustar la oferta y la demanda de todos los renglones y columnas no tachados, repitase el proceso asignando el valor mas grande posible a la variable con el costo unitario no tachado mas pequeño. El procedimiento esta completo cuando queda exactamente un rebglon o bien una columna sin tachar.
1
2
3
4
1
10
0
20
11
15
0
15
0
2
12
7
9
20
25
15
10
3
0
14
16
18
5
5
5
15
15
10
B. METODO DE APROXIMACION DE VOGEL (VAM)
Este metodo es heuristico y suele producir una mejor solucion inicial que los dos metodos antes descritos. De hecho, VAM suele producir una solucion inicial optima, o proxima al nivel optimo.
Los pasos del procedimiento son los siguientes:
Paso1: Evaluese una penalizacion para cada renglon restando el menor elemento del costo del renglon del elemento de costo menor siguiente en el mismo renglon.
Paso2: Identifiqueze el renglon o columna con la mayor penalizacion, rompiendo empates en forma arbitraria. Asignese el valor mayor posible a la variable con el costo mas bajo del renglon o columna seleccionado. Ajustese la oferta y la demanda y tachese el renglon o columna satisfecho. Si un renglon o columna se satisfacen al mismo tiempo, solo uno de ellos se tacha y al renglon restante se le asigna una oferta cero.Cualquier renglon o columna con oferta o demanda cero no debe utilizarce para calcular penalizaciones futuras.
Paso 3:
a.-si solo hay un renglon o columna sin tachar, detengase.
b.-si solo hay un renglon conoferta positiva sin tachar, determinense las variables basicas del renglon a travez del metodo del costo minimo.
c.-si todos los renglones y columnas sin tachar tienen oferta o demanda cero asignadas, determinese las variables basicas cero a travez del metodo del costo minimo. Detengase.
d.-de lo contrario, calculense las penalizaciones de las renglones y columnas no tachados y despues dirijase al paso 2.
1
2
3
4
PR
1
10
0
20
11
15
10
2
12
7
9
20
25
2
3
0
14
16
18
5
14
5
PC
5
15
15
10
10
7
7
7
PR = Penalización de Renglón
PC = Penalización de Columna
1
2
3
4
PR
1
10
0
20
11
15
11
2
12
7
9
20
25
10
2
15
3
0
5
0
–
5
PC
5
15
15
10
–
7
11
9
CONCLUSION:
Se han presentado varios métodos para obtener una solución al problema de transporte u otro semejante. Una consideración muy importante que hay que tener en cuenta con cualquier método que se utilice, es que el problema de transporte no siempre puede aislarse y resolverse dentro de sus propios límites. El transporte es tan sólo una parte de todo el sistema de distribución de la compañía. Es muy difícil resolver el mejor programa de transporte en términos de servicio y bajo costo. Esa área de la empresa requiere de una constante atención para incorporar los cambios que constituyan y una difícil tarea para cualquier grupo de investigaciones de negocios.
En ciencias aplicadas, un Modelo matemático es uno de los tipos de modelos científicos, que emplea algún tipo de formulismo matemático para expresar relaciones, proposiciones sustantivas de hechos, variables, parámetros, entidades y relaciones entre variables y/o entidades u operaciones, para estudiar comportamientos de sistemas complejos ante situaciones difíciles de observar en la realidad. El término modelización matemática es utilizada también en diseño gráfico cuando se habla de modelos geométricos de los objetos en dos (2D) o tres dimensiones (3D).
El significado de modelo matemático en matemática fundamental, sin embargo, es algo diferente. En concreto en matemáticas se trabajan con modelos formales. Un modelo formal para una cierta teoría matemática es un conjunto sobre el que se han definido un conjunto de relaciones unarias, binarias y trinarias, que satisface las proposiciones derivadas del conjunto de axiomas de la teoría. La rama de la matemática que se encarga de estudiar sistemáticamente las propiedades de los modelos es la teoría de modelos.
Clasificaciones de los modelos
Se podría decir que un modelo de las ciencias físicas es una traducción de la realidad física de un sistema en términos matemáticos, es decir, una forma de representar cada uno de los tipos entidades que intervienen en un cierto proceso físico mediante objetos matemáticos. Las relaciones matemáticas formales entre los objetos del modelo, deben representar de alguna manera las relaciones reales existentes entre las diferentes entidades o aspectos del sistema u objeto real. Así una vez «traducido» o «representado» cierto problema en forma de modelo matemático, se pueden aplicar el cálculo, el álgebra y otras herramientas matemáticas para deducir el comportamiento del sistema bajo estudio. Un modelo físico requerirá por tanto que se pueda seguir el camino inverso al modelado, permitiendo reinterpretar en la realidad las predicciones del modelo.
Según la información de entrada
Con respecto a la función del origen de la información utilizada para construir los modelos pueden clasificarse de otras formas. Podemos distinguir entre modelos heurísticos y modelos empíricos:
Modelos heurísticos (del griego euriskein ‘hallar, inventar’). Son los que están basados en las explicaciones sobre las causas o mecanismos naturales que dan lugar al fenómeno estudiado.
Modelos empíricos (del griego empeirikos relativo a la ‘experiencia’). Son los que utilizan las observaciones directas o los resultados de experimentos del fenómeno estudiado.
Según el tipo de representación
Además los modelos matemáticos encuentran distintas denominaciones en sus diversas aplicaciones. Una posible clasificación puede atender a si pretenden hacer predicciones de tipo cualitativo o pretende cuantificar aspectos del sistema que se está modelizando:
Modelos cualitativos o conceptuales, estos pueden usar figuras, gráficos o descripciones causales, en general se contentan con predecir si el estado del sistema irá en determinada dirección o si aumentará o disminuirá alguna magnitud, sin importar exactamente la magnitud concreta de la mayoría de aspectos.
Modelos cuantitativos o numéricos, usan números para representar aspectos del sistema modelizado, y generalmente incluyen fórmulas y algoritmos matemáticos más o menos complejos que relacionan los valores numéricos. El cálculo con los mismos permite representar el proceso físico o los cambios cuantitativos del sistema modelado.
Según la aleatoriedad
Otra clasificación independiente de la anterior, según si a una entrada o situación inicial concreta pueden corresponder o no diversas salidas o resultados, en este caso los modelos se clasifican en:
Determinista. Se conoce de manera puntual la forma del resultado ya que no hay incertidumbre. Además, los datos utilizados para alimentar el modelo son completamente conocidos y determinados.
Estocástico. Probabilístico, que no se conoce el resultado esperado, sino su probabilidad y existe por tanto incertidumbre.
Clasificación según su aplicación u objetivo
Por su uso suelen utilizarse en las siguientes tres áreas, sin embargo existen muchas otras como la de finanzas, ciencias etc.
Modelo de simulación o descriptivo, de situaciones medibles de manera precisa o aleatoria, por ejemplo con aspectos de programación líneal cuando es de manera precisa, y probabilística o heurística cuando es aleatorio. Este tipo de modelos pretende predecir qué sucede en una situación concreta dada.
Modelo de optimización. Para determinar el punto exacto para resolver alguna problemática administrativa, de producción, o cualquier otra situación. Cuando la optimización es entera o no lineal, combinada, se refiere a modelos matemáticos poco predecibles, pero que pueden acoplarse a alguna alternativa existente y aproximada en su cuantificación. Este tipo de modelos requiere comparar diversas condiciones, casos o posibles valores de un parámetro y ver cual de ellos resulta óptimo según el criterio elegido.
Modelo de control. Para saber con precisión como está algo en una organización, investigación, área de operación, etc. Este modelo pretende ayudar a decidir qué nuevas medidas, variables o qué parámetros deben ajustarse para lograr un resultado o estado concreto del sistema modelado.
Ejemplos
Un modelo mixto operacional estadístico es una teoría o situación causal de hechos y expresado con símbolos de formato matemático. Por ejemplo las tablas de contingencia. De hecho los modelos matemáticos se construyen con varios niveles de significación y con diferentes variables.
Kendall y Buckland catalogan hasta 40 tipos diferentes de modelos matemáticos. Ejemplos: Rapoport en modelo matemático e interacción social en 1961 y Bugeda en Sociología matemática en 1970. Por un principio de isomorfismo hay una equivalencia, a conseguir, entre un modelo y una teoría. Además teoría y modelo son sinónimos.
Ejemplos de modelos por tipos
Descriptivos / Simulación
Optimización / Elección
Control / Tratamiento
Determinista
Probabilista
Determinista
Probabilista
Determinista
Probabilista
Cuantitativo
Cálculos
astronómicos
Simulaciones
de tráfico
Cálculo componentes
de sistemas
Diseño ingenieril
Control
automático
?
Cualitativo
Análisis
microeconómicos
Teoría de
juegos
Modelos
de grafo/flujo
?
Teoría
psicológica
?
Modelo matemático de simulación
Se utilizan para estudiar situaciones extremas, difícilmente observables en la realidad, como por ejemplo los efectos de precipitaciones muy intensas y prolongadas en cuencas hidrográficas, en su estado natural, o en las que se ha intervenido con obras como canales, represas, diques de contención, puentes, etc.
La cuenca hidrográfica es dividida en sub-cuencas consideradas homogéneas desde el punto de vista: del tipo de suelo, de la declividad, de su cobertura vegetal. El número y tipo de las variables hidrológicas que intervienen en el modelo son función de objetivo específico para el cual se elabora el mismo.
Fases de construcción de un modelo
En muchos casos la construcción o creación de modelos matemáticos útiles sigue una serie de fases bien determindas:
Identificación de un problema o situación compleja que necesita ser simulada, optimizada o controlada y por tanto requeriría un modelo matemático predictivo.
Elección del tipo de modelo, esto requiere precisar qué tipo de respuesta u output pretende obtenerse, cuales son los datos de entrada o factores relevantes, y para qué pretende usarse el modelo. Esta elección debe ser suficientemente simple como para permitir un tratamiento matemático asequible con los recursos disponibles. Esta fase requiere además identificar el mayor número de datos fidedignos, rotular y clasificar las incógnitas (variables independientes y dependientes) y establecer consideraciones, físicas, químicas, geométricas, etc. que representen adecuadamente el fenómeno en estudio.
Formalización del modelo en la que se detallarán qué forma tienen los datos de entrada, qué tipo de herramienta matemática se usará, como se adaptan a la información previa existente. También podría incluir la confección de algoritmos, ensamblaje de archivos informáticos, etc, etc. En esta fase posiblemente se introduzcan también simplificaciones suficientes para que el problema matemático de modelización sea tratable computacionalmente.
Comparación de resultados los resultados obtenidos como predicciones necesitan ser comparados con los hechos observados para ver si el modelo está prediciendo bien. Si los resultados no se ajustan bien, frecuentemente se vuelve a la fase 1.
Es importante mencionar que la inmensa mayoría de modelos matemáticos no son exactos y tienen un alto grado de idealización y simplificación, ya que una modelización muy exacta puede ser más complicada de tratar de una simplificación conveniente y por tanto menos útil. Es importante recordar que el mecanismo con que se desarrolla un modelo matemático repercute en el desarrollo de otras tecnicas de conocimientos enfocadas al area socio-cultural.
METODO SIMPLEX CON WINQSB
Ejercicios:
EL METODO SIMPLEX PARA SOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL
Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución. Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.
El método del simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.
El método del simplex fue creado en 1947 por el matemático George Dantzig . El método del simplex se utiliza, sobre todo, para resolver problemas de programación lineal en los que intervienen tres o más variables.
El álgebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un sistema de ecuaciones lineales constituyen la base del método simplex.
Con miras a conocer la metodología que se aplica en el Método SIMPLEX, vamos a resolver el siguiente problema:
Maximizar
Z= f(x,y)= 3x + 2y
sujeto a:
2x + y 18
2x + 3y 42
3x + y 24
x0 , y 0
Se consideran las siguientes fases:
1. Convertir las desigualdades en igualdades
Se introduce una variable de holgura por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:
2x + y + h = 18
2x + 3y + s = 42
3x +y + d = 24
2. Igualar la función objetivo a cero
– 3x – 2y + Z = 0
3. Escribir la tabla inicial simplex
En las columnas aparecerán todas las variables del problema y, en las filas, los coeficientes de las igualdades obtenidas, una fila para cada restricción y la última fila con los coeficientes de la función objetivo:
Tabla I . Iteración nº 1
Base
Variable de decisión
Variable de holgura
Valores solución
x
y
h
s
d
h
2
1
1
0
0
18
s
2
3
0
1
0
42
d
3
1
0
0
1
24
Z
-3
-2
0
0
0
0
4. Encontrar la variable de decisión que entra en la base y la variable de holgura que sale de la base
Para escoger la variable de decisión que entra en la base, nos fijamos en la última fila, la de los coeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor (en valor absoluto).
En nuestro caso, la variable x de coeficiente – 3. Si existiesen dos o más coeficientes iguales que cumplan la condición anterior, entonces se elige uno cualquiera de ellos.
Si en la última fila no existiese ningún coeficiente negativo, significa que se ha alcanzado la solución óptima. Por tanto, lo que va a determinar el final del proceso de aplicación del método del simplex, es que en la última fila no haya elementos negativos.
La columna de la variable que entra en la base se llama columna pivote (En colorazulado).
Para encontrar la variable de holgura que tiene que salir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero. En nuestro caso:
18/2 [=9] , 42/2 [=21] y 24/3 [=8] Si hubiese algún elemento menor o igual que cero no se hace dicho cociente. En el caso de que todos los elementos fuesen menores o iguales a cero, entonces tendríamos una solución no acotada y no se puede seguir.
El término de la columna pivote que en la división anterior dé lugar al menor cociente positivo, el 3, ya 8 es el menor, indica la fila de la variable de holgura que sale de la base, d. Esta fila se llama fila pivote (En color azulado).
Si al calcular los cocientes, dos o más son iguales, indica que cualquiera de las variables correspondientes pueden salir de la base.
En la intersección de la fila pivote y columna pivote tenemos el elemento pivote operacional, 3.
5. Encontrar los coeficientes de la nueva tabla.
Los nuevos coeficientes de x se obtienen dividiendo todos los coeficientes de la fila d por el pivote operacional, 3, que es el que hay que convertir en 1.
A continuación mediante la reducción gaussiana hacemos ceros los restantes términos de su columna, con lo que obtenemos los nuevos coeficientes de las otras filas incluyendo los de la función objetivo Z.
También se puede hacer utilizando el siguiente esquema:
Fila del pivote:
Nueva fila del pivote= (Vieja fila del pivote) : (Pivote)
Resto de las filas:
Nueva fila= (Vieja fila) – (Coeficiente de la vieja fila en la columna de la variable entrante) X (Nueva fila del pivote)
Veámoslo con un ejemplo una vez calculada la fila del pivote (fila de x en la Tabla II):
Vieja fila de s
2
3
0
1
0
42
–
–
–
–
–
–
Coeficiente
2
2
2
2
2
2
x
x
x
x
x
x
Nueva fila pivote
1
1/3
0
0
1/3
8
=
=
=
=
=
=
Nueva fila de s
0
7/3
0
1
-2/3
26
Tabla II . Iteración nº 2
Base
Variable de decisión
Variable de holgura
Valores solución
x
y
h
s
d
h
0
1/3
1
0
-2/3
2
s
0
7/3
0
1
-2/3
26
x
1
1/3
0
0
1/3
8
Z
0
-1
0
0
1
24
Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:
La variable que entra en la base es y, por ser la variable que corresponde al coeficiente -1
Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote:
2:1/3 [=6] , 26:7/3 [=78/7] y 8:1/3 [=8]
y como el menor cociente positivo es 6, tenemos que la variable de holgura que sale es h.
El elemento pivote, que ahora hay que hacer 1, es 1/3.
Operando de forma análoga a la anterior obtenemos la tabla:
Tabla III . Iteración nº 3
Base
Variable de decisión
Variable de holgura
Valores solución
x
y
h
s
d
y
0
1
3
0
-2
6
s
0
0
-7
0
4
12
x
1
0
-1
0
1
6
Z
0
0
3
0
-1
30
Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:
La variable que entra en la base es d, por ser la variable que corresponde al coeficiente -1
Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote:
6/(-2) [=-3] , 12/4 [=3], y 6:1 [=6]
y como el menor cociente positivo es 3, tenemos que la variable de holgura que sale es s.
El elemento pivote, que ahora hay que hacer 1, es 4.
Obtenemos la tabla:
Tabla IV . Final del proceso
Base
Variable de decisión
Variable de holgura
Valores solución
x
y
h
s
d
y
0
1
-1/2
0
0
12
d
0
0
-7/4
0
1
3
x
1
0
-3/4
0
0
3
Z
0
0
5/4
0
0
33
Como todos los coeficientes de la fila de la función objetivo son positivos, hemos llegado a la solución óptima.
Los solución óptima viene dada por el valor de Z en la columna de los valores solución, en nuestro caso: 33. En la misma columna se puede observar el vértice donde se alcanza, observando las filas correspondientes a las variables de decisión que han entrado en la base: D(3,12)
* Si en el problema de maximizar apareciesen como restricciones inecuaciones de la forma: ax + by c; multiplicándolas por – 1 se transforman en inecuaciones de la forma – ax – by – c y estamos en el caso anterior* Si en lugar de maximizar se trata de un problema de minimizar se sigue el mismo proceso, pero cambiando el sentido del criterio, es decir, para entrar en la base se elige la variable cuyo valor, en la fila de la función objetivo, sea el mayor de los positivos y se finalizan las iteraciones cuando todos los coeficientes de la fila de la función objetivo son negativos
Interpretación geométrica del método del simplex
Las sucesivas tablas que hemos construido van proporcionando el valor de la función objetivo en los distintos vértices, ajustándose, a la vez, los coeficientes de las variables iniciales y de holgura.
En la primera iteración (Tabla I) han permanecido todos los coeficientes iguales, se ha calculado el valor de la función objetivo en el vértice A(0,0), siendo este 0.
A continuación se desplaza por la arista AB, calculando el valor de f , hasta llegar a B.
Este paso aporta la Tabla II.
En esta segunda iteración se ha calculado el valor que corresponde al vértice B(8,0): Z=f(8,0) = 24
Sigue por la arista BC, hasta llegar a C, donde se para y despliega los datos de la Tabla III.
En esta tercera iteración se ha calculado el valor que corresponde al vértice C(6,6) : Z=f(6,6)=30.
Continua haciendo cálculos a través de la arista CD, hasta llegar al vértice D. Los datos que se reflejan son los de la Tabla IV.
Concluye con esta tabla, advirtiendo que ha terminado (antes ha comprobado que la solución no mejora al desplazarse por la arista DE)
El valor máximo de la función objetivo es 33, y corresponde a x = 3 e y = 12 (vértice D).
Si calculas el valor de la función objetivo en el vértice E(0,14), su valor no supera el valor 33.
Existen dos metodologías para solucionar un problema modelado en Programación Lineal: elMétodo Gráfico y el Método Simplex.
El Método Gráfico se utiliza para ilustrar tres conceptos básicos: la metodología para la resolución de un problema de dos variables de decisión, la interpretación de la solución del problema modelado y la observación gráfica de como afectan los cambios a la solución del problema. El Método Gráfico es poco poderoso ya que está limitado a resolver problemas de dos o máximo tres variables de decisión. Sin embargo, su importancia radica en que permite visualizar los conceptos matemáticos implicados en la Programación Lineal.
Por su parte, el Método Simplex es utilizado para resolver problemas más complejos de Programación Lineal. Es un método poderoso, utilizado para resolver problemas de «n» variables de decisión, aunque también se puede emplear para resolver problemas de dos variables como lo hace el Método Gráfico.
El enfoque propuesto aquí, es utilizar la computadora como una herramienta de apoyo para resolver problemas de Programación Lineal de cualquier tamaño. Sin embargo, se deben estudiar primero los fundamentos de estos métodos de solución para posteriormente utilizar la computadora para este fin.
El uso de la computadora en la solución de problemas en Programación Lineal, implica utilizar cualquiera de estas dos alternativas: primera, usar una hoja electrónica como puede ser Excel, donde el usuario hace directamente la programación para solucionar el problema modelado; segunda, el uso de un paquete de software comercial, que ya está diseñado para la resolución del Método Gráfico y del Simplex.
Algunos de los paquetes de software comercial más conocidos son: el Storm, el WinQSB, Lindo, Eureka, etc.. Estos tipos de software han evolucionado de acuerdo a los avances tecnológicos de la época, con la tendencia de tener una herramienta más poderosa pero con cierta perdida de hacer usuarios más pensantes y no solo manipuladores de la misma. Es obvio que el uso de la computadora permite un gran ahorro de tiempo en el procesamiento de los datos y que hace posible la solución de problemas más complejos a los que normalmente se hacen dentro del aula.
Sin embargo, el uso de cualquier paquete de software requiere tener el problema ya modelado, para ser capturado en el formato requerido por dicho software. En esta forma, se puede obtener la solución óptima del problema como un reporte de salida de la computadora pero esta solución matemática requiere de una interpretación por parte del usuario para la toma de decisiones.
El ciclo completo a realizar en la solución de un problemas es: modelar el problema, solucionar el problema modelado e interpretar la solución obtenida. De estas tres partes, las que más desarrollan las habilidades del pensamiento son la modelación del problema y la interpretación de la solución encontrada. En este caso, se considera de menor contribución a la etapa de la solución del problema, que se puede hacer a través de la computadora.
Sin embargo, el enfoque de este capítulo es fundamentar los conceptos básicos de la Programación Lineal a través del Método Gráfico. Para esta finalidad, se han desarrollado dos ejercicios, el primero está enfocado a mostrar «la metodología y los conceptos básicos» del Método Gráfico y el segundo, presenta el «ciclo completo» que se sigue en la solución de un problema de Programación Lineal.
Ejercicio 1. Metodología y conceptos básicos del “Método Gráfico”.
Se presenta la metodología utilizada por el Método Gráfico para encontrar la solución óptima de un problema modelado y los conceptos básicos de la Programación Lineal que se pueden visualizar a través del él. Se presenta el siguiente problema:
Función Objetivo: Máx. Z = 3X1 + 6X2
JEVA / PTI
2
//
PROGRAMACIÓN LINEAL
MÉTODO GRÁFICO
Restricciones:
a.
X1≤ 10
b.
X2≤ 10
c.
X1 + X2≤ 16
d.
6X1 + 4X2≥ 48
e.
X1 + X2≤ 20
f.
2X1 + 4X2≥ 16
g.
X1 – X2≤ 0
h.
No negatividad: X1, X2≥ 0
1.1. Metodología.
El Método Gráfico utiliza la siguiente metodología para encontrar la solución óptima de un problema:
a. Calcular los puntos para graficar cada restricción.
b. Graficar las restricciones.
c. Determinar la región factible.
d. Calcular las coordenadas de los vértices de la región factible.
e. Calcular el valor de la Función Objetivo en dichos vértices.
f. Encontrar la solución óptima del problema.
Calcular los puntos para graficar cada restricción.
Para graficar una restricción, primero se le considera como una recta, es decir como si fuera una igualdad, y luego se encuentra el espacio solución que cumple con la condición de dicha restricción, poniendo una pequeña flecha para indicarlo.
En este problema se presentan tres variantes que se pueden encontrar al graficar una restricción: cuando es paralela a alguno de los ejes de coordenadas, cuando cruza los dos ejes de coordenadas y cuando pasa por el punto de origen (0,0). A continuación se presentan las variantes:
Las restricciones «a» y «b» del problema son paralelas a los ejes X1 y X2. Se reconoce que una restricción es paralela cuando solo tiene una de las variables, por ejemplo la restricción «a» solo tiene la X1 por lo que es paralela al eje X2.
Otro tipo de restricciones son las que cruzan por los dos ejes como las restricciones «c», «d», «e» y
«f».
Existen también restricciones que pasan por el punto (0,0) como la restricción «g».
Para graficar una recta existen diferentes métodos, uno de ellos es el «método de los dos puntos». En dicho método se establece que, para graficar una recta es necesario conocer al menos dos puntos pertenecientes a ella.
Para calcular las coordenadas de los dos puntos P1 y P2, se elige arbitrariamente una de las variables de la restricción, por ejemplo X1 y se hace igual a cero, calculándose la otra variable X2; luego se proceda a la inversa, se hace X2 = 0 y se calcula X1. Si la restricción es paralela a uno de los ejes, simplemente se fija la coordenada y se traza la recta. A continuación se muestra los puntos calculados para cada restricción:
Restricciones
Puntos para graficar la recta:
P1 (X1,0)
P2 (0,X2)
a. X1
≤ 10
10,0
–
b.
X2≤ 10
–
0,10
c. X1 + X2≤ 16
16,0
0,16
d. 6X1 + 4X2≥ 48
8,0
0,12
e. X1 + X2≤ 20
20,0
0,20
f. 2X1 + 4X2≥ 16
8,0
0,4
g. X1 – X2≤ 0
0,0
0,0
JEVA / PTI
3
//
PROGRAMACIÓN LINEAL
MÉTODO GRÁFICO
Graficar las restricciones.
A continuación se explica como graficar cada una de las variantes de las restricciones:
Para graficar una restricción paralela a uno de los ejes, como lo es «a», se marca el punto (10,0) que está sobre el eje X1 y se traza paralelamente al eje X2. El espacio de solución es evidente para este tipo de restricciones, que en este caso, el sentido de la restricción es hacia la izquierda como se puede ver en el gráfico de la Figura 1.
Para graficar una restricción que cruza los dos ejes, como sería «d», se marca el punto uno (8,0) en el eje X1 y el punto dos (0,12) en el eje X2 y se unen trazando una recta. Para determinar el espacio de solución, se puede hacer directamente observando el tipo de desigualdad que tiene la restricción, sin embargo, se recomienda probar el sentido de la restricción con el punto (0,0). Al sustituir estos valores en la restricción, se checa si cumple o no con la condición impuesta por dicha restricción. Si cumple con la condición, entonces el espacio solución será de la recta hacia el origen (0,0), que fue el punto que se probó. Si no cumple la condición, el espacio solución será en sentido contrario. Por ejemplo, si sustituimos este punto en la restricción «d, se tendrá 0≥ 48 que no cumple con la restricción, por lo que su sentido será en dirección contraria al origen (0,0) como se puede ver en el gráfico de la Figura 1.
Para graficar una restricción que pasa por el punto de origen (0,0), como lo es «g», se requiere generar un «punto auxiliar». Este punto auxiliar, se calcula dando un valor arbitrario a una de las variables para sustituirla en la ecuación de la restricción y poder despejar la otra variable, por ejemplo, si consideramos X1 = 2 se tiene que:
2-X2 = 0
X2 = 2
El punto auxiliar es (2,2). Ahora se tienen dos puntos, el (0,0) y el (2,2) por donde pasará la recta. Para determinar el espacio solución es necesario probar con cualquier punto separado de la recta, ya sea por arriba o por abajo de ella. Si el punto probado satisface la restricción, el espacio de solución será en esa dirección sino será en sentido contrario. Por ejemplo, si se prueba con el punto (10,2) que está por abajo de la recta, al sustituir en la restricción, se tendrá 8≤ 0 que no cumple con la restricción, por lo que el espacio solución será hacia arriba (ver Figura 1), es decir en sentido contrario al punto probado. Si se hubiera probado un punto por arriba de la recta como el (2,20) se llegaría a la misma conclusión.
Determinar la región factible.
Para determinar la región factible en la gráfica de la Figura 1, es importante atender el sentido de las restricciones para encontrar el área común a todas. Para hacer esto, nos podemos auxiliar de las pequeñas flechas que indican el sentido de cada restricción.
Cuando se tienen muchas restricciones graficadas, una forma simple de encontrar la región factible, es considerar a cada restricción como el corte que se hace en un pastel. Se regala la rebanada que no cumple con el sentido de la restricción y dejamos la que si cumple. Al seguir haciendo los demás cortes, la rebanada que queda se hará cada vez mas pequeña. La parte que queda al final será la región factible. Esta concepción propuesta, se puede visualizar considerando que cada restricción divide el espacio en dos partes. La parte que cumple con el sentido de la restricción está señalada por una pequeña flecha.
A continuación se presenta la gráfica de las restricciones del problema y la región factible:
JEVA / PTI
4
//
PROGRAMACIÓN LINEAL
MÉTODO GRÁFICO
Figura 1. Gráfica de las restricciones y de la región factible.
Calcular las coordenadas de los vértices de la región factible.
En el gráfico de la Figura 1, se marcaron los vértices que forman la región factible. La importancia de calcular las coordenadas de estos vértices, es que ayudan a calcular el valor de la Función Objetivo en cada uno de ellos y en base a este listado, se encuentra la solución óptima del problema.
Una forma sencilla de calcular las coordenadas de un vértice, es leerlas directamente en la gráfica, pero la precisión de la lectura dependerá de la calidad que se tenga en dicha gráfica. Otra forma que no depende de la precisión de la gráfica, es ver qué restricciones forman al vértice y solucionar este sistema de dos ecuaciones por algún método algebraico. Sin embargo, se pueden reducir los cálculos si clasificamos los vértices en dos tipos: los que están sobre uno de los ejes de coordenadas y los que están fuera de los ejes.
Cuando un vértice está sobre uno de los ejes, se pueden leer directamente sus coordenadas en el gráfico o en los puntos calculados para graficar la restricción. Si el vértice está fuera de los ejes, se requiere calcular sus coordenadas a través de un sistema de ecuaciones simultáneas, dado por las dos restricciones que se cruzan para formar dicho vértice. Si una de las restricciones es paralela, simplemente se sustituye el valor de esa variable en la otra restricción.
Analizando la gráfica, se verá que todos los vértices de la región factible están fuera de los ejes. El vértice «A» esta formado por la intersección de las restricciones «d» y «g», el vértice «B» por «b» y «d», el «C» por «b» y «c» y el «D» por «c» y «g». A continuación se calculan las coordenadas de cada vértice:
Vértice «A»:
Restricción «d»
6X1 + 4X2 = 48
Restricción «g»
4( X1 – X2 = 0)
10X1
= 48
X1 = 4.8
X2 = 4.8
Vértice «B»:
Restricción «b»
X2 = 10
Sustituyendo en la Restricción «d» se tiene:
6X1 + 4(10) = 48
X1 = 1.3
Vértice «C»:
Restricción «b»
X2 = 10
Sustituyendo en la Restricción «c» se tiene:
X1 + X2 =16
X1 = 6
JEVA / PTI
5
//
PROGRAMACIÓN LINEAL
MÉTODO GRÁFICO
Vértice «D»:
Restricción «c»
X1 + X2 = 16
Restricción «g»
X1 – X2 =0
2X1
= 16
X1 = 8
X2 = 8
Calcular el valor de la Función Objetivo en dichos vértices.
Para calcular el valor de la Función Objetivo en un vértice, simplemente se sustituye en ella el valor de
X1 y X2 dado por las coordenadas de dicho vértice.
A continuación se da una tabla con las coordenadas de los vértices de la región factible y el valor de la
Función Objetivo en cada uno de ellos:
Vértice
Coordenadas
(X1 , X2)
Z = 3X1 + 6X2
AB
CD
4.8, 1.3, 6.0, 8.0,
4.8
10.0
10.0
8.0
43.2 63.9 78.0 72.0
←Máx. Z
Encontrar la solución óptima del problema.
En la tabla anterior, se presentaron los valores de la Función Objetivo en cada uno de los vértices de la región factible, de éstos se escoge aquel valor que cumple con lo establecido en la Función Objetivo, en este caso la Máx. Z.
Al seleccionar en la tabla el renglón de la Máx. Z, se puede leer directamente los valores de la solución
óptima del problema y el vértice donde está.
La solución óptima del problema está en el vértice «C» de la región factible y sus valores son:
X1 = 6
X2 = 10
Máx. Z = 78
En este problema, si la Función Objetivo hubiera sido de minimización, se habría escogido el 43.2 que es el valor mínimo de la tabla. Entonces, la solución óptima hubiera sido localizada en el vértice «A» con los siguientes valores:
X1 = 4.8
X2 = 4.8
mín. Z = 43.2
Como se ha observado, la solución óptima del un problema, depende de la región factible que se forme con el conjunto de restricciones y de la inclinación que tenga la Función Objetivo que le permite alcanzar su valor óptimo, así sea de maximización o de minimización.
1.2. Conceptos básicos.
Algunos conceptos básicos de la Programación Lineal que se pueden visualizar a través del Método Gráfico
son:
a. Región factible.
b. Restricción activa y Restricción redundante.
c. Demostrar que: Máx. Z = mín.(-Z)
d. Demostrar que:
«La solución óptima de cualquier problema de Programación Lineal, siempre estará en
uno de los vértices o en todo un lado de su región factible».
e. Vértices fuera de la región factible.
JEVA / PTI
6
//
PROGRAMACIÓN LINEAL
MÉTODO GRÁFICO
f. Análisis de cambios que afectan al modelo del problema.
Región factible.
La región factible es formada por las restricciones del problema y en alguno(s) de sus vértices se localiza
la solución óptima.
La forma de la región factible depende del tipo de restricciones que se tengan. Aún así, se pueden
considerar dos tipos básicos: la región factible «cerrada» y la «abierta».
La región factible cerrada se tiene cuando las restricciones, incluyendo las de «no negatividad», delimitan la región factible del problema. En el tipo abierto, se tiene una región factible no acotada que solo permite la minimización. A continuación se presentan los gráficos de estos tipos de región factible:
Figura 2. Región factible cerrada:
Región factible abierta:
a. Apoyada en los 2 ejes.
a. Hacia la derecha.
b. Apoyada en un eje.
b. Hacia arriba.
c. Sin apoyo en los ejes.
Cuando un problema modelado no tiene región factible, es debido a que algunas de sus restricciones son contradictorias entre si. Este tipo de problemas son «infactibles», es decir, que el problema modelado no tiene solución. En estos casos es necesario revisar el modelo del problema, ya que existe alguna inconsistencia en las restricciones que no permite tener una región factible.
Restricción activa y Restricción redundante.
Las restricciones que forman parte de la región factible son las «restricciones activas» mientras las que
no la forman son las «redundantes».
Las restricciones activas son las realmente forman la región factible donde está la solución óptima. Estas restricciones son la esencia del problema modelado, de tal forma que, si se quita alguna de ellas se cambia la solución óptima. Las restricciones activas que se tienen en el problema son «b», «c», «d» y «g».
Una restricción redundante no tiene ningún efecto en la solución óptima del problema, es una restricción ficticia que da lo mismo dejarla en el modelo o quitarla. Las restricciones redundantes que se tienen en el problema son «a», «e» y «f».
Demostrar que: Máx. Z = mín.(-Z)
Al demostrar que Máx. Z = mín.(-Z), también se está demostrando que lo contrario es verdadero, es
decir que mín. Z = Máx. (-Z).
Este principio es muy poderoso en la solución de problemas de minimización mediante el Método
Simplex, método que se estudiará posteriormente para solucionar problemas de cualquier tamaño. Esto
JEVA / PTI
7
//
PROGRAMACIÓN LINEAL
MÉTODO GRÁFICO
permite que un problema de minimización sea transformado y solucionado como un problema de
Maximización, cambiando solamente los signos de su Función Objetivo.
Un ejemplo de como puede ser transformado un problema modelado de minimización para ser
solucionado a través del Método Simplex, es el siguiente:
min. Z = 30X1 + 10X2→ Máx. Z = – 30X1 – 10X2
Restricciones
2X1 + 4X2≤ 80
X1 + X2 = 25
8X1 + 6X2≥ 120
Ahora se tiene un problema modelado de Maximización, donde solo se cambió de signo a la Función Objetivo y las restricciones siguieron iguales. Este problema se soluciona con el Método Simplex para encontrar la solución óptima y el valor de la Máx. Z, valor que siempre será negativo. La solución al problema original de minimización, será la misma solución que se encontró para el problema resuelto de Máx (-Z) y el valor de la min. Z será el mismo que la Máx. Z pero con signo positivo.
Regresando a la demostración pedida, la podemos hacer en una forma muy simple. Aprovechando las coordenadas de los vértices de la región factible que se tienen en la tabla, se pueden sustituir en la Función Objetivo que quedó transformada como
mín. Z = -3X1 -6X2. A continuación se presenta el
análisis que permite hacer la demostración:
Vértice
Coordenadas
(X1, X2)
Z = 3X1 + 6X2
Z = -3X1 + 6X2
AB
CD
4.8, 1.3, 6.0, 8.0,
4.8
10.0
10.0
8.0
43.2 63.9 78.0 72.0
-43.2 -63.9 -78.0 -72.0
←Máx. Z
Comparando los valores de la solución óptima del problema, se puede concluir que:
Máx. Z = mín(-Z) y consecuentemente que mín. Z = Máx.(-Z)
Demostrar que:
«la solución óptima de cualquier problema de Programación Lineal, siempre estará en
uno de los vértices o en todo un lado de su región factible».
La solución óptima de un problema de Programación Lineal puede ser de dos tipos: solución «puntual o
única» y la solución en forma de «rango».
La solución del tipo puntual siempre estará en uno de los vértices de la región factible, como consecuencia de la pendiente que tiene la Función Objetivo al cruzar dicha región. Si se desplaza paralelamente la Función Objetivo a través de la región factible, se verá que la solución óptima estará en uno de los vértices.
Cuando la Función Objetivo es paralela a una de las restricciones que forman la región factible, se provoca un «rango óptimo» de soluciones. Este rango óptimo es consecuencia de que la Función Objetivo cruza la región factible por todo un lado, desde un vértice hasta el otro. Este rango de soluciones óptimas significa que se puede generar al menos una «solución óptima alterna» para el problema, o bien, una gama de «soluciones óptimas múltiples».
Para demostrar que la solución óptima está en uno de los vértices de la región factible, se puede ver en la tabla anterior, el listado de valores que adopta la Función Objetivo al cruzar por cada uno de los vértices y simplemente seleccionar el máximo valor que es la Máx. Z. Se observará que dicha solución óptima está en el vértice «C».
Otra forma que se tiene de hacer esta demostración, es que al graficar la Función Objetivo con el valor
de la Máx. Z deberá pasar por el vértice «C». El graficar la recta de la Función Objetivo es exactamente
JEVA / PTI
8
//
PROGRAMACIÓN LINEAL
MÉTODO GRÁFICO
igual que graficar la recta de una restricción. La ecuación de la Función Objetivo que se debe graficar es
la siguiente:
78 = 3X1 + 6X2
Con esta ecuación, se puede calcular los dos puntos sobre los ejes por donde pasa la Función Objetivo quedando P1(26,0) y P2(0,13). Al graficar la recta, se observa que efectivamente pasa por el vértice «C» como lo muestra la gráfica de las restricciones.
Con la intención de mostrar un problema que tenga «soluciones óptimas múltiples», se modificó
ligeramente el problema actual. Se dejaron las mismas restricciones y se cambió la Función Objetivo a:
Máx. Z = 6X1 + 6X2
Como las restricciones no cambiaron, se tiene la misma región factible con los mismos vértices y coordenadas que se pueden utilizar para sacar los valores de la Función Objetivo que se muestran en la siguiente tabla:
Vértice
Coordenadas
(X1 , X2)
Z = 6X1 + 6X2
AB
CD
4.8, 1.3, 6.0, 8.0,
4.8
10.0
10.0
8.0
57.6 67.8 96.0 96.0
}Rango Óptimo
Al buscar en la tabla anterior la solución óptima del problema, se encuentra dos soluciones óptimas, es decir una de ellas será la solución óptima y la otra será una solución óptima alterna, quedando en la siguiente forma:
Solución Óptima
Solución Óptima Alterna
(Vértice «C»)
(Vértice «D»)
X1 = 6
X1 = 8
X2 = 10
X2 = 8
Máx. Z = 96
Máx. Z = 96
Al tener dos soluciones óptimas se puede calcular el «rango óptimo» para el problema, quedando en la
siguiente forma:
6≤ X1≤ 8
8≤ X2≤ 10
Máx. Z = 96
Conociendo el rango óptimo, se pueden generar múltiples soluciones óptimas para el problema. Por ejemplo, para calcular otra solución óptima, que sea diferente a las que ya conocemos, se puede dar un valor arbitrario a una de las variables siempre y cuando este dentro de su rango. Si consideramos X1 = 7 entonces, sustituyendo este valor en la Función Objetivo, queda:
96 = 6(7) + 6X2
X2 = 9
Esta nueva solución óptima del problema fue sacada del rango óptimo, quedando como:
X1 = 7
X2 = 9
Máx. Z = 96
En esta forma, se pueden generar diferentes soluciones óptimas para el problema, pero todas ellas tendrán como característica el mismo valor de Máx. Z = 96. Algunas otras soluciones óptimas que se pueden sacar del rango óptimo son:
JEVA / PTI
9
//
PROGRAMACIÓN LINEAL
MÉTODO GRÁFICO
X1 = 6
X1 = 8
X2 = 10
X2 = 8
Máx Z = 96
Máx. Z = 96
Una advertencia, si se fijan las dos variables al mismo tiempo, aún con valores que estén dentro de sus rangos, no necesariamente ésto será una solución óptima para el problema. Por ejemplo, considere X1 = 6 y X2 = 9. Esta solución no es óptima, ya que sustituyendo en la Función Objetivo se tiene una Máx. Z = 90 pero no de 96. La razón se puede ver gráficamente, si se ubica este punto, se observará que está dentro de la región factible pero no sobre la recta que une los vértices «C» y «D», por lo que este punto es una solución factible pero no óptima. Solo los puntos que están exactamente sobre la recta que une los vértices «C» y «D» darán soluciones óptimas.
Vértices fuera de la región factible.
Anteriormente, se estableció que la solución óptima está en algún vértice de la región factible. También
se pueden ver en la gráfica, vértices que están fuera de la región factible, por lo que podemos preguntar:
¿Qué significado tiene el vértice formado por el cruce de las restricciones «a» y «c»?
Este vértice está formado por la restricción «a» que es redundante y por la restricción «c» que es activa ya que forma parte e la región factible. Además, este vértice está fuera de la región factible como lo muestra la gráfica, lo que significa, que ese punto no cumple con todas las restricciones del problema modelado y que tiene algún recurso sobrante. El recurso sobrante estará en la restricción redundante por lo que se puede calcular su valor. La restricción activa indica que el recurso ha sido utilizado completamente por lo que no hay sobrantes.
Si quiere conocer todas las restricciones que el vértice puede cumplir y las que no, es necesario calcular sus coordenadas para tener un valor de X1 y de X2. Resolviendo las ecuaciones de las restricciones «a» y «c», se tiene que X1 = 10 y X2 = 6. Al sustituir estos valores en cada una de las restricciones del problema modelado, se podrá decir si cumple o no con la restricción particular. Haciendo esto, nos damos cuenta que este vértice no cumple con la restricción «g» pero si con todas las demás.
Además de identificar la restricción con la que no cumple el vértice, también se puede hacer un «análisis de los recursos». Para hacer este análisis, se debe sustituir los valores de la solución óptima (X1=6 y X2=10) en las restricciones que forman el vértice. A continuación se muestra el análisis:
Restricción «a»:
X1≤ 10
6≤ 10
Sobran 4.
Restricción «c»:
X1 + X2≤ 16
6 + 10≤ 16 No sobra nada.
Se concluye que sobran 4 del recurso utilizado en la restricción «a» ya que se gastaron 6 de los 10 disponibles. Por otra parte, se gastó totalmente el recurso de la restricción «c» que forma parte de la región factible.
¿Qué significado tiene el vértice formado por las restricciones «a» y «e»?
Es un vértice fuera de la región factible donde sus dos restricciones son redundantes ya que no forman parte de la región factible. Al sustituir los valores de la solución óptima en las dos restricciones, se puede hacer el siguiente análisis de los recursos:
Restricción «a»:
X1≤ 10
6≤ 10
Sobran 4
Restricción «e»:
X1 + X2≤ 20
6 + 10≤ 20
Sobran 4
JEVA / PTI
10
//
PROGRAMACIÓN LINEAL
MÉTODO GRÁFICO
Se concluye que, un vértice fuera de la región factible siempre tendrá recursos sobrantes en cada
restricción redundante que tenga.
Análisis de cambios que afectan al modelo del problema.
Un problema modelado de Programación Lineal, que experimente algún tipo de cambio, puede o no cambiar su solución óptima dependiendo del cambio. Existen dos tipos básicos de cambio: el cambio de un coeficiente de contribución de la Función Objetivo o el cambio en la disponibilidad de los recursos de las restricciones.
Un cambio en alguno de los coeficientes de la Función Objetivo, equivale a rotar dicha Función Objetivo. Cuando se quiere provocar una solución óptima alterna, se rota la Función Objetivo hasta quedar paralela a una restricción activa. Dependiendo del sentido de la rotación que se haga en la Función Objetivo así será el cambio que tenga su ecuación.
Anteriormente, se trabajó un problema de rotación de la Función Objetivo donde se modificó la ecuación de una Máx. Z = 3X1 + 6X2 a Máx. Z = 6X1 +6X2. Más adelante se presentan los pasos que se siguieron para calcular esta «nueva Función Objetivo» que tiene una solución óptima alterna.
Si el cambio realizado afecta a la «disponibilidad del recurso» de la restricción, es decir al término independiente, entonces la recta se moverá paralelamente. Si el término independiente aumenta de valor, hará que la recta se mueva paralelamente hacia arriba o hacia la derecha. Por el contrario, si disminuye de valor, la recta se moverá paralelamente hacia abajo o hacia la izquierda.
Existen otros tipos de cambios que puede experimentar el modelo del problema, por ejemplo, quitar una restricción, agregar una nueva restricción, cambiar el sentido de una restricción. Dependiendo del tipo de cambio será el efecto que tenga en la solución óptima del problema. Estos cambios se analizan a continuación con las siguientes preguntas:
¿Qué pasa con la solución óptima del problema si se «quita» la restricción «a»?
Como la restricción «a» es una restricción redundante, al quitarla del modelo no afecta en nada a la
región factible por lo que la solución óptima sigue siendo la misma.
¿Se modifica la región factible del problema al quitar la restricción «b»?
Si en el modelo del problema se quita solo la restricción «b» que es una restricción activa, si se modifica
la región factible y en consecuencia cambia la solución óptima del problema.
¿Cambia la solución óptima del problema si se agrega al problema una nueva restricción, por
ejemplo X2 <= 7?
Esta nueva restricción disminuye la región factible que se tenía anteriormente, consecuentemente
cambia la solución óptima del problema.
¿Se afecta la solución óptima del problema si se cambia el «sentido» de la restricción «e»?
Al hacer este cambio, el problema modelado no tiene una solución óptima ya que se vuelve «infactible» a
consecuencia de que no tiene una región factible que cumpla con todas las restricciones.
¿Cómo se puede modificar la ecuación de una Función Objetivo para que tenga una solución
óptima alterna?
Es posible hacer intencionalmente que un problema tenga una solución óptima alterna como en el caso que se presentó. Para calcular una nueva Función Objetivo que sea paralela a alguna de las restricciones del problema modelado, es necesario rotar la Función Objetivo que se tiene hasta lograr esto.
JEVA / PTI
11
//
PROGRAMACIÓN LINEAL
MÉTODO GRÁFICO
La Función Objetivo del problema original (Máx. Z = 3X1+ 6X2) se forzó a rotar hasta que fuera paralela a
la restricción «c» para generar una solución óptima alterna.
Una condición indispensable para hacer que dos rectas sean paralelas es que tengan la misma pendiente. Uno de los métodos que existen para calcular la pendiente de una recta, es ponerla en el formato
y = mx + b, donde la «m» es la pendiente de la recta. Utilizando este método, se calcula la pendiente de la restricción «c» y la pendiente que debe de tomar la nueva Función Objetivo. Se expresan ambas ecuaciones con el formato requerido despejando la misma variable, en este caso X1 (variable dependiente). El coeficiente de la X1 en la Función Objetivo cambiará de valor, por lo que se deja expresado como una variable «a» que es necesario calcular. A continuación se presentan los cálculos:
Restricción «c» Nueva Función Objetivo
X1 + X2 = 16
Z = aX1
+ 6X2
X1 = -X2 + 16
X1 = (-6/a)X2 + Z/a
m = -1
m = -6/a
Para hacer estas dos rectas paralelas se igualan sus pendientes quedando:
-1 = -6/a
a = 6
Conociendo que a = 6, se puede sustituir este valor para dar la ecuación de la nueva Función Objetivo
que será:
Máx. Z = 6X1 + 6X2.
Se puede establecer que, si la rotación de la Función Objetivo es en el sentido de las manecillas del reloj, el coeficiente de la variable dependiente (en nuestro caso X1) incrementará su valor. Por el contrario, si la rotación es en contra de las manecillas del reloj, el coeficiente de la variable independiente (en nuestro caso X2) aumentará su valor. En ambos casos se tendrá una ecuación modificada por la rotación de la Función Objetivo.
En el problema desarrollado, el coeficiente de la X1 (variable dependiente) pasó de 3 a 6, es decir que se rotó la Función Objetivo en el sentido de las manecillas del reloj. Esta rotación se puede visualizar fácilmente
en la gráfica.
Ejercicio 2. Modelación, solución e interpretación para un problema de Programación Lineal.
Partiendo de un problema, se presenta el desarrollo de cada una de las partes que conforman el ciclo completo de la solución de un problema de Programación Lineal: la modelación del problema, la solución del mismo y la interpretación de la solución óptima obtenida:
Fabricación de Fertilizantes.
Una empresa de productos químicos fabrica, entre otros artículos, dos tipos de fertilizantes que requieren de la combinación de ciertos ingredientes que son comprados a proveedores extranjeros. Como cada mes se tiene que planear las toneladas que se deben de producir de cada fertilizante, se debe de considerar para hacer el programa de producción, el precio de venta de los fertilizantes, el costo de los ingredientes, cualquier pedido que se deba surtir y las restricciones propias de la fabrica como son la disponibilidad de mano de obra, la disponibilidad de materias primas en el almacén y los tiempos requeridos en el proceso de fabricación.
JEVA / PTI
12
//
PROGRAMACIÓN LINEAL
MÉTODO GRÁFICO
Otro aspecto a considerar es, que la empresa está implementando una nueva estrategia de mercadotecnia que consiste en vender sus fertilizantes mediante un mayorista en vez de hacerlo ella misma. Esto ha cambiado la forma normal de programar la producción, ya que ahora solo se deben considerar las restricciones de producción pero no las de ventas.
Uno de los fertilizante fabricado es el 5-5-10, indicando con estos números, la mezcla de los ingredientes que utiliza el fertilizante, en este caso es 5% de Nitrato, 5% de Fosfato, 10% de Potasio y el resto es un estabilizador formado por un relleno de tierra. El otro fertilizante llamado 5-10-5, tiene 5% de Nitrato, 10% de Fosfato, 5% de Potasio y resto es el relleno de tierra. El mayorista pagará a $715 la tonelada del 5-5-10 y $690 por el 5-10-5. La disponibilidad y los costos de las materias primas para el próximo mes son: 1,100 toneladas de Nitrato a $2000 por tonelada, 1,800 toneladas de Fosfato a $800 cada una y 2,000 toneladas de Potasio a $1600 cada una. La tierra está disponible en cantidades ilimitadas a un costo de $100 por tonelada. Considere que no hay restricciones por la capacidad de producción pero si existe un costo de mezclado de $150 por tonelada para cualquiera de los fertilizantes.
La empresa quiere desarrollar un modelo, que le ayude a utilizar correctamente los ingredientes que importa, para elaborar su programa de producción mensual de tal forma que permita maximizar su utilidad.
Después de conocer el problema, es conveniente organizar los datos que se dan en el mismo para
posteriormente modelarlo. En la siguiente tabla se presentan los datos del problema ya estructurados:
Tabla de Datos.
Ingredientes
Fertilizante (%)
5-5-10
5-10-5
Disponibilidad
(ton/mes)
Costo
($/ton)
Nitrato
Fosfato
Potasio
Relleno
55
10
80
5
10
5
80
1,100 1,800 2,000
ilimitado
2000
800
1600
100
Precio Venta
($/ton)
715
690
El costo de mezclado de cualquiera de los fertilizantes es de $150 por tonelada.
Modelación.
Variables de Decisión.
Xi = Toneladas del Fertilizante «i» a fabricarse por mes
(ton/mes)
Función Objetivo.
Para hacer la Función Objetivo, primero se debe calcular el margen de utilidad por tonelada de cada uno
de los fertilizantes en base a la siguiente ecuación:
Utilidad = Precio Venta – Costo Total
($/ton)
($/ton)
($/ton)
Se calcula el costo total por tonelada de fertilizante en base a la siguiente ecuación:
Costo Total = Costo de Materia Prima + Costo de mezclado
($/ton)
($/ton)
($/ton)
Fertilizante 5-5-10:
Costo Materia Prima = 0.05(2000)+0.05(800)+0.10(1600)+0.80(100)
= $380/ton
Costo de Mezclado = $150/ton
Costo Total
= $530/ton
Margen de Utilidad = 715 – 530 = $185/ton
JEVA / PTI
13
//
PROGRAMACIÓN LINEAL
MÉTODO GRÁFICO
Fertilizante 5-10-5:
Costo Materia Prima = 0.05(2000)+0.10(800)+0.05(1600)+0.80(100)
Aplicando la metodología del Método Gráfico tenemos:
Calcular los puntos para graficar cada restricción.
Puntos a graficar:
(X1,0)
(0,X2)
Nitrato
0.05X1 + 0.05X2≤ 1,100
22,000
22,000
Fosfato
0.05X1 + 0.10X2≤ 1,800
Potasio
0.10X1 + 0.05X2≤ 2,000
36,000
18,000
20,000
40,000
Graficar las restricciones y la región factible.
Calcular las coordenadas de los vértices de la región factible y el valor de la Función
Objetivo.
JEVA / PTI
14
//
PROGRAMACIÓN LINEAL
MÉTODO GRÁFICO
Los vértices «A» y «D» están en los ejes por lo que se pueden leer directamente de la gráfica, de la tabla de los puntos para graficar o bien se puede calcular. A continuación se ejemplifica el cálculo del vértice «A»:
0.05X1 + 0.10 X2 = 1,800
X1 = 0
Como X1=0 ya que está sobre el eje X2, entonces sustituyendo en la ecuación, se tiene que
X2=18,000, luego las coordenadas del vértice «A» son (0,18000).
Se pueden leer directamente las coordenadas del vértice «D» que son (20000,0).
El vértice «E» tiene de coordenadas (0,0).
Los vértices «B» y «C» están fuera de los ejes por lo que es necesario resolver las dos ecuaciones que
forman cada uno de los vértices y resolverlas por simultáneas.
Vértice «B»: Fosfato 0.05X1 + 0.10X2 = 1,800
Nitrato -(0.05X1 + 0.05X2 = 1,100)
0
0.05X2 = 700
X2 = 14,000
Sustituyendo X2 en una de las ecuaciones originales se tiene:
Fosfato 0.05X1 + 0.10(14,000) = 1,800
X1 = 8,000
Las coordenadas del vértice «B» son (8000,14000).
Vértice «C»:
Potasio 0.10X1 + 0.05X2 = 2,000
Nitrato -(0.05X1 + 0.05X2 = 1,100)
0.05X1
0 = 900
X1 = 18,000
Sustituyendo X1 se tiene: 0.10(18,000) + 0.05X2 = 2,000
X2 = 4,000
Las coordenadas del vértice «C» son (18000,4000).
En la siguiente tabla, se tiene un resumen de las coordenadas de cada vértice de la región factible y el
valor de la Función Objetivo:
Vértice
Coordenadas
(X1, X2)
Z = 185X1 + 200X2
($/mes)
AB
CDE
0
8,000
18,000
20,0000
18,000
14,000
4,00000
3600,000 4280,000 4130,000 3700,000
0
←Máx. Z
Encontrar la solución óptima del problema.
Con base en la tabla anterior, se determina que la solución óptima está en el vértice «B» y es:
X1 = 8,000
X2 = 14,000
Máx. Z = $4280,000
Interpretación de la Solución Óptima.
JEVA / PTI
15
//
PROGRAMACIÓN LINEAL
MÉTODO GRÁFICO
En la interpretación, es importante fijarse en el tipo de variables que maneja el problema. Las variables pueden ser de dos tipos: discretas y continuas. Las «variables discretas» se pueden expresar solo en valores enteros, mientras que las «variables continuas» se pueden expresar en cualquier valor, entero o fraccionado.
Este problema tienen variables continuas por lo que se puede hacer la siguiente interpretación:
El programa de producción para el siguiente mes será 8,000 toneladas del fertilizante 5-5-10 (X1 = 8,000)
y 14,000 toneladas del fertilizante 5-10-5 (X2 = 14,000) para tener la máxima utilidad de $4280,000 (Máx.
Z = 4280,000).
Después de hacer este programa de producción se tendrán 500 toneladas sobrantes de Potasio.
La Programación Lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales, optimizando la función objetivo, también lineal.
Consiste en optimizar (minimizar o maximizar) una función lineal, denominada función objetivo, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales.
1. Introducción a la Investigación de Operaciones.
1.1. Historia de la Investigación de Operaciones.
La primera actividad de Investigación de Operaciones se dio durante la Segunda Guerra Mundial en Gran Bretaña, donde la Administración Militar llamó a un grupo de científicos de distintas áreas del saber para que estudiaran los problemas tácticos y estratégicos asociados a la defensa del país.
El nombre de Investigación de Operaciones fue dado aparentemente porque el equipo estaba llevando a cabo la actividad de investigar operaciones (militares).
Motivados por los resultados alentadores obtenidos por los equipos británicos, los administradores militares de Estados Unidos comenzaron a realizar investigaciones similares. Para eso reunieron a un grupo selecto de especialistas, los cuales empezaron a tener buenos resultados y en sus estudios incluyeron problemas logísticos complejos, la planeación de minas en el mar y la utilización efectiva del equipo electrónico.
Al término de la guerra y atraídos por los buenos resultados obtenidos por los estrategas militares, los administradores industriales empezaron a aplicar las herramientas de la Investigación de Operaciones a la resolución de sus problemas que empezaron a originarse debido al crecimiento del tamaño y la complejidad de las industrias.
Aunque se ha acreditado a Gran Bretaña la iniciación de la Investigación de Operaciones como una nueva disciplina, los Estados Unidos tomaron pronto el liderazgo en este campo rápidamente creciente. La primera técnica matemática ampliamente aceptada en el medio de Investigación de Operaciones fue el Método Símplex de Programación Lineal, desarrollado en 1947 por el matemático norteamericano George B. Dantzig. Desde entonces las nuevas técnicas se han desarrollado gracias al esfuerzo y cooperación de las personas interesadas tanto en el área académica como en el área industrial.
Un segundo factor en el progreso impresionante de la Investigación de Operaciones fue el desarrollo de la computadora digital, que con sus tremendas capacidades de velocidad de cómputo y de almacenamiento y recuperación de información, permitieron al tomador de decisiones rapidez y precisión.
Si no hubiera sido por la computadora digital, la Investigación de Operaciones con sus grandes problemas de computación no hubiera crecido al nivel de hoy en día.
Actualmente la Investigación de Operaciones se está aplicando en muchas actividades. Estas actividades han ido más allá de las aplicaciones militares e industriales, para incluir hospitales, instituciones financieras, bibliotecas, planeación urbana, sistemas de transporte y sistemas de comercialización.
1.2. Características de la Investigación de Operaciones.
Es muy notable el rápido crecimiento del tamaño y la complejidad de las organizaciones (empresas) humanas que se ha dado en estos últimos tiempos. Tal tamaño y complejidad nos hace pensar que una sola decisión equivocada puede repercutir grandemente en los intereses y objetivos de la organización y en ocasiones pueden pasar años para rectificar tal error. También el ritmo de la empresa de hoy implica que las DECISIONES se tomen más rápidamente que nunca, pues el hecho de posponer la acción puede dar una decisiva ventaja al contrario en este mundo de la competencia.
La palpable dificultad de tomar decisiones ha hecho que el hombre se aboque en la búsqueda de una herramienta o método que le permita tomar las mejores decisiones de acuerdo a los recursos disponibles y a los objetivos que persigue. Tal herramienta recibió el nombre de Investigación de Operaciones.
De la definición de Investigación de Operaciones, como veremos en el siguiente apartado, podemos resaltar los siguientes términos: organización, sistema, grupos interdisciplinarios, objetivo y metodología científica.
Una organización puede entenderse como un sistema, en el cual existen componentes; canales que comunican tales componentes e información que fluye por dichos canales. En todo sistema las componentes interactúan unas con otras y tales interacciones pueden ser controlables e incontrolables. En un sistema grande, las componentes se relacionan de muchas maneras, pero no todas son importantes, o mejor dicho, no todas las interacciones tienen efectos importantes en las componentes del sistema.
Por lo tanto es necesario que exista un procedimiento sistemático que identifique a quienes toman decisiones y a las interacciones que tengan importancia para los objetivos de la organización o sistema. Uno de esos procedimientos es precisamente la Investigación de Operaciones.
Una estructura por la que no fluye información, no es dinámica, es decir, no podemos considerarla como un sistema. Por lo tanto podemos decir que la información es lo que da “vida” a las estructuras u organizaciones humanas.
Los objetivos de toda organización serán siempre alcanzar el liderato en su rama, controlando la eficiencia y efectividad de todas sus componentes por medio de métodos que permitan encontrar las relaciones óptimas que mejor operen el sistema, dado un objetivo específico.
Ante el tremendo avance que se ha dado en casi todas las ciencias en las últimas décadas, ya no es factible querer saber un poco de todo, sino más bien especializarse en alguna rama de la ciencia. Los problemas que se presentan en las organizaciones no fácilmente se pueden resolver por un sólo especialista. Por el contrario son problemas multidisciplinarios, cuyo análisis y solución requieren de la participación de varios especialistas. Estos grupos interdisciplinarios necesariamente requieren de un lenguaje común para poder entenderse y comunicarse, donde la Investigación de Operaciones viene a ser ese puente de comunicación.
El enfoque de la Investigación de Operaciones es el mismo del método científico. En particular, el proceso comienza por la observación cuidadosa y la formulación del problema y sigue con la construcción de un modelo científico (por lo general matemático) que intenta abstraer la esencia del problema real. En este punto se propone la hipótesis de que el modelo es una representación lo suficientemente precisa de las características esenciales de la situación como para que las conclusiones (soluciones) obtenidas sean válidas también para el problema real. Esta hipótesis se verifica y modifica mediante las pruebas adecuadas. Entonces, en cierto modo, la Investigación de Operaciones incluye la investigación científica creativa de las propiedades fundamentales de las operaciones. Sin embargo, existe más que esto. En particular, la Investigación de Operaciones se ocupa también de la administración práctica de la organización. Así, para tener éxito, deberá también proporcionar conclusiones positivas y claras que pueda usar el tomador de decisiones cuando las necesite.
La contribución del enfoque de Investigación de Operaciones proviene principalmente de:
1. La estructuración de una situación de la vida real como un modelo matemático, logrando una abstracción de los elementos esenciales para que pueda buscarse una solución que concuerde con los objetivos del tomador de decisiones. Esto implica tomar en cuenta el problema dentro del contexto del sistema completo.
2. El análisis de la estructura de tales soluciones y el desarrollo de procedimientos sistemáticos para obtenerlas.
3. El desarrollo de una solución, incluyendo la teoría matemática si es necesario, que lleva al valor óptimo de la medida de lo que se espera del sistema (o quizá que compare los cursos de acción opcionales evaluando esta medida para cada uno).
1.3. Definición.
Investigación de Operaciones o Investigación Operacional. Se puede definir de la siguiente manera: “La Investigación de Operaciones es la aplicación por grupos interdisciplinarios del método científico a problemas relacionados con el control de las organizaciones o sistemas a fin de que se produzcan soluciones que mejor sirvan a los objetivos de toda la organización”.
1.4. Metodología de la Investigación de Operaciones.
El proceso de la Investigación de Operaciones comprende las siguientes fases:
1.Formulación y definición del problema.
2.Construcción del modelo.
3.Solución del modelo.
4.Validación del modelo.
5.Implementación de resultados.
Demos una explicación de cada una de las fases:
1.Formulación y definición del problema. En esta fase del proceso se necesita: una descripción de los objetivos del sistema, es decir, qué se desea optimizar; identificar las variables implicadas, ya sean controlables o no; determinar las restricciones del sistema. También hay que tener en cuenta las alternativas posibles de decisión y las restricciones para producir una solución adecuada.
2.Construcción del modelo. En esta fase, el investigador de operaciones debe decidir el modelo a utilizar para representar el sistema. Debe ser un modelo tal que relacione a las variables de decisión con los parámetros y restricciones del sistema. Los parámetros (o cantidades conocidas) se pueden obtener ya sea a partir de datos pasados o ser estimados por medio de algún método estadístico. Es recomendable determinar si el modelo es probabilístico o determinístico. El modelo puede ser matemático, de simulación o heurístico, dependiendo de la complejidad de los cálculos matemáticos que se requieran.
3.Solución del modelo. Una vez que se tiene el modelo, se procede a derivar una solución matemática empleando las diversas técnicas y métodos matemáticos para resolver problemas y ecuaciones. Debemos tener en cuenta que las soluciones que se obtienen en este punto del proceso, son matemáticas y debemos interpretarlas en el mundo real. Además, para la solución del modelo, se deben realizar análisis de sensibilidad, es decir, ver como se comporta el modelo a cambios en las especificaciones y parámetros del sistema. Esto se hace, debido a que los parámetros no necesariamente son precisos y las restricciones pueden estar equivocadas.
4.Validación del modelo. La validación de un modelo requiere que se determine si dicho modelo puede predecir con certeza el comportamiento del sistema. Un método común para probar la validez del modelo, es someterlo a datos pasados disponibles del sistema actual y observar si reproduce las situaciones pasadas del sistema. Pero como no hay seguridad de que el comportamiento futuro del sistema continúe replicando el comportamiento pasado, entonces siempre debemos estar atentos de cambios posibles del sistema con el tiempo, para poder ajustar adecuadamente el modelo.
5.Implementación de resultados. Una vez que hayamos obtenido la solución o soluciones del modelo, el siguiente y último paso del proceso es interpretar esos resultados y dar conclusiones y cursos de acción para la optimización del sistema. Si el modelo utilizado puede servir a otro problema, es necesario revisar, documentar y actualizar el modelo para sus nuevas aplicaciones.
1.5. Estructura de los modelos empleados en la Investigación de Operaciones.
El enfoque de la Investigación de Operaciones es el modelaje. Un modelo es una herramienta que nos sirve para lograr una visión bien estructurada de la realidad. Así, el propósito del modelo es proporcionar un medio para analizar el comportamiento de las componentes de un sistema con el fin de optimizar su desempeño. La ventaja que tiene el sacar un modelo que represente una situación real, es que nos permite analizar tal situación sin interferir en la operación que se realiza, ya que el modelo es como si fuera “un espejo” de lo que ocurre.
Para aumentar la abstracción del mundo real, los modelos se clasifican como 1) icónicos, 2) análogos, 3) simbólicos.
Los modelos icónicos son la representación física, a escala reducida o aumentada de un sistema real.
Los modelos análogos esencialmente requieren la sustitución de una propiedad por otra con el fin de permitir la manipulación del modelo. Después de resolver el problema, la solución se reinterpreta de acuerdo al sistema original.
Los modelos más importantes para la investigación de operaciones, son los modelos simbólicos o matemáticos, que emplean un conjunto de símbolos y funciones para representar las variables de decisión y sus relaciones para describir el comportamiento del sistema. El uso de las matemáticas para representar el modelo, el cual es una representación aproximada de la realidad, nos permite aprovechar las computadoras de alta velocidad y técnicas de solución con matemáticas avanzadas.
Un modelo matemático comprende principalmente tres conjuntos básicos de elementos. Estos son: 1) variables y parámetros de decisión, 2) restricciones y 3) función objetivo.
1.Variables y parámetros de decisión. Las variables de decisión son las incógnitas (o decisiones) que deben determinarse resolviendo el modelo. Los parámetros son los valores conocidos que relacionan las variables de decisión con las restricciones y función objetivo. Los parámetros del modelo pueden ser determinísticos o probabilísticos.
2.Restricciones. Para tener en cuenta las limitaciones tecnológicas, económicas y otras del sistema, el modelo debe incluir restricciones (implícitas o explícitas) que restrinjan las variables de decisión a un rango de valores factibles.
3.Función objetivo. La función objetivo define la medida de efectividad del sistema como una función matemática de las variables de decisión.
La solución óptima será aquella que produzca el mejor valor de la función objetivo, sujeta a las restricciones.
1.6. Concepto de optimización.
Una característica adicional, que se mencionó como de pasada, es que la Investigación de Operaciones intenta encontrar la mejor solución, o la solución óptima, al problema bajo consideración. En lugar de contentarse con sólo mejorar el estado de las cosas, la meta es identificar el mejor curso de acción posible. Aún cuando debe interpretarse con todo cuidado, esta “búsqueda de la optimalidad” es un aspecto muy importante dentro de la Investigación de Operaciones.
1.7 Áreas de aplicación de la Investigación de Operaciones.
Como su nombre lo dice, Investigación de Operaciones significa “hacer investigación sobre las operaciones”. Esto dice algo del enfoque como del área de aplicación. Entonces, la Investigación de Operaciones se aplica a problemas que se refieren a la conducción y coordinación de operaciones o actividades dentro de una organización. La naturaleza de la organización es esencialmente inmaterial y, de hecho, la Investigación de Operaciones se ha aplicado en los negocios, la industria, la milicia, el gobierno, los hospitales, etc. Así, la gama de aplicaciones es extraordinariamente amplia. Casi todas las organizaciones más grandes del mundo (alrededor de una docena) y una buena proporción de las industrias más pequeñas cuentan con grupos bien establecidos de Investigación de Operaciones. Muchas industrias, incluyendo la aérea y de proyectiles, la automotriz, la de comunicaciones, computación, energía eléctrica, electrónica, alimenticia, metalúrgica, minera, del papel, del petróleo y del transporte, han empleado la Investigación de Operaciones. Las instituciones financieras, gubernamentales y de salud están incluyendo cada vez más estas técnicas.
Para ser más específicos, se consideran algunos problemas que se han resuelto mediante algunas técnicas de Investigación de Operaciones. La programación lineal se ha usado con éxito en la solución de problemas referentes a la asignación de personal, la mezcla de materiales, la distribución y el transporte y las carteras de inversión. La programación dinámica se ha aplicado con buenos resultados en áreas tales como la planeación de los gastos de comercialización, la estrategia de ventas y la planeación de la producción. La teoría de colas ha tenido aplicaciones en la solución de problemas referentes al congestionamiento del tráfico, al servicio de máquinas sujetas a descomposturas, a la determinación del nivel de la mano de obra, a la programación del tráfico aéreo, al diseño de presas, a la programación de la producción y a la administración de hospitales. Otras técnicas de Investigación de Operaciones, como la teoría de inventarios, la teoría de juegos y la simulación, han tenido exitosas aplicaciones en una gran variedad de contextos.
orígenes de la investigación de operaciones
La toma de decisiones es un proceso que se inicia cuando una persona observa un problema y determina que es necesario resolverlo procediendo a definirlo, a formular un objetivo, reconocer las limitaciones o restricciones, a generar alternativas de solución y evaluarlas hasta seleccionar la que le parece mejor, este proceso puede se cualitativo o cuantitativo.
El enfoque cualitativo se basa en la experiencia y el juicio personal, las habilidades necesarias en este enfoque son inherentes en la persona y aumentan con la práctica. En muchas ocasiones este proceso basta para tomar buenas decisiones. El enfoque cuantitativo requiere habilidades que se obtienen del estudio de herramientas matemáticas que le permitan a la persona mejorar su efectividad en la toma de decisiones. Este enfoque es útil cuando no se tiene experiencia con problemas similares o cuando el problema es tan complejo o importante que requiere de un análisis exhaustivo para tener mayor posibilidad de elegir la mejor solución.
La investigación de operaciones proporciona a los tomadores de decisiones bases cuantitativas para seleccionar las mejores decisiones y permite elevar su habilidad para hacer planes a futuro.
En el ambiente socioeconómico actual altamente competitivo y complejo, los métodos tradicionales de toma de decisiones se han vuelto inoperantes e inadmisibles ya que los responsables de dirigir las actividades de las empresas e instituciones se enfrentan a situaciones complicadas y cambiantes con rapidez que requieren de soluciones creativas y prácticas apoyadas en una base cuantitativa sólida.
En organizaciones grandes se hace necesario que el tomador de decisiones tenga un conocimiento básico de las herramientas cuantitativas que utilizan los especialistas para poder trabajar en forma estrecha con ellos y ser receptivos a las soluciones y recomendaciones que se le presenten.
En organizaciones pequeñas puede darse que el tomador de decisiones domine las herramientas cuantitativas y él mismo las aplique para apoyarse en ellas y así tomar sus decisiones.
Desde al advenimiento de la Revolución Industrial, el mundo ha sido testigo de un crecimiento sin precedentes en el tamaño y la complejidad de las organizaciones. Los pequeños talleres artesanales se convirtieron en las corporaciones actuales de miles de millones de pesos. Una parte integral de este cambio revolucionario fue el gran aumento en la división del trabajo y en la separación de las responsabilidades administrativas en estas organizaciones. Los resultados han sido espectaculares. Sin embargo, junto con los beneficios, el aumento en el grado de especialización creo nuevos problemas que ocurren hasta la fecha en muchas empresas. Uno de estos problemas es las tendencia de muchas de las componentes de una organización a convertirse en imperios relativamente autónomos, con sus propias metas y sistemas de valores, perdiendo con esto la visión de la forma en que encajan sus actividades y objetivos con los de toda la organización. Lo que es mejor para una componente, puede ir en detrimento de otra, de manera que pueden terminar trabajando con objetivos opuestos. Un problema relacionado con esto es que, conforme la complejidad y la especialización crecen, se vuelve más difícil asignar los recursos disponibles a las diferentes actividades de la manera más eficaz para la organización como un todo. Este tipo de problemas, y la necesidad de encontrar la mejor forma de resolverlos, proporcionaron el ambiente adecuado para el surgimiento de la investigación de operaciones (IO).
Las raíces de la investigación de operaciones se remontan a muchas décadas, cuando se hicieron los primeros intentos para emplear el método científico en la administración de una empresa. Sin embargo, el inicio de la actividad llamada investigación de operaciones, casi siempre se atribuye a los servicios militares prestados a principios de la segunda guerra mundial. Debido a los esfuerzos bélicos, existía una necesidad urgente de asignar recursos escasos a las distintas operaciones militares y a las actividades dentro de cada operación, en la forma más efectiva. Por esto, las administraciones militares americana e inglesa hicieron un llamado a un gran número de científicos para que aplicaran el método científico a éste y a otros problemas estratégicos y tácticos. De hecho, se les pidió que hicieran investigación sobre operaciones (militares). Estos equipos de científicos fueron los primeros equipos de IO. Con el desarrollo de métodos efectivos para el uso del nuevo radar, estos equipos contribuyeron al triunfo del combate aéreo inglés. A través de sus investigaciones para mejorar el manejo de las operaciones antisubmarinas y de protección, jugaron también un papel importante en la victoria de la batalla del Atlántico Norte. Esfuerzos similares fueron de gran ayuda en a isla de campaña en el pacífico.
Al terminar la guerra, el éxito de la investigación de operaciones en las actividades bélicas generó un gran interés en sus aplicaciones fuera del campo militar. Como la explosión industrial seguía su curso, los problemas causados por el aumento en la complejidad y especialización dentro de las organizaciones pasaron de nuevo a primer plano. Comenzó a ser evidente para un gran número de personas, incluyendo a los consultores industriales que habían trabajado con o para los equipos de IO durante la guerra, que estos problemas eran básicamente los mismos que los enfrentados por la milicia, pero en un contexto diferente. Cuando comenzó la década de 1950, estos individuos habían introducido el uso de la investigación de operaciones en la industria, los negocios y el gobierno. Desde entonces, esta disciplina se ha desarrollado con rapidez.
Se pueden identificar por lo menos otros dos factores que jugaron un papel importante en el desarrollo de la investigación de operaciones durante este período. Uno es el gran progreso que ya se había hecho en el mejoramiento de las técnicas disponibles en esta área. Después de la guerra, muchos científicos que habían participado en los equipos de IO o que tenían información sobre este trabajo, se encontraban motivados a buscar resultados sustanciales en este campo; de esto resultaron avances importantes. Un ejemplo sobresaliente es el método simplex para resolver problemas de programación lineal, desarrollado en 1947 por George Dantzing. Muchas de las herramientas características de la investigación de operaciones, como programación lineal, programación dinámica, líneas de espera y teoría de inventarios, fueron desarrolladas casi por completo antes del término de la década de 1950.
Un segundo factor que dio ímpetu al desarrollo de este campo fue el advenimiento de la computadoras. Para manejar de una manera efectiva los complejos problemas inherentes a esta disciplina, por lo general se requiere un gran número de cálculos. Llevarlos a cabo a mano puede resultar casi imposible. Por lo tanto, el desarrollo de la computadora electrónica digital, con su capacidad para realizar cálculos aritméticos, miles o tal vez millones de veces más rápido que los seres humanos, fue una gran ayuda para la investigación de operaciones. Un avance más tuvo lugar en la década de 1980 con el desarrollo de las computadoras personales cada vez más rápidas, acompañado de buenos paquetes de software para resolver problemas de IO, esto puso las técnicas al alcance de un gran número de personas. Hoy en día, literalmente millones de individuos tiene acceso a estos paquetes. En consecuencia, por rutina, se usa toda una gama e computadoras, desde las grandes hasta las portátiles, para resolver problemas de investigación de operaciones.
Naturaleza de la investigación de operaciones
Como su nombre lo dice, la investigación de operaciones significa «hacer investigación sobre las operaciones». Entonces, la investigación de operaciones se aplica a problemas que se refieren a la conducción y coordinación de operaciones (o actividades) dentro de una organización. La naturaleza de la organización es esencialmente inmaterial y, de hecho, la investigación de operaciones se ha aplicado de manera extensa en áreas tan diversas como la manufactura, el transporte, la constitución, las telecomunicaciones, la planeación financiera, el cuidado de la salud, la milicia y los servicios públicos, por nombrar sólo unas cuantas. Así, la gama de aplicaciones es extraordinariamente amplia.
La parte de investigación en el nombre significa que la investigación de operaciones usa un enfoque similar a la manera en que se lleva a cabo la investigación en los campos científicos establecidos. En gran medida, se usa el método científico para investigar el problema en cuestión. (De hecho, en ocasiones se usa el término ciencias de la administración como sinónimo de investigación de operaciones.) En particular, el proceso comienza por la observación cuidadosa y la formulación del problema incluyendo la recolección de los datos pertinentes. El siguiente paso es la construcción de un modelo científico (por lo general matemático) que intenta abstraer la esencia del problema real. En este punto se propone la hipótesis de que el modelo es una representación lo suficientemente precisa de las características esenciales de la situación como para que las conclusiones (soluciones) obtenidas sean válidas también para el problema real. Después, se llevan a cabo los experimentos adecuados para probar esta hipótesis, modificarla si es necesario y eventualmente verificarla. (Con frecuencia este paso se conoce como validación del modelo.) Entonces, en cierto modo, la investigación e operaciones incluye la investigación científica creativa de las propiedades fundamentales de las operaciones. Sin embargo, existe más que esto. En particular, la IO se ocupa también de la administración práctica de la organización. Así, para tener éxito, deberá también proporcionar conclusiones claras que pueda usar el tomador de decisiones cuando las necesite.
Una característica más de la investigación de operaciones es su amplio punto de vista. Como quedó implícito en la sección anterior, la IO adopta un punto de vista organizacional. de esta manera, intenta resolver los conflictos de intereses entre las componentes de la organización de forma que el resultado sea el mejor para la organización completa. Esto no significa que el estudio de cada problema deba considerar en forma explícita todos los aspectos de la organización sino que los objetivos que se buscan deben ser consistentes con los de toda ella.
Una característica adicional es que la investigación de operaciones intenta encontrar una mejor solución, (llamada solución óptima) para el problema bajo consideración. (Decimos una mejor solución y no la mejor solución porque pueden existir muchas soluciones que empaten como la mejor.) En lugar de contentarse con mejorar el estado de las cosas, la meta es identificar el mejor curso de acción posible. Aun cuando debe interpretarse con todo cuidado en términos de las necesidades reales de la administración, esta «búsqueda de la optimidad» es un aspecto importante dentro de la investigación de operaciones.
Todas estas características llevan de una manera casi natural a otra. Es evidente que no puede esperarse que un solo individuo sea un experto en todos lo múltiples aspectos del trabajo de investigación de operaciones o de los problemas que se estudian; se requiere un grupo de individuos con diversos antecedentes y habilidades. Entonces, cuando se va a emprender un estudio de investigación de operaciones completo de un nuevo problema, por lo general es necesario emplear el empleo de equipo. Este debe incluir individuos con antecedentes firmes en matemáticas, estadística y teoría de probabilidades, al igual que en economía, administración de empresas, ciencias de la computación, ingeniería, ciencias físicas, ciencias del comportamiento y, por supuesto, en las técnicas especiales de investigación de operaciones. El equipo también necesita tener la experiencia y las habilidades necesarias para permitir la consideración adecuada de todas las ramificaciones del problema a través de la organización.
¿Qué es la investigación de operaciones?
Como toda disciplina en desarrollo, la investigación de operaciones ha ido evolucionando no sólo en sus técnicas y aplicaciones sino en la forma como la conceptualizan los diferentes autores, en la actualidad no existe solamente una definición sino muchas, algunas demasiado generales, otras demasiado engañosas, aquí seleccionamos dos de las mas aceptadas y representativas.
La definición de Churchman, Ackoff y Arnoff: La investigación de operaciones es la aplicación, por grupos interdisciplinarios, del método científico a problemas relacionados con el control de las organizaciones o sistemas (hombre-máquina), a fin de que se produzcan soluciones que mejor sirvan a los objetivos de la organización.
De ésta definición se pueden destacar los siguientes conceptos:
1.Una organización es un sistema formado por componentes que se interaccionan, unas de estas interacciones pueden ser controladas y otras no.
2.En un sistema la información es una parte fundamental, ya que entre las componentes fluye información que ocasiona la interacción entre ellas. También dentro de la estructura de los sistemas se encuentran recursos que generan interacciones. Los objetivos de la organización se refieren a la eficacia y eficiencia con que las componentes pueden controlarse, el control es un mecanismo de autocorrección del sistema que permite evaluar los resultados en términos de los objetivos establecidos.
3.La complejidad de los problemas que se presentan en las organizaciones ya no encajan en una sola disciplina del conocimiento, se han convertido en multidisciplinario por lo cual para su análisis y solución se requieren grupos compuestos por especialistas de diferentes áreas del conocimiento que logran comunicarse con un lenguaje común.
4.La investigación de operaciones es la aplicación de la metodología científica a través modelos matemáticos, primero para representar al problema y luego para resolverlo. La definición de la sociedad de investigación de operaciones de la Gran Bretaña es la siguiente:
La investigación de operaciones es el ataque de la ciencia moderna a los complejos problemas que surgen en la dirección y en la administración de grandes sistemas de hombres, máquinas, materiales y dinero, en la industria, en los negocios, en el gobierno y en la defensa. Su actitud diferencial consiste en desarrollar un modelo científico del sistema tal, que incorpore valoraciones de factores como el azar y el riesgo y mediante el cual se predigan y comparen los resultados de decisiones, estrategias o controles alternativos. Su propósito es el de ayudar a la gerencia a determinar científicamente sus políticas y acciones.
En relación a ésta definición deben destacarse los siguientes aspectos:
1.Generalmente se asocian los conceptos de dirección y administración a las empresas de tipo lucrativo, sin embargo, una empresa es un concepto más amplio, es algo que utiliza hombres, máquinas, materiales y dinero con un propósito específico; desde éste punto de vista, se considera como empresa desde una universidad hasta una armadora de automóviles.
2.Para tratar de explicar el comportamiento de un sistema complejo, el científico debe representarlo en términos de los conceptos que maneja, lo hace expresando todos los rasgos principales del sistema por medio de relaciones matemáticas. A esta representación formal se le llama modelo.
3.La esencia de un modelo es que debe ser predictivo, lo cual no significa predecir el futuro, pero si ser capaz de indicar muchas cosas acerca de la forma en que se puede esperar que un sistema opere en una variedad de circunstancias, lo que permite valorar su vulnerabilidad. Si se conocen las debilidades del sistema se pueden tomar cursos de acción agrupados en tres categorías: A) Efectuar cambios que lleven a la empresa o parte de ella a una nueva ruta; B) Realizar un plan de toma de decisiones; C) Instalar estrategias que generen decisiones. Cuando se aplica alguno de estos remedios, la investigación de operaciones nos ayuda a determinar la acción menos vulnerable ante un futuro incierto.
4.El objetivo global de la investigación de operaciones es el de apoyar al tomador de decisiones, en cuanto ayudarlo a cumplir con su función basado en estudios científicamente fundamentados.
ENFOQUE DE LA INVESTIGACIÓN DE OPERACIONES:
la parte innovadora de la IO es sin duda alguna su enfoque modelístico, producto de sus creadores aunado a la presión de supervivencia de la guerra o la sinergía generada al combinarse diferentes disciplinas, una descripción del enfoque es la siguiente. (Ver la figura 11).
1.Se define el sistema real en donde se presenta el problema. Dentro del sistema interactuan normalmente un gran numero de variables.
2.Se seleccionan las variables que norman la conducta o el estado actual del sistema, llamadas variables relevantes, con las cuales se define un sistema asumido del sistema real.
3.Se construye un modelo cuantitativo del sistema asumido, identificando y simplificando las relaciones entre las variables relevantes mediante las utilización de funciones matemáticas.
4.Se obtiene la solución al modelo cuantitativo mediante la aplicación de una o mas de las técnicas desarrolladas por la IO.
5.Se adapta e imprime la máxima realidad posible a la solución teórica del problema real obtenida en el punto 4, mediante la consideración de factores cualitativos o no cuantificables, los cuales no pudieron incluirse en el modelo. Además se ajusta los detalles finales vía el juicio y la experiencia del tomador de decisiones.
6.Se implanta la solución en el sistema real.
La Investigación de Operaciones obtiene la solución del problema real indirectamente, y no como normalmente se intentaría pasando directamente del problema real a la solución real.
METODOLOGÍA DE LA INVESTIGACION DE OPERACIONES
Definición del problema y recolección de datos
La mayor parte de los problemas prácticos con los que se enfrenta el equipo IO están descritos inicialmente de una manera vaga. Por consiguiente, la primera actividad que se debe realizar es el estudio del sistema relevante y el desarrollo de un resumen bien definido del problema que se va a analizar. Esto incluye determinar los objetivos apropiados, las restricciones sobre lo que se puede hacer, las interrelaciones del área bajo estudio con otras áreas de la organización, los diferentes cursos de acción posibles, los límites de tiempo para tomar una decisión, etc. Este proceso de definir el problema es crucial ya que afectará en forma significativa la relevancia de las conclusiones del estudio. ¡Es difícil extraer una respuesta «correcta» a partir de un problema «equivocado»!
Por su naturaleza, la investigación de operaciones se encarga del bienestar de toda la organización, no sólo de algunos de sus componentes. Un estudio de IO busca soluciones óptimas globales y no soluciones subóptimas aunque sean lo mejor para uno de los componente. Entonces, idealmente, los objetivos que se formulan debe coincidir con los de toda la organización. Sin embargo, esto no siempre es conveniente. Muchos problemas interesan nada más a una parte de la organización, de manera que el análisis sería innecesariamente besado si los objetivos fueran muy generales y si se prestara atención especial a todos los efectos secundarios sobre el resto de la organización. En lugar de ello, los objetivos usados en un estudio deben ser tan específicos como sea posible, siempre y cuando contemplen las metas principales del tomador de decisiones y mantengan un nivel razonable de consistencia con los objetivos de los altos niveles.
Las condiciones fundamentales para que exista un problema es que se establezca una diferencia entre lo que es (situación actual) y lo que debe ser (situación deseada u objetivo) y además exista cuando menos una forma de eliminar o disminuir esa diferencia. Los componentes de un problema son: a) el tomador de decisiones o ejecutivo; b) los objetivos de la organización; c) el sistema o ambiente en el que se sitúa el problema; d) Los cursos de acción alternativos que se pueden tomar para resolverlo.
Para formular un problema se requiere; a) identificar las componentes y variables controlables y no controlables del sistema; b) identificar los posibles cursos de acción, determinados por las componentes controlables; c) definir el marco de referencia dado por las componentes no controlables; d) definir los objetivos que se busca alcanzar y clasificarlos por orden de importancia; e) identificar las interpelaciones importantes entre las diferentes partes del sistema y encontrar las restricciones que existen.
Formulación de un modelo matemático
Una vez definido el problema del tomador de decisiones, la siguiente etapa consiste en reformularlo de manera conveniente para su análisis. La forma convencional en que la investigación de operaciones realiza esto es construyendo un modelo matemático que represente la esencia del problema. Antes de analizar como formular los modelos de este tipo, se explorará la naturaleza general de los modelos y, en particular, la de los modelos matemáticos.
El modelo matemático está constituido por relaciones matemáticas (ecuaciones y desigualdades) establecidas en términos de variables, que representa la esencia el problema que se pretende solucionar.
Para construir un modelo es necesario primero definir las variables en función de las cuales será establecido. Luego, se procede a determinar matemáticamente cada una de las dos partes que constituyen un modelo: a) la medida de efectividad que permite conocer el nivel de logro de los objetivos y generalmente es una función (ecuación) llamada función objetivo; b) las limitantes del problema llamadas restricciones que son un conjunto de igualdades o desigualdades que constituyen las barreras y obstáculos para la consecución del objetivo.
Un modelo siempre debe ser menos complejo que el problema real, es una aproximación abstracta de la realidad con consideraciones y simplificaciones que hacen más manejable el problema y permiten evaluar eficientemente las alternativas de solución.
Los modelos matemáticos tienen muchas ventajas sobre una descripción verbal del problema. Una ventaja obvia es que el modelo matemático describe un problema en forma mucho más concisa. Esto tiende a hacer que toda la estructura del problema sea más comprensible y ayude a revelar las relaciones importantes entre causa y efecto. De esta manera, indica con más claridad que datos adicionales son importantes para el análisis. También facilita simultáneamente el manejo del problema en su totalidad y el estudio de todas sus interpelaciones. Por último, un modelo matemático forma un puente para poder emplear técnicas matemáticas y computadoras de alto poder, para analizar el problema. Sin duda, existe una amplia disponibilidad de paquetes de software para muchos tipos de modelos matemáticos, para micro y minicomputadoras.
Por otro lado, existen obstáculos que deben evitarse al usar modelos matemáticos. Un modelo es, necesariamente, una idealización abstracta del problema, por lo que casi siempre se requieren aproximaciones y suposiciones de simplificación si se quiere que el modelo sea manejable (susceptible de ser resuelto). Por lo tanto, debe tenerse cuidado de que el modelo sea siempre una representación válida del problema. El criterio apropiado para juzgar la validez de un modelo es el hecho de si predice o no con suficiente exactitud los efectos relativos de los diferentes cursos de acción, para poder tomar una decisión que tenga sentido. En consecuencia, no es necesario incluir detalles sin importancia o factores que tienen aproximadamente el mismo efecto sobre todas las opciones. Ni siquiera es necesario que la magnitud absoluta de la medida de efectividad sea aproximadamente correcta para las diferentes alternativas, siempre que sus valores relativos (es decir, las diferencias entre sus valores) sean bastante preciso. Entonces, todo lo que se requiere es que exista una alta correlación entre la predicción del modelo y lo que ocurre en la vida real. Para asegurar que este requisito se cumpla, es importante hacer un número considerable de pruebas del modelo y las modificaciones consecuentes. Aunque esta fase de pruebas se haya colocado después en el orden del libro, gran parte del trabajo de validación del modelo se lleva a cabo durante la etapa de construcción para que sirva de guía en la obtención del modelo matemático.
Obtención de una solución a partir del modelo
Resolver un modelo consiste en encontrar los valores de las variables dependientes, asociadas a las componentes controlables del sistema con el propósito de optimizar, si es posible, o cuando menos mejorar la eficiencia o la efectividad del sistema dentro del marco de referencia que fijan los objetivos y las restricciones del problema.
La selección del método de solución depende de las características del modelo. Los procedimientos de solución pueden ser clasificados en tres tipos: a) analíticos, que utilizan procesos de deducción matemática; b) numéricos, que son de carácter inductivo y funcionan en base a operaciones de prueba y error; c) simulación, que utiliza métodos que imitan o, emulan al sistema real, en base a un modelo.
Muchos de los procedimientos de solución tienen la característica de ser iterativos, es decir buscan la solución en base a la repetición de la misma regla analítica hasta llegar a ella, si la hay, o cuando menos a una aproximación.
Prueba del modelo
El desarrollo de un modelo matemático grande es análogo en algunos aspectos al desarrollo de un programa de computadora grande. Cuando se completa la primera versión, es inevitable que contenga muchas fallas. El programa debe probarse de manera exhaustiva para tratar de encontrar y corregir tantos problemas como sea posible. Eventualmente, después de una larga serie de programas mejorados, el programador (o equipo de programación) concluye que el actual da, en general, resultados razonablemente válidos. Aunque sin duda quedarán algunas fallas ocultas en el programa (y quizá nunca se detecten, se habrán eliminado suficientes problemas importantes como para que sea confiable utilizarlo.
De manera similar, es inevitable que la primera versión de un modelo matemático grande tenga muchas fallas. Sin duda, algunos factores o interpelaciones relevantes no se incorporaron al modelo y algunos parámetros no se estimaron correctamente. Esto no se puede eludir dada la dificultad de la comunicación y la compresión de todos los aspectos y sutilezas de un problema operacional complejo, así como la dificultad de recolectar datos confiables. Por lo tanto, antes de usar el modelo debe probarse exhaustivamente para intentar identificar y corregir todas las fallas que se pueda. Con el tiempo, después de una larga serie de modelos mejorados, el equipo de IO concluye que el modelo actual produce resultados
razonablemente válidos. Aunque sin duda quedarán algunos problemas menores ocultos en el modelo (y quizá nunca se detecten), las fallas importantes se habrán eliminado de manera que ahora es confiable usar el modelo. Este proceso de prueba y mejoramiento de un modelo para incrementar su validez se conoce como validación del modelo.
Debido a que el equipo de IO puede pasar meses desarrollando todas las piezas detalladas del modelo, es sencillo «no ver el bosque por buscar los árboles». Entonces, después de completar los detalles («los árboles») de la versión inicial del modelo, una buena manera de comenzar las pruebas es observarlo en forma global («el bosque») para verificar los errores u omisiones obvias. El grupo que hace esta revisión debe, de preferencia, incluir por lo menos a una persona que no haya participado en la formulación. Al examinar de nuevo la formulación del problema y comprarla con el modelo pueden descubrirse este tipo de errores. También es útil asegurarse de que todas las expresiones matemáticas sean consistentes en las dimensiones de las unidades que emplean. Además, puede obtenerse un mejor conocimiento de la validez del modelo variando los valores de los parámetros de entrada y/o de las variables de decisión, y comprobando que los resultados del modelo se comporten de una manera factible. Con frecuencia, esto es especialmente revelador cuando se asignan a los parámetros o a las variables valores extremos cercanos a su máximo o a su mínimo.
Un enfoque más sistemático para la prueba del modelo es emplear una prueba retrospectiva. Cuando es aplicable, esta prueba utiliza datos históricos y reconstruye el pasado para determinar si el modelo y la solución resultante hubieran tenido un buen desempeño, de haberse usado. La comparación de la efectividad de este desempeño hipotético con lo que en realidad ocurrió, indica si el uso del modelo tiende a dar mejoras significativas sobre la práctica actual. Puede también indicar áreas en las que el modelo tiene fallas y requiere modificaciones. Lo que es más, el emplear las alternativas de solución y estimar sus desempeños históricos hipotéticos, se pueden reunir evidencias en cuanto a lo bien que el modelo predice los efectos relativos de los diferentes cursos de acción.
Cuando se determina que el modelo y la solución no son válidos, es necesario iniciar nuevamente el proceso revisando cada una de las fases de la metodología de la investigación de operaciones.
ESTABLECIMIENTO DE CONTROLES SOBRE LA SOLUCION
Una solución establecida como válida para un problema, permanece como tal siempre y cuando las condiciones del problema tales como: las variables no controlables, los parámetros, las relaciones, etc., no cambien significativamente. Esta situación
se vuelve más factible cuando algunos de los parámetros fueron estimados aproximadamente. Por lo anterior, es necesario generar información adicional sobre el comportamiento de la solución debido a cambios en los parámetros del modelo. usualmente esto se conoce como análisis de sensibilidad. En pocas palabras, esta fase consiste en determinar los rangos de variación de los parámetros dentro de los cuales no cambia la solución del problema.
IMPLANTACIÓN DE LA SOLUCIÓN
El paso final se inicia con el proceso de «vender» los hallazgos que se hicieron a lo largo del proceso a los ejecutivos o tomadores de decisiones. Una vez superado éste obstáculo, se debe traducir la solución encontrada a instrucciones y operaciones comprensibles para los individuos que intervienen en la operación y administración del sistema. La etapa de implantación de una solución se simplifica en gran medida cuando se ha propiciado la participación de todos los involucrados en el problema en cada fase de la metodología. Preparación para la aplicación del modelo
Esta etapa es crítica, ya que es aquí, y sólo aquí, donde se cosecharán los beneficios del estudio. Por lo tanto, es importante que el equipo de IO participe, tanto para asegurar que las soluciones del modelo se traduzcan con exactitud a un procedimiento operativo, como para corregir cualquier defecto en la solución que salga a la luz en este momento.
El éxito de la puesta en práctica depende en gran parte del apoyo que proporcionen tanto la alta administración como la gerencia operativa. Es más probable que el equipo de IO obtenga este apoyo si ha mantenido a la administración bien informada y ha fomentado la guía de la gerencia durante el estudio. La buena comunicación ayuda a asegurar que el estudio logre lo que la administración quiere y por lo tanto merezca llevarse a la práctica. También proporciona a la administración el sentimiento de que el estudio es suyo y esto facilita el apoyo para la implantación.
La etapa de implantación incluye varios pasos. Primero, el equipo de investigación de operaciones de una cuidadosa explicación a la gerencia operativa sobre el nuevo sistema que se va a adoptar y su relación con la realidad operativa. En seguida, estos dos grupos comparten la responsabilidad de desarrollar los procedimientos requeridos para poner este sistema en operación. La gerencia operativa se encarga después de dar una capacitación detallada al personal que participa, y se inicia entonces el nuevo curso de acción. Si tiene éxito, el nuevo sistema se podrá emplear durante algunos años. Con esto en mente, el equipo de IO supervisa la experiencia inicial con la acción tomada para identificar cualquier modificación que tenga que hacerse en el futuro.
A la culminación del estudio, es apropiado que el equipo de investigación de operaciones documento su metodología con suficiente claridad y detalle para que el trabajo sea reproducible. Poder obtener una réplica debe ser parte del código de ética profesional del investigador de operaciones. Esta condición es crucial especialmente cuando se estudian políticas gubernamentales en controversia.
Introducción a la programación lineal
Muchas personas clasifican el desarrollo de la programación lineal entre los avances científicos más importantes de mediados del siglo XX, su impacto desde 1950 ha sido extraordinario. En la actualidad es una herramienta de uso normal que ha ahorrado miles o millones de pesos a muchas compañías o negocios, incluyendo empresas medianas en los distintos países industrializados del mundo; su aplicación a otros sectores de la sociedad se está ampliando con rapidez. Una proporción muy grande de los cálculos científicos en computadoras está dedicada al uso de la programación lineal.
¿Cuál es la naturaleza de esta notable herramienta y qué tipos de problemas puede manejar. Expresado brevemente, el tipo más común de aplicación abarca el problema general de asignar recursos limitados entre actividades competitivas de la mejor manera posible (es decir, en forma óptima). Con más precisión, este problema incluye elegir el nivel de ciertas actividades que compiten por recursos escasos necesarios para realizarlas. Después, los niveles de actividad elegidos dictan la cantidad de cada recurso que consumirá cada una de ellas. La variedad de situaciones a las que se puede aplicar esta descripción es sin duda muy grande, y va desde la asignación de instalaciones de producción a los productos, hasta la asignación de los recursos nacionales a las necesidades de un país; desde la selección de una cartera de inversiones, hasta la selección de los patrones de envío; desde la planeación agrícola, hasta el diseño de una terapia de radiación, etc. No obstante, el ingrediente común de todas estas situaciones es la necesidad de asignar recursos a las actividades eligiendo los niveles de las mismas.
La programación lineal utiliza un modelo matemático para describir el problema. El adjetivo lineal significa que todas las funciones matemáticas del modelo deber ser funciones lineales. En este caso, las palabra programación no se refiere a programación en computadoras; en esencia es un sinónimo de planeación. Así, la programación lineal trata la planeación de las actividades para obtener un resultado óptimo, esto es, el resultado que mejor alcance la meta especificada (según el modelo matemático) entre todas las alternativas de solución.
Aunque la asignación de recursos a las actividades es la aplicación más frecuente, la programación lineal tiene muchas otras posibilidades. de hecho, cualquier problema cuyo modelo matemático se ajuste al formato general del modelo de programación lineal es un problema de programación lineal. Aún más, se dispone de un procedimiento de solución extraordinariamente eficiente llamado método simplex, para resolver estos problemas, incluso los de gran tamaño. Estas son algunas causas del tremendo auge de la programación lineal en las últimas décadas.
Modelo de programación lineal
Los términos clave son recursos y actividades, en donde m denota el número de distintos tipos de recursos que se pueden usar y n denota el número de actividades bajo consideración. Algunos ejemplos de recursos son dinero y tipos especiales de maquinaria, equipo, vehículos y personal. Los ejemplos de actividades incluyen inversión en proyectos específicos, publicidad en un medio determinado y el envío de bienes de cierta fuente a cierto destino. En cualquier aplicación de programación lineal, puede ser que todas las actividades sean de un tipo general (como cualquiera de los ejemplos), y entonces cada una correspondería en forma individual a las alternativas específicas dentro de esta categoría general.
El tipo más usual de aplicación de programación lineal involucra la asignación de recursos a ciertas actividades. La cantidad disponible de cada recurso está limitada, de forma que deben asignarse con todo cuidado. La determinación de esta asignación incluye elegir los niveles de las actividades que lograrán el mejor valor posible de la medida global de efectividad.
Ciertos símbolos se usan de manera convencional para denotar las distintas componentes de un modelo de programación lineal. Estos símbolos se enumeran a continuación, junto con su interpretación para el problema general de asignación de recursos a actividades.
Z = valor de la medida global de efectividad
xj = nivel de la actividad j (para j = 1,2,…,n)
cj = incremento en Z que resulta al aumentar una unidad en el nivel de la actividad j
bi = cantidad de recurso i disponible para asignar a las actividades (para i = 1,2,…,m)
aij = cantidad del recurso i consumido por cada unidad de la actividad j
El modelo establece el problema en términos de tomar decisiones sobre los niveles de las actividades, por lo que x1,x2,….,xn se llaman variables de decisión. Los valores de cj, bi y aij (para i = 1,2,….,m y j = 1,2,….,n) son las constantes de entrada al modelo. Las cj, bi y aij también se conocen como parámetros del modelo.
Forma estándar del modelo
Ahora se puede formular al modelo matemático para este problema general de asignación de recursos a actividades. En Datos necesarios para un modelo de programación lineal que maneja la asignación de recursos a actividades particular, este modelo consiste en elegir valores de x1,x2,….,xn para:
optimizar (maximizar o minimizar) Z = c1x1 + c2x2 +….+ cnxn,
sujeta a las restricciones:
a11x1 + a12x2 +….+ a1nxn< b1
a21x1 + a22x2 +….+ a2nxn< b2
.
.
.
am1x1 + am2x2 +….+ amnxn< bm
X1 ³ 0, X2³0, …, Xn ³0.
Suposiciones del Modelo de Programación Lineal
Proporcionalidad
La contribución de cada actividad al valor de la función objetivo Z es proporcional al nivel de actividad xj, como lo representa el término cjxj en la función objetivo. De manera similar, la contribución de cada actividad al lado izquierdo de cada restricción funcional es proporcional al nivel de la actividad xj, en la forma en que lo representa el término aijxj en la restricción. En consecuencia, esta suposición elimina cualquier exponente diferente a 1 para las variables en cualquier término de las funciones (ya sea la función objetivo o la función en el lado izquierdo de las restricciones funcionales) en un modelo de programación lineal.
Actividad
Establece que la entrada y salida de un recurso en particular al conjunto de actividades, deben ser la misma cantidad; o sea, que las actividades transforman los recursos y no los crean o destruyen. Esta suposición garantiza que la contribución total tanto a la función objetivo como a las restricciones, es igual a la suma de las contribuciones individuales. Cuando en un problema dado no se tenga la aditividad puede recurrirse al empleo de otras técnicas de la programación matemática, dependiendo de cada caso en particular.
Aditividad
Cada función en un modelo de programación lineal (ya sea la función objetivo o el lado izquierdo de las restricciones funcionales) es la suma de las contribuciones individuales de las actividades respectivas.
Divisibilidad
Las variables de decisión en un modelo de programación lineal pueden tomar cualquier valor, incluyendo valores no enteros, que satisfagan las restricciones funcionales y de no negatividad. Así, estas variables no están restringidas a sólo valores enteros. Como cada variable de decisión representa el nivel de alguna actividad, se supondrá que las actividades se pueden realizar a niveles fracciónales.
Limitaciones del modelo de programación lineal
Modelo Determinístico
El modelo de PL involucra únicamente tres tipos de parámetros: Cj, aij y bi; de ahí su sencillez y gran aplicación. Sin embargo, el valor de dichos parámetros debe ser conocido y constante. Cuando el valor de los parámetros tiene un cierto riesgo o incertidumbre, pude utilizarse la programación paramédica, la programación estocástica, o realizarse un análisis de sensibilidad.
Modelo Estático
En algunos modelos matemáticos se han empleado con éxito las ecuaciones diferenciales, para inducir la variable tiempo en ellos. En este sentido, puede decidirse que la PL utiliza un modelo estático, ya que la variable tiempo no se involucra formalmente. Adquiriendo un poco de experiencia en la formulación de modelos de PL, puede imbuirse la temporabilidad mencionada, con el uso de subíndices en las variables.
Modelo que no suboptimiza
Debido a la forma que se plantea el modelo de PL, o encuentra la solución óptima o declara que ésta no existe. Cuando no es posible obtener una solución óptima y se debe obtener alguna, se recurre a otra técnica más avanzada que la PL, la cual se denomina programación lineal por metas.
Impacto de la investigación de operaciones
La investigación de operaciones ha tenido un impacto impresionante en el mejoramiento de la eficiencia de numerosas organizaciones en todo el mundo. En el proceso, la investigación de operaciones ha hecho contribuciones significativas al incremento de la productividad dentro de la economía de varios países. Hay ahora más de 30 países que son miembros de la International Federation of Operational Research Societies (IFORS), en la que cada país cuenta con una sociedad de investigación de operaciones.
Sin duda, el impacto de la investigación de operaciones continuará aumentando. Por ejemplo, al inicio de la década de los 90, el U.S. Bureau of Labor Statistics predijo que la IO sería el área profesional clasificada como la tercera de más rápido crecimiento para los estudiantes universitarios en Estados Unidos, graduados entre 1990 y 2005. Pronosticó también que, para el año 2005, habría 100 000 personas trabajando como analistas de investigación de operaciones.
RIESGO AL APLICAR LA INVESTIGACIÓN DE OPERACIONES
Al aplicar la I de O al estudio de sistemas y a la resolución de problemas se corre el riesgo de tratar de manipular los problemas para buscar que se ajusten a las diferentes técnicas, modelos de algoritmos establecidos en lugar de analizar los problemas y buscar resolverlos obteniendo las soluciones mejores, utilizando los métodos apropiados, es decir resolver el problema utilizando los métodos que proporcionan las mejoras soluciones y no buscar ajustar el problema a un método específico.
Para llegar a hacer un uso apropiado de la I de O, es necesario primero comprender la metodología para resolver los problemas, así como los fundamentos de las técnicas de solución para de esta forma saber cuándo utilizarlas o no en las diferentes circunstancias.
LIMITACIONES DE LA INVESTIGACIÓN DE OPERACIONES
1.Frecuentemente es necesario hacer simplificaciones del problema original para poder manipularlo y detener una solución.
2.La mayoría de los modelos sólo considera un solo objetivo y frecuentemente en las organizaciones se tienen objetivos múltiples.
3.Existe la tendencia a no considerar la totalidad de las restricciones en un problema práctico, debido a que los métodos de enseñanza y entrenamiento dan la aplicación de esta ciencia centralmente se basan en problemas pequeños para razones de índole práctico, por lo que se desarrolla en los alumnos una opinión muy simplista e ingenua sobre la aplicación de estas técnicas a problemas reales.
4.Casi nunca se realizan análisis costo-beneficio de la implantación de soluciones definidas por medio de la I de O, en ocasiones los beneficios potenciales se van superados por los costos ocasionados por el desarrollo e implantación de un modelo.
io3972 