Programación lineal

Imagina que un taller produce dos tipos de productos y que las restricciones de tiempo y materiales generan la región factible

$$x+y\le 4,\qquad x+2y\le 6,\qquad x\ge 0,\ y\ge 0.$$

Hay muchos pares $(x,y)$ posibles. Por ejemplo:

• $(0,0)$: no producir nada.
• $(4,0)$: producir 4 unidades del primer tipo y 0 del segundo.
• $(0,3)$: producir 0 unidades del primer tipo y 3 del segundo.
• $(2,2)$: producir 2 de cada tipo.

Todos cumplen las restricciones, pero si cada unidad del primer tipo deja $5$ soles y cada unidad del segundo deja $3$ soles, no todos generan la misma ganancia:

$$G(x,y)=5x+3y.$$

La programación lineal se encarga de responder: de todos los puntos posibles, ¿cuál hace que $G(x,y)$ sea máxima o mínima?

La expresión que se desea maximizar o minimizar recibe el nombre de función objetivo.

Un problema de programación lineal con dos variables tiene esta forma general:

$$\text{Optimizar } f(x,y)=ax+by$$

sujeto a restricciones:

$$\begin{cases} a_1x+b_1y\le c_1,\\ a_2x+b_2y\ge c_2,\\ \ \ \ \ \ \vdots\\ a_nx+b_ny\le c_n,\\ x\ge 0,\ y\ge 0. \end{cases}$$

Aquí, optimizar significa maximizar o minimizar.

Definiciones básicas

• Variables de decisión: $x$ y $y$, que representan cantidades del problema.
• Función objetivo: $f(x,y)=ax+by$, la expresión que se desea maximizar o minimizar.
• Restricciones: las inecuaciones lineales que limitan los valores permitidos de $x$ y $y$.
• Condición de no negatividad: $x\ge 0$, $y\ge 0$. En la mayoría de problemas aplicados, las variables representan cantidades que no pueden ser negativas.
• Región factible: el conjunto de todos los puntos $(x,y)$ que cumplen todas las restricciones a la vez.
• Punto factible: cualquier punto de la región factible.
• Solución óptima: el punto factible donde la función objetivo alcanza el máximo o el mínimo.
• Valor óptimo: el valor máximo o mínimo que toma la función objetivo en la solución óptima.

La región factible es la intersección de todos los semiplanos generados por las restricciones. Con dos variables, esta región suele ser un polígono.

Por ejemplo, para

$$\begin{cases} x+y\le 4,\\ x+2y\le 6,\\ x\ge 0,\ y\ge 0, \end{cases}$$

la región es el cuadrilátero de vértices

$$(0,0),\ (0,3),\ (2,2),\ (4,0).$$

En programación lineal, los candidatos más importantes son los vértices o puntos extremos. Un vértice es un punto de la región factible que está en la intersección de dos rectas frontera y que no se puede expresar como punto estrictamente interior de un segmento contenido en la región.

Dada

$$f(x,y)=ax+by,$$

si igualamos la función a un valor constante $k$, obtenemos

$$ax+by=k.$$

Esta es una recta. Al variar $k$, se generan rectas paralelas llamadas rectas de nivel.

Por ejemplo, para

$$f(x,y)=2x+3y,$$

algunas rectas de nivel son:

$$2x+3y=0,$$

$$2x+3y=6,$$

$$2x+3y=12.$$

Todas tienen la misma pendiente, $-\frac{2}{3}$, y son paralelas.

¿Para qué sirve esto? Sirve para entender por qué el óptimo se encuentra en un vértice: al desplazar las rectas de nivel en la dirección en la que la función crece, el último contacto con la región factible suele ocurrir en un vértice o, en algunos casos, a lo largo de todo un lado.

El vector

$$\vec{v}=(a,b)$$

indica la dirección en la que la función $f(x,y)=ax+by$ crece. Si se busca el máximo, se avanza en el sentido de $\vec{v}$; si se busca el mínimo, en sentido contrario.

El resultado central del tema es el siguiente:

Si un problema de programación lineal tiene región factible no vacía y su función objetivo alcanza un máximo o un mínimo, entonces ese valor óptimo se alcanza en al menos un vértice de la región factible.

Esto no quiere decir que el óptimo no pueda estar también en otros puntos. Si la función objetivo es paralela a un lado de la región factible, todos los puntos de ese lado pueden dar el mismo valor óptimo. Pero, en cualquier caso, también habrá un vértice que lo dé.

Justificación intuitiva

Si la función objetivo es

$$f(x,y)=ax+by,$$

y tomamos un punto interior de la región factible, normalmente podemos desplazarlo un poco en la dirección $(a,b)$ para aumentar el valor de $f$. Por lo tanto, un máximo no puede estar en el interior, salvo que $f$ sea constante, que no es lo habitual.

