TECNOLÓGICO NACIONAL DE MÉXICO

INSTITUTO TECNOLÓGICO DE OAXACA (TECNM CAMPUS OAXACA)

SEMESTRE AGOSTO-DICIEMBRE 2023

INGENIERÍA CIVIL
GRUPO:3CD
INVESTIGACION TEMA III
ALGORITMOS ESPECIALES DE
PROGRAMACION LINEAL.

CATEDRATICO:
HERNÁNDEZ MORENO FRANCISCO

ALUMNOS DEL EQUIPO 8:

MARTINEZ SANCHEZ JOSE LUIS
GONZÁLEZ VÁSQUEZ BETZABÉ
VASQUEZ CARRAZCO GUADALUPE DEL CARMEN
VÁSQUEZ ROCHELLE TIFFANY
MELCHOR GARCÍA HASSAN

FECHA DE ENTREGA:

1
 INDICE

INDICE.................................................................................................................................................. 2
3.1. El problema de transporte: planteamiento del problema, determinación de la Solución Básica
Factible Inicial, el criterio de optimalidad y el algoritmo de mejoramiento de la solución (Ruta de
los signos). ........................................................................................................................................... 4
Planteamiento del problema ......................................................................................................... 4
Modelo de programación lineal del problema de transporte ...................................................... 5
Determinación de la Solución Básica Factible ............................................................................... 6
Método de la esquina noroeste ..................................................................................................... 6
Problema de ejemplo ................................................................................................................. 6
Método del costo mínimo .............................................................................................................. 8
Problema ejemplo: ..................................................................................................................... 8
Método de Vogel .......................................................................................................................... 10
Problema ejemplo .................................................................................................................... 10
3.2 EL PROBLEMA DE ASIGNACION ................................................................................................... 15
3.3 EL USO DE SOFTWARE ................................................................................................................. 20
Software WinQsb.......................................................................................................................... 20
Software INVOP ............................................................................................................................ 22
FUENTES ............................................................................................................................................ 24

2
 INTRODUCCION

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.

3
3.1. El problema de transporte: planteamiento del problema, determinación de la
Solución Básica Factible Inicial, el criterio de optimalidad y el algoritmo de
mejoramiento de la solución (Ruta de los signos).

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á, una relación de uno a otro. 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 está en el gran número de combinaciones posibles, debido a eso el
problema del transporte recurre a buscar soluciones con la computara y software
especializado.
El responsable de gestión del trasporte debe determinar una política óptima: cómo hacer
llegar los productos de sus diversos depósitos, plantas de producción o bodegas a sus
consumidores o clientes, con el objeto de satisfacer la demanda a un costo mínimo de
transporte o de envío.

Planteamiento del problema

El problema del transporte en general se especifica mediante la siguiente información:

1. Un conjunto de m puntos de oferta desde los cuales se envían utilidades o bienes.
[Link] lista de capacidades de suministro máximo de cada sitio de oferta si para i = 1, 2,...,m.
3. Un conjunto de n puntos de demanda hacia los cuales se envía una utilidad o bien.
4. Una lista de demandas de utilidades o bienes dj de cada punto de demanda j las cuales
deben satisfacerse mínimamente.
5. Una matriz de valores que indica el costo fijo en el que se incurre al enviar una unidad
producida en el punto de oferta i y enviada al punto de demanda j, cij .

4
Modelo de programación lineal del problema de transporte
Sea: X i j = Unidades enviadas del origen i ( i =1,2,...m), al destino j ( j = 1,2,...,n)
C i j = Costo unitario desde el nodo origen i hasta el nodo destino j.
𝑎𝑖 = Oferta del origen i, ( i = 1, 2,...,m); b j = Demanda del destino j ( j = 1, 2,...,n)

El modelo de programación lineal aquí mostrado se presenta para un problema balanceado

con las restricciones de oferta y demanda en igualdad. Para el caso de un problema no
balanceado (oferta y demanda en desigualdad) es necesario el

5
Determinación de la Solución Básica Factible
La utilización del método SIMPLEX no resulta eficiente para resolver el Problema de
Transporte, por lo cual se utilizan otros métodos como:
a) Método de la Esquina Nor-Oeste (N-O)
b) Método de la Matriz de Costo Mínimo
c) Método de Vógel

Método de la esquina noroeste

Características

• Sencillo y fácil de hacer

• No tiene en cuenta los costos para hacer las asignaciones

• Generalmente nos deja lejos del óptimo

