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.

Answer 1

Maximize \(Z = 17x_1 + 10x_2 + 15x_3 + 19x_4 + 7x_5 + 13x_6 + 9x_7\) subject to constraints, where \(x_i\) is a binary variable indicating investment decisions.

To formulate this problem as an integer programming model, let's define decision variables, constraints, and the objective function.

Decision Variables: Let \(x_i\) be a binary variable representing whether to invest in opportunity \(i\) or not. Each \(x_i\) takes a value of 1 if the investment is selected and 0 otherwise.

Objective Function: Maximize the total estimated long-run profit (net present value):

\[ \text{Maximize} \quad Z = 17x_1 + 10x_2 + 15x_3 + 19x_4 + 7x_5 + 13x_6 + 9x_7 \]

Constraints: 1. The total amount of capital available is $100 million:

\[ 43x_1 + 28x_2 + 34x_3 + 48x_4 + 17x_5 + 32x_6 + 23x_7 \leq 100 \]

2. Investment opportunities 1 and 2 are mutually exclusive: \[ x_1 + x_2 \leq 1 \]

3. Investment opportunities 3 and 4 are mutually exclusive: \[ x_3 + x_4 \leq 1 \]

4. Opportunity 5 can be undertaken only if both 1 and 3 are taken: \[ x_5 \leq x_1 + x_3 \]

5. Opportunity 7 has to be chosen if both 2 and 4 are selected: \[ x_7 \geq x_2 + x_4 - 1 \]

6. Opportunity 7 cannot be invested unless at least one of 5 and 6 is invested: \[ x_7 \leq x_5 + x_6 \]

Integer Constraints: \[ x_i \in \{0, 1\} \quad \text{for} \quad i = 1, 2, 3, 4, 5, 6, 7 \]

This formulation represents the integer programming model for selecting the combination of capital investments that maximizes the total estimated long-run profit while considering the specified constraints.