Notas Optimizacion Ingenieros

OPTIMIZACIÓN PARA INGENIEROS CONHERRAMIENTAS INFORMÁTICAS

Versión 1.1

Ing. M.Sc. Antonio Medrano

1 de abril de 2015

Índice general

I. ASPECTOS BÁSICOS 5

1. INTRODUCCION 6

2. CONCEPTOS BÁSICOS DE OPTIMIZACIÓN 82.1. Tipos de Optimización . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2. Desarrollo de un Modelo para Optimización . . . . . . . . . . . . . . . . . . . . . 9

3. HERRAMIENTAS INFORMÁTICAS 123.1. Introducción al Software Libre de Código Abierto . . . . . . . . . . . . . . . . . . 123.2. Software a utilizar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.2.1. Maxima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.2.2. OpenO�ce Calc/LibreO�ce Calc . . . . . . . . . . . . . . . . . . . . . . . 143.2.3. SmathStudio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.2.4. Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.2.5. Octave . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.2.6. Scilab . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

II. OPTIMIZACIÓN APLICADA 20

4. OPTIMIZACIÓN NO LINEAL NO RESTRINGIDA EN UNA VARIABLE 214.1. Desarrollo de un modelo de Optimización . . . . . . . . . . . . . . . . . . . . . . 214.2. Optimización No Lineal en Maxima . . . . . . . . . . . . . . . . . . . . . . . . . . 224.3. Optimización No Lineal en Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.3.1. Caso Especial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.4. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5. OPTIMIZACIÓN LINEAL RESTRINGIDA EN VARIAS VARIABLES 355.1. Programación Lineal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5.1.1. Programación Lineal en Maxima . . . . . . . . . . . . . . . . . . . . . . . 385.1.2. Programación Lineal en OpenO�ce/LibreO�ce Calc . . . . . . . . . . . . 415.1.3. Programación Lineal en Sage . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.2. Modelos de Redes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485.2.1. Modelo de Transporte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505.2.2. Modelo de Asignación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.2.3. Modelo de Ruta Más Corta . . . . . . . . . . . . . . . . . . . . . . . . . . 585.2.4. Modelo de Flujo Máximo . . . . . . . . . . . . . . . . . . . . . . . . . . . 635.2.5. Arbol Mínimo de Expansión . . . . . . . . . . . . . . . . . . . . . . . . . . 685.2.6. Problema del Agente Viajero . . . . . . . . . . . . . . . . . . . . . . . . . 71

5.3. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735.3.1. Ejercicios Programación Lineal . . . . . . . . . . . . . . . . . . . . . . . . 735.3.2. Ejercicios Modelo de Transporte . . . . . . . . . . . . . . . . . . . . . . . 735.3.3. Ejercicios Modelo de Asignación . . . . . . . . . . . . . . . . . . . . . . . 735.3.4. Ejercicios Ruta Más Corta . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

2

Índice general

5.3.5. Ejercicios Flujo Máximo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735.3.6. Ejercicios Arbol Mínimo de Expansión . . . . . . . . . . . . . . . . . . . . 73

6. OPTIMIZACIÓN NO LINEAL NO RESTRINGIDA EN VARIAS VARIABLES 746.1. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

7. OPTIMIZACIÓN NO LINEAL RESTRINGIDA EN VARIAS VARIABLES 787.1. RESTRICCIONES DE IGUALDAD . . . . . . . . . . . . . . . . . . . . . . . . . 787.2. RESTRICCIONES DE DESIGUALDAD . . . . . . . . . . . . . . . . . . . . . . . 807.3. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

8. MÉTODOS HEURÍSTICOS PARA OPTIMIZACIÓN 85

III. MODELOS DE LINEAS DE ESPERA 86

3

Índice de �guras

1.1. Mapa Conceptual del Contenido . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1. Proceso de Solución de Problemas de Optimización . . . . . . . . . . . . . . . . . 92.2. Proceso para el desarrollo de un modelo de optimización . . . . . . . . . . . . . . 11

3.1. Imagenes de Maxima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.2. Solver de Calc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.3. Imagen de SmathStudio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.4. Imagenes de Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.5. Imagenes de Octave . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.6. Imagenes de Scilab . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

5.1. Ejemplos de Redes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495.2. Tipos de Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505.3. Ejemplo de una red con pesos (distancia) y sus respectivas matrices . . . . . . . 505.4. Ruta Mas Corta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585.5. Ejemplos de árbol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

7.1. Ejemplo de una función con muchos óptimos locales . . . . . . . . . . . . . . . . 81

4

Parte I.

ASPECTOS BÁSICOS

5

1. INTRODUCCION

La idea de desarrollar estas notas surgió hace algunos años cuando me fué solicitado porprimera vez impartir el curso denominado Algebra y Tecnología Informática en la Maestría enIngeniería Vial de la Universidad de San Carlos de Guatemala. El objetivo de ese curso, comome fué planteado en ese momento, era que los estudiantes de maestría aprendieran a utilizarherramientas informáticas para la solución de problemas matemáticos complejos.Inicialmente se me solicitó que el curso se orientara al uso del programa Matlab®1 como la

base del curso. Matlab® es reconocido a nivel mudial como la herramienta de cálculo mate-mático mas utilizada en ciencia e ingeniería. Sin embargo, por tratarse de un programa de tipocomercial, su uso implica el pago de una licencia por un período de tiempo limitado. Esto traeserias desventajas ya que para desarrollar el curso se requiere un laboratorio equipado con el pro-grama y las respectivas licencias, lo cual presentaba un obstáculo, tanto para impartir las clasesmagistrales como para que los estudiantes llevaran a cabo las respectivas prácticas de aplicaciónpara familiarizarse con el aplicativo.Otro aspecto que vale la pena mencionar, es algo que he podido observar y comprobar a través

de mi propia experiencia: Para aprender a utilizar una herramienta, del tipo que sea (mecánica,tecnológica u otro tipo) es necesario tener un propósito u objetivo de�nido para su uso. El procesode aprendizaje de los procedimientos y métodos para el uso de aplicaciones informáticas, cuandono se dá dentro de un contexto especí�co, es frágil y poco e�caz, ya que los estudiantes aprendenel �cómo� pero no el �para qué�, por lo que mas temprano que tarde los conocimientos caen en elolvido. Muchos de los estudiantes que cursan la maestría son profesionales que culminaron susestudios a nivel de licenciatura hace ya varios años y mucho de sus conceptos matemáticos seencuentran en desuso lo que di�culta aún mas el proceso, ya que en muchos casos hay que volvera visitar temas básicos en las distintas áreas como álgebra, cálculo diferencial e integral, algebramatricial, etc.Para subsanar la primera di�cultad, relacionada con el uso de programas comerciales que

requieren licencia, he optado en los últimos años por el uso de aplicaciones que pertenecen a lacorriente del Software Libre (FOSS, Free and Open Source Software, por sus siglas en inglés).Dentro de esta categoría se encuentra un conjunto de herramientas que poseen todas o casi todaslas características requeridas para cumplir el objetivo del curso, que son igual o en algunos casosmás poderosas que el software comercial y que tienen la enorme ventaja de que pueden obtenersesin ningún tipo de restricción para su instalación y uso, en forma gratuita y por tiempo inde�nido.Otro aspecto que considero importante es el no restringir el curso a una sola aplicación, puesto

que eso limita al estudiante al uso del software que conoce, lo que ocasiona que al encontrarse enel ejercicio profesional, si dicho progrma no está disponible y más aún si se trata de un softwarecomercial cuyo costo de licenciamiento es elevado, no pueda tener las herramientas necesarias parala solución de problemas. Es por tal razón que en este curso se presentan varias herramientasque pueden usarse en distintas situaciones, algunas en más de una situación, lo que abre lasposibilidades de tener un arsenal bien equipado para afrontar cualquier problema matemático.En lo que respecta al segundo inconveniente, el del propósito de�nido, opté por un campo

de suma importancia en todas las ramas de ingeniería, pero que lamentablemente no siempreestá incluído en las redes de estudio de algunas ingenierías: la optimización. El objetivo de todoingeniero, independientemente de su área de especialización, es resolver problemas haciendo usoóptimo de los recursos a su disposición, por lo que este tema debería ser de inclusión obligada en

1http://www.mathworks.com/products/matlab/

6

1. INTRODUCCION

Figura 1.1.: Mapa Conceptual del Contenido

todos los programas académicos de ingeniería. En el caso de la Ingeniería Civil, que es de dondeprovienen la mayoría de profesionales que cursan la Maestría en Ingeniería Vial, este tema no seincluye en su malla curricular.Combinando entonces un propósito claramente de�nido con un conjunto de herramientas dis-

ponibles y aptas para tal �n, surge el curso que más apropiadamente se denomina Optimizaciónpara Ingenieros con Herramientas Informáticas y esta compilación de apuntes que tienen comopropósito servir como guía y referencia para los estudiantes, debido a la poca disponibilidadde material sobre el tema especí�co. Cabe aclarar que el objetivo del curso y por ende de estosapuntes, es presentar al estudiante y al profesional un enfoque práctico y aplicado de las metodo-logías discutidas, en vez de profundizar en el aspecto teórico y el rigor matemático de los temasya que sobre eso existe su�ciente material de muy buena calidad y que se encuentra disponible,por lo que se pide a los lectores mantener esto en mente al utilizar los apuntes. Estas notas nopretenden servir como libro de texto, por lo que si se requiere profundizar en la parte teórica yconceptual de los métodos y las herramientas aquí presentadas, en la sección de Bibliografía seencuentra una lista de referencias que pueden ser consultadas.

7

2. CONCEPTOS BÁSICOS DEOPTIMIZACIÓN

Para iniciar, es necesario de�nir y delimitar el campo de acción sobre el cual se desarrollaráel curso: la optimización. Al enfrentarse al proceso de solución de problemas, los ingenieros seencuentran generalmente con una o varias soluciones al mismo, sin embargo, la solución óptimaen un sentido muy general es aquella que es la mejor entre todas las soluciones posibles.La optimización en ingeniería es una mezcla de ciencia y arte. La existencia de un conjunto de

algoritmos de optimización, es decir, procedimientos ya de�nidos, demostrados y probados paraobtener la solución óptima para determinados modelos de problema es la parte que cae dentrodel ámbito cientí�co y abarca áreas de conocimiento tales como la matemática, la estadística ylas ciencias de la computación. Sin embargo, la parte generalmente más difícil y que se convierteen un arte que requiere de mucho criterio y experiencia consiste en convertir el problema realen un modelo al cual pueda aplicarse alguno de los algoritmos mencionados, luego seleccionar yaplicar el algoritmo adecuado al modelo y �nalmente analizar la solución obtenida y convertirlaen una o varias decisiones que puedan ser tomadas sobre el problema real ya que muchas vecesla respuesta proporcionada por el algoritmo no puede aplicarse tal cual al problema original.

2.1. Tipos de Optimización

Existen muchos criterios bajo los cuales puede categorizarse un problema de optimización.1Eneste curso no se pretende abarcar todos los tipos de problema de optimización existentes. Lostipos de optimización puede clasi�carse de acuerdo a los siguientes criterios:

Por la cantidad de variables de decisión involucradas

� Univariada: Una sola variable de decisión.

� Multivariada: Dos o mas variables de decisión.

Por el grado de las variables de decisión y sus relaciones en la función objetivo y/o lasrestricciones:

� Lineal: Todas las variables en el objetivo y las restricciones tienen un exponente iguala 1 y las operaciones que se realizan entre ellas son solamente suma y resta.

� No Lineal: Existen variables con exponentes distintos a 1 y/o existen operacionesdistintas a suma/resta entre las variables de decisión.

Por la presencia o ausencia de restricciones en el modelo:

� No Restringida: Se desea optimizar una función objetivo pero no existen restriccionesadicionales a considerar en el modelo.

� Restringida: Se desea optimizar una función objetivo sujeto al cumplimiento de unao mas restricciones.

Por el dominio de las variables de decisión:

1http://en.wikipedia.org/wiki/Mathematical_optimization

8

2. CONCEPTOS BÁSICOS DE OPTIMIZACIÓN

Figura 2.1.: Proceso de Solución de Problemas de Optimización

� Continua: Las variables de decisión pertenecen al conjunto de los números reales ypueden tomar cualquier valor en dicho conjunto.

� Discreta: Las variables solo pueden tomar ciertos valores. Un caso especial es el casode la optimización entera.

� Combinatoria: Las variables de decisión solo pueden tomar valores dentro de un con-junto de�nido y se busca encontrar la combinación de valores para las distintas varia-bles que hace óptimo el resultado.

Por la cantidad de objetivos de optimización:

� Uniobjetivo: Un solo objetivo o función objetivo.

� Multiobjetivo: Dos o mas objetivos que compiten entre sí por los recursos.

Estos son solamente algunos de los criterios de clasi�cación de un problema de optimización,pero cada uno de ellos puede a su vez dividirse en otras categorías.En el sentido estríctamente matemático, una solución óptima está asociada directamente con

un punto de in�exión de una función, el cual, dependiendo del objetivo, puede tratarse de unmáximo o un mínimo, por lo que cuando hablamos de optimizar, estamos hablando de encontrarpara un conjunto de variables de decisión, los valores que maximizan o minimizan una funciónobjetivo al mismo tiempo que satisfacen un conjunto de restricciones que existen en el modelo.

2.2. Desarrollo de un Modelo para Optimización

A continuación se describe un procedimiento para el desarrollo de un modelo matemático.Al principio, mientras el estudiante se acostumbra a realizar el proceso de pensamiento paramodelar, se sugiere seguir paso a paso este algoritmo en forma sistemática. Con el paso deltiempo y la práctica constante, el proceso se volverá algo natural e intuitivo.

1. Entender el problema: Aunque pueda parecer obvio e innecesario incluír este paso explí-citamente, la experiencia en la solución de problemas muestra que la causa principal porla que se fracasa, es precisamente porque no se ha de�nido y delimitado correctamente

9


el problema a resolver por lo que no existe una comprensión del mismo. Para asegurar elcorrecto entendimiento del problema, hay varias estrategias que pueden seguirse, entre lascuales una de las más útiles es hacer un esquema, dibujo o diagrama del problema, de unaforma simple pero tratando de representar grá�camente todos los aspectos de la situación.

2. Identi�car el objetivo: Como se mencionó en la sección anterior, un problema de optimiza-ción busca siempre uno de dos objetivos posibles, maximizar o minimizar algo. En función ala información proporcionada y al contexto del problema en cuestión, es posible identi�cardicho objetivo. Por ejemplo, si en un problema se está tratando con aspectos como costos,distancia, mano de obra o materiales, es fácil llegar a la conclusión que lo que se buscaes minimizar dichos aspectos. Por el contrario, si se está hablando de cosas como ventas,ingresos, dinero, ganancias, rendimiento, etc. puede inferirse que el objetivo perseguido esmaximizar tales cosas.

3. Identi�car las variables de decisión: Las variables de decisión son, como su nombre losugiere, aquellos aspectos del modelo que se encuentran bajo el control del tomador dedecisiones, de manera que ajustando el valor de dichas variables, se modi�ca el resultadodel modelo. Generalmente estas variables son representadas matemáticamente en forma deun vector de la forma X = x1, x2, x3,...según sea la cantidad de variables que existen enel modelo.

4. Expresar el objetivo como una función matemática de las variables de decisión: Este pasoconsiste en identi�car las relaciones matemáticas existentes entre las variables de deci-sión que producen el objetivo del paso 2. A esta función matemática se le llama FunciónObjetivo. Expresado en forma matemática:

