En infinidad de aplicaciones de la industria, la economía, la estrategia militar, etc.. se presentan situaciones en las que se exige maximizar o minimizar algunas fucniones que se encuentran sujetas a determinadas limitaciones, que llamaremos restricciones.

Para hacernos una idea más clara de estos supuestos, veamos dos ejemplos:

Ejemplo 1: Problema de máximos.
En una granja se preparan dos clases de piensos, P y Q, mezclando dos productos A y B. Un saco de P contiene 8 kg de A y 2 de B, y un saco de Q contiene 10 kg de A y 5 de B. Cada saco de P se vende a 300 ptas. y cada saco de Q a 800 ptas. Si en la granja hay almacenados 80 kg de A y 25 de B, ¿cuántos sacos de cada tipo de pienso deben preparar para obtener los máximos ingresos?

Ejemplo 2: Problema de mínimos.
Una campaña para promocionar una marca de productos lácteos se basa en el reparto gratuito de yogures con sabor a limón o a fresa. Se decide repartir al menos 30000 yogures.
Cada yogur de limón necesita para su elaboración 0.5 gramos de un producto de fermentación y cada yogur de fresa necesita 0.2 gramos de este mismo producto. Se dispone de 9 kilogramos de este producto para fermentación.
El coste de producción de un yogur de limón es de 30 pesetas y 20 pesetas uno de fresa.

En los dos ejemplos descritos está claro que tanto la cantidad que deseamos maximizar como la cantidad que deseamos minimizar podemos expresarlas en forma de ecuaciones lineales. Por otra parte, las restricciones que imponen las condiciones de ambos problemas se pueden expresar en forma de inecuaciones lineales.

Tratemos de plantear en términos matemáticos los dos ejemplos anteriores:

1) Si designamos por x al número de sacos de pienso de clase P y por y el número de sacos de pienso de clase Q que se han de vender, la función : Z = 300x + 800y representará la cantidad de pesetas obtenidas por la venta de los sacos, y por tanto es la que debemos maximizar.
Podemos hacer un pequeño cuadro que nos ayude a obtener las restricciones:

	Nº	kg de A	kg de B
P	x	8x	2x
Q	y	10y	5y
		80	25

Por otra parte, las variables x e y, lógicamente, han de ser no negativas, por tanto : x 0, y 0
Conjunto de restricciones:

8x + 10y 80

2x + 5y 25

x 0, y 0

2) Si representamos por x el número de yogures de limón e y al número de yogures de fresa, se tiene que la fución de coste es Z = 30x + 20y.
Por otra parte, las condiciones del problema imponen las siguientes restricciones:

• De número : x + y 80
• De fermentación: 0.5x + 0.2y 9000
• Las variables x e y han de ser, lógicamente, no negativas; es decir: x 0, y 0

Conjunto de restricciones:

x + y 80

0.5x + 0.2y 9000

x 0, y 0

En definitiva:

Un problema de programación lineal en dos variables, tiene la siguiente formulación estándar:

puediendo cambiarse maximizar por minimizar, y el sentido de las desigualdades.

En un problema de programación lineal intervienen:

• La función f(x,y) = ax + by + c llamada función objetivo y que es necesario optimizar. En esa expresión x e y son las variables de decisión, mientras que a, b y c son constantes.

• Las restricciones que deben ser inecuaciones lineales. Su número depende del problema en cuestión. El carácter de desigualdad viene impuesto por las limitaciones, disponibilidades o necesidades, que son: inferiores a ... ( menores: < o ); como mínimo de ... (mayores: > o ) . Tanto si se trata de maximizar como de minimizar, las desigualdades pueden darse en cualquiera de los dos sentidos.

• Al conjunto de valores de x e y que verifican todas y cada una de las restricciones se lo denomina conjunto (o región ) factible. Todo punto de ese conjunto puede ser solución del problema; todo punto no perteneciente a ese conjunto no puede ser solución. En el apartado siguiente veremos como se determina la región factible.

• La solución óptima del problema será un par de valores (x_0, y₀) del conjunto factible que haga que f(x,y) tome el valor máximo o mínimo.

En ocasiones utilizaremos las siglas PPL para indicar problema de programación lineal.