una aplicación de programación lineal

Indice general

0.1. Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.2. Definiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.3. Teoremas Importantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20.4. Una introduccion al metodo simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20.5. Descripcion del Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30.6. Modelamiento del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40.7. Solucion del Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50.8. Codigo Python del programa a utilizar . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60.9. Solucion del problema con el programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1

2 INDICE GENERAL

0.1. Introduccion

El metodo simplex es un metodo analıtico de solucion de problemas de programacion lineal capaz deresolver modelos mas complejos que los resultados mediante metodo grafico sin restriccion en el numerode variables.El metodo simplex es un metodo iterativo que permite ir mejorando la solucion en cada paso. Larazon matematica de esta mejora radica en que el metodo consiste en caminar del vertice de un poliedroa un vertice vecino de manera que aumente o disminuya (segun la funcion objetivo) dado que el numerode vertices que presenta un poliedro solucion es finito siempre se hallara solucion.

0.2. Definiciones

Iteracion: Acto de repetir un proceso con el fin de alcanzar una meta objetivo o resultado.Antes de empezar a discutir el metodo simplex en cualquiera de sus formas recordemos que cualquierproblema puede ser llevado a su forma estandar compacta.

(PL) min ctx

Ax = bx ≥ 0

Donde son dados c∈Rn, b∈Rm, A∈Rm×n con m≤n. En la funcion objetivo ctx, la variable x se leconoce como variable de decision y c como vector de costos. Ası el conjunto de restriccionesP = {x/Ax = b, x≥0} es un poliedro cerrado y se llama conjunto factible. La matriz A se conocecomo la matriz de coeficientes tecnicos y b como el vector de recursos. Donde se maximiza o seminimiza el objetivo, las restricciones son igualdades y las variables son no negativas. Caso contrarioprocedemos de la siguiente manera:

Si una restriccion es de la forma ai1x1 + ai2x2 + · · ·+ ainxn≤bi convertirlo en una restriccion deigualdad mediante la adicion de una variable de holgura no negativa si la restriccion resultantees ai1x1 + ai2x2 + · · ·+ ainxn + si=bi donde si≥0.

Si la restriccion es de la forma ai1x1 + ai2x2 + · · ·+ ainxn≥bi convertirlo en una restriccion deigualdad restando una variable excedente no negativa si la restriccion resultante esai1x1 + ai2x2 + · · ·+ ainxn − si=bi donde si≥0.

Si alguna de las variables xj es irrestricta en signo, reemplazarlo por la x′j − x′′

j donde x′j≥0 y

x′′j≥0.

0.3. Teoremas Importantes

1. Sea P = {x/Ax = b;x≥0} y sea x∈P , entonces x es punto extremo de P ⇐⇒ x es solucion factiblebasica asociada a alguna base B de A.

2. Si el vector de costos relativos o reducidos es no negativo (Ct≥0) entonces la solucion basica

factible asociada a dicha base es optima.

0.4. UNA INTRODUCCION AL METODO SIMPLEX 3

0.4. Una introduccion al metodo simplex

Una propiedad general del metodo simplex es que resuelve la programacion lineal en iteraciones ası cadaiteracion desplaza la solucion a un nuevo punto esquina que tiene potencial de mejorar la funcion objetivoel proceso termina cuando ya no se puedan realizar mejoras.El metodo simplex implica calculos tediosos y voluminosos lo que hace que la computadora sea unaherramienta esencial para resolver los problemas de programacion lineal por consiguiente las reglascomputacionales del metodo simplex se adaptan para facilitar el calculo automatico. Si tenemos elsiguiente problema expresado en forma compacta:

(PL) min ctx

Ax = bx ≥ 0

Ahora supongamos que A es de rango m, entonces admite una representacion en la forma A = [B|N ]

con B∈Rn×n invertible consecuencia de esto tenemos lo siguiente: X =

(XB

XN

)y C =

(CB

CN

)ahora

desarrollando Ax = [B|N ]

[XB

XN

]=BXB+NXN = b=⇒XB = B−1b−B−1NXN De esto a las variables

del vector XB se les denomina variables basicas y a las del vector XN se les denomina no basicas.A la matriz B invertible se le denomina base y si por ultimo se cumple B−1b≥0, se dice base factible.Luego podemos reformular nuestro problema a resolver como sigue:

(PL) min CBtXB + CN

tXN

BXB+ NXN = bXB ≥ 0XN ≥ 0

Ahora si reemplazamos XB en la funcion objetivo tenemos:

(PL) min CBt(B−1b−B−1NXN + CN

tXN)

XB+ B−1NXN = B−1bXB ≥ 0XN ≥ 0

Por ultimo:

(PL) min CBtB−1b+ (CN

t − CBtB−1N)XN

XB+ B−1NXN = B−1bXB ≥ 0XN ≥ 0

4 INDICE GENERAL

La funcion objetivo generalZ(X) = CB

tXB + CNtXN

Coincide con:Z(XN) = CB

tB−1b+ (CNt − CB

tB−1N)XN

para ∀x∈P . Ası para minimizar Z(X) es equivalente a minimizar Z(XN) y se obtiene que el punto

