Upgrading a highway system in a developing country. The highway system in many developing...

Upgrading a highway system in a developing country. The highway system in many developing countries may be a tree-shaped structure onlv. By tree Vie mean a network with no loops, or one in which only one route exists between any two cities of the network. We begin by assuming that such a tree network connects the major cities in such a couutrv. The highway are currently in vcty poor condition. bur a modes deposit of oil has been discovered offshore and a highwav upgrading is desired.

The Transuort Miuistr, has been allotted B units of money for highway improvement and wishes to spend it in a way that connect the maximum population with the improved highway system, which radiates out from the coasted city at point P. The population is assumed to be concentrated at the junction points of the tree network Eacn link j that is improved connects a new increment of population aj to the system. For ther. no link can be conxnucted unless the link that irmuediatcly proceeds it en route to the coastal at P is also built.

Structure the problem as a zero one programming problem with the object of achieving the largest possible population on the continuous improved network Subject to a budget constraint. By continuous network, we mean that no gaps are allowed in which an improved highway exists on one link and unimproved highway on an adjacent link and then improved highway on the other side of the unimprovedlink. Use the diagram to guide your constraints.

Let Cj = costs 0[" link j, and

aj = the population connected when link j is built (the population at the tip of link j).