Selected topics in finite mathematics/Linear programming

Linear programming is...

Objectives

• To find the maximum or minimum value of a linear expression given linear constraints
  
• Understand the terms objective and constraint.
  
• Be able to draw a mixture chart and write down the objective and constraints when given a word problem.

Details

A typical Feasible Region with two variables x=x₁ and y=x₂

In an optimization problem, the objective is the mathematical expression for the factor you want to optimize. (Typically an optimization problem will have only one objective)
An example of an objective could be x+3y A constraint is an equation which must be satisfied in the optimization problem.
An optimization problem generally has multiple constraints and one objective, which is the mathematical expression to optimize.

A point that fits all the constraints is called feasible. When working on an optimization problem, the first step is to graph the feasible region. In an optimization problem, one of the corner points of the feasible region graph will be the maximum.

Steps to solve a linear program:

1. Create mixture chart
2. Find constraints
3. Graph the feasible region
4. Find the corner points
5. Take the best one (optimal point)

Examples

1. A shop sells t-shirts for $20 each and jeans for $70 each and wants to maximize profit. The objective would be written 20x + 70y. The variable x represents the number of t-shirts and y represents the number of jeans.
2. A farm can grow several different plants on a field (say p1, p2, and p3). With each plant is a unit cost (say c1, c2, and c3). They farm only has d dollars to spend, but has a unit revenue of r1, r2, and r3. The objective would then be (r1-c1)p1+(r2-c2)p2+(r3-c3)p3 subject to the constraints p1, p2, p3>=0 and c1r1+c2r2+c3r3<=d