UNIDAD 3 Algoritmos Especiales de Programación Lineal

UNIDAD 3
Algoritmos especiales de Programación

Lineal
Un algoritmo es un conjunto prescrito de instrucciones o reglas bien definidas, ordenadas y finitas que
permite llevar a cabo una actividad mediante pasos sucesivos que no generen dudas a quien deba hacer dicha
actividad. Dados un estado inicial y una entrada. Utilizados en programación.
3.1. El problema de 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).
El problema del transporte o distribución es

un problema de redes especial en programación
lineal que se funda en la necesidad de llevar
unidades de un punto específico
llamado Fuente u Origen hacia otro punto
específico llamado Destino. Los principales
objetivos de un modelo de transporte son la
satisfacción de todos los requerimientos
establecidos por los destinos y claro está la
minimización de los costos relacionados con el
plan determinado por las rutas escogidas.
El contexto en el que se aplica el modelo de transporte es amplio y

puede generar soluciones atinentes al área de operaciones,
inventario y asignación de elementos.
El procedimiento de resolución de un modelo de transporte se puede llevar a cabo mediante programación lineal
El procedimiento de resolución de un modelo de transporte se puede llevar a cabo mediante programación lineal
común, sin embargo su estructura permite la creación de múltiples alternativas de solución tales como la estructura de
común, sin embargo su estructura permite la creación de múltiples alternativas de solución tales como la estructura de
asignación o los métodos heurísticos más populares como Vogel, Esquina Noroeste o Mínimos Costos.
asignación o los métodos heurísticos más populares como Vogel, Esquina Noroeste o Mínimos Costos.
Los problemas de transporte o distribución

son uno de los más aplicados en la economía
actual, dejando como es de prever múltiples
casos de éxito a escala global que estimulan
la aprehensión de los mismos.
MÉTODO DE SOLUCIÓN.
1. Construir una tabla inicial de transporte: la cual incluye toda la

información de costos, oferta y demanda.
• Una forma práctica de representar un problema de transporte es la
siguiente tabla.
2. Hallar una solución inicial : existen varios métodos, estudiaremos 5

la regla del Costo Mínimo
1
1 15
3. Mejorar la solución: Técnica iterativa para pasar de una solución 2
factible a una solución óptima. Este proceso consta de dos partes, la
primera es someter a prueba la solución actual para determinar si es
2
15
posible una mejora, la segunda parte consiste en modificar la 3
solución actual para obtener una solución mejorada.
3 10
4
El problema de transporte puede ser resuelto de las siguientes formas:
MÉTODO SIMPLEX: El problema de transporte puede ser resuelto planteando el modelo de programación lineal y
utilizar ya sea el método de la M Grande o el método de las dos fases (métodos variantes del método simplex).
TÉCNICA DE TRANSPORTE: Consta de los mismos pasos del método simplex sin embargo es una técnica especifica
de solución.
Para que un problema de transporte pueda ser resuelto a través de la técnica de transporte debe cumplir con las
características:
• Ser un problema equilibrado (la oferta total y la demanda total deben ser igual).
• Contar con (n+m-1) variables básicas, siendo n los puntos de demanda y m los puntos de oferta.
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.
2) Una 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. Sea:
X i j = Unidades enviadas del origen i
4) Una lista de demandas de utilidades o bienes dj de cada ( i =1,2,...m), al destino j ( j = 1,2,...,n)
punto de demanda j las cuales deben satisfacerse
mínimamente. C i j = Costo unitario desde el nodo origen
i hasta el nodo destino j.
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 = Oferta del origen i, ( i = 1, 2,...,m);
i y enviada al punto de demanda j, cij . b j = Demanda del destino j ( j = 1, 2,...,n)
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.
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.
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.
3.2.El problema de asignación: planteamiento del problema,
Algoritmo para determinar la asignación óptima.
El problema de
asignación consiste en encontrar Es uno de los problemas fundamentales
la forma de asignar ciertos de optimización combinatoria de la rama
recursos disponibles (máquinas o de optimización o investigación
personas) para la realización de operativa en matemática. El modelo se
determinadas tareas al menor puede aplicar a la asignación de
coste, suponiendo que cada empleados a tareas, de fábricas a
recurso se destina a una sola productos, de vendedores a territorios, de
tarea, y que cada tarea es postores a contratos, etc. Con una sencilla
ejecutada por uno solo de los manipulación, el método también se puede
recursos. aplicar al caso en el que se pretende
maximizar cierta cantidad.
EL PROBLEMA DE LA ASIGNACIÓN consiste en encontrar un emparejamiento de peso óptimo en un grafo
bipartito ponderado. El problema de asignación es un caso particular del problema de transporte, en el que la oferta en
cada origen y la demanda en cada destino son ambas de valor 1.
El problema de asignación Para la representación de un problema de asignación

