FORMULACION ESTANDAR

CONCEPTOS BASICOS

Forma estandar.

Es la igualación de las restricciones del modelo planteado, así como el aumento de variables de holgura, o bien la resta de variables de exceso.

Ahora se puede formular al modelo matemático para este problema general de asignación de recursos a actividades. En  Datos necesarios para un modelo de programación lineal que maneja la asignación de recursos a actividades particular, este modelo consiste en elegir valores de x1,x2,....,xn para:
 

optimizar (maximizar o minimizar) Z = c1x1 + c2x2 +....+ cnxn,

sujeta a las restricciones:

            C11x1 + C12x2 +....+ C1nxn (≥,≤,=)  cn1

            C1x1 + C22x2 +....+ C2nxn (≥,≤,=)  cn2

                                      

                X1≥ 0, X2 ≥ 0, ......, Xn≥0

Ejemplo 1
 Funcion objetivo
  maximizar z=X1 + X2

5X1+ 3X2 ≤15

3X1+ 5x2 ≤15

xj ≥0; j=1,2

 Pasos para pasar un roblema de programacion lineal al FORMATO ESTANDAR, se consideran las siguientes fases:

 

1. Convertir las desigualdades en igualdades

Se introduce una variable de holgura por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:

Variable de holgura.

Se usa para convertir en igualdad una desigualdad de tipo "≤". La igualdad se obtiene al adicionar en el lado izquierdo de la desigualdad una variable no negativa, que representa el valor que le hace falta al lado izquierdo para ser igual al lado derecho. Esta se conoce como variable de holgura, y en el caso particular en el que las restricciones de tipo ≤ se refieren al consumo máximo de un recurso, la variable adicionada cuantifica la cantidad sobrante de recurso (cantidad no utilizada) al poner en ejecución la solución óptima.

todo problema programacion lineal que se formula de la forma maximice, con todas sus restricciones≤ y con la condicion de nonegatividad se le llama forma estandar o forma normal.
 aqui al igual que en el metodo algebraico, debemos conseguir una solucion basica factible, aplicando las variables de holgura o artificiales: quedando el sistema de ecuacion asi:

maximizar z=x1+x2

5X1+ 3X2 +X3=15
3X1+ 5X2 +X4=15

Xj ≥0;j=1,2,3,4
las variables basicas son X3 yX4 y porsupuesto en la funcion ojetivo Z.

2. Igualar la funcion objetivo a cero

 

Necesitamosque la funcion objetivo siempre sea de minimizacion y que todas las demas restricciones sean igualdades .

este problema de programacion lineal aun  no esta en forma estandar. Entonces el  paso a seguir que tenemos que realizar es: 

1. cambiar de maximizacion a minimizacion: multiplicando la funcion objetivo  por -1.

en este caso la funcion objetivo sera.

 minimizar Z-X1-X2=0

 sujeta a:  5X1+ 3X2 +X3=15
               31+ 5X2 +X4=15

Ejemplo 2

Modelo original

•  Funcion objetivo

 maximizar z=60X1 + 30X2+20X3

  

sujeta a:  8X1+ 6X2 +X3≤48
               4X1+ 2X2 +1.5X3≤20
               2X1+ 1.5X2 +0.5X3≤8
                          X2          ≤5

            Xj ≥0;j=1,2,3


 Modelo estandar

•   Funcion objetivo

maximizar z=60X1 + 30X2+20X3
  
sujeta a:  8X1+ 6X2 +X3+X4=48
               4X1+ 2X2 +1.5X3 +X5=20
               2X1+ 1.5X2 +0.5X3+X6=8
                          X2          +X7 =5


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

Minimizar z -60x1-30X2-20X3

sujeta a:  8X1+ 6X2 +X3+X4=48
               4X1+ 2X2 +1.5X3 +X5=20
               2X1+ 1.5X2 +0.5X3+X6=8
                          X2          +X7 =5


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

ADAPTACIÓN A OTRAS FORMAS DEL MODELO.

Hasta el momento sólo se han estudiado problemas en la forma estándar

Maximizar Z.
• Restricciones de la forma £ .
• Todas las variables no negativas.

Maximizar Z = 3X1 + 5X2

Sujeto a    :X1≤  4
              2X2 ≤ 12
    3X1 + 2X2≤ 18
     X1 , X2 = 0

Ahora bien xisten variaciones cuando:

•Restricciones en forma de igualdad.
•Lados derechos negativos.
•Restricciones de la forma≥  .
• Función objetivo minimizar.

1.Restricciones en forma de igualdad.

Cualquier restricción del tipo
a11X1 + a12X2 + .............+ a1nXn = b1
Es equivalente a
a11X1 + a12X2 + .............+ a1nXn ≤  b1
a11X1 + a12X2 + .............+ a1nXn ≥ b1
Esto es inconveniente pues se aumenta el número de restricciones, Lo que se hace
entonces es introducir variables artificiales Veamos un ejemplo:

Maximizar Z = 3X1 + 5X2
 

Sujeto a :   X1 ≤ 4
                2X2≤  12
     3X1 + 2X2 = 18
X1 , X2 ≥  0

La forma aumentada de este problema es:

(0)   Z - 3X1 -5X2                       =0

(1)           X1           + X3           = 4

(2)                  2X2          +X4    = 12

(3)         3X1+2X2                     = 18

Observe que no está completa la matriz identidad.Es necesario introducirvariables artificiales.

Variables artificiales.

1.  Facilitan hallar una S.B.F inicial.
2.  Deben cumplir requerimientos de no negatividad.
3.  Se deben introducir penalizaciones muy grandes en la función objetivo.
4.  Se convierten en V.B en la ecuación en que han sido introducidas.
5. El proceso iterativo del simplex se deshace de ellas.

Paso 1.
Se introduce una variable artificial X 5
3X1 + 2X2 + X5 = 18
Es muy similar a introducir una variable de holgura

 Paso 2.
Se asigna una penalización enorme en la
función objetivo por el hecho de tener X5 ≥  0
 

Se modifica la función objetivo

  Maximizar Z = 3X1 + 5X2 - MX5
Este método se llama el método de la M grande, pues M representa un número muy grande.

 La forma aumentada del problema artificial es:
 (0) Z- 3X1 -5X2 +MX5       =0
 (1)      X1 +  X3               = 4 
 (2)    2X2          + X4        = 12
 (3)    3X1 + 2X2        +X5 = 18




 X1=0 , X2=0 ,
X3=4 , X4=12 , X5=18