Investigación de operadores

Parcial corte 1

Nombre completo del estudiante: Cesar Augusto Cuervo Tovar Código estudiante: 90187

El parcial se debe entregar en un archivo pdf realizado en , ó en R, entregando sus archivos generadores .tex o .Rmd según sea el caso.

Tenga en cuenta que para cada punto aplicado que salga en su parcial, debe seguir los pasos vistos en clase:

1. Decir las variables de decisión

2. Función objetivo

3. Restricciones

4. Modelo matemático

5. Empezar la solución método simplex según sea el caso

Referencias (Taha 2004), (Mora 2004)

Parcial

1. Teorema de PL: Dado un problema de PL, en su forma Standard

\[\begin{align*} \text{Max }\, &c^tx\\ Ax&=b\\ x&\geq 0 \end{align*}\]

supongamos que el rango de \(A\) es \(m\), se tiene que:

1. Si existe una solución posible, también existe una solución posible básica.

2. Si el problema tiene una solución posible óptima, entonces también tiene una solución posible básica óptima.

Seleccione un problema que conozca y compruebe el Teorema de PL.

Función Objetivo

\[\text{Máximizar}\,\,z=2x_1 + 5x_2\]

Restricciones

\[\begin{align*} x_1+6x_2&\leq 20\\ x_1+x_2&\leq 10\\ x_1&\leq 9\\ x_1,x_2&\geq 0 \end{align*}\]

Gráfica

1. En la grafica se pueden ver 2 soluciones los puntos C y D, pero también hay dos soluciones básicas B y E.

2. \[Punto\,\, C\rightarrow 2(8)+5(2)=16+10=26\] \[Punto\,\, D\rightarrow 2(9)+5(1)=18+5=23\]

Por lo que el punto C es una solución óptima

\[Punto\,\, C\rightarrow 2(0)+5(\frac{10}{3})=\frac{50}{3}\approx 16,\overline{6}\] \[Punto\,\, D\rightarrow 2(9)+5(0)=18=18\]

Entonces el punto D es una solución óptima básica

Segundo Ejercicio

2. Burroughs Garment Company fabrica camisas para caballero y blusas de dama para las tiendas de descuento Falabella, corporación que aceptará toda la producción surtida por Burroughs. El proceso de producción incluye el corte, la costura y el empaque. Burroughs emplea \(T\) trabajadores en el departamento de corte, \(CT\) en el de costura, y \(EM\) en empaque. La fábrica trabaja un turno de 8 horas, 5 días a la semana. La siguiente tabla muestra los requerimientos de tiempo y utilidades por unidad para las dos prendas:

donde:

TR	CT	EM
30	38	8

Determine el programa de producción semanal óptimo para Burroughs.

Se tiene en minutos el tiempo que se gasta cada tipo de trabajador en hacer su trabajo, entoces para hallar el total de minutos semanales en cada proceso de producción se deben multiplicar el numero de minutos disponibles por trabajador (en este caso 2400 minutos), por el número de trabajadores de cada proceso.

	Camisas	Blusas	Total hrs	Total hrs
TR	20	60	(30)(2400)	72000
CT	70	60	(38)(2400)	91200
EM	12	4	(8)(2400)	19200
Beneficio	8	12

Variables

\[\text{x_1= Camisas para caballero}\] \[\text{x_2= blusas para dama}\]

Función Objetivo

\[\text{Maximizar }\, \, z=8x_1+12x_2\]

Restricciones

\[\begin{align*} 20x_1+60x_2&\leq 72000\\ 70x_1+60x_2&\leq 91200\\ 12x_1+4x_2&\leq 19200\\ x_1,x_2&\geq 0 \end{align*}\]

Gráfica

Gracias a la grafica podemos ver que la tercera restricción es redundante (no le aporta nada a la solución del problema), por lo que podemos precindir de ella para la solución del problema.

Ecuaciones

\[\begin{align*} -8x_1-12x_2+0s_1+0s_2+0s_3=0\\ 20x_1+60x_2+s_1 = 72000\\ 70x_1+60x_2+s_2 = 91200\\ x_1,x_2,s_1,s_2&\geq 0 \end{align*}\]

Método Simplex

La tabla con las ecuaciones es:

	\(x_1\)	\(\downarrow{x_2}\)	\(s_1\)	\(s_2\)	\(R\)
\(z\)	-8	-12	0	0	0
\(s_1\)	20	60	1	0	72000
\(s_2\)	70	60	0	1	91200

Con la variable de entrada \(x_2\):

	\(x_2\)	\(R\)	\(\frac{R}{x_2}\)
