ejercicio

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 lasrestricciones 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 formacanó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 ≥ bX ≥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 ⎤
⎢ ⎥
⎢x ⎥
⎢ 2 ⎥ b = ⎢b2 ⎥
X =
⎢.⎥
⎢.⎥
⎢ ⎥
⎢ ⎥
⎣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. Algunasvariables 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 loque 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 igualn

∑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
dondex 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 cantidadesfí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...