Caso de minimizacin

Ejemplo:
Min Z= 8X1+7X2+9X3
Sujeto a:
2X1 + X2 + X3 5
X1 + 2X2 + 2X3 6
Siendo X1, X2, X3, no negativas

Paso 1. Convertiremos las desigualdades de las restricciones en igualdades, conforme a la

tabla V.1. En este problema las restricciones son el tipo mayor o igual que () por lo que en
cada una de ellas incorporemos las variables de holgura con coeficiente -1 y una variable
artificial con coeficiente +1, con estas modificaciones las restricciones ser:
2X1 + X2 + X3 H1 +F1 = 5
X1 + 2X2 + 2X3 H2 + F2 = 6

Paso 2. Incluiremos las variables de holgura y artificiales en la ecuacin de la funcin

objetivo con coeficiente cero para H1 y H2, mientras que por su pare F1 y F2 tendrn +M
por tratarse de un problema de minimizacin, con esto la funcin objetivo vendr dada por:
Min Z = 8X1 + 7X2 + 9X3 + 0H1 + 0H2 + MF1 + MF2
Paso 3. Formaremos la primera tabla.
a) Expresaremos las ecuaciones de las restricciones en funcin de sus coeficientes, as
como el regln de variables, para obtener:

8 7 9 0 0 M M
X1 X2 X3 H1 H2 F1 F2
5 2 1 1 -1 0 1 0
6 1 2 2 0 -1 0 1

b) El regln objetivo ya est presente en la tabla anterior con los valores de los
coeficientes de las variables en la funcin objetivo.
c) La primera solucin la daremos con F1 y F2 , pues son las variables que tienen
coeficiente +1 en la parte identidad de la tabla, con esto tendremos:

8 7 9 0 0 M M
X1 X2 X3 H1 H2 F1 F2
M F1 5 2 1 1 -1 0 1 0
M F2 6 1 2 2 0 -1 0 1

d) Ahora generaremos el regln ndice, para este caso de minimizacin la formula (V.I)
se modifica y queda con los signos cambiados en el segundo miembro, es decir:
 Sumatoria de los productos de
El elemento correspondiente
NMERO los elementos de la columna
= a la columna en el regln -
INDICE por el respectivo elemento en
objetivo
la columna objetivo

Al aplicar esta frmula a cada elemento tendremos:

Columna que encabeza X1: Nmero ndice = 8 (MX2 + MX1) = 8 - 3M
Columna que encabeza X2: Nmero ndice = 7 (MX1 + MX2) = 7 - 3M
Columna que encabeza X3: Nmero ndice = 9 (MX1 + MX2) = 9 - 3M
Columna que encabeza H1: Nmero ndice = 0 [ MX (-1) + MX0] = M
Columna que encabeza H2: Nmero ndice = 0 (MX0 + MX(-1) = M
Columna que encabeza F1: Nmero ndice = M (MX2 + MX0) = 0
Columna que encabeza F2: Nmero ndice = M (MX0 + MX1) = 0
Columna de constates: Nmero ndice (utilidad)= 0 (MX2 + MX1) = - 11 M
Al descomponer los nmeros ndice en su parte numrica y de M e incluirlos en la tabla
Simplex, tendremos:

8 7 9 0 0 M M
X1 X2 X3 H1 H2 F1 F2
M F1 5 2 1 1 -1 0 1 0
M F2 6 1 2 2 0 -1 0 1
0 8 7 9 0 0 0 0
-3 -3 -3 1 1 0 0

Aqu hemos omitido el -11M del elemento correspondiente a la columna de constantes.

Esta es una muestra primera solucin, la cual indica:
Variables bsicas Variables no bsicas
F1 = 5 X1 = 0
F2 = 6 X2 = 0
Z =0 H1 = 0
H2 = 0
Como vemos en la taba simplex, esta primera aproximacin no es el ptimo, pues aparecen
nmeros negativos en el regln ndice, por tanto iremos al
Paso 4. Iremos a la siguiente iteracin para mejorar nuestra aproximacin.
a) Para determinar la columna lave, vemos que hay un triple empate por lo seleccionamos
arbitrariamente esa X2:

8 7 9 0 0 M M
X1 X2 X3 H1 H2 F1 F2
M F1 5 2 1 1 -1 0 1 0
M F2 6 1 2 2 0 -1 0 1
0 8 7 9 0 0 0 0
-3 -3 -3 1 1 0 0

b) Calculamos los cocientes de los dos reglones de restricciones :

5
Para el primer regln = 1 = 5
6
Para el segundo regln = 2 = 3

Por lo que este ltimo es el regln de clave, lo cual ya aparece sealado en la tabla anterior.
c) El nmero clave es el 222 que aparece encuadrado en la tabla.
d) Para hacer el numero clave igual a la unidad, dividimos el regln clave entre 2, con eso
quedara de la manera siguiente:
3 0.5 1 1 0 -0.5 0 0.5