\(s_1\)	60	72000	1200\(\leftarrow\)
\(s_2\)	60	91200	1520

Tenemos que 1200 es el mínimo valor, por lo que \(s_1\) es la variable de salida

\(s_1\rightarrow x_2\)

Para hallar el primer pivote vamos a:

\[\text{$x_2\rightarrow\frac{x_2}{60}$} \]

	\(x_1\)	\(\downarrow x_2\)	\(s_1\)	\(s_2\)	\(R\)
\(z\)	-8	-12	0	0	0
\(\underrightarrow{x_2}\)	\(\frac{1}{3}\)	1	\(\frac{1}{60}\)	0	1200
\(s_2\)	70	60	0	1	91200

Se convierten las demás filas en 0 usando el pivote así:

\[\text{$z\rightarrow z\ +12x_2$}\] \[\text{$s_2\rightarrow s_2-60x_2$}\]

	\(\downarrow x_1\)	\(x_2\)	\(s_1\)	\(s_2\)	\(R\)
\(z\)	-4	0	\(\frac{1}{5}\)	0	14400
\(x_2\)	\(\frac{1}{3}\)	1	\(\frac{1}{60}\)	0	1200
\(s_2\)	50	0	-1	1	19200

Ahora tenemos que la nueva variable de entrada es \(x_1\), entonces:

	\(x_1\)	\(R\)	\(\frac{R}{x_1}\)
\(x_2\)	\(\frac{1}{3}\)	1200	3600
\(s_2\)	50	19200	384\(\leftarrow\)

Tenemos que 384 es el mínimo valor, por lo que \(s_2\) es la variable de salida

\(s_2\rightarrow x_1\)

Ahora hallamos el segundo pivote

\[\text{$x_1\rightarrow\frac{x_1}{50}$} \]

	\(\downarrow x_1\)	\(x_2\)	\(s_1\)	\(s_2\)	\(R\)
\(z\)	-4	0	\(\frac{1}{5}\)	0	14400
\(x_2\)	\(\frac{1}{3}\)	1	\(\frac{1}{60}\)	0	1200
\(\underrightarrow{x_1}\)	1	0	\(\frac{-1}{50}\)	\(\frac{1}{50}\)	384

Se convierten las demás filas en 0 usando el pivote así:

\[\text{$z\rightarrow z\ +4x_1$}\] \[\text{$x_2\rightarrow x_2-\frac{1}{3}x_1$}\]

	\(x_1\)	\(x_2\)	\(s_1\)	\(s_2\)	\(R\)
\(z\)	0	0	\(\frac{3}{25}\)	\(\frac{2}{25}\)	15936
\(x_2\)	0	1	\(\frac{7}{300}\)	\(\frac{-1}{150}\)	1072
\(x_1\)	1	0	\(\frac{-1}{50}\)	\(\frac{1}{50}\)	384

Entonces las variables deben tomar:

\[\text{Número de camisetas que se deben producir $x_1=384$}\] \[\text{Número de blusas que se deben producir $x_2=1072$}\]

Loas datos coinciden con el punto C de la gráfica.

Y su respuesta es:

\[\text{Beneficio $z=15936$}\]

Tercer Ejercicio

3. Considere el siguiente modelo de Progranación Lineal:

\[\text{Maximizar }\, \, z=5x_1+4x_2\]

sujeto a:

\[\begin{align*} 6x_1+4x_2&\leq 24\\ 6x_1+3x_2&\leq 22.5\\ x_1+x_2&\leq 5\\ x_1+2x_2&\leq 6\\ -x_1+x_2&\leq 1\\ x_2&\leq2\\ x_1,x_2&\geq 0 \end{align*}\]

En programación lineal se dice que una restricción es redundante si su eliminación del modelo no modifica el espacio de soluciones factibles. Use el medio gráfico con Geogebra para identificar las restricciones redundantes, luego demuestre que su eliminación (basta con no graficarlas) no afecta al espacio de soluciones ni a la solución óptima.

Gráfica con restricción redundante

La inecución que esta de rojo es la restriccion redundante, ya que como vemos corresponde a la line roja y esta no modifica la región factible, por lo que podemos pasarla por alto sin afectar la solución.

Como vemos tiene 3 posibles soluciones no básicas:

\[\text C=(1,2)\,D=(2,2)\,E=(3,\frac{3}{2}))\]

Gráfica sin restricción redundante

Como vemos las 3 posibles soluciones no básicas se mantienen

\[\text C=(1,2)\,D=(2,2)\,E=(3,\frac{3}{2}))\]

