Objetivo de la competencia. El alumno comprenderá las definiciones y conceptos de programación por metas, así como el modelado y solución de planteamientos orientados al desarrollo de las habilidades cognitivas necesarias para proporcionar una interpretación adecuada a las soluciones óptimas obtenidas.
La programación lineal es un método de optimización matemática que permite el manejo masivo de múltiples variables, esto ha permitido que haya recibido especial atención en áreas de la Ingeniería Indutrial, como lo son la programación de la producción, logística y estudios de transporte, inclusive se ha llegado a utilizar en otras disciplinas demostrando su efectividad como método de toma de decisiones. Sin embargo, el método de Programación Lineal está limitado por efecto de la rigidez de las restricciones utilizadas, lo que lleva a que algunas soluciones no sean factibles o inclusive sean imposibles de resolver mediante métodos convencionales, como lo son el Método Simplex(Nash, 2000).
En el caso particular de los planes ejecutivos de en el área industrial, muchas veces es necesario evaluar el modelo de decisión desde una óptica diferente, menos rígida, que permita a los decisores analizar posibles escenarios, mismos que implican que alguna meta organizacional particular o bien no se cumple o bien sea rebasada(Charnes, Cooper, & Ferguson, 1955).
Dentro de las organizaciones existen diferentes niveles jerárquicos, cada uno de ellos está encargado de tomar las decisiones de acuerdo a su área de competencia, normalmente, ponderando la importancia de los factores involucrados en la decisión de acuerdo criterios preestablecidos por un nivel jerárquico superior, mismo que define la importancia de los factores de acuerdo a entrevistas con expertos, la experiencia de los trabajadores, gente afín a la actividad que sea realiza, etc. Estas ponderaciones son completamente subjetivas y dependen directamente de la persona encargada de tomar la decisión.
En el caso de los modelos matemáticos tradicionales, estos se basan en la optimización de una sola función objetivo, sin embargo, en los ambientes previamente comentados, en muchas ocasiones no se trata de tomar la mejor decisión para el cumplimiento de una sola meta, si no de múltiples objetivos, en donde en muchos de los casos, las metas pueden ser rebasadas o simplemente no se puede llegar al cumplimiento de las mismas, situación que hace que no se logre establacer una solución en términos estrictos “óptima”, si no en un solución “eficiente”, que minimice el impacto de excederse o quedarse corto en una meta específica(Taha, 2004).
Dados \(S\subseteq{R^N}\), \(S\neq{\phi}\), \({f_j: S{\longrightarrow}R}\), \({j{\in}\{1,...,p}\}\), el problema de optimización multiobjetivo se plantea como(Rodrı́guez & otros, 2019):
\[min({f_1}(x),...,{f_p}(x))\] \[s.a:~~x{\in}S\]
Esto es, dado un espacio vectorial \(S\) que contiene a un conjunto de soluciones \(R^N\), donde \(S\) no pertenece al conjunto vacío y las funciones objetivo \(f_j\) estan contenidas en \(R\) para toda \(j\) en \(\{1,..,p\}\), entonces el problema de optimización matemática de metas se define como la minimización de las funciones objetivo implicadas, dado que se desea minimizar el impacto de la violación o exceso en cualquiera de las metas planteadas, para un conjunto de variables de decisión que pertenecen al conjunto \(S\). Dicho planteamiento tiene una solución óptima \({\bar{x}}^j\) con un valor óptimo \({f_j}^*\).
Una solución ideal es cualquier solución factible \(x^*\) del problema multiobjetivo en la que \(({f_1}(x^*),...{f_p}(x^*))=({f_1}^*,...,{f_p}^*)\). Al vector \(({f_1}^*,...,{f_p}^*)\) se le denomina punto ideal o utopía.
En lo general, las soluciones ideales son no factibles. La, en general, no factibilidad del óptimo absoluto impone la búsqueda de soluciones optimales y conduce a la siguiente definición(Rodrı́guez & otros, 2019).
\({\bar{x}}{\in}X\) es una solución eficiente sí, y sólo si, \({\nexists}{x'}{\in}S\) tal que \({{f_j}(x'){\leq}{f_j}(\bar{x})}{\in}{\{1,...,p\}}\) y \({f_{j_0}}(x')<{f_{j_0}(x)}\). Estas soluciones también se denominan no dominadas u óptimas de Pareto.
\({\bar{x}}{\in}X\) es una solución débilmente eficiente sí, y sólo si,\({\nexists}{x'}{\in}S\) tal que \({f_{j}}(x')<{f_j}(\bar{x})\), \({{\forall}_j}{\in}{\{1,...,p\}}\).
Cualquier solución eficiente es débilmente eficiente. Lo contrario no es cierto. En lo general, el conjunto de soluciones eficientes es muy numeroso.
Una solución preferida es la que optimiza las preferencias del decisor. La coherencia impone que la solución preferida tenga que elegirse entre las soluciones eficientes.
Si las preferencias del decisor pueden establecerse a través de una función sobre los valores que alcanzan los objetivos, tenemos una función de utilidad.
Obviamente, si se conoce la función de utilidad, encontrar soluciones al problema planteado se convierte en resolver un problema uniobjetivo. Las soluciones preferidas del decisor deben ser soluciones factibles (eficientes) en las que la función de utilidad alcance un valor máximo(Rodrı́guez & otros, 2019).
Se llaman soluciones satisfactorias a las que superan determinados niveles (que expresan la satisfacción del decisor) asociados a los diferentes objetivos (atributos).
Se llaman soluciones de compromiso a las soluciones factibles en las que las desviaciones de los niveles de las funciones objetivos (atributos) respecto al nivel ideal son pérdidas que pueden ser aceptadas por el decisor.
Lo anterior indica que la búsqueda de soluciones al problema de optimización multiobjetivo debe incluir procesos de generación de soluciones eficientes que, o bien siguen criterios que incorporan las preferencias del decisor, o, cuando es posible, construyen todo el conjunto de dichas soluciones. en este último caso, en una etapa posterior, la selección de la solución preferida se hará en el citado conjunto(Rodrı́guez & otros, 2019).
En el caso del modelo de una sola meta, en vez de plantearse la función objetivo como de una forma estricta, se programa de tal manera que sea flexible, esto se logra mediante la adición de un conjunto de vairbales adicional, que se denomina variables de desviación. Dichas variables no negativas se denotan mediante \({s_i}^+\) y \({s_i}^-\) y representan las desviaciones arriba y abajo respecto al lado derecho de la restricción \(i\).
Por definición, las variables \({s_i}^+\) y \({s_i}^-\) son dependientes y en consecuencia no pueden ser al mismo tiempo variables básicas. Esto quiere decir que en cualquier interacción simplex, cuando menos una de las dos variables de desviación puede asumir un valor positivo. Si la \(i-ésima\) desigualdad original es de tipo \(\leq\) y su \({{s_i}^+}>0\), entonces se satisfará la \(i-ésima\) meta; en caso contrario, si \({{s_i}^-}>0\), la meta \(i\) no se satisfará. En esencia, la definición de \({s_i}^+\) y \({s_i}^-\) permitesatisfacer o violar la \(i-ésima\) meta cuando se desee. Ésta es la clave de la flexibilidad que caracteriza a la programación de metas cuando busca una solución de compromiso. Naturalemente, una buena solución de compromiso trata de minimizar la cantidad por la cual se viola cada meta(Taha, 2004).
Es decir, cuando la meta \({g_j}(x_i)\) tiene el signo menor (\(<\)), la variable de desviación que se opone al cumplimiento de la meta es \({s_i}^-\), por lo tanto, esta variable deberá minimizarse en la función objetivo, es decir:
\[Min~~{g_j}(x_i)\] En caso contrario, cuando la meta \({g_j}(x_i)\) tiene el signo mayor (\(>\)), la variable de desviación que se opone al cumplimiento de la meta es \({s_i}^+\), por lo tanto, esta variable deberá minimizarse en la función objetivo, tal y como se plantea en la meta anterior.
Para ejemplificar el modelo de una sola meta se analizará el modelo propuesto por (Render, Stair, Hanna, & otros, 2006), en la página 396 del Capítulo 10 de su libro Métodos cuantitativos para los negocios, bajo el enfoque de Programación de Metas el cual a la letra plantea que:
La compañía Harrison Electric, localizada en el área antigua de Chicago, fabrica dos productos que son populares con los restauradores de casas: candelabros y ventiladores de techo de estilo antiguo. Tanto los candelabros como los ventiladores requieren un proceso de producción de dos pasos, que implica cableado y ensamble. Se requieren 2 horas para cablear cada candelabro y 3 para cablear un ventilador de techo. El ensamble final de los candelabros y los ventiladores requiere de 6 y 5 horas, respectivamente. La capacidad de producción es tal que solamente están disponibles 12 horas de cableado y 30 horas de ensamble. Si cada candelabro producido reditúa a la empresa $ 7 y cada ventilador $ 6, formule un programa de producción que maximice la utilidad por la actividad antes mencionada considerando que la gerencia ha establecido una meta de por lo menos $30 para el periodo en que está llevando a cabo este análisis.
En el caso de análisis, se desea lograr la meta de conseguir $ 30 en el periodo sujeto de estudio, en función de los candelabros y ventiladores de techo estilo antiguo, para lo cual se establecen las siguientes variables de decisión:
\(x_i\)=Cantidad de artefactos de la categoría \(i\), donde \(x_i\) es una variable entera.
\(i\)=1,2
1= Candelabro.
2= Ventilador de techo estilo antiguo.
Las necesidades de la gerencia están orientadas a obtener un beneficio de $30, por lo que se debe plantear la meta de utilidad con las condiciones de flexibilidad antes planteadas, es decir, agregar a la modelación las variables \({{s_1}^+}+{{s_1}^-}\), donde \({{s_1}^+}\) es la desviación de la meta hacia un nivel mayor, lo que implica superar el límite establecido por la gerencia; y \({{s_1}^-}\), que es la desviación de la meta hacia un nivel inferior, lo que implica quedar por abajo del límite establecido por la gerencia.
Dado lo anterior, la modelación de meta se establece de la siguiente manera:
\[7{x_1}+6{x_2}=30\] Agregando las variables de desviación, la función se escribe de la siguiente forma:
\[7{x_1}+6{x_2}+{{s_1}^+}-{{s_1}^-}=30\] Sin embargo, el objetivo principal de este plantemaiento es minimizar el efecto de las variables de desviación, lo cual implica que si \({{s_1}^+}>0\) y \({{s_1}^-}=0\), la meta planteada será rebasada, mientras que, \({{s_1}^+}=0\) y \({{s_1}^-}>0\), la meta planteada no se alcanzará. El valor mínimo deseable de la función objetivo es cero, y esto solo ocurrirá si se minimizan ambas variables de desviación, es decir, \({{s_1}^+}=0\) y \({{s_1}^-}=0\), lo que implica el cumplimiento de la meta de la gerencia.
De lo anterior se establece la función objetivo del planteamiento, quedando definida como:
\[\begin{equation}
\label{E1}
\tag{1}
Min~{G}={{s_1}^+}+{{s_1}^-}
\end{equation}\]
Mientras que el sistema de restricciones se escribe de la siguiente forma:
\[\begin{equation} \label{E2} \tag{2} 7{x_1}+6{x_2}+{{s_1}^+}-{{s_1}^-}~=~30 \end{equation}\]
\[\begin{equation} \label{E3} \tag{3} 2{x_1}+3{x_2}~{\leq}~12 \end{equation}\]
\[\begin{equation} \label{E4} \tag{4} 6{x_1}+5{x_2}~{\leq}~30 \end{equation}\]
\[\begin{equation} \tag{5} {x_i},{{s_i}^+},{{s_i}^-}{\geq}0 \end{equation}\]
Donde la equación (1) representa la función objetivo, que es minimizar las variables de desviación del modelo planteado, la función (2) es la meta planteada por la gerencia, el ella se establece el límite deseado, la función (3) asegura que el tiempo disponible para cableado no será mayor a 12 horas, la función (4) asegura que el tiempo disponible para ensamble no excederá de 30 horas, la función (5) es la condición lógica de no negatividad.
Ahora se procederá a asignar las variables adicionales al sistema para estar en condiciones de resolverlo mediante el método simplex, dichas variables adiciones son las de holgura y artificiales necesarias según sea el caso, quedando el sistema de la siguiente manera:
\[{G}-{{s_1}^+}-{{s_1}^-}=0\] \[7{x_1}+6{x_2}+{{s_1}^+}-{{s_1}^-}+{r_1}~=~30\] \[2{x_1}+3{x_2}+{h_1}~=~12\] \[6{x_1}+5{x_2}+h_2~=~30\] Donde \(r_1\) corresponde a una variable artificial y las variables \(h_1\) y \(h_2\) corresponden a las variables de holgura.
Para el caso de este curso, se utilizarán paquetes computacionales en lenguaje R para resolver los modelos matemáticos planteados, dada la complejidad de los mismos, esto se abordará en el tema 1.6 de esta unidad.
La única difrencia entre el modelo lineal y el modelo de metas es que mientras que en un modelo lineal tradicional de la forma:
\[Max~~o~~Min~~z({x_i})=f(x_i)\] \[s.a:~~A(x_i){\leq}{b_j}\] \[x_i{\geq}{0}~~{\forall}~{x_i=1,2,...,k}\] Donde \(z(x_i)\) representa la función objetivo en términos de las variables de decisión, misma que se minimiza ó se maximiza, según sea el caso; \(A(x_i)\), término que representa a la matriz A de coeficientes de las restricciones del modelo y el vector \(b_j\), mismo que representa la región factible de la modelación matemática y por último la restricción lógica de no negatividad, misma que asegura que los valores de las variables de decisión sólo podrán asumir valores no mayores o iguales a cero, podrá ser minimizado ó maximizado, mientras que en un modelo de programación de metas de la forma: \[Max~~o´~~Min~~{g_1}=f(x_i)\] \[Max~~o´~~Min~~{g_2}=g(x_i)\] \[\vdots\] \[Max~~o´~~Min~~{g_p}=h(x_i)\] \[s.a:~~A(x_i){\leq}{b_j}\] \[x_i{\geq}{0}~~{\forall}~{x_i=1,2,...,k}\] Deberá revisarse si la meta puede ser cumplida o quedarse corta, de acuerdo a los recursos disponibles para tal fin, es decir, el objetivo de la optimización es acercarse tanto como sea posible al cumplimiento de la meta (Render, Stair, Hanna, & otros, 2006).
Para explicar el modelo de programación de metas múltiples, se tomará el problema de la programación de un paquete publicitario, extraído de libro de Investigación de Operaciones de Hamdy A. Taha (Taha, 2004) en la página 352, mismo que textualmente dice:
TopAd es una nueva agencia de publicidad, con 10 empleados; ha recibido un contrato para promover un producto nuevo. La agencia puede anunciarlo por radio y por televisión. La tabla siguiente contiene datos sobre la cantidad de personas a las que llega cada tipo de anuncio, y sus requisitos de costo y mano de obra:
| Concepto | Radio | Televisión |
|---|---|---|
| Exposición (millones de personas) | 4 | 8 |
| Costo (miles de dólares) | 8 | 24 |
| Empleados Asignados | 1 | 2 |
El contrato prohíbe a TopAd que use más de 6 minutos en anuncios por radio. Además, los anuncios por radio y televisión deben llegar cuando menos a 45 millones de personas. TopAd ha establecido para el proyecto una meta de presupuesto de $100,000 dólares. ¿Cuántos minutos en radio y televisión debe programar TopAd?
En este planteamiento, la gerencia desea cumplir dos metas, la primera es llegar a por lo menos 45 millones de personas y la segunda es no exceder el presupuesto de $100,000 dólares, para esto lo que se debe programar es la cantidad de minutos tanto de radio como de televisión, por lo que éstos serán las variables de decisión, mismas que se definen de la siguiente manera:
\(x_i\)= Tiempo programado en el medio i, por la naturaleza de la variable se considera que ésta es continua.
\(i\)=1,2
1= Minutos de radio
2= Minutos de televisión
Para el problema planteado, se requiere la modelación de dos metas, una que represente la exposición que puede tener cada medio, en el caso del radio, la tabla de información reporta que se puede llegar a 4 \(\frac{millones~de~personas}{minuto}\), mientras que para el caso de la televisión, la tabla de datos reporta que se puede llegar a 8 \(\frac{millones~de~personas}{minuto}\), la meta de la gerencia es llegar por lo menos a 45 millones de personas, por lo que, la meta de exposición, de acuerdo con los objetivos planteados, se escribe de la siguiente manera:
\[4{x_1}+8{x_2}~{\geq}~45\]
La otra meta a modelar es la de presupuesto, dado que la gerencia tiene planteado que no se exceda de la cantidad planteada, para el caso, la tabla de datos reporta, en miles de datos, que se requieren $ 8 \(\frac{miles~de~dólares}{minuto}\) de radio y $ 24 \(\frac{miles~de~dólares}{minuto}\) de televisión y sólo se cuenta con $100 miles de dólares, por lo que, la meta de presupuesto de acuerdo a los objetivos de la gerencia se modela de la siguiente forma:
\[8{x_1}+24{x_2}~{\leq}~100\] Dado lo anterior, se agregan las variables de desviación de para ambas metas, quedando escritas como sigue:
\[4{x_1}+8{x_2}+{{s_1}^+}-{{s_1}^-}~=~45\] \[8{x_1}+24{x_2}+{{s_2}^+}-{{s_2}^-}~=~100\] DAdo que la meta de exposición es de \({\geq}\), la variable de desviación a minimizar es \({{s_1}^+}\), en el caso de la meta de presupuesto, dado que es de \({\leq}\), la variable de desviación a minimizar es \({{s_2}^-}\), por lo que la función objetivo queda definida de la siguiente manera:
\[Min~G~=~{{s_1}^+}+{{s_2}^-}\] Esta meta permite que se minimicen las variables de desviación que se oponen al cumplimiento de las metas, ya sea que se queden cortas, es decir, que no se alcance la exposición deseada o que no se consuma todo el presupuesto, o en caso contrario, que se exceda la exposición prevista por la gerencia y se exceda el presupuesto disponible.
El modelo matemático para el problema de TopAd queda definido de la siguiente manera:
\[\begin{equation} \tag{1} G-{{s_1}^+}-{{s_2}^-}=0 \end{equation}\]
\[\begin{equation} \tag{2} 4{x_1}+8{x_2}+{{s_1}^+}-{{s_1}^-}~=~45 \end{equation}\]
\[\begin{equation} \tag{3} 8{x_1}+24{x_2}+{{s_2}^+}-{{s_2}^-}~=~100 \end{equation}\]
\[\begin{equation} \tag{4} {x_1}+2{x_2}~{\leq}~10 \end{equation}\]
\[\begin{equation} \tag{5} {x_1}~{\leq}~6 \end{equation}\]
\[\begin{equation} \tag{6} {x_i},{{s_i}^+},{{s_i}^-}~{\geq}~0 \end{equation}\]
Donde la ecuación (1) representa la función objetivo, la ecuación (2) representa la meta de exposición, la ecuación (3) representa la meta de presupuesto, la función (4) asegura que no se exceda de 10 empleados en el cumplimiento de las metas, la función (5) asegura que se cumpla la restricción del contrato y la función (6) es la condición lógica de no negatividad.
De la misma manera en que se modeló el problema de una meta, el modelo matmático se reescribe para puderlo utilizar en el algoritmo del método simplex.
Ahora se procederá a asignar las variables adicionales al sistema para estar en condiciones de resolverlo mediante el método simplex, dichas variables adiciones son las de holgura y artificiales necesarias según sea el caso, quedando el sistema de la siguiente manera:
\[G-{{s_1}^+}-{{s_2}^-}=0\] \[4{x_1}+8{x_2}+{{s_1}^+}-{{s_1}^-}+{r_1}~=~45\] \[8{x_1}+24{x_2}+{{s_2}^+}-{{s_2}^-}+{r_2}~=~100\] \[{x_1}+2{x_2}+{h_1}~=~10\] \[{x_1}+{h_2}~=~6\] \[{x_i},{{s_i}^+},{{s_i}^-}~{\geq}~0\] Para este caso particular, se recomienda implementar el procedimiento simplex y comprobarlo mediante los algoritmos que se abordarán en el apartado 1.6 de este contenido temático.
En este modelo, si se tienen \(j\) metas, se tienen que cumplir en orden todas las metas para el cumplimiento de la meta general, como por ejemplo, un proceso de maquinado, una línea de producción, procesos de manufactura lineal, etc.
Para ejemplificar este modelo, se modela el siguiente plantamiento.
Se fabrican dos productos en máquinas consecutivas. La siguiente tabla muestra los tiempos de maquinado, en minutos por unidad, para cada producto(Taha, 2004).
| Tiempo de maquinado, min | ||
| Máquina | Producto 1 | Producto 2 |
| 1 | 5 | 3 |
| 2 | 6 | 2 |
Las cuotas diarias de producción para los dos artículos son 80 y 60 unidades, respectivamente. Cada máquina trabaja 8 horas por día. Se puede recurrir al tiempo extra, aunque no es deseable, si es necesario para llenar la cuota de producción. Formule formule el problema como modelo de programación de metas.
Para este planteamiento, la generencia desea establecer un esquema de producción para cumplir con las cuotas planteadas sin exceder el tiempo de funcionamiento de las máquinas; sin embargo, de ser necesario se puede recurrir a tiempo extra.
Las variables se definen de la siguiente manera:
\(x_i\)= Tiempo, en minutos, de funcionamiento de la máquina \(i\) para lograr la cuota de producción diaria, por la naturaleza de la variable, se considerará continua.
\(i\)= 1,2
1= Minutos de funcionamiento de la máquina 1.
2= Minutos de funcionamiento de la máquina 2.
Para lograr el cumplimiento de las cuotas, se debe plantear un modelo matemático en donde se minimicen las desviaciones del tiempo de funcionamiento de las máquinas, cuidando que no se exceda, dado que si esta situación se hace presente, se tendrá que recurrir a teimpo extra. En la tabla de datos se muestran los tiempos de funcionamiento en cada máquina por producto, sin embargo lo que se desea programar son los tiempos, por lo que, si las unidades presentadas en dicha tabla son \(\frac{minutos}{unidad~producida}\), se deberán programar el número de unidades necesarias para las cuotas de producción.
Por lo tanto, para cada producto, se plantearán las siguientes funciones:
\[5{x_1}+6{x_2}=480\] \[3{x_1}+2{x_2}=480\] Para establecer estas fucniones como metas, se le agrega las variables de desviación, por lo que se reescriben de la siguiente manera:
\[5{x_1}+6{x_2}+{s_1^+}-{s_1^-}=480\] \[3{x_1}+2{x_2}+{s_2^+}-{s_2^-}=480\]
Dentro de este esquema, el sistema está restringido por las propias cuotas de producción, es decir, del producto 1 se debe cumplir la meta de 80 unidades y de la del producto 2 la de 60 unidades, esto se planteará en forma de restricción de la siguiente manera:
\[{x_1}=80\] \[{x_2}=60\] Dado lo anterior, como el objetivo de la gerencia es no recurrir a tiempo extra, a menos que sea estrictamente necesario, las variables de desviación a minimizar son aquellas que coadyuvan a que el objetivo sea rebasado, en este caso las dichas variabes son \(s_1^+\) y\(s_2^+\). Por lo que la función objetivo se escribe de la siguiente manera:
\[Min~G={s_1^+}+{s_2^+}\]
Una vez definido lo anterior, podemos establecer el modelo matemático que nos ayudará a planificar la producción de tal forma que se minimice las desviaciones en torno al tiempo de funcionamiento de las máquinas.
El modelado para el planteamiento en comento queda defindo de la siguiente manera:
\[\begin{equation} \tag{1} Min~G={s_1^+}+{s_2^+} \end{equation}\] \[\begin{equation} \tag{2} 5{x_1}+6{x_2}+{s_1^+}-{s_1^-}=480 \end{equation}\] \[\begin{equation} \tag{3} 3{x_1}+2{x_2}+{s_2^+}-{s_2^-}=480 \end{equation}\] \[\begin{equation} \tag{4} {x_1}=80 \end{equation}\] \[\begin{equation} \tag{5} {x_2}=60 \end{equation}\] \[\begin{equation} \tag{6} {x_1},~{x_2},~{s_1^+},~{s_1^-},~{s_2^+},~{s_2^-}~{\geq}~0 \end{equation}\]
En donde la función (1) asegura que las desviaciones en torno al tiempo de utilización de las máquinas será el mínimo, la ecuación (2) asegura que el tiempo de la máquina uno no se desviará del objetivo de 480 minutos diarios, la ecuación (3) asegura que el tiempo de la máquina dos no se desviará del objetivo de 480 minutos diarios, la ecuación (4) asegura el cumplimiento de la cuota de producción para el Producto 1, la ecuación (5) asegura el cumplimiento de la cuota de producción para el Producto 2 y por último la ecuación (6) es a condición lógica de no negatividad de las variables.
Ahora se procederá a asignar las variables adicionales al sistema para estar en condiciones de resolverlo mediante el método simplex, dichas variables adiciones son las de holgura y artificiales necesarias según sea el caso, quedando el sistema de la siguiente manera:
\[G-{s_1^+}-{s_2^+}=0\] \[5{x_1}+6{x_2}+{s_1^+}-{s_1^-}+{r_1}=480\] \[3{x_1}+2{x_2}+{s_2^+}-{s_2^-}+{r_2}=480\] \[{x_1}+{r_3}=80\] \[{x_2}+{r_4}=60\] Para este caso particular, se recomienda implementar el procedimiento simplex y comprobarlo mediante los algoritmos que se abordarán en el apartado 1.6 de este contenido temático.
Supngamos que el modelo de programación de metas tiene \(n\) metas, y que la \(i-ésima\) meta se expresa como sigue:
\[Min~{G_i}, i=1,2,...,n\] La función objetivo combinada que se usa en este método se define como sigue:
\[Minimizar~Z={w_1}{G_1}+{w_2}{G_2}+{\dotsm}~+{w_i}{G_i}\] El parámetro \(w_i\), \(i=1,2,...,n\), representa factores de ponderación positivos que reflejan las preferencias de quien toma las decisiones, respecto a la importancia relativa de cada meta. Por ejemplo, \({w_i}=1\), pata toda \(i\) significa que todas las metas tienen el mismo factor de ponderación, es decir, la misma importancia desde el punto de vista de quien toma la decisión. La determinación de los valores específicos de esos factores es subjetiva, es decir, tienen que ver más con las experiencias y sentimientos del decisor, pudiendo cambiar de una a otra persona(Taha, 2004).
En el método de jerarquías, quien toma las decisiones debe clasificar las metas del problema por orden de importancia. Dado un caso de \(n\) metas, los objetivos del problema se escriben como sigue:
\[Minimizar~{G_1}={\rho_1}~(Máxima~Prioridad)\] \[\vdots\] \[Minimizar~{G_n}={\rho_n}~(Mínima~Prioridad)\]
Este método ordena las metas por orden de prioridad y una vez obtenida la solución para la meta prioritaria, se reescribe como una restricción de un nuevo programa lineal que tiene como función objetivo la minimización de la siguiente meta en orden de importancia, y así sucesivamente hasta terminar con la meta menos prioritaria. Este método tiene la característica de reuerir un número elevado de cálculos, lo que hace que piere eficiencia.
En muchas ocasiones, dada la complejidad del modelo a resolver, el elevado número de variables involucradas y el elevado número de funciones que estan planteadas, resulta indispensable la utilización de un software que nos permita procesar los resultados y así establecer con mayor facilidad las conclusiones necesarias, para este fin, utilizaremos las paqueterias de R-Project denominadas ompr y ROI, las cuales nos van a permitir modelar de manera simple los planteamientos.
A manera de ejemplo se resolverá el modelo de cada uno de los tipos de metas aquí comentados.
Para el ejemplo de la compañía de Harrison Electric, se prcederá en el mismo orden en que se planteó, es decir:
Resolveremos nuestro modelo con la siguiente línea de comandos, en donde las variables de desviación serán escritas de otra manera para que puedan ser leídas por el software, es decir, la variable \({s_1^+}\) se escribirá como s[1,1], mientras que la variable \(s_2^+\) se escribirá s[2,1], es decir el signo positivo se cambiará por el número 1 y el negativo por el número 2, quedando el código de la siguiente manera:
library(ROI)
library(ROI.plugin.glpk)
library(ompr)
library(ompr.roi)
library(dplyr)
modelo_harrison=MILPModel()%>%
add_variable(x[i],i=1:2,type = "integer")%>% #Definición de las variables xi
add_variable(s[i,j],i=1,j=1:2,type= "integer")%>% #Definición de las variables si
set_objective(s[1,1]+s[1,2],sense = "min")%>% #Definicion de la funcion objetivo
add_constraint(7*x[1]+6*x[2]+s[1,1]-s[1,2]>=30)%>% #Defincion de las restricciones
add_constraint(2*x[1]+3*x[2]<=12)%>%
add_constraint(6*x[1]+5*x[2]<=30)%>%
add_constraint(x[i]>=0,i=1:2)%>%
add_constraint(s[i,j]>=0,i=1,j=1:2)
solucion_harrison=solve_model(modelo_harrison,with_ROI(solver = "glpk",verbose=TRUE))## <SOLVER MSG> ----
## GLPK Simplex Optimizer, v4.65
## 7 rows, 4 columns, 12 non-zeros
## 0: obj = 0.000000000e+00 inf = 3.000e+01 (1)
## 1: obj = 0.000000000e+00 inf = 0.000e+00 (0)
## * 3: obj = 0.000000000e+00 inf = 0.000e+00 (0)
## OPTIMAL LP SOLUTION FOUND
## GLPK Integer Optimizer, v4.65
## 7 rows, 4 columns, 12 non-zeros
## 4 integer variables, none of which are binary
## Integer optimization begins...
## Long-step dual simplex will be used
## + 3: mip = not found yet >= -inf (1; 0)
## Solution found by heuristic: 0
## + 6: mip = 0.000000000e+00 >= tree is empty 0.0% (0; 7)
## INTEGER OPTIMAL SOLUTION FOUND
## <!SOLVER MSG> ----print(solucion_harrison$objective_value)## [1] 0get_solution(solucion_harrison,x[i])## variable i value
## 1 x 1 3
## 2 x 2 2get_solution(solucion_harrison,s[i,j])## variable i j value
## 1 s 1 1 0
## 2 s 1 2 0La solución de compromiso para este caso que arroja el modelo matemático es que se logra la minimización de las dos variables de desviación \(s_1^+\) y \(s_1^-\), para el caso de las variables de decisión, a sugerencia del modelo matemático se deben producir:
Con estos valores se logra obtener una ganancia de $33 , es decir, se rebasa la meta de utilidades, asi mismo, para la primera restricción, en la que se establece un límite de 12 horas de cableado, con esta producción, se utilizan las doce horas disponibles, y para el caso de la restricción 2, en la que se establce un límite de 30 horas de ensamble, se utilizan un total de 28 horas de ensamble, por lo que se cumplen las restricciones planteadas por la gerencia.
Para el caso del modelo propuesto para la empresa TopAd, se propone el siguiente código para su solución:
library(ROI)
library(ROI.plugin.glpk)
library(ompr)
library(ompr.roi)
library(dplyr)
modelo_topad=MILPModel()%>%
add_variable(x[i],i=1:2,type = "continuous")%>%
add_variable(s[i,j],i=1:2,j=1:2,type = "continuous")%>%
set_objective(s[1,1]+s[2,2],sense = "min")%>%
add_constraint(4*x[1]+8*x[2]+s[1,1]-s[1,2]==45)%>%
add_constraint(8*x[1]+24*x[2]+s[2,1]-s[2,2]==100)%>%
add_constraint(x[1]+2*x[2]<=10)%>%
add_constraint(x[1]<=6)%>%
add_constraint(x[i]>=0,i=1:2)%>%
add_constraint(s[i,j]>=0,i=1:2,j=1:2)
solucion_topad=solve_model(modelo_topad,with_ROI(solver = "glpk",verbose=TRUE))## <SOLVER MSG> ----
## GLPK Simplex Optimizer, v4.65
## 10 rows, 6 columns, 17 non-zeros
## 0: obj = 0.000000000e+00 inf = 1.450e+02 (2)
## 3: obj = 5.000000000e+00 inf = 0.000e+00 (0)
## * 5: obj = 5.000000000e+00 inf = 0.000e+00 (0)
## OPTIMAL LP SOLUTION FOUND
## <!SOLVER MSG> ----print(solucion_topad$objective_value)## [1] 5get_solution(solucion_topad,x[i])## variable i value
## 1 x 1 5.0
## 2 x 2 2.5get_solution(solucion_topad,s[i,j])## variable i j value
## 1 s 1 1 5
## 2 s 2 1 0
## 3 s 1 2 0
## 4 s 2 2 0La solución de compromiso para este caso que arroja el modelo matemático es que se no se logra la minimización de la variable de desviación correspondiente a la exposición, es decir, no se logra minimizar la variable \(s_1^+\), por lo que se concluye que la meta de exposición no se cumplirá y harían falta 5 millones de personas para cumplirla, en el caso de las demás variables de desviación, no existe problema alguno dado que se logran minimizar las variables de desviación, es decir, asumen un valor a nivel cero.
A sugerencia del modelo, se deben programar:
Con estos valores, sustityéndolos en las restricciones, se logra llegar a una exposición de 40 millones de personas, lo que evidente no es valor deseable para la empresa, sin embargo se logra el cumplimiento de la meta de presupuesto, es decir, se ejerce solamente $96,000 dólares.
Para el caso del modelo propuesto para la programación de producción, se propone el siguiente código para su solución:
library(ROI)
library(ROI.plugin.glpk)
library(ompr)
library(ompr.roi)
library(dplyr)
modelo_produccion=MILPModel()%>%
add_variable(x[i],i=1:2,type = "continuous")%>%
add_variable(s[i,j],i=1:2,j=1:2,type = "continuous")%>%
set_objective(s[1,1]+s[2,1],sense = "min")%>%
add_constraint(5*x[1]+6*x[2]+s[1,1]-s[1,2]==480)%>%
add_constraint(3*x[1]+2*x[2]+s[2,1]-s[2,2]==480)%>%
add_constraint(x[1]==80)%>%
add_constraint(x[2]==60)%>%
add_constraint(x[i]>=0,i=1:2)%>%
add_constraint(s[i,j]>=0,i=1:2,j=1:2)
solucion_produccion=solve_model(modelo_produccion,with_ROI(solver = "glpk",verbose=TRUE))## <SOLVER MSG> ----
## GLPK Simplex Optimizer, v4.65
## 10 rows, 6 columns, 16 non-zeros
## 0: obj = 0.000000000e+00 inf = 1.100e+03 (4)
## 5: obj = 1.200000000e+02 inf = 0.000e+00 (0)
## * 6: obj = 1.200000000e+02 inf = 0.000e+00 (0)
## OPTIMAL LP SOLUTION FOUND
## <!SOLVER MSG> ----print(solucion_produccion$objective_value)## [1] 120get_solution(solucion_produccion,x[i])## variable i value
## 1 x 1 80
## 2 x 2 60get_solution(solucion_produccion,s[i,j])## variable i j value
## 1 s 1 1 0
## 2 s 2 1 120
## 3 s 1 2 280
## 4 s 2 2 0La solución al modelo propuesto da como resultado que la variable de desviación \(s_2^+\) no logra minimizarse, esta variable está asociada a la programación para el producto 2, por lo cual es de esperarse que, para completar las cuotas de producción, se rebase el tiempo límite de las máquinas, es decir, se tendrá que recurir a 120 minutos de tiempo extra, sólo así se podrá cumplir con \({x_1^*=80}\) y \({x_2^*}=60\).