SECRETARIA DE EDUCACIÓN PÚBLICA

SUBSECRETARÍA DE EDUCACIÓN SUPERIOR

TECNOLÓGICO NACIONAL DE MEXICO

INSTITUTO TECNOLOGICO DE BOCA DEL RIO

Modelos de Optimización de Recursos

Unidad #3

TEMA DE INVESTIGACIÓN: 
Algoritmos especiales de programación lineal

Equipo 3

SUBTEMAS:  
3.1 El problema del transporte: planteamiento del problema, determinación de
la solución básica factible inicial, el criterio de optimabilidad y el algoritmo de
mejoramiento de la solución (Ruta de los signos).
3.2 El problema de asignación: planteamiento del problema, algoritmo para
determinar la asignación óptima.
3.3 El uso del Software.

EQUIPO 3
*Contreras Del Valle Isidro René
Castro Luna Manuel Isaac 
Hernández Yescas Fátima 
Valero Figueroa Omar
 Sánchez Bautista Joana Lizzeth 

DOCENTE: Ing. Juan Manuel Riquer Trujillo

integrantes A(10%)EXPOCISIO B(20%)INVSTIGACIO C(20%)POWEROINT ABC(50%)
N N

*Contreras
Del Valle
Isidro René
Castro Luna
Manuel Isaac
Hernández
Yescas
Fátima
Valero
Figueroa
Omar
Sánchez
Bautista
Joana Lizzeth

1
 ÍNDICE
FRASE CELEBRE.................................................................................................................. 3

INTRODUCCIÓN.................................................................................................................... 4

3. ALGORITMOS ESPECIALES DE PROGRAMACIÓN LINEAL.........................................6

ALGORITMOS ESPECIALES............................................................................................6

3.1 EL PROBLEMA DEL TRANSPORTE..............................................................................6

3.1.1 UN EJEMPLO DEL PROBLEMA DEL TRANSPORTE............................................................7

3.1.2 LA FORMULACIÓN CON PROGRAMACIÓN LINEAL............................................................8

3.2 EL PROBLEMA DE ASIGNACIÓN: PLANTEAMIENTO DEL PROBLEMA,

ALGORITMO PARA DETERMINAR LA SOLUCIÓN ÓPTIMA.................................................12

3.2.1 EL PROBLEMA DE ASIGNACION.........................................................................12

3.2.2 DEFINICIÓN DEL PROBLEMA DE ASIGNACIÓN.................................................13
3.2.3 ALGORITMOS Y GENERALIZACIONES............................................................................15
3.2.4 EL ALGORITMO HÚNGARO SE DEBE A D. KÖNIG Y E. E EGERVÓRY.............................16
3.2.5 EL MÉTODO HÚNGARO:.............................................................................................. 16

3.3 EL USO DE SOFTWARE................................................................................................ 17

3.3.1 SOFTWARE WINQSB................................................................................................... 17

3.3.2 SOFTWARE INVOP.................................................................................................... 18

CONCLUSIONES................................................................................................................. 20

CUESTIONARIO................................................................................................................... 22

BIBLIOGRAFIA.................................................................................................................... 26

2
 FRASE CELEBRE

“Una de las razones por las que las personas se resisten al cambio es porque se
concentran en lo que tienen que renunciar, en lugar de en lo que tienen para ganar”
Rick Godwin

Richard Goodwin fue un matemático y economista norteamericano nacido en

Indiana. Se denominó a sí mismo como un «marxista descarriado de toda la vida»
(1983). Se dedicó al estudio de la dinámica de las economías capitalistas. Su trabajo se
basó en la premisa de que el capitalismo solo puede ser correctamente entendido si se lo
consideraba como un sistema no lineal, más específicamente, como un sistema
autoorganizado (de carácter caótico) en donde la interacción de múltiples agentes hace
que, a diferencia de los planteamientos ortodoxos, no haya garantía de que los mercados
se vacíen, además que la tasa media de desempleo durante el ciclo económico puede ser
alta o baja.1

1
http://www.asociacioneconomiacritica.org/clasicos-u-olvidados/name/richard-goodwin/
#:~:text=Biogr%C3%A1fica,din%C3%A1mica%20de%20las%20econom%C3%ADas
%20capitalistas.

3
 INTRODUCCIÓN