Solución Óptima

\[\text{Maximizar }\, \, z=5x_1+4x_2\] \[\text 5(1)+4(2)=5+8=13\rightarrow Mín\] \[\text 5(2)+4(2)=10+8=18\] \[\text 5(3)+4(\frac{3}{2})=15+6=21\rightarrow Máx\]

El punto \(E=(3,\frac{3}{2})\) ofrece la máxima solución, teniendo como resultado un valor de 21.

Cuarto Ejercicio

4. Resuleve el siguiente problema

\[Maximizar\, z=3x_1+5x_2\]

sujeta a

\[\begin{align*} x_1+4x_2&\leq 4\\ 5x_1-2x_2&\leq 10\\ 9x_1+15x_2&\leq 18\\ 2x_2&\leq 3\\ x_1,x_2&\geq 0 \end{align*}\]

Demuestre que no todos los óptimos alternativos son puntos de esquina (es decir, no básicos). Provea una demostración gráfica bidimensional del tipo de espacio de soluciones y representa una ecuación para encontrar todos los puntos óptimos alternativos.

Gráfica

Tenemos que \(2x_2\leq 3\) ^ \(5x_1-2x_2\leq 10\) son redundantes, ya que no afectan la región factible.

Ecuaciones

\[\begin{align*} -3x_1-5x_2+0s_1+0s_2=0\\ x_1+4x_2+s_1= 4\\ 9x_1+15x_2+s_2= 18\\ x_1,x_2,s_1,s_2&\geq 0 \end{align*}\]

Método Simplex

La tabla con las ecuaciones es:

	\(x_1\)	\(\downarrow{x_2}\)	\(s_1\)	\(s_2\)	\(R\)
\(z\)	-3	-5	0	0	0
\(s_1\)	1	4	1	0	4
\(s_2\)	9	15	0	1	18

Con la variable de entrada \(x_2\):

	\(x_2\)	\(R\)	\(\frac{R}{x_2}\)
\(s_1\)	4	4	1\(\leftarrow\)
\(s_2\)	15	18	\(\frac{6}{5}\)

Tenemos que 1 es el mínimo valor, por lo que \(s_1\) es la variable de salida

\(s_1\rightarrow x_2\)

Para hallar el primer pivote vamos a:

\[\text{$x_2\rightarrow\frac{x_2}{4}$} \]

	\(x_1\)	\(\downarrow x_2\)	\(s_1\)	\(s_2\)	\(R\)
\(z\)	-3	-5	0	0	0
\(\underrightarrow{x_2}\)	\(\frac{1}{4}\)	1	\(\frac{1}{4}\)	0	1
\(s_2\)	9	15	0	1	18

Se convierte las demás filas en 0 usando el pivote así:

\[\text{$z\rightarrow z\ +5x_2$}\] \[\text{$s_2\rightarrow s_2-15x_2$}\]

	\(\downarrow x_1\)	\(x_2\)	\(s_1\)	\(s_2\)	\(R\)
\(z\)	\(\frac{-7}{4}\)	0	\(\frac{5}{4}\)	0	5
\(x_2\)	\(\frac{1}{4}\)	1	\(\frac{1}{4}\)	0	1
\(s_2\)	\(\frac{21}{4}\)	0	\(\frac{-15}{4}\)	1	3

Ahora tenemos que la nueva variable de entrada es \(x_1\), entonces:

	\(x_1\)	\(R\)	\(\frac{R}{x_2}\)
\(x_2\)	\(\frac{1}{4}\)	1	4
\(s_2\)	\(\frac{21}{4}\)	3	\(\frac{4}{7}\,\leftarrow\)

Tenemos que \(\frac{4}{7}\) es el mínimo valor, por lo que \(s_2\) es la variable de salida

\(s_2\rightarrow x_1\)

Ahora hallamos el segundo pivote

\[\text{$x_1\rightarrow\frac{4}{21}$}x_1 \]

	\(x_1\)	\(x_2\)	\(s_1\)	\(s_2\)	\(R\)
\(z\)	\(\frac{-7}{4}\)	0	\(\frac{5}{4}\)	0	5
\(x_2\)	\(\frac{1}{4}\)	1	\(\frac{1}{4}\)	0	1
\(x_1\)	1	0	\(\frac{-5}{7}\)	\(\frac{4}{21}\)	\(\frac{4}{7}\)

Se convierte las demás filas en 0 usando el pivote así:

\[\text{$z\rightarrow z\ + \frac{7}{4}x_1$}\] \[\text{$x_2\rightarrow x_2-\frac{1}{4}x_1$}\]

	\(x_1\)	\(x_2\)	\(s_1\)	\(s_2\)	\(R\)
