[Escribir texto]

MÉTODO ALGEBRÁICO

Introducción

El método algebraico es muy dispendioso, en razón a que trabaja con todos los

datos de las ecuaciones, para mejorar éste aspecto se creó el método simplex

cuya gran virtud es su sencillez, método muy práctico, ya que solo trabaja con

los coeficientes de la función objetivo y de las restricciones. Ilustraremos su

funcionamiento mediante un ejemplo, pero previamente mostraremos las reglas

de decisión para determinar la variable que entra, la que sale, la gran M, y cómo

determinar que estamos en el óptimo; Todas éstas reglas de decisión fueron

deducidas del método algebraico, solamente que aquí se han acomodado para

ser usadas en el tipo de tablero simplex que se usará.

Criterio de decisión Maximizar Minimizar

Gran M en la función

objetivo

- MXj +MXj

Variable que entra La más negativa de los Zj -

Cj

La más positiva de los Zj -

Cj

Variable que sale

La menos positiva de los b/a

,

Siendo a > 0 , de lo contrario

no restringe

La menos positiva de los b/a

,

Siendo a > 0 , de lo contrario

no restringe a la variable

que entra

Solución óptima Cuando todos los Zj – Cj > 0 Cuando todos los Zj – Cj < 0

Adicionalmente se presentan las siguientes notas a tener en cuanta:

• Si en el tablero simplex de la solución óptima queda al menos una variable de Super

avit ó artificial dentro de las variables básicas, con un valor > 0 , el problema no

tiene solución, esto quiere decir que al menos existen dos restricciones

excluyentes, por lo tanto no existe área de soluciones factible y menos una

solución , en éste caso se debe revisar la formulación del problema.

• Si al escoger la variable que sale, ninguna de las variables básicas restringe el

crecimiento de la variable no básica escogida para entrar, el problema tiene

solución indeterminada y se debe revisar la formulación en busca de una nueva

restricción que no se tuvo en cuenta en la formulación inicial.

• Si en el tablero simplex del óptimo, al menos una de las variables no básicas tiene

coeficiente cero (0) en la función objetivo, esto es su Zj – Cj = 0, el problema

[Escribir texto]

tiene múltiples soluciones y se nos está ofreciendo una de ellas.

Ejemplo 1 Maximizar Z = X1 + X2

C.S.R.

5X1 + 3X2 < 15

3X1 + 5X2 < 15

Xj > 0 ; j = 1, 2

Todo problema de programación

lineal que se formule de la forma

Maximice, con todas sus

restricciones < y con la condición

de no negatividad, se le llama

Forma Estándar ó Forma

Normal

Aquí, al igual que en el método algebraico, debemos conseguir una solución básica factible, empleando las variables de holgura y/o artificiales, quedando el sistema de ecuaciones así:

Maximizar Z = X1 + X2

C.S.R.

5X1 + 3X2 + X3 = 15

3X1 + 5X2 + X4 = 15

Xj > 0 ; j = 1,2,3,4

Las variables básicas son X3 y X4 y

por su puesto en la función

objetivo Z.

.

A continuación construimos la siguiente tabla:

C

j →

1 1 0 0 b/

a

↓

V.

B. b X1 X2 X3 X4

0 X3 15 5 3 1 0

0 X4 15 3 5 0 1

Zj - Cj 0 -1 -1 0 0

El valor de la función objetiva Z, se encuentra frente a la casilla de Zj – Cj , en éste

caso vale cero (0) y se calcula multiplicando el vector fila (en la tabla es la columna

inmediatamente anterior a la de las variables básica V.B.) que contiene los

coeficientes de las variables básicas en la función objetiva original por el vector

columna de los términos independientes b

CXB = Vector fila de los coeficientes en la función objetivo original de las variables

[Escribir texto]

básicas actuales, sus valores se encuentran en la primera columna del tablero.

b = Vector columna de los términos independientes de las restricciones, que al mismo

tiempo son los valores de las variables básicas actuales, sus valores se encuentran

bajo la columna denominada

El valor de los Zj – Cj se calcula multiplicado el vector fila CxB por el vector apuntador aj de la columna de la variable j-ésima, menos el Cj, esto es:

Recuerde que la columna de b/a se calcula, siempre y cuando el denominador sea a > 0 ; de lo

contrario la variable básica respectiva no restringe el valor de la variable escogida para entrar, los

[Escribir texto]

valores de a, están en el respectivo vector apuntador de la variable j-ésima escogida para

entrar, en ésta iteración son 5 y 3 y el cálculo respectivo 15/5 = 3 y 15/3 = 5; Lo que

significa que la variable básica X3 restringe el crecimiento de la variable que entra X1

hasta 3 (no la deja tomar valores superiores a 3) y la variable básica X4 restringe el

crecimiento de la variable que entra X1 hasta 5 (no la deja tomar valores superiores a

5). Por supuesto la variable básica que restringe más el crecimiento de la variable que

entra X1 es X3 por lo tanto es la variable básica escogida para salir.

La fila de la variable básica escogida para salir se divide por el elemento que se

encuentra en la intersección de dicha fila con la columna de la variable que entra, la

fila resultante es la fila pivote y se coloca en un nuevo tablero, desde el que se suman

múltiplos de la fila pivote a las demás filas del tablero anterior de tal forma que se

eliminen de cada una de ellas la variable escogida para entrar, en nuestro caso X1 ,

este procedimiento se denomina, hacer un uno (1) en la intersección y el resto de la

columna ceros (0), por lo tanto en dicha columna aparecerá un vector unitario, el

procedimiento se repite en cada iteración, hasta que todos los Zj – Cj sean mayores ó

