Investigación operativa: formulación de problemas lineales y resolución gráfica

1. La pregunta

Un taller tiene 200 horas de máquina, 150 kg de acero y tres productos que puede fabricar, cada uno con su margen y su consumo de recursos. ¿Cuánto fabrica de cada uno?

Nadie resuelve esto derivando: la respuesta no está donde una pendiente se anula, sino en una esquina del conjunto de planes factibles. La investigación operativa es la disciplina que convierte ese tipo de problema en un modelo resoluble, y la programación lineal su herramienta central. Este tema enseña lo más difícil y lo que menos se practica: traducir un enunciado en un modelo.

2. Intuición

La investigación operativa nació en la Segunda Guerra Mundial para decidir cómo asignar recursos escasos —convoyes, radares, aviones— y desde entonces se aplica a logística, producción, dietas, carteras y turnos.

La estructura es siempre la misma:

• Hay unas decisiones que tomar: cuánto producir de cada cosa.
• Hay un criterio para saber si un plan es mejor que otro: normalmente maximizar beneficio o minimizar coste.
• Hay unos límites que no se pueden rebasar: recursos, capacidades, obligaciones.

Cuando el criterio y los límites son lineales —el doble de producción consume el doble de recurso y da el doble de beneficio— el problema se llama de programación lineal y tiene una propiedad extraordinaria: la solución está siempre en una esquina del conjunto factible.

Eso ya se demostró en el tema 9: el conjunto factible es un poliedro convexo, y una función lineal alcanza su óptimo en un vértice. Con dos variables se puede ver directamente en un dibujo, y eso es lo que hace la resolución gráfica.

Y aquí conviene ser honesto: el método gráfico solo sirve para dos variables. Su valor no es práctico, es pedagógico. Todo lo que el símplex del tema 16 hará a ciegas con números se entiende primero viéndolo en el plano.

3. Formalización

Estructura de un problema lineal