\(z\)	0	0	0	\(\frac{1}{3}\)	6
\(x_2\)	0	1	\(\frac{41}{84}\)	\(\frac{-1}{21}\)	\(\frac{6}{7}\)
\(x_1\)	1	0	\(\frac{-5}{7}\)	\(\frac{4}{21}\)	\(\frac{4}{7}\)

Como vemos el punto (\(\frac{4}{7}\),\(\frac{6}{7}\)) corresponde al máximo óptimo alternativo no básico.

Gráfica

En la gráfica vemos como una restriccion (línea verde) es paralela a la función objetivo(línea roja), por ende la linea \(\overline{CD}\) contiene infinitas soluciones, dónde el punto C es el máximo óptimo alternativo no básico.

Quinto ejercicio

5. Top Toys planea una nueva campaña de publicidad por radio y TV. Un comercial de radio cuesta \(A\) y uno de TV \(B\). Se asigna un presupuesto total de \(C\) a la campaña. Sin embargo, para asegurarse de que cada medio tendrá por lo menos un comercial de radio y uno de TV, lo máximo que puede asignarse a uno u otro medio no puede ser mayor que el 80% del presupuesto total. Se estima que el primer comercial de radio llegará a \(D\) personas, y que cada comercial adicional llegará sólo a \(E\) personas nuevas. En el caso de la televisión, el primer anuncio llegará a \(G\) personas y cada anuncio adicional a \(H\). ¿Cómo debe distribuirse la suma presupuestada entre la radio y la TV?

Los valores de \(A,\dotsc, G\) son:

A	B	C	D	E	G	H
155	1974	23170	5178	2014	4083	3165

Tabla organizando los datos del problema.

	Radio	TV
Costo	155	1974	23170
Personas que ven comercial	5178	4083
Personas que ven comercial adic	2014	3165

Variables

\[\text{$x_1$ = comerciales de radio}\] \[\text{$x_2$ = comerciales de TV}\]

Fución Objetivo

\[\text{Máximizar}\,\,5178+2014(x_1-1)+4083+3165(x_2-1)\]

Restricciones

El problema dice que el costo del total de comerciales de radio o TV no debe exceder el 80%, además las restricciones admiten \(x_1,x_2\geq 0\) pero lo mejor seria tomar \(x_1,x_2\geq 1\)

Tenemos que el 80% del presupuesto es:

80% = \(\frac{8}{10}\) \(\rightarrow\) \({23170}( \frac{8}{10})=\frac{18536\not0}{1\not0}=18536\)

\[\begin{align*} 155x_1+1974x_2&\leq 23170\\ 155x_1&\leq 18536\\ 1974x_2&\leq 18536\\ x_1,x_2&\geq 0 \end{align*}\]

Gráfica

Ecuaciones

\[\begin{align*} -2014x_1-3165x_2+0s_1+0s_2+0s_3=0\\ 155x_1+1974x_2+s_1 = 23170\\ 155x_1+s_2= 18536\\ 1974x_2+s_3= 18536\\ x_1,x_2,s_1,s_2,s_3&\geq 0 \end{align*}\]

Método Simplex

La tabla con las ecuaciones es:

	\(x_1\)	\(\downarrow x_2\)	\(s_1\)	\(s_2\)	\(s_3\)	\(R\)
\(z\)	-2014	-3165	0	0	0	0
\(s_1\)	155	1974	1	0	0	23170
\(s_2\)	155	0	0	1	0	18536
\(s_3\)	0	1974	0	0	1	18536

Con la variable de estrada \(x_2\):

	\(x_2\)	\(R\)	\(\frac{R}{x_2}\)
\(s_1\)	1974	23170	\(\frac{23170}{1974}\)
\(s_2\)	0
\(s_3\)	1974	18536	\(\frac{18536}{1974} \leftarrow\)

Tenemos que \(\frac{18536}{1974}\) es el valor mínimo, por lo que \(s_3\) es la variable de salida

\(s_3 \rightarrow x_2\)

Para hallar el primer pivote vamos a:

\[x_2 \rightarrow \frac{x_2}{1974}\]

	\(x_1\)	\(\downarrow x_2\)	\(s_1\)	\(s_2\)	\(s_3\)	\(R\)
\(z\)	-2014	-3165	0	0	0	0
\(s_1\)	155	1974	1	0	0	23170
\(s_2\)	155	0	0	1	0	18536
\(\underrightarrow{x_2}\)	0	1	0	0	\(\frac{1}{1974}\)	\(\frac{18536}{1974}\)