Sabemos que para que un ordenador pueda llevar adelante una tarea cualquiera, se
tiene que contar con un algoritmo que le indique, a través de un programa, que es lo que
debe hacer con la mayor precisión posible. Consecuencia de lo anterior es la
importancia del estudio de los algoritmos.
Concepto de Algoritmo
Un algoritmo es un conjunto ordenado y finito de pasos o instrucciones que permite
realizar una actividad mediante pasos sucesivos sin generar dudas a quien deba realizar
dicha actividad, conduciendo a la solución de un problema determinado. De esta
manera, dados un estado inicial y una entrada, siguiendo los pasos sucesivos se llega a
un estado final y se obtiene una solución. En la vida cotidiana, frecuentemente se
emplean algoritmos para resolver problemas.
Algoritmos especiales
Son diseñados para problemas de programación lineal, son problemas enunciados
con ecuaciones lineales y con una función objetivo, y una o más funciones
restricciones, para lograr la optimización de la función objetivo que se analiza. Algunos
de ellos son: Gran M, Flujo mínimo, Algoritmo Fraccional, Método Dual Simplex,
entre otros.
Aplicación
Son empleados principalmente en problemas de flujo de redes y problemas de flujo
de mercancías. Son muy usados en la microeconomía y la administración de empresas,
ya sea para aumentar al máximo los ingresos o reducir al mínimo los costos de un
sistema de producción.
El término “Problema del Transporte” está ligado a la literatura de Investigación de
Operaciones como una aplicación exitosa para resolver el problema de distribuir carga
de la manera más económica desde los orígenes donde ésta se encuentra hasta los
destinos donde es requerida, dados los costos de transporte desde cada origen hasta cada
destino.

Aunque este problema es uno de los modelos comúnmente discutidos en las

aplicaciones de la Investigación de Operaciones, probablemente el trabajo más antiguo

4
conocido de este modelo se debe a G. Monge, matemático francés del siglo XVIII
(Schrjiver, 1986). De acuerdo a Appell (1928), Monge publicó en 1781 Le Problème
Géométrique des Déblais et Remblais (El Problema Geométrico del Movimiento y
Relleno de Tierras) en las memorias de la Academia Francesa de Ciencias. Aunque
Monge estaba interesado básicamente en geometría, propone el problema de minimizar
el costo total de mover tierra desde varios orígenes para rellenar en varios destinos
como sigue:2

“Dados dos volúmenes equivalentes, descomponerlos en partículas infinitamente

pequeñas, correspondiéndose uno-a-uno, de modo tal que la suma de los productos de
los recorridos hechos para llevar cada partícula sobre su contraparte, por el volumen de
la parte movida, sea un mínimo”.(citado en Appell 1928, p.1). 3
Como lo describe Taton (1951), el interés de Monge en problemas de movimiento de
tierras tuvo que ver con su disposición a resolver problemas de ingeniería militar
relativos a la construcción de fuertes. Su percepción de los costos implicados en la tarea,
es una cruda aproximación al costeo por tonelada-kilómetro que se usa en nuestros días:
“El precio del transporte de una molécula dada, manteniendo todo lo demás igual, es
proporcional a su peso y a la distancia que recorre, de modo que el precio total del
transporte es la suma de los productos de la moléculas multiplicadas cada una por la
distancia recorrida  .” (citado por Taton 1951, p. 194). 4

2
Appell, P. “Le probléme géométrique des déblais et ramblais”. (in French). Gauthier-
Villars. Paris. [online]. Available at:URL:http://gallica.bnf.fr. [Accessed January 2003]. 1928.
3
Ibid
4
Arnoff, E.L. and Sengupta, S.S. Mathematical programming. In: “Progress in Operations
Research”. Vol. I. Edited by Russell L. Ackoff. John Wiley & Sons. USA. 1961.

5
 3. ALGORITMOS ESPECIALES DE PROGRAMACIÓN
LINEAL

ALGORITMOS ESPECIALES
Un algoritmo es un conjunto ordenado y finito de pasos o instrucciones que permite
realizar una actividad mediante pasos sucesivos sin generar duda a quien deba realizar
dicha actividad.
Algoritmos Especiales.- Son diseñados para problemas de programación lineal, son
problemas enunciados con ecuaciones lineales, con una función objetivo y una o mas
funciones restricciones para lograr la optimización de la función objetivo que se analiza.
Son muy usados en la microeconomía y la administración de empresas, ya sea para
aumentar al máximo los ingresos o reducir al mínimo los costos de un sistema de
producción.5

3.1 EL PROBLEMA DEL TRANSPORTE

Si bien Monge usa un lenguaje geométrico discutiendo puntos, líneas y partículas
infinitamente pequeñas, el problema que plantea corresponde al Problema del
Transporte, en el cual hay N orígenes con cantidades conocidas de un cierto producto
disponible, M destinos con demandas conocidas del producto y todos los costos de
transporte para cada par origen-destino son conocidos.
La Figura 1 ilustra el problema con dos orígenes y tres destinos, con el objetivo de
encontrar el plan de costo mínimo para distribuir los productos en los orígenes y
satisfacer las demandas en los destinos.6

5
https://prezi.com/p/j0sstsb0wwcu/algoritmos-especiales-de-programacion-lineal/
#:~:text=Algoritmos%20Especiales.,funci%C3%B3n%20objetivo%20que%20se%20analiza.
6
Arnoff, E.L. and Sengupta, S.S. Mathematical programming. In: “Progress in Operations
Research”. Vol. I. Edited by Russell L. Ackoff. John Wiley & Sons. USA. 1961.

6
 3.1.1 Un ejemplo del problema del transporte
