Unidad 3 algoritmos especiales de programacion lineal

ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3

ANGEL RAMOS APARICIO

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.

Introducción

¿Qué significa problema de transporte? Supongamos que un fabricante tiene tres

plantas que producen el mismo producto. Estas plantas a su vez mandan el

producto a dos depósitos. Cada planta puede mandar productos a todos los

depósitos, pero el costo de transporte varía con las diferentes combinaciones. El

INTRODUCCION

3.1 EL PROBLEMA DE TRANSPORTE



problema es determinar la cantidad que cada planta debe mandar a cada depósito

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á, 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.

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.

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 .



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

Equilibrio: = b j; además, debe cumplirse que toda X i j >= 0

Tabla del problema de transporte

D1 D2 ............... Dn ai

O1

c11 c12

...............c1n

a1

O2

c12 c22

...............c2n

a2

.........

.........

.........

...............

.........

.........

Om

cm1 cm2

...............

cmn

am

bj b1 b2 ................ bn

D E S T I N O S

O R

I G

E N

E S



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

Se colocan los datos en forma tabular:

Por consiguiente la solución es:

D1 D2 D3 D4

O1 17 20 13 12

O2 15 21 26 25

O3 15 14 15 17



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.

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:

CAP 1 CAP 2 CAP 3 CAP 4 CAP 5Número de

asegurados

Ciudad 1 2 5 4 8 6 500

Ciudad 2 5 6 3 8 7 700

Ciudad 3 6 2 8 10 5 1000

Ciudad 4 6 8 9 5 3 800

Ciudad 5 8 5 7 10 6 600

Capacidad

máxima de

atención

750 800 650 900 500



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

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.



Fíjese que el número de variables básicas es: m+n-1=8

Solución básica factible no degenerada:

X15=40 ; X21=30 ; X23=20 ; X25=10 ; X32=40 ; X33=30 ; X44=40 ; X45=10

Z = 16(40) + 15(30) + 13(20) + 16(10) + 15(40) + 18(30) + 0(40) + 0(10) = 2.650

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.

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

ai

17 20 13 12

50 20

15 21 26 25

40 50

15 14 15 17

20 95

bj

Z = $ 5305

90

115

50 60 70 95

D2 D3 D4

70O1

O2

O3

D1

17 20

21 26

15 17



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

vj

ui 0 3 8 10

17 17 20 25 27

18 18 21 26 28

7 7 10 15 17

17 20 13 12

15 21 26 25

15 14 15 17

vj

ui 0 3 8 10

17 17 20 25 27

18 18 21 26 28

7 7 10 15 17

0 0 -12 -15

-3 0 0 -3

8 4 0 0

Cij - Zij

-

=



Se selecciona la casilla (1,4) que tiene el costo de entrada más pequeño, por

consiguiente debe entrar a la base la variable X14

El costo de la nueva solución es: Z1 = 5305 + (20)(-15) = 3005

A continuación probamos si esta solución es o no la óptima

Se calcula Cij - Zij

ai

- +50 20

+ -40 50

+ -20 95

bj

O3 115

50 60 70 95

O1 70

O2 90

D1 D2 D3 D4 ai

50 20

60 30

40 75

bj

O3 115

50 60 70 95

O1 70

O2 90

D1 D2 D3 D4

17 20 13 12

15 21 26 25

15 14 15 17

vj

ui 0 -12 -7 -5

17 17 5 10 12

33 33 21 26 28

22 22 10 15 17

0 15 3 0

-18 0 0 -3

-7 4 0 0

Cij - Zij

-

=





El costo de la nueva solución es: Z2 = 5005 + (30)(-18) = 4465





ai

- +50 20

+ -60 30

+ -40 75

115

50 60 70 95

70

90

D1 D2 D3 D4 ai

20 50

30 60

70 45115

50 60 70 95

70

90

D1 D2 D3 D4

17 20 13 12

15 21 26 25

15 14 15 17

vj

ui 0 -6 -7 -5

17 17 23 10 12

15 15 21 8 10

22 22 28 15 17

0 -3 3 0

0 0 18 15

-7 -14 0 0

Cij - Zij

ai

- +50 20

+ -60 30

+ -40 75

bj

O3 115

50 60 70 95

O1 70

O2 90

D1 D2 D3 D4ai

70

50 40

20 70 25

bj

O3 115

50 60 70 95

O1 70

O2 90

D1 D2 D3 D4

-

=



El costo de la nueva solución es: Z2 = 4465+ (20)(-14) = 4185



Esta es la solución óptima

El algoritmo de mejoramiento de la solución

Dado que los métodos estudiados no garantizan una solución óptima, es

