Programacion lineal

Universidad de Chile Facultad de Ciencias F´ ısicas y Matem´ticas a Departamento de Ingenier´ Industrial ıa

Modelamiento de Problemas de Programaci´n Lineal o con Variables Continuas.
Marcel Goic F.1

IN34A: Clase Auxiliar

Esta es una versi´n bastante preliminar por lo que puede contar con numerosas faltas de ortografia y o errores no forzados. Si encuentran alguno favor de denunciarlo amgoic@cec.uchile.cl

1

IN34A: Optimizaci´n o

Pag. 1

1.

Introducci´n o

No existe una metodolog´ muy concreta acerca de como se debe modelar matem´ticamente ıa a un problema y el asunto tiene mucho de intuici´n y arte. En la siguiente clase intentaremos o dar una introducci´n al modelamiento de problemas de optimizaci´n, mostrando un par de o o problemas t´ ıpicos y discutiendo unpoco las dificultades que pueden presentarse y cuales son los errores mas comunes. Una forma sencilla y bastante general de ordenar el proceso de modelaci´n, consiste en o dividirlo en tres partes: 1. Definici´n de variables de decisi´n. o o 2. Planteamiento de las restricciones del problema. 3. Planteamiento de la funci´n objetivo. o

1.1.

Definici´n de variables. o

Como primer paso parapoder modelar ordenadamente un problema de optimizaci´n debemos o distinguir que variables son aquellas sobre las que podemos tomar decisiones en el problema y darles un nombre, es decir, debemos darnos cuenta que variables estan bajo nuestro control. A veces es necesario incluir variables que si bien no podemos ejercer una decisin directa sobre ellas, nos sirven como herramienta auxiliar ya sea paraplantear restricciones o para escribir nuestra funci´n objetivo. Ser´ variables de decisi´n por ejemplo la cantidad de producto a o ıan o enviar desde el centro de producci´n i hasta el centro de consumo j (que podr´ o ıamos llamar xij ), la cantidad de insumos a adquirir en el per´ ıodo t (que podr´ ıamos llamar yt ), el numero de horas que destinaremos la m´quina i a trabajar en el proceso j enel per´ a ıodo t (que t podr´ ıamos llamar zij ), etc.

1.2.

Planteamiento de restricciones.

En un problema de optimizaci´n, intentaremos buscar combinaciones de variables de decisi´n o o que generen un mejor valor de la funci´n objetivo, pero en la pr´ctica nuestro problema esta o a limitado por un gran n´mero de restricciones f´ u ısicas, econ´micas, t´cnicas, etc. Es por esto o e queen el planteamiento de nuestro problema debemos especificar que limitantes tienen los valores que puedan tomar las variables de decisi´n. En s´ o ıntesis, en esta parte debemos escribir matem´ticamente las limitaciones que nos impone la naturaleza del problema. a

IN34A: Optimizaci´n o

Pag. 2

1.3.

Planteamiento de funci´n objetivo. o

En general podemos decir que en un problema deoptimizaci´n se intenta encontrar el mejor o 2 valor de algo. Es por esto que necesitamos especificar que criterio usaremos para decir que una soluci´n es mejor que otra. Para ello deberemos especificar una funci´n de I n a I en que o o R R una combinaci´n de variables ser´ mejor que otra si genera un mayor valor de la funci´n en o a o el caso de maximizaci´n y un menor valor de la funci´n en el caso deminimizaci´n. Ejemplos o o o t´ ıpicos de funciones objetivos vienen dados por maximizaci´n de utilidades y minimizaci´n o o de costos, los que deben ser escritos en funci´n de las variables del problema. o En esta parte del curso, veremos un muy importante caso particular de problemas: problemas de programaci´n lineal (PPL) en que tanto las restricciones como la funci´n objetivo o o sonlineales3 . En esta clase introductoria veremos un subconjunto a´n mas reducido: solo u consideraremos variables continuas (mas adelante incluiremos variables discretas y binarias).

2.

Problemas

Partiremos con un par de problemas bien sencillos para que se entienda la idea y soltar un poco la mano.

2.1.

Problema 1

La oficina t´cnica coordinadora de cultivos (OTCC), tiene a su cargo la...