Date post: | 27-Jul-2015 |
Category: |
Education |
Upload: | diego-gomez |
View: | 1,560 times |
Download: | 2 times |
1
Soluciones enteras en un problema de programación lineal.- Supongamos que tenemos el siguiente problema.3X1 + 7X2 <= 189X1 + 8X2 <= 25Z = 3X1 + 4X2 Maximizar
La solución es X1=0,7949 X2=2,2308 Z=11,3077
X1=0,7949
X2=2,2308
Z=11,3077
2
3
Trabajaremos primero con X1<=0 y para ello agregaremos una ecuación que así lo diga quedando el problema3X1 + 7X2 <= 189X1 + 8X2 <= 25X1 <= 0Z = 3X1 + 4X2 MaximizarEsto da como resultado lo siguiente: X1=0 X1=0,7949 X2=2,5714 X2=2,2308 Z=10,2857 Z=11,3077 X1=1 X2=2 Z=11
X1<=0
X1>=1
4
Vemos que luego sacamos el X1<=0 y lo cambiamos por X1>=1 y de ahí ya surgió el resultado entero que maximiza el funcional
5
6
7
8
9
Hay otra manera de hacer lo mismo pero a partir de la última tabla del primer simplex, despejando el valor de X1 , haciéndolo <= a 0 y agregando esa ecuación al problema inicial del simplex. Se actúa de la misma manera pero haciendo X1 >= a 1.X1-0,2051 X3+0,1795 X4 = 0,7949X1=0,7949+0,2051 X3-0,1795 X4<=0-0,2051 X3+0,1795 X4 >= 0,7949-2051 X3+1795 X4 >= 7949
10
Resolver de la misma manera el siguiente ejercicio:12X1+4X2+5X3<=369X1+7X2+12X3<=1516X1+12X2+9X3<=17Z=7X1+8X2+9X3 MaximizarX1=0 X2=.8519 X3=.7531 Z=13.5926
X1=0 X2=.8519
X3=.7531
Z=13.5926
X1=1 X2=0
X3=.1111
Z=8
NO POSIBLE
X1=1,0625 X2=0
X3=0
Z=7,4375
X1=0.333 X2=0
X3=1
Z=11.333
X1=0 X2=0
X3=1 Z=9
X2<=0
X2>=1
X3>=1
X3<=0
X1<=0
X1>=0
X1=0.333 X2=0
X3=1
Z=11.333
X1=0.333 X2=0
X3=1
Z=11.333
11
Algoritmo de corte.-2X1+5X2<=173X1+2X2<=10Z=2X1+X2 Maximizar
Al resolver nos da X1=3,333 X2=0 Z=6,6667
12
13
Para tratar de que X1 que vale 10/3 pase a tomar un valor entero, se toma su fila y se opera así:X1+2/3X2+1/3X4=10/3
Escribimos cada coeficiente como la suma de un entero y una fracción positiva entre 0 y 1.x1+(0+2/3)X2+(0+1/3)X4=3+1/3Separamos los enteros de los fraccionariosX1-3=1/3-2/3X2-1/3X4
Para que la parte izquierda sea entera la derecha debe ser menor que 0. Luego1/3-2/3X2-1/3X4<=0 por tanto 2x2+X4>=1
Con las ecuaciones del cuadro anterior más esta última tenemos:11/3X2+X3-2/3X4=31/3X1+2/3X2+1/3X4=10/32X2+4>=1Z=2X1+X2+0X3+0X4 MaximizarQue da como resultadoX1=3, X2=1/2, X3=17/2, X4=X5=0
14
15
16
PROGRAMACIÓN LINEAL BINARIA.- Propongamos el siguiente problema: Se puede hacer una fábrica en A y otra en B. También se podrá construir un almacén pero debe estar en la misma ciudad en que esté la fábrica. A deja un valor actual neto de 9 millones y se debe gastar 6 millones. B deja 5 millones y se gasta 3 millones. C(almacén en A) deja 6 millones y cuesta 5 millones. D(almacén en B) deja 4 millones y cuesta 2 millones.El gasto total debe ser menor a 10 millones.
Si se construye A, X1=1, si no se construye x1=0 Si se construye B, X2=1, si no se construye x2=0 Si se construye C, X3=1, si no se construye x3=0 Si se construye D, X4=1, si no se construye x4=0
La compañía quiere construir solamente un almacén nuevo o ninguno. Para ello se usa la restricción X3+X4<=1
La compañía consideraría la construcción de un almacén en una ciudad sólo si la nueva fábrica va a estar ahí.Eso queda expresado por las ecuacionesX3-X1<=0 ; X4-X2<=0
Entonces el modelo completo de programación binaria queda expresado así:
17
Maximizar Z= 9X1 + 5X2 + 6X3 + 4X4 Sujeto a: 6X1 + 3X2 + 5X3 + 2X4 <= 10
X3 + X4 <= 1 -X1 + X3 <= 0 -X2 +X4 <= 0 Xj <=1 Xj >=0 Xj es entero para j= 1, 2, 3, 4
A continuación va la solución como si el problema no fuera entero binario.
18
Esta es la resolución del problema sin tener en cuenta su calidad de binario
19
Esta es la solución haciendo X1 = 0
20
Esta es la solución haciendo X1=1
21
Esta es la solución haciendo X1=1 y X2=0
22
Esta es la solución haciendo X1=1 y X2=1
23
La solución X1=1, X2=1, X3=1 da sin solución, la solución X1=1, X2=1, X3=0, X4=1 da sin solución. Probaremos con X1=1,X2=1,X3=0, X4=0
24
Como se ve esta es la solución con Z=14