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:

max z = 4𝑥1 + 𝑥2 s. t. 8𝑥1 + 2𝑥2 ≤ 16 𝑥1 + 𝑥2 ≤ 12 𝑥1, 𝑥2 ≥ 0

Q2) MP – p.119 #37

Graphically find all solutions to the following LP:

min z = 6𝑥1 + 2𝑥2 s. t. 3𝑥1 + 2𝑥2 ≥ 12 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 in 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)