The tourism department of a certain country would like to decide which projects to fund during the coming year. The projects were divided into three main categories: religious, historical, and construction (hotels, roads, nightclubs, and so on). Three proposals A, B, and C for restoring religious sites have been submitted with estimated costs of $5, 57, and $3 million, respectively. Four proposals D, E, F, and G for the restoration of historical sites have been submitted with estimated costs of $15, $12, S5, and $7 million. Finally, five proposals H, I, J, K, and L for constructing new facilities have been submitted. These cost $2, $15, $22, $8, and $10 million, respectively. In order to determine the relative priority of these projects, experts from the tourism department have developed a scoring model with the following scores for proposals A, B, C, D, E, F, G, H, E, J, K, and L: 5, 6, 2, 8, 11, 1, 7, 2, 10, 9, 5, and 4, respectively. The department has decided that at least one project from each category must be funded. Projects E and F represent a continuation of a plan that started during the previous year, and at least one of them must be funded. Furthermore, at most two historical and three construction projects can be chosen. Which project should the tourism department fund in order to maximize the total score and not to exceed $80 million? (Hint: Project j is chosen if xj = 1 and is not chosen if X; = 0). (a) Formulate the problem as an LP and solve the model using either LINDO, LINGO, EXCEL Solver, or CPLEX. Hint: unit upper bounds on some decision variables may be needed.
(b) Formulate the problem as a 0-1 linear integer program by replacing the bounded variables by binary variables. Solve the model using the same LP solver you chose in part (a).
(c) Compare the two solutions and provide some relevant conclusions.