Flashcards
Answer
Linear Programming
Linear programming is optimization with a linear objective function and linear constraints.
It is the central model of this course.
See
-
LP Formulation
- How to translate a real-world problem into a linear program.
-
Matrix Form of LP Problems
- How to write many constraints compactly using $A$, $b$, $c$, and $x$.
-
Feasible Solutions
- How to check whether a candidate decision satisfies all constraints.
-
Bounded Infeasible and Unbounded Problems
- The main possible statuses of an LP problem.
-
Production Problems
- Models where activities consume resources and produce profit.
-
Transportation Problems
- Models where goods are shipped from sources to destinations.
-
Diet Problems
- Models where minimum requirements must be satisfied at minimum cost.
-
Investment Problems
- Models where capital is allocated across financial alternatives.
-
Resource Allocation Problems
- General allocation models with limited resources.
Basic Definition
A linear programming problem has the form:
\[\max c_1x_1+c_2x_2+\cdots+c_nx_n\]or:
\[\min c_1x_1+c_2x_2+\cdots+c_nx_n\]subject to linear constraints such as:
\[a_{i1}x_1+a_{i2}x_2+\cdots+a_{in}x_n \le b_i\]or:
\[a_{i1}x_1+a_{i2}x_2+\cdots+a_{in}x_n \ge b_i\]or:
\[a_{i1}x_1+a_{i2}x_2+\cdots+a_{in}x_n = b_i\]Components of an LP
Every LP has three parts.
| Part | Meaning |
|---|---|
| Decision variables | quantities we choose |
| Objective function | quantity we maximize or minimize |
| Constraints | restrictions the decision must satisfy |
The variables are usually written as:
\[x=(x_1,x_2,\ldots,x_n)\]The objective coefficients are usually written as:
\[c=(c_1,c_2,\ldots,c_n)\]Why It Is Called Linear
The problem is linear because:
- the objective is a linear function of the variables
- each constraint is a linear equation or inequality
Allowed:
\[3x_1+2x_2\le 10\]Not allowed in linear programming:
\[x_1x_2\le 10\] \[x_1^2+x_2\le 10\] \[\sqrt{x_1}+x_2\le 10\]Common LP Form
A compact form is:
\[\max c^Tx\]subject to:
\[Ax\le b\] \[x\ge 0\]For minimization:
\[\min c^Tx\]subject to:
\[Ax\le b\] \[x\ge 0\]Here:
- $x$ is the decision vector
- $c$ is the cost or profit vector
- $A$ is the constraint matrix
- $b$ is the right-hand side vector
Standard Form Preview
A common standard form is:
\[\min c^Tx\]subject to:
\[Ax=b\] \[x\ge 0\]General LP problems can be converted to this form using:
- slack variables
- surplus variables
- sign transformations
- free-variable substitutions
Feasible Set
The feasible set is the set of all points satisfying all constraints.
For example:
\[S=\{x\in\mathbb{R}^n\mid Ax\le b,\ x\ge 0\}\]Only feasible points can be optimal.
Geometric Meaning
In two variables, each linear inequality defines a half-plane.
The feasible region is the intersection of all half-planes.
The objective function gives contour lines:
\[c^Tx=k\]For a maximization problem, these lines are moved in the direction of $c$.
For a minimization problem, they are moved in the direction of $-c$.
An optimum, when it exists, is found at a vertex of the feasible region.
Possible Outcomes
An LP can have:
- a unique optimal solution
- multiple optimal solutions
- no feasible solution
- an unbounded optimal value
Typical Applications
Linear programming is used for:
- production planning
- transportation
- diet and blending problems
- investment allocation
- staff scheduling
- resource allocation
- capacity planning
Exam Pattern
Most formulation questions follow this structure:
- define the decision variables
- write the objective function
- translate each sentence into a constraint
- add nonnegativity constraints
- check units
- state the final LP clearly
Key Takeaway
A linear program is a decision model where the goal and all restrictions are linear.
Once a real problem is written as an LP, it can be solved graphically in two variables or algorithmically using simplex and solver tools.
Added exam practice
- Formulation Drill Set
- Solved Exam Template
- [[ Exam Coverage Matrix ]]
Exam checkpoint
For formulation questions, show variables, objective, constraints, sign restrictions, and units. Do not solve unless the question asks for a solution.