La programación lineal es un conjunto de técnicas racionales de análisis y de resolución de problemas que tiene por objeto ayudar a los responsables en las decisiones sobre asuntos en los que interviene un gran número de variables.

El nombre de programación lineal no procede de la creación de programas de ordenador, sino de un término militar, programar, que significa 'realizar planes o propuestas de tiempo para el entrenamiento, la logística o el despliegue de las unidades de combate'.

El procedimiento es iterativo, pues mejora los resultados de la función objetivo en cada etapa hasta alcanzar la solución buscada. Ésta se encuentra en un vértice del que no parta ninguna arista a lo largo de la cual la función objetivo aumente.

viernes, 8 de octubre de 2010

EJERCICIO 9.7-3

Reconsidere el problema  del flujo de costo mínimo formulado en el problema 9.6.2



Una empresa fabricará el mismo producto nuevo en dos plantas y después lo mandará a dos almacenes. La fabrica 1 puede enviar una cantidad ilimitada por ferrocarril solo al almacén 1 mientras que la fábrica 2 puede mandar una cantidad ilimitada por ferrocarril solo al almacén 2. Sin embargo, se pueden usar camiones de carga independientes para enviar hasta 50 unidades a cada almacén. En la siguiente tabla se muestra el costo unitario de embarque para cada alternativa junto con las cantidades que se producirán en las fábricas y las cantidades que se necesitan en los almacenes.



A) Obtenga una solución BF inicial resolviendo el árbol de expansión factible que corresponde a usar solo las dos vías y la fabrica 1 que demanda unidades al almacén a través del centro de distribución.



A = Fábrica 1

B = Fábrica 2
C = Centro de distribución
D = Almacén1
E  = Almacén2

Maximizar
 Z=7XAD+3XAC+4XCE+9XBE+4XBC+2XCD

S. A.
 XAD + XAC = 80
 XBE = 70
-XAC + XCE = 0
-XAD = -60
-XCE – XBE = -90

Solución:
De ecuación 4 tenemos
-XAD = -60
XAD = 60
Reemplazando en la ecuación 1
XAD + XAC = 80
60 + XAC = 80
XAC = 20
Reemplazando en la ecuación 3
-XAC + XCE = 0
-20 + XCE = 0
XCE = 20
Y de ecuación 2 tenemos que
XBE = 70

Con lo cual, obtenemos una solución BF inicial resolviendo el árbol de expansión factible que corresponde a usar sólo las dos vías y la fábrica 1 que envía unidades al almacén 2 a través del centro de distribución.





B) Use el método simplex de redes (sin usar la rutina de la computadora) para resolver este problema.



Para la solución final hacemos el planteamiento y resolvemos obteniendo el siguiente diagrama, para hallar Z, resolvemos:

Z = 7XAD + 3XAC + 4XCE + 9XBE + 4XBC + 2XCD
Z = 7(30) + 3(50) + 4(50) + 9(40) + 4(30) + 2(30)
Z = 1100




Publicado por en No hay comentarios:

viernes, 1 de octubre de 2010

EJERCICIOI 9-6-4

Makolson es una compañía integrada por completo que produce bienes y los vende en sus propias tiendas. Después de la producción los bienes se colocan en dos almacenes hasta que las tiendas los necesitan. Se usan camiones para transportar los bienes a los almacenes y luego a las tres tiendas. Utilice una carga completa de camión como unidad; la siguiente tabla muestra la producción mensual de cada planta, su costo de transporte por carga enviada a cada almacén y la cantidad máxima que se puede enviar al mes a cada uno.

Para cada tienda (T), la siguiente tabla contiene su demanda mensual, si el costo de transporte por carga desde cada almacén y la cantidad máxima que se puede enviar al mes desde cada uno.
La administración desea determinar un plan  de distribución (numero de cargas enviadas al mes de cada planta a cada almacén y de cada uno de estos a cada tienda) de modo que se minimice el costo total de transporte.

* Trace una red que describa la red de distribución de la compañía. Identifique en ella los nodos fuente, transbordo y demanda.
* Formule este problema como un problema de del flujo de costo mínimo colocando todos los datos necesarios.

*  Resolviendo con Solver





Publicado por en No hay comentarios:

lunes, 13 de septiembre de 2010

EJERCICIO 8

Un contratista tiene que acarrear grava a tres construcciones. Puede comprar hasta 18 toneladas en un foso de grava al norte de  la ciudad y 14 toneladas en uno al sur. Necesita 10, 5 y 10 toneladas en las respectivas construcciones 1, 2 y 3. El precio de compra por tonelada en cada foso y los costos de acarreo son los siguientes:
COSTO/TONELADA ACARREADA
PRECIO/TON
FOSO
1
2
3
NORTE
$ 30
$ 60
$ 50
$ 100
SUR
$ 60
$ 30
$ 40
$ 120