max o min Z = f(x1, x2, x3, ...)

5. Identi�car las restricciones en el problema: Una restricción en un problema de optimiza-ción se re�ere a cualquier obstáculo que nos impide obtener un resultado ideal o deseado.Generalmente las restricciones se originan de las siguientes situaciones:

a) Limitaciones de recursos disponibles, tales como materia prima, tiempo, espacio, per-sonal, etc.

b) Requerimientos que deben ser cumplidos, tales como cantidades mínimas de produc-ción, especi�caciones de producto, calidad, etc.

c) Condiciones sobre las variables de decisión para su aplicación en la práctica, como porejemplo, variables no negativas, variables enteras, variables binarias, etc.

6. Expresar las restricciónes como relaciones entre las variables de decisión: Las relacionespara representar las restricciones no se limitan solamente a relaciones de igualdad sino quepueden expresarse también como desigualdades, por lo que es importante tener muy clarala naturaleza de la restricción, es decir, saber si:

a) Debe cumplirse con un valor especí�co: Restricción de igualdad =

b) Existe un valor mínimo que debe alcanzarse: Restricción de desigualdad del tipo ≥c) Existe un valor máximo que no puede excederse: Restricción de desigualdad del tipo≤

7. Expresar el modelo en una forma canónica o estándar: Esto permitirá identi�car y aplicarcorrectamente el algoritmo de solución en la etapa correspondiente. Ciertos algoritmosrequieren que el problema esté expresado en una forma de�nida para iniciar el proceso desolución.

Este proceso se entenderá mas claramente en los siguientes capítulos cuando se desarrolleen el contexto de un caso especí�co.

10


Figura 2.2.: Proceso para el desarrollo de un modelo de optimización

11

3. HERRAMIENTAS INFORMÁTICAS

Como se mencionó en la introducción, este es un curso eminentemente práctico y aplicado, porlo que la solución de los modelos de optimización se hará únicamente por medio de herramientasinformáticas, así que en este capítulo se hará una breve introducción a las mismas. Se presentanen la seccion de bibliografía varias referencias donde el estudiante puede consultar en detalle lateoría detrás de cada uno de los algoritmos, así como su desarrollo en forma manual si necesitaconocerlo.

3.1. Introducción al Software Libre de Código Abierto

El movimiento de software libre de código abierto (Free and Open Source Software o FOSS)1

surgió durante la década de 1980 como una respuesta al cambio en el modelo de negocios en elmundo de la informática. Anteriormente, los programas de computadoras eran incluídos comoparte de la venta del equipo o hardware y era permitido realizar copias del mismo y tener accesoincluso al código fuente para poder hacer modi�caciones para adaptarlo a las necesidades parti-culares. Con el advenimiento del mercado de programas informáticos, principalmente impulsadoa �nales de la década de 1970 con el surgimiendo de Microsoft®, el software se convirtió enun producto que se vendía por separado, bajo un modelo de licenciamiento para su uso, lo cualimplica una serie de restricciones ya que las compañías desarrolladoras mantienen todos los de-rechos sobre el mismo, lo cual impide al comprador copiarlo, instalarlo en otras computadoras,ver el código fuente para entender su funcionamiento o hacer modi�caciones o adaptaciones deacuerdo a sus propias necesidades.En 1983 Richard Stallman2, un académico e informático de MIT funda el movimiento de

software libre cuyo objetivo es desarrollar programas que puedan ser de libre acceso para quienesdeseen usarlos. Las características de una aplicación de software libre son principalmente lassiguientes:

Puede ser obtenido en forma gratuita, aunque esto no siempre es totalmente cierto, ya quealgunas veces se puede cobrar el costo del medio en el cual se distribuya, pero no existe unpago por licencia para su uso.

Puede copiarse las veces que se desee e instalarse en todas las computadoras que se requiera,sin limitaciones ni restricción alguna.

Se puede tener acceso al código fuente para poder estudiar y comprender su funcionamiento.También puede modi�carse si es necesario para adaptarlo a distintas necesidades.

Este último aspecto es especialmente importante en el caso especí�co de los programas cientí�cosdebido a que en el proceso de investigación y desarrollo, así como en la solución de problemas,no es válido el modelo de �caja negra� utilizado por el software comercial, donde se aceptan losresultados obtenidos sin validar la forma de obtenerlos, por lo que es sumamente importanteentender los algoritmos que los programas utilizan.Con la llegada y expansión de internet a nivel global, el movimiento de software libre se ha

fortalecido y extendido de tal forma que en la actualidad, los programas desarrollados bajo estemodelo, compiten con los programas comerciales en calidad, incluso en algunos casos superando

1http://en.wikipedia.org/wiki/Free_and_open-source_software2http://es.wikipedia.org/wiki/Richard_Stallman

12


a sus pares comerciales. Muchas organizaciones en todo el mundo han adoptado el sofware librepor diversas razones, siendo una de ellas el ahorro en los costos de licencia, pero en muchos casosno es la principal, sino que se ha comprobado la calidad y versatilidad de los programas librespor encima del software comercial.En este curso estaremos utilizando varias aplicaciones que pertenecen a la categoría de software

libre, lo cual presenta una serie de ventajas para el desarrollo del programa del curso. Entre lasventajas podemos mencionar las siguientes:

Todos los programas a utilizar pueden ser descargados de internet sin ningún costo.

Pueden instalarse en las computadoras personales de los estudiantes, lo que les permitetenerlos siempre disponibles para realizar prácticas y tareas. La mayoría de ellos puede serinstalado en diversos sistemas operativos como MS Windows®, Linux o Mac OS®

Pueden utilizarlo sin restricción, incluso para �nes comerciales por lo que pueden aplicarloen su ejercicio profesional.

Existe una gran cantidad de material de referencia disponible en internet para aprender autilizarlo.

Los programas se encuentran en constante desarrollo por parte de una comunidad muyactiva alrededor del mundo, por lo que frecuentemente se liberan versiones actualizadas ymejoradas.

3.2. Software a utilizar

En esta sección se enumera cada una de las aplicaciones de software libre que pueden utilizarsepara resolver problemas de optimización y se hace una breve reseña de ellas, indicando su principalárea de aplicación así como algunas de sus características mas importantes. Cuando es pertinentese indica el nombre de un programa comercial similar para usarlo como referencia y punto decomparación en cuanto a funcionalidad. Es posible que no todas sean utilizadas en el curso, peroes importante conocer su existencia y aplicación para quienes deseen en un futuro profundizarsobre alguna de ellas.

3.2.1. Maxima

Maxima puede ser catalogado dentro de la categoría de los CAS (Computer Algebra Systems).Un CAS es un programa matemático cuya fortaleza radica en la capacidad de realizar operacio-nes y manipulación sobre objetos simbólicos. Es decir, un CAS es capaz de tomar una expresiónrepresentada en forma simbólica y realizar operaciones básicas (suma, multiplicacion, exponen-ciación, etc.) y también operaciones más avanzadas como derivación e integración simbólica,representación grá�ca, solución de ecuaciones, etc.Maxima desciende del programa más antíguo dentro de los CAS, llamado Macsyma, que fué

desarrollado en la década de 1960. Es una herramienta sumamente completa, poderosa, versátily estable, aparte de ser una aplicación 100% libre. Dentro del tema de optimización, puede seraplicado en los siguientes casos:

Optimización No Lineal y No Restringida para una variable

Optimización Lineal Restringida Multivariada

Optimizacion No Lineal Restringida Multivariada

13


Figura 3.1.: Imagenes de Maxima

Maxima es similar en funcionalidades a algunos programas comerciales tales como Mathemati-ca®3, Maple®4 o MathCad®5.Maxima puede ser descargado en la siguiente dirección:http://maxima.sourceforge.net/

3.2.2. OpenO�ce Calc/LibreO�ce Calc

OpenO�ce es una suite de o�cina que compite con la omnipresente Microsoft O�ce®. Dehecho, existe un alto nivel de compatibilidad entre ellas de manera que OpenO�ce puede abrirarchivos de O�ce. Aunque la suite se compone de una serie de aplicaciones (procesador de texto,herramienta de presentaciones, base de datos, etc.) nos interesa principalmente su aplicación deHoja Electrónica, llamada Calc, muy similar y compatible con Excel de MS O�ce, por lo quelos procedimientos de optimización pueden fácilmente y con pocos cambios, replicarse de unaherramienta a otra.Existen 2 opciones para escoger en el caso de Calc. La primera es OpenO�ce (anteriormente

llamada StarO�ce), que es la herramienta más antigua, con casi 20 años de existencia y que haalcanzado un nivel de madurez y estabilidad que permite sea utilizado en muchas organizaconesen el mundo como un sustituto de Excel. La segunda opción es LibreO�ce, que es una derivaciónque hizo un grupo de desarrolladores en el 2010 a partir de OpenO�ce cuando éste fué adquiridopor Oracle. Por tratarse de aplicaciones de software libre, el código fuente original de LibreO�ceera el mismo que OpenO�ce por lo que ambos son casi idénticos, lo que implica que puede usarseuno u otro indistintamente.

3http://www.wolfram.com/4http://www.maplesoft.com/products/maple/5http://www.ptc.com/product/mathcad/

14


Figura 3.2.: Solver de Calc

Por tratarse de una hoja electrónica, Calc puede utilizarse para un sinfín de propósitos comoherramienta de cálculo. En el caso de la optimización, las 3 aplicaciones aquí mencionadas cuentancon una herramienta denominada �solver� que permite resolver problemas de distinta índole.Dado que muchas personas están familiarizadas con el uso de hojas electrónicas, así como suestructura matricial de celdas, se hace muy sencillo el planteamiento de modelos, especialmenteen el tema de optimización de redes, tema de mucha importancia en la ingeniería vial.OpenO�ce puede ser descargado en:http://www.openoffice.org/

LibreO�ce puede ser descargado en:http://www.libreoffice.org/

3.2.3. SmathStudio

SmathStudio es una herramienta con cierto nivel de similitud con la herramienta comercialMathCad® mencionada anteriormente. Se trata de una aplicación de cálculo matemático in-teractiva que permite plasmar expresiones matemáticas y obtener los resultados utilizando lasimbología técnica tal y como se presenta en la mayoría de libros de texto y como si se estuvie-se trabajando sobre una hoja de papel. SmathStudio funciona bajo el concepto de region de

cálculo, es decir que el resultado de una expresión depende del área donde dicha expresión seencuentre.Adicionalmente, posee la capacidad de implementar algoritmos gracias a su capacidad de

programación, lo que hace que sea muy fácil y rápido el desarrollo de procesos de cálculo que enotras herramientas serían relativamente complejos o extensos.En este curso se utilizará esta herramienta para desarrollar los modelos analíticos para el

estudio de líneas de espera, o Teoría de Colas, ya que permite utilizar la misma nomenclatura ysimbología que se utiliza en la mayor parte de literatura sobre el tema.SmathStudio no es un programa que cumpla en su totalidad con las características de un

software libre, puesto que su código fuente no se pone a disposición de los usuarios, sin embargo,se trata de una aplicación gratuita y que puede utilizarse para los propósitos que se desee, porlo que llena los requerimientos para ser utilizada en este curso.

15


Figura 3.3.: Imagen de SmathStudio

SmathStudio puede obtenerse en la siguiente dirección:http://en.smath.info/forum/

3.2.4. Sage

Sage es, quizá, el proyecto de software libre matemático más ambicioso y completo existen-te en la actualidad. Siendo un programa relativamente nuevo, iniciado en el 2005, ha logradoconsolidarse en los circulos académicos mundiales como una herramienta predilecta por variasrazones. La primera, Sage no reinventó la rueda partiendo de cero en su desarrollo, sino que haceuso de muchas otras aplicaciones matemáticas de sofware libre ya existentes las cuales integra enuna sola interfaz, lo que lo hace extremadamente poderoso y versátil. Otra razón es el hecho quecombina todas las herramientas con el poder y sencillez del lenguaje de programación de másrápido crecimiento: Python.Las aplicaciones de Sage abarcan una amplia gama de temas, tales como álgebra, cálculo,

algebra lineal, teoría de números, teoría de grafos, etc. En lo que respecta a optimización, Sagepuede hacer todo lo que Maxima hace, puesto que Maxima es uno de los componentes de Sage.En adición, Sage posee amplias capacidades de trabajar con grafos, lo que lo hace ideal para laaplicacion de algoritmos de optimización de redes, como la ruta más corta y el árbol mínimo deexpansión, por mencionar algunos.El objetivo del proyecto Sage es muy claro, convertirse en una alternativa de software libre

para aplicaciones comerciales como Matlab, Mathematica, Maple, etc. Por lo que se puede ver, enpoco tiempo se ha avanzado un gran trecho hacia el logro de tal objetivo. En mi opinión, en unoscuantos años, Sage será la herramienta de uso mas generalizado entre la comunidad cientí�ca yacadémica en el mundo.Sage puede ser obtenido en la siguiente dirección:http://sagemath.org/

3.2.5. Octave

Octave es una herramienta que puede clasi�carse dentro de las aplicaciones de Cálculo Numé-rico. Su objetivo es crear una alternativa de software libre para Matlab y de hecho, actualmenteexiste un alto nivel de compatibilidad entre ambas, cercana al 99%, es decir que el código deMatlab puede ejecutarse casi sin modi�caciones en Octave. Sus fortalezas radican en la enormecapacidad de procesar grandes cantidades de datos a una grán velocidad de cálculo, así como

16


Figura 3.4.: Imagenes de Sage

17


Figura 3.5.: Imagenes de Octave

el manejo en forma natural de estructuras matriciales, lo cual la hace ideal para trabajar conalgoritmos de optimización, puesto que muchos de éstos se basan en cálculo matricial.Mas que una aplicación, tanto Matlab como Octave son mas bien un lenguaje de programación

y un entorno de desarrollo de aplicaciones para el cálculo cientí�co. Existe una grán cantidad depaquetes adicionales que pueden descargarse y que extienden las funcionalidades de Octave enáreas especí�cas. Existen paquetes especí�cos para el área de optimización, tanto lineal como nolineal.Quizá una de las mayores desventajas de Octave es la falta de una Interfase Gráfica de

Usuario o GUI por sus siglas en inglés. Aunque existen algunos proyectos que se han desarrolladoen forma independiente para subsanar esta debilidad, aún no existe una interfaz que llene en sutotalidad ese vacío, aunque ya se ha anunciado por parte de los desarrolladores del proyectoOctave que ya se está trabajando en una GUI que vendrá integrada en futuras versiones.Octave puede descargarse de la siguiente dirección:http://www.gnu.org/software/octave/

3.2.6. Scilab

Scilab es un software muy similar a Octave y que también pertenece a la categoría de softwarepara cálculo numérico. Aunque su compatibilidad con Matlab no es tan alta como Octave, puedeser considerado una alternativa. Al igual que Octave, Scilab basa su fortaleza en el manejo deobjetos matriciales en forma natural y simple. También puede considerarse un lenguaje y unentorno de programación para el desarrollo de aplicaciones complejas.Otra cosa que tienen en común Scilab y Octave es la amplia variedad de paquetes adicionales

para extender la funcionalidad básica hacia aplicaciones especí�cas. Scilab cuenta con un pa-quete (o Toolbox, como se denomina comunmente) desarrollado especí�camente para resolverproblemas en el campo de la optimización, tanto lineal como no linea.Scilab también incluye un programa sumamente interesante denominado XCos y que sirve

