Aplicación a la Formulación de los Modelos de Investigación de operaciones

(a) Modelo Matemático: Se emplea cuando la función objetivo y las restricciones del modelo se pueden expresar en forma cuantitativa o matemática como funciones de las variables de decisión.

(b) Modelo de Simulación: Los modelos de simulación difieren de los matemáticos en que las relación entre la entrada y la salida no se indican en forma explícita. En cambio, un modelo de simulación divide el sistema representado en módulos básicos o elementales que después se enlazan entre si vía relaciones lógicas bien definidas. Por lo tanto, las operaciones de cálculos pasaran de un módulo a otro hasta que se obtenga un resultado de salida.

Los modelos de simulación cuando se comparan con modelos matemáticos; ofrecen mayor flexibilidad al representar sistemas complejos, pero esta flexibilidad no esta libre de inconvenientes. La elaboración de este modelo suele ser costoso en tiempo y recursos. Por otra parte, los modelos matemáticos óptimos suelen poder manejarse en términos de cálculos.

Modelos de Investigación de Operaciones de la ciencia de la administración: Los científicos de la administración trabajan con modelos cuantitativos de decisiones.

Modelos Formales: Se usan para resolver problemas cuantitativos de decisión en el mundo real. Algunos modelos en la ciencia de la administración son llamados modelos deterministicos. Esto significa que todos los datos relevantes (es decir, los datos que los modelos utilizarán o evaluarán) se dan por conocidos. En los modelos probabilísticos (o estocásticos), alguno de los datos importantes se consideran inciertos, aunque debe especificarse la probabilidad de tales datos.

En la siguiente tabla se muestran los modelos de decisión según su clase de incertidumbre y su uso en las corporaciones. (D, determinista; P, probabilista; A, alto; B, bajo)

Modelo de Hoja de Cálculo Electrónica: La hoja de cálculo electrónica facilita hacer y contestar preguntas de "que si" en un problema real. Hasta ese grado la hoja de cálculo electrónica tiene una representación selectiva del problema y desde este punto de vista la hoja de cálculo electrónica es un modelo.

En realidad es una herramienta más que un procedimiento de solución. 

Etapas de la Investigación de Operaciones 

Las etapas de un estudio de Investigación de Operaciones son las siguientes:

Definición del problema de interés y recolección de los datos relevantes.

Formulación de un modelo matemático que represente el problema.

Desarrollo de un procedimiento basado en computadora para derivar una solución al problema a partir del modelo.

Prueba del modelo y mejoramiento según sea necesario.

Preparación para la aplicación del modelo prescrito por la administración.

Puesta en marcha. 

El método Simplex es un procedimiento interactivo 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 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.

Deberá tenerse en cuenta que este método sólo trabaja para restricciones que tengan un tipo de desigualdad "=" y coeficientes independientes mayores o iguales a 0, y habrá que estandarizar las mismas para el algoritmo. En caso de que después de éste proceso, aparezcan (o no varíen) restricciones del tipo "=" o "=" habrá que emplear otros métodos, siendo el más común el método de las Dos Fases.

PREPARANDO EL MODELO PARA ADAPTARLO AL MÉTODO SIMPLEX

Esta es la forma estándar del modelo:

Para ello se deben cumplir las siguientes condiciones:

El objetivo es de la forma de maximización o de minimización.

Todas las restricciones son de igualdad.

Todas las variables son no negativas.

Las constantes a la derecha de las restricciones son no negativas.

Cambio del tipo de optimización.

Si en nuestro modelo, deseamos minimizar, podemos dejarlo tal y como está, pero deberemos tener en cuenta nuevos criterios para la condición de parada (deberemos parar de realizar iteraciones cuando en la fila del valor de la función objetivo sean todos menores o iguales a 0), así como para la condición de salida de la fila. Con objeto de no cambiar criterios, se puede convertir el objetivo de minimizar la función F por el de maximizar F·(-1).

Ventajas: No deberemos preocuparnos por los criterios de parada, o condición de salida de filas, ya que se mantienen.

