Study Guides
(238,252)

Canada
(115,037)

University of Waterloo
(5,555)

CO 250
(11)

Christine Dupont
(5)

# CO327W13_a2_soln.pdf

Unlock Document

University of Waterloo

Combinatorics and Optimization

CO 250

Christine Dupont

Winter

Description

Assignment 2
Due: Wednesday February 6 at the BEGINNING of class
1. Example of a Multiperiod Problem: Investing
A person has $20,000 and plans to invest it over the next 3 years. Their ▯nancial advi-
sor has suggested three investments to invest in. Each investment can be purchased for
any amount at the beginning of the year and is locked in for one year. The company
the advisor works for has projections for the next 3 years on the rate of return for each
investment. The advisor has also ▯gured out some minimum/maximum levels to invest
in each investment based on the person’s goals and adversion to risk. At the end of
each year, the person can change what they invest in.
investment percent return after one year Investment Range
year 1 year 2 year 3
1 4% 5% 6% 9,000-14,000
2 8% 9% 9% 7,000-15,000
3 12% 9% 10% 2,000-5,000
(Note: There is no guarantee that all the money from one year is invested the next
year.)
(a) Write a linear program to maximize how much the person is expected to have
after 3 years of investing.
Solution:
▯ Decision Variables
Let x ij▯ 0 be a variable representing the amount to invest on investment i
at the beginning of year j.
For convenience (and for part (b) ), let y ▯ 0 denote the amount of money
j
there is at the end of year j.
▯ Objective Function
To maximize the amount the person has after year 3, we want:
maximize y
3
▯ Constraints
The amount invested in each investment should be in the investment range
at the beginning of each year.
9000 ▯ x 1j▯ 14000 for j 2 f1;2;3g for investment 1
7000 ▯ x 2j▯ 15000 for j 2 f1;2;3g for investment 2
2000 ▯ x3j▯ 5000 for j 2 f1;2;3g for investment 3 The person can only invest at the beginning of year i what they have at the
end of the year i ▯ 1. At the start of year 1, the person invests $20,000.
x + x + x ▯ 20000
11 21 31
x 12+ x 22+ x 32 ▯ y 1
x 13+ x 23+ x 33 ▯ y 2
Since there is no guarantee that all the money at the end of one year is
invested at the beginning of next year, we need an expression for the amount
of money at the end of year j, y j in terms of how much money is left at the
end of year j ▯ 1, yj▯i, and how much is made from investments.
y = 20000 + 0:04x + 0:08x + 0:12x
1 11 21 31
y = y + 0:05x + 0:09x + 0:09x
2 1 12 22 32
y3 = y +20:06x 13+ 0:09x 23+ 0:1x 33
The resulting LP is:
maximize y3
subject to x1j ▯ 9000 for j 2 f1;2;3g
x ▯ 14000 for j 2 f1;2;3g
1j
x2j ▯ 7000 for j 2 f1;2;3g
x2j ▯ 15000 for j 2 f1;2;3g
x3j ▯ 2000 for j 2 f1;2;3g
x3j ▯ 5000 for j 2 f1;2;3g
x11+ x 21+ x 31 ▯ 20000
x12+ x 22+ x 32 ▯ y 1
x + x + x ▯ y
13 23 33 2
20000 + 0:04x + 0:08x + 0:12x = y
11 21 31 1
y1+ 0:05x 12+ 0:09x 22+ 0:09x 32 = y 2
y2+ 0:06x 13+ 0:09x 23+ 0:1x 33 = y 3
xij ▯ 0 for i;j 2 f1;2;3g
yj ▯ 0 for i;j 2 f1;2;3g (b) Solve the linear program from part (a) using AMPL. Your solution should in-
clude a prinout of your .mod ▯le that is properly documented to explain your
variables/constraints/what your model is doing, a printout of your .dat ▯le, and
the ▯nal solution including how much the person is expected to have after every
year and how much was invested in each investment every year.
Solution:
See the a2q1.mod and a2q1.dat ▯les on LEARN.
After year 1, the person will have $21,400.
After year 2, the person will have $22,966.
After year 3, the person will have $24,812.94.
How the person should invest their money at the beginning of each year is given
by the following table:
Amount to invest in
Investment year 1 year 2 year 3
1 9,000 9,000 9,000
2 7,000 10,400 8,966
3 4,000 2,000 5,000
2. Give an example of a linear program in two variables (x an1 x ) wh2re there is more
than one optimal solution. Prove your result is correct by drawing the feasible region
on the x 1 2plane and giving a geometric argument.
Solution:
Consider the LP:
maximize x1+ x 2
subject to x1+ x 2 ▯ 4
x1;x 2 ▯ 0
If you draw the feasible region and lines of the form x1+x =2d for di▯erent constants
d, you will see that one of the boundaries of the region is parallel to lines representing
the objective function at di▯erent values d. The line x + x1= d 2hat touches the
region and has the highest d is when d = 4. But x + x =14 is2a boundary of the
region. Thus, all the points on x 1 x =24 where x ;x 1 0 2re optimal solutions. 3. Write an infeasible linear program whose dual linear program is also infeasible. Brie
y
explain why both linear programs are infeasible. (Hint: You will need at least two
variables.)
Solution:
Consider the primal LP:
maximize x 1
subject to x1+ x 2 = 3
x1+ x 2 = 2
Note that we can never satisfy both constraints so the LP is infeasible.
The dual LP is:
minimize 3y1+ 2y 2
subject to y 1 y 2 = 1
y + y = 0
1 2
Note that we can never satisfy both constraints so the dual LP is infeasible.
4. Consider the following linear program:
minimize 3x ▯ 2x ▯ 6x
1 2 4
subject to x 2 4x 3 2x 4 ▯ ▯3

More
Less
Related notes for CO 250