Programacion Lineal

República Bolivariana de Venezuela
Ministerio de Poder Popular Para La Educación
Instituto Universitario de Tecnología Elías Calixto Pompa
Tópicos Especiales de Informática
5ª Semestre Diurno


Programación Lineal


















Guatire, 08 de Diciembre del 2010


Programación Lineal

La Programación Lineal es un procedimiento o algoritmo matemático mediante elcual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales, optimizando la función objetivo, también lineal.
Los modelos de Programación Lineal por su sencillez son frecuentemente usados para abordar una gran variedad de problemas de naturaleza real en ingeniería y ciencias sociales, lo que ha permitido a empresas y organizaciones importantes beneficios y ahorrosasociados a su utilización.
Formulación de la Programación Lineal
Variables
Las variables son números reales mayores o iguales a cero.
En caso que se requiera que el valor resultante de las variables sea un número entero, el procedimiento de resolución se denomina Programación entera.
Restricciones
Las restricciones pueden ser de la forma:
Tipo 1:
Tipo 2:
Tipo 3:
Donde:
A = valorconocido a ser respetado estrictamente;
B = valor conocido que debe ser respetado o puede ser superado;
C = valor conocido que no debe ser superado;
j = número de la ecuación, variable de 1 a M (número total de restricciones);
a; b; y, c = coeficientes técnicos conocidos;
X = Incógnitas, de 1 a N;
i = número de la incógnita, variable de 1 a N.
En general no hay restricciones en cuanto a losvalores de N y M. Puede ser N = M; N > M; ó, N < M.
Sin embargo si las restricciones del Tipo 1 son N, el problema puede ser determinado, y puede no tener sentido una optimización.
Los tres tipos de restricciones pueden darse simultáneamente en el mismo problema.
Función Objetivo
La función objetivo puede ser:


ó

Donde:
f = coeficientes son relativamente iguales a cero.
Ejemplo:

Éste esun caso curioso, con solo 6 variables (un caso real de problema de transporte puede tener fácilmente más de 1.000 variables) en el cual se aprecia la utilidad de este procedimiento de cálculo.
Existen tres minas de carbón cuya producción diaria es:
La mina "a" produce 40 toneladas de carbón por día;
La mina "b" otras 40 t/día; y,
La Mina "c" produce 20 t/día.
En la zona hay dos centralestermoeléctricas que consumen:
La central "d" consume 40 t/día de carbon; y,
La central "e" consume 60 t/día
Los costos de mercado, de transporte por tonelada son:
De "a" a "d" = 2 monedas
De "a" a "e" = 11 monedas
De "b" a "d" = 12 monedas
De "b" a "e" = 24 monedas
De "c" a "d" = 13 monedas
De "c" a "e" = 18 monedas
Si preguntáramos a una asamblea de pobladores de la zona, cómo organizar eltransporte, con certeza, la gran mayoría opinaría que debemos aprovechar el precio ofrecido por el transportista que va de "a" a "d", porque es mucho más conveniente que los otros.
En este caso, el costo total del transporte seria:
Transporte de 40 t de "a" a "d" = 80 monedas
Transporte de 20 t de "c" a "e" = 360 monedas
Transporte de 40 t de "b" a "e" = 960 monedas
Total 1.400 monedas.
Sinembargo, formulando el problema para ser resuelto por la programación lineal tendríamos las siguientes ecuaciones:
Restricciones de la producción:






Restricciones del consumo:




La función objetivo será:

La solución de costo mínimo de transporte diario resulta:
Xb-d = 40 resultando un costo de 12 x 40 = 480 monedas
Xa-e = 40 resultando un costo de 11 x 40 = 440 monedasXc-e = 20 resultando un costo de 18 x 20 = 360 monedas
Total 1.280 monedas.
Reflexiones que surgen del problema:
1. Es discutible la conveniencia de tomar decisiones por consenso en cuestiones estrictamente técnicas;
2. Es discutible la aplicación de la intuición en el caso de problemas con más de 4 variables;
3. Una vez conocida la solución del problema lineal, generalmente le resulta casi...