An optimal solution is a decision that satisfies every constraint and achieves the required minimum or maximum objective value. In a minimization problem, no other feasible decision has a smaller objective value. In a maximization problem, no other feasible decision has a larger objective value. An optimization problem may have one unique optimal solution or several different decisions with the same optimal objective value. It may also have no optimal solution if the feasible set is empty or the objective is unbounded in the required direction. In some problems, a finite optimum exists but is not attained, such as when the feasible set is open and the best value can only be approached. The distinction between a feasible and optimal solution is fundamental: feasibility checks validity, while optimality checks quality among valid decisions.
Optimal Solutions
An optimal solution is a feasible decision that produces the best possible objective value according to the optimization problem.
Minimization: f(x*) ≤ f(x) for all x ∈ S
Maximization: f(x*) ≥ f(x) for all x ∈ S
Explanation
Variables
x*: optimal decision vector
x: any feasible decision vector
f: objective function
S: feasible set
Example or application
A company can produce up to 10 units. If each unit generates $5 profit and there are no other restrictions, producing 10 units is optimal because it gives the greatest feasible profit of $50.
Definition
An optimal solution is a feasible decision vector whose objective value is at least as good as that of every other feasible decision, according to the specified minimization or maximization objective.
Purpose
The purpose is to identify the best allowable decision according to the exact objective and constraints of the model.
Importance
Optimal solutions provide a mathematical basis for comparing alternatives and selecting decisions that make the best use of available resources.
Learning Objectives
Define an optimal solution.
Distinguish optimality from feasibility.
Interpret optimality for minimization and maximization.
Recognize unique and multiple optimal solutions.
Identify situations where an optimal solution may not exist.
Key Concepts
Optimal solution
Optimal objective value
Feasibility
Global optimality
Multiple optima
Unbounded objective
Working Principle
An optimization method first respects the feasible set and then searches for a decision that gives the best objective value. The final candidate must satisfy the constraints and meet the mathematical definition of optimality.
Process
Define the objective function.
Determine the feasible set.
Generate or analyze feasible candidate decisions.
Evaluate their objective values.
Compare the values in the required direction.
Verify that the selected decision satisfies every constraint.
Determine whether the optimum is unique or multiple.
Applications
Maximum-profit production planning
Minimum-cost transportation
Efficient energy allocation
Engineering design selection
Optimal staff scheduling
Worked Example
Maximize Z = 3x + 2y subject to x + y ≤ 4, x ≥ 0, and y ≥ 0. The corner points are (0, 0), (4, 0), and (0, 4). Their objective values are 0, 12, and 8, respectively. Therefore, (4, 0) is an optimal solution, and the maximum objective value is Z = 12.
Common Misconceptions
Every feasible solution is not necessarily optimal.
The optimal objective value and the optimal decision vector are not the same thing.
An optimal solution may not be unique.
A mathematically optimal result is optimal only for the model that was formulated.
Practice Questions
Define an optimal solution.
What is the difference between feasibility and optimality?
Find the maximum of Z = 2x + y over x + y ≤ 5, x ≥ 0, y ≥ 0.
Can an optimization problem have multiple optimal solutions?
What does an unbounded objective value mean?
Key Takeaway
An optimal solution is not merely an allowed decision; it is the best allowed decision according to the specified objective.
Prerequisites
Objective Functions
Constraints and Feasible Solutions
Feasible and Infeasible Regions
Reference
Bertsimas, D., and Tsitsiklis, J. N. Introduction to Linear Optimization.
Hillier, F. S., and Lieberman, G. J. Introduction to Operations Research.
Related Topics
Feasible and Infeasible Regions
Local and Global Optima
Maximization and Minimization Problems
Optimization Algorithms and Solution Methods
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Source verification pending; check an authoritative textbook, university, standards body, or peer-reviewed source.
Suggest a correction or source · More in Optimization & Operations Research