LP and Non-LP Issues

Linear Programming

• Mathematical method used for optimization problems
• Main applications are to maximize profits and minimize costs
• Objective function is linear when:
• Optimum always attained at constraint boundaries
• A local optimum is also global optinum
• Other applications
• operational research - solve multi-commodity flow issues and network flow
• strategic games - chess, manufacturing, resource conservation, transportation systems for buses and trains, and military budgeting
• microeconomics
• Assumptions:
• all variables have non-negative values
• A negative value will be written as a function of two non negative values
• ie. If $x = -5$, then we let $x_1 = 0$, $x_2=5$ and assign $x = x_1 - x_2$
• Advantages:
• Works with inequalities with non negative coefficients. As long as the inequalities are changed into standard form
• The simplex algorithm can determine if there is no solution to the problem (if pivot can't be made)
• Algorithm is easy to program in a computer
• Disadvantages:
• The algorithm becomes inefficient if too many variables are used. It may require an exponential number of steps.
• Strict inequalities might not work in LP
• Example: same example as earlier, using x as the first pivot

Non Linear LP

• Objective function is non linear when:
• Optimum may be interior as well as at boundaries of constraint 
• A local optimum is not necessarily the global optinum
• Nonlinearity came from
• multiplication of variables: economies of scale, transaction costs
• quadratic terms: variances, interest rates mean-variance optimization
• nonlinear functions: quantiles in common risk measures
• Approach to nonlinear optimization: iterative method
• Basic Numerical methods: Solving for non linear functions
• Other methods: 
• Steepest Descent Method
• Newton's Method 
• Quasi-Newton Method
• Lagrange multipliers 
• Conjugate Gradient Method
• Penalty Function Method
• In general, optimization problems are unsolvable.
• "It's the user's responsibility to choose an algorithm that is appropriate for the specific applications

Take-aways

• revised way of pivoting starting with $x$ in the simplex method
• What if the constraints are less than the unknown? Will there be a difference in the simplex method?
• Always check on the assumptions coz it might not gonna work because of wrong constraints
• the answer might not be exactly the solution to the problem at hand. We might be creating more problems than the solution of the problems
• Portfolio optimization technique - "robustness"
• The methods are just tools for the user to use. The question is, is the user using the right tools for the problem at hand?

Resources: Class groups ppt.

LP: Simplex Method

Maximization

How lucky my sister was for waking me up at the middle at the night to teach her the simplex method, in the matrix way for her exam in a few hours. How luckier I am, it is one of the class topics we were about to discuss allowing me to recall on some things. 

Here is a simple maximization problem from her book. All we needed to do after the first table is to make the $2$ x $2$ matrix on the upper left an identity matrix and the last $1$ x $2$ matrix on the lower left, zeroes. Remember that these are equations so the "elimination via matrix" is applied.

Minimization

For minimization problems, a little tweaking is needed. Example, if you are given
 \[ \text{min } z = 0.15x_1+0.12x_2\]
with constraints
\[ \begin{split} 60x_1 +60x_2 & \geq 300 \\ 12x_1 + 6x_2 & \geq 36 \\ 10x_1 + 30x_2 & \geq 90 \end{split} \]
then we have the matrix
\[ \begin{bmatrix} 60 & 60 & \vdots & 300 \\ 12 & 6 & \vdots & 36 \\ 10 & 30 & \vdots & 90 \\ \cdots &\cdots & \vdots & \cdots \\ 0.15 & 0.12 & \vdots & 0\\ \end{bmatrix} \]
The transpose of this matrix will give you a maximization problem and the rest of the process is the same as earlier.  

Application - Simplex method Application varies from business to business and are commonly used.

Links for more info is provided below: 
http://pages.intnet.mu/cueboy/education/notes/algebra/simplex.htm
http://college.cengage.com/mathematics/larson/elementary_linear/5e/students/ch08-10/chap_9_3.pdf
http://college.cengage.com/mathematics/larson/elementary_linear/5e/students/ch08-10/chap_9_4.pdf