Proyecto de programación lineal: The Truman Show

Este proyecto requiere conocimientos de programación lineal y algoritmos de optimización combinatoria, incluidos Branch & Bound.

proyecto programación lineal optimización combinatoria ramificar y acotar

“Nos aburrimos de ver a los actores darnos emociones falsas. Estamos cansados de la pirotecnia y los efectos especiales. Si bien el mundo en el que habita es, en algunos aspectos, falso, el propio Truman no tiene nada de falso. Sin guiones, sin tarjetas de referencia. No siempre es Shakespeare, pero es genuino. Es una vida. "

Inicio del proyecto

Proyecto de programación lineal: la programación lineal de Truman Show

La televisión de realidad genera miles de millones de euros al año. Pero para marcar la diferencia, siempre tienes que atreverte a más. Como recién graduado de la famosa escuela de cine y audiovisuales Herr Guerard's Blinded Academy, debes ingresar a la profesión lo más rápido posible.

Así es como se le ocurrió la idea de hacer realidad The Truman Show. No hay escasez de pueblos fantasmas, pero tu presupuesto es limitado y tienes que rascar el dinero donde puedas. Para no perder ni una gota de tu reality show, debes recorrer la ciudad con tu cámara. La construcción de este último varía enormemente de un punto a otro. Afortunadamente, recordará las lecciones del eminente profesor Guerard sobre problemas de enteros lineales (ILP).

" A cobertura máxima Dónde transverso de uno grafico GRAMO es un conjunto VS de vértices de modo que cada borde de GRAMO = (V, mi) es incidente en al menos un vértice de VSv ∈ S {\ Displaystyle v \ in S}. "

Concretamente, esto equivale al siguiente ejemplo: Hay 6 carriles para controlar y el número mínimo de cámaras de 360 ° debe colocarse de manera que cada carril sea visto por al menos una cámara. El número mínimo es 2 y las dos cámaras forman una cobertura de los vértices.

proyecto programación lineal optimización combinatoria ramificar y acotar

El problema está escrito de la siguiente manera:

proyecto programación lineal optimización combinatoria ramificar y acotar

Con CV) el costo de instalar la cámara en la parte superior v. Xv vale 1 si construimos una cámara en la parte superior v, de lo contrario es 0. Para cada borde (u, v), establecemos la siguiente restricción Xtu+ xv menos que 1.

proyecto programación lineal optimización combinatoria ramificar y acotar

Las intersecciones y los ángulos rectos son vértices, la carretera entre dos vértices es un borde. Una rotonda cuenta como una sola cumbre. Solo las carreteras son crestas (no estacionamientos, carriles de un solo sentido o carreteras sin marcar). El costo de las cámaras es igual al número de líneas de las líneas de demarcación de las carreteras adyacentes (hasta los siguientes vértices).

Clasificación

  1. Construye el gráfico correspondiente (2 puntos)
  2. Haciendo el ILP (3 puntos)
  3. Encontrar un solución básica (5 puntos)
  4. Desenrollar el algoritmo Branch & Bound (10 puntos)

Tiene derecho a utilizar cualquier simplex para resolver el PL.