Se convierten las demás filas en 0 usando el pivoteasí:

\[z \rightarrow \ z+3165x_2\] \[s_1 \rightarrow \ s_1-1974x_2\]

	\(\downarrow x_1\)	\(x_2\)	\(s_1\)	\(s_2\)	\(s_3\)	\(R\)
\(z\)	-2014	0	0	0	\(\frac{3165}{1974}\)	\(\frac{1396820}{47}\)
\(s_1\)	155	0	1	0	-1	4634
\(s_2\)	155	0	0	1	0	18536
\(x_2\)	0	1	0	0	\(\frac{1}{1974}\)	\(\frac{18536}{1974}\)

La nueva variable de entrada es \(x_1\)

	\(x_1\)	\(R\)	\(\frac{R}{x_1}\)
\(s_1\)	155	4634	\(\frac{4634}{155} \leftarrow\)
\(s_2\)	155	18536	\(\frac{18536}{155}\)
\(x_2\)	0	\(\frac{18536}{1974}\)	Indeterminación

Tenemos que \(\frac{4634}{155}\) es el valor mínimo por lo que \(s_1\) es la variable de salida

\(s_1 \rightarrow x_1\)

Ahora hallamos el pivote

\[x_1\rightarrow \frac{x_1}{155}\]

Se convierten las demás filas en 0 usando el pivote así:

	\(\downarrow x_1\)	\(x_2\)	\(s_1\)	\(s_2\)	\(s_3\)	\(R\)
\(z\)	-2014	0	0	0	\(\frac{3165}{1974}\)	\(\frac{1396820}{47}\)
\(\underrightarrow{x_1}\)	1	0	\(\frac{1}{155}\)	0	\(\frac{-1}{155}\)	\(\frac{4634}{155}\)
\(s_2\)	155	0	0	1	0	18536
\(x_2\)	0	1	0	0	\(\frac{1}{1974}\)	\(\frac{18536}{1974}\)

Se convierten las demás filas en 0 usando el pivote:

\[z\rightarrow z+2014x_1\] \[s_2\rightarrow s_2-155x_1\]

	\(x_1\)	\(x_2\)	\(s_1\)	\(s_2\)	\(\downarrow s_3\)	\(R\)
\(z\)	0	0	\(\frac{2014}{155}\)	0	\(\frac{-1161687}{101990}\)	\(\frac{655152272}{7285}\)
\(x_1\)	1	0	\(\frac{1}{155}\)	0	\(\frac{-1}{155}\)	\(\frac{4634}{155}\)
\(s_2\)	0	0	-1	1	1	13902
\(x_2\)	0	1	0	0	\(\frac{1}{1974}\)	\(\frac{1324}{141}\)

La nueva variable de entrada es \(s_3\), por lo tanto:

	\(s_3\)	\(R\)	\(\frac{R}{s_3}\)
\(x_1\)	\(\frac{-1}{155}\)	\(\frac{4634}{155}\)	-4634
\(s_2\)	1	13902	13902\(\leftarrow\)
\(x_2\)	\(\frac{1}{1974}\)	\(\frac{1324}{141}\)	\(\frac{2613576}{141}\)

Tenemos que 13902 es el valor mínimo, entonces \(s_2\) es la variable de salida

\(s_2 \rightarrow s_3\)

En este caso no hay que hallar el pivote

Se convierten en 0 las demás filas así:

\[z+\frac{1161687}{101990}s_3\] \[x_1 +\frac {1}{55}s_3\] \[x_2-\frac{-1}{1978}\]

	\(x_1\)	\(x_2\)	\(s_1\)	\(s_2\)	\(s_3\)	\(R\)
\(z\)	0	0	\(\frac{1055}{658}\)	\(\frac{1161687}{101990}\)	0	\(\frac{1808707463}{7285}\)
\(x_1\)	1	0	0	\(\frac{1}{155}\)	0	\(\frac{18536}{155}\)
\(s_2\)	0	0	-1	1	1	13902
\(x_2\)	0	1	\(\frac{1}{1974}\)	\(\frac{-1}{1974}\)	0	\(\frac{331}{141}\)

Tenemos que se deben emitir 119 comerciales de radio y 2 de TV.Los datos coinciden con el punto B de la grafica

\[5178+2014(118)+4083+3165(1)=5178+237652+4083+3165\approx250078\]

Bibliografía

Mora, HM. 2004. Programación Lineal. Universidad Nacional de Colombia.

Taha, Hamdy A. 2004. Investigación de Operaciones. Pearson Educación.