MÉTODO SIMPLEX

MÉTODO SIMPLEX

Resuelve la programación lineal en interaciones. Cada interación desplaza la solución a un nuevo punto esquina que tiene potencial de mejorar el valor de la función objetivo.

El método simplex implica cálculos voluminosos y tediosos, por ese motivo se utiliza lo programas de cómputo; pues permiten resolver o facilitar el cálculo automáticamente.

Espacio de soluciones en forma de ecuación

Para estandarizar:

·         Todas la restricciones (excepto las de no negatividad) son ecuaciones con lado derecho no negativo.

·         Todas las variables son no negativas.

Conversión de desigualdades a ecuaciones.

En las desigualdades la diferencia entre el lado derecho y el lado izquierdo de la restricción (≤) representa, por consiguiente, la cantidad no usada u holgura del recurso.

Para convertir una desigualdad en ecuación, se le agrega una variable de holgura al lado izquierdo de la restricción. Si se define s1 como holgura la ecuación se convierte de la siguiente manera:

6x1 + 4x2 + s1 = 24, s1 ≥ 0

La conversión de  (≥) a (=) se logra restando una variable de excedencia del lado izquierdo de la desigualdad. Ejm:

x1 + x2 - s1 = -3, s1 ≥ 0

Lo importante es saber que las variables de holgura y de excedencia, s1 y S1 siempre son no negativas.

El único requisito primordial es que el lado derecho de la ecuación sea no negativo. Esta condición se puede satisfacer siempre, si es necesario multiplicando ambos lados de la ecuación resultante por (-1) ejm:

-x1 + x2 = -3

-x1 + x2 + s1 = -3, s1 ≥ 0(-1)

x1 - x2 - s1 = 3

Existen dos tipo de soluciones:

PRIMAL:

Tiene una forma de:

                                                                             

Paso1: escoger el valor más negativo de las ZJ – CJ, y se llama variable entrante.

Paso2: elegir la mejor división de: LD/entr, y se le llama variable saliente.

Paso3: pasar el pivote a su inversa.

Paso4: los demás valores de la variable saliente se dividen entre el pivote.

Paso5: la columna se divide entre el pivote con el signo cambiado.

Los demás valores restantes:

a	b	c	d	e
f	g	h	i	j
k	l	m	n	ñ
o	p	q	r	s

b = b-

ñ = ñ-

Y así sucesivamente.

Esta forma de resolver las programaciones lineales finaliza cuanla la función objetiva y el lado derecho sean mayores o iguales que 0.

	METODO SIMPLEX PRIMAL
	MAX	4X1+8X2
		3X1+6X2<=12
				4X1+3X2<=12
		4X1+3X2=12
				4X1+3X2>=12	(-1)	-4X1-3X2<=12
		4	8
		X1	X2	LD
0	H1	3	6	12		2
0	H2	4	3	12		4
0	S3	-4	-3	12		-4
	ZJ-CJ	-4	-8	0
		4	0
		X1	H1	LD
8	X2	1/2	1/6	2
0	H2	2   1/2	-   1/2	6
0	S3	-2   1/2	1/2	18
	ZJ-CJ	0	1   1/3	16
	x1=	0
	x2=	2
	z=	16

	METODO SIMPLEX DUAL
	MIN	2X1+3X2+12X3	(-1)	MAX	-2X1-3X2-12X3
		4X1+3X2+X3>=6	(-1)	-4X1-3X2-X3<=-6
		2X1-4X2-3X3<=10
		4X1+0X2+5X3>=8	(-1)	-4X1-0X2-5X3<=-8
		-2	-3	-12
		X1	X2	X3	LD
0	S1	-4	-3	-1	-6
0	H2	2	-4	-3	10
0	S3	-4	0	-5	-8
	ZJ-CJ	2	3	12	0
		0	-3	-12
		S3	X2	X3	LD
0	S1	-1	-3	4	2
0	H2	1/2	-4	-5   1/2	6
-2	X1	-   1/4	0	1   1/4	2
	ZJ-CJ	1/2	3	9   1/2	-4
		x1=
		x2=
		z=