Linear Programming - Feasible sets?

[flyingpig]

Homework Statement

Consider the following LOP K:

Max $$z = 4x_1 + 3x_2$$

s.t

$$7x_1 + 6x_2 \leq 42$$

$$2x_1 - 3x_2 \geq -6$$

$$x_1 \geq 2, x_1 \leq 5, x_2 \geq \frac{1}{2}$$

(a) Decide whether the solution sets are feasible

i) $$x = (3.5, 2.5)^t$$
ii) $$x = (2.1, 4)^t$$
iii) $$x = (5,1/2)^t$$

(b) Graph the system of constraints of K. Label the corner points

(c) Draw the line z = 12 and z = 24 on the graph

(d) Estimate where the optimum occurs

The Attempt at a Solution

(a) Does the t mean transpose? If not, I have no idea what to do. There's a lot of weird words in this course I am taking.

(b) [PLAIN]http://img707.imageshack.us/img707/9267/unledwuj.png

(c) I don't know what this means, z(x_1, x_2), that's a plane

(d) ONe of the corners? No computation? Confused

 

[Mark44]

a) Yes, the t means transpose.

Also, I'm not happy with the phrasing "Decide whether the solution sets are feasible"
What you are given for i), ii), iii) are just points, and you should determine whether they are in the "feasible region" or "feasible set". This set is all of the points that satisfy your constraints.

b) Your graph of the feasible region is not quite right. The inequality you have wrong is x2 >= 1/2. Your graph shows x2 <= 1/2

c) z is a function of x1 and x2, so z(2, 5) for example, means the value you get if you put 2 in for x1 and 5 in for x2.
This is NOT a plane - it's a line.
They are asking you to draw the lines 4x1 + 3x2 = 12 and 4x1 + 3x2 = 24

d) Draw the lines and see...

 

[flyingpig]

a) Wouldn't the transpose (I know this isn't a matrix) make my solution set vertical? How would I plug that in? Why is that there?

b) So it's the triangle above my pink region right? (the white triangle, yes i realize there are 4 triangles in my picture)

c) Wow that's confusing!

d) Will do

 

[flyingpig]

[PLAIN]http://img607.imageshack.us/img607/8898/unledcz.png

I will draw the lines later

 

[Mark44]

a) Wouldn't the transpose (I know this isn't a matrix) make my solution set vertical? How would I plug that in? Why is that there?

All they are doing is writing 2D points as column vectors. It's nothing more than that.

b) So it's the triangle above my pink region right? (the white triangle, yes i realize there are 4 triangles in my picture)

Not quite. Your "triangle" has four sides.

c) Wow that's confusing!

I know you can do it.
Think of it like this:
z = f(x1, x2) = 4x1 + 3x2.

It's true that z = 4x1 + 3x2 is a plane in R³, but what we're looking at here is the intersection of this plane with the planes z = 12 and z = 24. These intersections are also called contour lines.
What is the "locus of points in the plane" such that z = f(x1, x2) = 12? z = f(x1, x2) = 24?
These are nothing more than straight lines.

d) Will do

 

[flyingpig]

Mark, I hope you are here tomorrow and on the weekend LOL. The drawing takes some time, I will finish the lines tomorrow. Thanks

 

[flyingpig]

a) All they are doing is writing 2D points as column vectors. It's nothing more than that.

They are vectors?? They look like points. WHy would they do that? Actually why would my professor do that?

b) Some quadrilateral -trapezoid thing.

[PLAIN]http://img262.imageshack.us/img262/2933/unled.png

I still don't know where to guess

 

[Mark44]

For a) are the three points in your feasible region or not? That's all you need to say. For some reason your instructor is writing points as vectors. Big deal.
b) done
c) You need to graph 4x1 + 3x2 = 24 and 4x1 + 3x2 = 12. These are parallel lines.
d) The optimum point will be the point in the feasible region (yes, it will be a corner point) that is closest to the two lines of part c).

 

