maximal-flow-0

se Problem

T HE B ATTLE OF THE B ULGE

On December 16, 1944, in the last year of World War II, two German panzer armies, supported by a third army of infantry, together totaling more than 250,000 men, staged a massive counteroffensive in northern France, overwhelming the American First Army in the Ardennes. The offensive emanated from the German defensive line along the Our River, north of the city of Luxembourg, and was directed almost due west toward Namur and Li ge in Belgium. The result, after several days of fighting, was a huge “bulge” in the Allied line and, therefore, this last major ground battle of World War II became known as the Battle of the Bulge.

On December 20, General Dwight D. Eisenhower, Supreme Allied Commander, called on General George Patton to attack the German offensive with his Third Army, which was then situated near Verdun, approximately 100 miles due south of the German left flank. Patton’s immediate objective was to relieve the 101st Airborne and elements of Patton’s own 9th and 10th Armored Divisions surrounded at Bastogne. Within 48 hours, on December 22, Patton was able to begin his counteroffensive, with three divisions totaling approximately 62,000 men.

The winter weather was cold with snow and fog, and the roads were icy, making the movement of troops, tanks, supplies , and equipment a logistical nightmare. Nevertheless, on December 26 Bastogne was relieved, and on January 12, 1945, the Battle of the Bulge effectively ended in one of the great Allied victories of the war.

General Patton’s staff did not have knowledge of the maximal flow technique nor access to computers to help plan the Third Army’s troop movements during the Battle of the Bulge. However, the following figure shows the road network between Verdun and Bastogne, with (imagined) troop capacities (in thousands) along each road branch between towns. Using the maximal flow technique (and your imagination ), determine the number of troops that should be sent along each road in order to get the maximum number of troops to Bastogne. Also indicate the total number of troops that would be able to get to Bastogne.

[Page 318]