Programacion Lineal

Problema principal o general de la Programación Lineal (PL). Modelación matemática de los diferentes problemas de Programación Lineal. Objetivo: Describir los problemas de PL y los pasos a seguir para la modelación de los mismos. Planteamiento del problema: Llamaremos problema general de Programación Lineal el problema,
c, x Ax b ext.

(Pr)

con

x

( x1 , x2 ,

, xn )
a11 a12 a 22am2

n

, c
a1n a 2n a mn

(c1 , c 2 ,

, cn )

n

, b

(b1 , b2 ,

, bm )

m

,

A

(aij ) mxn

a 21 a m1

,

y el producto escalar

, x, y

:

2n

x1 y1

x2 y2

xn yn

.

Los problemas de PL se analizan, por regla general, reduciéndolos a la forma canónica,
c, x Ax ext. b, x 0

(Prc)

o a la forma normal,

c, x Ax

ext. b, x 0

(Prn)

Laforma canónica es más cómoda para describir los algoritmos de solución, además, los problemas (Pr) y (Prn) son utilizados para examinar las cuestiones de existencia de soluciones y de dualidad. Para la modelación de problemas de PL en general se requiere de cuatro pasos básicos: I. Extraer el conjunto de datos. II. Definir el conjunto de variables involucradas en el problema, junto con susrespectivos dominios de definición.

III. Deducir el conjunto de restricciones lineales del problema que definen el conjunto de soluciones admisibles. IV. Escoger la función lineal que debe ser optimizada (función objetivo). A continuación plantearemos tres problemas a modelar, en los cuales ilustraremos los cuatro pasos básicos de la modelación en la PL. Problema del Transporte Copextel necesitatrasladar computadoras en determinadas cantidades desde varios almacenes de la empresa hacia un número determinado de Universidades. Cada Universidad tiene asignado cierto número de computadoras, mientras que cada almacén puede suministrar hasta cierta cantidad. El problema consiste en determinar las cantidades que debe enviar cada almacén a las universidades de tal forma que se minimice el costo detransportación. 1. Datos: m : número de almacenes. n: número de universidades. u i : cantidad de computadoras que deben enviarse desde el almacén i. v j : cantidad de computadoras que debe recibir la universidad j.
cij : costo unitario de transportación de una computadora desde el almacén i a la

universidad j. 2. Variables: xij : cantidad de computadoras que se envían desde el almacén i a launiversidad j. 3. Restricciones: Las restricciones de este problema son,
n

xij
j 1 m

ui , i 1,2, vj , j 1,2,

,m

xij
i 1

,n
1,2, ,n

xij

0, i 1,2,

,m , j

4. Objetivo que debe optimizarse. En el problema del transporte nos interesa normalmente minimizar los costos de envío (suma de los costos de envío por unidad de producto multiplicado por las cantidades enviadas); esdecir, se debe minimizar
m n

Z

cij xij
i 1j 1

Problema de análisis de actividades Un fabricante dispone de cantidades fijas de cierto número de recurso diferentes. Estos recursos, tales como materia prima, trabajo y equipos; pueden ser combinados para producir cualquier producto o combinaciones de ellos entre el grupo de productos que pueden ser fabricados. El fabricante conoce quécantidad de recurso i se requiere para producir una unidad del artículo j. También conoce qué utilidad obtiene por cada unidad producida del artículo j. El fabricante desea producir una combinación de artículos tal, que maximice las utilidades totales. 1. Datos: m : número de recursos. n : número de productos. ai : cantidad del recurso i. rij : cantidad del recurso i necesaria para producir una unidaddel producto j.
u j : utilidad obtenida por la fabricación del producto j.

2. Variables: x j : cantidad de unidades del producto j. 3. Restricciones:
n

rij x j
j 1

ai

xj

0, i 1,2,

, n.

4. Función objetivo a optimizar:
n

Maximizar Z
i 1

uj xj

El problema de la dieta El problema de la dieta consiste en determinar las cantidades de distintos nutrientes que deben...