Graphically find all solutions to the following LP

IE 405 Spring 2013, HW 2

Due Date: 2/7 in class.

Q1) MP – p.118 #33

Graphically find all solutions to the following LP:

maxz = 4푥 1 + 푥 2

s.t. 8푥 1 + 2푥 2 6

푥 1 + 푥 2 ≤ 12

푥 1 ,푥 2 ≥ 0

Q2) MP – p.119 #37

Graphically find all solutions to the following LP:

minz = 6푥 1 + 2푥 2

s.t. 3푥 1 2푥 2

2푥 1 + 4푥 2 12

푥 2 1

푥 1 ,푥 2 ≥ 0

Q3) Consider the feasible set in 푅 2 defined by the constraints; - 푥 1 + 푥 2 ≤ 1,

푥 1 ,푥 2 ≥ 0, which is shown Figure 1. For cost vector c = (푐 1 ,푐 2 ), the cost

minimization problem is defined with objective function cx = 푐 1 푥 1 + 푐 2 푥 2 . For

each of the cost vector listed in the figure, discuss the possibilities of optimal

solutions.

Figure 1

Q4) Consider the following Problem:

min z = x + y

s.t : x – y ≤1

2x + y ≥6

x, y ≥ 0

Part A:

Graph the feasible region

Part B:

Is the feasible region unbounded?

Part C:

Solve the problem using the geometric method.

Part D:

Now suppose we change the min to a max. What is the new optimal solution to the

problem.

Part E:

Come up with two different vectors that point in the unbounded direction (also

known as a direction of unboundedness). Call these two vectors C = (c1, c2) and

D= (d1, d2). This means that for any solution (a’, b’) and for any non-negative real

number r, both (a’ + rc1, b’ + rc2) and (a’ + rd1, b’ + rd2) are feasible solutions.

Part F:

Give an objective function (other then the function z=0 or z=constant) for the

original problem that yields multiple optimal solutions.

Part G:

Add a constraint that makes the problem infeasible, show this graphically.

Part H:

Consider the original problem with the added constraint that y is at most 6 as

shown below.

min z = x + y

s.t : x – y ≤1

2x + y ≥6

y ≤ 6

x, y ≥ 0

What is the new optimal solution to this problem?

Part I:

Express the feasible region as a convex hull using the representation theorem.

Part J:

Consider the following modified problem

min z = x + y

s.t : x – y ≤1

2x + y ≥G

y ≤ 6

x, y ≥ 0

Let Z(G) be the optimal objective value for a given G. Plot Z(G) for Z=-50 to z=50.

Q5) Please check the 1st case study in ‘Case Study’ folder. (Due Date: Feb. 12)