La programación lineal es el campo de la optimización matemática dedicado a maximizar

o minimizar (optimizar) una función lineal, denominada función objetivo, de tal forma que
las variables de dicha función estén sujetas a una serie de restricciones expresadas
mediante un sistema de inecuaciones también lineales. Los métodos más recurridos para
resolver problemas de programación lineal son algoritmos de pivote, en particular

Cronología1
Año Acontecimiento
Joseph Fourier anticipa la programación lineal. Carl Friedrich Gauss
1826
resuelve ecuaciones lineales por eliminación "gaussiana".
1902 Gyula Farkas concibe un método para resolver sistemas de inecuaciones.
George Dantzig publica el algoritmo simplex y
John von Neumann desarrolló la teoría de la dualidad.
1947
Se sabe que Leonid Kantoróvich también formuló la teoría en forma
independiente.
Narendra Karmarkar introduce el método del punto interior para resolver
1984
problemas de programación lineal.

los algoritmos simplex. Historia de la programación lineal[editar]

El problema de la resolución de un sistema lineal de inecuaciones se remonta, al menos,
a Joseph Fourier, después de quien nace el método de eliminación de Fourier-Motzkin. La
programación lineal se plantea como un modelo matemático desarrollado durante
la Segunda Guerra Mundial para planificar los gastos y los retornos, a fin de reducir los
costos al ejército y aumentar las pérdidas del enemigo. Se mantuvo en secreto hasta 1947.
En la posguerra, muchas industrias lo usaron en su planificación diaria.
Los fundadores de la técnica son George Dantzig, quien publicó el algoritmo simplex, en
1947, John von Neumann, que desarrolló la teoría de la dualidad en el mismo año,
y Leonid Kantoróvich, un matemático de origen ruso, que utiliza técnicas similares en la
economía antes de Dantzig y ganó el premio Nobel en economía en 1975. En 1979, otro
matemático ruso, Leonid Khachiyan, diseñó el llamadoAlgoritmo del elipsoide, a través del
cual demostró que el problema de la programación lineal es resoluble de manera eficiente,
es decir, en tiempo polinomial.2 Más tarde, en 1984, Narendra Karmarkar introduce un
nuevo método del punto interior para resolver problemas de programación lineal, lo que
constituiría un enorme avance en los principios teóricos y prácticos en el área.
El ejemplo original de Dantzig de la búsqueda de la mejor asignación de 70 personas a 70
puestos de trabajo es un ejemplo de la utilidad de la programación lineal. La potencia de
computación necesaria para examinar todas las permutaciones a fin de seleccionar la
mejor asignación es inmensa (factorial de 70, 70!) ; el número de posibles configuraciones
excede al número de partículas en el universo. Sin embargo, toma sólo un momento
encontrar la solución óptima mediante el planteamiento del problema como una
programación lineal y la aplicación del algoritmo simplex. La teoría de la programación
lineal reduce drásticamente el número de posibles soluciones factibles que deben ser
revisadas.

Variables[editar]
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[editar]
Las restricciones pueden ser de la forma:

Tipo 1:

Tipo 2:

Tipo 3:
Donde:

 A = valor conocido 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 los valores 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[editar]
La función objetivo puede ser:

Donde:

 = coeficientes son relativamente iguales a cero.

Programación entera[editar]
En algunos casos se requiere que la solución óptima se componga de valores enteros para
algunas de las variables. La resolución de este problema se obtiene analizando las
posibles alternativas de valores enteros de esas variables en un entorno alrededor de la
solución obtenida considerando las variables reales. Muchas veces la solución del
programa lineal truncado está lejos de ser el óptimo entero, por lo que se hace necesario
usar algún algoritmo para hallar esta solución de forma exacta. El más famoso es el
método de 'Ramificar y Acotar' o Branch and Bound por su nombre en inglés. El método de
Ramificar y Acotar parte de la adición de nuevas restricciones para cada variable de
decisión (acotar) que al ser evaluado independientemente (ramificar) lleva al óptimo
entero.

