Análisis Convexo. Revisión previa de aspectos de algebra lineal

UNIVERSIDAD NACIONAL MAYOR DE SAN MARCOS

ESCUELA PROFESIONAL DE INVESTIGACIÓN OPERATIVA

PROGRAMACIÓN LINEAL Y ENTERA

Análisis Convexo

Revisión previa de aspectos de Algebra Lineal

Cuando anteriormente presentamos las diferentes formas de los modelos de Programación Lineal, observamos que también podía representarse el problema usando vectores y matrices. 

También observamos que existe la forma general del modelo de Programación Lineal en la cual las diferentes restricciones pueden ser expresiones con el signo ≤, ≥ o =.

Así tenemos:

FORMA GENERAL DEL MODELO DE PROGRAMACIÓN LINEAL

                        Max (Min) Z = c1x1 + c2x2 + … + cnxn

                        s.a:        

                                                                  ≤[pic 1]

                                a11x1 +a12x2+…+a1nxn      ≥        b1

                                                                  =        

                                                                  ≤        [pic 2]

                                a21x1 +a22x2+…+a2nxn     ≥        b2

                                                                  =

                                        .   .   .                                                

                                                                  ≤[pic 3]

                                am1x1 +am2x2+…+amnxn           ≥        bm

                                                                  =

                                       xj   ≥ 0; j = 1, 2, …, n

Donde:

  Z        =        función que se desea optimizar (maximizar o

                 minimizar)

cj        =        coeficientes de la función objetivo; j = 1, 2, …, n

xj        =        variables de decisión; j = 1, 2, …, n

aij        =        coeficientes tecnológicos; i = 1, 2, …, m; j = 1, 2, …, n

bi        =        valor que representa la disponibilidad de un recurso

          (limitación).

 bi puede indicar:

• Disponibilidad de una materia prima.
• Disponibilidad de tiempo.
• Límites de producción.
• Demanda.
• Cantidad comprometida a entregar al cliente.

Cuando es un requerimiento mínimo, la restricción correspondiente se expresa:  ≥ bi

Cuando es un valor máximo posible, la restricción correspondiente se expresa:  ≤ bi

Cuando se requiere satisfacer exactamente, la restricción se expresa:  = bi

    Examinando la función objetivo:[pic 4]

[pic 5]

       [pic 7][pic 6]

                      [pic 8][pic 9]

Entonces tenemos:

Max(Min) Z = c.x

Examinando las restricciones:

                                                                    ≤[pic 10]

                                a11x1 +a12x2+…+a1nxn      ≥        b1

                                                                  =        

                                                                  ≤        [pic 11]

                                a21x1 +a22x2+…+a2nxn     ≥        b2

                                                                  =

                                        .   .   .                                                

                                                                  ≤[pic 12]

                                am1x1 +am2x2+…+amnxn           ≥        bm

                                                                  =

Observando el lado izquierdo por columnas, formamos la matriz de coeficientes tecnológicos A, por el vector de variables x,  ≤, ≥, =, vector del lado derecho b:[pic 13][pic 14][pic 15][pic 16][pic 17]

[pic 18]

Observando las condiciones de no negatividad de las variables:

≥  [pic 19][pic 20]

  Entonces, tenemos:                        ≥   0 [pic 21]

Entonces, el problema general inicialmente expresado así:

FORMA GENERAL DEL MODELO DE PROGRAMACIÓN LINEAL

                        Max (Min) Z = c1x1 + c2x2 + … + cnxn

                        s.a:        

                                                                  ≤[pic 22]

                                a11x1 +a12x2+…+a1nxn      ≥        b1

...