El problema de asignación
es necesario acoplar un se requiere de un grafo bipartito.
esnumero
necesario acoplar
determinadoun de G=(N,E) cuyos vértices se pueden separar en
numero determinado
personas de
a un numero dos conjuntos disjuntos U y V, es decir, tal que se
personas a un numero
especifico de tareas Donde cualquier
Donde cualquier
cumple:
especifico de tareas persona puede ser
persona puede ser
asignado para
asignado para
desarrollar cualquier
desarrollartarea
cualquier
tarea
de manera que las aristas sólo pueden conectar
Se requiere evaluar la vértices de un conjunto con vértices del otro; es
Seasignación
requiere evaluar la
de un mayor decir:
asignación
numero de de un mayor
tareas a una sola
numero de tareas a una
persona para que el costesolatotal
persona para que elsea
de asignación coste total
mínimo
de asignación sea mínimo
Los grafos bipartitos suelen representarse gráficamente con En su forma más general, el problema es como sigue:
dos columnas (o filas) de vértices y las aristas uniendo
vértices de columnas (o filas) diferentes. Hay un número de agentes y un número de tareas.
Cualquier agente puede ser asignado para desarrollar
Un grafo bipartito con la partición de los vértice cualquier tarea, contrayendo algún coste que puede variar
en U y V suele denotarse G = (U, V, E). Si |U| =|V|, esto es, si dependiendo del agente y la tarea asignados.
los dos subconjuntos tiene la misma cantidad de elementos,
decimos que el grafo bipartito G es balanceado. Este tipo de problemas son lineales, con una estructura
de transporte, solo 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 algoritmo de transporte.
• La particularidad con el problema es que: 0i =1, El problema de asignación presenta las siguientes características:
dj =1 para todo i,j
• El Problema de Asignación debe estar equilibrado, es decir, que las
• Los orígenes = son trabajadores, proyectos, ofertas y las demandas sean igual a 1.Para obtener una solución
maquinas, personas, agentes. correcta la matriz debe ser cuadrada.
• Los destinos = trabajo, entidades, tareas, • 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
servicios, ciudades.
cada agente el problema es llamado problema de asignación lineal.
Formas de representación:
• Modelo de programación lineal

• Matriz de costos
• Tabla de transporte
• Red
CASOS ESPECIALES
• Oferta y demanda desiguales. Cuando la oferta y la demanda son
desiguales, se asigna una actividad ficticia con un costo de cero para
mantener la condición de método que deben ser igual número de ofertas
y demandas
• Problemas de Maximización. Considere un problema de asignación en

el que la respuesta a cada asignación es una utilidad en vez de un costo.
• Problemas con asignación inaceptable. No sabe que ciertas

asignaciones son inaceptables. Para alcanzar esta meta, simplemente
asigna un costo arbitrariamente grande representado mediante la letra M.
M es un número tan grande que si se le resta un número finito
cualquiera, queda todavía un valor mayor que los demás.
• Problema de selección: Es un caso especial donde la función u objetivo