Aplicaciones[editar]
La programación lineal constituye un importante campo de la optimización por varias
razones, muchos problemas prácticos de la investigación de operaciones pueden
plantearse como problemas de programación lineal. Algunos casos especiales de
programación lineal, tales como los problemas de flujo de redes y problemas de flujo de
mercancías se consideraron en el desarrollo de las matemáticas lo suficientemente
importantes como para generar por si mismos mucha investigación sobre algoritmos
especializados en su solución. Una serie de algoritmos diseñados para resolver otros tipos
de problemas de optimización constituyen casos particulares de la más amplia técnica de
la programación lineal. Históricamente, las ideas de programación lineal han inspirado
muchos de los conceptos centrales de la teoría de optimización tales como la dualidad, la
descomposición y la importancia de la convexidad y sus generalizaciones. Del mismo
modo, la programación lineal es muy usada en la microeconomía y la administración de
empresas, ya sea para aumentar al máximo los ingresos o reducir al mínimo los costos de
un sistema de producción. Algunos ejemplos son la mezcla de alimentos, la gestión de
inventarios, la cartera y la gestión de las finanzas, la asignación de recursos humanos y
recursos de máquinas, la planificación de campañas de publicidad, etc.
Otros son:

 Optimización de la combinación de cifras comerciales en una red lineal de distribución

de agua.

 Aprovechamiento óptimo de los recursos de una cuenca hidrográfica, para un año con
afluencias caracterizadas por corresponder a una determinada frecuencia.

 Soporte para toma de decisión en tiempo real, para operación de un sistema de obras
hidráulicas;

 Solución de problemas de transporte.

Ejemplo[editar]

Este es un 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" produce 40 t/día; y,
 La mina "c" produce 20 t/día.
En la zona hay dos centrales termoeléctricas que consumen:

 La central "d" consume 40 t/día de carbón; 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 se preguntase a los pobladores de la zona cómo organizar el transporte, tal vez la
mayoría opinaría que debe aprovecharse el precio ofrecido por el transportista que va
de"a" a "d", porque es más conveniente que los otros, debido a que es el de más bajo
precio.
En este caso, el costo total del transporte es:

 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.
Sin embargo, formulando el problema para ser resuelto por la programación lineal se
tienen 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 ser:

 Xb-d = 40 resultando un costo de 12 x 40 = 480 monedas

 Xa-e = 40 resultando un costo de 11 x 40 = 440 monedas
 Xc-e = 20 resultando un costo de 18 x 20 = 360 monedas
 Total 1.280 monedas.
120 monedas menos que antes.
 Programación lineal

La programación lineal da respuesta a situaciones en las que se exige maximizar

o minimizar funciones que se encuentran sujetas a determinadas limitaciones,
que llamaremos restricciones.

Su empleo es frecuente en aplicaciones de la industria, la economía, la estrategia

militar, etc.

Función objetivo

En esencia la programación lineal consiste en optimizar (maximizar o

minimizar) una función objetivo, que es una función lineal de varias variables:

f(x,y) = ax + by.

Restricciones

La función objetivo está sujeta a una serie de restricciones, expresadas por

inecuaciones lineales:

a1x + b1y ≤ c1

a2x + b2y ≤ c2

... ... ...

anx + bny ≤ cn

Cada desigualdad del sistema de restricciones determina un semiplano.

Solución factible

El conjunto intersección, de todos los semiplanos formados por las restricciones,

determina un recinto, acotado o no, que recibe el nombre de región de validez o
zona de soluciones factibles.

Solución óptima
 El conjunto de los vértices del recinto se denomina conjunto de soluciones
factibles básicas y el vértice donde se presenta la solución óptima se llama
solución máxima (o mínima según el caso).

Valor del programa lineal

El v al or qu e t om a l a f un ci ón obje t i v o e n el v é rti ce de sol u ci ón

ópt i m a se l l am a v al or del program a l i n e al .

Pasos para resolver un problema de programación lineal

1 El e gi r l as i n cógni t as.

2 E scri bi r l a fu n ci ón obje ti v o en f un ci ón de l os dat os del

probl e m a.

3 E scri bi r l as re st ri cci on e s e n f orm a de si ste m a de

i n e cu aci one s.

4 Av e ri gu ar el con jun t o de sol u ci one s f acti bl e s re pre se n t an do

