Programacion Lineal

Programación lineal – Matemáticas Aplicadas a las Ciencias Sociales II

1

Programación lineal.
Orígenes de la programación lineal.
En el mundo que vivimos, pocas son las ramas del saber en las que las Matemáticas no han
mostrado su influencia, en particular los conceptos de máximo y mínimo han contribuido a resolver
bastantes problemas en otras ciencias.
Desde tiempos muy remotos se hanestudiado problemas de optimización. Pues basta con
que nos fijemos en la obra denominada “Elementos”, escrita por el matemático griego Euclides,
que hacía referencia a la menor y mayor recta que puede ser trazada a una circunferencia desde un
punto exterior, o la forma de hallar el paralelogramo de área máxima, estando fijado su perímetro.
También se estudiaron posteriormente problemas deoptimización con el desarrollo del Cálculo
Infinitesimal y el Cálculo de Variaciones (siglos XVII y XVIII), por matemáticos como Leibnitz,
Newton o Bernoulli.
Sin embargo, es a partir de la Revolución Industrial, cuando surgen nuevos problemas de
optimización, que conlleva también la aparición de nuevas técnicas. Así por ejemplo, Leonid
Vitalevich Kantarovitch publicó “Métodos matemáticos deorganización y planificación de la
producción” en la que por primera vez se plantean problemas de programación lineal.
Posteriormente, aparecerían otros problemas de optimización, como el problema de transporte o el
problema de régimen alimenticio optimo. Paralelamente a la aparición y desarrollo de problemas
de optimización, se han desarrollado técnicas de computación que han hecho posible laresolución
y simplificación de algunos de estos problemas.
Una de las primeras aplicaciones de la programación lineal fue el puente aéreo de Berlín 1.
En 1947, George Bernard Dantzig formula, en términos matemáticos precisos, _(método
del simplex) el enunciado al que se debe reducir todo problema de programación lineal. Dantzig.
Los fundamentos matemáticos de la programación lineal se deben almatemático norteamericano
de origen húngaro John von Neumann (1903-1957), que publicó la teoría de juegos.

1 A mediados de 1948, la U.R.S.S. bloqueó las comunicaciones terrestres en poder de los aliados, que se plantearon
dos posibilidades: romper el bloqueo terrestre por la fuerza, o llegar a Berlín por el aire.
Se adoptó la segunda decisión utilizando un modelo de programación lineal,organizando de forma efectiva el
abastecimiento aéreo y terrestre: en diciembre de 1948 se estaban transportando 4500 toneladas diarias; en marzo de
1949, se llegó a las 8000 toneladas, tanto como se transportaba por carretera y ferrocarril antes del corte de las
comunicaciones.

Programación lineal – Matemáticas Aplicadas a las Ciencias Sociales II

2

Inecuaciones lineales. Interpretacióngeométrica.
Una inecuación lineal es de la forma
a xb yc≥0

o

a xb yc≤0

Además, una inecuación lineal, geométricamente representa el conjunto de puntos de uno de
los dos semiplanos en los que la recta de la ecuación a xb yc=0 divide el plano
# Ejemplo.- Gráficamente el conjunto 3 x2 y – 12≤0 es

Sistema de inecuaciones lineales. Interpretación geométrica.
Un sistema deinecuaciones lineales representa geométricamente un conjunto de puntos que
cumplen todas las inecuaciones (recinto) que puede ser acotada o no
# Ejemplos.
Gráficamente el conjunto de puntos que verifica
3 x2 y – 12≤0
x− y−2=0
es el conjunto de puntos de intersección de las dos regiones (verde y azul)

que no está acotado.

Programación lineal – Matemáticas Aplicadas a las Ciencias SocialesII

3

Gráficamente el conjunto de puntos que verifica

x2 y≤10
x y≥2
x≤8
x≥0
y≥0

Q

es el conjunto encerrado en el pentágono irregular. Además el valor de d¡cada uno de los
vértices del recinto, se puede obtener resolviendo el sistema formado por cada par de ecuaciones
de las rectas; así por ejemplo resolviendo el sistema { x = 8 ; x + 2 y = 10 } se obtiene el vértice
del...