MA569编程设计代写、Python，Java程序语言代做

日期：2021-06-27 02:56

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 ≤ 03x1 +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?