[flyingpig]

Yeah my lines are on there in the picture.

How do you know it will be inside the two lines? How did he even know what line to choose?

 

[Mark44]

Yeah my lines are on there in the picture.

How do you know it will be inside the two lines? How did he even know what line to choose?

I just did a more careful drawing of the feasible region, and have discovered a mistake in yours. The feasible region should have five sides, not four as you have drawn. The line 2x - 3y = -6 has an x-intercept at (-3, 0) and a y-intercept at (0, 2). Your drawing has these reversed. (I've switched to using x and y instead of using subscripts on x.)

In my drawing, one of the lines passes through the feasible region, but the other one is completely outside it. The objective function, z = 4x + 3y, gets larger as both x and y increase. Assuming that your goal is to maximize the objective function, you want the line that is farthest from (0, 0), but still lies inside or just touches the feasible region.

 

[SammyS]

The objective function, z = 4x + 3y, can be thought of as giving a family of parallel lines -- a different line for each different value of z. Solving z = 4x + 3y for y gives:

$\displaystyle y=-\frac{4}{3}x+\frac{z}{3}$​

This represents a family of lines each with a y intercept of z/3 and all with slope of -4/3 . The maximum z occurs for the line in this family that has the largest y-intercept, but which also intersects the feasible region. This is consistent with what Mark has pointed out.

 

[flyingpig]

1) How exactly do show that it is a feasible set? Like for (3.5, 2.5), do I just ue the inequalities?

$$1/2 \leq 3.5 \leq 5$$

 

[Mark44]

In part b you are asked to sketch the feasible region, which you did, but with the error noted in post #10. You should be able to tell from your sketch, whether a point is in the feasible region.

 

[flyingpig]

[PLAIN]http://img600.imageshack.us/img600/4136/unledclp.png

 

[flyingpig]

In part b you are asked to sketch the feasible region, which you did, but with the error noted in post #10. You should be able to tell from your sketch, whether a point is in the feasible region.

Yeah but how do I show that to the grader?

 

[Mark44]

How are you going to show the grader that you have sketched the feasible region? If the grader sees your sketch, he/she will also be able to see whether the point (3.5, 2.5) is in the feasible region.

 

[flyingpig]

For d) it asked me to "guess", you said it would be the farthest point from the origin (which make sense), but I think they want us to give them a point and explain why?

That sounds tedious seeing I might have to use the distance formula for each point?

 

[Mark44]

It says, "Estimate where the optimum occurs".
USE THE SKETCH - you don't need to calculate any distances. Look to see which corner point of the feasible region is closest to whichever line is outside the feasible region.

You are really overthinking this stuff...

 

[HallsofIvy]

Yeah but how do I show that to the grader?

By drawing the feasible region and marking the point.

 

[flyingpig]

OKay I checked my prof's solution on another similar problem and I am suppose to put my points into all of the constraints and show that it satisfies the inequality.

Kinda stupid but okay

 

[Ray Vickson]

Yeah but how do I show that to the grader?

What's stopping you from writing "yes, the point is in the feasible region" or "no, the point is not in the feasible region", whichever is the case? You can even PROVE it, if the diagram is not convincing or is not accurate enough: just plug the values of x_1 and x_2 into the constraints and see if they all work.

RGV

 

[flyingpig]

Because my prof is picky and incompetent

i) Feasible
ii) infeasible
iii)Feasible

 

[flyingpig]

It says, "Estimate where the optimum occurs".
USE THE SKETCH - you don't need to calculate any distances. Look to see which corner point of the feasible region is closest to whichever line is outside the feasible region.

Couldn't he have chosen another z= c that lies outside the region and you can make the same argument? Like the point closest it (30/11,47/11) to z = 24, but if say another z = c such that it lies outside the region, but the closest point isn't (30/11,47/11)?

Like would it better phrased if the question said "estimate the optimum is with respected to z = 12 and z = 24?"