e) Cambiaremos de variable sacando a F2 y su contribucin en la zona de solucin, he

introduciendo a X2 y su contribucin. Adems de acuerdo a la metodologa simplex de
dos fases, eliminaremos a la columna de F2 de la tabla.

8 7 9 0 0 M
X1 X2 X3 H1 H2 F1
M F1 5 2 1 1 -1 0 1
7 X2 3 0.5 1 1 0 -0.5 0
0 8 7 9 0 0 0
-3 -3 -3 1 1 0

f) Aremos 0 los elemento de la columna clave con excepcin del numero clave, entonces
tendremos:
Al primer regln le restaremos el regln clave:

5 2 1 1 -1 0 1
(3 0.5 1 1 0 -0.5 0)
2 1.5 0 0 -1 0.5 1

A la parte numrica del regln ndice, le restaremos el regln clave multiplicado por 7:

0 8 7 9 0 0 0
-7 (3 1 1 1 0 -0.5 0)
-21 4.5 0 2 0 3.5 0

A la parte M del regln ndice le sumaremos el regln clave multiplicado por 3:

-3 -3 -3 1 1 0
+3 (0.5 1 1 0 -0.5 0)
-21 0 0 1 -0.5 0

Con estos cambios tala tabla simplex ser ahora:

8 7 9 0 0 M
X1 X2 X3 H1 H2 F1
M F1 2 1.5 0 0 -1 0.5 1
7 X2 3 0.5 1 1 0 -0.5 0
-21 4.5 0 2 0 3.5 0
-1.5 0 0 1 -0.5 0

A cual es nuestra nueva aproximacin

Variables bsicas Variables no bsicas
F1 = 2 X1 = 0
F2 = 3 X3 = 0
Z = 21 H1 = 0
H2 = 0
Aqu debemos de aclarar que Z no es -21 Como aparece en la tabla simplex, sino +21 puesto
que la metodologa simplex nos presenta z con el signo invertido cuando se trata de
problemas de minimizacin.

De esta aproximacin, vemos que no es el ptimo, puesto que an hay nmeros negativos en
el regln ndice, por lo cual aremos repetir el paso 4. Reiniciando con el inciso (a)

a) La columna clave ser ahora la que est encabezada por X1. Puesto que contiene al
nmero ndice ms negativo.

b) Calculando los cocientes tendremos:

2
Para el primer regln = 1.5 = 1.3333
3
Para el segundo regln = 0.5 = 6

Por lo que el regln clave ser el primero

8 7 9 0 0 M
X1 X2 X3 H1 H2 F1
M F1 2 1.5 0 0 -1 0.5 1
7 X2 3 0.5 1 1 0 -0.5 0
-21 4.5 0 2 0 3.5 0
-1.5 0 0 1 -0.5 0

c) El numero clave es el 1.5, pues pertenece al regln y a la columna clave

d) Si dividimos regln clave entre 1.5 este nos quedara;

1.333 3 0 0 -0.667 0.3333 0.667

e) Con el cambio de variable , sale F1 y entra X1, con esto y eliminando de una ves a F1 de
la tabla esta quedara en la siguiente forma :

8 7 9 0 0
X1 X2 X3 H1 H2
8 X1 1.333 1 0 0 -0.667 0.333
7 X2 3 0.5 1 1 0 -0.5
-21 4.5 0 2 0 3.5
-1.5 0 0 1 -0.5
 f) Ahora generaremos ceros en los restantes elementos de la columna clave de la siguiente
manera:

Al segundo regln le restamos el regln clave multiplicando por 0.5:

3 0.5 1 1 0 -0.5
-0.5 (1.333 1 0 0 -0.667 0.333)
2.333 0 1 1 0.333 -0.667

A la parte numrica del regln ndice le restamos el regln clave multiplicando por 4.5:

-21 4.5 0 2 0 3.5

-4.5 (1.333 1 0 0 -0.667 0.333)
-27 0 0 2 3 -0.667

Finalmente a la parte M del regln ndice le sumaremos el regln clave multiplicando por
1.5:

-1.5 0 0 1 -0.5
-1.5 (1 0 0 0.667 0.333
0 0 0 0 0

Con estas modificaciones nuestra tabla es:

8 7 9 0 0
X1 X2 X3 H1 H2
8 X1 1.333 1 0 0 -0.667 0.333
7 X2 2.333 0 1 1 0.333 -0.667
-27 0 0 2 3 2
0 0 0 0 0

Aqu vemos que la parte M del regln ndice desaparece al hacerse cero todos sus
elementos, pues ya no hay ninguna variable artificial en la zona de solucin
Adems en la parte numrica este mismo regln ya no hay nmeros negativos, por lo que
esta aproximacin ha resultado ser el ptimo, con la siguiente solucin
Variables bsicas Variables no bsicas
X1 = 1.333 X3 = 0
X2 = 2.333 H1 = 0
Z = 27 H2 = 0