Thread: Linear Programing - Negative Numbers Help

Hi,

I am wondering what to do with this question

Minimize 2x1 - 3x2

with constraints

A: -3x1 + x2 = 90
B: 4x1 + 2x2 = 120
C: x1 + 2x2 = 150

The first constraint works out to be: x1= -30, and x2 = 90. I don't think this is right because you cannot have a negative number in a linear model.

Can anyone help me?

Have you tried to solve this graphically?

But is it possible to have a negative number? ie x1= -30?

I don't understand how you can give a numerical value to constraints. They are functions - in this case, linear functions. You should start by graphing the constraints.

Are you sure all the constraints are equalities - I would think they should be inequalities...

Ok, I just assumed since my textbook says it must be a non-negative number. I'm just unsure what to do with negative numbers.

So I should be able to sole that graphically and find the optimum using simultaneous equations?

Yes, the basic idea of "Linear Programming" is that the max or min of a linear object function, on a convex polytope, occurs at one of the vertices. However, to get a "convex polytope", your constraints must be inequalities, not equations. Are you sure you have written them correctly? I recommend you check the problem again since I cannot set "<" or ">" to give a bounded feasible region.

Here' the question:

Constraint A: -3X1 + X2 =< 90
Constraint B: 4X1 - 2X2 >= 120
Constraint C: X1 + 2X2 =< 150
All variables are required to be non-negative. Let the objective function be Min: 2X1 - 3X2. Corner points of the feasible region include?

Originally Posted by guthrie23

Here' the question:

Constraint A: -3X1 + X2 =< 90

On the boundary, if X1= 0, then X2= 90. If X2= 0, then X1= -30. The boundary is the line through (0, 90) and (-30, 0). The feasible region is below that line.

Constraint B: 4X1 - 2X2 >= 120

On the boundary, if X1= 0, then X2= -60. If X2= 0, then X1= 30. The boundary is the line through (0, -60) and (30, 0). The feasible region is above that line.

Constraint C: X1 + 2X2 =< 150

On the boundary, if X1= 0 then X2= 75. If X2= 0, then X1= 150. The boundary is the line through (0, 75) and (150, 0).

All variables are required to be non-negative. Let the objective function be Min: 2X1 - 3X2. Corner points of the feasible region include?

Requiring that all variables be non-negative means that X1= 0 and X2= 0 are also boundaries.

The vertices of the feasible region are
1) Where X1= 0 any X2= 0 intersect: (0, 0)
2) Where X2= 0 and 4X1 - 2X2 = 120 intersect: (30, 0)
3) Where X1= 0 and -3X1 + X2 = 90 intersect: (0, 90)
4) Where 4X1- 2X2= 120 and -3X1+ X2= 90 intersect: solve those equations
5) Where -3X1+ X2= 90 and X1 + 2X2 = 150 intersect: solve those equations

How would I do this? Constraint C is throwing me off.

Constraint A: 3X1 + X2 =< 90
Constraint B: 3X1 + 2X2 =< 120
Constraint C: X1 - X2 =< 0
All variables are required to be non-negative. Let the objective function be Max: X1 + X2. The objective function value corresponding to the optimal solution will be?

How would I do this? Constraint C is throwing me off.

Constraint A: 3X1 + X2 =< 90
Constraint B: 3X1 + 2X2 =< 120
Constraint C: X1 - X2 =< 0
All variables are required to be non-negative. Let the objective function be Max: X1 + X2. The objective function value corresponding to the optimal solution will be?

This is what I came up with.

2(3X1 + X2 =< 90)

=6x1 + 2x2 =< 180
-3x1 + 2x2 =< 120
3x1 = 60

x1 = 20

3(20) + 2x2 = 120
2x2 = 60

x2 = 30

Therefore, Z = x1 + x2 = 50. Is that the right way to do it?

Constraint A:

Constraint B:

Constraint C:

Nonnegativity Constraints: .


Start by graphing these inequalities to find the feasible region. It helps if you shade the half-planes that are NOT included, so that your feasible region stays blank.

Then substitute each corner point into your objective function and evaluate. Whichever is the maximum is the optimal solution.

How do i graph constraint C?

x2 => x1

If you think of as and as , graph the function then shade the half-plane below the graph (since you are shading the half-plane that's not included).