Simplex Method Implementation

A numerical implementation of the Simplex method for linear programming, from first principles.

Table of Contents

• Overview
• Tech Stack
• Architecture
• Theoretical Background
• Installation
• Usage
• API Reference
• Case Study
• Testing
• Limitations
• Roadmap
• License

Overview

The Simplex method is a widely used algorithm for solving linear programming problems. It is an iterative method that starts with a basic feasible solution and improves it at each step until an optimal solution is found.

Tech Stack

• Python 3.8+
• NumPy
• SciPy

Architecture

simplex-method/
|--- notebooks/
|    |--- exploration.py
|--- src/
|    |--- simplex.py
|    |--- tableau.py
|    |--- utils.py
|--- tests/
|    |--- test_simplex.py
|    |--- test_tableau.py
|--- results/
|    |--- findings.md

Theoretical Background

The Simplex method is based on the concept of a tableau, which is a matrix representation of the linear programming problem. The tableau is used to store the coefficients of the variables and the constraints, and to perform the necessary calculations to find the optimal solution.

The Simplex method consists of two main phases: the Phase I and Phase II. In Phase I, the method finds a basic feasible solution by minimizing the artificial variables. In Phase II, the method finds the optimal solution by maximizing the objective function.

Installation

To install the Simplex method implementation, run the following commands:

pip install -r requirements.txt
 git clone https://github.com/user/simplex-method.git

Usage

To use the Simplex method implementation, create an instance of the Simplex class and call the solve method:

from src.simplex import Simplex

# Define the coefficients of the objective function and the constraints
c = np.array([3, 4])
b = np.array([7, 11, 8])
A = np.array([[1, 2], [3, 2], [2, 1]])

# Create an instance of the Simplex class and solve the problem
simplex = Simplex(c, A, b)
result = simplex.solve()
print(result)

API Reference

• Simplex(c, A, b): Creates an instance of the Simplex class.
• solve(): Solves the linear programming problem using the Simplex method.

Case Study

See the findings.md file for a written analysis of the results.

Testing

To run the tests, execute the following command:

pytest tests/

Limitations

The current implementation only supports problems with a small number of variables and constraints.

Roadmap

• Improve the performance of the implementation for large problems.
• Add support for more advanced features, such as integer programming.

License

This implementation is licensed under the MIT License.

Requirements

pip install -r requirements.txt