MA569 Summer I: Homework #5
1. Consider the following integer program:
objective Max 2x +5y
Subjective 2x +3y ≤ 15;
x +3y ≤ 10
x , y ≥ 0;
x , y ∈Z
(a) Sketch graph of the region. Determine the coordinates of the vertices for the correspond-
ing linear program (including vertices with non-integer coordinates).
(b) What is the optimal solution and optimal objective value to the linear program where the
variables are not required to be integers?
(c) List all of the integer-valued points that occur in the feasible region.
(d) What is the optimal solution and optimal objective value for the integer program?
1
2. A company manufactures three products whose daily labor and raw material requirements are
given in the following table:
Product Required daily labor (hr/unit) Required daily raw material (lb/unit)
1 4 3
2 3 4
3 5 6
The profits per unit of the three products are $25, $30, $22, respectively. The company has two
locations for locating its plant. The two locations differ primarily in their availability of labor
and raw material, as shown in the following table:
Location Available daily labor (hr) Available daily raw material (lb)
1 90 120
2 100 100
(a) Formulate an integer program to determine where they should locate the plant and how
much of each product they should produce in order to maximize their profit.
(b) Use Excel to solve the integer program. Where should they locate the plant? How much
of each product should they produce?
2
3. Consider the following BIP:
Max Z = 3x1 +3x2 +5x3−2x4− x5
Subject to x1 +2x2−3x4− x5 ≤ 0
−3x1 +6x2−7x3 +9x4 +9x5 ≥ 10
x1, x2, x3, x4, x5 ∈{0, 1}.
Use the BIP branch-and-bound algorithm to solve this BIP. You can use Excel to solve the LP’s
that occur during the algorithm. Show that branching tree that results when you perform the
algorithm, and clearly label the vertices of the tree with the solution to the corresponding LP
and the resulting bound for Z .
3
4. Consider the following MIP:
Min Z = 5x1 +2x2 + x3 +2x4 +3x5
Subjective x2−5x3 + x4 +2x5 ≥−1
5x1− x2 + x5 ≥ 8
x1 + x2 +6x3 + x4 ≥ 5
x1, x2, x3, x4, x5 ∈Z+ ∪{0}.
Use the MIP branch-and-bound algorithm to solve this MIP. You can use Excel to solve the LP’s
that occur during the algorithm. Show the branching tree that results when you perform the
algorithm, and clearly label the vertices of the tree with the solution to the corresponding LP
and the resulting bound for Z .
4
5. Consider the following integer program:
Max Z = 100x1 +220x2 +50x3 +15x4 +17x5 +12x6 +4x7
Subjective 50x1 +30x2 +80x3 +9x4 +16x5 +5x6 +10x7 ≤ 800;
x1, x2, x3 ∈ {0, 1};
x4, x5, x6, x7 ∈ Z+ ∪{0}∩ [0, 200].
For each of the parts below, explain how to modify the integer program, so that the given con-
dition is also satisfied. Each of the parts in independent, so that no part depends on the parts
preceding it.
(a) Modify the integer program so that at least two of the following constraints are satisfied:
x4 ≥ 50; x5 ≤ 25; x6 + x7 ≤ 100.
(b) Modify the integer program so that x5 equals 9, 15, or 20.
(c) Modify the integer program so that 2x4 + x5 ≤ 50 or 4x4− x5 ≥ 20, but not both.
(d) Modify the integer program so that if x2 = 1, then x1 = 0.
(e) Modify the integer program so that x1, x2 and x3 cannot all equal 1.
(f) Modify the integer program so that x7 is divisible by 3 but not 6.
5
6. Consider a 3× 3 game board. You are required to field each square with a number between 1
and 9 such that the sum of the numbers in each row, each column, and each diagonal equals
15. Additionally, the numbers in all the squares must be distinct.
(a) Formulate an integer program to determine an assignment of numbers to squares. (Since
you are just trying to find a solution, your objective function can be anything.)
(b) Use Excel to solve the program. What is the solution?
6

欢迎咨询51作业君