El problema del transporte resurgió en la década de 1940 dentro de la corriente de
trabajos planteados con el nacimiento de la Investigación de Operaciones como una
disciplina autónoma. El problema fue considerado en 1941 por Hitchcock e
independientemente por Kantorovich en 1942 y por Koopmans en 1947. El modelo de
Hitchcock plantea encontrar el mínimo costo de distribuir un producto desde varias
fábricas a un número dado de ciudades, y desde entonces el modelo es conocido
también como el Problema de Transporte de Hitchcock. En 1951, G. Dantzig desarrolló
la primera solución al problema, utilizando programación lineal (Arnoff & Segupta,
1961).7

A pesar de su simplicidad, el problema del transporte contiene ya algunos de los

elementos básicos que se han utilizado en subsiguientes esfuerzos de modelación del
transporte de carga:
a)     Una función objetivo, esto es, el costo total del plan de transporte, que refleja el
objetivo del decisor, así como un criterio mensurable para la transportación involucrada,
es decir, la tonelada-kilómetro (considerando la distancia como costo).
b)     Las restricciones del problema, esto es, las distintas ofertas de productos en los
orígenes y las respectivas demandas en los destinos, y
c)      Los parámetros del problema, es decir, los costos para los distintos enlaces
origen-destino que representan las características de la red carretera.

Cabe notar, sin embargo, que el problema del transporte no puede hacer explícita la
topología de la red carretera, ni puede considerar diferencias en los costos percibidos
por los transportistas ni diferencias en las capacidades de los vehículos que mueven las
cargas. Esto ha dado lugar a otros desarrollos en la modelación del transporte de carga,
que buscan hacer modelos más realistas cada vez, como es el caso del modelo
gravitacional para distribución de viajes (Ortúzar & Willumsen, 1994, pp. 394-395).8

Arnoff, E.L. and Sengupta, S.S. Mathematical programming. In: “Progress in Operations
7

Research”. Vol. I. Edited by Russell L. Ackoff. John Wiley & Sons. USA. 1961.
8
Bazaraa, M.S., Jarvis, J.J. and Sherali, H.D. “Linear programming and network
flows”. John Wiley & Sons. Singapore. 1990.

7
 3.1.2 La formulación con Programación Lineal
El problema del transporte puede verse como la simplificación del objetivo de
minimizar los costos del transportista que mueve carga desde los orígenes a los destinos
para satisfacer la demanda. El planteamiento del problema de transporte como un
programa lineal, junto con la interpretación dual de éste permite visualizar un segundo
punto de vista del problema, donde el interesado es el embarcador que intenta satisfacer
la demanda en los destinos, tratando de maximizar el beneficio que le representa la
operación.9

El planteamiento es como sigue: llamando Xij al flujo de productos del origen  i  al

destino  j  , cij al costo unitario por tonelada movida, Si a la oferta de producto en el
nodo i  , Dj  a la demanda de productos en el nodo j, y Z al costo total del plan de
transporte, entonces para el caso con dos orígenes y tres destinos, el programa lineal es:

…
[1]
Éste es el problema del transportista que busca satisfacer la demanda en los destinos
a un costo total mínimo. Las restricciones del programa representan la conservación del
flujo en los nodos, impidiendo al transportista planear movimientos de carga mayores a
la disponibilidad en los orígenes y obligándolo a entregar en los destinos al menos la
demanda solicitada. Para fines de presentación, el problema es puesto en la forma
canónica de un programa lineal para minimización (con restricciones ³):

Cournot, A. “Researches into the mathematical principles of the theory of

9

wealth”. Translated by Nathaniel T. Bacon. The Macmillan Co. New York, 1927. 1838.

8
 …
[2]

Así, escribiendo el dual del problema anterior resulta:

…[3]
Una interpretación económica del problema dual aclara el “segundo punto de vista”
implícito en el problema del transporte original, que corresponde al interés del
embarcador.  Llamando U1 y U2 a los precios del producto a los que el embarcador
compra en los orígenes 1 y 2, y V1, V2, V3 al precio del producto que los consumidores
pagan en los destinos 1, 2 y 3 respectivamente, resulta que el objetivo del programa dual
es el del embarcador que compra el producto en los orígenes y lo vende en los destinos,
tratando de maximizar la utilidad de la operación expresada en la función objetivo dual:
(ingreso) - (costo de compra). Las variables duales U i y Vj son llamadas usualmente
“precios sombra”.

9
 Conforme a la interpretación económica para el problema dual propuesta por Bazaraa
et al (Bazaraa et al, 1990, p.254-256), si Z * e la solución óptima del programa primal [2]
y la demanda es ligeramente alterada en los nodos, de modo que la solución óptima no
cambie, entonces las variables duales (precios sombra) satisfacen:

                   …[4]

Estas ecuaciones [4] muestran que los precios sombra Ui* and Vj* cambian con la tasa
de cambio del costo óptimo de transporte Z* con respecto a la oferta en los orígenes o a
la demanda en los destinos. Así, por ejemplo, al aumentar una unidad la demanda D 1 en
el destino 1, aumenta el costo óptimo Z * por V1*, y éste sería el precio justo (precio
sombra) que los consumidores en el destino 1 tendrían que pagar para obtener ésa
demanda adicional.

Respecto de las restricciones, para un par de origen  i  y destino  j, la restricción dual:

que se reescribe como:

  …[5]
