A binary integer programming problem is expressed as: Max z = 3x 1 + 2x 2 - 5x 3

Question

A binary integer programming problem is expressed as:

Max z = 3x1 + 2x2 - 5x3 - 2x4 + 3x5
Subject to
x1 + x2 + x3 +2x4 + x5 <= 4
   7x1 + 3x3 - 4x4 +3x5 <= 8
11x1 - 6x2 + 3x4 - 3x5 <= 3
   x1,...,x5 all take values of either 0 or 1

Suppose now you are in the middle of the Branch-and-Bound solution, and you need to solve the relaxed LP for the case where you have preset and . Again you use the syntax x=linprog(f,A, B, [], [], lb, ub). Which of the following formulations will give you the correct answer?

a) f = [3 2 -5 -2 3]; A =[1 1 1 2 1; 7 3 -4 3; 11 -6 3 -3]; b=[4 8 3]’; lb = zeros(3,1); ub=ones(3,1);

b) f = -[3 2 -5 -2 3]; A =[1 1 1 2 1; 7 0 3 -4 3; 11 -6 0 3 -3]; b=[4 8 3]’; lb = zeros(5,1); ub= ones(5,1);

c) f = [3 2 -5 -2 3]; A =[1 1 1 2 1; 7 3 -4 3; 11 -6 3 -3]; b=[4 8 3]’; lb = zeros(3,1); ub=[1, 0, 1]’;

d) f = -[3 2 -5 -2 3]; A =[1 1 1 2 1; 7 0 3 -4 3; 11 -6 0 3 -3]; b=[4 8 3]’; lb=[1, 0, 0, 0, 0]; ub=[1, 0, 1, 1, 1]’;

e) You will have to use the syntax x=linprog(f,A, B, Aeq, beq, lb, ub) because Aeq and beq cannot be empty.

Explanation / Answer

The answer is :

b) f = -[3 2 -5 -2 3]; A =[1 1 1 2 1; 7 0 3 -4 3; 11 -6 0 3 -3]; b=[4 8 3]’; lb = zeros(5,1); ub= ones(5,1);

The options a,c,d cannot be the answer as the value of A in a and c are wrong and value of ub is wrong in d. Hence the answer is b.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.