Matemáticas

Programación lineal

Formulación algebraica, función objetivo, restricciones, región factible, optimización por método algebraico y gráfico, problemas de transporte.

Se llama programación lineal a la formulación algebraica que pretende optimizar (maximizar o minimizar) una función lineal de varias variables, denominada función objetivo:

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

sujeta a restricciones, formuladas en inecuaciones lineales:

\begin{cases} a_1 x + b_1 y \leq \geq c_1 \\ a_2 x + b_2 y \leq \geq c_2 \\ \quad \vdots \qquad \vdots \qquad \vdots \\ a_n x + b_n y \leq \geq c_n \end{cases}

La representación de la región que cumple las inecuaciones recibe el nombre de región factible

Teorema fundamental de la programación lineal:
Si existe una solución única que optimice la función objetivo, esta se encuentra en un punto extremo (vértice) de la región factible

Ejemplo: Una industria produce queso en envases de 100 y 300 gramos, con un beneficio por envase de 0,50 € y 1,40 € respectivamente. Cada día dispone de 2400 kg de queso para envasar, aunque no puede producir más de 15000 envases pequeños. Además, el número de envases de 100 gr debe ser mayor o igual al de 300 gr. Se pide encontrar el punto de máximo beneficio.

1) Definimos las variables y la función objetivo:
x = nº de envases de 100 gr (0,1 Kg)
y = nº de envases de 300 gr (0,3 Kg)

Función objetivo:

B(x,y)=0,5x+1,4y

2) Organizamos la información en una tabla de datos

	Nº envases	Kg. queso	Beneficio
Envases 100 gr	x	0,1 x	0,5 x
Envases 300 gr	y	0,3 y	1,4 y
Restricciones	x ≤ 15000 x ≥ y	≤ 2400

3) Sistema de inecuaciones de las restricciones

\begin{cases} 0,1x + 0,3y \leq 2400 \\ x \leq 15000 \\ x \geq y \end{cases}

4) Representar la región factible

5) Encontramos los puntos vértice

\begin{aligned} A &= \begin{cases} 0,1x + 0,3y = 2400 \\ x = y \end{cases} & A &= (6000, 6000) \\ B &= \begin{cases} 0,1x + 0,3y = 2400 \\ x = 15000 \end{cases} & B &= (15000, 3000) \\ C &= \begin{cases} x = 15000 \\ y = 0 \end{cases} & C &= (15000, 0) \end{aligned}

Resolución por el método algebraico

6) Aplicamos cada punto vértice en la función objetivo para encontrar el valor óptimo:

\begin{aligned} B(6000, 6000) &= 0,5 \cdot 6000 + 1,4 \cdot 6000 = 11400 \\ B(15000, 3000) &= 0,5 \cdot 15000 + 1,4 \cdot 3000 = 11700 \\ B(15000, 0) &= 0,5 \cdot 15000 + 1,4 \cdot 0 = 7500 \end{aligned}

Resolución por el método gráfico

6) Se dibujan las rectas de nivel asociadas a la función objetivo

\displaystyle 0,5x+1,4y=k

Se dibuja una recta cualquiera, por ejemplo

0,5x+1,4y=0

, y se trazan paralelas hasta encontrar el vértice óptimo. Si se quiere maximizar será el punto que toca la recta más a la derecha y si se quiere minimizar será el punto que toca la recta más a la izquierda

7) Expresión del resultado:
El punto de fabricación óptimo es 15.000 envases de 100 gr y 3.000 envases de 300 gr, con un beneficio de 11.700 €

Una fábrica de jamones tiene dos secaderos A y B que producen 50 y 80 jamones por mes. Se distribuyen a tres tiendas M, N y O cuya demanda es 35, 50 y 45 respectivamente, con coste de transporte por jamón según la tabla siguiente:

	M	N	O
Secadero A	5	6	8
Secadero B	7	4	2

Calcular la distribución para que el coste sea mínimo.

1) Las restricciones están interrelacionadas, se definen las variables arbitrariamente. Tomaremos:
x = jamones a enviar del secadero A a la tienda M
y = jamones a enviar del secadero A a la tienda N

2) Organizamos la información en una tabla de datos

	M	N	O
Demanda	35	50	45
Secadero A - 50	x	y	50 - x - y
Secadero B - 80	35 - x	50 - y	45 - (50 - x - y)
Coste	5x + 7(35 - x)	6y + 4(50 - y)	8(50 - x - y) + 2(x + y - 5)

La función objetivo es la suma de todos los costes:

C(x,y) = 835 - 8x - 4y

3) Las restricciones se deducen de tener en cuenta que todas las cantidades son positivas:

\begin{cases} x \geq 0 \\ y \geq 0 \\ 50 - x - y \geq 0 \\ 35 - x \geq 0 \\ 50 - y \geq 0 \\ x + y - 5 \geq 0 \end{cases}

Programación lineal

Programación lineal

Problema de programación lineal

Problema de transporte. Planteamiento