iguales a cero en el caso de maximizar ó menores ó iguales a cero en el caso de

minimizar.

A continuación se muestran todas las iteraciones y en cada fila los valores por los

cuales fueron multiplicadas para ser sumadas a otras filas, ello se expresa como sumar

múltiplos de una fila a otra.

Fíjese que se suman múltiplos de las restricciones a la función objetivo para eliminar

las variables básicas de ella.

Conclusiones:

• La solución es única: X1*

= 15/8 ; X2*

= 15/8 ; Z* = 14/4

• El método simplex es más práctico que el método algebraico

[Escribir texto]

Ejemplo 2

Minimizar Z = 6X1 + 4X2 + 2X3

C.S.R.

6X1 + 2X2 + 6X3 > 6

6X1 + 4X2 = 12

2X1 - 2X2 < 2

Ejemplo 3

Aquí, se muestra el método simplex aplicado al ejemplo 3 del capítulo de método

algebraico.

Minimizar Z = 10X2 + 30X3 + 40X4 + 10X5 + 20X7

C.S.R. = Con las siguientes restricciones:

[Escribir texto]

3X1 + 2X2 + X6 + X7 = 5.000

2X4 + X5 + X6 = 15.000

X2 +3X3 + 2X5 + X6 + 2X7 = 5.000

Xj > 0 ; j = 1,2,3,4,5,6,7

Adicionando las variables artificiales necesarias para obtener una solución básica

factible, el problema queda expresado de la siguiente forma:

Min Z = 10X2 + 30X3 + 40X4 + 10X5 + 20X7 + MX8 + MX9 + MX10

C.S.R.

3X1 + 2X2 + X6 + X7 + X8 = 5.000

2X4 + X5 + X6 + X9 = 15.000

X2 + 3X3 + 2X5 + X6 + 2X7 + X10 = 5.000

Xj > 0 ; j = 1,2,3,4,5,6,7,8,9,10

Variables básicas X8 , X9 y X10

[Escribir texto]

Solución:

Variables de Decisión: X1* = X2* = X3* = X5* = X7* = 0 ; X4* = X6* = 5.000 ; Z* = 200.000

Variables Artificiales: X8* = X9* = X10* = 0

Interpretación: Para que hallar un mínimo de desperdicio de 200.000 cm de lámina y cumplir exactamente con los pedidos, hay que cortar 5.000 láminas de la forma 4 y 5.000 láminas de la forma 6

Ejemplo 4

En este ejemplo se muestra cómo resolver un problema en donde no todas las

variables deben cumplir la condición de no negatividad, dicho de otra manera, con

variables irrestrictas. Aquí el secreto consiste en reemplazar cada una de las

variables irrestrictas por la diferencia de dos variables que si deban cumplir la

condición de no negatividad.

Maximizar Z = 4X1 + 5X2 + 2X3 – X4

C.S.R.

X1 + X2 + 2X3 – X4 > 1

2X1 + 2X2 - 3X3 + X4 < 3

X1 + 4X2 + 3X3 + 2X4 < 5

Xj > 0 ; j = 1, 2, 4

[Escribir texto]

Aquí X3 tiene libertad en el signo, esto es puede tomar valores positivos ó negativos.

Hacemos X3 = K – W , en donde K y W deben ser positivas, K > 0 y W > 0

Fíjese que si K > W => X3 será positiva, si K = W => X3 será igual a cero (0) y si K < W =>

X3 será negativa.

Lo que hemos conseguido es convertir un problema que es irrestricto en su variable X3

en uno que es restringido en todas sus variables, el problema queda así:

Maximizar Z = 4X1 + 5X2 + 2K – 2W – X4

C.S.R.

X1 + X2 + 2K –2W – X4 > 1

2X1 + 2X2 - 3K + 3W + X4 < 3

X1 + 4X2 + 3K – 3W + 2X4 < 5

Xj > 0 ; j = 1, 2, 4 ; K > 0 ; W > 0

Fíjese que este problema, es uno clásico de

programación lineal y procedemos a

resolverlo empleando el método simplex,

para lo que adicionamos las variables de

holgura y artificiales que sean necesarias

para conseguir la solución básica factible.

Maximizar Z = 4X1 + 5X2 + 2K – 2W – X4 – MX6

C.S.R.

X1 + X2 + 2K – 2W – X4 – X5 + X6 = 1

2X1 + 2X2 - 3K + 3W + X4 X7 = 3

X1 + 4X2 + 3K – 3W + 2X4 +X8 < 5

Xj > 0 ; j = 1, 2, 4 ; K > 0 ; W > 0

Aquí las variables básicas son:

X6, X7, y X8

[Escribir texto]

Aquí todos los Zj – Cj son > 0 , entonces estamos en la solución óptima.

La solución, mostrando las variables clasificadas es:

[Escribir texto]

Ejemplo 6

Solución al problema número 4) El problema de los paquetes de tuercas, del capítulo 2,

formulación.

[Escribir texto]

[Escribir texto]

Conclusión

[Escribir texto]

El método simplex es más práctico que el método algebraico, pero para problemas de

un gran número de variables y restricciones, fácilmente se vuelve dispendioso por el

número de iteraciones y por supuesto demorado para obtener la solución óptima, es

aquí donde el uso del computador se hace indispensable y útil en términos de

eficiencia, para ello existe el software adecuado, los más conocidos son:

• Winqsb de Yih-Long Chang, distribuido por John Wiley & Sons. Inc N.Y.

• Solver de Frontline Systems Inc. , que viene integrado con el Excel de Microsoft.

• Lindo de Lindo Systems Inc. Que viene integrado con Visicalc.

• El AD, Ayuda a la decisión de la Universidad Cienfuegos de Cuba.