$$\max z=c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n$$ $$\text{sujeto a}\{\begin{array}{l}{a}_{11}{x}_1+\cdots +a_{1n}{x}_n\le b_1\\ ⋮\\ a_{m1}{x}_1+\cdots +a_{mn}{x}_n\le b_m\\ x_1,\dots ,x_n\ge 0\end{array}$$

o en forma matricial, con la notación del tema 6:

$$\max z={\mathbf{c}}^{\top }\mathbf{x}\text{s.a.}\mathbf{Ax}\le \mathbf{b},\mathbf{x}\ge 0$$

Los elementos:

Elemento	Significado
$\mathbf{x}$	variables de decisión: lo que se decide
$\mathbf{c}$	coeficientes de la función objetivo: márgenes o costes unitarios
$\mathbf{A}$	coeficientes técnicos: consumo de cada recurso por unidad
$\mathbf{b}$	términos independientes: disponibilidad de cada recurso
$z$	valor de la función objetivo

Las restricciones $\mathbf{x}\ge 0$ son las de no negatividad, y se escriben siempre aparte porque el símplex las trata de forma distinta.

Hipótesis del modelo lineal

Conviene saber qué se está suponiendo, porque a veces no se cumple:

• Proporcionalidad. Doblar una actividad dobla su aporte al objetivo y su consumo de recursos. No hay descuentos por volumen ni costes fijos de puesta en marcha.
• Aditividad. Los efectos de las actividades se suman, sin interacciones.
• Divisibilidad. Las variables pueden tomar valores fraccionarios. Si eso no tiene sentido —no se fabrican 3,7 autobuses— hace falta programación entera, que es otro problema y bastante más difícil.
• Certidumbre. Todos los coeficientes se conocen con exactitud. Como en la práctica no es así, se hace análisis de sensibilidad (tema 19).

Cómo formular: los tres pasos

1. Definir las variables de decisión con precisión. Es el paso decisivo y donde más se falla. No basta con «producción de sillas»: hay que escribir

$x_1$ = número de sillas fabricadas por semana

con su unidad y su periodo. Un modelo con variables mal definidas no se puede interpretar aunque se resuelva bien.

2. Escribir la función objetivo. ¿Qué se maximiza o minimiza, y en qué unidades? Cuidado con incluir costes fijos: no afectan a la decisión y solo estorban.

3. Escribir una restricción por cada límite. Para cada recurso: lo que se consume $\le$ lo que hay. Conviene revisar la coherencia de unidades de cada restricción: si un lado está en horas y el otro en kilos, hay un error.

Restricciones que se olvidan a menudo: demanda máxima de mercado, producción mínima comprometida por contrato, proporciones obligatorias entre productos, y por supuesto la no negatividad.

Formas de expresar restricciones frecuentes

Enunciado	Restricción
«Al menos el 30 % de la producción debe ser del tipo A»	$x_A\ge 0,3(x_A+x_B)$, o sea $0,7x_A-0,3x_B\ge 0$
«Por cada unidad de A hay que producir 2 de B»	$x_B=2x_A$
«No se pueden vender más de 40 unidades de A»	$x_A\le 40$
«La mezcla debe tener como mucho 5 % de grasa»	$g_A{x}_A+g_B{x}_B\le 0,05(x_A+x_B)$

Las de porcentaje siempre hay que pasarlas a forma lineal moviendo todo a un lado: en la forma original no lo parecen, pero lo son.

Resolución gráfica (dos variables)

1. Dibujar cada restricción como una recta (sustituyendo $\le$ por $=$) y determinar de qué lado queda la región válida. Truco: probar el punto $(0,0)$; si lo cumple, la región es la que lo contiene.
2. La intersección de todas las regiones es el conjunto factible.
3. Localizar los vértices resolviendo los sistemas de dos restricciones y descartando los puntos no factibles.
4. Evaluar $z$ en cada vértice y quedarse con el mejor.

Alternativa al paso 4: dibujar una recta de nivel de la función objetivo, $c_1{x}_1+c_2{x}_2=k$, y desplazarla paralelamente en el sentido de crecimiento hasta el último punto de contacto con la región. Es más rápido si hay muchos vértices, y hace visible por qué el óptimo es una esquina.

Casos especiales, que hay que reconocer

• Solución única: la recta de nivel toca en un solo vértice.
• Soluciones múltiples: la recta de nivel es paralela a una restricción activa. Entonces todo el segmento entre dos vértices es óptimo, con el mismo valor de $z$.
• No acotado: la región es infinita en la dirección de mejora y $z$ crece sin límite. En un problema real significa que falta una restricción.
• Infactible: las restricciones se contradicen y el conjunto factible es vacío.

Estos cuatro casos se estudiarán algebraicamente en el tema 17; aquí se reconocen a la vista.

4. Ejemplo económico resuelto

Problema. Una carpintería fabrica mesas y estanterías. Cada mesa requiere 4 horas de carpintería y 2 de acabado; cada estantería, 3 horas de carpintería y 1 de acabado. Se dispone de 240 horas de carpintería y 100 de acabado a la semana. El margen es de 70 € por mesa y 50 € por estantería. Además, por contrato hay que fabricar al menos 20 estanterías.

Paso 1. Variables de decisión.

$x_1$ = mesas fabricadas por semana $x_2$ = estanterías fabricadas por semana

Paso 2. Función objetivo.

$$\max z=70x_1+50x_2\text{(euros de margen semanal)}$$

Paso 3. Restricciones.

$$\{\begin{array}{ll}4x_1+3x_2\le 240& \text{(carpinterıˊa, horas)}\\ 2x_1+x_2\le 100& \text{(acabado, horas)}\\ x_2\ge 20& \text{(compromiso contractual)}\\ x_1\ge 0,x_2\ge 0& \end{array}$$

Comprobación de unidades: en la primera, $\text{h/mesa}\times \text{mesas}=\text{horas}$, y el lado derecho son horas. Correcto.

Paso 4. Encontrar los vértices. Con dos variables, cada vértice es el corte de dos restricciones activas. Las candidatas son las cuatro rectas: $4x_1+3x_2=240$, $2x_1+x_2=100$, $x_2=20$, $x_1=0$.

Corte $x_1=0$ con $x_2=20$: punto $(0,20)$. Comprobar: $60\le 240✓$, $20\le 100✓$. Vértice A.

Corte $x_1=0$ con carpintería: $3x_2=240⟹(0,80)$. Comprobar acabado: $80\le 100✓$; $x_2=80\ge 20✓$. Vértice B.

Corte carpintería con acabado:

$$\{\begin{array}{l}4x_1+3x_2=240\\ 2x_1+x_2=100\end{array}$$

De la segunda, $x_2=100-2x_1$. Sustituyendo:

$$4x_1+300-6x_1=240⟹-2x_1=-60⟹x_1=30,x_2=40$$

Comprobar: $x_2=40\ge 20✓$. Vértice C: $(30,40)$.

Corte acabado con $x_2=20$: $2x_1+20=100⟹x_1=40$. Comprobar carpintería: $160+60=220\le 240✓$. Vértice D: $(40,20)$.

Corte carpintería con $x_2=20$: $4x_1+60=240⟹x_1=45$. Comprobar acabado: $90+20=110>100$. No factible, se descarta.

Paso 5. Evaluar la función objetivo.

Vértice	$x_1$	$x_2$	$z=70x_1+50x_2$
A	0	20	1000
B	0	80	4000
C	30	40	2100 + 2000 = 4100
D	40	20	2800 + 1000 = 3800

Paso 6. Solución.

$$x_1^{\ast }=30\text{ mesas},x_2^{\ast }=40\text{ estanterıˊas},z^{\ast }=4100\text{ €}$$

Paso 7. Leer el resultado. ¿Qué recursos se agotan en el óptimo?

$$\text{Carpinterıˊa: }4(30)+3(40)=120+120=240=240\text{agotada}$$ $$\text{Acabado: }2(30)+40=100=100\text{agotada}$$ $$\text{Contrato: }40\ge 20\text{holgura de 20 estanterıˊas}$$

Los dos recursos productivos se agotan por completo y el compromiso contractual sobra. Esa información —qué ata y qué no— es la misma que daban los multiplicadores de Kuhn-Tucker en el tema 14, y es la que la dualidad del tema 18 convertirá en precios.

Anticipo útil. Como los dos recursos productivos están agotados, ampliar cualquiera de los dos aumentaría el beneficio; ampliar el compromiso contractual, no. Cuánto exactamente es lo que responderá el análisis de sensibilidad.

5. Errores típicos

Definir mal las variables. «Sillas» no es una variable; «número de sillas fabricadas por semana» sí. Sin unidad y sin periodo, el resultado no se puede interpretar ni comprobar.

Confundir coeficientes técnicos con disponibilidades. Los $a_{ij}$ son consumo por unidad; los $b_i$, el total disponible. Meter un total en la matriz de coeficientes es un error que da resultados absurdos y difíciles de detectar.

Olvidar la no negatividad. Sin ella, el modelo puede «producir» cantidades negativas para generar recursos de la nada, y la solución es un disparate.

Dejar restricciones de porcentaje sin linealizar. «Al menos el 30 % debe ser A» hay que escribirlo como $0,7x_A-0,3x_B\ge 0$, con todas las variables a la izquierda.

Incluir costes fijos en la función objetivo. No cambian la solución óptima —solo desplazan $z$ en una constante— y ensucian la interpretación. Se suman al final si hace falta el beneficio total.

Dar por vértice un corte no factible. Cada punto candidato debe cumplir todas las restricciones, no solo las dos que lo generan. En el ejemplo, uno de los cinco cortes se descartó por eso.

Confundir maximizar con minimizar al desplazar la recta de nivel. Para maximizar se desplaza en el sentido en que crece $z$; conviene comprobarlo evaluando dos puntos.

Creer que el método gráfico escala. Con tres variables el dibujo ya es incómodo y con cuatro imposible. Sirve para entender, no para trabajar.

6. Ejercicios

Ejercicio 1 · Formular un problema de producción

básico

Una fábrica produce dos tipos de pintura, interior y exterior. Cada litro de interior necesita 1 kg de pigmento A y 2 kg de B; cada litro de exterior, 2 kg de A y 1 kg de B. Hay 24 kg de A y 18 kg de B. El beneficio es 5 €/litro de interior y 4 €/litro de exterior. Formula el problema.

Ver solución

Variables:

$x_1$ = litros de pintura interior producidos $x_2$ = litros de pintura exterior producidos

Objetivo:

$$\max z=5x_1+4x_2\text{(euros)}$$

Restricciones:

$$\{\begin{array}{ll}{x}_1+2x_2\le 24& \text{(pigmento A, kg)}\\ 2x_1+x_2\le 18& \text{(pigmento B, kg)}\\ x_1,x_2\ge 0& \end{array}$$

Comprobación de unidades: en la primera, kg de A por litro $\times$ litros $=$ kg de A. Coherente con el lado derecho.

Nótese que los coeficientes de la matriz $\mathbf{A}$ son $\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right)$: cada columna corresponde a un producto y cada fila a un recurso. Esa disposición es la que espera el símplex.

Ejercicio 2 · Resolver gráficamente

básico

Resuelve el problema del ejercicio 1.

Ver solución

Vértices:

$(0,0)$: factible. $z=0$.

$x_1=0$ con pigmento A: $2x_2=24⟹(0,12)$. Comprobar B: $12\le 18✓$. $z=48$.

$x_2=0$ con pigmento B: $2x_1=18⟹(9,0)$. Comprobar A: $9\le 24✓$. $z=45$.

Corte de las dos restricciones:

$$\{\begin{array}{l}{x}_1+2x_2=24\\ 2x_1+x_2=18\end{array}$$

Multiplicando la primera por 2 y restando la segunda: $4x_2-x_2=48-18⟹3x_2=30⟹x_2=10$, y $x_1=24-20=4$. Punto $(4,10)$. $z=20+40=60$.

$x_2=0$ con A: $(24,0)$ incumple B ($48>18$). Descartado. $x_1=0$ con B: $(0,18)$ incumple A ($36>24$). Descartado.

Vértice	$z$
$(0,0)$	0
$(0,12)$	48
$(4,10)$	60
$(9,0)$	45

Óptimo: 4 litros de interior y 10 de exterior, con 60 € de beneficio. Los dos pigmentos se agotan: $4+20=24$ y $8+10=18$.

Ejercicio 3 · Problema de dieta con restricción de proporción

medio

Un ganadero mezcla dos piensos. El pienso A cuesta 0,30 €/kg y aporta 20 g de proteína y 5 g de fibra por kg; el B cuesta 0,45 €/kg y aporta 30 g de proteína y 15 g de fibra. Cada ración diaria debe tener al menos 240 g de proteína y al menos 90 g de fibra. Además, el pienso B no puede superar el 60 % de la mezcla.

Formula el problema de coste mínimo y resuélvelo gráficamente.

Ver solución

Variables: $x_A$, $x_B$ = kg de cada pienso por ración.

Objetivo:

$$\min z=0,30x_A+0,45x_B$$

Restricciones:

$$\{\begin{array}{ll}20x_A+30x_B\ge 240& \text{(proteıˊna, g)}\\ 5x_A+15x_B\ge 90& \text{(fibra, g)}\\ x_B\le 0,6(x_A+x_B)& \text{(proporcioˊn)}\\ x_A,x_B\ge 0& \end{array}$$

Linealizar la tercera:

$$x_B\le 0,6x_A+0,6x_B⟹0,4x_B\le 0,6x_A⟹2x_B\le 3x_A$$

o bien $3x_A-2x_B\ge 0$.

Simplificamos las dos primeras dividiendo por 10 y por 5:

$$2x_A+3x_B\ge 24,x_A+3x_B\ge 18$$

Vértices. La región es no acotada por arriba (siempre se puede echar más pienso), así que buscamos los vértices de su frontera inferior.

Corte proteína–fibra: restando la segunda de la primera: $x_A=6$, y de la segunda $3x_B=12⟹x_B=4$. Punto $(6,4)$. Comprobar proporción: $3(6)-2(4)=18-8=10\ge 0✓$. Vértice P. $z=1,80+1,80=3,60$.

Corte proteína–proporción:

$$\{\begin{array}{l}2x_A+3x_B=24\\ 3x_A-2x_B=0\end{array}$$

De la segunda, $x_A=\frac{2}{3}{x}_B$. Sustituyendo: $\frac{4}{3}{x}_B+3x_B=24⟹\frac{13}{3}{x}_B=24⟹x_B=5,538$, y $x_A=3,692$. Comprobar fibra: $3,692+3(5,538)=3,692+16,615=20,31\ge 18✓$. Vértice Q. $z=1,108+2,492=3,60$.

Corte fibra con $x_B=0$: $x_A=18$. Comprobar proteína: $36\ge 24✓$; proporción $✓$. Vértice R. $z=5,40$.

Pero antes hay que ver si el corte proteína–$x_B=0$ ($x_A=12$) es factible: fibra $12<18$, no. Se descarta.

Vértice	$x_A$	$x_B$	$z$
Q	3,692	5,538	3,60
P	6	4	3,60
R	18	0	5,40

Soluciones múltiples. Dos vértices dan el mismo coste mínimo de 3,60 €, así que todo el segmento entre P y Q es óptimo.

Por qué. La recta de nivel del objetivo, $0,30x_A+0,45x_B=k$, tiene pendiente $-0,30/0,45=-2/3$. La restricción de proteína, $2x_A+3x_B=24$, tiene pendiente $-2/3$. Son paralelas, y por eso la recta de nivel se apoya sobre todo un lado del poliedro en lugar de tocar un vértice.

Lectura económica. Los dos piensos tienen exactamente la misma relación precio/proteína ($0,30/20=0,015$ y $0,45/30=0,015$ €/g). Al ganadero le da igual cualquier mezcla del segmento, y puede elegir por otro criterio —disponibilidad, plazo de entrega, sabor— sin coste alguno.

Ejercicio 4 · Diagnóstico: un modelo que se comporta mal

avanzado

Un consultor plantea el siguiente modelo para una empresa que fabrica dos productos:

$$\max z=30x_1+20x_2$$$$\text{s.a.}{x}_1-x_2\le 10,-2x_1+3x_2\le 15,x_1,x_2\ge 0$$

1. Resuélvelo gráficamente y explica qué ocurre.
2. Diagnostica el error de modelización.
3. Propón la corrección y resuelve.

Ver solución

1. Los vértices de la región:

$(0,0)$: factible, $z=0$. $x_1=0$ con la segunda: $3x_2=15⟹(0,5)$. Comprobar la primera: $-5\le 10✓$. $z=100$. $x_2=0$ con la primera: $(10,0)$. Comprobar la segunda: $-20\le 15✓$. $z=300$. Corte de las dos:

$$\{\begin{array}{l}{x}_1-x_2=10\\ -2x_1+3x_2=15\end{array}$$

De la primera $x_1=10+x_2$; sustituyendo: $-20-2x_2+3x_2=15⟹x_2=35$, $x_1=45$. $z=1350+700=2050$.

Pero probemos a seguir creciendo: el punto $(100,90)$ cumple $100-90=10\le 10$ y $-200+270=70>15$. No vale. Probemos $(1000,500)$: $500>10$. No vale. Probemos $(60,45)$: $15>10$. No.

Busquemos una dirección de crecimiento admisible. Un desplazamiento $(d_1,d_2)$ es admisible desde un punto factible si $d_1-d_2\le 0$ y $-2d_1+3d_2\le 0$, es decir, $d_2\ge d_1$ y $d_2\le \frac{2}{3}{d}_1$. Con $d_1>0$ ambas exigen $d_1\le d_2\le \frac{2}{3}{d}_1$, imposible. Con $d_1=d_2=0$ no hay movimiento.

Probemos $d_1=3,d_2=2$: $3-2=1>0$, viola la primera. Y $d_1=d_2=1$: $0\le 0✓$ y $-2+3=1>0$, viola la segunda.

La región está acotada y el óptimo es $(45,35)$ con $z=2050$.

2. El diagnóstico. El problema no es que no tenga solución, sino que las restricciones no representan recursos. Los coeficientes negativos ($-2$ en la segunda, $-1$ en la primera) significarían que producir $x_2$ genera recurso en lugar de consumirlo, lo cual no describe ninguna tecnología de producción.

Además, en el óptimo se producen 45 y 35 unidades sin que aparezca ningún límite de capacidad, horas o materia prima: el modelo no tiene ninguna restricción de recurso escaso. Las dos que hay son restricciones de proporción mal escritas.

Lo más probable es que el consultor quisiera expresar «la diferencia entre productos no puede superar 10 unidades» y «$x_2$ no puede superar cierta proporción», y haya olvidado por completo las restricciones de capacidad.

3. Corrección. Supongamos que el taller tiene 200 horas y que cada unidad de $x_1$ consume 4 h y cada una de $x_2$, 5 h. El modelo corregido:

$$\max z=30x_1+20x_2$$$$\text{s.a.}4x_1+5x_2\le 200,x_1-x_2\le 10,x_1,x_2\ge 0$$

Vértices:

$(0,0)$: $z=0$. $(0,40)$ (horas con $x_1=0$): comprobar $0-40=-40\le 10✓$. $z=800$. $(10,0)$ (segunda con $x_2=0$): $40\le 200✓$. $z=300$. Corte de las dos: $x_1=10+x_2$, luego $4(10+x_2)+5x_2=200⟹9x_2=160⟹x_2=17,78$, $x_1=27,78$. $z=833,3+355,6=1188,9$. $(50,0)$ (horas con $x_2=0$): comprobar $50-0=50>10$. No factible.

Vértice	$z$
$(0,0)$	0
$(0,40)$	800
$(27,78;17,78)$	1188,9
$(10,0)$	300

Óptimo: $x_1=27,78$, $x_2=17,78$, con $z=1188,90$ €. Las horas se agotan ($111,1+88,9=200$) y la restricción de diferencia también está activa ($27,78-17,78=10$).

La lección. Un modelo de programación lineal puede resolverse perfectamente y ser un disparate. Comprobar que cada restricción representa algo real y que las unidades cuadran es parte del trabajo, no un formalismo. La señal de alarma aquí eran los coeficientes negativos en lo que debían ser consumos de recursos.

7. Qué desbloquea

Necesitas antes:

• Espacios vectoriales y conjuntos convexos — tema 9

Te abre la puerta a:

• El algoritmo símplex: conceptos, teoremas fundamentales y funcionamiento — tema 16

8. Recursos externos

• OCW UPV/EHU — Investigación Operativa. Programación Lineal, Tema 1. Modelos lineales y solución gráfica; es el encaje más exacto con 21.411 y termina con una colección de problemas resueltos.
• OCW Unizar — Modelos de Investigación Operativa. Formulación de problemas lineales con casos de producción y mezclas, y pruebas de evaluación resueltas.
• OCW UC3M — Investigación Operativa. Temario de contraste, útil para ver los mismos conceptos con otra notación.
• LINDO. La versión gratuita resuelve estos problemas en segundos. Conviene usarla para comprobar los resultados hechos a mano, no para sustituirlos: lo que se evalúa es la formulación.
• Gnuplot. Dibujar la región factible del ejemplo: plot [0:60] (240-4*x)/3, 100-2*x, 20.