ClubEnsayos.com - Ensayos de Calidad, Tareas y Monografias
Buscar

Transformar el sistema de desigualdades en el sistema de ecuaciones


Enviado por   •  2 de Septiembre de 2013  •  Tutoriales  •  6.174 Palabras (25 Páginas)  •  330 Visitas

Página 1 de 25

En muchas ocasiones la función que necesitamos optimizar está determinada por más de dos variables independientes, estos es, la función objetivo y las restricciones tienen tres o más variables. Para estos casos el método gráfico no es aplicable debido a que necesitamos un eje cartesiano por cada variable independiente, pero podemos recurrir a un método algebraico llamado método Simplex.

El método consiste en convertir el sistema de desigualdades en un sistema de igualdades con la restricción de tener todas las variables positivas. Debido a que el sistema de igualdades tendrá más variables que ecuaciones, existen un número infinito de soluciones. El método busca la solución óptima (máxima o mínima) de ese con junto infinito de soluciones.

Primero convertimos cada restricción en una igualdad introduciendo una variable no negativa diferente en cada restricción (sin considerar las restricciones naturales), a la cual llamamos variable de holgura. Representamos el conjunto de ecuaciones matricialmente incluyendo la función objetivo en una matriz aumentada o tabla símplex. Es posible probar que el valor óptimo de la función objetivo se presenta cuando algunas de las variables son cero, a dicha solución la llamamos solución básica, si cumple con todas las igualdades generadas y las variables son no negativas, entonces se denomina solución básica factible (SBF).

Si la primera tabla símplex representa una solución básica factible, entonces nos damos a la labor de encontrar otra SBF que mejore el valor de la función objetivo, esto se logra mediante reducción de renglones en la matriz aumentada. Para poder decidir las operaciones de renglones a realizar se utilizan algunos criterios que detallamos en los siguientes ejemplos.

Ejemplo 1. Se desea maximizar la función:

Z = 2x + 3y,

sujeta a las restricciones

x  0, y  0,

x + 4y  9, y

2x + y  4.

Cada restricción se convierte en igualdad mediante la introducción de una variable de holgura que debe sumarse a la parte menor de la desigualdad, en nuestro ejemplo, al lado izquierdo:

Si u, v  0 entonces

x + 4y  9  x + 4y + u = 9

2x + y  4  2x + y + v = 4

De manera que el sistema de ecuaciones incluyendo la función objetivo tiene la siguiente representación matricial:

x y u v

x + 4y + u = 9 u 1 4 1 0 9

2x + y + v = 4  v 2 1 0 1 4

2x + 3y = Z 2 3 0 0 Z

Observamos que el conjunto de soluciones para este sistema es:

Si x = 0 y y = 0 entonces u = 9 y v = 4

Este conjunto de valores constituye una solución básica factible que nos permite inicializar el método: partimos del valor Z = 0 y trataremos de optimizarlo, en nuestro ejemplo esto significa incrementarlo, dado que realizamos una maximización de la función objetivo.

Para lograr la meta anterior intercambiamos alguna de las variables que valen cero por una variable cuyo valor no es cero mediante reducción de renglones. Llamamos a x y y variables de entrada, mientras que u y v son las variables de salida y al renglón de la función objetivo le llamamos indicadores.

En una maximización la primera variable de entrada la determinamos con el indicador más grande:

x y u v

u 1 4 1 0 9

v 2 1 0 1 4

2 3 0 0 Z

variable de entrada: y

Para entender esta elección si escribimos la ecuación correspondiente al renglón de los indicadores:

2x + 3y = Z

si y = 0 y x > 0, por ejemplo x = 1, obtenemos un incremento de 2 en Z, pero si x = 0 y y > 0 por ejemplo y = 1 el incremento de Z es de 3 unidades. Por tanto, conviene que y deje de ser cero para tomar un valor mayor.

Ahora dividimos los términos independientes entre los coeficientes de la variable de entrada y: el cociente más pequeño positivo determina la variable de salida:

x y u v

u 1 4 1 0 9  9/4 variable de salida: u

v 2 1 0 1 4  4/1

2 3 0 0 Z

variable de entrada: y

De manera que debemos transformar la columna en por medio de reducción de renglones, obteniendo la siguiente matriz:

x y u v

y 1/4 1 1/4 0 9/4

v 7/4 0 1/4 1 7/4

5/4 0 3/4 0 Z27/4

En esta matriz podemos leer los siguientes valores:

si suponemos

x = 0, u = 0

entonces

y = 9/4, v = 7/4 y Z = 27/4.

Esta solución es factible ya que cumple con el conjunto de restricciones y es mejor que nuestra solución inicial (Z = 0), sin embargo ¿será la solución óptima? Para determinarlo escribimos la ecuación correspondiente al renglón de los indicadores:

x  u = Z 

Despejando Z tenemos:

Z = + x  u

Podemos observar que Z puede incrementarse si u = 0 y x > 0, por tanto, la solución encontrada no es óptima. Podemos mecanizar el análisis anterior notando que si un indicador permanece positivo, dicho indicador permite incrementar el valor de la función, así, el proceso de maximización no termina mientras existan indicadores positivos.

Repetimos el procedimiento de transformar una variable de entrada en una de salida:

x y u v

...

Descargar como (para miembros actualizados)  txt (20.3 Kb)  
Leer 24 páginas más »
Disponible sólo en Clubensayos.com