extremo X =

(B−1b0

)es optimo cuando CN

t − CBtB−1N≥0 puesto que

Z(X) = CBtXB + CN

tXN = CBtB−1b≤CB

tB−1b+ (CNt − CB

tB−1N)XN

para todo XN≥0.Usaremos las siguientes notaciones:

1. πt = B−1b sera denominado vector de multiplicadores.

2. CNt= CN

t − CBtB−1N sera el costo a reducir.

0.5. Descripcion del Problema

La fabrica de juguetes TOYS KIDS produce 6 juguetes a partir de 6 materias primas, cada uno caracte-rizado por una diferente combinacion de estas materias primas, la tabla adjunta muestra le beneficio porunidad de producto que se produzca .Como debe realizarse la produccion para maximizar el beneficiototal usando solo el actual inventario de materia prima? .

Producto Skaters Esquiador Super-Heroe Futbolista Bombera Playa InventarioAcero 1 4 − 4 2 − 800Madera 4 5 3 − 1 − 1160Plastico − 3 8 − 1 − 1780Goma 2 − 1 2 1 5 1050Vidrio 2 4 2 2 2 4 1360Pintura 1 4 1 4 3 4 1240Beneficio 30 45 24 26 24 30 −

0.6. Modelamiento del problema

En este modelo estan planteadas todas las configuraciones posibles que equivalen a cada juguete, portanto consideraremos las siguientes variables..

Primero identifiquemos las variables a usar:

x1 := Cantidad unidades de skaters.

x2 := Cantidad unidades de esquiadores.

x3 := Cantidad unidades de super-heroes.

0.6. MODELAMIENTO DEL PROBLEMA 5

x4 := Cantidad unidades de futbolistas.

x5 := Cantidad unidades de bomberos.

x6 := Cantidad unidades de playas.

Entonces el problema a maximizar quedara planteado de la siguiente manera:

max{30x1 + 45x2 + 24x3 + 26x4 + 24x5 + 30x6} ,

Modelando las restricciones, se tendra:

Para la primera restriccion:

x1 + 4x2 + x4 + 2x5 ≤ 800

Para la segunda restriccion:

4x1 + 5x2 + 3x3 + x5 ≤ 1160

Para la tercera restriccion:3x2 + 8x3 + x5 ≤ 1780

Para la cuarta restriccion:

2x1 + x3 + 2x4 + x5 + 5x6≤1050

Para la quinta restriccion:

2x1 + 4x2 + 2x3 + 2x4 + 2x5 + 4x6≤1360

Para la sexta restriccion:

x1 + 4x2 + x3 + 4x4 + 3x5 + 5x6≤1240

Con todo esto, el problema de programacion lineal sera:

max{30x1 + 45x2 + 24x3 + 26x4 + 24x5 + 30x6}

x1 + 4x2 + x4 + 2x5 ≤ 8004x1 + 5x2 + 3x3 + x5 ≤ 1160

3x2 + 8x3 + x5 ≤ 17802x1 + x3 + 2x4 + x5 + 5x6≤1050

2x1 + 4x2 + 2x3 + 2x4 + 2x5 + 4x6≤1360x1 + 4x2 + x3 + 4x4 + 3x5 + 5x6≤1240

6 INDICE GENERAL

0.7. Solucion del Problema

Pasamos el problema a su forma estandar, anadiendo las respectivas variables de holgura.

La restriccion 1 tiene la forma ≤ ası que se agrega la variable de holgura X7.






Teniendo lo siguiente:

max{30x1 + 45x2 + 24x3 + 26x4 + 24x5 + 30x6}

x1 + 4x2 + 0x3 + x4 + 2x5 + 0x6 + 1x7 + 0x8 + 0x9 + 0x10 + 0x11 + 0x12 = 8004x1 + 5x2 + 3x3 + 0x4 + x5 + 0x6 + 0x7 + 1x8 + 0x9 + 0x10 + 0x11 + 0x12 = 11603x2 + 0x2 + 8x3 + 0x4 + x5 + 0x6 + 0x7 + 0x8 + 1x9 + 0x10 + 0x11 + 0x12 = 17802x1 + 0x2 + x3 + 2x4 + x5 + 5x6 + 0x7 + 0x8 + 0x9 + x10 + 0x11 + 0x12 = 10502x1 + 4x2 + 2x3 + 2x4 + 2x5 + 4x6 + 0x7 + 0x8 + 0x9 + 0x10 + x11 + 0x12 = 1360x1 + 4x2 + x3 + 4x4 + 3x5 + 4x6 + 0x7 + 0x8 + 0x9 + 0x10 + 0x11 + x12 = 1240

x1, x2, x3, x4, x5, x6≥0

0.8. Codigo Python del programa a utilizar

Trabajaremos con el metodo de la inversa explıcita

from numpy import *

from sys import exit

def ingresa_matriz(n,m):

### Ingreso de datos de la matriz A

print "Ingrese los elementos de la matriz A fila por fila con un espacio luego enter"

A = [[0.0]*m for i in range(n)]

aux = [[0.0]*m for i in range(n)]

