Linear Programming

isabella2296

My school textbook teaches that to find, for instance, the maximum profit you can make within a set of constraints in a business or whatever, you first graph the constraints and shade the common region. You then take the coordinates of the vertices of the region and find the profit each of them would yield. The largest would be the maximum profit.

But it didn't explain why this works, and that's what I'm wondering. Thanks in advance!

**Posted:** Tue Nov 03, 2009 10:39 am

_________________
Czech out $\mathfrak {Encyclopedia } \mathfrak { Mathematica}$
Latest entry: Morley's Theorem (Proof)

Ihatepie

Which part don't you understand?

**Posted:** Tue Nov 03, 2009 11:49 am

_________________
2010 Goals: ARML-7 AMC10- 144 AMC12- 126 AIME- 8 USAJMO-14?

Bugi

Nice... That is the graphic method BTW

Now, what are we doing? Suppose we are doing with 2 variables, put them on a graph (normal axes, each one represents one of the variables). Now, we should (with the given conditions) enclose an area in which those values can be.
For example, find the maximum of $2a-b$ if
$a,b\ge0$
$-3a+2b\le2$
$2a-3b\le3$
$a+b\le6$

We draw lines which separate for each of these conditions such that they separate the plane into 2 parts, one which satisfies the condition, one that isn't (for every point inside it) - in other words, the line is the equality case (example $a+b=6$ , so $b=6-a$ and so on)

Now for the given example, we are left with a polygon, with vertexes $(0,0),(1.5,0),(4.5,1.5),(2,4),(1,0)$

We know that $a$ and $b$ are inside or on the sides of that polygon. Now use the fact that minimum and maximum of a linear function are on its ''ends'', so we get that one of the vertexes is the solution, or in our example: $(4.5,1.5)$

Note: this is not a good method for many variables and/or higher degree conditions

**Posted:** Tue Nov 03, 2009 1:45 pm

isabella2296

@Ihatepie: Well, I know "how" to do it, I just didn't know "why".

@Bugi: Thanks! That was really helpful Smile

**Posted:** Tue Nov 03, 2009 3:47 pm

_________________
Czech out $\mathfrak {Encyclopedia } \mathfrak { Mathematica}$
Latest entry: Morley's Theorem (Proof)

10000th User

**Posted:** Wed Nov 04, 2009 6:40 am

_________________
$\mathrm{Hom}(\mathbb{Z},\mathbb{Z})\cong\mathbb{Z}$
Disclaimer: I'll revive old threads if: 1) something ambiguous in the solution or wrong argument, 2) no solution, 3) I got new insight to input.

Bugi

@Izzy: no problem Smile

@10000th: as I said, linear function has its maximum on one of its ends, so if we draw a segment through a point which we look at such that one of the endpoints is one of the vertexes, and the other lies on one of the sides, we see that the value at that interior point is less or equal to at least one of the segment endpoints, which are vertex and point on a side (or vertex again)

**Posted:** Mon Nov 09, 2009 2:09 pm

brainomega

**Posted:** Tue Nov 10, 2009 7:27 am

10000th User

**Posted:** Tue Nov 10, 2009 3:48 pm

_________________
$\mathrm{Hom}(\mathbb{Z},\mathbb{Z})\cong\mathbb{Z}$
Disclaimer: I'll revive old threads if: 1) something ambiguous in the solution or wrong argument, 2) no solution, 3) I got new insight to input.

Bugi

@10000th: OK, no need for any panic Wink

I just wanted to write it in the thread, so people could know, and it was addressed to you, because you said you can't find a source

@brainomega: hahahaha yeah I forgot it was linear programming...

**Posted:** Tue Nov 10, 2009 4:18 pm