Inconvenientes: En el caso de que la función tenga todas sus variables básicas positivas, y además las restricciones sean de desigualdad "=", al hacer el cambio se quedan negativas y en la fila del valor de la función objetivo se quedan positivos, por lo que se cumple la condición de parada, y por defecto el valor óptimo que se obtendría es 0.

Solución: En la realidad no existen este tipo de problemas, ya que para que la solución quedara por encima de 0, alguna restricción debería tener la condición "=", y entonces entraríamos en un modelo para el método de las Dos Fases.

Conversión de signo de los términos independientes (las constantes a la derecha de las restricciones)

Deberemos preparar nuestro modelo de forma que los términos independientes de las restricciones sean mayores o iguales a 0, sino no se puede emplear el método Simplex. Lo único que habría que hacer es multiplicar por "-1" las restricciones donde los términos independientes sean menores que 0.

Ventaja: Con ésta simple modificación de los signos en la restricción podemos aplicar el método Simplex a nuestro modelo.

Inconvenientes: Puede resultar que en las restricciones donde tengamos que modificar los signos de las constantes, los signos de las desigualdades fueran ("=", "="), quedando ("=","=") por lo que en cualquier caso deberemos desarrollar el método de las Dos Fases. Este inconveniente no es controlable, aunque nos podría beneficiar si sólo existen términos de desigualdad ("=","="), y los "=" coincidieran con restricciones donde el término independiente es negativo.

Todas las restricciones son de igualdad.

Si en nuestro modelo aparece una inecuación con una desigualdad del tipo "=", deberemos añadir una nueva variable, llamada variable de exceso si, con la restricción si = 0. La nueva variable aparece con coeficiente cero en la función objetivo, y restando en las inecuaciones.

Surge ahora un problema, veamos cómo queda una de nuestras inecuaciones que contenga una desigualdad "=" :

a11·x1 + a12·x2 = b1 a11·x1 + a12·x2 – 1·xs = b1

Como todo nuestro modelo, está basado en que todas sus variables sean mayores o iguales que cero, cuando hagamos la primera iteración con el método Simplex, las variables básicas no estarán en la base y tomarán valor cero, y el resto el valor que tengan. En este caso nuestra variable xs, tras hacer cero a x1 y x2, tomará el valor -b1. No cumpliría la condición de no negatividad, por lo que habrá que añadir una nueva variable, xr, que aparecerá con coeficiente cero en la función objetivo, y sumando en la inecuación de la restricción correspondiente. Quedaría entonces de la siguiente manera:

a11·x1 + a12·x2 = b1 a11·x1 + a12·x2 – 1·xs + 1 ·xr = b1

Este tipo de variables se les llama variables artificiales, y aparecerán cuando haya inecuaciones con desigualdad ("=","="). Esto nos llevará obligadamente a realizar el método de las Dos Fases, que se explicará más adelante.

Del mismo modo, si la inecuación tiene una desigualdad del tipo "=", deberemos añadir una nueva variable, llamada variable de holgura sí, con la restricción si "=" 0 . La nueva variable aparece con coeficiente cero en la función objetivo, y sumando en las inecuaciones.

A modo resumen podemos dejar esta tabla, según la desigualdad que aparezca, y con el valor que deben estar las nuevas variables.

* 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

DESARROLLANDO EL MÉTODO SIMPLEX

Una vez que hemos estandarizado nuestro modelo, puede ocurrir que necesitemos aplicar el método Simplex o el método de las Dos Fases. Véase en la figura como debemos actuar para llegar a la solución de nuestro problema.

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.

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.

Con miras a conocer la metodología que se aplica en el Método SIMPLEX, vamos a resolver el siguiente problema:

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:

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:

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 color azulado).

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:

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:

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:

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)

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.

FORMA ESTÁNDAR DE UN PROBLEMA

Un problema lineal está en forma estándar si todas las restricciones son igualdades y se conoce una solución factible. En notación matricial, la forma estándar es:

Optimizar z = cx

Con la condición: ax = b

Con: X=> 0

Donde:

X es el vector columna de todas las variables de holgura, superfluas (exceso) y artificiales.

C es el vector renglón de los costos (utilidades) correspondientes.

a es la matriz de coeficientes de las ecuaciones de restricciones.

