1 Consider the problem max fx st Axb gx 0 OR hx 0 or both x

1) Consider the problem

max f(x)

s.t. Ax=b

      g(x) 0   OR   h(x) 0 (or both)

      x 0

where f(x), g(x), and h(x) are linear functions. Explain why the \"OR\" dichotomy can replaced by the following without changing the feasible set:

g(x) m

h(x) p (1 - )

= 0,1

(Here, m and p are lower bounds (possible negative) for the two functions:

g(x) m , h(x) p       for all feasible x. )

Hence, the problem can be converted to a mixed integer program.

2) Generalize problem 1.

max f(x)

s.t. Ax=b

x 0

And, at least k of the following m constraints must be satisfied. (In problem 1, at least one of the two constraints had to be satisfied)

(Replace the k-fold alternatives with a set of linear inequalities involving binary variables.)

3) A firm has 5 projects that it would like to undertake but, because of budget limitations, not all can be selected. Selection of a project means a commitment of investing a certain number of dollars for each of the following 3 years, as indicated below. (No \"partial projects\" are allowed. The company either pays the entire amount for all three years, or it does not select that project at all.) The table also gives the present value for each of the 5 potential projects. (Units of money are hundreds of thousands of dollars)

Project Number                 Required investment for            Present value  

                                        year 1       year 2     year 3

        1                                2                4             1                       15

        2                                3                1             2                       12

        3                                1                2             1                       10

        4                                2                1             3                       13

        5                                2                2             1                       14

The amounts of money available in years 1,2, and 3 will be 7, 8, and 6, respectively. Express, as an integer programming problem with binary variables, the problem of deciding which projects to select in order to maximize the total present value.

Solution

Problem 3:

Capital budgeting:

Let, X_j = 1 if the project j is selected otherwise 0 if rejecteed

j = 1, 2, 3, 4, and 5

Objective Function:

The objective of the capital budgeting problem is to maximize the total net present of the project portfolio.

Max Z = 15X₁ + 12X₂ + 10X₃ + 13X₄ + 14X₅

Subject to:

First year budget constraint: 2X₁ + 3X₂ + 1X₃ + 2X₄ + 2X₅ <= 7

Second year budget constraint: 4X₁ + 1X₂ + 2X₃ + 1X₄ + 2X₅ <= 8

Third year budget constraint: 1X₁ + 2X₂ + 1X₃ + 3X₄ + 1X₅ <= 6