para modelar y simular sistemas dinámicos complejos. Aunque este tema está fuera del alcancede este documento, es importante mencionarlo porque es una alternativa al programa llamadoSimulink® que es un complemento de Matlab, aunque se adquiere por aparte. En estas aplica-

18


Figura 3.6.: Imagenes de Scilab

ciones, tanto XCos como Simulink es posible modelar, simular y analizar el comportamiento desistemas dinámicos cuyo análisis sería extremadamente difícil por la forma tradicional, es decir,utilizando herramientas matemáticas, ya que la complejidad de las relaciones es muy alta.Scilab es una aplicación desarrollada en Francia y es utilizada por muchas organizaciones

cientí�cas y académicas en Europa.Scilab puede descargarse en:http://www.scilab.org/

19

Parte II.

OPTIMIZACIÓN APLICADA

20

4. OPTIMIZACIÓN NO LINEAL NORESTRINGIDA EN UNA VARIABLE

La decisión de iniciar esta segunda parte con los modelos de optimización no lineal sin restric-ciones para una sola variable se basa en el hecho que este es un tema que generalmente se cubreen un curso introductorio de cálculo diferencial. La optimización (maximización o minimización)de funciones no lineales en una sola variable es una de las primeras aplicaciones de la derivadaque se aprende.Partiendo del hecho que se trata de un curso para ingenieros, es válido suponer que existe ya la

base de cálculo diferencial necesaria para entender los fundamentos teóricos del tema, razón porla cual, como se aclaró en la Introducción en estos apuntes no se cubre la teoría sino solamentela aplicación de los conceptos directamente con el uso de las herramientas computacionales. Elestudiante puede consultar cualquier libro de texto de cálculo para refrescar aquellos conceptosque considere necesarios antes de avanzar a la siguiente sección.

4.1. Desarrollo de un modelo de Optimización

Dicho lo anterior, la forma más directa de exponer el tema y más especí�camente, el procesode desarrollo del modelo es a través de un ejemplo:

Los barriles que se utilizan para almacenar petróleo tienen forma cilíndrica y una capaci- Ejemplo # 1dad de 160 litros. Hallar las dimensiones del cilindro para que el material empleado en suconstrucción sea mínimo.

Paso # 1: Entender el problema

Como se mencionó el la primera parte, es necesario estar seguro que se tiene claro el problema.Para eso, generalmente es recomendable realizar un diagrama de la situación bajo análisis:

La �gura muestra el envase cilíndrico y las dimensiones que lo de�nen, en este caso el diámetro(D) y la altura (H). Adicionalmente el enunciado del ejemplo indica que el volumen que debencontener los recipientes es de 160 litros. El material a utilizar es la super�cie total que ocupa elbarril, es decir, las 2 tapas superiores y el cilindro.

Paso # 2: Identi�car el Objetivo

En este caso el enunciado es muy claro respecto a que lo que se pretende es minimizar elmaterial para fabricar el barril, y en el paso anterior identi�camos que el material correspondeal área total del cilindro, por lo que el objetivo se puede expresar como: Minimizar el Area Totaldel Cilindro.

21

4. OPTIMIZACIÓN NO LINEAL NO RESTRINGIDA EN UNA VARIABLE

Paso # 3: Identi�car las Variables de Decisión

Las Variables de Decison (VD) son los parámetros del modelo que están bajo nuestro control yque podemos modi�car para lograr el objetivo. En este ejempo, las decisiones que debemos tomarcorresponden a el diámetro y la altura del cilindro. Puede pensarse que se trata de 2 variablesindependientes, pero en realidad ambas están relacionadas ya que el volumen total del cilindroya esta de�nido. El volumen y el área de un cilindro están dadas por las siguientes relaciones:

V = π ×(D2

)2×H ⇒ H = 4×V

π×D2

A = 2× π ×(D2

)2+ π ×D ×H

Paso # 4: Expresar el Objetivo como una función de las Variables de Decisión

Si expresamos el Area Total y hacemos la sustitución correspondiente como se indicó en elpaso anterior, obtenemos la función siguiente para el Area Total que queremos minimizar, enfunción de una sola variable, en este caso el diámetro (D), por lo que al resolver para D, solodebemos sustituír su valor en la expresión despejada para H en el paso anterior.

Paso # 5: Identi�car las Restricciones

En este problema particular, como se in�ere por el título del tema, por tratarse de un problemade optimizacion lineal no restringido, no existen restricciones. Es posible que se pueda pensar queel volumen del cilindro es una restricción, pero no sería correcto. Una restricción generalmente sere�ere a ciertas condiciones que deben cumplir las variables de decision, por ejemplo, si en esteproblema nos indicaran que los barriles no deben exceder una altura de 1 metro, o si nos indicaranque el diámetro no debe exceder 70 cms nos estarían imponiendo restricciones al modelo. Estose hará mas claro en el siguiente capítulo.

Paso # 6: Expresar las Restricciones como relaciones de las Variables de Decisión

No aplica en este problema.

Paso # 7: Colocar el modelo en una forma canónica o estándar

En el caso de la optimización no lineal de una variable sin restricciones, basta con expresar lafunción matemática de una variable e indicar cual es el objetivo, ya sea maximizar o minimizar,por lo que quedaría tal y como se representa en el paso # 3.

4.2. Optimización No Lineal en Maxima

Ahora vamos a introducirnos en el uso de las aplicaciones especí�cas y para este problemaen particular vamos a utilizar Maxima. Este no es un tutorial introductorio de Máxima, ya queexiste un grán número de ellos disponibles en internet para ser descargados y utilizados paraaprender los primeros pasos. En este curso se proporcionan algunos de ellos a los estudiantes. Aliniciar Maxima, nos encontramos con una pantalla como la mostrada abajo:

22


Al iniciar a escribir algo, inmediatamente aparece el �prompt� del programa, seguido por cual-quier cosa que tecleemos. Es importante recordar que para ejecutar una instrucción en Maxima,debemos presionar simultáneamente las teclas

[SHIFT]+[ENTER]

En la siguiente pantalla se presenta el procedimiento, con sus respectivas instrucciones sobrecada paso:

Ahora, sería interesante tener una idea de la forma de la grá�ca en un intervalo de�nido,para poder intuír donde podria encontrarse el mínimo que buscamos. Para esto, Maxima poseeexcelentes funcionalidades de gra�cación y en forma sumamente simple, como se muestra acontinuación:

23


Como se puede observar en la grá�ca, el valor mínimo para esta función se encuentra cercadel valor de D=0.6, o sea, esperaríamos que el diámetro para el barril será aproximadamentede 60 cms. Sin embargo, esto es solo una aproximación a la solución exácta, la cual tambiénpodemos obtener por medio de Maxima. Como recordamos de nuestro curso básico de cálculodiferencial, para encontrar un punto de in�exión en una función contínua y derivable en unintervalo, simplemente necesitamos encontrar la primera derivada de la función, luego igualaresta primera derivada a 0 y resolver la ecuación respectiva. Como se expresó en la introducción, esposible que algunos de los estudiantes de este curso ya hayan olvidado sus técnicas de derivación eintegración y otros aspectos básicos del cálculo. No hay porque preocuparse, para esto, recurrimosa la tecnología y en este caso, a nuestras herramientas de software matemático. Hacer esteprocedimiento en Maxima es sumamente sencillo y puede hacerse en 2 pasos, como se muestra acontinuación:

24


De esta forma, obtenemos la respuesta exácta que buscamos, el diámetro del barril debe tener0.588 mts (58 cms) de diámetro. A partir de este valor, podemos encontrar el valor de la altura,sustituyendo D en la expresión para H en el paso # 3. Se deja esto al lector curioso, asi como unanálisis del resultado obtenido.Realizaremos un ejemplo más, aunque ya sin el detalle para cada uno de los pasos, solo para

que el estudiante tenga claro el proceso. El ejemplo a resolver es el siguiente:

Una ventana normanda tiene forma de rectángulo rematado por un semicírculo. Si el perí- Ejemplo # 2metro de la ventana es de 30 pies, encuentre las dimensiones de la ventana de modo queentre la cantidad más grande de luz. A continuación se presenta un diagrama que representala ventana, para tener una idea más clara del problema:

25


En este caso, necesitamos determinar las dimensiones de la ventana (Variables de Decision), osea la base (b) y la altura (h). La base también corresponde al diámetro del semicírculo superior dela ventana. Partiendo del hecho que conocemos la longitud total del perímetro podemos utilizarlapara reducir la cantidad de variables a una sola, de la siguiente forma. Para este ejemplo, vamosa poner a Maxima a realizar toda la manipulación algebráica de las expresiones, recuerden quees un Sistema Algebráico Computarizado!!

26


Podemos observar que el punto máximo se alcanza en un valor de b ligeramente mayor a 8.Ahora podemos proceder a encontrar el valor exácto:

4.3. Optimización No Lineal en Sage

Sage es una herramienta verdaderamente impresionante y con un futuro muy prometedor enel ámbito académico y cientí�co, como se mencionó en el capítulo anterior, por lo que vale lapena familiarizarse con ella. Vamos a resolver los mismos ejemplos de la sección anterior, soloque esta vez utilizando Sage.Sage es, como ya se mencionó, una de las herramientas más poderosas de cálculo cientí�co

disponibles en la actualidad, que integra a una amplia variedad de aplicaciones en un únicointerfase.Sage puede ejecutarse directamente en un navegador. Al iniciar la sesión, nos encontraremos

con la pantalla que se presenta a continuación:

27


Al seleccionar la opción �New Worksheet�, podemos crear una nueva hoja de trabajo, a laque deberemos dar un nombre. Una vez hecho esto, estamos ante un ambiente integrado detrabajo que nos permitirá hacer muchas cosas ya que integra la funcionalidad de muchas otrasherramientas en una sola, potenciada por la facilidad y claridad de un lenguaje de programacióncomo Python.

28


29


Ahora mostraremos el desarrollo del Ejemplo # 2 de una forma mas breve, sin incluír todo eldetalle del ejemplo anterior:

30


Como era de esperarse, los resultados son los mismos a los obtenidos por medio de Maxima. Enrealidad, Sage utiliza Maxima internamente para realizar la manipulación de objetos simbólicos,sin embargo, existen diferencias en los nombres de las instrucciones o funciones de un sistema aotro, por ejemplo, como vimos, en Maxima, la función para derivar es:

diff(expresión, variable)

mientras que en Sage, el mismo objetivo se logra utilizando la función siguiente:

derivative(expresión, variable)

Para el propósito especí�co de la optimización no lineal en una variable y sin restricciones,decidir la herramienta a utilizar entre Sage y Maxima es simplemente una cuestión de gustos opreferencias, aunque para otras aplicaciones mas so�sticadas en ciencia e ingeniería, Sage es unaherramienta mucho mas completa y poderosa.

4.3.1. Caso Especial

Existen algunos casos en los cuales los CAS (Computer Algebra Systems) no son capacesde resolver ecuaciones en forma simbólica. Esto es relativamente común y es necesario estarpreparado para afrontar estas situaciones. Vamos a demostrar como hacerlo con un ejemplo.

Dos puntos A, B se encuentran en la orilla de una playa recta, separados 6 km entre sí. Ejemplo # 3Un punto C esta frente a B a 3 km en el mar. Cuesta $400.00 tender 1 km de tubería enla playa y $500.00 en el mar. Determine la forma más económica de trazar la tubería desdeA hasta C . (No necesariamente debe pasar por B.) Como hemos dicho, siempre es buenovisualizar el problema utilizando algun tipo de ayuda como un diagrama. Veamos como se veríaesta situación diagramada:

31


De acuerdo a lo mostrado en el diagrama, la distancia total de tubería requerida es igual ala longitud de x mas la longitud de la hipotenusa del triángulo rectángulo que se forma por 6-xy 3 que son las distancias entre los puntos A, B y C. Conociendo lo anterior, es relativamentesencillo formar la función objetivo a optimizar, en este caso, a minimizar. Para esto, haremosuso de Sage, de la siguiente manera:

Resulta evidente por la grá�ca que el valor mínimo de la función se encuentra cerca de 2. Paraestar seguros, necesitamos seguir el procedimiento usual, primero derivamos la función objetivorespecto a x y luego resolvemos la primera derivada para x y eso debería darnos el valor mínimo.Veamos que sucede cuando lo hacemos en Sage:

32


¾Que sucede? Parece que la solución a la primera derivada es otra función de x en lugar de serun número real. Esto tiene una explicación simple, Sage no pudo resolver la ecuación en formasimbólica. Esto es algo relativamente común. Cuando se trabaja con expresiones algebraicas,algunos programas computarizados son incapaces de encontrar una solución en forma simbólicao lo que se conoce como Forma Cerrada1. Cuando esto sucede, no hay porque preocuparse, yaque siempre hay formas alternativas de encontrar los valores que buscamos. Para esto, el lectorseguramente recordará sus cursos de Métodos Numéricos en los cuales se utilizaban algoritmositerativos para resolver una gran cantidad de problemas matemáticos, desde la solución de ecua-ciones, pasando por la integración numérica hasta llegar a la solución de ecuaciones diferenciales yotras. Nuevamente, este material no cubre la teoría detrás de dichos algoritmos, pero sí podemoshacer uso de las herramientas informáticas disponibles.Para resolver este problema, lo que necesitamos es encontrar la solución (raíz) de una ecuación

no lineal de la forma f(x)=0. Para esto existen una serie de algoritmos numéricos como el métodode Newton o Newton Raphson. Afortunadamente, Sage nos permite usar estos métodos sin tenerque programarlos nosotros mismos.

Podemos ver que Sage encuentra fácilmente la solución en forma numérica, la cual se encuentracasi exáctamente en 2, ya que la pequeña diferencia es atribuída a un error de redondeo en elcálculo numérico.Sage nos ofrece casi siempre, mas de una forma de resolver los distintos problemas a los que

nos enfrentamos. En el caso del ejemplo en cuestión, existe una forma mas directa de encontrarel valor óptimo (mínimo, en este caso) de la función sin necesidad de recurrir al método de laprimera derivada. Para esto podemos utilizar una función especial de Sage directamente sobrela función objetivo como se ve a continuación:

Esta función es sumamente útil cuando se desea optimizar funciones no lineales en varias

1http://es.wikipedia.org/wiki/Forma_cerrada_(matemática)

33


variables, como se verá mas adelante, sin embargo, la limitación de este enfoque es que solopuede utilizarse para minimizar.

4.4. Ejercicios

34

5. OPTIMIZACIÓN LINEALRESTRINGIDA EN VARIAS VARIABLES

El tema de Optimización Lineal Restringida Multivariable es uno de los temas mas importantesde este curso, puesto que su aplicación no solo se limita al campo de la ingeniería sino que tambiénse extiende al mundo de los negocios y la administración.La optimización lineal restringida pertenece a un campo de la matemática aplicada que se

llama Programación Matemática y cuyo origen se remonta a la Segunda Guerra Mundial y enespecial a los aportes de George Dantzig1 a quien se le atribuye el desarrollo de la ProgramacionLineal la cual fue aplicada para resolver problemas reales de optimización en el uso de recursospara las operaciones militares.Como ya se dijo anteriormente, la Programación Lineal es un tema generalmente incluído en

los contenidos curriculares de algunas carreras de ingeniería pero lamentablemente no en todas.También se encuentra en contenidos de cursos de las carreras de Administración de Empresas,Economía, Agronomía y en algunos programas de postgrado, en cursos tales como Investigaciónde Operaciones o Métodos Cuantitativos para Administración.

5.1. Programación Lineal

