This blog I will share my notes in Penn State MATH 484: Linear Programming.

Optimization Problem

For mapping ${ x-> f(x) }$ ranges in interval ${ [220,484] }$, how can we find the max/min value?

We can derivate ${ f(x) }$ to find the point ${ x}$ such that ${ f’(x) = 0 }$ and ${ f’‘(x) >0 }$ and check the boundary value ${ f(220) }$ and ${ f(484) }$. We will find min value from local minima ${ f(x)}$ and boundary value ${f(220), f(484) }$

Linear function

Form like ${ f(x) = cx }$ can be called a linear funtion. Take a simple example

$$ f(x) = 1/2 x$$ $$ \begin{aligned} &\text{minimize } & 1/2 x &\text{ # linear cost function} \\ &\text{subject to } & 220 \leq x \leq 484 &\text{ # feasible set, always include boundry, set of linear inequality constriaints} \end{aligned} $$

Term:

• optimal cost: the optimal value
• optimal feasible solution: the solution of optimal cost

Linear Optimization problem

$$ \begin{aligned} &\text{minimize } &x_1 + x_2 & \text{ or } \begin{bmatrix} 1 \\ 1 \end{bmatrix} \begin{bmatrix} x_1 & x_2 \end{bmatrix} \\ &\text{subject to } &2x_1+ x_2 &\geq 2 \\ & &x_1 + x_2 &\leq 3\\ & &x_1 &\geq 0\\ & &x_2 &\geq 0\\ \end{aligned} $$

After drawing the figure, we will find the feasible set is the polygon in ${ x_1 - x_2 }$ plane with verties ${ (1,0) (0,2) (0,3) (3,0) }$.

The red plane represent the cost function ${ x_1 + x_2 }$, which projects to ${ x_1 - x_2 }$ plane. We can check the altitude of all the corner points in the polygon to get the minima value of cost function on feasible set.