• Author / Uploaded
• Krlos Castro Espinoza

• Categories
• Desigualdad (Matemáticas)
• Análisis
• Objetos matemáticos
• Álgebra
• Matemáticas Aplicadas

Citation preview

Forma Canónica y Estándar

Investigación de Operaciones I

FORMA CANONICA Y FORMA ESTANDAR Un problema de programación lineal puede ser establecido en diferentes formas equivalentes a través de manipulaciones apropiadas. Dos formas en particular serán de bastante utilidad. Estas son las formas Estándar y Canónica. Un problema lineal se dice que esta en la forma estándar si ; a) Todas las restricciones son igualdades b) Todas las variables son no-negativas c) Las limitaciones ( lado derecho de la restricción) son positivas El Método Simplex, esta diseñado para ser aplicado únicamente hasta que el problema se encuentre en la forma Estándar. La forma Canónica es también de bastante utilidad, especialmente en explorar la relación de Dualidad. Un problema de P.L. está en la forma canónica si para un problema de: Maximización, las variables son no-negativas y las restricciones son del tipo ≤ Minimización, las variables son no-negativas y las restricciones son del tipo ≥

Considere el siguiente problema de P.L. en forma canónica n

Minimice Z = ∑ c j x j

Minimice Z=CX

Sujeto a;

Sujeto a;

j =1

n

∑a x j =1

ij

j

≥ bi , i = 1,2,...m

Ax ≥ b X ≥0

xj ≥ 0

Donde : A= Matriz de coeficientes de las variables en el sistema de ecuaciones de (mxn) aij= coeficiente de la variable j en la restricción i x=Vector solución (nx1) xj= Variable j bi= Lado derecho de la restricción i ( Limitación i ) C=Vector de costos o utilidades (1xn) cj= Coeficiente de la variable j en la función objetivo

M.C. Héctor Martínez Rubin Celis

1

Forma Canónica y Estándar

⎡ b1 ⎤ ⎡ x1 ⎤ ⎢b ⎥ ⎢x ⎥ 2⎥ ⎢ X = b = ⎢ 2⎥ ⎢.⎥ ⎢.⎥ ⎢ ⎥ ⎢ ⎥ ⎣bn ⎦ ⎣ xn ⎦

Investigación de Operaciones I

⎡ a11 a12 ⎢a a22 A = ⎢ 21 ⎢ . . ⎢ ⎣am1 am 2

. a1n ⎤ . a2 n ⎥⎥ . . ⎥ ⎥ . amn ⎦

Los motivos para que un problema no este en la forma estándar son: 1. Algunas restricciones son desigualdades 2. Algunas bi son negativas 3. Algunas variables de decisión xj pueden ser negativas Igualdades y desigualdades en las restricciones Una desigualdad puede fácilmente ser transformada a una igualdad (ecuación ) a través del uso de las variables de holgura qué representan en caso de:

a) La desigualdad menor o igual (≤ ), la deficiencia de unidades para el lado izquierdo de la restricción iguale a lado derecho de la misma. Por lo que se agrega una variable de holgura con signo positivo en el lado izquierdo de la restricción.. b) La desigualdad menor o igual (≥ ),el exceso de unidades que tiene el lado izquierdo de la restricción con respecto al lado derecho de la misma. Por lo que se agrega una variable de holgura con signo negativo en el lado izquierdo de la restricción.

En el caso de una desigualdad mayor o igual n

∑a x j =1

n

∑a j =1

ij

ij

j

≥ bi

Se agrega una variable con signo negativo xn+1, como se muestra a continuación

x j − x n +1 = bi

donde

x n +1 ≥ 0

En el caso de una desigualdad menor o igual n

∑a j =1

ij

x j ≤ bi

ij

x j + x n +1 = bi

n

∑a j =1

Se agrega una variable con signo positivo xn+1, como se muestra a continuación donde

x n +1 ≥ 0

Así mismo, la ecuación de la forma

M.C. Héctor Martínez Rubin Celis

2

Forma Canónica y Estándar

