00040800

PROGRAMACION LINEAL
INTRODUCCIÓN
Veamos. Si tienes en el bolsillo una cantidad de dinero, la puedes usar para comprar comida, bebidas, pagar
por tener diversión, etc. Además del dinero, puedes tener un reloj que pudieras empeñar, y quizás otras piezas
de joyería. El problema de programación al que te enfrentas es: ¿Cómo obtengo mayor valor por los
productos y servicios que adquiero con el dineroque tengo?
La Programación Lineal es una técnica de optimización matemática que permite asignar recursos limitados y
así encontrar una solución aproximada a problemas de decisión como el planteado anteriormente, y siempre
relacionados con la maximización o minimización, utilizando apropiadamente los recursos.
Para poder aplicar la Programación Lineal a un problema, deben existir 4 condiciones:
•Los recursos deben ser limitados (p.ej. el dinero, los trabajadores, etc.), de lo contrario, no habría ningún
problema;
• Debe existir un objetivo explícito (como maximizar las utilidades o minimizar costos);
• Las relaciones deben ser lineales (p.ej. si lleva tres horas fabricar una pieza, entonces dos piezas requieren
seis horas y se necesitan nueve para fabricar tres);
• Debe existirhomogeneidad (son idénticos los productos que se obtienen de una máquina, o son igual de
productivas todas las horas disponibles de un trabajador)
DEFINICIONES
Función objetivo
Es la función principal de la cual hay que averiguar el valor máximo desde una serie de restricciones o rectas
que delimitan la gráfica de dicha función.
Restricciones
Son desigualdades a las cuales se les añaden unas variablesllamadas de holgura para convertirlas en rectas y
delimitar el área de la función objetivo. Los puntos de cortes entre rectas (sistemas de ecuaciones) serán los
que indiquen el máximo de la función objetivo.
Convexidad
Se dice que el área delimitada por las restricciones es un conjunto convexo si está completamente cerrada por
los puntos como resultado de resolver la representación gráfica. Siempre setoma el área mínima en los puntos
de corte con las rectas.
MÉTODO GRÁFICO
Normalmente, se tratarán funciones de 2 variables. La función objetivo se presenta de la siguiente manera:
Z = Ax1 + Bx2
Para evitar dificultades, se tomarán como muestra 3 restricciones para dicha función, siendo el número
mínimo una restricción por cada variable:
1

a1x1 + b1x2 " c1
a2x1 + b2x2 " c2
a3x1 + b3x2 " c3
x1, x2" 0
En el método gráfico, las anteriores desigualdades se convierten en igualdades y ya tenemos las rectas que
delimitarán la función. Para hallar los puntos de corte con los ejes de coordenadas, se igualan a 0 cada
variable, quedando de la siguiente forma:
a1x1 + b1x2 = c1

a2x1 + b2x2 = c2

a3x1 + b3x2 = c3

x1 = 0 ! (0, c1/b1)

x1 = 0 ! (0, c2/b2)

x1 = 0 ! (0, c3/b3)

x2 = 0 ! (c1/a1, 0)

x2= 0 ! (c2/a2, 0)

x2 = 0 ! (c3/a3, 0)

La última restricción sirve para tomar en cuenta el punto (0,0) como origen del área delimitada por las rectas.
Para el eje de coordenada X (variable x1) se tomará el mínimo de los ptos (ci/ai, 0):
Min[ (c1/a1, 0) , (c2/a2, 0) , (c3/a3, 0) ]
Igualmente, para el eje de coordenada Y (variable x2) se tomará el mínimo de los puntos (0, ci/bi):
Min[ (0, c1/b1) ,(0, c2/b2) , (0, c3/b3) ]
A continuación, se toman aquellos puntos que sean intersección de las tres rectas y que pertenezcan además a
las rectas que contienen los puntos mínimos anteriores. El área total de la función vendrá delimitada por los
puntos (ci/ai, 0), (0, ci/bi) y los de la intersección de las rectas. Una vez obtenidos los puntos de intersección,
se crean tantos sistemas de ecuacionescomo puntos de intersección que cumplan la condición anterior haya.
En nuestro caso, para tres rectas se hacen dos sistemas de ecuaciones tomando en cada uno una de las rectas
asociadas con uno de los puntos de corte, y la tercera será común a ambos sistemas. Por último, cada punto
resultante se resuelve en la función objetivo, sustituyéndolo en las variables x1 y x2, y se toma aquél que dé el...