La contratista desea determinar cuánto acarrear de cada foso a cada construcción de manera que se minimice el costo total de compra y acarreo de la grava.


 A) Formule el modelo de programación lineal. Use el método de la M para construir la tabla simplex inicial lista para aplicar el método simplex (pero no lo resuelva).
COSTO/TONELADA ACARREADA
PRECIO/TON.
FOSO
1
2
3
NORTE
$ 30+$100
$ 60+$100
$ 50+$100
$ 100
SUR
$ 60+$120
$ 30+$120
$ 40+$120
$ 120

COSTO/TONELADA ACARREADA

FOSO
1
2
3

NORTE
$ 130
$ 160
$ 150

SUR
$ 180
$ 150
$ 160



COSTO/TONELADA ACARREADA
TONELADAS OFERTA
FOSO
1
2
3
NORTE
$ 130
$ 160
$ 150
18
SUR
$ 180
$ 150
$ 160
14
DEMANDA
10
5
10



Introducimos variables de holgura y se deben introducir variables artificiales (M’s)

Como se desea minimizar z para facilitar las operaciones cambiamos a maximizar –z; entonces:
Luego la tabla resulta:
IT0
ECU
VB
Z
X11
X12
X13
X21
X22
X23
X7
X8
X9
X10
X11
LD
0
z
-1
130
160
150
180
150
160
0
0
M
M
M
0
1
x7
0
1
1
1
0
0
0
1
0
0
0
0
18
2
x8
0
0
0
0
1
1
1
0
1
0
0
0
14
3
x9
0
1
0
0
1
0
0
0
0
1
0
0
10
4
x10
0
0
1
0
0
1
0
0
0
0
1
0
5
5
x11
0
0
0
1
0
0
1
0
0
0
0
1
10

Aplicamos Gauss Jordan:
Operamos:
Y obtenemos:
IT0
ECU
VB
Z
x11
x12
x13
x21
x22
x23
x7
x8
x9
x10
x11
LD

0
z
-1
130-M
160-M
150-M
180-M
150-M
160-M
0
0
0
0
0
 -25M
1
x7
0
1
1
1
0
0
0
1
0
0
0
0
18
2
x8
0
0
0
0
1
1
1
0
1
0
0
0
14
3
x9
0
1
0
0
1
0
0
0
0
1
0
0
10
4
x10
0
0
1
0
0
1
0
0
0
0
1
0
5
5
x11
0
0
0
1
0
0
1
0
0
0
0
1
10

B)  Ahora formule este problema como uno de transporte construyendo la tabla de parámetros adecuada. Compare el tamaño de esta tabla (y de la tabla simplex de transporte correspondiente) usada por el método simplex de transporte, con el tamaño de la tabla simplex del inciso a) necesaria para aplicar el método simplex.














Aquí se debe adicionar una columna ficticia ya que hay la oferta y la demanda no son iguales, por lo tanto se debe hacer un balanceo de las cifras, para ello la fila ficticia

DESTINO
TONELADAS OFERTA
FOSO
1
2
3
4 (F)
NORTE
1
$ 130
$ 160
$ 150
$ 0
18
SUR
2
$ 180
$ 150
$ 160
$ 0
14
DEMANDA
10
5
10
7

La tabla obtenida es más pequeña y menos compleja que la tabla simplex de transporte.








C) El contratista ha observado que puede abastecer por completo las construcciones 1 y 2 del foso norte y la construcción 3 del foso sur. Utilice la prueba de optimalizada (pero no realice iteraciones) del método simplex de transporte para verificar si la solución BF correspondiente es optima.
(0)
DESTINO
TONELADAS
OFERTA
FOSO
1
2
3
4 (F)
Norte
1
$ 130
$ 160
$ 150
$ 0
18
Sur
2
$ 180
$ 150
$ 160
$ 0
14
DEMANDA
10
5
10
7

Asignamos las cantidades demandas en las construcciones 1 y 2 desde el foso norte y a la construcción 3 desde el sur
(0)
DESTINO
TONELADAS
OFERTA
FOSO
1
2
3
4 (F)
Norte
1
$ 130
$ 160
$ 150
$ 0
18
10
5
Sur
2
$ 180
$ 150
$ 160
$ 0
14
10
DEMANDA
10
5
10
7

En la columna ficticia asignamos las cantidades sobrantes

(0)
DESTINO
TONELADAS
OFERTA
U(i)
FOSO
1
2
3
4 (F)
Norte
1
$ 130
$ 160
$ 150
$ 0
18
0
10
5
3