necesario verificar que no exista una ruta no utilizada que lo sea. De ser este el

caso, se determina esta nueva solución.

Se estudiarán 2 métodos para el mejoramiento de una solución básica factible

inicial:

a) Método de la Distribución Modificada

b) Método del Paso Secuencial

MÉTODO DEL PASO SECUENCIAL

1) Localizar una celda no básica, que no tenga costo marginal, y determinar

un circuito con el mínimo número de celdas básicas siguiendo trayectorias

horizontales y verticales solamente.

17 20 13 12

15 21 26 25

15 14 15 17

vj

ui 0 6 7 9

3 3 9 10 12

15 15 21 22 24

8 8 14 15 17

14 11 3 0

0 0 4 1

7 0 0 0

Cij - Zij

-

=



2) Asignar intercalando signos positivos “+” y negativos “-” al circuito

determinado en el paso 1, comenzando con la asignación “+” a la celda no

básica.



3) Determinar el costo marginal del circuito localizado, que consiste en el

costo de ingresar una unidad a la celda no básica utilizando los signos del

paso 2:

4) Si existen celdas no básicas sin costo marginal regresar al paso1.

5) Si todas las celdas no básicas tienen costo marginal no negativo la solución

actual es óptima. FIN.

6) Localizar la celda que tenga el costo marginal más negativo. Asignar a esta

celda xP, donde xP es el mínimo valor de las celdas del circuito que tienen signo

menos “-”:

xP = min (x1, x3, x5)

Reajuste el valor de las celdas básicas en xP conforme a los signos correspondientes:

x1 = x1 - xP

x2 = x2 + xP

x3 = x3 - xP

x4 = x4 + xP

x = x x

x5 x5 – xP

Z = Z + (Costo Marginal) x xP

7) Descarte los costos marginales de las celdas no básicas y regrese al paso 1.













MÉTODO DE LA DISTRIBUCIÓN MODIFICADA

1) Asignar a cada fila las variables:

ui , i = 1, 2, ..., m

Asignar a cada columna las variables:

vj , j = 1, 2, ..., n

2) Con cada celda básica se tiene:

cij = ui + vj

se asigna:

u1 = 0

determinar las restantes variable u y v.

3) Determinar el costo marginal de las celdas no básicas de la siguiente forma: Costo Marginal (k, m) = ckm – ( uk + vm ) 4) Si todas las celdas no básicas tienen costo marginal no negativo la solución actual es óptima.FIN. 5) Localizar la celda que tenga el costo marginal más negativo. Diseñar un circuito similar al método anterior para esta celda. Asignar a esta celda xP, donde xP es el mínimo valor de las celdas del circuito que tienen signo menos “-”: xP = min ( x1, x3, x5)

Reajuste el valor de las celdas básicas en xP conforme a los signos correspondientes:



6) Descarte los costos marginales de las celdas no básicas y regrese al paso 1.













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 razones-

Programació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.

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:

3.2 EL PROBLEMA DE ASIGNACION

M1 M2 ............... Mn ai

T1

c11 c12

...............c1n

1

T2

c12 c22

...............c2n

1

.........

.........

.........

...............

.........

.........

Tm

cm1 cm2

...............

cmn

1

bj 1 1 ................ 1

M A Q U I N A S

T A

R E

A S



• cada tarea se asigne a una y sólo una máquina

• cada máquina realice una y sólo una tarea

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:

1,0

..1,1

..1,1

..

c

n

1j

m

1i

m

1i

n

1j

ij

ij

ij

ij

ij

x

mix

njx

as

xMin Xij: 1 si la tarea i se hace con la máquina j

cij: costo de realizar la tarea i con máquina j

n: tareas

m: máquinas

Si hay más máquinas que tareas se formula

con desigualdades, y se resuelve con tareas

ficticias



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.

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

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

I II III IV V

A 5 3 7 3 4

B 5 6 12 7 8

C 2 8 3 4 5

D 9 6 10 5 6

E 3 2 1 4 5

I II III IV V

A 3 1 6 0 0

B 3 4 11 4 4

C 0 6 2 1 1

D 7 4 9 2 2

E 1 0 0 1 1

I II III IV V

A 3 1 6 0 0

B 0 1 8 1 1

C 0 6 2 1 1

D 5 2 7 0 0

E 1 0 0 1 1



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

Se observa que r = 5 = m =5, por consiguiente se ha llegado al óptimo

6. Determinamos la asignación óptima

I II III IV V

A 3 1 6 0 0 2

B 0 1 8 1 1 1

C 0 6 2 1 1 1

D 5 2 7 0 0 2

