Optimization Methods: Linear Programming and Project Analysis

Operations Research and Linear Programming Fundamentals

• Operations Research (OR) Systems: Exact methods, heuristics, deterministic methods, and probabilistic models.
• Linear Programming (LP) Introduction:
  • Elements of the linear model.
  • Feasible region (or possible region).
  • Feasible solutions and LP assumptions.

Simplex Method and Duality

LP Certainty Programming and Geometry

• Isostability line and Iso-cost line.
• Possible cases of optimal solutions.
• Heuristic algorithms versus exact algorithms.
• Convex sets and their properties.
• Basic canonical form of the system.

Solutions and Simplex Basics

• Non-basic and basic variables.
• Fundamental Simplex Theorems (First and Second).
• Properties of extreme points of the feasible region.
• Detection of non-optimal, feasible, and multiple solutions.

Advanced Simplex Techniques

• Detection of degenerate cases.
• The Two-Phase Simplex Method.
• Linear programming model problems.

Duality and Sensitivity Analysis

• Relationship between the primal and dual problems.
• Interpretation of shadow prices (dual prices).
• Complementary Slackness Theorem and Unboundedness Theorem.
• Cost interpretation.
• Consequences of coefficient changes in the objective function (for basic variables).
• Consequences of technological changes (for non-basic variables).

Transportation and Assignment Problems

Transportation Problem Modeling

• The Transportation Table.
• Methods to calculate the initial feasible solution.
• What happens if new variables or constraints are added?
• Transportation problem structure and closed circuits.
• Comparison methods for solution evaluation.
• Degenerate transportation problems.
• Resolution of maximization transportation problems.

Optimal Solution Methods

• Methods for finding the optimal solution.
• Exchanges between basic variables.
• The Hungarian Test (for assignment problems).

Project Management (PERT/CPM)

PERT/CPM Elements

• Basic techniques for project management.
• Precedence analysis in PERT.
• Key time metrics: Early Time and Late Time for nodes.
• Chain, cycle route, and critical path.
• Total float of an activity.
• Activities with zero slack ($M_{ij} = 0$).
• Activity duration uncertainty (PERT formulation).

Network Components

• Connected nodes and arcs.
• Arc capacity.
• Critical Path definition.
• Activity notation: $t_{ij}$ (e.g., $t_{Lij} = t_{Eij}$).
• Free float (e.g., activities where $t_{Lij} = 0$).

Network Flow and Integer Programming

Flow and Routing Problems

• Maximum Flow Problem.
• Feasible flow conditions.
• Vehicle Routing Problem (VRP).
• Shortest Path Problem.
• Fixed Charge Problem.

Integer Programming (IP)

• Characteristics of whole programming models (IP).
• Types of IP and basic model assumptions.
• The Knapsack Problem (storage/inventory).
• Traveling Salesman Problem (TSP).
• Why Simplex cannot apply to certain problems (e.g., IP).
• Examples of problem types, characteristics, and resolution methods.

Inventory Management and Diagnostics

Inventory and Cost Analysis

• Logistics function.
• Sensitivity cost and storage cost.
• Economic Order Quantity (EOQ) model.
• Shortage cost (cost of rupture).
• Total Economic Cost (TEC) expression and amendments.
• Point-to-point request or order systems.

LP Diagnostics and Advanced Concepts

• Adjacent basic solutions in degenerate linear models.
• Detection of unbounded problems.
• Detection of infeasible regions.
• Sensitivity analysis.