metodo de la gran "M"

Para el caso de minimizar Z=Cx+11W sujeta a las restricciones y penalizando a Zw1-Cw.

*Condicion de introducción de las variables
Restricción > resta
Restricción < suma

Ejemplo:
3x1+5x2>25 -Mw
2x1-4x2<28 +Mw
4x1-3x2=15

EJERCICIO:
U SANDO EL METODO DE LA GRAN M, TABULAR EL SIGUIENTE SISTEMA DE INECUACIONES.
min z = 3x1+5x2
Sujeta a: X1< 4
X2< 6
3x1+2x2> 18

*X1, X2 > 0
* Z= 3x1-5x2

X1 +X3
X2 +X4 =6
3X1+2X2 -X5 = 18

X1 , X2 , X3 , X4 , X5 , > 0


H X1 X2 X3 X4 X5 W1
VECTORES 1 -3 5 0 0 0 M 0 *funcion objetivo
a 0 1 0 1 0 0 0 4
a 0 0 1 0 1 0 0 6
a 0 3 2 0 0 -1 1 18



W= 0
W> 0
Debido a que M es un valor positivo suficientemente grande, la variable A1 se penaliza en la funcios objetivo utilizando – Ma para maximización y +Ma en el caso de minimización.
Solo las restricciones que tengan “<” (lados derechos no negativos) se consideran con solucion basica factible, con posibilidad de iniciar un procedimiento simplex; las restricciones restantes “=” y “>” se debe considerar una variable de holgura, por no tener solucion basica factible.
Pasar a la forma estandar el modelo matematico.
Agregar variable artificial donde no hay variable ni holgura.
Penalizar las variables artificiales en la funcion objetivo asignando coeficiente positivo muy grande “M” Minimizar y Maximizar –“M”.Quitar las “M” de la columna artificial ya teniendo solucion inicial.

1. Se aplica el metodo simples usando el metodo de la gran “M” maximizar Z= 3x1+5x2

X1 < 4
2x2 < 8
3x1+2x2 <> 0

La funcion objetivo se debe penalizar con –Ma1 por ser maximización y para hacer a Z= 0; Z-3X1-5X2+Ma1=0 las restricciones quedaran
X1+M1=4
2x2+M2=12
3x1+2x2+A1=18

BASE Z X1 X2 M1 M2 A1 SOLUCION

Z 1 -3 -5 0 0 11 0
M1 0 1 0 1 0 0 4
M2 0 0 2 0 1 0 12
A1 0 0 2 0 0 1 0


BASE Z X1 X2 M1 M2 A1 SOLUCION


Z 1 0 -2m5 3y3 0 0 -6
X1 0 1 0 1 0 0 4
M2 0 0 2 0 1 0 12
A1 0 0 2 -3 0 1 6


BASE Z X1 X2 M1 M2 A1 SOLUCION


Z 1 0 0 -9/12 0 -3/2 27
X1 0 1 0 1 0 0 4
M2 0 0 0 3 1 1 6
X2 0 0 1 -3/2 0 1/2 3

BASE Z X1 X2 M1 M2 A1 SOLUCION


Z 1 0 0 0 3/2 M+1 36
X1 0 1 0 0 1/3 1/3 2
M1 0 0 0 1 1/3 -1/3 2
X2 0 0 0 0 1/2 1 6


X1 = 2 Z= 3x1+5x2
X2 = 6 Z= 3(2)+5(6)
M1 = 2 Z= 6+30
Z= 36


X1+M1=4 2+2=4
2X2+M2=12 2(6)+0=12
3X1+2X2+A1=18 3(2)+2(6)+0=18

MÉTODO DE LAS DOS FASES

CONSIDERAR:
A) Minimización, se resuelve como se indicador el metodo simples.
B) Maximización, se resuelve como minimización para la primera fase; la segunda fase ya es maximización.


VARIABLE ARTIFICIAL

Donde existe una fase cuyo objetivo es encontrar una solución o verificar un sistema.

Z= CX+MW
Agregar variables artificiales que no tuenen variables de holgura.
Penalizar variables artificiales en la F.O. asignándoles coeficientes grandes:
En minimizar se suma
En maximización se resta -> la penalización
4 .En la F.O. no deben aparecer variables básicas eliminar v. artificiales.
5. Aplicar método simplex.
Nota: Cuando las variables artificiales básicas tienen “igual a cero”, la solución si es factible.


TEORIA DE LA GRAN “M”

Existen problemas de programación lineal, donde el método simples ya conocido es funcional, debido a que los valores de una o mas variables básicas son negativas, y eso que significa que esta violando el principio de no negatividad en las restricciones, para ello, el problema se podrá resolver por otros métodos que son:
A) El método de la gran “M” (PENALIZACION).
B) El método de las dos fases.


EL METODO DE LA GRAN “M”
PENALIZACION

Consiste en modificar el problema original para dar lugar a un nuevo problema agregando una W llamada artificial y se penalizara mediante un costo “M”, de valores grandes y positivos en forma arbitraria , y eso permite que la función objetivo tome valores muy grandes también cuando sea minimización.

Llegara el momento en que W salga de la base en ese momento W=0 y esto indica a ver regresado al problema original, pero si se llega A W>0, entonces el problema no tiene solución.

metodo de transporte

METODO DE TRANSPORTE.
Es una forma del metodo simple y de P.L. para resolver situaciones de ORIGEN DESTINO basandose en el metodo de la esquina noroeste.
EMPRESA $ 1 PROV 1 CLIENTE1 CAP PRODUCC
2 PROV 2 10 K 5K 8K 10 <
3 PROV 3 15 K 13K 14K 15<
4 PROV 4 8 K 7K 10K 13<
Nos da la oferta y la demanda.

