Flashcards
Answer
Optimization Foundations
Optimization is the study of choosing the best possible decision from a set of allowed decisions.
In operational research, optimization is used to improve decision-making when resources are limited.
See
-
Decision Variables
- The unknown quantities we choose.
-
Objective Functions
- The function we want to maximize or minimize.
-
Constraints
- The conditions that feasible decisions must satisfy.
-
Feasible Sets
- The set of all candidate solutions satisfying the constraints.
-
Optimal Solutions and Optimal Values
- The best feasible decision and its objective value.
-
Constrained Optimization
- Optimization when not every point is allowed.
-
Modeling Workflow
- How to translate a real-world decision problem into mathematics.
General Optimization Problem
An optimization problem has the form:
\[\min f(x)\]or:
\[\max f(x)\]where:
\[f:\mathbb{R}^n \to \mathbb{R}\]is the objective function.
The vector:
\[x=(x_1,x_2,\ldots,x_n)\]contains the decision variables.
Maximization and Minimization
We use maximization when the objective represents a benefit.
Examples:
- profit
- revenue
- expected return
- production output
- utility
We use minimization when the objective represents a cost or loss.
Examples:
- cost
- distance
- time
- waste
- risk
Constraints
A constraint is a condition that the solution must satisfy.
Constraints can be:
- equality constraints
- inequality constraints
- integer constraints
- sign constraints
Example:
\[x_1+x_2\le 100\]could mean that the total use of a resource cannot exceed $100$.
Feasible Set
The feasible set is the set of all points satisfying all constraints.
If the feasible set is called $S$, then a constrained optimization problem is:
\[\min f(x)\]subject to:
\[x\in S\]Only points inside $S$ are allowed.
Optimal Solution
An optimal solution is a feasible point that gives the best objective value.
For minimization:
\[x^* \in S\]is optimal if:
\[f(x^*)\le f(x)\]for every feasible $x\in S$.
For maximization:
\[x^* \in S\]is optimal if:
\[f(x^*)\ge f(x)\]for every feasible $x\in S$.
Optimal Value
The optimal value is the value of the objective function at the optimal solution.
If $x^*$ is optimal, then:
\[z^*=f(x^*)\]The point $x^*$ is the optimal solution.
The scalar $z^*$ is the optimal value.
Decision Process
A typical operational research workflow is:
- identify the problem
- identify the variables
- formulate a mathematical model
- solve the model using an algorithm
- validate the model
- analyze the result
Why Models Matter
A real-world problem must be translated into a mathematical model before it can be solved.
The model should specify:
- what we choose
- what we want
- what limits us
In mathematical terms:
- what we choose → decision variables
- what we want → objective function
- what limits us → constraints
Linear Programming as a Special Case
Linear programming is an optimization problem where:
- the objective function is linear
- the constraints are linear
A general linear programming problem has the form:
\[\min \text{ or } \max \quad c_1x_1+c_2x_2+\cdots+c_nx_n\]subject to linear constraints.
In matrix form, the standard form is:
\[\min c^Tx\]subject to:
\[Ax=b\] \[x\ge 0\]OR Mental Model
Operational research is about making the best decision under limitations.
Examples:
| Situation | Decision | Objective | Constraint |
|---|---|---|---|
| production | how much to produce | maximize profit | limited machines/materials |
| transport | how much to ship | minimize cost | supply and demand |
| diet | how much food to buy | minimize cost | nutrient requirements |
| investment | how much to invest | maximize return | budget and risk limits |
Checklist
You understand optimization foundations if you can:
- identify decision variables
- write an objective function
- distinguish maximization from minimization
- identify constraints
- define the feasible set
- distinguish optimal solution from optimal value
- explain why OR problems are decision problems
- recognize linear programming as a special optimization model
See Also
Exam checkpoint
In exam problems, translate the story into variables, objective, constraints, feasible set, and optimal value. Always state whether the problem is a maximization or minimization and what the units are.