b es el vector columna de los lados derechos de las ecuaciones de restricciones (vector mano derecha o de disponibilidad de recursos)

SOLUCIÓN BÁSICA INICIAL FACTIBLE – S.B.I.F.

1. Se obtiene una Solución Básica Inicial por medio de la Forma Estándar del modelo, es decir, convertir las desigualdades en igualdades introduciendo variables de holgura (=).

Una Solución Básica es una Solución Básica Factible sí y sólo sí las variables Básicas tienen valores no negativos, es decir, mayores o iguales a cero (>=).

2. Debe existir en cada ecuación una variable con coeficiente +1 y que no este en ninguna otra restricción; las otras variables con coeficiente cero (0) para formar el Canónico o Base del sistema de ecuaciones. Se obtiene una Solución Básica Factible Inicial inicializando n-m variables adecuadas (No Básicas) al nivel de cero.

Donde: n Número de incógnitas

m Número de restricciones o ecuaciones

m < n

La función Objetivo no se tiene en cuenta para determinar el sistema de ecuaciones, aunque hace parte del Canónico.

VARIABLES ARTIFICIALES

Sumar una variable no negativa a primer miembro de cada ecuación o restricción que no tenga variables básicas iníciales evidentes. Esta variable desempeña la misma función que una variable de holgura, al proporcionar una variable básica inicial para una solución básica inicial.

Las variables artificiales no tienen sentido físico (artificial) y será válido cuando se hace igual a cero cuando se llegue al valor óptimo.

Se utilizan para iniciar la solución y después se hacen cero en la solución final, de lo contrario, la solución resultante será no factible.

MÉTODO DE LA GRAN M

Una variable artificial se agrega a una restricción si ésta no ha cumplido con el punto (2) y debe ser incluida en la Función Objetivo con un coeficiente M negativo (-) muy grande (en caso de maximización) ó un coeficiente M positivo (+) muy grande (en caso de minimización).

Las variables artificiales se sustituyen en la función objetivo.

Las variables artificiales proporcionan las variables Básicas que se necesitan para las ecuaciones que no cumplen con el punto (2) y así poder tener una Solución Básica Factible Inicial.

El motivo de por que el coeficiente de las variables artificiales debe ser un valor muy grande, es para que en una sucesión de pivotes estas variables resulten ser No Básicas (iguales a cero).

Cada vez que una variable artificial es retirada de la base, la columna correspondiente puede ser eliminada también de la tabla.

TÉCNICA DE LAS DOS FASES

FASE I

• a. Aumentar variables artificiales para dar una solución básica inicial.

• b. Formar una segunda función objetivo que haga la minimización de la suma de las variables artificiales sujeta a las restricciones del problema original modificados por las variables artificiales.

• c. Sí el valor mínimo de la nueva función objetivo es igual a cero, es decir, todas las variables artificiales son cero, hay un espacio de Soluciones Factibles, de lo contrario el problema no tiene solución factible.

FASE II

• 1. Se utiliza la solución básica óptima de la Fase I como la solución inicial para el problema original, eliminando las variables artificiales no básicas y se toman las nuevas ecuaciones dadas en esta fase I.

• 2. Estas ecuaciones son equivalentes a las de la forma estándar del problema original, antes de que se el sumaran las variables artificiales.

• 3. Se sustituyen las variables básicas de la Fase I en la función objetivo del problema original.

• 4. Se verifica la condición de optimidad en el tablero Simplex, con el fin de determinar una Solución Optima.

MÉTODO DUAL SIMPLEX

En el sentido de Maximización, la iteración primal no es óptima cuando se tienen los coeficientes Cj < 0 por lo menos para una variable. Sólo en el óptimo tenemos Cj > 0 pata todas las j.

Desde el punto de vista de la dualidad se tiene Cj < 0 lo que significa que el dual es infactible cuando el primal es no óptimo.

Por otra parte, cuando Cj >= 0 , indica que el dual se vuelve factible, cuando el primal alcanza la optimidad.

Esto significa que se debe trabajar con un nuevo método de solución para programas lineales, que comienza infactible pero óptima (los coeficientes de la función Objetivo son negativos – minimización). El problema Simplex regular empieza factible pero no óptimo.