Algoritmo
1. Construya una tabla de ofertas (disponibilidades) y demandas (requerimientos).
2. Empiece por la esquina noroeste.
3. Asigne lo máximo posible (Lo menor entre la oferta y la demanda, respectivamente)
4. Actualice la oferta y la demanda y rellene con ceros el resto de casillas (Filas ó Columnas)
en donde la oferta ó la demanda halla quedado satisfecha.
5. Muévase a la derecha o hacia abajo, según halla quedado disponibilidad para asignar.
6. Repita los pasos del 3 al 5 sucesivamente hasta llegar a la esquina inferior derecha en la
que se elimina fila y columna al mismo tiempo.
Nota: No elimine fila y columna al mismo tiempo, a no ser que sea la última casilla. El
romper ésta regla ocasionará una solución en donde el número de variables básicas es
menor a m+n-1, produciendo una solución básica factible degenerada.

Problema de ejemplo
Una compañía tiene 3 fábricas ubicadas en A, B y C, las cuales proveen a los
almacenes que están ubicados en D, E, F y G. La capacidad de producción de las
fábricas es de 70, 90 y 115 unidades mensuales respectivamente, mientras que las
capacidades de los almacenes son de 50, 60, 70 y 95 unidades respectivamente. El costo de

6
envió de una unidad desde cada una de las fábricas a cada una de los almacenes se presenta
en el siguiente cuadro (en pesos):

Por consiguiente la solución es:

7
Método del costo mínimo

Características:

• Es más elaborado que el método de la esquina noroeste

• Tiene en cuenta los costos para hacer las asignaciones

• Generalmente nos deja alejados del óptimo

Algoritmo:
1. Construya una tabla de disponibilidades, requerimientos y costos
2. Empiece en la casilla que tenga el menor costo de toda la tabla, si hay empate, escoja
arbitrariamente (Cualquiera de los empatados).
3. Asigne lo máximo posible entre la disponibilidad y el requerimiento (El menor de los dos).
4. Rellene con ceros (0) la fila o columna satisfecha y actualice la disponibilidad y el
requerimiento, restándoles lo asignado.
Nota: Recuerde que no debe eliminar ó satisfacer fila y columna al mismo tiempo, caso en
que la oferta sea igual a la demanda, en tal caso recuerde usar la ε (Épsilon).
5. Muévase a la casilla con el costo mínimo de la tabla resultante (Sin tener en cuenta la
fila o columna satisfecha).
6. Regrese a los puntos 3,4,5 sucesivamente, hasta que todas las casillas queden asignadas.

Problema ejemplo:

El hospital Saludmuch pertenece a la Compañía de Seguros Todosalud SA. Esta sociedad

tiene un Centro de Asistencia Primaria (CAP) en 5 ciudades de una región (un CAP en cada
ciudad). Para obtener un buen funcionamiento global del servicio y poder planificar el
número de visitas en función del personal previsto en cada CAP y de su dimensión,
Todosalud S.A. ha decidido organizar el servicio de tal forma que todos sus asegurados
tengan un CAP de referencia asignado, pero que sea éste el más cercano posible a su lugar
de residencia. En la región hay 5 ciudades y la compañía sabe cuántos asegurados tiene en
cada uno de ellos. Los CAP tienen una capacidad máxima de pacientes que pueden soportar.
El objetivo es asignar a los asegurados a los CAPs minimizando el coste de desplazamiento
o la distancia total.

8
Si no existiera el problema de capacidad de los CAPs, el modelo sería trivial, ya que bastaría
asignar cada ciudad al CAP más cercano, obteniéndose el coste de transporte más barato.
Al tener límites en la capacidad, puede ser que no todas las ciudades tengan asignado el
centro más cercano, ya que esto implicaría una sobre utilización. Entonces, puede ser que
alguna ciudad, o parte de ella tenga asignada un CAP que no es el más cercano, en función
de la disponibilidad o holgura del sistema.
En su forma tabular quedaría de la siguiente manera:

9
Método de Vogel

Características

• Es más elaborado que los anteriores, más técnico y dispendioso.

• Tiene en cuenta los costos, las ofertas y las demandas para hacer las asignaciones.

• Generalmente nos deja cerca al óptimo.