indica que el precio Vj en el destino  j  no puede exceder la suma del precio en el
origen  i  (Ui ) más el costo del transporte involucrado c ij. A esta condición se refiere
Harker (1987) como el Equilibrio de Cournot en su discusión sobre los modelos de
equilibrio espacial de precios.10

10
Harker, P.T. Issues and models for planning and regulating freight transport systems. In:
“Lecture Notes in Economics and Mathematical Systems”. Lucio Bianco and Agostino La
Bella, editors. International Seminar on Freight Transport Planning and Logistics, Italy. Springer-
Verlag.pp. 374-408. 1987.

10
 En las propias palabras de Cournot:
   “Es evidente que un artículo capaz de ser transportado debe fluir del mercado
donde su valor es menor al mercado donde su valor es más grande, hasta que la
diferencia en valor, de un mercado al otro, no represente más que el costo del
transporte.” (Cournot, 1838, p. 117). 11

Adicionalmente, resulta de interés que la teoría de dualidad garantiza que en la

solución óptima, tanto el objetivo del problema primal como el del dual tienen el mismo
valor, con lo que tanto el transportista como el embarcador pueden lograr
simultáneamente sus óptimos.

3.2 EL PROBLEMA DE ASIGNACIÓN:

PLANTEAMIENTO DEL PROBLEMA, ALGORITMO
PARA DETERMINAR LA SOLUCIÓN ÓPTIMA

11
Cournot, A. “Researches into the mathematical principles of the theory of
wealth”. Translated by Nathaniel T. Bacon. The Macmillan Co. New York, 1927. 1838.

11
 3.2.1 EL PROBLEMA DE ASIGNACION
El problema de la asignación es uno de los problemas fundamentales de
optimización combinatoria de la rama de optimización o investigación operativa en
matemática.

Una descripción apropiada de lo que trata de lograr el modelo de asignación es:

"La mejor persona para el trabajo"

El problema de asignación tiene que ver con la designación de tareas a

empleados, de territorios a vendedores, de contratos a postores o de trabajos a
plantas, etc. En otras palabras, a la disposición de algunos recursos (máquinas o
personas) para la realización de ciertos productos a costo mínimo.12

Una definición más formal pudiera ser:

Problema de Asignación: Caso particular del problema de Transporte donde los

asignados son recursos destinados a la realización de tareas, los asignados pueden ser
personas, máquinas, vehículos, plantas o períodos de tiempo. En estos problemas la
oferta en cada origen es de valor 1 y la demanda en cada destino es también de valor.

HISTORIA

El problema de asignación tuvo su origen en la revolución industrial, ya que el

surgimiento de las máquinas hizo que fuera necesario asignar una tarea a un
trabajador.

Thomas Jefferson en 1792 lo sugirió para asignar un representante a cada estado,

pero formalmente aparece este problema en 1941, cuando F.L. Hitchcook publica una
solución analítica del problema, pero no es hasta 1955 cuando Harold W. Kuhn plantea
el Método húngaro, que fue posteriormente revisado por James Munkres en 1957;
dicho método está basa.13
12
Schrijver, A. “Theory of Linear and Integer Programming”. John Wiley & Sons.
Chichester. pp 376-377. 1986.

13
Schrijver, A. “Theory of Linear and Integer Programming”. John Wiley & Sons.
Chichester. pp 376-377. 1986.

12
fundamentalmente en los primeros trabajos de otros dos matemáticos húngaros: Dénes
Köning y Jenö Egervary.

Hoy en día en pleno apogeo de la globalización este problema surge cada vez con
mayor frecuencia el uso de este problema de la rama de la investigación de
operaciones, podemos decir que es la aplicación del método científico para asignar los
recursos o actividades de forma eficaz, en la gestión y organización de sistemas
complejos, su objetivo es ayudar a la toma de decisiones.

3.2.2 DEFINICIÓN DEL PROBLEMA DE ASIGNACIÓN

En su forma más general, el problema es como sigue:

Hay un número de agentes y un número de tareas. Cualquier agente puede ser

asignado para desarrollar cualquier tarea, contrayendo algún coste que puede variar
dependiendo del agente y la tarea asignados. Es necesario para desarrollar todas las
tareas asignar un solo agente a cada tarea para que el coste total de la asignación sea
minimizado.14

Este tipo de problemas son lineales, con una estructura de transporte, sólo que la
oferta en cada origen es de valor uno y la demanda en cada destino es también de valor
uno. Sería muy ineficiente resolver este tipo de problemas por medio del método
simplex o por medio del de transporte. Debido a la estructura propia de los problemas
de asignación, existen métodos de solución llamados algoritmos de asignación que son
más eficientes que el simplex o que el método de transporte.

Los problemas de asignación presentan una estructura similar a los de transporte,

pero con dos diferencias: asocian igual número de orígenes con igual número de
demandas y las ofertas en cada origen es de valor uno, como lo es la demanda en cada
destino.15

14
Taton, R. “L’oeuvre scientifique de Monge”.  Presses Universitaires de France. Paris. pp.
193-196. 1951.