Sur
2
$ 180
$ 150
$ 160
$ 0
14
0
10
4

DEMANDA
10
5
10
7


Creamos fila Vj con los coeficientes de la fila con la mayor asignación, para este caso la fila 1, la cual se le han asignado 15 unidades, la fila dos solo se le ha asignado 10 unidades.
(0)
DESTINO
TONELADAS
OFERTA
U(i)
FOSO
1
2
3
4 (F)
Norte
1
$ 130
$ 160
$ 150
$ 0
18
0
10
5
3

Sur
2
$ 180
$ 150
$ 160
$ 0
14
0
10
4

DEMANDA
10
5
10
7

V(J)
130
160
160
0



Para completar la tabla realizamos:

(0)
DESTINO
TONELADAS
OFERTA
U(i)
FOSO
1
2
3
4 (F)
Norte
1
$ 130
$ 160
$ 150
$ 0
18
0
10
5
-10
3

Sur
2
$ 180
$ 150
$ 160
$ 0
14
0
50
-10
10
4

DEMANDA
10
5
10
7

V(J)
130
160
160
0



Como tenemos coeficientes negativos en la tabla, entonces la solución dada por la contratista no es la óptima.


D) 




Con la regla de la esquina noroeste, use la rutina interactiva del método simplex de transporte para resolver el problema formulado en el inciso b.




  (0)

DESTINO
OFERTA
Ui
FOSO
1
2
3
4 (F)
NORTE
1
$ 130
$ 160


$ 150


$ 0


18




10 










SUR
2
$ 180


$ 150

$ 160

$ 0

14













DEMANDA
10
5
10
7
Vj






Partimos de x11 donde se asignan 10, como sobran 8, estos deben asignarse a las celda siguiente, o sea, x12; los cuales son limitas a 5 por la demanda de la columna y se debe seguir con los 3 restantes a las celda siguiente, repitiendo los pasos sistemáticamente:

  (0)

DESTINO
OFERTA
Ui
FOSO
1
2
3
4 (F)
NORTE
1
$ 130
$ 160


$ 150


$ 0


18
0



10 


5


 3





SUR
2
$ 180


$ 150

$ 160

$ 0

14








7


7



DEMANDA
10
5
10
7
Vj
130
160
150



Resolvemos los Ui Y los Vj y los ubicamos en la tabla:


  (0)

DESTINO
OFERTA
Ui
FOSO
1
2
3
4 (F)
NORTE
1
$ 130
$ 160


$ 150


$ 0


18
0



10 

5


 3





SUR
2
$ 180


$ 150

$ 160

$ 0

14
10







7

7



DEMANDA
10
5
10
7
Vj
130
160
150
-10


Resolvemos los Cij y los ubicamos en la tabla:


 (0)

DESTINO
OFERTA
Ui
FOSO
1
2
3
4 (F)
NORTE
1
$ 130
$ 160


$ 150


$ 0


18
0




10 



5


 3


10



SUR
2
$ 180


$ 150

$ 160


$ 0

14
10



40


-20


7

 

7



DEMANDA
10
5
10
7
Vj
130
160
150
-10


Como resultan coeficientes negativos, debemos volver a iterar, comenzando el más negativo que es el  -20 y está en x22, y el menor positivo de las variables básicas es 5, y pasa a la posición x22, restablecemos valores en Vj con los coeficientes de la fila donde está el mayor negativo.
Hallamos  Ui:


 (1)

DESTINO
OFERTA
Ui
FOSO
1
2
3
4 (F)
NORTE
1
$ 130
$ 160


$ 150


$ 0


18
-10



10 




 3


10



SUR
2
$ 180


$ 150

$ 160

$ 0

14
0



40


5


7


7



DEMANDA
10
5
10
7
Vj
140
150
160



Resolvemos los Cij y los ubicamos en la tabla:

 (1)

DESTINO
OFERTA
Ui
FOSO
1
2
3
4 (F)
NORTE
1
$ 130
$ 160


$ 150


$ 0


18
-10



10 


20


 3


10



SUR
2
$ 180


$ 150

$ 160

$ 0

14
0



40


5


7


7



DEMANDA
10
5
10
7
Vj
140
150
160



Reajustamos las comunas y las filas:
 (1)

DESTINO
OFERTA
Ui
FOSO
1
2
3
4 (F)
NORTE
1
$ 130
$ 160


$ 150


$ 0


18
-10



10 


20


 8


10



SUR
2
$ 180


$ 150

$ 160

$ 0

14
0



40


5


2


7



DEMANDA
10
5
10
7
Vj
140
150
160



Luego hacemos el producto de cada una de las casillas con asignación para obtener:


















































































Publicado por en No hay comentarios:
Suscribirse a: Entradas (Atom)