La característica principal de la programación lineal es la condición que todas las variablesde decisión tanto en la función objetivo como en las restricciones tienen grado 1. Esto garantizala existencia de algoritmos de�nidos que pueden resolver estos problemas en forma directa. Elmás famoso y utilizado de estos algoritmos es el denominado Método Simplex2 que es el quecomunmente se enseña en un curso de Operaciones y que se basa en algebra matricial paraobtener los valores óptimos para las variables de decisión. Sin embargo, no es el único algoritmoexistente, ya que entre otros podemos mencionar el Algorítmo de Punto Interior3 que tambiéngoza de cierta popularidad.No entraremos en toda la teoría porque el estudiante puede revisar las referencias bibliográ-

�cas para profundizar en ella, por lo que vamos a demostrar el modelo de Programación Linealmediante un ejemplo, el cual estaremos desarrollando nuevamente siguiendo detalladamente elproceso de modelación que se usó en el capítulo anterior ya que en este caso si podremos aplicartodos los pasos en forma explícita.El ejemplo a desarrollar es el siguiente:

Una compañía posee dos minas: la mina A produce cada día 1 tonelada de hierro de alta Ejemplo # 3calidad, 3 toneladas de calidad media y 5 de baja calidad. La mina B produce cada día 2toneladas de cada una de las tres calidades. La compañía necesita al menos 80 toneladastotales de mineral de alta calidad, 160 toneladas totales de calidad media y 200 toneladastotales de baja calidad. Sabiendo que el coste diario de la operación es de 2000 euros encada mina, desarrollar un modelo de optimización para la operación de las minas.

1http://es.wikipedia.org/wiki/George_Dantzig2http://es.wikipedia.org/wiki/Metodo_simplex3http://en.wikipedia.org/wiki/Interior_point_method

35

5. OPTIMIZACIÓN LINEAL RESTRINGIDA EN VARIAS VARIABLES

Paso # 1: Entender el Problema

Nuevamente un aspecto fundamental antes de iniciar el proceso de modelado es la comprensiónde la situación a modelar. En los ejemplos y ejercicios contenidos en los libros de texto general-mente el enunciado de los problemas de�ne explícitamente el objetivo que se busca y cuales sonlas variables de decisión del modelo. En este caso, decidí en forma consciente no incluír dicha in-formación en el enunciado para que el estudiante vaya desarrollando la habilidad para identi�carcorrectamente lo que se necesita, basandose en la información proporcionada. Para este ejercicio,es conveniente representar el problema en forma matricial como se muestra a continuación:

Alta Calidad Calidad Media Baja Calidad Costo/Operación

Mina A 1 ton/dia 3 ton/dia 5 ton/dia 2000 ¿/díaMina B 2 ton/dia 2 ton/dia 2 ton/dia 2000 ¿/día

Requerimiento 80 ton 160 ton 200 tonEsta práctica de representar los problemas en forma matricial será de suma utilidad en en

desarrollo de modelos de programación lineal y en especial cuando se utilizan hojas electrónicaspara resolver este tipo de problemas.

Paso # 2: Identi�car el Objetivo

Como ya se dijo, un problema de optimización se reduce a una de dos alternativas, maximizaro minimizar algo. De�nir esto debe hacerse tomando como punto de partida la información queel caso proporciona. En este caso en particular, el enunciado nos habla de costos de operación yno menciona ingresos o ganancias, por lo que podemos inferir que el objetivo será minimizar elcosto total de operación de ambas minas.

Paso # 3:Identi�car las Variables de Decisión

Necesitamos de�nir cuales parámetros del modelo quedan bajo nuestro control, es decir, aque-llos que nosotros podemos cambiar y que van a incidir en el objetivo. Puesto que según lainformación proporcionada, el costo de operar las minas está expresado en Euros por día, porlo que al variar la cantidad de días que operamos cada mina, estaremos cambiando el valor delobjetivo planteado en el paso anterior. Puesto que podemos decidir operar cada mina una can-tidad distinta de días, la decision que debemos tomar es cuantos dias vamos a operar la mina Ay cuantos dias la mina B, para que el costo sea mínimo.

Paso # 4: Expresar la Función Objetivo

Con lo de�nido en los 2 pasos anteriores, es bastante sencillo expresar el objetivo en funciónde las variables de decisión. El costo total será igual a la cantidad de dias a operar cada minamultiplicado por el costo diario de operar cada una, expresandolo en forma matemática:

xA = Cantidad de dıas a operar Mina A

xB = Cantidad de dıas a operar Mina B

Min Costo Total = 2000xA + 2000xB

Paso # 5: Identi�car las Restricciones

Como se explicó con anterioridad, las restricciones provienen de limitaciones que nos impidenimplementar una solución ideal. En este ejemplo especi�co, puesto que nuestro objetivo es obtenerel costo mínimo, lo ideal sería tener un costo de 0, lo cual implica no operar las minas ni unsolo día. La razón por la cual no podemos tomar la decisión de no operar las minas es porque

36


debemos cumplir con los requerimientos mínimos de material (Hierro) que debemos producir. Eneste caso existen 3 requerimientos, uno por cada tipo de material, por lo que cada requerimientose convierte en una restricción de la siguiente forma:

Restricción # 1 = Hierro de Alta Calidad a Producir debe ser al menos 80 toneladas.

Restricción # 2 = Hierro de Calidad Media a Producir debe ser al menos 160 toneladas.

Restricción # 3 = Hierro de Baja Calidad a Producir debe ser al menos 200 toneladas.

Paso # 6: Expresar las Restricciones como relaciones de las V.D.

Ya en el paso anterior se adelantó bastante con este tema, lo que debemos hacer ahora essimplemente expresarlo en forma matemática. Para cumplir el requerimiento de cada uno de lostipos de material, es necesario operar las minas cierto numero de días, lo cual, combinado conel rendimiento de cada tipo de material en cada mina nos debe producir al menos lo requerido.Es muy importante de�nir la naturaleza de la restricción, si se trata de un límite máximo, unmínimo a cumplir o un valor exacto a obtener, para determinar si se trata de una igualdad (=)o una desigualdad (≤, ≥). En este caso, las 3 restricciones se re�eren a cantidades mínimas acumplir, por lo que el signo de la restricción será ≥.

R1 : 1xA + 2xB ≥ 80

R2 : 3xA + 2xB ≥ 160

R3 : 5xA + 2xB ≥ 200

Paso # 7: Colocar el modelo en una forma estándar o canónica.

La forma canónica o estándar para un modelo de programación lineal generalmente consisteen expresar lo que se pretente de la función objetivo (max/min) y todas las restricciones conun mismo sentido en cuanto a la dirección de la desigualdad. Generalmente, si el objetivo esmaximizar, todas las restricciones se expresan de la forma ≤y si el objetivo es minimizar, todaslas restricciones se expresan como ≥. Recordemos que podemos cambiar el sentido, o sea elsigno de una restricción multiplicando ambos lados de la desigualdad por -1. Adicionalmente,en la forma estándar se deben incluír otras restricciones que estén implícitas en el modelo, porejemplo, que las V.D. no pueden ser negativas, si deben ser enteras, binarias, etc. Para el ejemploen cuestión, esto quedaría de la siguiente forma:min CT = 2000xA + 2000xBs.a.

1xA + 2xB ≥ 80

3xA + 2xB ≥ 160

5xA + 2xB ≥ 200

xA, xB ≥ 0

Otra forma estándar comunmente utilizada para expresar un modelo de programación lineales la forma matricial, la cual es utilizada para la aplicación del método Simplex. Nuevamente,en este curso no vamos a explorar los algoritmos en detalle sino que vamos a utilizar el poder delas herramientas computacionales a nuestro alcance.

37


5.1.1. Programación Lineal en Maxima

El método o algoritmo más utilizado por las aplicaciones informáticas para resolver proble-mas de programación lineal es el Simplex. Maxima, adicionalmente a sus capacidades, posee laversatilidad de ser expandido por medio de módulos adicionales, algunos de ellos ya vienen pordefecto en la instalación original y otros pueden ser desarrollados por el usuario para �nes másespeci�cos. Uno de los módulos que Maxima ya trae incluído es el del método Simplex, el cualcombinado con las capacidades algebráicas de Maxima hacen sumamente sencilla la soluciónde los modelos de programación lineal ya que el modelo puede expresarse tal y como lo hemosexpresado en el paso # 7 de la sección anterior. Esto funciona bastante bien para modelos pe-queños, con pocas variables y restricciones, sin embargo, cuando se trata de modelos grandescon muchas variables y restricciones, la solución con esta herramienta puede volverse engorrosa,por lo que para problemas grandes, es mas recomendable utilizar herramientas que utilizan lanotación matricial.A continuación mostraremos la solución al ejemplo # 3, detallando paso a paso el proceso de

solución:

Como puede observarse, Maxima proporciona la solución al modelo en forma rápida, sencillay exácta.El ejemplo anterior correspondía a un problema de minimización, por lo que a continuación

vamos a presentar un ejemplo de maximización para completar esta sección.

Un fabricante de cemento produce dos tipos de cemento, a saber en gránulos y polvo. Él no Ejemplo # 4puede hacer más de 1600 bolsas un día debido a una escasez de vehículos para transportarel cemento fuera de la planta. Un contrato de ventas establece que él debe producir 500

38


bolsas al dia de cemento en polvo. Debido a restricciones del proceso, se requiere el dobledel tiempo para producir una bolsa de cemento granulado en relación al tiempo requeridopor el cemento en polvo. Una bolsa de cemento en polvo consume para su fabricación0.24 minutos/bolsa y la planta opera 8 horas al día. Su ganancia es $4 por bolsa para elcemento granulado y $3 por bolsa para el cemento en polvo. Nuevamente, en este ejemplo seomite la parte del enunciado que indica explícitamente el objetivo y las variables de decisión paradesarrollar la habilidad en el estudiante de identi�carlas basado en la información proporcionada.En los verdaderos problemas, aquellos que surgen en la vida real durante el ejercicio profesional,no existen enunciados que nos digan que hacer, es algo que debemos descubrir por nosotrosmismos.

Paso # 1: Entender el problema.

Nuevamente, es conveniente tratar de representar en forma matricial la información que se nosproporciona. El pensamiento multidimensional es una de las formas mas e�caces en la soluciónde problemas complejos.

Producto Tiempo Req. Ganancia Prod. mín Prod. max Tiempo Disp.

Cem en Polvo 0.24 min/b $3/b 500 b/día

Cem Granul 0.48 min/b $4/b -

Total 1600 b/día 8 h (480 m)

Paso # 2: Identi�car el Objetivo.

Basado en la información proporcionada en el enunciado, donde se menciona la ganancia porbolsa, podemos inferir que el objetivo perseguido es el de maximizar la ganancia total obtenida.

Paso # 3: Identi�car las Variables de Decisión.

Si lo que buscamos es maximizar la ganancia total, debemos de�nr cuales son las variables quedebemos manipular para modi�car la ganancia. Es fácil deducir que la ganancia total dependeráde la cantidad de bolsas de cada uno de los dos tipos de cemento que se fabrican por día.

x1 = Cantidad de Bolsas de Cemento en Polvo/dıa

x2 = Cantidad de Bolsas de Cemento Granulado/dıa

Paso # 4: Expresar la Función Objetivos.

Ganancia Total = ($3/bolsa) x1 + ($4/bolsa) x2

Es muy importante siempre chequear la consistencia dimensional tanto de la función objetivocomo de las restricciones. En este caso, las variables están expresadas en bolsas y los coe�cientesestán expresados en dinero/bolsa por lo que al multiplicar ambos se obtiene solamente dinero,lo cual permite sumar ambos términos de la función y nos dá la ganancia total en dinero.

Paso # 5: Identi�car las Restricciones.

Si pudiesemos producir una cantidad in�nita de bolsas de cada tipo de producto y venderlastodas, obtendríamos una ganancia in�nita. Obviamente hay algo que nos impide hacer esto.Primero, aún cuando pudiesemos producir todas las bolsas de cemento que quisieramos, existeuna cantidad máxima que podemos transportar (y por ende vender) cada dia.

R1 = Cantidad Maxima De Bolsas Totales/dıa = 1600

39


Segundo, debemos cumplir con una cantidad mínima de bolsas de cemento en polvo por dia.

R2 = Cantidad Mınima Bolsas Cemento en Polvo = 500

Tercero, producir cada bolsa requiere de una cantidad de tiempo y disponemos de un de-terminado tiempo de producción total por cada dia. Aunque en el enunciado no se menciona,suponemos que ambos tipos de cemento se producen utilizando la misma línea de producciónpor lo que la suma total del tiempo requerido para fabricar ambos productos no puede excederel tiempo disponible.

R3 = Tiempo Disponible/dıa = 480min

Paso # 6: Expresar las Restricciones en relación a las V.D.

R1 : x1 + x2 ≤ 1600

R2 : x1 ≥ 500

R3 : 0.24x1 + 0.48x2 ≤ 480

Paso # 7: Colocar el modelo en la forma estándar.

max GT = 3x1 + 4x2

s.a.

x1 + x2 ≤ 1600

−x1 ≤ −500

0.24x1 + 0.48x2 ≤ 480

x1, x2 ≥ 0

Ahora, vamos a resolver el modelo utilizando Maxima. Hay que recordar que al iniciar elprograma, debemos cargar el módulo Simplex.

La solución óptima es, entonces, producir 1200 bolsas diarias de cemento en polvo y 400bolsas de cemento granulado, lo que produce una ganancia total por día de $5200. Es importante

40


recordar que, de acuerdo al signi�cado de optimalidad, ninguna otra combinación producirá unaganancia mayor a 5200. Es posible, sin embargo, que existan soluciones óptimas alternativas y queproduzcan la misma ganancia total con una combinación diferente. Si se buscara incrementar laganancia, se deberían cambiar las condiciones bajo las cuales opera el modelo. Existe una formade estimar el efecto que ciertos cambios en las condiciones del modelo tendrán en la soluciónóptima, esto se conoce como Análisis de Sensibilidad o Análisis Post Optimo.

5.1.2. Programación Lineal en OpenO�ce/LibreO�ce Calc

El uso de hojas electrónicas para modelar y resolver problemas de optimización se ha gene-ralizado en los últimos años. A continuación vamos a utilizar OpenO�ce Calc para resolver losdos ejemplos anteriores de programación lineal. Es razonable asumir que los estudiantes ya estanfamiliarizados con el uso de hojas electrónicas para otras aplicaciones, en especial MS Excel® ydado que existe un alto grado de similitud y compatibilidad entre éste y Calc, el proceso de so-lución debe ser bastante sencillo. Obviaremos los pasos del proceso de solución porque ya fueronrealizados en la sección anterior.Existe una diferencia signi�cativa entre una hoja electrónica y las aplicaciones previamente

utilizadas (Maxima y Sage): las hojas electrónicas no pueden manipular objetos algebráicos, sinoque solamente son capaces de trabajar con cantidades por lo que utilizan algoritmos numéricospara resolver esta clase de problemas. Adicionalmente, dada estructura matricial de las hojaselectrónicas, es mas conveniente representar el modelo en forma de una matriz de coe�cientes.

En la imagen anterior se puede observar los datos del modelo. Para este paso, solamente senecesita ingresar los valores tal y como aparecen en la imagen, pero esto es solamente la primeraparte del desarrollo del modelo ya que se deberán crear las fórmulas necesarias para relacionarlas variables y los coe�cientes tal y como se muestra a continuación:

41


42