13
 La restricción importante para cada agente es que será asignado a una y solo una tarea.

CARACTERÍSTICAS

El problema de asignación presenta las siguientes características:

El Problema de Asignación debe estar equilibrado, es decir, que las ofertas y las
demandas sean igual a 1. Un elemento importante para el problema de asignación es la
matriz de costos, si el número de renglones o columnas no son iguales el problema está
desbalanceado y se puede obtener una solución incorrecta, para obtener una solución
correcta la matriz debe ser cuadrada.

Si el número de agentes y tareas son iguales y el coste total de la asignación para

todas las tareas es igual a la suma de los costes de cada agente (o la suma de los costes
de cada tarea, que es lo mismo en este caso), entonces el problema es llamado problema
de asignación lineal.16

Normalmente, cuando hablamos de problema de asignación sin ninguna matización

adicional, nos referimos al problema de asignación lineal.

Oferta: Cantidad que representa la disponibilidad del artículo en la fuente/fábrica de

donde proviene.

Demanda: Cantidad de artículos que necesita recibir el destino para cumplir sus
necesidades.

15
Taton, R. “L’oeuvre scientifique de Monge”.  Presses Universitaires de France. Paris. pp.
193-196. 1951.

16
El Problema De Asignacion. (2014, noviembre 9). Clubensayos.com.

https://www.clubensayos.com/Temas-Variados/El-Problema-De-Asignacion/2179152.html

14
 3.2.3 Algoritmos y generalizaciones
El algoritmo Húngaro es uno de los muchos algoritmos que han sido diseñados para
resolver el problema de la asignación lineal con un tiempo acotado por una expresión
polinómica del número de agentes.

El problema de asignación es un caso especial del problema del transportador, que es

un caso especial del problema del flujo de coste mínimo. El problema de asignación
también puede ser resuelto por medio del algoritmo simplex (creado en 1947 por el
matemático George Dantzig). El método simplex se utiliza, sobre todo, para resolver
problemas de programación lineal en los que intervienen tres o más variables. Es un
método iterativo que permite ir mejorando la solución en cada paso. Cada
especialización tiene algoritmos más eficientes tomando ventaja de su estructura
espacial.17

El algoritmo Húngaro está destinado para minimizar si tenemos que maximizar

tendremos previamente que darle la vuelta a la matriz restándole el mayor elemento
de toda la matriz a cada uno de los elementos de esta de manera que el elemento que era
más pequeño pasara a ser el más grande y a la inversa.

17
Wikipedia contributors. (s/f). Problema de asignación. Wikipedia, The Free Encyclopedia.

https://es.wikipedia.org/w/index.php?title=Problema_de_asignaci

%C3%B3n&oldid=148233641

15
 3.2.4 El Algoritmo Húngaro se debe a D. König y E. E Egervóry.
Cuando hay que pasar de maximizar a minimizar en lugar de operar con el mayor de
toda la matriz podemos ir tomando el mayor de cada fila o columna e ir restándole todos
los elementos de esa fila o columna con lo cual conseguiremos de camino obtener por lo
menos un cero como mínimo en cada fila o columna. Si en alguna columna no hubiera
ceros le quitamos el mayor a la columna.18
3.2.5 El método Húngaro:
Este algoritmo se usa para resolver problemas de minimización, ya que es más eficaz
que el empleado para resolver el problema del transporte por el alto grado de
degeneración que pueden presentar los problemas de asignación. Las fases para la
aplicación del método Húngaro son:
Paso 1: Encontrar primero el elemento más pequeño en cada fila de la matriz de
costos m*m; se debe construir una nueva matriz al restar de cada costo el costo mínimo
de cada fila; encontrar para esta nueva matriz, el costo mínimo en cada columna. A
continuación, se debe construir una nueva matriz (denominada matriz de costos
reducidos) al restar de cada costo el costo mínimo de su columna.
Paso 2: (En algunos pocos textos este paso se atribuye a Flood). Consiste en trazar el
número mínimo de líneas (horizontales o verticales o ambas únicamente de esas
maneras) que se requieren para cubrir todos los ceros en la matriz de costos reducidos;
si se necesitan m líneas para cubrir todos los ceros, se tiene una solución óptima entre
los ceros cubiertos de la matriz. Si se requieren menos de m líneas para cubrir todos los
ceros, se debe continuar con el paso 3. El número de líneas para cubrir los ceros es igual
a la cantidad de asignaciones que hasta ese momento se pueden realizar.
Paso 3: Encontrar el menor elemento diferente de cero (llamado k) en la matriz de
costos reducidos, que no está cubierto por las líneas dibujadas en el paso
2; a continuación, se debe restar k de cada elemento no cubierto de la matriz de costos
reducidos y sumar k a cada elemento de la matriz de costos reducidos cubierto por dos
líneas (intersecciones). Por último, se debe regresar al paso 2.

18
Yunior, A. C. S. (2015, mayo 11). Problema de asignación en la investigación de
operaciones. Monografias.com. https://www.monografias.com/trabajos104/problema-
asignacion-investigacion-operaciones/problema-asignacion-investigacion-operaciones