EJERCICIO:Supongamos que una empresa transnacional que tiene tres plantas x,w,y,,y,estas surgen de un producto a 7 almacenes Abcdefg que forma parte del grupo empresarial debemos considerar lo relacionado al costo del transporte desde la planta a cada almacen


ORIGEN PLANTA OFERTA ALMACEN DESTINO DEMAN
CAP DE PRODUCCION REQ.V
W 7,000 A 1,000
X 4,000 B 2,000
Y 10,000 C 4,500
D 4,000
E 2,000
F 3,500
G 3,000

A B C D E F G OFERTA

1,000 2,000 4,000
W 6 7 5 4 3 6 5 7000
X 10 5 4 5 4 3 2 4000
Y 4 5 3 6 5 9 4 10,000 1,000
DEMANDA 1,000 2,000 4,500 4,000 2,000 3,500 5,000 21,000 21,500
2,000
0 0 500 500 0 0 0


RUTA DE UNIDADES COSTO X COSTO TOTAL
DISTRIBUCION ENVIADAS UNIDAD MINIMO
W-A 1000 6,7 6,000
W-B 2,000 5 14,000
W-C 4,000 4 20,000
X-C 500 5 2,000
X-D 3,500 6 17,500
Y-D 500 5 3,000
Y-E 2,000 9 10,000
Y-F 3,500 4 31,500
Y-G 3,000 12,000
COSTO TOTAL MINIMO $ 116,000

metodo de transportacion

METODO DE TRANSPORTACION.
EJEMPLO: La compañía azul celeste aplica y vende fertilizante de aplicación general, la compañía aplica fertilizante entre tres plantas distintas y envia el producto final 24 almacenes diferentes ubicados en diversos puntos del pais.
Puesto que en algunas operaciones productivas han existido durante mas tiempo que otras, hay diferentes costos de producción en las distintas plantas.
En la tabla siguiente se representan los costos de producción en $ por tonelada, capacidad para la planta y requerimientos de los cuatro almcenes.

Asi mismo los precios de venta de los productos los cuales debido a que cada almacen opera en forma directa, los precios por tonelada en los respectivos almacenes difieren un poco. El objetivo de los administradores de la compañía es maximizar las utilidades totales para ella deben de considerar ademas los costos de transporte asociados con el envio del producto de una planta determinada a un almacen en especifico.

PLANTA COST .PROD COSTO DE TRANSPORTE CAP. TOTAL
1 $38 23 18 21 25 650
2 $35 21 24 23 18 600
3 $30 28 21 27 23 600
PRECIO 0 62 63 64 64
VIA
DEMANDA 0 300 450 500 500 1850/1850


TONELADA

CT= 23 (300)+18 (350)+24 (100)+23(500)+27(100)+23(500)=
CT= 41.300
CP= 38(300)+38(350)+35(100)+25(500)+30(100)+30(500)=
CP= 63,700
CV= 62(300)+63(350)+63(100)+64(500)+64(100)+64(500)
CV= 117.350
U= CV-CP-CT
U=117,350-63,700-41,300
U= 12,250

METODO DUAL (PRIMAL)
Para cualquier problema de programación lineal (primal), debe tener su metodología (dual); el problema primal puede tener mas restricciones que variables, esto significa la solucion dual, y debe resolverse con nuevas restricciones.

Si el primal se refiere a Maximizar el problema dual sera Minimizar.
Los coeficientes de la funcion objetivo del primal seran los coeficientes del vector de disponibilidad de recursos en el Dual.
Asi, los coeficientes del vector disponibilidad de recursos del problema primal seran los coeficientes de la funcion objetivo (vector, costos de precios, o utilidad) en el problema dual.
Los coeficientes de las restricciones en el primal (transpuesta de la matriz, sera la matriz de los coeficientes en el dual).
Los signos de desigualdad del problema Dualson contrarios a los del problema primal.
Las variables “X” del primal se convierten en nuevas variables “Y” en el Dual.

Considerando el siguiente problema, calcular su modelo PRIMARIO, DUAL.

Sea Max Z= 3x+5y Dual
Minimizar
Restricciones X< 4 P= 4z1+6z2+18z3+10z4
Y<> 3
3x +2y<>5
X+4y<> 0



Donde: x, y > 0

Ponemos los coeficientes disponibilidad en forma de vector columna (matriz), primal.

b= 4 estos se conviertenen vector horizontal o vertical (matriz fila) traspuesta;
6 esto es:
18 b= (4,6,18,10)
10

Hacemos las restricciones del primal en forma de matriz


1 0 1 0
A 0 1 por lo tanto su traspuesta (Dual), sera: A= 0 1
3 2 3 2
1 4 1 4

Al maximizar:
C= (3,5) su matriz traspuesta (Dual) sera: C= 3
5

2.Dado el siguiente modelo Primal,expresra su modelo dual correspondiente.

Max: Z= 3x1+8x2+2x3+4x4
Restricciones:
X1+X2+2x3+3x4 < 5
X1-X2 =-1
X3+X4 > 46
Donde: X1,X2,X3,X4 > 0

Por lo tanto (Dual), Min: G= 5y1-y2 +46y3
Las restricciones quedan:


y1+y2+ > 3
y1-y2 > 8
2 y1 + y3 > 2
3y1 -y3 > -4


Donde: y1, y2, y3 > 0
B= 5
-1 b= (5 -1 46)
46

Entonces el primal sera: y el dual sera:

1 1 2 3 1 1 0
A= 1 -1 0 0 A= 1 -1 0
0 0 1 -1 2 0 1
3 0 -1



Asi el primal queda como: y el dual quedara como:

C= 3 8 2 -4 C= 3
8
2
-4