Clase 1 modelamiento matemático

Clase N◦ 1
27 de Julio 2009

1.

Problemas de Optimización Lineal y Entera

Estudiaremos problemas de programación lineal, esto es, el problema de minimizar (maximizar) una función de costo (beneficio) lineal, sujeto a restricciones lineales de igualdad o desigualdad. Estos problemas son de la forma: m´n c · x + h · y ı st. A · x + G · y ≤ b n x ∈ Z+ y ∈ Rn A continuación revisaremosalgunos modelos lineales y lineales enteros clásicos de optimización.

1.1.

0-1 Knapsack Problem

Suponga que se tienen n proyectos. El proyecto j tiene un costo asociado a j y de realizarse, aportaría un beneficio de c j . Se debe decidir que proyectos realizar con el fin de maximizar el beneficio, considerando un presupuesto de b, y que los proyectos no pueden ser realizados en forma parcial.Variable de decisión xj = El problema a resolver: m´ x ∑n c j · x j a j=1 st. ∑n a j · x j ≤ b j=1 x j ∈ {0, 1}n 1 Si se realiza el proyecto j 0 ∼

1.2.

Assignment Problems

Matching bi-partito: Considere el problema se asignación en que se tienen m trabajos y n personas y se deben asignar los trabajos a las personas (m ≤ n). Cada trabajo debe ser asignado a una persona, y cada persona puedetrabajar a lo más en un trabajo. El costo de asignar trabajo j al trabajador i es ci j . Se quiere buscar la asignación de todos los trabajos a costo mínimo. Variables: xi j = 1 Si se asigna trabajo j al trabajor i. 0 ∼

Restricciones: − Cada persona realiza a lo más un sólo trabajo.
m j=1

∑ xi j ≤ 1
n

∀i

− Cada trabajo es realizado por una persona.

i=1

∑ xi j = 1

∀j

−Naturaleza de las variables. xi j ∈ {0, 1} ∀i, j Función Objetivo:
n,m

m´n ı

∑ ci j · xi j
i, j

Matching Perfecto: Se tienen 2n trabajadores, y se deben formar n parejas de trabajo, maximizando el beneficio global (de la empresa). Considerando ci j el beneficio de que el trabajador i sea equipo con el trabajador j. Variables: xi j = 1 Si se asigna trabajo j al trabajor i. 0 ∼Restricciones: − Trabajador 1 tiene una pareja asociada.
2n j=2

∑ x1 j = 1

− Cada trabajo es realizado por una persona.
i−1 k=1 2n

∑ xki + ∑

xi j = 1 ∀i = 2, ..., 2n − 1

j=i+1

− Trabajador 2n tiene una pareja asociada.
2n−1

∑
k=1

xk,2n = 1

− Naturaleza de las variables. xi j ∈ {0, 1} ∀i = 1, ..., 2n − 1 Función Objetivo:
2n−1 2n

j = 2, ..., 2n

m´ x a

i=1 j=i+1

∑ ∑ci j · xi j

1.3.

Set Covering, Set Packing, Set Partitioning

Consideremos un conjunto base M = {1, . . . , m}, y poseemos una serie de sub-conjuntos {M j }n , M j ⊆ M . j=1 Decimos que J ⊆ {1, . . . , n} covering M si
i∈J

Mi = M .
∀i, j ∈ J.

/ Decimos que J ⊆ {1, . . . , n} es un packing en M si Mi ∩ M j = 0

Decimos que J ⊆ {1, . . . , n} es una partición en M si es uncovering y un packing a la vez. Para describir todos los posibles J, basta definir: ai j : 1 si i ∈ M j , 0 en caso contrario. x j : 1 si j ∈ J, 0 en caso contrario.

Luego, considerando x ∈ {0, 1}n J será covering ssi Ax ≥ 1 J será packing ssi Ax ≤ 1 J será partition ssi Ax = 1 con 1, un vector de 1’s de dimensión m. Ejemplo: Localización de Estaciones de Bomberos. Definimos los siguientes parámetros,suponiendo que las localizaciones de clientes han sido discretizadas (ej:en cuadras): N = {1, ..., n}: Posibles localizaciones para las estaciones de bomberos. M = {1, ..., m}: Localización de comunidades. c j : Costo de instalar una estación en j. Podemos definir además:

M j : Conjunto de comunidades que pueden ser atendidas desde j en menos de 10
min. ai j : Si la comunidad i puede seratentida por la estación ubicada en j en menos de 10 min, 0 en caso contrario (Notar que ésta podría ser una variable de decisión en otro problema). Variables: xi j = 1 Si se ubica la estación de bomberos en la localización j. 0 ∼

Restricciones: − Toda comunidad debe ser atentida al menos por una estación.
n j=1

∑ ai j x j ≥ 1

∀i ∈ M j

− Naturaleza de las variables. x j ∈ {0, 1} ∀ j...