El Metodo Simplex

EL METODO SIMPLEX

Se entiende por programa lineal aquel que optimiza Z=cX sujeto a AX⋚b y X≥0.
Donde la función lineal Z=cX se llama función objetivo; las desigualdades AX⋚b se llamanrestricciones y a X≥0 se le conoce como condición de no-negatividad. La palabra optimizar puede significar maximizar o minimizar.
En el programa lineal definido arriba se tiene que X es un vector columnacon n componentes. A este valor se le denomina el vector de actividades y sus n componentes son variables. Sea entonces:
X=x1x2xn
Al vector renglón c, también con n componentes (c1, c2, …, cn) sele denomina el vector de precios o costos unitarios. El vector columna b, con m componentes se le denomina el vector de disponibilidad de recursos. El vector 0 es un vector columna de n ceros. Porúltimo la matriz A, con m renglones y n columnas se le denomina la matriz de coeficientes tecnológicos. Cada elemento aij en la matriz A, con i=1,…, m y j=1,…, n representa la cantidad de recursos jque se necesita por unidad de la actividad i.
Puede representarse así:

Opt Z= c1X1+ c2X2+ …+cnXn
Sujeto a:
a11X1+ a12X2+ …+ a1nXn ⋛ b1
a21X1+ a22X2+ …+ a2nXn ⋛ b2
…………………………………………….
am1X1+am2X2+ …+ amnXn ⋛ bm
X1≥0, X2≥0, … , Xn≥0.

Teoremas básicos de la programación lineal:
Se considera la forma canónica
Máx Z=cX
Sujeto a
AX ≤b
X≥0
Donde:
X=x1x2xn, c=(c1, c2, …, cn),b=b1b2bm, 0= 000
Y A es de orden m por n.
Definiciones:
Solución factible: es aquella solución con no más de m componentes positivas.
Solución factible básica no degenerada: es una solución factiblebásica donde exactamente m componentes del vector columna X son positivas.
Solución factible básica degenerada: es una solución factible básica donde hay menos de m componentes positivas del vector X.Región de factibilidad: es el conjunto de todas las soluciones factibles.

Teorema 2.1. El conjunto de todas las soluciones factibles de un programa de programación lineal es un conjunto...