1. You may use lp_solve program - a free-ware. You can download it from thefollowing web site: http://lpsolve.sourceforge.net/5.5/ 2. If you want to use some other lp solver that is fine. 3. Solve the following problem and write a report: a. What tool you are using (eg. lp_solve) ? b. features of the tool you are using (as for as lp program solving is concerned). c. The number of nodes for the following program should be at least 10. d. The number of edges should be at least 20. e. Assign some capacity to eache edge. f. Assign a unit cost for capacity. g. assign unit profit. Hint: Formulate it first as optimizing the ratio of two linear functions under linear constraints. This is still not an LP, since the objective function is a fraction. Then convert it into an LP in two steps, using the following idea. * A telecommunications company sets up routes through its network to servecertain source-destination (S-D) pairs of traffic. We want to assign bandwidth to each route, under the following conditions: The routes are fixed and known in advance, each route goes through a known set of links. (These sets can possibly overlap, as the routes may share links.) Each link has a known available capacity, which cannot be exceeded by the routes that use the link, in the sense that the sum of the route bandwidths on the link cannot be more than the link capacity. Assigning bandwidth to a route has a cost. This cost is proportional to the bandwidth assigned. The cost of unit bandwidth is known for each route (may be different for different routes). Each route generates a profit, due to the traffic it carries. The profit of each route is proportional to the bandwidth assigned to the route. The profit generated by unit bandwidth is known for each route (may be different for different routes). Under the above conditions, the company wants to decide how much bandwidth to assign to each route. The goal is that the ratio of the total profit vs. the total cost is maximized. In other words, they want to maximize the yield of the bandwidthinvestment in the sense that it brings the highest profit percentage. Formulate thisoptimization problem as a linear
View Full Document
Unlocking...