Algoritmo
1. Construir una tabla de disponibilidades (ofertas), requerimientos (demanda) y costos.
2. Calcular la diferencia entre el costo más pequeño y el segundo costo más pequeño, para
cada fila y para cada columna.
3. Escoger entre las filas y columnas, la que tenga la mayor diferencia (en caso de empate,
decida arbitrariamente).
4. Asigne lo máximo posible en la casilla con menor costo en la fila o columna escogida en
el punto 3.
5. asigne cero (0) a las otras casillas de la fila o columna donde la disponibilidad ó el
requerimiento quede satisfecho.
6. Repita los pasos del 2 al 5, sin tener en cuenta la(s) fila(s) y/o columna(s) satisfechas,
hasta que todas las casillas queden asignadas.
Nota: Recuerde que no debe satisfacer filas y columnas al mismo tiempo; caso en que la
disponibilidad sea igual al requerimiento; en tal caso use el ε (epsilon).

Problema ejemplo

10
Fíjese que la mayor diferencia la tiene la columna 4 con un valor de 19, escogido entre
2,2,3,0,15,13,19 y 16.
El menor costo de la columna 4 es cero (0), se asigna lo máximo posible entre 50 y 40, que
es 40, se satisface la columna y se actualiza la oferta y la demanda.
Ahora recalculamos las diferencias, sin tener en cuenta la columna 4, que está satisfecha.
Una vez ejecutado todo el algoritmo hasta asignar todas las casillas, obtenemos la siguiente
asignación básica y factible inicial.

El criterio de la optimalidad
Hemos conseguido tres (3) soluciones básicas factibles no degeneradas por medio de tres
métodos: El de la esquina noroeste, el del costo mínimo y el de Vogel. Pero ninguna de ellas
nos garantiza que la solución encontrada es la óptima. Para saberlo, debemos estar seguros
que ninguna de las variables no básicas pueda entrar a la base haciendo que la función
objetivo disminuya. Para discernir un método que nos evalúe el efecto de introducir una
unidad de cada variable no básica, recurrimos al método MODI.
Método MODI o UV
Consideremos la solución inicial hallada por el método de la Esquina N.O.

11
Paso 2: Se dibuja la matriz Zij que contiene los costos de la variable solución.

Paso 3: Se construye un conjunto de números vj y ui tal que la suma iguale a los valores de
la matriz Zij del paso 2 y se completa las celdas vacías con la suma de los ui y vj la matriz Zij
que contiene los costos de la variable solución.

Se tiene las siguientes ecuaciones de las celdas básicas:

U1 + v1 = 17 u2 + v3 = 26
U1 + v2 = 20 u3 + v3 = 15
U2 + v2 = 21 u3 + v4 = 17
Haciendo v1 = 0 se encuentra que: u1 = 17 ; v2 = 3 ; u2 = 18 V3 = 8 ; u3 = 7 ; v4 = 10 Paso 4:
Se calcula Cij – Zij

12
13
Se selecciona la casilla (3,2) que tiene el costo de entrada más pequeño, por consiguiente
debe entrar a la base la variable X32

14
El costo de la nueva solución es: Z2 = 4465+ (20)(-14) = 4185
A continuación probamos si esta solución es o no la óptima Se calcula Cij - Zij

3.2 EL PROBLEMA DE ASIGNACION

Introducción
Muchas de las situaciones en la vida exigen una de dos respuestas posibles: si o no. Así
Muchas de las situaciones en la vida exigen una de dos respuestas posibles: si o no. Así es
que podemos representar éstas posibilidades con los valores 0 (no) y 1 (si), y aprovechar las
matemáticas para que nos den una mano ante decisiones difíciles; a esto es lo que solemos
llamar -por obvias razonesProgramación Binaria.
Una de las muchísimas aplicaciones de la Programación Binaria, es el problema de la
Asignación. Este método analiza el problema de asignar un cierto número de recursos a un
determinado número de tareas, con base en algún tipo de valoración para cada recurso.
Cada recurso, podrá ser asignado a una sola tarea.

15
El PA consiste en asignar recursos a tareas en función de un objetivo ligado a la eficiencia
del sistema. Un ejemplo típico es el de asignación de personas a turnos horarios, o el de
asignar personas a máquinas.
El esquema tabular del PA es:

Planteamiento del problema

Minimizar el costo total de operación de modo que:
• cada tarea se asigne a una y sólo una máquina
• cada máquina realice una y sólo una tarea

16
Algoritmo para determinar la asignación optima
La utilización del método SIMPLEX o los métodos del Problema de Transporte, no resultan
eficientes para resolver el Problema de Asignación, por lo cual se utiliza otro método
denominado METODO HÚNGARO.

El Método Húngaro se desarrolló por Kuhn, basado en un trabajo de Egerváry y Konig. Fue
Kuhn quien lo denominó: Método Húngaro.
Característica del Método Húngaro