16
 3.3 EL USO DE SOFTWARE

3.3.1 Software winQsb

El WinQsb maneja el problema del transporte en su módulo de Modelos de Redes, el
cual en su inicio nos muestra la siguiente ventana, que se debe diligenciar así:

Fíjese que este módulo también resuelve otros modelos de redes, que se especifican en
la parte izquierda de la ventana.

Los datos se pueden ingresar de dos formas: En una matriz o tablero de doble entrada o
de forma gráfica.

A continuación, se ilustra el ingreso de datos en la tabla de doble entrada.

El modo de edición del menú principal permite cambiar los rótulos de las fuentes y los
destinos. No es necesario que la oferta sea igual a la demanda, el software se encarga de
agregar fuentes ó destinos de holgura, según sea la necesidad.

Para solucionar el problema se da click en el icono que aparece en la parte superior.

El winqsb le ofrecerá entonces una ventana con la respuesta optima del problema,
indicando cuantas unidades enviar desde cada una de las ciudades de destino, con su
costo por envió y el costo total por operación.

17
 Observe que en este problema la oferta de los Centros
de distribución es igual a los requerimientos de los
detallistas, por lo tanto, no hubo necesidad de
adicionar ni fuentes, ni destinos ficticios y se trata de
un problema de mercado perfecto.

3.3.2 Software INVOP

Este software maneja las siguientes aplicaciones: asignaciones, transporte, distancia en

redes (ruta más corta, árbol de mínimo recorrido, agente viajero), flujo de redes.

El invop está en Español y su metodología dirigida a la enseñanza, ofreciendo al usuario

tanto la parte teórica de fundamento matemático como la parte práctica de solución de
problemas con sus respectivos ejemplos.

18
Al escoger la opción de transporte, el lNVOP nos ofrece una ventana en donde captura
los datos del problema y en un recuadro situado en la parte inferior derecha, donde nos
ofrece la solución óptima. Colocando el cursor sobre algunos sitios de interés de esta
ventana, se ofrece un rótulo en fondo amarillo con la respectiva instrucción de ayuda.

En la parte inferior izquierda de la ventana se especifica el criterio de optimización y la

cantidad de fuentes y destinos, en la parte superior derecha se introducen los costos por
unidad a transportar y habilitando el cuadro de control, se editan los encabezados de fila
y columna, al igual que las ofertas y las demandas de fuentes y destinos.

Cuando la información del problema está introducida, se procede a solucionar el

problema, haciendo clic sobre el icono del menú superior, que tiene la figura de una
calculadora,

Se recomienda al Usuario del Software leer la ayuda (Help), en la que se explica toda la
parte conceptual y matemática del algoritmo del transporte al igual que se ilustran
varios ejemplos de muy buena calidad.19

19
Yunior, A. C. S. (2015, mayo 11). Problema de asignación en la investigación de
operaciones. Monografias.com. https://www.monografias.com/trabajos104/problema-
asignacion-investigacion-operaciones/problema-asignacion-investigacion-operaciones

https://es.slideshare.net/kakel17/unidad-3-algoritmos-especiales-de-programacion-lineal

19
 CONCLUSIONES

Dentro del enfoque de planeación del transporte usado en la actualidad, el

planteamiento del problema del transporte (representado al transportista) y su problema
dual asociado (representando al embarcador) permite apreciar una condición
comúnmente encontrada en el modelado del transporte de carga: la existencia de
múltiples actores que intervienen en la generación de los flujos de carga, y que
usualmente tienen objetivos distintos, y en ocasiones hasta opuestos. En el caso del
problema del transporte, la solución óptima afortunadamente satisface tanto al
transportista como al embarcador, pero ésta es una situación que generalmente no
ocurre en el transporte de carga. Cuando los distintos actores en el transporte de carga
tienen objetivos que se oponen, la tarea de modelado exige buscar enfoques adecuados
para representar la solución de conflictos.

Así pues, la modelación del transporte de carga conlleva la dificultad de buscar

técnicas matemáticas para representar adecuadamente a los múltiples actores que
determinan los flujos de carga, y sus distintos objetivos, cuando todos estos actores
tratan de optimizar sus propios criterios de desempeño simultáneamente aún cuando
estos objetivos se contrapongan. Entre los enfoques reportados en la literatura, técnicas
como la Teoría de Juegos, la programación por objetivos o la programación bi-nivel han
mostrado ser perspectivas promisorias para la modelación del comportamiento del
transporte de carga (Moreno, 2004), aportando de este modo nuevas herramientas
analíticas para el planificador del transporte.

Como hemos visto a lo largo del documento existen problemas que no pueden ser
solucionados con la programación lineal debido a que posee elementos no
ineales.

Primero empezamos viendo los conceptos básicos de la programación no

lineal, Sus restricciones, La representación matemática la función objetivo,
Además vimos como maximizar la función, También la representación de los intervalos