Como puede verse en las imagenes anteriores, se realiza la sumatoria de los productos de cadacoe�ciente por el valor de las variables de decisión, tanto en la función objetivo como en lasrestricciones. En este ejemplo esto se realizó uno a uno, mas adelante se verá que esto puederealizarse copiando las fórmulas hacia abajo y dejando las referencias �jas a los valores de lasV.D.Una vez completados los pasos anteriores, el modelo en la hoja electrónica está listo y podemos

proceder a la solución del mismo utilizando la opción de solver.

43


Como se esperaba, la solución obtenida es la misma a la obtenida en la sección anterior pormedio de Maxima. Es interesante notar que en la hoja electrónica podemos ver los resultadospara cada una de las variables de decisión, la función objetivo y también el valor de cada una delas restricciones. Así podemos observar que las primeras dos restricciones se cumplen a cabalidadmientras que en la tercera restricción el valor del lado derecho es excedido, lo cual es válido dadoque la restricción es del tipo ≥.Ahora procederemos a resolver el ejemplo # 4 de la producción de cemento. Vamos a hacerlo

44


de una forma mas detallada, para que pueda observarse el procedimiento a seguir en la hojaelectrónica:

Nuevamente, el modelo se plantea exáctamente igual que en el ejemplo anterior. Algo impor-tante de mencionar es la escogencia de valores iniciales para las variables de decisión. En realidadpuede colocarse cualquier valor, sin embargo, es conveniente colocar un valor distinto de cero co-mo valor inicial ya que dado que Calc utiliza un algoritmo numérico para resolver el modelo, eluso de 0 puede ocasionar algún error durante los cálculos.

Seleccionamos la opción �SOLVER� y en el cuadro de diálogo de�nimos la celda objetivo, elobjetivo, que en este caso es maximización, las variables de decision y las restricciones como semuestra a continuación:

45


Ahora, haciendo click en �Options� nos aseguramos que esté marcada la opción que dice �Assu-me variables as non-negative� que básicamente se re�ere a la restricción de no negatividad paralas variables de decisión:

Aceptamos haciendo click en OK y luego hacemos click en �Solve�. Calc nos da un mensajeindicando que se ha tenido éxito en la búsqueda de la solución:

Finalmente hacemos click en la opción de guardar el resultado �Keep Result� y ya podemosver la solución obtenida, que es la misma que ya conocíamos por medio de Maxima.

46


5.1.3. Programación Lineal en Sage

Una de las enormes ventajas de Sage es que cuenta con una gran cantidad de módulos especí-�cos para el cálculo cientí�co y la programación lineal no es la excepción. Sage cuenta con unaclase de objetos especial llamada MixedIntegerLinearProgram, que corresponde a un modelo deProgramación Lineal Entera Mixta o MILP por sus siglas en inglés. Para entender el conceptode objeto es necesario remitirse a la literatura sobre programación orientada a objetos, se reco-mienda consultar la literatura de programación orientada a objetos con Python. En este caso noslimitaremos a indicar que en Python, un objeto, como en cualquier lenguaje de este tipo, tienemétodos y atributos. En el caso de un objeto de tipo MixedIntegerLinearProgram se tienen lossiguientes atributos:

Variables de Decisión

Función Objetivo

Restricciones

Por lo que el procedimiento para resolver un problema de programación lineal en Sage es elsiguiente:

1. Crear el objeto tipo MixedIntegerLinearProgram y asignarle un nombre (cualquier nombrede variable)

2. Asignarle los atributos anteriormente mencionados

3. Llamar el método para resolver el objeto

Esto se aclarará de una mejor forma a través de un ejemplo. Vamos a resolver en Sage el mismoproblema que se resolvió tanto en Maxima como en OpenO�ce.

47


Como puede verse, los resultados obtenidos son exáctamente los mismos que para los anterioresprogramas, aunque en el caso de una de las variables de decisión, Sage proporciona una respuestaque varía en 6*10−14, que es una cantidad muy poco signi�cativa, esto debido a la forma comoSage maneja el aritmética de punto �otante pero la explicación de esta diferencia está fuera delalcance de estas notas.Los modelos de programación lineal se adaptan a una gran variedad de problemas en el mundo

de la ingeniería y los negocios. En la siguiente sección se presenta una de las áreas de aplicaciónde la optimización lineal de mayor interés en este curso: los modelos de redes.

5.2. Modelos de Redes

Los modelos de redes aparecen en muchas aplicaciones de ciencias e ingeniería. Existe unaenorme variedad de problemas y situaciones que pueden representarse en forma de una red.El estudio de las redes pertenece a otro campo de las matemáticas que lamentablemente nose encuentra en todos los programas académicos de ingeniería: Matemáticas Discretas4. LasMatemáticas Discretas comprenden un grán número de tópicos uno de los cuales es la Teoría deGrafos5. Por medio de los grafos, es posible modelar una grán cantidad de situaciones tales como:redes de carreteras, redes de distribución de servicios públicos (agua, electricidad, teléfono, etc.),redes de computadoras, relaciones entre personas, etc. Una vez se ha modelado el asunto bajoestudio, puede utilizarse los algoritmos de redes para encontrar soluciones a problemas comunes,

4http://es.wikipedia.org/wiki/Matemáticas_discretas5http://es.wikipedia.org/wiki/Teoría_de_grafos

48


Figura 5.1.: Ejemplos de Redes

tal como el de encontrar la ruta mas corta que conecta a dos nodos o el �ujo máximo que puedemoverse por toda una red.Una de las características importantes de las redes es la facilidad de representarse en forma

matricial, lo cual permite que puedan ser manipuladas y procesadas matemáticamente. Por elcarácter matricial, la herramienta que mejor se presta al desarrollo de los algoritmos de redes, esla hoja electrónica. Sin embargo, existen ciertos algoritmos que requieren un desarrollo a nivel deprogramación, en cuyo caso, es mejor recurrir a herramientas que ya incluyen dichos algoritmosprede�nidos, como es el caso de Sage.Aunque existe una grán cantidad de métodos y algoritmos para redes, en este curso vamos a

enfocarnos solo en los que mayor aplicación tienen en el campo de la ingeniería. Los algoritmosa cubrir en estas notas son los siguientes:

Algoritmo de Transporte

Algoritmo de Asignación

Algoritmo de Ruta Más Corta

Algoritmo de Flujo Máximo

Algoritmo de Arbol Mínimo de Expansión

Antes de iniciar con el desarrollo de cada uno de los métodos, es importante recordarle a losestudiantes que estas notas no cubren la teoría, sin embargo, es necesario conocer y entenderciertos conceptos básicos sobre redes, por lo que se deja al estudiante buscar en el material dereferencia u otras fuentes, los siguientes términos:

Grafo

� Dirigido

� No Dirigido

49


Figura 5.2.: Tipos de Grafos

Figura 5.3.: Ejemplo de una red con pesos (distancia) y sus respectivas matrices

� Conexo

� No Conexo

� Fuertemente Conexo

� Simple

� Multigrafo

Vértice o Nodo

Arista o Arco

Camino o Ruta

Arbol

Matriz de Adyacencia

Matriz de Pesos (Distancias, Costos, etc.)

5.2.1. Modelo de Transporte

El problema de Transporte es uno de los modelos más comunes en el tema de optimizaciónrelacionada con redes. Es un problema típico en los cursos de Operaciones en muchos cursos depre y post grado en distintos programas académicos. También es uno de los más sencillos deresolver por medio de una herramienta informática, en especial las hojas electrónicas, ya que suestructura se presta de forma conveniente para dicho propósito.

50


Nuevamente, vamos a desarrollar un ejemplo a través del cual se desarrollará el modelo y serealizará la solución del mismo.

La Empresa transportista ABC posee varios camiones usados para acarrear piedra molida Ejemplo # 5para proyectos de carreteras en el municipio. El contratista de carreteras para quien trabajale ha dado el programa de la semana siguiente. Encontrar el plan óptimo del transporte.A continuación se muestran las tablas con los datos de requerimientos y costos por carga:

En realidad, el modelo de transporte es un caso especial de un problema de programaciónlineal, por lo que su solución podría muy bien seguir la secuencia presentada con anterioridad.Aunque no vamos a resolver este problema utilizando el modelo general de programación lineal,es interesante analizarlo desde esa perspectiva. Por tratarse de un problema con 3 fuentes deoferta y 3 puntos de demanda, tendríamos un total de 9 variables de decisión. Además, por cadapunto de demanda tendríamos una restricción para cubrir el requerimiento y por cada punto deoferta tendríamos una restricción para no exceder la disponibilidad, lo que hace un total de 6restricciones. Se deja como ejercicio al estudiante plantear este modelo en la forma estándar deprogramación lineal.A continuación se presenta una representación de este ejemplo utilizando una notación de

redes:

El grafo anterior, de acuerdo a la taxonomía de grafos que puede consultarse en la teoría,corresponde a un grafo dirigido, bipartito, con el respectivo peso (en este caso: costo) de losarcos claramente indicado.A partir del grafo, podemos construír la respectiva representación matricial para este problema.

Por tratarse de un grafo bipartito, es decir, podemos separar los nodos en dos grupos y los arcosvan de un grupo hacia el otro, la matriz tendrá como �las, los nodos de oferta y como columnaslos nodos de demanda. Para representar y resolver este problema, utilizaremos la hoja electrónicaque ya hemos presentado en secciones anteriores: Calc.

51


En la imagen de arriba, puede observarse el problema representado en forma matricial en lahoja electrónica. En los problemas de transporte, se acostumbra representar la oferta como �lasy la demanda como columnas, los totales de la oferta y la demanda se colocan al �nal de cada�la/columna y los costos de transporte entre cada punto de oferta y cada punto de demanda secolocan en las celdas de la matriz.El primer punto a validar en un problema de transporte es el balance entre la oferta y la

demanda. Para poder resolver correctamente el problema, debemos asegurarnos que la oferta seaigual a la demanda, o sea, que ambas estén balanceadas. Si esto no se cumple en las condicionesiniciales del problema, es necesario balancearlo, agregando puntos de oferta o demanda ��cticios�(es decir, nodos en el grafo o �las/columnas en la matriz).La forma de proceder es la siguiente:

Oferta > Demanda: Se agrega una columna �cticia. Esta columna tendrá una demandatotal que será igual a

∑Oferta−

∑Demanda

Oferta < Demanda: Se agrega una �la �cticia. Esta �la tendrá una oferta total que seráigual a

∑Demanda−

∑Oferta

En ambos casos, los costos asociados a la �la o columna serán igual a cero.En este ejemplo,

∑Demanda = 175

∑Oferta = 145por lo que la diferencia es de 30

cargas semanales. Se deberá agregar una �la de oferta �cticia para compensar la diferencia.Una vez balanceado el modelo, es necesario crear otra matriz a la que llamaremos Matriz Solu-

ción que será la que contendrá nuestras variables de decisión y donde obtendremos la distribuciónóptima del problema de transporte. Al igual que hicimos con el modelo de programación linealen Calc, es necesario asignar un valor inicial a las variables de decisión, por lo que utilizaremos1. Los totales de �las y columnas deben ser fórmulas que contienen la sumatoria de la respectiva�la/columna, tal y como se muestra a continuación:

52


Ahora estamos listos para de�nir nuestra función de costo total, que estará integrada por lasumatoria de multiplicar cada celda de costo por cada celda conteniendo la variable de decisión.Expresando esto en forma matemática tenemos la siguiente expresión:min Costo Total =

∑∑(ci,j × xi,j)

En la hoja electrónica, existe una función que permite realizar esta operación entre 2 o másmatrices, es decir, computar el producto de cada pareja de celdas y luego sumarlo. Esta funciónse llama =SUMPRODUCT() y está disponible tanto el Calc como en Excel.

La celda conteniendo este resultado será nuestra celda objetivo en el modelo al ingresarlo alsolver. Ahora estamos listos para de�nir el modelo en Solver. Las variables de decisión será lamatriz conteniendo los �1�. En el caso de las restricciones, si plantearamos el modelo en la formatradicional de un problema de programación lineal, tendríamos una restricción para cada puntode oferta y una para cada punto de demanda (incluyendo las �cticias) por lo que si n es el númerode �las y m es el número de columnas, el total de restricciones esta dado por n + m.

En el caso de la solución por medio de la hoja electrónica, Solver nos permite de�nir en unasola restricción, un conjunto de restricciones que tienen el mismo signo. En el caso de la oferta,sabemos que no podemos exceder la cantidad disponible, por lo que todas las restricciones deoferta son del tipo ≤. En el caso de la demanda, la condición es satisfacer al menos la demandaen cada punto, por lo que todas las restricciones de demanda son del tipo ≥.

53


En la �gura anterior se pueden observar los detalles de la de�nición del modelo en Solver.Buscamos minimizar la celda objetivo que contiene la suma producto de la matriz de costos y lamatriz de decisión. Las celdas cambiantes son las variables de decisión y tenemos 2 restricciones,una para la oferta y una para la demanda. En las opciones de Solver, solo debemos asegurarnosque tengamos marcada la opción para que asuma que las variables son no negativas, o sea, laya conocida restricción de no negatividad. Solver nos proporciona la solución correcta al modelocomo se muestra en la siguiente imagen:

La solución presentada por Solver nos permite saber exáctamente cuanto debemos mover decada punto de oferta a cada punto de demanda, sin infringir ninguna restricción y alcanzando elcosto total más bajo posible (de lo contrario no sería óptimo). Cuando se trata de un problemaque inicialmente no se encontraba balanceado, habrá cierta cantidad que quedará asignada a unpunto de oferta/demanda �cticia. En este caso, hay 30 cargas semanales que no van a poder ser

54


cubiertas con la capacidad actual, lo que implica no satisfacer completamente la demanda de A,pero podemos tener la certeza que lo que tenemos disponible está siendo distribuído al menorcosto posible. Es posible que existan soluciones óptimas alternas, es decir, una forma diferentede distribuír la oferta entre la demanda, sin embargo el costo total será el mismo.A continuación se muestra la solución en forma de grafo, mostrando en cada arco la cantidad

que debe moverse de cada nodo oferta a los de demanda:

Este es un ejemplo de un problema típico de transporte, sin embargo, existen muchos casosque, sin ser problemas relacionados con transporte, pueden modelarse y resolverse utilizandoeste algoritmo. El algoritmo de transporte usualmente busca la minimización del costo totalde transporte (tiempo, dinero, distancia, etc.), sin embargo, también es posible utilizarlo parael caso en que se desee maximizar algo, ya sea utilidades, ingresos, ventas, etc. El proceso desolución será exáctamente el mismo, solo asegurándonos de seleccionar correctamente en Solverel objetivo que estamos buscando.

5.2.2. Modelo de Asignación

Así como el modelo de transporte representa un caso especial del modelo general de progra-mación lineal, existe un tipo de problemas que puede verse como un caso especial del modelode transporte, esto es el Modelo de Asignación. El problema de asignación consiste en asignaruna serie de trabajos, tareas, actividades, etc. a un grupo de personas, máquinas, lugares, etc.de forma que se pueda optimizar el resultado de dicha asignación.La representación grá�ca de este tipo de problema es igual al modelo de transporte, es decir,

se trata de un grafo bipartito dirigido, donde cada nodo de un lado del grafo está conectado contodos los nodos del lado opuesto. La única diferencia existente entre ambos modelos es que enla asignación, existe una relación biunívoca en la solución �nal al modelo, de tal forma que unnodo del lado de la oferta solo puede ser asignado a un nodo del lado de la demanda, ya que seentiende que cada nodo tiene una oferta implícita de 1 unidad.Nuevamente, la mejor forma de presentar el modelo y la forma de solución es a través de un

ejemplo, por lo que vamos a proceder a su desarrollo:

Una empresa que está desarrollando proyectos de construcción de carreteras en 4 ubicaciones Ejemplo # 6diferentes necesita asignar a cada proyecto un ingeniero. La empresa posee o�cinas en 5ciudades diferentes que se encuentran cada una a cierta distancia de cada uno de losproyectos. Cada ingeniero deberá desplazarse una vez por día entre la ciudad y el proyectoutilizando para esto un vehículo de la compañía. Los datos de las distancias entre las ciudadesy los proyectos, en Km se presentan a continuación:

55


En principio, este parece un problema bastante sencillo de resolver y de hecho puede que lo sea.Existen ciertos problemas de asignación que pueden ser resueltos a simple vista. Sin embargo,un enfoque empírico no garantiza encontrar una solución óptima y esto se complica mientrasmas grande es la cantidad de variables involucradas, o sea, mientras mas grande sea la matrizde costos/distancias. Existe un método simpli�cado para resolver en forma manual un problemade asignación, denominado el Método Húngaro6. Sin embargo, en estas notas nos estaremoslimitando a la solución por medio de computadora.Nuevamente, el primer punto de veri�cación para este problema es que la oferta y la demanda

se encuentren balanceadas. Como se mencionó anteriormente, en un problema de asignación laoferta y la demanda de cada nodo es igual a una unidad, lo que signi�ca que para que el problemaesté balanceado, la matriz debe ser cuadrada.El ejemplo anterior consta de 5 ciudades (ingenieros) y 4 proyectos, lo que implica que uno de

los ingenieros no será asignado a ningún proyecto, sin embargo, es necesario balancear la matrizagregando una columna adicional (demanda) para hacer la matriz cuadrada. Al igual que en elmodelo de transporte, el costo (distancia) para cada celda en esta columna sera igual a 0.A continuación se muestra el ejemplo modelado en Calc:

Es importante recordar que para la matriz de asignación (o matriz solución) los valores de lasuma de �las y columnas debe ser una formula, no un valor. También, como se ve en la �gura, lacelda D20 contiene una formula =SUMPRODUCT() para calcular el resultado de la sumatoriadel producto individual de las celdas de ambas matrices. Ahora veamos el planteamiento delmodelo en Solver:

6http://es.wikipedia.org/wiki/Algoritmo_húngaro

56


Podemos ver la celda objetivo, que es la que contiene la suma producto de las matrices, tambiénel objetivo que es minimizar dicha celda, las variables de decisión (celdas cambiantes) que sonlas de la matriz solución que contienen los �1�. La principal diferencia respecto al modelo detransporte se observa al de�nir las restricciones. De�nimos 2 restricciones, una para la columnaque contiene las sumatorias de �las y otra para la �la que contiene las sumatorias de columnas,sin embargo, a diferencia de transporte, aquí igualamos ambas restricciones a 1, lo que quieredecir que Solver deberá hacer que solamente una celda por �la y una celda por columna seandistintas de cero e igual a uno. Las opciones son las mismas que en el modelo de transporte:

La solución al modelo se muestra a continuación:

Como se observa en la matriz de asignación, en la solución óptima, el ingeniero de la ciudad4 es quien queda asignado al proyecto �cticio, es decir que en la práctica, será el único que noquede asignado a un proyecto. Los otros 4 ingenieros quedan asignados a un proyecto de talforma que se minimiza la distancia total que deben recorrer entre las ciudades y los proyectos,que será de 240 kilómetros (o 480 si tomamos el viaje redondo) asumiendo que cada ingenierovisita una vez por día el proyecto.

57


Figura 5.4.: Ruta Mas Corta

5.2.3. Modelo de Ruta Más Corta

El problema de la ruta más corta es quizá uno de los que mas interés despierta debido asus obvias aplicaciones. Existen varios algoritmos para resolver dicho problema, de los cuales elmás conocido es el Algoritmo de Dijkstra.7El objetivo del algoritmo también es bastante obvio:encontrar el camino más corto entre dos nodos cualesquiera en una red que puede ser dirigida ono dirigida. La �gura 5.4 muestra un ejemplo de una red dirigida donde se trata de encontrarel camino o la ruta más corta entre el nodo 1 y el nodo 9. De la de�nición de camino o ruta,sabemos que es una secuencia de arcos y nodos intermedios que conectan dos nodos en una red.En este modelo, nuevamente es muy útil el poder representar la red en forma matricial. Para

tal propósito, se coloca cada uno de los nodos como �las y como columnas, por lo que siemprese obtiene una matriz cuadrada. Cada elemento de la matriz, que es una intersección entre una�la y una columna representa el arco que conecta ambos nodos. En este modelo, será necesariogenerar 3 matrices para representar nuestro problema:

Matriz de Adyacencia: La matriz se compone de 0's y 1's, donde un 1 indica que existeun arco conectando directamente 2 nodos, es decir, ambos nodos son adyacentes. Si elgrafo es no dirigido, es decir, los arcos no tienen un sentido de�nido sino que los nodos seconectan en ambos sentidos, la matriz de adyacencia será simétrica respecto a su diagonalprincipal. En un grafo dirigido los arcos tienen una dirección especí�ca, por lo que la matrizde adyacencia no será simétrica sino que tendrá un 1 en el sentido del arco y un 0 en elsentido contrario.

Matriz de Distancias: La matriz de distancia se obtiene simplemente sustituyendo los ele-mentos iguales a 1 en la matriz de adyacencia, por la respectiva distancia para dicho arco.Al igual que la matriz de adyacencia, en un grafo dirigido esta matriz será simétrica respectoa la diagonal principal.

Matriz Solución: Si se representara el problema de ruta mas corta como un problemade programación lineal, el número de variables de decisión de tal problema sería igual alcuadrado del número de nodos en la red. La matriz de decisión tiene las mismas dimensionesque las dos matrices anteriores y una vez resuelto el modelo, tendrá un 1 si el arco queconecta al nodo �la con el nodo columna es parte de la ruta mas corta, de lo contrario talelemento será igual a 0.

Vamos a realizar un ejemplo para la solución del modelo de ruta más corta:

Encontrar la ruta más corta entre los nodos 1 y 6 en el modelo de red representado por la Ejemplo # 7

7http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra

58


�gura que se muestra a continuación: La red puede representar cualquier cosa, la distanciaentre distintos puntos, la duración en tiempo de una serie de actividades en un proceso o proyecto,etc.

En este ejemplo, puede observarse que se trata de un grafo no dirigido, ya que los arcos notienen un sentido de�nido, por lo que podemos asumir que es posible moverse en ambos sentidos.Vamos a representar el modelo en forma de las tres matrices que se mencionaron anteriormente:

Hasta este momento, todo lo que se ha ingresado al modelo en la hoja electrónica son solamentedatos, sin fórmulas de cálculo . Como se observa, la matriz de decisión (solución) está compuestade 1's que son las variables de decisión que la hoja electrónica calculará al momento de laoptimización por lo que en la solución óptima, solo algunas de esas variables tendrán un valorde 1 y el resto serán 0.Para completar el modelo, vamos a ingresar algunas fórmulas de cálculo que necesitamos para

ingresarlo a Solver para ser resuelto. El primer cálculo que necesitamos hacer es el de la distanciatotal, que no es mas que el resultado de multiplicar la matriz de distancias por la matriz dedecisión, elemento por elemento. Como ya sabemos, esto puede hacerse por medio de la función+SUMPRODUCT() como se muestra a continuación:

59


Luego, tenemos que realizar varios cálculos en la matriz solución. Vamos a calcular la sumade cada �la y cada columna de la siguiente forma:

Como siguiente paso, vamos a colocar en la parte de abajo de la matriz solución, una �lacalculada, que es el resultado de la diferencia entre el total de �la y el total de columna. Porejemplo, debajo de la columna 1 colocamos una fórmula para calcular la diferencia entre la sumade la �la 1 menos la columna 1. Es importante que el orden sea siempre

∑fila −

∑columna.

Por tratarse de una matriz cuadrada con el mismo número de �las y de columnas y dado quecomo valores iniciales ingresamos 1's en todas las celdas, esta diferencia siempre va a dar 0, taly como se muestra a continuación:

60


Finalmente, vamos a agregar una última �la abajo de la que acabamos de ingresar, dondevamos a identi�car los 2 nodos entre los cuales vamos a calcular la Ruta Mas Corta. Para esto,colocamos un valor de 1 en el nodo de inicio y un -1 en el nodo de llegada, dejando en 0 todoslos demás, tal y como se muestra a continuación:

Ahora, estamos listos para ingresar nuestro modelo a Solver para encontrar la solución. Aligual que en cualquier problema de programación lineal, tenemos que de�nir la celda objetivo,las variables de decisión y las restricciones, lo cual en nuestro modelo sería de la siguiente forma:

Celda Objetivo. Es la celda que contiene la distancia total, es decir, el resultado de multi-plicar la matriz de distancias por la matriz solución.

Variables de Decisión. Corresponde a la matriz solución o matriz de decisión, asegurandonosde seleccionar solo los elementos de la matriz, no los encabezados de �la ni columna.

Restricciones. Este modelo tiene 2 restricciones.

� R1: Cada elemento en la matriz de decisión debe ser menor o igual al elemento co-rrespondiente en la matriz de adyacencia. La razón de esta restricción es garantizarque la solución solo puede considerar los arcos existentes y no agregar un arco dondeno existe, por lo que si dos nodos son adyacentes, el arco entre ellos puede ser partede la Ruta Mas Corta, puesto que tendrá un 1 en la matriz de adyacencia pero si los

61


nodos no son adyacentes, el valor en la matriz de adyacencia es de 0 por lo que noexiste un camino entre dichos nodos.

� R2: La �la que contiene las diferencias entre las sumas de �las y columnas debe serigual a la �la donde se identi�ca el nodo de entrada y salida. Esto nos garantiza quese identi�que solamente una ruta, con un único punto de entrada y uno de salida.

A continuación se muestra el cuadro de diálogo para el Solver de�niendo el modelo:

En el cuadro de opciones, debemos asegurarnos que esté seleccionada la opción para asumirvariables no negativas:

Con esto estamos listos para que Solver proceda a resolver el modelo, el cual queda como semuestra en la �gura siguiente:

Como puede observarse, la matriz solución presenta solamente 2 celdas con valor de 1 (resal-tadas en color verde) y el resto con 0. Las celdas con 1 son, en coordenadas(�la,columna): (1,4)y (4,6). Esto quiere decir que la Ruta Mas Corta entre los nodos 1 y 6 inicia en el nodo 1, luegova al nodo 4 y �nalmente al nodo 6. En la celda objetivo, podemos ver la longitud total de dicha

62


ruta, que es de 4 unidades de distancia. Al corroborar la red original, podemos constatar que,efectivamente, no existe ningún camino para llegar del nodo 1 al nodo 6 que tenga una longitudmenor a 4 unidades. Como en cualquier problema de optimización lineal, es posible que existansoluciones alternas, es decir, una ruta diferente, pero podemos tener la certeza que ninguna so-lución será menor a 4 unidades. En este ejemplo en particular, no existe ningún otro camino conuna longitud igual a 4 para llegar del nodo 1 al 6.Ahora procederemos a resolver el mismo ejemplo en Sage para ilustrar la facilidad de trabajar

con los algoritmos de redes en esta poderosa y versatil herramienta.Una de las aplicaciones para las cuales Sage ya viene preparado, es la de Teoría de Grafos. Sage

permite la creación, visualización y manipulación de grafos y ya incluye una gran variedad dealgoritmos para los mismos. Existen distintas formas de representar un grafo en Sage. Podemoshacerlo por medio de una matriz de adyacencia, una lista de arcos y un diccionario de arcos ynodos entre otras. Por simplicidad, vamos a escoger la segunda, es decir, vamos a representar elgrafo en forma de una lista de arcos. Cada elemento de la lista estará formado por una triadade la forma (X, Y, Z) donde X y Y representan los números de los nodos y Z representa el peso(costo) del arco que los une.

5.2.4. Modelo de Flujo Máximo

El problema de �ujo máximo es uno de los más comunmente encontrados en aplicaciones deredes para ingeniería. El problema básicamente consiste en determinar la cantidad máxima de

63


un tipo de material que puede �uír entre 2 nodos, llamados comunmente fuente y sumidero,respectivamente, en una red que puede representar distintas situaciones como puede ser:

Una red de tuberías

Una red de carreteras

Una red de computadoras

Una red de distribución eléctrica

etc.

El algoritmo más utilizado para resolver este modelo es el denominado Ford Fulkerson8que buscaincrementar gradualmente el �ujo en cada camino hasta alcanzar el máximo posible en la red.Se deja al lector la lectura y comprensión del algoritmo, ya que nos estaremos limitando alplanteamiento y solución del modelo por medio de una hoja de cálculo electrónica.Este algoritmo parte de los siguientes principios:

Existe un �ujo que viaja desde un unico lugar de origen hasta un unico lugar de destino através de arcos que conectan nodos intermedios.

Cada arco tiene una capacidad que no puede ser excedida.

La capacidad no necesariamente será la misma para cada arco.

La capacidad de un arco en un sentido puede ser distinta a la capacidad en el sentidocontrario.

A continuación se presenta un ejemplo de dicho problema, con el cual se desarrollará la soluciónal mismo:

Una ciudad es atravesada por una red interestatal de carreteras de norte a sur que le permite Ejemplo # 8alcanzar un nivel de 15000 vehículos/hora en el horario �pico�. Debido a un programa demantenimiento general, el cual requiere el cierre de dichas vías, un grupo de ingenieros hapropuesto una red de rutas alternas para cruzar la ciudad de norte a sur, la cual incorporaavenidas importantes. La red propuesta es la siguiente, en donde se indica claramente lacantidad máxima de vehículos (en miles) que pueden circular por dichas vías en cada sentido:En la grá�ca siguiente puede observarse la red, donde cada arco tiene 2 valores de �ujo. Porejemplo, el �ujo del nodo 1 al 2 es de 5 unidades (en este caso, miles de vehículos/hora) mientrasque en el sentido contrario (de 2 a 1) el �ujo es 0, lo que en este ejemplo, indicaría que se tratade una vía en un solo sentido.

Para resolver el modelo de �ujo máximo, es necesario representar el problema en forma ma-tricial. Se utilizarán 2 matrices a las cuales denominaremos Matriz de Capacidades y MatrizSolución, respectivamente.

8http://es.wikipedia.org/wiki/Algoritmo_de_Ford-Fulkerson

64


Nuevamente, la imagen anterior muestra las 2 matrices iniciales que solamente contienen datos,sin incluír ningún cálculo ni fórmula en la hoja electrónica. La primera es la matriz de capacidades,que contiene para cada arco conectando un par de nodos, la capacidad en un sentido, tomandoen cuenta que las �las representan nodos de salida y las columnas, nodos de llegada. Así, porejemplo, la �la 1 contiene la capacidad máxima que puede salir del nodo 1, llegando a los nodos2, 3 y 4, mientras que la columna 2 contiene el �ujo máximo que puede llegar de los nodos 1 y3. La matriz de decisión o matriz solución contiene los 1's que son simplemente valores inicialesque Solver utilizará para encontrar la solución al modelo.Ahora debemos proceder a agregar las fórmulas de cálculo, las cuales para este caso se realizan

sólamente en la matriz de decisión. Al igual que en el problema de Ruta Más Corta, se procedea calcular la sumatoria para cada una de las �las y para cada una de las columnas. Luego, aligual que en RMC procedemos a calcular, en forma de �la, la diferencia entre la sumatoria de�las y la sumatoria de columnas, en ese orden,