El método a estudiar tiene la siguiente característica:

a) Se garantiza la solución óptima.
b) El procedimiento requiere que la matriz de costos sea no negativa.
c) La solución óptima se obtiene en una matriz de costos equivalente cuyo valor óptimo es
cero (0).
d) El problema planteado debe estar balanceado:

e) La solución óptima no varía si a la matriz original se le incrementa un valor k a cada celda.

Pero el valor Z se incrementa en nk.
f) La solución óptima no varía si a la matriz original se le incrementa un valor k a una fila o
columna. Pero el valor Z se incrementa en k.

Proceso del Método Húngaro

1) Reducción por filas Determinar el mínimo valor de cada fila y restarlo a todas las celdas
de su correspondiente fila. Esto garantiza un cero en cada fila.
2) Reducción por columnas Determinar el mínimo valor de cada columna y restarlo a todas
las celdas de su correspondiente columna. Esto garantiza un cero en cada columna.
3) Cubrimiento de ceros Con el mínimo número de rectas cubrir los ceros de la matriz
reducida. Empezar por la fila o columna que tenga el mayor número de ceros. Si el número
de rectas resulta igual a n (número de tareas o equipos) se ha llegado a la solución óptima
Pasar al paso 5 de lo contrario pasar al óptima. 5, paso 4.

17
4) Reducción posterior Localizar la celda no cubierta de menor costo. Restar el valor
determinado a las celdas no cubiertas. Sumar el valor determinado a las celdas que se
encuentren en la intersección de las rectas. Regresar al paso 3.
5) Localización de la solución Determinar las filas que tengan un único valor cero y
asignarlos, eliminar las columnas correspondientes. Determinar las columnas que tengan
un único valor cero y asignarlos, eliminar las filas correspondientes. Repetir este
procedimiento tantas veces sea necesario. En caso de celdas con empates seleccionar
arbitrariamente. La asignación localizada de valor cero, implantarla en la matriz de costos
original y determinar el valor de Z.

Problema ejemplo
Existen 5 operarios (A, B, C, D y C) que tienen que llenar 5 cargos (I, II, III, IV y V). La matriz
de costos que caracteriza el problema de asignación es la siguiente:

Determinar la asignación óptima

1- Se calcula C’ij= Cij – elemento más pequeño de cada columna

18
2. Se calcula C*ij = C’ij – elemento mas pequeño de cada fila

3. Procederemos a encontrar el número mínimo de recta r que cubren todos los ceros de la
matriz C*

Vemos que r = 4 que es diferente de m=5, por consiguiente no se ha llegado al óptimo

4. En este caso ⍬= 1 (elemento mínimo no cubierto por las rectas). Se resta ⍬ a todos
los elementos no cubiertos por las rectas- Se suma ⍬ a todos los elementos en las
intersecciones entre 2 rectas y se vuelve al paso 3. La matriz C* se transforma en

19
Se observa que r = 5 = m =5, por consiguiente se ha llegado al óptimo 6. Determinamos la
asignación óptima.

Hay dos soluciones óptimas:

A es asignado a IV
B es asignado a II
C es asignado a I
D es asignado a V
E es asignado a II
O bien:
A es asignado a V
B es asignado a II
C es asignado a I
D es asignado a IV
E es asignado a III El costo total del programa en ambos casos es Z = $ 18

3.3 EL USO DE SOFTWARE

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í:

20
Fíjese que éste 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 ó tablero de doble entrada ó 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 clic sobre el icono que aparece en la parte
superior y que se señala en la figura siguiente:

21
Software INVOP

Este software maneja las siguientes aplicaciones: Asignaciones, Transporte, Distancias 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 dirigido 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.

22
Al escoger la opción de transporte, el INVOP 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 ésta 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 ycolumna, 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, Entonces se
llena el cuadro en la parte inferior derecha con la solución óptima.

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.

23
 FUENTES

• [Link]
• [Link]
• [Link]
• [Link]
• 1. Arbonas, M.E. Optimización Industrial (I): Distribución de los recursos.
Colección Productica No. 26. Marcombo S.A, 1989
• 2. Arbonas, M.E. Optimización Industrial (II): Programación de recursos.
Colección Productica No. 29. Marcombo S.A, 1989.
• 3. Anderson, D.R., Sweeney.J. , Williams,T.A. , Introducción a los Modelos
Cuantitativos para Administración. Grupo Editorial Iberoamérica. 1993.

24