20
y que significa la simbología de los intervalos, Por lo tanto, esto nos ayudó a
comprender los siguientes temas.
Después se le dio énfasis al tema de los métodos de programación no lineal que
resuelven problemas más complejos que la programación lineal, También los distintos
elementos que tienen estos métodos de la programación no lineal. Posteriormente vimos
la ilustración grafica la cual nos explica problemas de dos o tres variables máximo, ya
que no hay manera de representar gráficos a más de tres dimensiones. Y que aparte la
ilustración grafica nos ayudaba a comprender más fácilmente la solución de un
problema de programación no lineal y como la gente que no sabe mucho de
investigación de operaciones, Puede darse cuenta ya sea del rendimiento o reportes
financieros de una organización.

Después se presentó la teoría clásica de optimización para encontrar máximos y

mínimos de los problemas no lineales restringidos. Y la conclusión es que no es
adecuada para fines de cálculo. En el caso del método simplex para
sistemas lineales las condiciones de optimidad y factibilidad garantizan,
partiendo de un punto extremo factible (solución básica), el poder mejorar el valor de la
función objetivo hasta llegar al óptimo en cada iteración.

21
22
 CUESTIONARIO

1.- ¿Qué es un algoritmo?

Un algoritmo es un conjunto ordenado y finito de pasos o instrucciones que permite
realizar una actividad mediante pasos sucesivos sin generar duda a quien deba realizar
dicha actividad.

2.- ¿Qué es un algoritmo especial?

Son diseñados para problemas de programación lineal, son problemas enunciados
con ecuaciones lineales, con una función objetivo y una o mas funciones restricciones
para lograr la optimización de la función objetivo que se analiza.

3.- ¿En donde se ocupan los algoritmos especiales?

Son muy usados en la microeconomía y la administración de empresas, ya sea para
aumentar al máximo los ingresos o reducir al mínimo los costos de un sistema de
producción.

4.- ¿Qué es el problema del transporte?

El término “Problema del Transporte” está ligado a la literatura de Investigación de
Operaciones como una aplicación exitosa para resolver el problema de distribuir carga
de la manera más económica desde los orígenes donde ésta se encuentra hasta los
destinos donde es requerida, dados los costos de transporte desde cada origen hasta cada
destino.

5.- ¿Cuándo resurge el problema del transporte?

El problema del transporte resurgió en la década de 1940 dentro de la corriente de
trabajos planteados con el nacimiento de la Investigación de Operaciones como una
disciplina autónoma. El problema fue considerado en 1941 por Hitchcock e
independientemente por Kantorovich en 1942 y por Koopmans en 1947. El modelo de
Hitchcock plantea encontrar el mínimo costo de distribuir un producto desde varias
fábricas a un número dado de ciudades, y desde entonces el modelo es conocido
también como el Problema de Transporte de Hitchcock. En 1951, G. Dantzig desarrolló

23
la primera solución al problema, utilizando programación lineal (Arnoff & Segupta,
1961)
6.- ¿Cuáles son los elementos del problema del transporte?
a)     Una función objetivo, esto es, el costo total del plan de transporte, que refleja el
objetivo del decisor, así como un criterio mensurable para la transportación involucrada,
es decir, la tonelada-kilómetro (considerando la distancia como costo).
b)     Las restricciones del problema, esto es, las distintas ofertas de productos en los
orígenes y las respectivas demandas en los destinos, y
c)      Los parámetros del problema, es decir, los costos para los distintos enlaces
origen-destino que representan las características de la red carretera.

7.- ¿Cómo es el planteamiento del problema del transporte?

El planteamiento del problema de transporte como un programa lineal, junto con la
interpretación dual de éste permite visualizar un segundo punto de vista del problema,
donde el interesado es el embarcador que intenta satisfacer la demanda en los destinos,
tratando de maximizar el beneficio que le representa la operación.

8.- ¿Cuál es la formula para el problema del trasnporte?

El planteamiento es como sigue: llamando Xij al flujo de productos del origen  i  al
destino  j  , cij al costo unitario por tonelada movida, Si a la oferta de producto en el
nodo i  , Dj  a la demanda de productos en el nodo j, y Z al costo total del plan de
transporte, entonces para el caso con dos orígenes y tres destinos,

9.- ¿Qué es el problema de asignación?

El problema de la asignación es uno de los problemas fundamentales de
optimización combinatoria de la rama de optimización o investigación operativa en
matemática.

Una descripción apropiada de lo que trata de lograr el modelo de asignación es:

"La mejor persona para el trabajo"

24
 10.- ¿Cuándo se utiliza el problema de asignación?
El problema de asignación tiene que ver con la designación de tareas a empleados, de
territorios a vendedores, de contratos a postores o de trabajos a plantas, etc. En otras
palabras, a la disposición de algunos recursos (máquinas o personas) para la realización
de ciertos productos a costo mínimo.

11.- ¿Dónde se utiliza el problema de asignación?

Este tipo de problemas son lineales, con una estructura de transporte, sólo que la
oferta en cada origen es de valor uno y la demanda en cada destino es también de valor
uno. Sería muy ineficiente resolver este tipo de problemas por medio del método
simplex o por medio del de transporte. Debido a la estructura propia de los problemas
de asignación, existen métodos de solución llamados algoritmos de asignación que son
más eficientes que el simplex o que el método de transporte.

