Ejemplo 2

Una compañía de ámbito nacional produce y distribuye una línea de neveras de alta eficiencia energética.

La empresa tiene líneas de producción y montaje en dos ciudades, Pamplona y Calahorra, y tres cadenas de distribución localizadas en Madrid, Barcelona y Logroño. La oficina de Madrid presenta una demanda anual de 10000 neveras, la de Logroño 4000 y la de Barcelona 13000.

La planta de Calahorra puede producir hasta 13000 neveras anuales y la de Pamplona 18000.

Los costes de transporte por unidad (en euros) son los mostrados en la siguiente tabla.

Se plantea un problema de programación lineal que minimiza los costes anuales de la compañía

Ejemplo 3

Un ganadero se quiere asegurar de que sus animales ingieren diariamente al menos 14 unidades de hierro, 12 de vitamina A y 18 de vitamina C

Un kilogramo de harina tiene un coste de 2€ y cuenta con 1 unidad de hierro, 1 de vitamina A y 3 de vitamina C. Un kilogramo de maíz tiene un coste de 3€ y contiene 2 unidades de hierro, 1 de vitamina A y 1 de vitamina C.

Determinad las posibles maneras de alimentar al ganado que satisfagan las necesidades mínimas alimenticias diarias con el mínimo coste posible

Ejemplo 4

Supongamos que una entidad bancaria necesita diariamente entre 10 y 20 cajeros en función de la hora del día. Las necesidades diarias se especifican en la siguiente tabla

Ejemplo 5

La oficina tiene 12 trabajadores a jornada completa y dispone de personal suficiente para trabajar a media jornada.

Un cajero que trabaja a media jornada debe estar operativo 4h al día y estar disponible para comenzar a trabajar a cualquier hora entre las 9:00 y las 13:00. Los trabajadores a jornada completa deben estar operativos desde las 9:00 hasta las 17:00 y tienen una hora libre para comer (la mitad come de 11:00 a 12:00 y la otra mitad de 12:00 a 13:00).

Las normas de la entidad limitan el número de horas realizadas por los trabajadores a tiempo parcial a, como mucho, el 50% de las horas diarias que se realicen. Nótese que se realizan 112 horas diarias. Estos trabajadores ganan 16€/día y los trabajadores a jornada completa 50€/día.

Plantead un problema de programación lineal que establezca un horario que minimiza los costes salariales del banco.

Ejemplo 6

Un banco invierte en crédito al consumo, bonos corporativos, depósitos de oro y préstamos de la construcción. Actualmente dispone de cinco millones de euros para invertir y pretende, por un lado maximizar el interés esperado para los próximos seis meses y por el otro, cumplir con la diversificación propugnada por la Junta Directiva según se especifica en la tabla siguiente.

La Directiva también exige que como mínimo un 55% de los fondos se dediquen a depósitos de oro y préstamos a la construcción, mientras que el porcentaje dedicado a los créditos al consumidor no han de superar el 15% de los fondos.

Se plantea un problema de programación lineal que optimice el objetivo del banco

Ejemplo 7

Una cadena nacional de locales de ocio dispone de 8000 euros semanales para publicidad. Este dinero se ha de destinar a publicar anuncios en TV, periódicos y dos emisoras de radio.

El objetivo final es conseguir la mayor audiencia posible. La tabla siguiente recoge toda la información referente a la audiencia esperada por anuncio, el coste en euros de cada anuncio y el número máximo de anuncios semanales posibles en cada medio.

La empresa también exige la contratación de un mínimo de 5 anuncios por radio semanales y no se puede destinar a este medio más de 1800 euros por semana.

Plantead un problema de programación lineal que optimice el objetivo de la empresa

Ejemplo 8

Se va a realizar una encuesta para determinar la opinión de los ciudadanos de las Islas Baleares sobre la inmigración. La encuesta ha de satisfacer lo siguiente:

