Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose that P and Q are two of the corner points of the feasible region lying completely in the first quadrant. In addition, P is located at SE of Q*.

z = 0 (or more specifically, Ax + By = 0) is a profit function (or any other terms applicable) with positive slope.

To find graphically at which corner point that max(z) is obtained is by drawing lines L1, L2, …, Ln, parallel to z = 0 towards the SE direction*. This way, we found Ln hits P.

Judging from the method used above, we can reasonably re-phrase the above by just finding which of the L’s has the least y-intercept.

If this is true, is there any mathematical proof (especially in co-ordinate geometry)?

  • pardon me for not using more specific mathematical terms.
share|improve this question

1 Answer 1

I have a proposed solution (see below) that I am not 100% satisfied. Please comment.

Given that a convex feasible region lying completely inside the first quadrant has n corner points. Among them, we are only interested in P(x0, y0) and Q(x1, y1) where P is located lower and righter than Q. F(x, y) = Ax + By is the objective function such that m(L) > 0 where L is the simplest line of reference that has the equation Ax + By= 0.

L(Q) is a line through Q with slope = m(L) and its y-intercept = q > 0, say. L(P) is a line through P with slope = m(L) and its y-intercept = p > 0, say. [For simplicity only, the argument works well if p < 0.]

In linear programming practice, if we want to find max[F(x, y)] graphically, we start from L(Q) and move in the direction “South-East” until we find P(x0, y0). Then, max[F(x, y)] = Ax0 + By0.

The effect will be exactly the same as finding which of the lines has the smaller y-intercept. In this case, it is L(P). This can then be re-phrased as “if p Axk + Byk; where k = 1, 2, … , n”.

Preliminaries: m(L) > 0 ; where L: Ax + By = 0 => we can assume that A > 0 and B < 0. [If not, we can use L’ : –(Ax + By) = 0 as our line of reference instead.]

Proof L(P) : y = – (A/B) x + p It passes through P(x0, y0), ∴ y0 = – (A/B) x0 + p i.e. p = y0 + (A/B) x0 Similarly, q = y1 + (A/B) x1 p < q => [y0 + (A/B)x0] < [y1 + (A/B)x1] i.e. Ax0 + By0 > Ay1 + By1 [since B < 0]

I am not comfortable with the argument in the preliminaries. Take a simple example, let F(x, y) = x – y. Then, we draw the line of reference as x – y = 0. If we draw – x + y = 0 instead, what are we calculating? (maximizing x – y / maximizing y – x / minimizing x – y / minimizing y - x?)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.