12.- ¿Cuándo surge el problema de asignación?

El problema de asignación tuvo su origen en la revolución industrial, ya que el
surgimiento de las máquinas hizo que fuera necesario asignar una tarea a un
trabajador.

Thomas Jefferson en 1792 lo sugirió para asignar un representante a cada estado,

pero formalmente aparece este problema en 1941, cuando F.L. Hitchcook publica una
solución analítica del problema, pero no es hasta 1955 cuando Harold W. Kuhn plantea
el Método húngaro, que fue posteriormente revisado por James Munkres en 1957; dicho
método está basa.
13.- ¿Cómo se plantea el problema de asignación?
Los problemas de asignación presentan una estructura similar a los de transporte,
pero con dos diferencias: asocian igual número de orígenes con igual número de
demandas y las ofertas en cada origen es de valor uno, como lo es la demanda en cada
destino.

25
 14.- ¿Cuáles son las caracteristicas del problema de transporte?
El Problema de Asignación debe estar equilibrado, es decir, que las ofertas y las
demandas sean igual a 1. Un elemento importante para el problema de asignación es la
matriz de costos, si el número de renglones o columnas no son iguales el problema está
desbalanceado y se puede obtener una solución incorrecta, para obtener una solución
correcta la matriz debe ser cuadrada.

Si el número de agentes y tareas son iguales y el coste total de la asignación para

todas las tareas es igual a la suma de los costes de cada agente (o la suma de los costes
de cada tarea, que es lo mismo en este caso), entonces el problema es llamado problema
de asignación lineal.

15.- ¿Qué es oferta?

Cantidad que representa la disponibilidad del artículo en la fuente/fábrica de donde
proviene.

16.- ¿Qué es demanda?

Cantidad de artículos que necesita recibir el destino para cumplir sus necesidades.

17.- ¿Qué es el algoritmo hungaro?

El algoritmo Húngaro es uno de los muchos algoritmos que han sido diseñados para
resolver el problema de la asignación lineal con un tiempo acotado por una expresión
polinómica del número de agentes.

18.- ¿Para qué sirve el Software winQsb?

El WinQsb maneja el problema del transporte en su módulo de Modelos de Redes.

19.- ¿Para qué sirve el Software INVOP?

Este software maneja las siguientes aplicaciones: asignaciones, transporte, distancia en

redes (ruta más corta, árbol de mínimo recorrido, agente viajero), flujo de redes.

20.- ¿Qué tipos de problemas resuelven estos software?

Trasnporte y asignación

26
 BIBLIOGRAFIA

REFERENCIAS
1. Appell, P. “Le probléme géométrique des déblais et ramblais”. (in French). Gauthier-
Villars. Paris. [online]. Available at: URL:http://gallica.bnf.fr. [Accessed January
2003]. 1928.
2. Arnoff, E.L. and Sengupta, S.S. Mathematical programming. In: “Progress in Operations
Research”. Vol. I. Edited by Russell L. Ackoff. John Wiley & Sons. USA. 1961.
3. Bazaraa, M.S., Jarvis, J.J. and Sherali, H.D. “Linear programming and network flows”.
John Wiley & Sons. Singapore. 1990.
4. Cournot, A. “Researches into the mathematical principles of the theory of wealth”.
Translated by Nathaniel T. Bacon. The Macmillan Co. New York, 1927. 1838.
5. Harker, P.T. Issues and models for planning and regulating freight transport systems. In:
“Lecture Notes in Economics and Mathematical Systems”. Lucio Bianco and Agostino
La Bella, editors. International Seminar on Freight Transport Planning and Logistics,
Italy. Springer-Verlag.pp. 374-408. 1987.
6. Moreno, E. Planner-user interactions in road freight transport. “A modelling approach
with a case study from Mexico”. (PhD Thesis). Institute for Transport Studies,
University of Leeds. United Kingdom. 2004.
7. Ortúzar, J.D. and Willumsen, L.G. “Modelling Transport”. 2nd edition. Chichester, UK.
John Wiley & Sons. 1994.
8. Schrijver, A. “Theory of Linear and Integer Programming”. John Wiley & Sons.
Chichester. pp 376-377. 1986.
9. Taton, R. “L’oeuvre scientifique de Monge”.  Presses Universitaires de France. Paris. pp.
193-196. 1951.

10. El Problema De Asignacion. (2014, noviembre 9). Clubensayos.com.

https://www.clubensayos.com/Temas-Variados/El-Problema-De-Asignacion/

2179152.html

27
 11. Wikipedia contributors. (s/f). Problema de asignación. Wikipedia, The Free

Encyclopedia. https://es.wikipedia.org/w/index.php?title=Problema_de_asignaci

%C3%B3n&oldid=148233641

12. Yunior, A. C. S. (2015, mayo 11). Problema de asignación en la investigación de

operaciones. Monografias.com. https://www.monografias.com/trabajos104/problema-

asignacion-investigacion-operaciones/problema-asignacion-investigacion-operaciones

https://es.slideshare.net/kakel17/unidad-3-algoritmos-especiales-de-programacion-lineal

28