E 1 0 0 1 1 2

2 1 1 2 2

I II III IV V

A 3 0 5 0 0 3

B 0 0 7 1 1 2 1

C 0 5 1 1 1 1

D 5 1 6 0 0 2

E 2 0 0 2 2 2

2 3 1 2 2

2 1 1

1



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

I II III IV V

A 3 0 5 0 0 3

B 0 0 7 1 1 2

C 0 5 1 1 1 1

D 5 1 6 0 0 2

E 2 0 0 2 2 2

2 3 1 2 2

0

0 0

0 0

0

0



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

El WinQsb le ofrecerá entonces una ventana con la respuesta

óptima del problema, indicando cuántas unidades enviar desde cada una

de las ciudades de origen a cada una de las ciudades de destino, con su

costo por envío y el costo total de la operación.

Si se usa éste icono, el WinQsb nos ilustrará mediante una red la respectiva

respuesta óptima al problema.

Observe que en éste 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.

A continuación se ilustra el mismo problema; Pero

bajo el software del INVOP (Investigación de

Operaciones), Software creado por Beatriz Loubet y Sandra Segurade la Facultad

de Ciencias Económicas de la Universidad del Cuyo en Argentina; El software

está hecho en lenguaje Delphi y puede ser adquirido gratuitamente dela

siguientes direcciones en internet:

http//members.tripod.com/~operativa www.cui.edu.co/industrial/SOF01.html

Software INVOP

Este software maneja las siguientes aplicaciones: Asignaciones, Transporte,

Distancias en redes (Ruta más corta, Árbol de mínimo recorrido, Agente viajero),

http://members.tripod.com/~operativa

http://members.tripod.com/~operativa

http://www.cui.edu.co/industrial/SOF01.html



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.

El Invop presenta una ventana principal, en la que hace una breve, pero útil

reseña de sus aplicaciones, de ellas seleccionamos la de transporte, como se

muestra en la figura siguiente:

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. En

la figura siguiente se ilustra ésta ventana.

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.

RESOLUCIÓN DE UN PROBLEMA DE ASIGNACIÓN MEDIANTE WINQSB -

NETWORK MODELING

La facilidad de resolver un problema de asignación mediante WinQSB es aún

mayor a la que se incurre mediante programación lineal, y esta metodología

justifica el pensar en que el método húngaro es sumamente anacrónico

http://www.ingenieriaindustrialonline.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/programaci%C3%B3n-lineal/



únicamente contemplado para fines históricos y académicos. En el módulo

NETWORK MODELING del paquete de herramientas WinQSB se puede resolver

el modelo tan solo traspasando los costos de una matriz n*m a otra que brinda el

módulo n*m.

INGRESANDO LOS DATOS A WINQSB - NETWORK MODELING

RESULTADOS OBTENIDOS MEDIANTE WINQSB - NETWORK MODELING

Por ende la asignación que representa el menor costo para la jornada de

mantenimiento preventivo determina que el Equipo 1 realice el mantenimiento de

la Máquina 1, el Equipo 2 realice el mantenimiento de la Máquina 3 y el Equipo 3

realice el mantenimiento de la Máquina 2, jornada que tendrá un costo total de 17

unidades monetarias.

De esta manera se hace evidente cual es la alternativa predilecta para resolver

problemas de asignación.

Bibliografía

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.

Direcciones electrónicas:

http://www.monografias.com/trabajos6/proli/proli.shtml#Bibliograf%C3%ADa

http://www.monografias.com/trabajos11/travent/travent.shtml

http://www.monografias.com/trabajos4/refrec/refrec.shtml

http://www.monografias.com/trabajos13/discurso/discurso.shtml

http://www.monografias.com/trabajos36/administracion-y-gerencia/administracion-y-gerencia.shtml

http://www.monografias.com/trabajos14/dinamica-grupos/dinamica-grupos.shtml

http://www.monografias.com/trabajos6/proli/proli.shtml#Bibliograf%C3%ADa



www.ditutor.com/programacion_lineal/programacion_lineal.html

www.programacionlineal.net/

www.vitutor.com/algebra/pl/a_1.htm

www.vitutor.com/algebra/pl/a_3.html

http://www.ditutor.com/programacion_lineal/programacion_lineal.html

http://www.programacionlineal.net/

http://www.vitutor.com/algebra/pl/a_1.htm

http://www.vitutor.com/algebra/pl/a_3.html

Date post:	06-Jul-2015
Category:	Education
Upload:	angel-ramos-aparicio
View:	1,302 times
Download:	67 times

Unidad 3 algoritmos especiales de programacion lineal

Education