Optimizacion Avanzada

Karen Rodríguez 200715309
Andrés Flores 200711077
Juan Felipe García 200723603
11 de Febrero, 2011
Tarea1
-------------------------------------------------
Optimización Avanzada

Punto 1:
Introducción
Es claro que dado un problema de este tipo en la vida real, resultaría más eficiente cruzar el puente utilizando sentido común, antes de ponerse a resolverlo matemáticamente. Sinembargo, la idea es poder resolver este problema de manera general (para cualquier número de personas, y con cualquier capacidad), de tal forma que sirva como base para problemas más complejos que cumplan con características similares. Por ejemplo un comandante deba decir cómo enviar sus tropas a través de un océano dado que sus barcos tienen un cupo limitado y lo deba hacer en el menor tiempoposible.
Para resolver este problema se utilizará un modelo de optimización lineal. Esta formulación se describe detalladamente a continuación.
a)
Formulación matemática
* Conjuntos
P: Conjunto de los miembros de la familia que va a cruzar el puente, indexado con la letra p
P = {hijo, hija, mamá, papá, abuelo}
V: Conjunto de los viajes que se realizan para cruzar el puente, indexadocon la letra v
V = {1,2,…, numViajes} – Los índices impares representan viajes de ida, y los índices pares viajes de regreso
* Parámetros
tPersonasP- Tiempo que le toma cruzar el puente al miembro p de la familia
capacidad- Máxima cantidad de personas que pueden cruzar el puente a la vez

numViajes- El mínimo número de viajes necesarios para que la familia entera cruce elpuente. Esto es un parámetro ya que se calcula directamente del número de familiares (n) y la capacidad del puente (C). Éste cálculo se hace con la siguiente fórmula, la cual fue deducida intuitivamente:
numViajes= 2*n-2C-1+1
* Variables de decisión
Xpv- Variable binaria que toma el valor de 1 si la persona p , justo después del viaje v, se encuentra del lado IZQUIERDO del puente (ladoinicial), es decir, todavía debe cruzarlo. Toma el valor de 0 si está del lado DERECHO del puente (lado final).
Zpv- Variable binaria que toma el valor de 1 si la persona p cruza el puente en el viaje v. No tiene en cuenta si está yendo o si se está devolviendo, simplemente significa que lo está cruzando. Toma el valor de 0 si en este viaje no se mueve en lo absoluto.
tv- Variable auxiliar que indicael tiempo de cada viaje v. Esto tendrá en cuenta únicamente el tiempo que le toma cruzar al más lento. La suma de todos los tv, representará el tiempo total que le toma a la familia en cruzar el puente.

* Función Objetivo
min vϵVtv
Se busca minimizar el tiempo total que le toma a la familia cruzar el puente

* Restricciones
pϵPXp0=numPersonas
-Todos los miembros de la familiainician del lado IZQUIERDO del puente

pϵPXpk=0, donde k=numViajes
-Al final, todos los miembros de la familia deben quedar del lado DERECHO del puente

pϵPZpo=0
- En el viaje 0 (momento inicial) nadie puede estar cruzando el puente

pϵPZpv≤capacidad , ∀ vϵV
-En cada viaje, máximo puede cruzar un número de personas igual a la capacidad del puente

Zpv- Xpv-1+Xp v ≥ 0, ∀ pϵP, vϵV tal que v>0
-Si la persona p estaba en el lado IZQUIERDO y en este viaje NO se movió, no podrá quedar en el lado DERECHO

-Zpv- Xp v-1-Xp v+2 ≥ 0, ∀ pϵP, vϵV tal que v>0
- Si la persona p estaba en el lado IZQUIERDO y en este viaje SÍ se movió, no podrá quedar en el lado IZQUIERDO

Zpv+ Xp v-1-Xp v ≥ 0, ∀ pϵP, vϵV tal que v>0- Si la persona p estaba en el lado DERECHO y en este viaje NO se movió, no podrá quedar en el lado IZQUIERDO

-Zpv+ Xp v-1+Xp v ≥ 0, ∀ pϵP, vϵV tal que v>0
- Si la persona p estaba en el lado DERECHO y en este viaje SI se movió, no podrá quedar en el lado DERECHO

tv ≥ Zpv*tPersonasP, ∀ pϵP, vϵV tal que v>0
- Para cada viaje v, el tiempo de cada viaje...