3
$\begingroup$

I'm taking my first class in Linear Programming. The book I am reading from is good in that it uses a lot of examples, but bad in that it provides few proofs. I need a proof for the following theorem.

Theorem:

If the constraint set $S$ of a canonical maximization or a canonical minimization linear programming problem is bounded, then the maximum or minimum value of the objective function is attained at an extreme point of $S$.

Glossary of Terms:

Definition 1

The problem

Maximize $f(x_1,x_2,\cdots,x_n)=c_1x_1+c_2x_2+\cdots+c_nx_n$

Subject to $a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n\leq b_1$

$a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n \leq b_2$

$\cdots$

$a_{m1}x_1+a_{m2}x_2+ \cdots + a_{mn}x_n \leq b_n$

$x_1,x_2, \dots, x_n \geq 0$

is said to be a canonical maximization linear programming problem. The definition for minimization is analogous.

Definition 2

Let $x= (x_1,x_2,\cdots ,x_n), y=(y_1,y_2,\cdots ,y_n)\in$ R$^n$. Then $tx+(1-t)y$ for $0\leq t\leq 1$ is said to be the line segment between $x$ and $y$ inclusive.

Definition 3

The set of all points $(x_1,x_2, \cdots, x_n)$ satisfying the constraints of the canonical maximization problem is said to be the constraint set

Definition 4

Let $S$ be a subset of R$^n$. $S$ is said to be convex if, whenever $x$=$(x_1,x_2,\cdots,x_n)$,$y$$=(y_1,y_2,\cdots,y_n)\in S$, then

$tx+(1-t)y \in S$ for $0\leq t \leq 1$

Definition 5

A subset $S$ of R$^n$ is said to be bounded if there exists $r\geq 0$ such that every element of $S$ is contained in the closed ball of radius $r$ centered at the origin. A subset of R$^n$ is unbounded if it is not bounded.

Definition 6

The function $f(x_1,x_2,\cdots,x_n)$ is called the objective function of a canonical linear programming problem.

Definition 7

Any element of the constraint set is said to be a feasible point or feasible solution. Any feasible solution which maximizes/minimizes the objective function is said to be an optimal solution.

My Work

I genuinely have no idea how to do this problem. It wasn't assigned as homework, I just want to understand the reasoning behind it because that will help me do better in my course.

$\endgroup$
  • 1
    $\begingroup$ Need one more definition "extreme point". $\endgroup$ – coffeemath Jan 15 '16 at 17:27
  • $\begingroup$ @coffeemath I have added it under Definition 7. Apologies for the delay, I posted this question right before a lecture. $\endgroup$ – Darcy Olson Jan 15 '16 at 18:30
  • $\begingroup$ A gaphical representation may help as in here:maaw.info/TOCClassProblem2.htm $\endgroup$ – NoChance Jan 15 '16 at 20:09
  • $\begingroup$ How I convince my freshman non-math major students(we only do 2 variable LP so I will use a plane section): I bring in a big piece of cardboard and chop it up so it looks like a feasible set. Then I mention that the objective function can be thought of as slanting the piece of cardboard(so embedding the feasible set in R^3 with the z coordinate given by the output of the Objective function). Could the highest point be anywhere other than a corner? This is non-rigorous, but intuitive(I hope). $\endgroup$ – Sean English Jan 15 '16 at 20:13
2
$\begingroup$

This is due to the fact that the function you are optimizing is linear, and defined on a compact space.

To understand why this is true, consider the mono variable case: $$ \mbox{Max}\quad f(x)=\alpha x \quad \mbox{subject to}\quad a\le x \le b $$

Draw the function and the interval $[a,b]$: it is clear that the optimum is in $x=b$, which is an extreme point of your polygon (a closed interval here).

You can do the same drawing if you have two variables (you will have to draw in 3D) to convince yourself that it is true in this case as well. This is exactly what user Sean English says in his comment above.

Now for a formal proof: since $f$ is continuous and defined on a compact space, it is bounded and attains its maximum and minimum at least once by the extreme value theorem . But since $f$ is linear, it can only attain it once, necessarily on the border of the compact space, namely the extreme points here.

$\endgroup$
  • $\begingroup$ What is a compact space? $\endgroup$ – Darcy Olson Jan 15 '16 at 20:52
  • $\begingroup$ A closed and bounded one. $\endgroup$ – Kuifje Jan 15 '16 at 20:55
  • $\begingroup$ Consider the function $f(x,y):=y$ on the unit square $[0,1]^2$. It of course satisfies the claim, but takes its max at an infinity of points. $\endgroup$ – Christian Blatter Jan 18 '16 at 16:48
  • $\begingroup$ Yes I agree. But the optimum is still on the $\textit{border}$ of the compact square. So to complete the proof, we would need to set apart two cases: there is a unique solution, or there are an infinity. In the first case, it will attain it on an extreme point, in the second on an edge. $\endgroup$ – Kuifje Jan 18 '16 at 17:01
  • $\begingroup$ Nonetheless, if the user is looking for AN optimal solution, there are still two at extreme points (1,0) and (1,1). $\endgroup$ – Kuifje Jan 18 '16 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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