es maximizar pero el problema se trata igual que una minimización al
multiplicar por (-1).
3.3. El uso de software
SOLVER
SOLVER
Solver es una herramienta que forma parte de una serie de
Solver es auna
comandos herramienta
veces que forma
denominados parte deYuna
de "análisis si".serie
Conde
comandos
Solver, puedea buscarse
veces denominados
el valor óptimo de para
"análisis Y si". Con
una fórmula de
Solver,
celda, puede buscarse
denominada celda el valor óptimo
objetivo, en unapara
hojauna fórmula de
de cálculo.
celda,funciona
Solver denominada
en un celda
grupo objetivo,
de celdas enqueuna hoja
estén de cálculo.
relacionadas,
Solvero funciona
directa en un grupo
indirectamente, con ladefórmula
celdas que estén
de la relacionadas,
celda objetivo.
Solver ajusta los valores en las celdas cambiantes objetivo.
directa o indirectamente, con la fórmula de la celda que se
Solver ajusta los valores en las celdas cambiantes
especifiquen, denominadas celdas ajustables, para generar queelse
especifiquen,
resultado denominadas
especificado celdas de
en la fórmula ajustables, para generar el
la celda objetivo.
resultado especificado en la fórmula de la celda objetivo.
ALGORITMOS Y MÉTODOS UTILIZADOS POR
SOLVER
La herramienta Microsoft Excel Solver utiliza el código de

optimización no lineal (GRG2) desarrollado por la
Universidad Leon Lasdon de Austin (Texas) y la
Universidad Allan Waren (Cleveland).

Los problemas lineales y enteros utilizan el Método

Simplex con límites en las variables y el método de
ramificación y límite (método de branch and bound),
implantado por John Watson y Dan Fylstra de Frontline
Systems, Inc. El método de branch and bound corresponde
al mismo método utilizado por WinQSB para la solución de
problemas de programación lineal entera y/o que utilicen
variables binarias.
¿CÓMO HABILITAR EL COMPLEMENTO SOLVER DE
EXCEL?
1. El primer paso consiste en dirigirse a la pestaña "Archivo", dirigirse a la

opción "Ayuda" y seleccionar la opción "Opciones":
2. Luego, se abrirá una ventana emergente de "Opciones de Excel", en ella

vamos a la opción "Complementos" (ubicada en la barra lateral izquierda).
Ya en complementos, nos dirigimos a la opción "Administrar: Complementos
de Excel" y damos clic en botón "IR":
3. Luego se abrirá una pequeña ventana emergente, en ella se podrán observar

varios complementos junto con una casilla de verificación cada uno.
Activamos la casilla de verificación de Solver y damos clic en "Aceptar":
4. Una vez se ha habilitado el complemento, para ambas versiones, Solver se

ubicará en la pestaña de "Datos".

UNIDAD 3 Algoritmos Especiales de Programación Lineal

Cargado por

Copyright:

Formatos disponibles

UNIDAD 3 Algoritmos Especiales de Programación Lineal

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

UNIDAD 3 Algoritmos Especiales de Programación Lineal

Cargado por

Copyright:

Formatos disponibles

UNIDAD 3

Algoritmos especiales de Programación

El problema del transporte o distribución es

El contexto en el que se aplica el modelo de transporte es amplio y

Los problemas de transporte o distribución

1. Construir una tabla inicial de transporte: la cual incluye toda la

2. Hallar una solución inicial : existen varios métodos, estudiaremos 5

1) Un conjunto de m puntos de oferta desde los cuales se

2) Una lista de capacidades de suministro máximo de cada sitio

3) Un conjunto de n puntos de demanda hacia los cuales se

El problema de asignación Para la representación de un problema de asignación

• Modelo de programación lineal

• Problemas de Maximización. Considere un problema de asignación en

• Problemas con asignación inaceptable. No sabe que ciertas

• Problema de selección: Es un caso especial donde la función u objetivo

La herramienta Microsoft Excel Solver utiliza el código de

Los problemas lineales y enteros utilizan el Método

1. El primer paso consiste en dirigirse a la pestaña "Archivo", dirigirse a la

2. Luego, se abrirá una ventana emergente de "Opciones de Excel", en ella

3. Luego se abrirá una pequeña ventana emergente, en ella se podrán observar

4. Una vez se ha habilitado el complemento, para ambas versiones, Solver se

También podría gustarte