Clase 2


Definiciones  

1.-  En un problema de programación lineal deseamos maximizar o minimizar una función objetivo lineal, sujeta a determinadas restricciones sobre las variables.  Esto puede expresarse como sigue:

 Max (MIN) Z = C1X1 + C2X2 + ... + CnXn

Sujeto a:
A11X1 + A12X2 + ... + A1nXn (<=,=,>=) B1
A21X1 + A22X2 + ... + A2nXn (<=,=,>=)B2
........................................................................
Am1X1 + Am2X2 + ... + AmnXn (<=,=,>=)Bm
Xj >= 0 para j=1...n

2.- Z = C1X1 +C2X2 + ... + CnXn se denomina función objetivo

3.- Ai1X1 +Ai2X2 + AinXn (<=,=,>=) Bi es una restricción.

4.- Xj >= 0 para j=1...n designa la restricción NO negativa.

5.- El Conjunto que satisface todas las restricciones recibe el nombre de REGION FACTIBLE.

6.- La región factible es el conjunto intersección de semi - planos y, como tal, es un conjunto CONVEXO. Un conjunto es convexo si para cualesquiera puntos P1 y P2 contenidos en él, la recta que los une está contenida en dicho conjunto.

7.- Un VERTICE de la región factible se denomina un PUNTO EXTREMO de la región. Una definición más exácta es: Un punto es extremo de una región convexa si no está sobre el segmento que une cualquier otro par de puntos en la región.

 


Geometría

A)  En dos dimensiones podemos trazar la región factible correspondiente a las restricciones de un problema de PL con dos variables.

B)  Consideremos la función objeto Z = C1X1 + C2X2 . Si resolvemos esta ecuación para X2, se obtiene: X2 = (-C1/C2)X1 + Z/C2

Para los diferentes valores de Z tenemos una serie de rectas cuyas pendientes son todas (-C1/C2). Puesto que Z/C2 es la intersección X2 de cada una de las rectas, para MAXIMIZAR (minimizar) Z tratamos de incrementar (o disminuir) el corte X2 hasta donde sea posible, a la vez que se mantiene por lo menos un punto sobre los lados de la región factible.  

 C) Un Problema de programación lineal puede no tener solución sí:

• La región factible es un conjunto vacío. (No Factible)
• La región factible no este delimitada, pudiendose incrementar (o disminuir) Z sin límite (INFINITA).

D) Si el problema tiene solución, sucede que dicha solución se encuentra en un punto vértice o a lo largo de un borde de la región factible. (ALTERNA). En todo caso, el conjunto de soluciones incluye cuando menos un punto extremo de la región factible.

E) Con tres Variables, la región factible consiste en un cuerpo sólido y la función objetivo corresponde a una serie de planos paralelos.

Aquí de nuevo la Z óptima se obtiene determinando el plano en función de esta serie que optimiza Z a la par que tiene cuando menos un punto en común con la región factible.

Este plano puede tocar a la región factible en un punto (vértice), o a lo largo de un borde, o a lo largo de las caras del sólido. Sin embargo, como en el caso anterior, el conjunto de soluciones incluye por lo menos un punto extremo de la región factible.

 
Copyright Daniel Redondo