El nuevo método, llamado Simplex Dual, conservará la optimidad y las iteraciones sucesivas trabajarán para anular la infactibilidad.

Cuando se llega a la factibilidad, el proceso termina porque la solución es factible y óptima.

CONDICIÓN DE FACTIBILIDAD

La variable que sale es la variable básica que tiene el valor más negativo. (Los empates se rompen arbitrariamente.) Si todas las variables básicas son no negativas el proceso termina y se alcanza la solución factible (óptima).

CONDICIÓN DE OPTIMIDAD

La variable que entra se elige de entre las variables no básicas como sigue:

Se toman los cocientes (razones) de los coeficientes del lado izquierdo de la ecuación de la función objetivo entre los coeficientes correspondientes a la ecuación (fila) asociada a la variable que sale de la base. Ignore los cocientes (razones) asociados a denominadores positivos o cero.

La Variable que entra es aquella con el cociente (razón) más pequeño si el problema es de minimización o el valor absoluto más pequeño de las razones si el problema es de maximización (Los empates se rompen arbitrariamente). Si todos los denominadores son ceros o positivos el problema no tiene ninguna solución factible.

Después de elegir la variable que entra y la que sale, se aplican los operaciones de renglón como es usual para obtener la siguiente iteración de la solución.

INTERPRETACIÓN DE LAS VARIABLES DUALES

Yi se interpreta como la contribución a la ganancia por unidad del recurso i, cuando se usa el conjunto actual de Variables Básicas para obtener la solución primal.

En términos generales nos pueden indicar cuales unidades de recursos o capacidades podrían ser compradas o vendidas y sus respectivos valores.

"La solución óptima del problema dual proporciona los precios en el mercado o los beneficios de los recursos escasos asignados en el problema original."

AFIRMACIONES SOBRE UNA SOLUCIÓN ÓPTIMA

1. Si una restricción del primal es sobresatisfecha (Variable Holgura > 0) entonces la correspondiente variable dual es cero.

2. Si una variable real del dual es positiva, la restricción correspondiente en el primal es exactamente satisfecha (Variable Holgura primal = 0)

3. Si una de las restricciones del dual es sobresatisfecha (Variable Holgura-exceso del dual > 0) entonces la correspondiente variable en el primal es cero.

4. Si una variable real del primal es positiva, la restricción correspondiente en el dual es exactamente satisfecha (Variable Holgura-exceso del dual = 0)

INTERPRETACIÓN

• 1. Si un recurso no es usado completamente en la solución óptima primal, el valor de ese recurso tiene que ser cero (0), es decir, se puede vender a valores mayores que cero (Vr > 0), si es posible, pero no a comprar unidades de ese recurso.

• 2. Si se usan todos los recursos (Variable holgura primal = 0), se puede valorar un recurso a un precio marginal positivo (Yi > 0)

Formulación del Modelo de Transporte.

La programación lineal es un campo tan amplio que se extiende a subclases de problemas para los cuales existen métodos de solución especiales. Una de estas subclases se conoce como problemas de transporte. El método símplex de programación lineal, puede servir para resolver estos problemas. Pero se han desarrollado métodos más sencillos que aprovechan ciertas características de los problemas. Entonces, el método del transporte son sólo técnicas especiales para resolver ciertos tipos de problemas de programación lineal.

El transporte desempeña un papel importante en la economía y en las decisiones administrativas. Con frecuencia la disponibilidad de transporte económico es crítica para la sobre-vivencia de una empresa.

¿Qué significa problema de transporte? Supóngase que un fabricante tiene tres plantas que producen el mismo producto. Estas plantas a su vez mandan el producto a cuatro almacenes. Cada planta puede mandar productos a todos los almacenes, pero el costo de transporte varía con las diferentes combinaciones. El problema es determinar la cantidad que cada planta debe mandar a cada almacén con el fin de minimizar el costo total de transporte.