∑fila −

∑columna, con una sola diferencia

respecto a RMC: para este modelo esta diferencia no se calcula para el nodo de salida (fuente) nipara el nodo de llegada (sumidero) sino solamente para los nodos intermedios. En este ejemplo,queremos calcular el �ujo máximo de norte a sur, es decir, entre el nodo 1 y el nodo 7 por lo queno se calcula la diferencia para esos 2 nodos.

Finalmente, agregamos, abajo de la �la anterior, los valores de �ujo neto para los nodos

65


intermedios, que al igual que en el modelo RMC deben ser todos igual a 0.

Con esto, ya podemos proceder a plantear el modelo en Solver. Aquí también hay algunasdiferencias respecto a los modelos anteriores. Los parámetros del modelo son los siguientes:

1. La celda objetivo corresponde a la celda que contiene la sumatoria de la �la 1, en esteejemplo, la celda J14, ya que esto corresponde a todo lo que sale del nodo fuente y queeventualmente llegará al nodo sumidero.

2. Esta celda debe ser maximizada.

3. Las variables de decisión, como siempre, son las que están en nuestra matriz de decisión omatriz solución.

4. Las restricciones del modelo pueden plantearse en 2 pasos:

a) La matriz de decisión debe ser menor o igual a la matriz de capacidad.

b) El �ujo neto en los nodos intermedios debe ser igual a 0

5. Las variables de decisión deben ser no negativas

El modelo planteado en Solver se muestra a continuación:

Al resolver el modelo, la solución se muestra en la matriz de decisión:

66


En la matriz de decisión puede verse claramente que el �ujo máximo a través de esta red esde 14000 vehículos/hora, lo cual es insu�ciente para manejar la capacidad de la red original.Aunque en la matriz también puede verse el �ujo en cada uno de los arcos, esto puede apreciarsemejor cuando lo representamos grá�camente, donde puede comprobarse que ninguno de los �ujosindividuales excede la capacidad del arco respectivo:

Nuevamente procederemos a mostrar lo sencillo que es hacer el mismo ejercio pero utilizandoSage.

67


5.2.5. Arbol Mínimo de Expansión

Como se indicó anteriormente, el estudiante debió haber realizado una revisión bibliográ�capara algunos términos importantes en el lenguaje de grafos. Como resultado de dicha revisión,seguramente encontró el concepto de Arbol, el cual, en el contexto de Teoría de Grafos, se re�erea un grafo conexo que no contiene ciclos.

El algoritmo de Arbol Mínimo de Expansión es de suma utilidad en aplicaciones de ingenieríarelacionadas a la plani�cación de instalación de servicios públicos, tales como:

Redes de carreteras

Redes de cableado para eléctricidad, telefonía, CATV, datos, etc.

Redes de distribución de agua potable, gas, etc.

El objetivo de dicho algoritmo es interconectar un conjunto de nodos de tal forma que el costototal (la suma de los costos de los arcos) para dicha conexión sea mínima. Hay que recordar queen el contexto de optimización, el término costo es un concepto genérico que puede representarcualquier característica que se desea minimizar, lo que puede referirse a la cantidad de materialrequerido (cable, asfalto, tubería, etc.).El algoritmo mas comunmente utilizado para encontrar un árbol de expansión mínima es

el denominado Algoritmo de Kruskal 9. Este es un algoritmo que cae en la categoría de losdenominados �algoritmos voraces� 10 por la forma como se desarrolla, buscando en cada pasola mejor opción disponible. Esto hace que la aplicación de dicho algoritmo sea muy sencilla derealizar manualmente. Nuevamente se deja al estudiante la tarea de leer y entender el algoritmoen las fuentes de consulta disponibles.Aunque es posible aplicar programación lineal para resolver el problema del árbol mínimo de

expansión, para esto se requiere de algunos conceptos (teoría de dualidad, relajación, etc.) queestán fuera del alcance de estas notas por lo que para la solución de este problema, por lo queen este caso vamos utilizar unicamente Sage para este algoritmo.Uno de los algoritmos que ya vienen por defecto en Sage es el de Arbol Mínimo de Expansión.

Para utilizarlo, simplemente debemos crear la red para la cual deseamos calcular el árbol. Vamosa desarrollar un ejemplo sencillo donde se demostrará paso a paso el uso de la herramienta parala aplicación de este algoritmo.

La ciudad de Vancouver está plani�cando el desarrollo de una nueva linea en sistemas de Ejemplo # 9

9http://es.wikipedia.org/wiki/Algoritmo_de_Kruskal10http://es.wikipedia.org/wiki/Algoritmo_voraz

68


Figura 5.5.: Ejemplos de árbol

tránsito. El sistema debe conectar 8 puntos distintos entre residencias, centros comerciales yotros puntos importantes. El departamento de plani�cación de tránsito de la ciudad necesitaseleccionar un conjunto de rutas que conecten los distintos puntos al menor costo posible.La red seleccionada debe considerar la factibilidad y el costo de cada ruta. A continuaciónse muestra la red para este ejemplo. Los nodos en esta red representan los distintos puntos quedeben interconectarse por medio del sistema. Los arcos entre los nodos indican la factibilidad deconstruír la línea entre cada par de nodos, así, por ejemplo, el arco entre los nodos 1 y 3 indicaque es factible la construcción mientras que la ausencia de un arco entre los nodos 1 y 4 indicaque no es factible construir una linea que una directamente esos 2 puntos. Los valores en losarcos indican el costo (en millones de US$) de construir la línea en ese arco en particular.Ahora vamos a proceder a representar el modelo de red en Sage.

Así, por ejemplo, el arco entre el nodo 1 y el 3 se representaría de la forma (1,3,33) y el arcoentre 1 y 2 quedaría de la forma (1,2,28).Para de�nir una lista en Sage, encerramos los elementos entre corchetes [] separándolos por

comas. Le daremos a la lista un nombre, que en este caso será �arcos�, de la siguiente forma:

69


genos muestra el arbol indicando claramente los vértices que lo forman y el peso de cada uno, asícomo el peso (costo) total del mismo que es de 236 que en este ejemplo corresponde a millones deUS$. La grá�ca siguiente muestra como quedaría formado el sistema de tránsito para la ciudadcon la solución obtenida:

70


Todos los nodos de la red han sido conectados por medio del árbol mínimo de expansión conlo cual se optimiza el uso de los recursos para la construcción del sistema de tránsito requerido.

5.2.6. Problema del Agente Viajero

Uno de los problemas más famosos en el mundo de la optimización es el que se conoce comoel Problema del Agente Viajero (Traveling Salesman Problem)11 debido a la complejidad que susolución conlleva. En forma resumida, el problema se puede describir de la siguiente forma: dadoun conjunto de ciudades (o nodos en un grafo) que se encuentran conectados y se conocen lasdistancias, se necesita encontrar un tour (saliendo de uno de los nodos o ciudades y volviendo almismo nodo de partida) de manera que se visiten todos los nodos (ciudades) y que la distanciatotal recorrida sea mínima. Para entender la forma como la complejidad de solución de este pro-blema crece, pensemoslo de la siguiente forma: si queremos resolver el problema para 5 ciudades,debemos primero elegir la ciudad de partida, esto nos da 5 posibilidades, luego, tenemos 4 posi-bilidades para elegir la ciudad siguiente a visitar, después tenemos 3 posibilidades para la ciudadsiguiente y así sucesivamente. Como podrá apreciar el lector, se trata de un problema que creceen forma factorial respecto al número de ciudades a visitar. En realidad, ya que la distancia entrelas ciudades es la misma en ambos sentidos (de A a B es igual que de B a A) y que cada rutaconstituye un ciclo, por lo que el punto de partida no es importante, el número total de rutasposibles es igual a (n−1)!

2 .Dado lo anterior, el espacio de búsqueda para el problema de 5 ciudades es de 12 posibles rutas,

pero si hablamos de un problema con 10 ciudades, el número posible de rutas es de 181,440 ysi el problema fuera de 20 ciudades, el número posible de tours sería de 6.082E16. Si nuestracomputadora pudiese evaluar 1 millón de tours cada segundo, tardaría poco menos de 1929 añospara encontrar el tour óptimo.El problema del viajero pertenece a la categoría de los problemas NP completos 12. Esta

terminología pertenece a la teoría de complejidad computacional, que es algo que está fuera delalcance de estas notas, sin embargo, basta decir que no existe un algoritmo que garantice poderencontrar una solución óptima. Para problemas de un tamaño relativamente pequeño (algunasdecenas o incluso cientos de nodos) puede utilizarse algunos algoritmos que son capaces deencontrar el tour óptimo, por ejemplo, programación dinámica, branch and bound (rami�cación yacotamiento) y otros. Afortunadamente, Sage nos facilita la vida para solucionar estos problemassin tener que preocuparnos de la operatoria.Para demostrar este tipo de problemas, lo haremos por medio de un ejemplo:

La tabla siguiente muestra las distancias (en km) entre algunas de las principales ciudades Ejemplo # 9

11http://es.wikipedia.org/wiki/Problema_del_viajante12http://es.wikipedia.org/wiki/NP-completo

71


europeas. Si un turista mochilero desea realizar un tour visitando todas las ciudades, ¾cualdebe ser el orden en que debería hacerlo para recorrer la mínima distancia total? Paraproceder a resolver este problema, es necesario cambiar un poco la estrategia respecto a losotros modelos de redes que hemos resuelto anteriormente. En los modelos anteriores, nosotrosle indicamos a Sage en forma explícita cada uno de los arcos de la forma (inicio, �n, distancia),sin embargo, en este tipo de problemas, esto sería poco práctico, ya que la cantidad de arcoscrecería en forma cuadrática respecto al número de ciudades a visitar, por lo que, aunque en esteproblema es manejable ya que son solamente 6 ciudades, en un problema mayor sería demasiadoengorroso.

Vamos entonces a atacar el problema de una forma mas inteligente, aprovechando las ventajasque Sage nos da al hacer uso de las estructuras de programación de Python. Para ello, primerovamos a ingresar la matriz de distancias en su forma puramente matricial, de la siguiente forma:

Esta forma es sumamente práctica ya que si tuviesemos un problema de 20 ciudades, solamentedeberíamos ingresar la matriz de distancias en lugar de ingresar los 400 nodos individualmente.Una vez que tenemos los arcos, la creación del grafo y su posterior solución es sumamente sencilla.Veamos:

72


Notese que por tratarse de un grafo dirigido, Sage dibuja dos arcos entre cada par de nodos,uno en cada sentido, lo cual sería importante en caso que las distancias fueran diferentes, lo cualno es el caso, sin embargo para la solución de este tipo de modelos, siempre debemos declararlocomo un grafo dirigido.

La solución nos muestra el tour óptimo entre las 6 ciudades, el cual es independiente del puntode inicio (igual al de �nal) ya que se puede iniciar en cualquiera de los 6 nodos y seguir el ordenindicado por el grafo. Al regresar al nodo (ciudad) de partida, se habrá recorrido una distanciatotal de 4773 km que es el valor mínimo de todos los posibles tours.

5.3. Ejercicios

5.3.1. Ejercicios Programación Lineal

5.3.2. Ejercicios Modelo de Transporte

5.3.3. Ejercicios Modelo de Asignación

5.3.4. Ejercicios Ruta Más Corta

5.3.5. Ejercicios Flujo Máximo

5.3.6. Ejercicios Arbol Mínimo de Expansión

73

6. OPTIMIZACIÓN NO LINEAL NORESTRINGIDA EN VARIAS VARIABLES

Al igual que en el caso de la optimización no restringida en una variable, este tipo de problemaspertenece al campo del cálculo diferencial, aunque en este caso se trata de cálculo multivaria-do. Existe una diversidad de métodos para resolver estos problemas y la mayoría involucranel gradiente de la función1. El gradiente, como el estudiante recuerda de sus cursos de cálculomultivariado, es un vector que está compuesto por las derivadas parciales de la función respectoa cada una de las variables de dicha función y que es perpendicular u ortogonal al punto de lasuper�cie de la función en el cual se obtiene.Nuevamente se deja al estudiante refrescar estos conceptos y la teoría relacionada ya que

como lo hemos hecho hasta aquí, recurriremos a nuestras herramientas tecnológicas para resolvereste tipo de problemas. En este caso nuevamente haremos uso de Sage como la herramientapor excelencia. Como lo habrá notado el estudiante, Sage es una especie de navaja del ejércitosuizo para el cálculo matemático por computadora, aquella que tiene una herramienta para cadanecesidad, solo que si quisieramos tener una navaja suiza con tantas opciones como Sage, talvezse vería algo como esto:

En el caso de la optimización multivariada no lineal y no restringida, Sage nos presenta conuna función que nos facilita el trabajo enormemente y la cual se mostrará a continuación a travésde un ejemplo:

Suponga que se está desarrollando un proyecto de carreteras en 4 frentes distintos, A, Ejemplo #10B, C y D que tienen coordenadas en un plano cartesiano igual a (2,3), (7,2), (5,4) y

(4,2) respectivamente. Es necesario establecer una centro de operaciones para abastecerde insumos los 4 frentes. Cada frente tiene distinta demanda de insumos por lo que se haestimado que se tienen que realizar 9 viajes diarios al frente A, 5 viajes diarios al frente B,3 viajes al frente C y 6 viajes al frente D cada día. Se necesita determinar las coordenadaspara establecer el centro de operaciones de manera que la distancia total recorrida cadadía a los 4 frentes sea mínima. En un problema de este tipo, se puede utilizar dos tipos dedistancias como función a minimizar, la Distancia Euclidiana2 o la Distancia Manhattan3. Para

1http://es.wikipedia.org/wiki/Gradiente2http://es.wikipedia.org/wiki/Distancia_euclidiana3http://es.wikipedia.org/wiki/Geometría_del_taxista

74

6. OPTIMIZACIÓN NO LINEAL NO RESTRINGIDA EN VARIAS VARIABLES

desarrollar este ejemplo, estaremos utilizando la distancia euclidiana.Como primer paso, es interesante ver la ubicación en el plano cartesiano de los puntos que

representan los frentes. Para esto, podemos utilizar las maravillosas funcionalidades de gra�caciónde Sage que nos permite visualizar esto de una forma rápida y sencilla. A continuación se muestrala sesión de Sage conteniendo las instrucciones para hacer esto:

El objetivo en este ejemplo es minimizar la distancia total euclidiana, la cual puede ser expre-sada por la siguiente ecuación:

DT =∑√

(x− xi)2 + (y − yi)2

Donde x y y son las coordenadas del centro de operaciones y xiy yison las coordenadas decada uno de los frentes. Al sustituír los valores para este ejemplo, la distancia total queda de lasiguiente manera:

75


DT =√

(x− 2)2 + (y − 3)2+√

(x− 7)2 + (y − 2)2+√

(x− 5)2 + (y − 4)2+√

(x− 4)2 + (y − 2)2

Como puede observarse, la distancia total corresponde a una función claramente no lineal en2 variables.Ahora, procedemos a ingresar la función de Distancia Total en Sage para después poderla

optimizar, utilizando para ello la rutina de optimización no lineal que Sage ya tiene prede�nida.

Como puede observarse en la �gura anterior, el punto que señala la ubicación óptima para el

76


Centro de Operaciones se encuentra en las coordenadas (3.94, 2.19) lo que se ubica muy cercanoal punto D cuyas coordenadas son (4,2). Esto quiere decir que al ubicar el Centro de Operacionesen esas coordenadas, se estará minimizando la distancia total que se recorre cada día a cada unode los frentes.Como se mencionó al inicio de esta sección, la mayoría de algoritmos para resolver problemas

