✦ScienexySCIENCE KNOWLEDGE LIBRARY
reference · SCI-MAT-013-013

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

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.

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