Question

The board of directors of General Wheels Co. is considering seven 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.

Investment opportunity	Estimated profit ($million)	Capital required ($million)
1	$17	$43
2	$10	$28
3	$15	$34
4	$19	$48
5	$7	$17
6	$13	$32
7	$9	$23

The total amount of capital available for these investments is $100 million. Investment opportunities 1 and 2 are mutually exclusive (i.e., they cannot be chosen simultaneously), and so are 3 and 4. Furthermore, 5 can be undertaken only if both 1 and 3 are taken. Opportunity 7 has to be chosen if both 2 and 4 are selected, and Opportunity 7 cannot be invested unless at least one of 5 and 6 is invested. The objective is to select the combination of capital investments that will maximize the total estimated long-run profit (net present value). Formulate this problem as an integer programming model.

Decision variables (1 mark):

Objective function (1 mark):

Constraints (7 mark):

Answer 1

Answer: We will formulate the given problem as an integer programming model as mentioned below:

Decision Variable:

Let Decision Variables:

X1 = 1 If Investment Opportunity 1 is selected, 0 otherwise,

X2 = 1 If Investment Opportunity 2 is selected, 0 otherwise,

X3 = 1 If Investment Opportunity 3 is selected, 0 otherwise,

X4 = 1 If Investment Opportunity 4 is selected, 0 otherwise,

X5 = 1 If Investment Opportunity 5 is selected, 0 otherwise,

X6 = 1 If Investment Opportunity 6 is selected, 0 otherwise, and

X7 = 1 If Investment Opportunity 7 is selected, 0 otherwise.

Objective Function:

Here, an objective is to maximize the total estimated long-run profit. Hence, the objective function:

Maximize Z = 17 X1 + 10 X2 + 15 X3 + 19 X4 + 7 X5 + 13 X6 + 9 X7

Subject to Constraints:

C1 = 43 X1 + 28 X2 + 34 X3 + 48 X4 + 17 X5 + 32 X6 + 23 X7 ≤100 (Total Amount of Capital Available)

C2 = X1 + X2 = 1 (Opportunities 1 and 2 can not be chosen symultanously)

C3 = X3 + X4 = 1 (Opportunities 3 and 4 can not be chosen symultanously)

C(4-a) = 2 X5 X1 + X3 (Opportunity 5 can be taken only if Opportunites 1 and 3 both are under taken), or

C(4-b) = X5 X1 + X3 - 1 (Opportunity 5 can be taken only if Opportunites 1 and 3 both are under taken)

C(5-a) = X2 + X4 2 X7 (Opportunity 7 has to be chosen if, Opportunites 2 and 4 both are under taken), or

C(5-b) = X2 + X4 - 1 X7 (Opportunity 7 has to be chosen if, Opportunites 2 and 4 both are under taken)

C6 = X7 X5 + X6 (Opportunity 7 can not be chosen unless at least one of Opportunity 5 and 6 is chosen)

Where X1, X2, X3, X4, X5, X6, X7 ∈ {0, 1}