de optimización no lineal en varias variables utilizan métodos basados en el cálculo de gradientespara las funciones, lo cual implica el cálculo y evaluación de derivadas parciales. Existen diversosmétodos para hacer esto, la mayoría utiliza técnicas numéricas. Estas técnicas presumen que lafunción objetivo es derivable y tiene caracteristicas �suaves�, es decir, gradientes moderados. Enel ejemplo anterior, podemos visualizar la función que estamos optimizando ya que Sage tambiénpermite realizar grá�cos en 3D y en este caso, por tratarse de una función de 2 variables, generaráuna super�cie tridimensional. Veamos la grá�ca:

De hecho, con Sage podemos manipular la gra�ca en 3D, rotándola para verla desde distintosángulos, lo cual nos puede dar una mejor idea de donde puede estar el valor óptimo.Cuando las funciones a minimizar no son �suaves� sino que presentan demasiados óptimos

locales, los métodos basados en cálculo no son la mejor alternativa. En estos casos se debenutilizar técnicas heurísticas, de las cuales se habla un poco en el capítulo 8.

6.1. Ejercicios

77

7. OPTIMIZACIÓN NO LINEALRESTRINGIDA EN VARIAS VARIABLES

En el caso de la optimización no lineal con restricciones en varias variables, entramos enun territorio mas escabroso y complejo desde la perspectiva del análisis matemático, ya queen este caso tampoco se cuenta con un algoritmo que funcione de una manera universal paracualquier tipo de problema. Los métodos para resolver este tipo de problemas, por tratarse defunciones no lineales y en varias variables son inevitablemente basados en cálculo diferencial,aunque estos no necesariamente garantizan la solución e�caz de cualquier problema. Debido amuchas condiciones de complejidad que se presentan, la solución de estos problemas no es trivialy de hecho, hasta hace relativamente muy poco tiempo se empezó a estudiar estos problemas ya desarrollar metodologías de solución, muchas de ellas quedan fuera del alcance de estas notaspor lo que no serán abordadas. En cambio, nos enfocaremos en algunos problemas relativamentesencillos pero que demuestran la forma como estos problemas pueden ser abordados. En el casode problemas demasiado complejos para ser resueltos en forma analítica, se requiere el uso demétodos numéricos o técnicas heurísticas de las cuales se habla un poco en el capítulo 8.Para la optimización no lineal con restricciones pueden presentarse dos situaciones respecto al

tipo de restricciones:

Restricciones de igualdad

Restricciones de desigualdad

Se tratarán ejemplos sencillos de cada una de ellas.

7.1. RESTRICCIONES DE IGUALDAD

Uno de las metodologías más utilizadas ante esta situación y que seguramente el lector recor-dará de sus cursos de cálculo multivariado es el de los Multiplicadores de Lagrange1. Al igualque en los casos anteriores, se deja al estudiante la inquietud de revisar la bibliografía pertinentepara cubrir los fundamentos teóricos de la metodología, pero baste decir que este es uno de losmétodos para los cuales contar con una herramienta informática de manipulación algebraica esde suma utilidad, puesto que el método requiere realizar varias operaciones sobre objetos al-gebraicos, por ejemplo, derivadas parciales y solución de ecuaciones no lineales, lo cual puedecomplicarse bastante al momento de realizarlo de forma manual.La forma general del método de Multiplicadores de Lagrange es la siguiente: Por ejemplo,

para determinar los valores mínimos y máximos de la funciónf(x, y, z) sujeta a la restriccióng(x, y, z) = k determinar todos los valores de x, y, z y λtales que:

∇f(x, y, z) = λ∇g(x, y, z)

Recordando que ∇f se re�ere al gradiente de una función, es decir, el vector formado porlas derivadas parciales de la función respecto a cada una de sus variables, como sigue: ∇f =(∂f∂x ,

∂f∂y ,

∂f∂z )

De esto se obtiene el Lagrangiano que queda de la siguiente forma:

1http://es.wikipedia.org/wiki/Multiplicadores_de_Lagrange

78

7. OPTIMIZACIÓN NO LINEAL RESTRINGIDA EN VARIAS VARIABLES

L = f − λ(g − k)

Y luego derivando parcialmente esta expresión respecto a cada una de las variables x, y, z, λse obtiene un sistema de ecuaciones simultáneas, muchas veces no lineales, las cuales se debenresolver para encontrar la solución al problema original, de la forma:

∂L

∂x= 0

∂L

∂y= 0

∂L

∂z= 0

∂L

∂λ= 0

Por lo que en el caso de una función de 3 variables y una restricción, se requiere resolver unsistema de 4 ecuaciones simultáneas no lineales. Por cada restricción que se tenga se agregará unmultiplicador y por ende, una variable y una ecuación más al sistema.Vamos a desarrollar un ejemplo para ayudar a aclarar este procedimiento, apoyándonos en

Sage para realizar todo el proceso. El ejemplo es el siguiente:

Cuales deben ser las dimensiones de un envase para leche de forma rectangular, volumen Ejemplo #11de 512 cm3 y costo mínimo, si el material de los lados de la caja cuestan 10 centavos el

centrimetro cuadrado y el material de la tapa y el fondo cuestan 20 centavos el centímetrocuadrado. En este caso, vamos a realizar un diagrama para representar la caja de carton ypoder asignar una variable a cada una de las dimensiones de la caja:En este caso, lo que se desea es minimizar la función de costo total del material necesario para

el envase, el cual estaría dado por la siguiente ecuación:

CT = 10 ∗ (2xz) + 10 ∗ (2yz) + 20 ∗ (2xy)

CT = 20xz + 20yz + 40xy

Mientras que la restricción en este caso se re�ere al volumen total que el envase debe contener:

V T = xyz = 512

Ahora aplicando el lagrangiano a las 2 ecuaciones anteriores nos queda de la siguiente manera:

L = CT − λ(V T − 512)

Ahora podemos utilizar Sage para resolver el modelo:

79


Como se puede ver, Sage nos proporciona todas las soluciones al sistema de ecuaciones, inclu-yendo las soluciones complejas. Para efectos prácticos solo nos interesa la única solución real po-sitiva por lo que en este caso, las dimensiones óptimas para el envase son x = 6.35cm,y = 6.35cmy z = 12.7cm.En resumen, Sage nos permite resolver un problema relativamente complejo sin tener que

preocuparnos por realizar el proceso de derivación parcial y luego de solución de las ecuacionessimultáneas no lineales, lo cual puede llegar a ser bastante engorroso y complejo para ciertosproblemas.

7.2. RESTRICCIONES DE DESIGUALDAD

Como se mencionó en la sección anterior, la optimización no lineal restringida es un camposumamente complejo y que es objeto de constante investigación y desarrollo por parte de expertosen muchas disciplinas cientí�cas como matemáticas, ciencias de la computación, física, estadística,etc. Es importante que el estudiante entienda un concepto clave en optimización no lineal, ladiferencia entre un óptimo local y un óptimo global.

1. Optimo Local: Se re�ere a un valor máximo o mínimo de una función respecto al conjuntode valores cercanos2. En otras palabras, se re�ere a un valor óptimo en una región especí�cadel dominio de la función. Una función puede tener muchos óptimos locales. Para encontrarun óptimo local puede recurrirse a métodos basados en gradientes y buscar el punto en el

2http://en.wikipedia.org/wiki/Local_optimum

80


Figura 7.1.: Ejemplo de una función con muchos óptimos locales

que el gradiente es 0. Existen varios algoritmos e�cientes para la búsqueda de óptimoslocales.

2. Optimo Global: El óptimo global es un valor máximo o mínimo de una función en todosu dominio3. Como se mencionó anteriormente, una función puede tener varios óptimoslocales por lo que el óptimo global será el máximo (o mínimo) de todos los óptimos locales.La búsqueda de óptimos globales es un problema sumamente complejo ya que no existenalgoritmos que garanticen poder encontrarlos. Para encontrar óptimos locales generalmentese debe recurrir a algoritmos heurísticos y que muchas veces son diseñados para un problemaespecí�co por lo que dependerá del tipo de problema y sus características particulares. Estosalgoritmos se basan en explorar en forma selectiva todo el espacio de soluciones.

Al igual que en la sección anterior, vamos a presentar un ejemplo relativamente sencillo de aplica-ción de optimización no lineal multivariada con restricciones de desigualdad, esto principalmentepara demostrar el uso de las herramientas para su solución, especí�camente Sage que ya vienepreparado con algoritmos para este tipo de problemas. La clave del éxito en la solución de estosproblemas es el correcto planteamiento del modelo matemático, algo en lo cual ya hemos abun-dado con ejemplos a lo largo de estas notas y la selección de la herramienta para su solución, queen este caso es Sage. Veamos un ejemplo especí�co de un problema no lineal en varias variablesy con restricciones de desigualdad:

Una compañía petrolífera debe determinar cuántos barriles de petróleo debe extraer en los Ejemplo #12próximos 2 años. Si la compañía extrae x1 millones de barriles durante un año, se podrá

vender cada barril en 30−x1 Euros. Si extrae x2 millones de barriles durante el segundo año,se podrán vender en 35−x2 Euros cada barril. El costo de extraer x1 barriles el primer año esde x21 millones de Euros y el costo para extraer x2 millones de barriles el segundo año es de2x22 millones de Euros. Se puede obtener como máximo un total de 20 millones de barriles depetróleo y se puede gastar como máximo 250 millones de Euros en la extracción. Formularel problema de optimización para determinar cuánto debe extraer durante los próximos 2años. En este caso, el problema nos da su�cientes indicios sobre el objetivo, ya que se nosproporciona información de precio de venta por barril así como el costo de extraer el petróleo.Basado en esto podemos inferir que la compañía buscará maximizar su ganancia. Las variables

3http://en.wikipedia.org/wiki/Global_optimum

81


de decisión también son bastante obvias puesto que el enunciado del problema prácticamentenos da la pauta que debemos decidir cuántos millones de barriles extraer el primer año (lo quese denomina como x1y cuántos millones de barriles debemos extraer el segundo año, denotadopor x2. Con esto nuestro modelo quedará de la siguiente forma:

max G=(30− x1)x1 − x21 + (35− x2)x2 − 2x22

max G = 30x1 − 2x21 + 35x2 − 3x22

Sujeto a las siguientes restricciones:

x1 + x2 ≤ 20

x21 + 2x22 ≤ 250

Como puede observarse, se trata de un modelo de programación matemática que es claramenteno lineal, puesto que la función objetivo presenta 2 variables de decisión elevadas al cuadrado.De igual forma, el modelo es restringido por la presencia de 2 restricciones, una de las cualescontiene también a ambas variables elevadas al cuadrado. Para resolver este modelo, vamos arecurrir nuevamente a nuestra navaja del ejército suizo, Sage, que ya contiene una serie de rutinaspara la optimización no lineal restringida.Uno de los módulos que Sage contiene, pero que en realidad pertenece al lenguaje de progra-

mación Python, es Scipy. Se trata de una librería de funciones cientí�cas y matemáticas. Entreestas funciones existe una denominada �optimize� que a su vez contiene una serie de rutinas pararealizar optimización de funciones. Lo primero que debemos hacer es importar esta librería, paralo cual hacemos lo siguiente:

El módulo �optimize� contiene a su vez una rutina denominada COBYLA que sirve paraoptimización restringida. COBYLA viene de las siglas Constrained Optimization BY LinearAproximation4 que traducido signi�ca Optimización Restringida Por Aproximación Lineal. Estees un método desarrollado por Michael Powel y que permite optimizar funciones sin utilizargradientes o derivadas si no, como su nombre lo indica, aproximaciones lineales. Se deja alestudiante leer mas acerca de este método. Una particularidad de la implementación de estealgoritmo en Python es que solamente permite encontrar el mínimo de una función en la cualtodas las restricciones son del tipo ≥ 0 . En este ejemplo tenemos un problema de maximizacióncon restricciones ≤. Vamos a recurrir a una manipulación muy común en optimización quepermite convertir un problema de maximización en minimización y viceversa. Recordemos que:

max f ≡ min − f

Por lo que la función objetivo a minimizar quedaría de la siguiente forma:

min −G = 2x21 + 3x22 − 30x1 − 35x2

Igualmente, para invertir el signo de las restricciones, simplemente las multiplicamos por −1y pasamos todos los términos al lado izquierdo para que quede 0 del lado derecho, con lo cualquedarían de la siguiente forma:

4http://en.wikipedia.org/wiki/COBYLA

82


20− x1 − x2 ≥ 0

250− x21 − 2x22 ≥ 0

Adicionalmente, debemos agregar en forma explícita las restricciones de no negatividad paralas variables ya que este algoritmo no asume dicha condición:

x1 ≥ 0

x2 ≥ 0

Ahora vamos a proceder a de�nir las funciones en Sage. Para esto, vamos a utilizar esta vez elformato de de�nición de funciones de Python, que tiene la forma

def nombrefunción(parámetros):

return expresión

y vamos a de�nir una función para cada una de las expresiones anteriores, es decir, la funciónobjetivo y cada una de las restricciones. En el caso de los parámetros, en lugar de utilizar variablesindividuales vamos a utilizar una lista a la que vamos a llamar X y cada uno de sus elementosserá una variable de decisión. Recordemos que el primer elemento de una lista tiene el índice 0.También vemos que las funciones para las restricciones deben retornar solamente el lado izquierdoya que la rutina asume que el lado derecho es ≥ 0. Veamos como se hace en Sage:

Ahora ya podemos proceder a llamar la subrutina de optimización, la cual tiene la siguienteestructura:

optimize.fmin_cobyla(función_objetivo, [lista de valores iniciales],

[lista de restricciones], rhoend=tolerancia)

83


Como podemos observar, Sage nos proporciona la solución al modelo. En la �gura anteriorpodemos ver la solución en la cual los valores de las variables están denotadas por X, por lo quela solución para x1es 7.5 y para x2es igual a 5.8333. El valor de la función objetivo está dadopor F = −2.1458E + 02 pero recordemos que estabamos minimizando el negativo de la funciónobjetivo original por lo que debemos cambiarle el signo, entonces la solución para la máximaganancia que la empresa petrolera puee obtener es de 214.58 millones de Euros, extrayendo elprimer año 7.5 millones de barriles y el segundo año 5.833 millones de barriles de crudo.Existe otra rutina que Sage también trae de�nida y que puede ser utilizada en estos problemas

de optimización multivariada no lineal restringida. La estructura es parecida a la rutina anterior,aunque cambia un poco el orden de los factores:

minimize_constrained(función_objetivo, [lista de restricciones],

[lista de valores iniciales])

Si utilizamos esta rutina, obtenemos los mismos valores para las variables de decisión:

En este ejemplo ambas rutinas tienen exito en encontrar la solución y ambas coinciden, sinembargo, como ya se mencionó, la solución de problemas de optimización no lineal es un problemacomplejo y no existe garantía de poder llegar a la solución óptima. Algunas veces, si al principiono se tiene éxito en obtener una solución con una de las rutinas, puede probarse con otra ose puede probar cambiando los valores iniciales de las variables para que el algoritmo inicie labúsqueda en un punto diferente, pero eso tampoco nos da certeza de que vamos a obtener lasolución óptima.

7.3. Ejercicios

84

8. MÉTODOS HEURÍSTICOS PARAOPTIMIZACIÓN

85

Parte III.

MODELOS DE LINEAS DE

ESPERA

86

Documents

Notas Optimizacion Ingenieros