for i in range(n):

temp = raw_input()

A[i] = temp.split()

for j in range(m):

A[i][j] = float((A[i][j]))

0.8. CODIGO PYTHON DEL PROGRAMA A UTILIZAR 7

if A == aux:

exit(’Matriz nula, vuelva a escribir la matriz’)

return A

def ingresa_vec_objetivo(M):

### Ingreso de datos del vector objetivo (C)

n=len(M[0])

print ’Ingrese los’,n,’elementos del vector objetivo de forma horizontal ’

temp=raw_input()

corta=temp.split()

c=[]

for i in range(n):

c.append(float((corta[i])))

return c

def ingresa_vector(M):

### Ingreso de datos del vector independiente (b)

n = len(M)

print ’Ingrese los ’,n,’ elementos del vector b de forma vertical’

b=[]

for i in range(n):

b.append([0])

for i in range(n):

b[i][0]=float((raw_input()))

return b

### Para calcular la inversa de una matriz A

### from numpy import *

### Inversa=linalg.inv(A)

### y la puedes usar con tus funciones

def escoge_columna(A,h,n):

b=[] ### "n" es numero de filas de la Matriz A

for i in range(n): ### devolvera la columna "h-1" de la matriz A

b.append([0])

for i in range(n):

b[i][0]=float((A[i][h-1]))

return b

def elige_h(c,m):

8 INDICE GENERAL

### Te devuelve la posicion "i" del vector C para que entre la columna h=i de C

### la columna que entrara sera "h-1"

### en la posicion "r" de B (otra funcion hallara eso)

h=0

for i in range (m):

if (c[i]<0):

h=i

return h+1

def elige_r(b,a,n):

### Devuelve la posicion "i" en la cual b[i][0]/a[i][0] es el mınimo

### La posicion "r" que se necesitara sera el "i"

minimo=float(b[0][0])/float(a[0][0])

r=0

for i in range (n):

if (a[i][0]>0):

if (float(b[i][0])/float(a[i][0])<minimo):

r=i

return r+1

def cambia_columna(A,B,r,h,n):

### Reemplaza la columna "r" de B por la columna "h" de A

for i in range (n):

temp=float((A[i][h-1]))

B[i][r-1]=temp

return B

def vector_c_basico(Cb,c,r,h):

### Devolvera la parte basica del vector Cb

###intercambiando el elemento de la posicion "r" de "c"

### por el elemento de la posicion "h" en C

### Retornara un vector de dimension 1 x n, siendo n la dimension de la matriz basica

c[r-1]=float((Cb[h-1]))

return c

print ’ *********************************************************’

print ’ Algoritmo Simplex - Metodo de las Inversas Explıcitas’

print ’ *********************************************************’

print ’Ingrese la Matriz A ’

print ’------------------- ’

0.8. CODIGO PYTHON DEL PROGRAMA A UTILIZAR 9

n = int(input("Ingrese el numero de filas: "))

m = int(input("Ingrese el numero de columnas: "))

A=ingresa_matriz(n,m)

print ’Ingrese el vector b ’

print ’-------------------’

b=ingresa_vector(A)

print ’Ingrese el vector C ’

print ’-------------------’

Cb=ingresa_vec_objetivo(A)

h=0

r=0

c=[0,0,0,0]

no_acotado=False

optimo=False

B=[[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]

while (optimo==False and no_acotado==False):

Bi=matrix(B).I### Binv es ela inversa de B

print Bi

Ut = dot(c,Bi) ### producto de las matrices

print "Ut :",Ut

UtA=dot(Ut,A) ### producto de las matrices

print "UtA: ",UtA

Ct=Cb-UtA

tempCt=Ct.T ### transpuesta de Ct para poder comparar los valores

print "Ct: ",Ct

condicion1=True

for i in range (m):

if(tempCt[i]<0):

condicion1=False

break

if (condicion1==True):

optimo=True

print optimo

10 INDICE GENERAL

else:

h=elige_h(tempCt,m) ### se elige la posicion ’h’

###de los Cb[i], el primero que sea <0

print "h: ",h

br=dot(Bi,b) ### producto de las matrices

print "br: ",br

ah=escoge_columna(A,h,n) ### escoge la columna ’h’ de A,

###devuelve un vector columna

###ah=matrix(ah)

print "ah: ",ah

ahr=dot(Bi,ah) ### producto de matrices

print "ahr: ",ahr

print Bi

condicion2=True

for i in range (len(ahr[0])):

if(ahr[i]>0):

condicion2=False

break

if (condicion2==True):

no_acotado=True

else:

r=elige_r(br,ahr,n) ### se elige la posicion ’r’

entre el minimo de los br[i]/ahr[i]###

print "r: ",r

B=cambia_columna(A,B,r,h,n)

print B

temp=float((Cb[h-1]))

c[r-1]=temp

print ""

print ""

print array(B)

print ""

print ""

print B

print Ct

0.9. SOLUCION DEL PROBLEMA CON EL PROGRAMA 11

print no_acotado

print optimo

0.9. Solucion del problema con el programa

una aplicación de programación lineal

Documents