n

∑a j =1

ij

Investigación de Operaciones I

x j = bi

Pude ser transformada en dos desigualdades n

∑a j =1

ij

x j ≤ bi

n

y

∑a j =1

ij

x j ≥ bi

Para la mayoría de los problemas prácticos, las variables representan cantidades físicas y por lo tanto no pueden ser negativas. El Método Simplex, que se cubrirá más adelante, esta diseñado para resolver problemas lineales donde las variables deben ser nonegativas. Si una variable xn no tiene restricción en signo, entonces esta puede ser reemplazada por: xj ´ y xj+1´´ , donde ambas son ≥ 0 y xj ´ representa la parte positiva de la variable xj y xj+1´´ representa la parte negativa de la variable xj . Una vez resuelto el problema, en el caso de que la variable xj este en solución, únicamente podrá tener valor una de las variables xj ´ y xj+1´´ y la otra deberá tener valor de cero, es decir que solamente podrá estar en solución una de las dos variables (pero no necesariamente esta variable xj estará en solución). Ejemplo: Minimizar Z= -x1 - 3x2 Sujeto a; x1 – x2 ≤ 6 -x1 + 2x2 ≥ 8 x1,x2≥ 0 Transformando a l forma estándar tenemos: Minimizar Z= -x1 - 3x2 Sujeto a; =6 x1 – x2 + x3 -x1 + 2x2 + x4 = 8 x´s≥ 0 x3, y x4 son variables de holgura. Si ahora consideramos que x1 no esta restringida en signo, el problema se puede plantear de la forma siguiente; Minimizar Z= -(x1´ - x1´´ ) - 3x2 Sujeto a; (x1´ - x1´´ ) – x2 + x3 =6 + x4 = 8 -(x1´ - x1´´ ) + 2x2 x´s≥ 0 donde x1=-(x1´ - x1´´ ) , x1 no esta restringida en signo y x2 ≥ 0

M.C. Héctor Martínez Rubin Celis

3

Forma Canónica y Estándar

Investigación de Operaciones I

Para efectos de resolver este problema por el método Simplex, se modifican los subíndices de las variables; Minimizar Z= -x1 – x2 - 3x3 Sujeto a; x1 - x2 + x3 + x4 =6 -x1 + x2 + 2x3 + x5 = 8 x´s≥ 0 donde x1= x1´ y x2 = x1´´ y se recorren los subíndices delas variables restantes. Una vez que se resuelva este problema, las variables retoman sus subíndices iniciales. No-negatividad de las limitaciones bi Cuando el problema se desea representar en forma estándar y alguna de las bi es negativa, se multiplica la restricción que corresponda a esta limitación por (-1) y así se hace positiva.

Ejemplo: Minimizar Z= -x1 - 3x2 Sujeto a; = 6 x1 – x2 + x3 + x4 = -8 -x1 + 2x2 x´s≥ 0 x3, y x4 son variables de holgura. Se multiplica la segunda restricción por (-1), resultando; Minimizar Z= -x1 - 3x2 Sujeto a; =6 x1 – x2 + x3 - x4 = 8 x1 - 2x2 x´s≥ 0 .

VALOR DE LA FUNCIÓN OBJETIVO TIPO DE RESTRICCIONES 1.- Desigualdad ≤, añadir una variable de Holgura de Déficit (con signo + ). 2.- Desigualdad ≥, añadir una variable de Holgura de Exceso (con signo - ) y una variable Artificial (con signo + ). 3.- Igualdad =, añadir una variable Artificial ( con signo +)

MAXIMIZACION

MINIMIZACION

Coeficiente de la variable de Coeficiente de la variable de Holgura igual a cero. Holgura igual a cero. Coeficiente de la variable de Coeficiente de la variable de Holgura igual a cero y de la Holgura igual a cero y de la variable Artificial igual a +M. variable Artificial igual a -M. Coeficiente de la Artificial igual a -M.

M.C. Héctor Martínez Rubin Celis

variable Coeficiente de la variable Artificial igual a -M.

4