1. Entrevistar a un mínimo de 2300 familias baleares
2. En al menos 1000 familias entrevistadas, la persona de más edad no debe superar los 30 años
3. En al menos 600 familias entrevistadas, la edad de la mayor persona ha de estar comprendida entre los 31 y los 50 años, ambos incluidos
4. El porcentaje de familias entrevistadas que pertenecen a zonas con alta tasa de inmigración no ha de ser inferior al 15% del total

Todas las encuestas deben hacerse personalmente y ha de responder la persona de más edad de cada familia

La siguiente tabla indica el coste (en euros) de cada encuesta según la edad del encuestado y si pertenece o no a una zona con tasa elevada de inmigración

Plantead el problema de programación lineal que satisface todas las condiciones de la encuesta y minimiza su coste

Ejemplo 9

Maximícese la función \(Z = 3x+y\) bajo las restricciones

\[\left\{\begin{matrix}-x+y\le 2\\ x+y\le 6\\ x\le 3\\ 2x-y\le 4\\ -y\le 0\\ -x-y\le -1\\ -x\le 0\end{matrix}\right.\]

Representad gráficamente la región factible. Ésta será la intersección de todos los semiplanos que determinen cada una de las restricciones.

Considerad las siguientes rectas:

\[r_1: -x+y = 2\] \[r_2: x+y = 6\] \[r_3: x = 3\] \[r_4: 2x-y = 4\] \[r_5: -y = 0\quad\Leftrightarrow\quad r_5:y=0\] \[r_6: -x-y = -1\quad\Leftrightarrow\quad r_6:x+y=1\] \[r_7: -x = 0\quad\Leftrightarrow\quad r_7:x=0\]

• La recta \(r_1\) pasa por los puntos \((0,2)\) y \((-2,0)\)
• La recta \(r_2\) pasa por los puntos \((0,6)\) y \((6,0)\)
• La recta \(r_3\) es paralela al eje \(y\)
• La recta \(r_4\) pasa por los puntos \((0,-4)\) y \((2,0)\)
• La recta \(r_5\) es paralela al eje \(x\)
• La recta \(r_6\) pasa por los puntos \((0,1)\) y \((1,0)\)
• La recta \(r_7\) es paralela al eje \(y\)

Al representar gráficamente estas rectas, obtenemos las intersecciones siguientes

• \(r_1\cap r_2 = \{(2,4)\}\)
• \(r_2\cap r_3 = \{(3,3)\}\)
• \(r_3\cap r_4 = \{(3,2)\}\)

La región factible \(R\) en este caso es un polígono cerrado.

Las soluciones siempre se encuentran en los extremos de la región factible, por lo tanto se evaluará la función objetivo \(Z = 3x+y\) en los vértices de \(R\)

• \(Z(0,1) = 1\)
• \(Z(0,2) = 2\)
• \(Z(2,4) = 10\)
• \(Z(3,3) = 12\)
• \(Z(3,2) = 11\)
• \(Z(2,0) = 6\)
• \(Z(1,0) = 3\)

Por lo tanto, el máximo se alcanza en el punto \(\bar{x} = (3,3)\) y vale \(Z(3,3)=12\)

Ejemplo 10

Maximizad la función \(Z = x+y\) bajo las siguientes restricciones

\[\left\{\begin{matrix}-x+y\le 2\\ x+y\le 6\\ x\le 3\\ 2x-y\le 4\\ -y\le 0\\ -x-y\le -1\\ -x\le 0\end{matrix}\right.\]

Observad que las restricciones de nuestro PPL son exactamente las mismas que en el ejemplo anterior, el Ejemplo 9. Por lo tanto, la región factible será la misma.

Sin embargo, al evaluar la función objetivo en los vértices obtenemos que el máximo se alcanza en los puntos \((2,4)\) y \((3,3)\). De este modo, los puntos del segmento que une estos dos puntos son máximos globales de nuestro PPL. Este segmento estará sobre la recta \(r_2\)

Ejemplo 11

Maximizad la función \(Z = 3x+y\) bajo las siguientes restricciones

\[\left\{\begin{matrix}-x+y\le 2\\ -y\le 0\\ -x-y\le -1\\ -x\le 0\end{matrix}\right.\]

En este caso se puede observar que la región factible no está acotada en la dirección de crecimiento de la función objetivo

Ejemplo 12

Minimizar la función \(Z = 0.6x+y\) bajo las siguientes restricciones

\[\left\{\begin{matrix}10x+4y\ge 20\\ 5x+5y\ge 20\\ 2x+6y\ge 12\\ x\ge 0\\ y\ge 0\end{matrix}\right.\]

En este caso la región factible no está acotada, pero la función objetivo alcanza el mínimo en el punto \((3,1)\) y vale \(Z = 2.8\)

Ejemplo 13

Minimizad la función \(Z = 2x-3y\) bajo las siguientes restricciones

\[\left\{\begin{matrix}x-2y\ge 4\\ 2x-4y\le -6\\ x\ge 0\\ y\ge 0\end{matrix}\right.\]

En este caso, la región facitble es \(R = \emptyset\), es decir, el problema no tiene solución

Ejemplo 14

Encuentra el máximo de \(Z = 2x_1-3x_2+5x_3\) bajo las restricciones siguientes

\[\left\{\begin{matrix}x_1+x_2\le 2\\ 3x_1+x_2-x_3\ge 3\\ x_1,x_2,x_3\ge 0\end{matrix}\right.\]

En forma estándar será

\[\max Z = 2x_1-3x_2+5x_3+0\cdot x_4+0\cdot x_5\]

bajo las restricciones

\[\left\{\begin{matrix}x_1+x_2+x_4 = 2\\ 3x_1+x_2-x_3-x_5 = 3\\ x_1,x_2,x_3,x_4,x_5\ge 0\end{matrix}\right.\]

Si quisiésemos el mismo problema en forma estándar de mínimo, lo que tendríamos sería

\[\min Z = -2x_1+3x_2-5x_3+0\cdot x_4+0\cdot x_5\]

bajo las restricciones

\[\left\{\begin{matrix}x_1+x_2+x_3 = 2\\ 3x_1+x_2-x_3-x_5 = 3\\ x_1,x_2,x_3,x_4,x_5\ge 0\end{matrix}\right.\]

Ejemplo 15

Encuentra el máximo de \(Z = 2x_1-3x_2+5x_3\) bajo las siguientes restricciones

\[\left\{\begin{matrix}x_1+x_2\le 2\\ 3x_1+x_2-x_3\ge 3\\ x_1,x_2\ge 0\end{matrix}\right.\]

Observad que lo único que cambia con respecto al ejemplo anterior, el Ejemplo 14, es que la variable \(x_3\) no está restringida en signo. Por tanto, debemos escribir \[x_3 = x_6-x_7\]

donde \(x_6 = x_3^+\) y \(x_7 = x_3^-\) y tal que \(x_3^+,x_3^-\ge 0\).

De este modo, la forma estándar de este PPL sería

\[\max Z = 2x_1-3x_2+5(x_6-x_7)+0\cdot x_4+0\cdot x_5\]

bajo las siguientes restricciones

\[\left\{\begin{matrix}x_1+x_2+x_4 =0\\ 3x_1+x_2-(x_6-x_7)-x_5 = 3\\ x_1,x_2,x_4,x_5,x_6,x_7\ge 0\end{matrix}\right.\]

Ejemplo 16

Hallad el máximo de \(Z = 3x_1-x_3\) bajo las siguientes restricciones

\[\left\{\begin{matrix}x_1+x_2+x_3 = 1\\ x_1-x_2-x_3\le 1\\ x_1+x_3\ge -1\\ x_1\ge 0\end{matrix}\right.\]

Como todas las variables han de ser no negativas,

\[x_2 = x_4-x_5\quad \text{ donde }\quad x_4 = x_2^+;\ x_5 = x_2^-\] \[x_3 = x_6-x_7\quad \text{ donde }\quad x_6 = x_3^+;\ x_7 = x_3^-\]

donde \(x_4,x_5,x_6,x_7\ge 0\)

Notad también que el término independiente de la tercera restricción es negativo, con lo cual se multiplica por \(-1\).

Con todo, el PPL inicial en su forma estándar será:

\[\max Z = 3x_1-x_6+x_7\]

bajo las restricciones

\[\left\{\begin{matrix}x_1+x_4-x_5+x_6-x_7 = 1\\ x_1-x_4+x_5-x_6+x_7 \le 1\\ -x_1-x_6+x_7 \le 1\\ x_1,x_4,x_5,x_6,x_7\ge 0\end{matrix}\right.\]

Ahora ya solo nos falta transformar las restricciones de desigualdad en restricciones de igualdad. Con lo cual nos queda

\[\left\{\begin{matrix}x_1+x_4-x_5+x_6-x_7 = 1\\ x_1-x_4+x_5-x_6+x_7+x_8 = 1\\ -x_1-x_6+x_7+x_9 = 1\\ x_1,x_4,x_5,x_6,x_7,x_8,x_9\ge 0\end{matrix}\right.\]

Ejemplo 17

Encuentra las soluciones básicas de

\[\left\{\begin{matrix} x_1 &+& 2x_2 &+& x_3&=&8\\ x_1 &+& 3x_2 &-& x_3&=&12\end{matrix}\right.\]

Se tiene que \[A = \begin{pmatrix}1 & 2 & 1\\ 1 & 3 & -1\end{pmatrix}\quad b = \begin{pmatrix} 8\\12\end{pmatrix}\]

Si se considera \[M_b = \begin{pmatrix} 1 & 2\\ 1 & 3\end{pmatrix}\]

Las variables básicas son \(x_1,x_2\) y la variable no básica \(x_3=0\), entonces:

\[x_b = M_b^{-1}b = \begin{pmatrix}3 & -2\\ -1 & 1\end{pmatrix}\begin{pmatrix}8\\ 12\end{pmatrix} = \begin{pmatrix}0 \\ 4\end{pmatrix}\]

De este modo, \((x_1,x_2) = (0,4)\) es una solución básica factible

Si se considera \[M_b = \begin{pmatrix} 1 & 1\\ 1 & -1\end{pmatrix}\]

Las variables básicas son \(x_1,x_3\) y la variable no básica \(x_2=0\), entonces:

\[x_b = M_b^{-1}b = \begin{pmatrix}\frac{1}{2} & \frac{1}{2}\\ \frac{1}{2} & -\frac{1}{2}\end{pmatrix}\begin{pmatrix}8\\ 12\end{pmatrix} = \begin{pmatrix}10 \\ -2\end{pmatrix}\]

En este caso se obtiene una solución básica no factible ya que \(x_3<0\)

Si se considera \[M_b = \begin{pmatrix} 2 & 1\\ 3 & -1\end{pmatrix}\]

Las variables básicas son \(x_2,x_3\) y la variable no básica \(x_1=0\), entonces:

\[x_b = M_b^{-1}b = \begin{pmatrix}\frac{1}{5} & \frac{1}{5}\\ \frac{3}{5} & -\frac{2}{5}\end{pmatrix}\begin{pmatrix}8\\ 12\end{pmatrix} = \begin{pmatrix}4 \\ 0\end{pmatrix}\]

De este modo, \((x_2,x_3) = (4,0)\) es una solución básica factible

El número de soluciones básicas factibles de un PPL acotado con un número finito de restricciones es siempre finito y a cada una le corresponde un punto extremo de la región factible

Ejemplo 18

Encuentra el máximo de \(Z = 40x_1 + 30x_2\) bajo las restricciones

\[\left\{\begin{matrix}x_1\le 16\\ x_2\le 8\\ x_1+2x_2\le 24\\ x_1,x_2\ge 0\end{matrix}\right.\]

Para aplicar el Método Símplex se deben hacer una serie de pasos:

PASO 1

Se debe escribir el problema en forma estándar de máximo, que será el mismo que denota el sistema:

\[\begin{matrix} Z & -& 40x_1 & -& 30x_2 &+& 0\cdot x_3 &&+& 0\cdot x_4&+& 0\cdot x_5 & = & 0\\ & & x_1 & & &+& x_3 &&& && & = & 16\\ & & & & x_2&& &+&x_4& && & = & 8\\ & & x_1 &+ & 2x_2&& &&& &+&x_5 & = & 24\\ \end{matrix}\]

con \(x_1,x_2,x_3,x_4,x_5\ge 0\)

Ahora, podemos construir la siguiente tabla

La matriz básica factible inicial (matriz identidad) corresponde a las variables básicas, en este caso las variables compensatorias \(x_3,x_4,x_5\) y las variables no básicas son \(x_1=x_2=0\)

Teniendo en cuenta también la fila 1 de la tabla, se puede expresar el sistema

\[\begin{pmatrix}1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\end{pmatrix}\begin{pmatrix} Z\\ x_3\\ x_4\\ x_5\end{pmatrix} = \begin{pmatrix} 0\\ 16\\ 8\\ 24 \end{pmatrix}\]

Que corresponde a \(x_3 = 16,\ x_4 = 8,\ x_5 = 24,\ Z=0\), con \((x_1,x_2) = (0,0)\). Observad que \((0,0)\) es uno de los vértices de la región factible

PASO 2

• Se busca la columna que en la fila 1 tiene la entrada negativa con mayor valor absoluto, columna pivote
• Se dividen las constantes por los valores positivos de la columna pivote y se elige el mínimo, la fila correspondiente a este mínimo será la fila pivote
• El elemento que esté en la intersección de la fila y la columna pivotes debe corresponderse con la nueva variable básica. Notad que en nuestro caso la columna pivote es la segunda y la fila pivote es la segunda fila, ya que la entrada negativa con mayor valor absoluto es \(-40\) (columna de \(x_1\)) y \(\min\{\frac{16}{1},\frac{24}{1}\} = 16\) se encuentra en la segunda fila. En definitiva, el pivote es 1 y le corresponde la variable \(x_1\).
• Se transforma la tabla inicial de forma que la columna pivote sea un vector unitario (todos los elementos de la columna han de ser nulos salvo el pivote que debe ser 1).

De la tabla se puede extraer el sistema básico:

\[\begin{pmatrix}1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\end{pmatrix}\begin{pmatrix} Z\\ x_1\\ x_4\\ x_5\end{pmatrix} = \begin{pmatrix} 640\\ 16\\ 8\\ 8\end{pmatrix}\]

Lo que se corresponde con \(x_1 = 16,\ x_4 = 8\ x_5 = 8\) y \(Z = 640\), con \(x_2 = x_3 = 0\).

Observad que de nuevo \((x_1,x_2)= (16,0)\) es otro vértice de la región factible

PASO 3

Como en la fila 1 todavía hay un número negativo, la solución se puede mejorar. Iterando el paso anterior, obtenemos

• La nueva variable básica es \(x_2\).
• Si hacemos \(\min\{\frac{8}{1},\frac{8}{2}\}\), se obtiene que el pivote está en la fila 4
• El pivote es 2, por tanto se divide la cuarta fila entre 2 para obtener así el pivote 1
• Finalmente, se hacen 0 el resto de elementos de la tercera columna, la columna pivote.

De la tabla se puede extraer el sistema básico:

\[\begin{pmatrix}1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\end{pmatrix}\begin{pmatrix} Z\\ x_1\\ x_4\\ x_2\end{pmatrix} = \begin{pmatrix} 760\\ 16\\ 4\\ 4\end{pmatrix}\]

Lo que se corresponde con \(x_1 = 16,\ x_2 = 4,\ x_4 = 4\) y \(Z = 760\), con \(x_3 = x_5 = 0\).

Observad que de nuevo \((x_1,x_2)= (16,4)\) es otro vértice de la región factible

Como en la fila 1 ya no quedan números negativos, tenemos que la solución no se puede mejorar

En conclusión, el máximo de \(Z\) se toma en el punto \((x_1,x_2) = (16,4)\)

Ejemplo 19

Encontrad el mínimo de \(Z = x_1 + 4x_2\) bajo las siguientes restricciones

\[\left\{\begin{matrix}x_1+x_2\ge 8\\ 3x_1+2x_2\ge 12\\ x_1,x_2\ge 0\end{matrix}\right.\]