simplex_example.C File Reference

Simplex Algorithm: Linear Programming Optimization. More...

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <Simplex.H>
#include <tclap/CmdLine.h>

Include dependency graph for simplex_example.C:

Go to the source code of this file.

Functions
string	state_to_string (Simplex< double >::State state)
	Helper to print solution state.
void	demo_production_planning ()
	Classic example: Production Planning.
void	demo_diet_problem ()
	Diet Problem (classic LP problem)
void	demo_resource_allocation ()
	Transportation Problem (simplified)
void	demo_special_cases ()
	Demonstrate unbounded and infeasible cases.
void	demo_algorithm_steps ()
	Demonstrate the algorithm steps.
int	main (int argc, char *argv[])

Detailed Description

Simplex Algorithm: Linear Programming Optimization.

This example demonstrates the Simplex algorithm for solving linear programming (LP) problems - one of the most important algorithms in optimization and operations research. Despite exponential worst-case complexity, Simplex is remarkably efficient in practice.

What is Linear Programming?

Linear programming finds the optimal value (maximum or minimum) of a linear objective function subject to linear constraints.

Standard Form

Maximize:   Z = c₁x₁ + c₂x₂ + ... + cₙxₙ
Subject to: a₁₁x₁ + a₁₂x₂ + ... ≤ b₁
            a₂₁x₁ + a₂₂x₂ + ... ≤ b₂
            ...
            xᵢ ≥ 0 (non-negativity)

Key Concepts

• Decision variables: x₁, x₂, ..., xₙ (what we're optimizing)
• Objective function: What we want to maximize/minimize
• Constraints: Linear inequalities that must be satisfied
• Feasible region: Set of all points satisfying constraints
• Optimal solution: Point in feasible region maximizing objective

The Simplex Algorithm

How It Works

1. Start: Begin at a vertex (corner) of the feasible region
2. Pivot: Move to an adjacent vertex with better objective value
3. Repeat: Continue until no better adjacent vertex exists
4. Optimal: Current vertex is optimal

Key Insight

The optimal solution always occurs at a vertex (corner point) of the feasible region. Simplex efficiently explores vertices.

Algorithm Steps

1. Convert to standard form (slack variables for ≤ constraints)
2. Find initial basic feasible solution
3. While not optimal: a. Choose entering variable (improves objective) b. Choose leaving variable (maintains feasibility) c. Pivot (update tableau)
4. Extract optimal solution

Complexity

• Worst case: O(2^n) - exponential (rarely occurs)
• Average case: O(n + m) iterations where m = constraints
• Practical: Typically very fast, often faster than polynomial algorithms

Note: Despite exponential worst case, Simplex is usually efficient in practice. Interior-point methods guarantee polynomial time but are often slower for typical problems.

Applications

Business and Economics

• Production planning: Maximize profit given resource limits
• Supply chain: Minimize transportation costs
• Finance: Portfolio optimization (Markowitz model)
• Marketing: Media mix optimization

Engineering

• Scheduling: Resource allocation, job scheduling
• Network flow: Routing and capacity planning
• Design: Optimal structural design

Operations Research

• Transportation: Vehicle routing, logistics
• Assignment: Job assignment, matching problems
• Cutting stock: Material cutting optimization

Example Problem Types

Maximization

• Maximize profit subject to resource constraints
• Maximize production given material limits

Minimization

• Minimize cost subject to demand requirements
• Minimize transportation costs

Limitations

• Linearity: Only works for linear objective and constraints
• Continuous: Variables are continuous (not discrete)
• Deterministic: No uncertainty in parameters

For non-linear or discrete problems, use:

• Integer Programming: For discrete variables
• Non-linear Programming: For non-linear functions
• Stochastic Programming: For uncertainty

Usage

# Run simplex example
./simplex_example

See also

Simplex.H Simplex algorithm implementation

mincost_flow_example.cc Network flow (can be solved with LP)

Author

Leandro Rabindranath León

Definition in file simplex_example.C.

Function Documentation

demo_algorithm_steps()

void demo_algorithm_steps

(

)

Demonstrate the algorithm steps.

Definition at line 460 of file simplex_example.C.

References Aleph::maps().

Referenced by main().

demo_diet_problem()

void demo_diet_problem

(

)

Diet Problem (classic LP problem)

Find minimum cost diet meeting nutritional requirements:

• Food 1: $2/unit, 3g protein, 1g fat
• Food 2: $4/unit, 4g protein, 3g fat
• Need: at least 12g protein, at least 6g fat

Note: This is a minimization problem. Minimize: C = 2*x1 + 4*x2 Subject to: 3*x1 + 4*x2 >= 12 (protein) 1*x1 + 3*x2 >= 6 (fat)

Convert to standard form (maximization): Maximize: -C = -2*x1 - 4*x2 Convert >= to <= by multiplying by -1: -3*x1 - 4*x2 <= -12 -1*x1 - 3*x2 <= -6

Definition at line 267 of file simplex_example.C.

References Aleph::maps(), and state_to_string().

Referenced by main().

demo_production_planning()

void demo_production_planning

(

)

Classic example: Production Planning.

A factory produces two products (A and B):

• Product A: $40 profit, needs 1 hr labor, 2 hrs machine
• Product B: $30 profit, needs 1 hr labor, 1 hr machine
• Available: 40 labor hours, 60 machine hours

Maximize: Z = 40*xA + 30*xB Subject to: xA + xB ≤ 40 (labor) 2*xA + xB ≤ 60 (machine)

Definition at line 186 of file simplex_example.C.

References Aleph::maps(), and state_to_string().

Referenced by main().

demo_resource_allocation()

void demo_resource_allocation

(

)

Transportation Problem (simplified)

Allocate resources to maximize output:

• Resource X: 2 units capacity, yields 5 per unit
• Resource Y: 3 units capacity, yields 4 per unit
• Resource Z: 4 units capacity, yields 3 per unit
• Total capacity limit: 6 units

Definition at line 334 of file simplex_example.C.

References Aleph::maps(), state_to_string(), and y.

Referenced by main().

demo_special_cases()

void demo_special_cases

(

)

Demonstrate unbounded and infeasible cases.

Definition at line 402 of file simplex_example.C.

References Aleph::maps(), and state_to_string().

Referenced by main().

main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 518 of file simplex_example.C.

References demo_algorithm_steps(), demo_diet_problem(), demo_production_planning(), demo_resource_allocation(), demo_special_cases(), and Aleph::maps().

state_to_string()

string state_to_string

(

Simplex< double >::State

state

)

Helper to print solution state.

Definition at line 161 of file simplex_example.C.

Referenced by demo_diet_problem(), demo_production_planning(), demo_resource_allocation(), and demo_special_cases().