Metodo simplex

1. Restricciones de Desigualdad

Universidad Nacional de Colombia
Sede Medellín
Medellí

El método
mé
algebraico:
resolver un
conformado
funcionales.

Clase # 6

EL MÉTODO SIMPLEX
MÉ
1.Restricciones de Desigualdad
1.Restricciones
2.Procedimiento algebraico
2.Procedimiento

simplex es un procedimiento
las soluciones se obtienen al
sistema de ecuaciones lineales
a partir delas restricciones

El sistema de ecuaciones lineales se
obtiene al convertir cada desigualdad de
la forma original, en una igualdad
equivalente.

Ejemplo Prototipo: La Wyndor Glass Co.
Co.
6-1

6-2

En el ejemplo de la Wyndor.

1.1 Restricciones del tipo m,
habrá:
habrá

m:

Ejemplo:
Sistema Original

variables básicas
bá

n - m: variables no básicas,
bá
(iguales acero, por definición)
definició
sigue

6-10

(4,3)

Sistema Aumentado
(4,3,0,6,0)
Solución Básica Factible

veamos
6-11

6-12

2

¿Cuántas soluciones en un vértice existen?
Cuá
vé

Ejemplo
sistema original

Sistema aumentado
n

(0,6,4,0,6)

(0,6)

(0,6)

Variables básicas

7
6
5
4

5!

R2

2

0

= 10 soluciones en el
vértice

2!3!

3

1(n)!
m! (n –m)!

n: número de variables
m: número de restricciones funcionales
nú
Ejemplo de la Wyndor: n = 5 y m = 3
Wyndor:
existirán:
existirá

Variables no básicas
R1

10 x
2
9
8

=

m

R3
1

2

3

4

5

6

7

8

9

10
x1

6-13

6-14

EL MÉTODO SIMPLEX
MÉ

Teorema

2. Procedimiento algebráico
algebrá

Dos soluciones básicas factibles sonbá
adyacentes entre sí, si tienen todas las
sí
V.N.B menos 1 comunes.

1. Hallar una solución inicial.
2. Hacer una Prueba de optimalidad.
3. Realizar nueva iteración
3.1 Determinación de la dirección de movimiento:

Ejemplo
(0,0)
(0,0,4,12,18)

Variable que entra a la base: columna pivote

(0,6)

3.2 Determinación de donde detenerse.

(0,6,4,0,6)

Variable que sale de labase: fila pivote

4. Calcular una nueva solución básica factible
4.1 Obtener 1 en la fila pivote
4.2 Obtener 0 en el resto de la columna pivote

Comparten todas las variables no básicas menos una.
6-15

Este sistema de ecuaciones está en la
forma apropiada de la eliminación Gaussiana

1. Hallar una solución inicial (básica factible)
(bá
Seleccionar las variable básicas: las queconforman una matriz identidad, de orden m, en
el
sistema
de
ecuaciones
(coeficientes
tecnológicos)
Asignar el valor de cero a las
restantes: Variables no básicas = 0

(1)

x1

(3)

variables

+ x3
2x2

(2)

3x1 + 2x2

=4
+x4
+x5

= 12
= 18

las v.b están en azul.
Como x1= 0 y
x5= 18

En el ejemplo:
Variables básicas: x3, x4, x5
Variables no básicas: x1= 0 y6-16

x2= 0 , entonces x3= 4 , x4= 12 y

La solución B.F. Inicial es (0,0,4,12,18)

x2= 0.
6-17

6-18

3

3. Iteraciones
3.1 Variable que entra a la base

2. Prueba de optimalidad.

La función objetivo es

Determinación de la dirección de movimiento
Determinació
direcció

Z = 3X1 + 5X2 + 0X3 + 0X4 + 0X5

Z = 3X1 + 5X2

- ¿ Existen tasas de mejoramiento positivas?¿Aumenta X1?

Esto es equivalente a que haya coeficientes negativos en el
renglón (0): Z – 3X1 – 5X2 = 0
Sí hay forma de mejorar

6-19

3.2 Variable que sale de la Base

¿Cuánto aumentar el valor de la v.b entrante X2, antes
de detenerse?

(2)

X4 = 12 - 2X2 ≥ 0

(3)

X5 = 18 - 3X1 - 2X2 ≥ 0

5 > 3 , se elige X2 para aumentar su valor
En este momento X2 es una v.n.b y se seleccionacomo
la variable que entra a la base: X2 (columna pivote)
Para ello se deben ajustar los valores de las demás
variables.
6-20

El método SIMPLEX realiza el anterior análisis
mé
aná
mediante la Prueba del cociente mínimo:
mediante
mí

Puedo aumentar X2 siempre y cuando:
Todas las variables permanezcan no negativas

X3 = 4 - X1 ≥ 0

Tasa de mejoramiento en Z=5

Entonces X2...