Luego, si el máximo está en la frontera, y la frontera está formada por segmentos de recta, sobre un segmento la función $ax+by$ también se comporta de manera lineal. Su máximo sobre ese segmento estará en uno de sus extremos, es decir, en un vértice.

Región factible acotada y no acotada

• Si la región factible es acotada y no vacía, entonces la función objetivo alcanza máximo y mínimo.
• Si la región factible es no acotada, puede ocurrir que exista mínimo, pero no máximo, o máximo, pero no mínimo, dependiendo de la dirección de crecimiento de la función objetivo.

Por ejemplo, si la región es

$$x+y\ge 4,\qquad x\ge 0,\ y\ge 0,$$

y se desea minimizar

$$f(x,y)=2x+3y,$$

el mínimo sí existe y ocurre en un vértice. En cambio, el máximo no existe, porque se puede hacer $x$ o $y$ tan grandes como se quiera y la función crecerá sin límite.

Este es el método más útil para problemas de admisión con dos variables.

Paso 1: Definir las variables

Lee el problema y escribe claramente qué representa cada variable.

Ejemplo breve:

• $x$: número de paquetes del primer tipo.
• $y$: número de paquetes del segundo tipo.

No pongas simplemente “$x=A$”. Es mejor definir con palabras.

Paso 2: Plantear la función objetivo

Identifica qué se desea maximizar o minimizar.

Si cada paquete del primer tipo se vende a $16$ soles y cada uno del segundo a $18$ soles, la función ingreso es

$$I(x,y)=16x+18y.$$

Paso 3: Traducir las limitaciones a inecuaciones

Construye una tabla si el problema tiene recursos. Por ejemplo:

Cada fila se convierte en una restricción.

Paso 4: Agregar la condición de no negatividad

En problemas de cantidades, siempre se agrega

$$x\ge 0,\qquad y\ge 0.$$

Paso 5: Graficar la región factible

Grafica cada recta frontera y determina el semiplano que corresponde a cada inecuación. La región común es la región factible.

Paso 6: Hallar todos los vértices

Los vértices se obtienen intersecando pares de rectas frontera. Generalmente son:

• La intersección con $x=0$.
• La intersección con $y=0$.
• Las intersecciones entre las rectas dadas.

Descarta los puntos que no cumplan todas las inecuaciones.

Paso 7: Evaluar la función objetivo en cada vértice

Sustituye cada vértice en $f(x,y)$ y compara.

Paso 8: Responder exactamente lo que pide el problema

No es lo mismo preguntar “¿cuál es la ganancia máxima?” que “¿cuántas unidades de cada producto se deben fabricar?”. La primera pide el valor óptimo; la segunda pide la solución óptima.

En los problemas de admisión, la dificultad no suele estar en la teoría, sino en traducir correctamente el enunciado.

Algunas expresiones frecuentes son:

Por ejemplo:

• “Se dispone, como máximo, de 10 horas de máquina” se traduce como

$$2x+3y\le 10.$$

• “La dieta debe contener al menos 20 gramos de proteína” se traduce como

$$4x+5y\ge 20.$$

1. Variables enteras

Muchos problemas de admisión trabajan con productos que no pueden partirse: paquetes, sacos, buses, personas, puertas, ventanas, etc.

La programación lineal básica se desarrolla en los números reales. Si el vértice óptimo resulta entero, no hay problema. Si un vértice óptimo tiene coordenadas fraccionarias y las variables deben ser enteras, no basta redondear. En ese caso habría que examinar los puntos enteros cercanos que estén dentro de la región factible.

En los problemas de admisión de la UNMSM, normalmente la solución óptima tiene coordenadas enteras, por lo que el método de vértices se aplica sin complicación adicional.

2. Maximizar un sobrante de dinero

Si un problema dice:

“Se dispone de $C$ soles y se desea saber cuánto dinero le queda como máximo después de comprar”

entonces el sobrante es

$$S = C-\text{gasto}.$$

Como $C$ es constante, maximizar $S$ equivale a minimizar el gasto. Esta trampa aparece con frecuencia.

3. Soluciones óptimas múltiples

Si la función objetivo es paralela a un lado de la región factible, puede haber infinitas soluciones óptimas.

Por ejemplo, si la región factible está limitada por

$$x+y\le 5$$

y se desea maximizar

$$f(x,y)=2x+2y,$$

cualquier punto sobre el lado $x+y=5$ da el mismo valor máximo:

$$f(x,y)=2(x+y)=10.$$

En este caso, todos los puntos de ese lado son solución óptima.

4. Región factible vacía

Si las restricciones son incompatibles, no existe región factible y el problema no tiene solución.

Ejemplo breve:

$$x+y\le 2,\qquad x+y\ge 4.$$

No puede haber un punto cuya suma sea a la vez menor o igual que 2 y mayor o igual que 4.