La manera más fácil de reconocer un problema de transporte es por su naturaleza o estructura"de-hacia": de un origen hacia un destino, de una fuente hacia un usuario, del presente hacia el futuro, de aquí hacia allá. Al enfrentar este tipo de problemas, la intuición dice que debe haber una manera de obtener una solución. Se conocen las fuentes y los destinos, las capacidades y demandas y los costos de cada trayectoria. Debe haber una combinación óptima que minimice el costo (o maximice la ganancia). La dificultad estriba en el gran número de combinaciones posibles.

Puede formularse un problema de transporte como un problema de programación lineal y aplicarse el método símplex. Si se hiciera, se encontraría que los problemas de transporte tienen características matemáticas únicas. Para visualizar esto, considérese el siguiente ejemplo:

Ejemplo prototipo.

Chícharos enlatados es uno de los productos más importantes de la compañía P & T. Los chícharos se preparan en tres enlatadoras (cercanas a Bellingham, Washington; a Eugene, Oregón y a Albert Lea, Minnesota) y después se mandan por camión a cuatro almacenes de distribución (en Sacramento, California; Salt Lake City, Utah; Rapid City, South Dakota y Alburquerque, New Mexico) en el oeste de Estados Unidos. Puesto que los costos de embarque constituyen un gasto importante, la gerencia ha iniciado un estudio para reducirlos lo más posible que se pueda. Se ha hecho una estimación de la producción de cada enlatadora para la próxima temporada y se ha asignado a cada almacén una cierta cantidad de la producción total de chícharos. En la siguiente tabla se proporciona esta información (en unidades de carga de camión), junto con el costo de transporte por camión cargado para cada combinación de enlatadora-almacén. Como se ve hay un total de 300 cargas de camión que se deben transportar. El problema es determinar el plan de asignación de estos embarques a las distintas combinaciones de enlatadora-almacén que minimice el costo total de transporte.

Costo de embarque ($) por carga

Este, de hecho, es un problema de programación lineal del tipo de los problemas de transporte. Para formularlo, sea Z el costo total de transporte y sea xij (i = 1, 2, 3; j = 1, 2, 3, 4) el número de cargas de camión que se mandan de la enlatadora i al almacén j. Entonces el objetivo es seleccionar los valores de estas 12 variables de decisión (las xij) para:

La siguiente tabla muestra los coeficientes de las restricciones. Como se verá enseguida, lo que distingue a este problema como un problema de transporte es la estructura especial en el patrón de estos coeficientes, no su contexto.

Modelo general del problema de transporte.

Para describir el modelo general del problema de transporte es necesario emplear términos que sean mucho menos específicos que los que se usaron para los componentes del ejemplo prototipo. En particular, el problema general de transporte se refiere (literal o en sentido figurado) a la distribución de cualquier bien desde cualquier grupo de centros de abastecimiento, llamados orígenes, a cualquier grupo de centros de recepción, llamados destinos, de tal manera que se minimicen los costos totales de distribución. La correspondencia en terminología entre el ejemplo prototipo y el problema general se resume en la siguiente tabla:

Así, por lo general, el origen i (i = 1, 2, …, m) dispone de si unidades para distribuir a los destinos y el destino j (j = 1, 2, …, n) tiene una demanda de dj unidades que recibe desde los orígenes. Una suposición básica es que el costo de distribución de unidades desde el origen i al destino j es directamente proporcional al número distribuido, donde cij denota el costo por unidad distribuida. Igual que para el ejemplo prototipo, estos datos de entrada se pueden resumir en forma muy conveniente en la tabla de costos y requerimientos que se muestra enseguida:

Note que la tabla que resulta de los coeficientes de las restricciones tiene la estructura especial que se muestra en la siguiente tabla:

Cualquier problema de programación lineal que se ajuste a esta formulación especial es del tipo de problemas de transporte, sin importar su contexto físico. De hecho, se han realizado numerosas aplicaciones no relacionadas con el transporte que se ajustan a esta estructura especial. Ésta es una de las razones por las que el problema de transporte se suele considerar como uno de los tipos especiales de problemas de programación lineal más importantes.

Una condición necesaria y suficiente para que un problema de transporte tenga soluciones factibles es que:

