Simplex Algorithm Implementation for Linear Programming

Introduction

This repository contains a C++ implementation of the Simplex algorithm, a popular method for solving linear programming (LP) problems. The Simplex algorithm is used to find the optimal solution to a linear objective function, subject to a set of linear constraints. This implementation supports maximization problems with constraints in the form of inequalities (≤).

The code is designed to be simple and easy to understand, making it suitable for educational purposes or as a starting point for more advanced implementations.

---

How It Works

The Simplex algorithm works by iteratively improving the solution to a linear programming problem. It operates on a tableau, which is a matrix representation of the LP problem. The algorithm proceeds as follows:

1. Initialization: The tableau is initialized with the coefficients of the objective function and constraints. Slack variables are added to convert inequality constraints into equalities.

2. Pivot Column Selection: The algorithm identifies the most negative entry in the bottom row of the tableau (corresponding to the objective function). This column is chosen as the pivot column.

3. Pivot Row Selection: The algorithm performs the ratio test to determine the pivot row. The pivot element is the intersection of the pivot column and pivot row.

4. Pivot Operation: The pivot row is normalized, and the tableau is updated to eliminate the pivot column from all other rows.

5. Termination: The algorithm terminates when there are no negative entries in the bottom row, indicating that an optimal solution has been found. If no pivot row can be found, the problem is unbounded.

---

Usage

To use this implementation, follow these steps:

1. Input the Problem:

   • Enter the number of variables and constraints.
   • Input the coefficients of the objective function (to be maximized).
   • Input the coefficients of the constraints (in ≤ form).

2. Run the Algorithm:

   • The program will construct the tableau and apply the Simplex algorithm to find the optimal solution.

3. Output:

   • The program will output the optimal value of the objective function.

---

Example

Input:

Enter the number of variables: 2
Enter the number of constraints: 2
Enter the coefficients of the objective function (maximize):
3 5
Enter the coefficients of the constraints (<= form):
1 2 18
2 1 12

Output:

Optimal value: 36

Explanation:

• The objective function is 3x + 5y.
• The constraints are:
  • x + 2y ≤ 18
  • 2x + y ≤ 12
• The optimal solution is x = 0, y = 7.2, with an optimal value of 36.

---

Functions

The code includes the following functions:

1. findPivotColumn:

   • Identifies the pivot column by finding the most negative entry in the bottom row of the tableau.

2. findPivotRow:

   • Determines the pivot row using the smallest ratio test.

3. pivot:

   • Performs the pivot operation to update the tableau.

4. simplex:

   • Implements the Simplex algorithm to solve the LP problem.

5. main:

   • Handles user input, constructs the tableau, and calls the simplex function to solve the problem.

---

Dependencies

This implementation is written in C++ and has the following dependencies:

• Standard C++ Library: The code uses the <iostream> and <vector> headers for input/output and matrix operations.
• Compiler: A C++ compiler (e.g., g++) is required to build and run the code.

To compile and run the code, use the following commands:

g++ -o simplex simplex.cpp
./simplex

Group Members

Samuel Joseph Chimdindu U22CS1109 Username:Sjay2468

U22CS1122 Luka innocent tumba Username: Tumba2022

Sayudi mohammed Abdulmajeed U22CS1110 Username: Abdulmajeed007

Samuel Emmanuel U22CS1108

Polchong Precious Peter U22CS1105 Username:Pirotkinen

Rotimi oluwatobiloba temilade U22CS1106 Username Toby556

Prosper Chigozie Victor U22CS1121 Username: provibez

Salau Promise .o. U22CS1107 Username:Salau promise

Joshua Simon U22CS1111