Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to learn more about the Berlin Airlift transport problem. Two links I could find are here:

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

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

Problem statement is as follows:

On June 24, 1948, the former Soviet Union blocked all land and water routes through East Germany to Berlin. A gigantic airlift was organized using American and British planes to supply food, clothing and other supplies to more than 2 million people in West Berlin. The cargo capacity was 30,000 cubic feet for an American plane and 20,000 cubic feet for a British plane. To break the Soviet blockade, the Western Allies had to maximize cargo capacity, but were subject to the following restrictions: No more than 44 planes could be used. The larger American planes required 16 personnel per flight; double that of the requirement for the British planes. The total number of personnel available could not exceed 512. The cost of an American flight was \$9000 and the cost of a British flight was \$5000. The total weekly costs could note exceed \$300,000. Find the number of American and British planes that were used to maximize cargo capacity.

Based on this the author has

$x+y \le 44$

$16x + 8y \le 512$

$9000x + 5000y \le 300000$

The cost function was not given [see @joriki's answer for the correct cost]. My questions are, problem says planes cannot exceed 44, but the problem doesn't state the connection between flights and planes. There are 44 planes, right, but can I use all 44 in one day? In a week?

In a related request, if anyone has the complete definition of this problem, it would be much appreciated.

Also the numeric solution would be great, so I can replicate it.

Addition:

Using the Python LP code:

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

I call it as:

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

I receive 20 and 23 as results.

Thanks,

share|improve this question

2 Answers 2

up vote 4 down vote accepted

A cost function usually specifies a quantity to be minimized. In the present case, you're trying to maximize the cargo capacity. A more general term for a function to be optimized (minimized or maximized) is "objective function". If you want to use an optimization algorithm or package that expects a cost function to be minimized, you can let it minimize the negative of the function to be maximized. In the present case, the cargo capacity to be maximized is $30000x+20000y$, so you could use $-30000x-20000y$, or equivalently $-3x-2y$ as a cost function.

Regarding planes and flights, the problem statement is a bit vague in that respect: It constrains the "total weekly costs", but it doesn't specify the time period over which "no more than 44 planes could be used". From the inequalities you cite, it seems that "weekly" is irrelevant and all the restrictions given are intended to apply to some common time period; otherwise the inequalities shouldn't all be using the same variables $x$ and $y$ without any time factors.

share|improve this answer

The problem has already been analyzed by @joriki. You can get a numerical solution by trying an online Simplex solver. Just google for it. I tried the first one that I found: Simplex Method Tool and got for the maximal capacity c:

enter image description here

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.