Problema de optimización lineal de puente aéreo de Berlín

Question

Estoy tratando de aprender más sobre el puente aéreo de Berlín problema de transporte. Dos enlaces que he podido encontrar están aquí:

http://drmohdzamani.com/notes/file/Simplex%20Method.pdf

http://www.cabrillo.edu/~mladdon/math13/LP%20Dantzig%20Berlin%20Problem.pdf

Declaración del problema es como sigue:

El 24 de junio de 1948, la Unión Soviética bloqueó todas las tierras y el agua de las rutas a través de la Alemania Oriental a Berlín. Un gigantesco puente aéreo fue organizado a través de Estadounidenses y Británicos aviones para el suministro de alimentos, ropa y otros suministros para más de 2 millones de personas en el Oeste de Berlín. La capacidad de carga era de 30.000 pies cúbicos para un avión de American y 20.000 pies cúbicos para un avión Británico. A romper el bloqueo Soviético, los Aliados Occidentales habían maximizar la carga capacidad, pero estaban sujetos a las siguientes restricciones: No más de 44 los aviones podrían ser utilizados. El más grande de América aviones de 16 de personal por el vuelo; el doble que el de la exigencia de los aviones Británicos. El total de número de personal disponible no podría superar los 512. El costo de un Vuelo de American fue \$9000 and the cost of a British flight was \$5000. El semanal total de los costos de nota exceder \$300,000. Encontrar el número de Estadounidenses y Británicos aviones que fueron utilizados para maximizar la capacidad de carga.

Sobre esta base, el autor ha

$x+y \le 44$

$16x + 8y \le 512$

$9000x + 5000y \le 300000$

La función de costo no fue dada [ver @joriki la respuesta para el costo correcto]. Mis preguntas son, el problema dice que los aviones no pueden exceder de 44, pero el problema no es el estado de la conexión entre vuelos y aviones. Hay 44 aviones, a la derecha, pero ¿puedo usar todos los 44 en un día? En una semana?

En relación con esta petición, si alguien tiene la definición completa de este problema, sería muy apreciado.

También el valor numérico de la solución sería genial, así que me puede replicar.

Además:

El uso de Python LP código:

http://projects.scipy.org/scipy/attachment/ticket/1252/lp.py

Yo lo llamo como:

import numpy as np
import lp

A = np.array([[1., 1.],[16., 8.],[9000., 5000.]])
b = np.array([44., 512., 300000.])
c = np.array([30000., 20000.])
optx,zmin,is_bounded,sol,basis = lp.lp(c,A,b)
print zmin
print optx

Voy a recibir el 20 y 23 de resultados.

Gracias,

Answer 1

Una función de costo por lo general se especifica una cantidad que se reduce al mínimo. En el presente caso, usted está tratando de maximizar la capacidad de carga. Un término más general de una función a optimizar (minimizar o maximizar) es la "función objetivo". Si desea utilizar un algoritmo de optimización o paquete que se espera de una función de costo que se reduce al mínimo, usted puede dejar de minimizar el negativo de la función a maximizar. En el presente caso, la capacidad de carga para maximizar el es $30000x+20000y$, por lo que puede utilizar $-30000x-20000y$, o, equivalentemente, $-3x-2y$ como una función de coste.

Con respecto a los aviones y los vuelos, el enunciado del problema es un poco vago en ese sentido: Se restringe el "total de gastos semanales", pero no especifica el período de tiempo durante el que "no más de 44 aviones podrían ser utilizados". A partir de las desigualdades que mencionas, parece que "semanal" es irrelevante y todas las restricciones dadas están destinadas a aplicarse a algún período de tiempo común; de lo contrario, las desigualdades no debería ser todos con las mismas variables $x$ $y$ sin factores de tiempo.

Answer 2

El problema ya ha sido analizado por @joriki. Puede obtener una solución numérica por tratar de un solver simple en línea. Buscalo en google para él. Probé el primero de ellos que he encontrado: Herramienta método Simplex y de la c: capacidad máxima