Question

You’ve been asked to develop a problem that can be used to explain some of the concepts you know to someone who has never heard of linear programming. 1. Formulate a maximization problem such that the following conditions are met (you may not use a problem has appeared on this assignment). Make sure to include all elements of formulation that we have discussed (i.e., objective function, constraints, non-negatives). a. LP problem with two decision variables (using X and Y as your variables) b. There are multiple optimal solutions when the objective function is maximized c. There are two constraints (not counting non-negatives) and one of them must be a redundant constraint 2. Graph your formulation and label the objective function and constraints accordingly. 3. Explain why there would be multiple optimal solutions when maximized (max. 2 sentences).

Answer 1

1. Formulate a maximization problem such that the following conditions are met (you may not use a problem has appeared on this assignment). Make sure to include all elements of formulation that we have discussed (i.e., objective function, constraints, non-negatives).

a. LP problem with two decision variables (using X and Y as your variables)

b. There are multiple optimal solutions when the objective function is maximized

c. There are two constraints (not counting non-negatives) and one of them must be a redundant constraint

Linear programming graphical method

Step 1

Let X1,X2 be the decision variables

Decision variable-x1,x2

Objective

MAXIMIZE: Z = 2 X1 + 6 X2

Constraints

X1 + 3 X2 ≤ 60

X1 ≤ 70

X1, X2 ≥ 0

2. Graph your formulation and label the objective function and constraints accordingly.

Step 2

Decision variable X1 is represented in X axis and X2 is represented in Y axis. Constraint equations are represented by lines in the graph. Each constraint line meets x-axis and y-axis at two points. Find the coordinates of the points. The line joining these points represents the constraint line

Example

1. For Constraint 1, Let,    X1 + 3 X2 = 60

At the point where the line meets X axis, X2=0

When X2=0,    X1=60

At the point where the line meets Y axis, X1=0

When. X1=0,    X2=20

Constraint 1 is formed by joining the points that meets x-axis and y-axis at two points B(60,0) and A(0,20) respectively

Constraint 2 is represented by line x1=70

The last non-negativity constraint shows that the value is in the first quadrant of a graph

The feasible region is the one that satisfies the constraints-shaded green. We find the graph is bounded ie the feasible region in graph is bounded on all sides by the axes and the constraints

Optimal solution occurs at extreme corner points A,B

Graph

28 18 16 14 12 18 0 70 56 42 28 14 63 49 35 21

Graph

• In green, the points where the solution is located
• In red, the points that not belong to the feasible region.
• Feasible region is Shaded green
• Black lines represent constraints
• Red line represents objective function.
• Blue line represents objective function line moving away from origin and meeting the optimal solution at E

Point	X coordinate (X1)	Y coordinate (X2)	Value of the objetive function (Z)
O	0	0	0
A	0	20	120
B	60	0	120
C	70	0	140

REDUNDANCY

Constraint 2 represented by line x1=70 is overshadowed by the constraint 1 . constraint 2 is redundant constraint

Step 3

Objective line method

Find the objective function line

MAXIMIZE: Z= 2 X1 + 6 X2

Let,

2 X1 + 6 X2= (coefficient of x ) * (coefficient of x2 )

2 X1 + 6 X2= 2 * 6

2 X1 + 6 X2= 12

The line meets x-axis and y-axis at two points. Find the coordinates of the points. The line joining these points represents the objective line

When. X2=0, X1=6

When X1=0, X2=2

The objective function line meets x-axis and y-axis at two points (6,0) and (0,2) respectively

Step 4

Now move the objective function line away from   the origin in the feasible region (since it is a maximization problem we move away from origin. If it is a minimization problem, we move towards the origin. ) such that the line stays parallel to the original objective line. The last point in the feasible region that the line touches when we keep moving is the optimal solution. Here the line touches both point A and B.

There are multiple optimal solutions

Another method- Corner points method

Plug the values of each corner point- x1, x2 in the objective function. The one that gives maximum value is the optimal solution

The values of the objective function at these extreme points are:

Point	X coordinate (X1)	Y coordinate (X2)	Value of the objective function (Z)
O	0	0	0
A	0	20	120
B	60	0	120

Both A and B have maximum values- multiple solutions

3. Explain why there would be multiple optimal solutions when maximized (max. 2 sentences).

Generally multiple optimal solutions occur when objective line is parallel to a binding constraints .i.e. when they have the same slope

Objective

MAXIMIZE: Z = 2 X1 + 6 X2 = 2 ( X1 + 3 X2)

Constraint

X1 + 3 X2 ≤ 60

*Compare the bold items

Actually every point between them on the line are also optimal

28 18 16 14 12 18 0 70 56 42 28 14 63 49 35 21