# Proof required for an alternate method in solving a linear programming problem

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 South-East 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.
-

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(x_0, y_0)$ and $Q(x_1, y_1)$ 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(x_0, y_0)$. Then, max $[F(x, y)] = Ax_0 + By_0$.

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<q$, then $Ax_0 + By_0 > Ax_k + By_k$; 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(x_0, y_0)$, ∴ $y_0 = – (A/B) x_0 + p$ i.e. $p = y_0 + (A/B) x_0$ Similarly, $q = y_1 + (A/B) x_1$ $p < q => [y_0 + (A/B)x_0] < [y_1 + (A/B)x_1]$ i.e. $Ax_0 + By_0 > Ay_1 + By_1$ [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$?)

-