gráf i came n te l as re st ri cci on e s.
 5 C al cu l ar l as coorde n adas de l os v é rt i ce s de l re ci n t o de
sol u ci one s f acti bl e s ( si son pocos) .

6 C al cul ar el v al or de l a f u n ci ón obje ti v o en cada u n o de l os

v é rti ce s para v e r en cu ál de el l os pre se n t a el v al or m áxi m o o
mí ni m o se gú n n os pi da el probl em a ( h a y que te n e r en cu e n t a
aqu í l a posi bl e n o e xi st e n ci a de sol u ci ón si el re ci n t o n o e st á
acot ado) .

Ejemplos de programación lineal

Unos grandes almacenes encargan a un fabricante pantalones y chaquetas

deportivas.

El fabricante dispone para la confección de 750 m de tejido de algodón y 1000 m

de tejido de poliéster. Cada pantalón precisa 1 m de algodón y 2 m de poliéster.
Para cada chaqueta se necesitan 1.5 m de algodón y 1 m de poliéster.

El precio del pantalón se fija en 50 € y el de la chaqueta en 40 €.

¿Qué número de pantalones y chaquetas debe suministrar el fabricante a los

almacenes para que estos consigan una beneficio máxima?

1 Elección de las incógnitas.

x = número de pantalones

y = número de chaquetas

2 Función objetivo

f(x,y)= 50x + 40y

3 Restricciones
Para escribir las restricciones vamos a ayudarnos de una tabla:

pantalones chaquetas disponible

algodón 1 1,5 750

poliéster 2 1 1000

x + 1.5y ≤ 750 2x+3y ≤ 1500

2x + y ≤ 1000

Como el número de pantalones y chaquetas son números naturales, tendremos

dos restricciones más:

x≥0

y≥0

4 Hallar el conjunto de soluciones factibles

Tenemos que representar gráficamente las restricciones.

Al ser x ≥ 0 e y ≥ 0, trabajaremos en el primer cuadrante.

Representamos las rectas, a partir de sus puntos de corte con los ejes.
Resolvemos gráficamente la inecuación: x + 1.5y ≤ 750, para ello tomamos un
punto del plano, por ejemplo el (0,0).

0 + 1.5· 0 ≤ 750

0 ≤ 750 entonces el punto (0,0) se encuentra en el semiplano donde se cumple la

desigualdad.

De modo análogo resolvemos 2x + y ≤ 1000.

2 · 0 + 0 ≤ 1 000

La zona de intersección de las soluciones de las inecuaciones sería la solución al

sistema de inecuaciones, que constituye el conjunto de las soluciones factibles.
 5 Calcular las coordenadas de los vértices del recinto de las soluciones
factibles.

La solución óptima, si es única, se encuentra en un vértice del recinto. Estas son

las soluciones a los sistemas:

2x + 3y = 1500; x = 0 (0, 500)

2x + y = 1000; y = 0 (500, 0)

2x + 3y =1500; 2x + y = 1000 (375, 250)

 6 Calcular el valor de la función objetivo

En la función objetivo sustituimos cada uno de los vértices.

f(x, y) = 50x + 40y

f(0, 500) = 50 · 0 + 40 · 500 = 20 000 €

f(500, 0) = 50 · 500 + 40 · 0 = 25 000 €

f(375, 250) = 50 · 375 + 40 · 250 = 28 750 € Máximo

La solución óptima es fabricar 375 pantalones y 250 chaquetas para obtener

un beneficio de 28750 €.

Solución múltiple

La solución no siempre es única, también podemos encontrarnos con una

solución múltiple.

Si la función objetivo del ejercicio anterior hubiese sido:

 f(x,y)= 20x + 30y

f(0,500) = 20 · 0 + 30 · 500 = 15 000 € Máximo

f(500, 0) = 20 · 500 + 30 · 0 = 10 000 €

f(375, 250) = 20 · 375 + 30 · 250 = 15 000 € Máximo

En este caso todos los pares, con soluciones enteras, del segmento trazado en
negro serían máximos.

f(300, 300)= 20 · 300 + 30 · 300 = 15 000 € Máximo