YOU ARE TRANSPORTING MANGOES BY AIRCRAFT FROM MANILA TO SINGAPORE....

2. You are transporting mangoes by aircraft from Manila to Singapore. There are 12

planes available with the following weight capacities: 2, 2, 3, 3, 4, 7, 8, 8, 10, 10,

11 and 13 tons. Since no two planes may be assigned to the same route, then you

may direct each plane to one of the following 12 routes:

Bangkok–Singapore Hong Kong–Kuala Lumpur

Hong Kong–Singapore Jakarta–Singapore

Kuala Lumpur–Bangkok Kuala Lumpur–Singapore

Manila–Hong Kong Manila–Jakarta

Manila–Kuala Lumpur Manila–Taipei

Taipei–Bangkok Taipei–Hong Kong

What is the maximum number of tons of mangoes you can ship from Manila to

Singapore?

【Solution】

The chart below shows that it is possible to ship 35 tons (5 points) of mangoes from

Manila to Singapore. (5 points)

Route Capacity Shipment

Bangkok–Singapore 4 4

Hong Kong–Kuala Lumpur 2 1

Hong Kong–Singapore 13 13

Jakarta–Singapore 8 8

Kuala Lumpur–Singapore 10 10

Kuala Lumpur–Bangkok 2 1

Manila–Kuala Lumpur 10 10

Manila–Taipei 7 6

Manila–Hong Kong 11 11

Manila–Jakarta 8 8

Taipei–Hong Kong 3 3

Taipei–Bangkok 3 3

It is not possible to ship more than 35 tons of mangoes from Manila to Singapore.

Note that there are four routes leading from Manila and four other routes leading into

Singapore. The highest capacities that can be assigned to these eight routes are 13, 11,