Esta condición de que los recursos totales deben ser iguales a la demanda total en realidad exige que el sistema esté balanceado. Si el problema tiene algún significado físico y esta condición no se cumple, casi siempre significa que, o bien si, o bien dj de hecho representan una cota y no un requerimiento exacto. Si este es el caso, se puede introducir un "origen" o "destino" imaginario (llamado origen ficticio o destino ficticio) para captar la holgura, con el fin de convertir las desigualdades en igualdades y satisfacer la condición de factibilidad.

El problema de transporte es sólo un tipo especial de problemas de programación lineal y puede resolverse aplicando el método símplex tal y como lo hemos estudiado. Sin embargo, veremos que si se aprovecha la estructura especial que se muestra en la tabla anterior, se puede lograr un importante ahorro en los cálculos. Se hará referencia a este procedimiento simplificado como el método símplex de transporte.

Para hacer hincapié en la simplificación lograda por el método símplex de transporte, se revisará primero la forma en que el método símplex general (no simplificado) establecería el problema de transporte en forma tabular.

En esta tabla, todos los elementos que no se muestran en estas columnas son ceros. El único ajuste que queda por hacer antes de la primera iteración es eliminar algebraicamente los coeficientes distintos de cero de las variables básicas iniciales (artificiales) en el renglón de Z (renglón 0).

Después de cualquier iteración subsecuente, el renglón 0 tendría la forma que se muestra en la siguiente tabla:

A causa del patrón de ceros y unos que siguen los coeficientes en la tabla anterior, ui y vj tienen la siguiente interpretación:

ui = múltiplo del renglón i original que se ha restado (directa o indirectamente) del renglón 0 original durante todas las iteraciones del método símplex que llevaron a la tabla actual.

vj = múltiplo del renglón m+j original que se ha restado (directa o indirectamente) del renglón 0 original durante todas las iteraciones del método símplex que llevaron a la tabla actual.

El renglón 0 actual se puede obtener sin usar ningún otro renglón con sólo calcular los valores de ui y vj directamente. Como cada variable básica debe tener coeficiente cero en el renglón 0, estos valores se pueden obtener resolviendo el sistema de ecuaciones:

cij(ui(vj = 0 para cada i y j tal que xij es variable básica, lo cual se puede hacer de manera directa.

Además de los datos de entrada (los valores de cij, si y dj), la única información que necesita el método símplex de transporte es la solución básica factible actual, los valores actuales de ui y vj y los valores resultantes de cij(ui(vj para las variables no básicas xij. Cuando se resuelve un problema a mano es conveniente registrar esta información en una tabla símplex de transporte, como la que se muestra enseguida:

En los casos en que la sumatoria de todo lo que se produce en todos los orígenes es mayor que la sumatoria de todo lo que se demanda en todos los destino o viceversa, entonces se dice que el problema no está balanceado. En estos casos lo primero que se debe hacer antes de intentar resolver el problema es balancearlo.

Para el caso de SOBREPRODUCCIÓN

Si el caso es que se dispone de mayor producción de la que se demanda, entonces para balancear el problema se agrega un destino imaginario o artificial (llamado también destino ficticio) el cual tendrá como demanda dicha sobreproducción. En cuanto a los costos asociados a este nuevo destino los estableceremos a cero (¿por qué?). El siguiente dibujo muestra lo que se debe hacer:

Para el caso de SOBREDEMANDA

Si el caso es que se tiene mayor demanda de lo que se produce, entonces para balancear el problema se agrega un origen imaginario o artificial (llamado también origen ficticio) el cual tendrá como recursos (producirá) dicha sobredemanda. En cuanto a los costos asociados a este nuevo origen los estableceremos a cero (¿por qué?). El siguiente dibujo muestra lo que se debe hacer:

Como todas las restricciones funcionales en el problema de transporte son igualdades, el método símplex obtendría una solución inicial básica factible introduciendo variables artificiales y usándolas como variables básicas iniciales. La solución básica que resulta de hecho sólo es factible para la versión aumentada del problema, por lo que se necesita un buen número de iteraciones para hacer que el valor de estas variables artificiales sea cero y se alcancen las soluciones básicas factibles reales. El método símplex de transporte pasa por alto todo esto, pues usa un procedimiento más sencillo para construir directamente una solución básica factible real en la tabla de transporte.