Question 1:

Please solve this problem by branch and search also.

Question 2:

solve part a) by branch and bound and please provide the graph also

Question 3:

please formulate the above question as linear integer programming.

12.1-4. The board of directors of General Wheels Co. is considering six large capital investments. Each investment can be made only once. These investments differ in the estimated long-run profit (net present value) that they will generate as well as in the amount of capital required, as shown by the following table (in units of millions of dollars): The total amount of capital available for these investments is $100 million. Investment opportunities 1 and 2 are mutually exclusive, and so are 3 and 4 . Furthermore, neither 3 nor 4 can be undertaken unless one of the first two opportunities is undertaken. There are no such restrictions on investment opportunities 5 and 6 . The objective is to select the combination of capital investments that will maximize the total estimated long-run profit (net present value). (a) Formulate a BIP model for this problem. 12.3-5.* Northeastern Airlines is considering the purchase of new long-, medium-, and short-range jet passenger airplanes. The purchase price would be $67 million for each long-range plane, $50 million for each medium-range plane, and $35 million for each short-range plane. The board of directors has authorized a maximum commitment of $1.5 billion for these purchases. Regardless of which airplanes are purchased, air travel of all distances is expected to be sufficiently large that these planes would be utilized at essentially maximum capacity. It is estimated that the net annual profit (after capital recovery costs are subtracted) would be $4.2 million per long-range plane, \$3 million per medium-range plane, and $2.3 million per short-range plane. It is predicted that enough trained pilots will be available to the company to crew 30 new airplanes. If only short-range planes were purchased, the maintenance facilities would be able to handle 40 new planes. However, each medium-range plane is equivalent to 131 short-range planes, and each long-range plane is equivalent to 132 short-range planes in terms of their use of the maintenance facilities. The information given here was obtained by a preliminary analysis of the problem. A more detailed analysis will be conducted subsequently. However, using the preceding data as a first approximation, management wishes to know how many planes of each type should be purchased to maximize profit. (a) Formulate an IP model for this problem. C (b) Use the computer to solve this problem. (c) Use a binary representation of the variables to reformulate the IP model in part (a) as a BIP problem. 12.4-7. An increasing number of Americans are moving to a warmer climate when they retire. To take advantage of this trend, Sunny Skies Unlimited is undertaking a major real estate development project. The project is to develop a completely new retirement community (to be called Pilgrim Haven) that will cover several square miles. One of the decisions to be made is where to locate the two fire stations that have been allocated to the community. For planning purposes, Pilgrim Haven has been divided into five tracts, with no more than one fire station to be located in any given tract. Each station is to respond to all the fires that occur in the tract in which it is located as well as in the other tracts that are assigned to this station. Thus, the decisions to be made consist of (1) the tracts to receive a fire station and (2) the assignment of each of the other tracts to one of the fire stations. The objective is to minimize the overall average of the response times to fires. The following table gives the average response time to a fire in each tract (the columns) if that tract is served by a station in a given tract (the rows). The bottom row gives the forecasted average number of fires that will occur in each of the tracts per day. Formulate a BIP model for this problem. Identify any constraints that correspond to mutually exclusive alternatives or contingent decisions