Code solution of simplex method (including super detailed code notes and the whole flow chart)

Function implementation flow chart of code ：

The process is solved by taking the minimum value of the objective function as the standard form , That is, when the objective function needs to solve the maximum value , Inverse the objective function first , Then find the minimum value of the inverse function .

Implementation code

#include "pch.h"
#include <iostream>
#include<stdio.h>
#include<stdlib.h> 
#include<string.h>
#include<math.h>
#include<iostream>
using namespace std;

#define M 1000 // Big M Count 
#define zero 0.000001 // As 0 Substitution of 
#define maxn 100 // Represents the size of the array 

float matrix[maxn][maxn], x[maxn]; //x An array of solutions  //matrix It represents the coefficient matrix （ Store the coefficients in the constraint matrix and the coefficients of the objective function ）
int a[maxn]; // Determine which are base variables  0: Non basic ,1: Basics 
int m; 		// The number of variables in the equation 
int n;		// Number of constraints 
int type;	// Find the type of maximum and minimum value ,0: Minimum  1: Maximum 
int Loose_variable; 	// Number of relaxation variables 
int Remain_variable;	// Number of remaining variables 
int Artificial_variable;	// Number of manual variables 
int total_variable;		// Total variables 
int base[maxn];			// Store subscripts of base variables 
int T = 0;		// Used to store the number of base variables 
int Duo = 0;			// Whether there is a sign of multiple solutions 
int non = 0;	// When non by 1 The time of zero represents that there is no feasible solution at present 

void Other_update(int in, int temp) {
    
	float c = 0;
	for (int i = 0; i <= n; i++) {
    
		c = matrix[i][in] / matrix[temp][in];

		if (i != temp) {
           // Except for the main element line   Process other rows 
			for (int j = 0; j <= total_variable; j++) {
    
				matrix[i][j] = matrix[i][j] - matrix[temp][j] * c;		//aij-asj/ask·aik→aij  and  bi-bs/ask·aik→bi
			}
		}
	}
}

void Main_update(int in, int temp) {
    	//temp Corresponding to the main element line ,in Corresponding to the main element column 
	for (int i = 0; i <= total_variable; i++) {
    
		if (i != in) {
    
			matrix[temp][i] = matrix[temp][i] / matrix[temp][in]; // bs/ask → bs
		}
	}
	matrix[temp][in] = 1;			// 1→ask
}

int ExchangeOut(int *temp, int in) {
    		// Find the commutative base 
	int i;
	float minn = 10000;
	for (i = 0; i < n; i++) {
          // For all aik>0 Calculate the relevant θ,θ=bi/aik.（ It's actually matrix[i][total_variable] / matrix[i][in]） （k Yes, use it in）
		if (fabs(matrix[i][in]) >= zero && (matrix[i][total_variable] / matrix[i][in] >= 0) && minn > matrix[i][total_variable] / matrix[i][in]) {
    
			minn = matrix[i][total_variable] / matrix[i][in];
			*temp = i;
		}
	}

	for (i = 0; i < total_variable; i++) {
    
		if (a[i] == 1 && matrix[*temp][i] == 1)
			return i;			// Returns the subscript of the swapped out variable （ The premise is that this variable is the base variable ）
	}
}

int Is_unbounded(int in) {
       // Determine the unbounded solution 
	float maxx = -1;
	for (int i = 0; i < n; i++) {
    
		if (fabs(matrix[i][in]) >= zero && maxx < matrix[i][total_variable] / matrix[i][in]) {
    
			maxx = matrix[i][total_variable] / matrix[i][in];
		}
	}
	if (maxx < 0)  return 1;
	return 0;
}

void FinalResult() {
    	// Output final results 
	if (type == 0) printf("\n The minimum value of the objective function is : %f", -matrix[n][total_variable]);
	else printf("\n The maximum value of the objective function is : %f, ", matrix[n][total_variable]);
	cout << " The corresponding base feasible solution is ：(";
	for (int i = 0; i < total_variable - 1; i++) {
    
		printf("%.2f,", x[i]);
	}
	printf("%.2f)\n", x[total_variable - 1]);
	
	cout << " The solution vector of the original problem is ：(";
	for (int i = 0; i < m - 1; i++) {
    
		printf("%.2f,", x[i]);
	}
	printf("%.2f)\n", x[m - 1]);
}

int Duojie() {
    			// Determination of the test number of non basic variables 
	for (int i = 0; i < total_variable; i++) {
    			// Determine in the test number corresponding to the non base variable 
		int flag = 0;
		for (int j = 0; j < T; j++) {
    
			if (i + 1 == base[j]) {
    			// Represents the corresponding base variable 
				flag = 1;
				break;
			}
		}

		if (!flag) {
    			// Handle the inspection number of non base variables 
			if (fabs(matrix[n][i]) <= zero) {
    		// Think of existence as 0 The situation of 
				printf(" There are an infinite number of optimal solutions \n");
				Duo = 1;
				return 0;
			}
		}
	}
	return 0;
}

void Is_solution() {
    
	for (int i = m + Loose_variable + Remain_variable; i < total_variable; i++) {
    
		if (fabs(x[i]) >= zero) {
         // Represents that there is a non-zero artificial variable in the base variable 
			printf(" There is no feasible solution to this problem \n");			// No feasible solution 
			non = 1;
			return;
		}
	}
}

int Min_test() {
            // Find the subscript of the minimum inspection number 
	int temp = 0;
	float min = matrix[n][0];
	for (int i = 1; i < total_variable; i++) {
    
		if (min > matrix[n][i]) {
    
			min = matrix[n][i];
			temp = i;
		}
	}
	return temp;
}

int test_number() {
    		// All inspection numbers are the same as 0 Compare 
	for (int i = 0; i < total_variable; i++) {
    
		if (fabs(matrix[n][i]) >= zero) {
    
			if (matrix[n][i] < 0)
				return 0;
		}
	}
	return 1;
}

void iteration_Result() {
    		// Output the results of each iteration 
	cout << endl;
	for (int i = 0; i < total_variable; i++) {
    
		printf(" X%d", i + 1);
	}
	cout << " ( The solution vector corresponding to this process )";
	cout << endl;

	cout << " ";
	for (int i = 0; i < total_variable; i++) {
    
		printf("%12.2f", x[i]);
	}

	if (type == 1)
		printf(" f(max)=%f\n", matrix[n][total_variable]);
	else printf(" f(min)=%f\n", matrix[n][total_variable]);
}

void Print_factor() {
    		// Output intermediate coefficient and inspection number 
	memset(base, 0, sizeof(base));			// Clear the base variable array 
	T = 0;
	int temp = 0;
	cout << "—————————————————————————————————————————————————————\n";
	for (int i = 0; i < n; i++) {
    
		for (int k = temp; k < total_variable; k++) {
    
			if (a[k] == 1) {
    
				printf("X%d ", k + 1);		// Output base variable symbol 
				base[T++] = k + 1;				// Store base variable subscripts in base in 
				temp = k + 1;
				k = total_variable;
			}
		}

		for (int j = 0; j <= total_variable; j++) {
    
			printf("%12.2f", matrix[i][j]);
		}
		cout << endl;
	}

	cout << "δj ";
	for (int j = 0; j <= total_variable; j++) {
    
		printf("%12.2f", matrix[n][j]);				// The value here is the inspection number Rj
	}
	cout << endl;
}

void Base_solution() {
    	// Find the value of the base variable , The non base variable is set to 0
	for (int i = 0; i < n; i++)
		for (int j = 0; j < total_variable; j++)
			if (matrix[i][j] == 1 && a[j] == 1) {
       // Suppose a variable is the base variable , Find it in this line 
				x[j] = matrix[i][total_variable];		// Consider that all non base variables are set to 0, Then the value of the base variable is equal to the right value of the equation 
				j = total_variable;
			}
	for (int i = 0; i < total_variable; i++)
		if (a[i] == 0) x[i] = 0;			// Non base variables are set to 0
}

void Print_head() {
    		// Print header 
	cout << "\n\n The results and process are as follows ：" << endl;
	cout << "**************************************************************************************************************" << endl;
	cout << "X";
	for (int i = 1; i <= total_variable; i++)
		printf(" a%d", i);
	printf(" b\n");
}

void Initial_test() {
      // Calculate the initial inspection number 
	if (Artificial_variable != 0) {
    
		for (int i = m + Loose_variable + Remain_variable; i < total_variable; i++) {
    
			for (int j = 0; j < n; j++) {
    
				if (matrix[j][i] == 1) {
           // Determine which constraint lines have artificial variables added 
					for (int k = 0; k <= total_variable; k++) {
    	// This part is large M The test number in the rule Rj The calculation of , And deposit in matrix Matrix 
						matrix[n][k] = matrix[n][k] - matrix[j][k] * M;		// Here M The coefficient corresponding to the artificial variable 
					}
					j = n;		// Jump out of current loop 
				}
			}
		}
	}
}

void Initial_base() {
    	// Initial set base variable , The corresponding subscript exists a Array   The remaining and manual variables are initially set as base variables 
	int i;
	for (i = 0; i < m + Loose_variable; i++)
		a[i] = 0;
	for (i = m + Loose_variable; i < total_variable; i++)		// The initial assumption is that some variables are base variables （ The number of base variables should be the same as the number of constraints ）
		a[i] = 1;					// from m + Loose_variable To s-1 Corresponding x Set as base variable 
}

void Merge(float loose[][maxn], float remain[][maxn], float artificial[][maxn], float b[]) {
    
	int i, j;			// In the coefficient matrix, the relaxation （ Negative variables ） A merger , Then merge the remaining variables and artificial variables outward in turn 
	for (i = 0; i < n; i++) {
    
		for (j = m; j < m + Loose_variable; j++) {
    
			if (loose[i][j - m] != -1) matrix[i][j] = 0;
			else matrix[i][j] = -1;
		}

		for (j = m + Loose_variable; j < m + Loose_variable + Remain_variable; j++) {
    
			if (remain[i][j - m - Loose_variable] != 1) matrix[i][j] = 0;
			else matrix[i][j] = 1;
		}

		for (j = m + Loose_variable + Remain_variable; j < total_variable; j++) {
    
			if (artificial[i][j - m - Loose_variable - Remain_variable] != 1) matrix[i][j] = 0;
			else matrix[i][j] = 1;
		}
		matrix[i][total_variable] = b[i];			// At the end of each row in the matrix is the right value of the equation 
	}

	// The following is the objective function z Setting of coefficient 
	for (i = m; i < m + Loose_variable + Remain_variable; i++)// Set the coefficient of relaxation variable and residual variable 0
		matrix[n][i] = 0;
	for (i = m + Loose_variable + Remain_variable; i < total_variable; i++)
		matrix[n][i] = M;		// Using a large M The laws of , stay martix Set a large coefficient at the corresponding artificial variable of the matrix 
	matrix[n][total_variable] = 0;
}

void SetZero(float c[][maxn], int row, int vol) {
    
	for (int i = 0; i < n; i++) {
    
		if (i != row)
			c[i][vol] = 0;	// Make sure that each type of array is on the current line （row） Of vol As a 1, Other rows （ Other constraint lines ） Set to 0
	}
}

void Input(float b[], int expression[]) {
         // A program that processes input 
	cout << " The number of variables in the equation ：" << endl;
	cin >> m;
	cout << " Number of constraints ：" << endl;
	cin >> n;

	cout << " Enter the constraint equation coefficients in sequence 、 The right value of the equation 、 Equation type ( 0:<= 1:= 2:>=n )：" << endl;
	for (int i = 0; i < n; i++) {
    
		for (int j = 0; j < m; j++)
			cin >> matrix[i][j];
		cin >> b[i] >> expression[i];
	}

	cout << " Enter the objective function Z The coefficient in :" << endl; /*  Input z */
	for (int i = 0; i < m; i++)
		cin >> matrix[n][i];			//matrix In the n Row stores the coefficients in the objective function 

	cout << " Select the solution type ( 0:Min 1:Max )：" << endl; // Enter the maximum or minimum value 
	do {
    
		cin >> type;			//type Can only choose 0 or 1
		if (type != 0 && type != 1) printf(" Input error !");
	} while (type != 0 && type != 1);

	if (type == 1)		// When the objective function is maximized 
		for (int i = 0; i < m; i++)		// The objective function Z The inverse of the coefficient in 
			matrix[n][i] = -matrix[n][i];
}

void Normal(float b[], int expression[]) {
    
	float loose[maxn][maxn];	// Relax variable array 
	float remain[maxn][maxn];	// Array of remaining variables 
	float artificial[maxn][maxn]; // Artificial variable array 
	Loose_variable = Remain_variable = Artificial_variable = 0;
	for (int i = 0; i < n; i++) {
         // Determine the inequality of constraints 
		if (expression[i] == 0) {
          // Represents that the input symbol is less than or equal to 
			remain[i][Remain_variable++] = 1;		// Add a remaining variable 
			SetZero(remain, i, Remain_variable - 1); // Ensure that the coefficients for the remaining rows of the column are 0
		}

		if (expression[i] == 1) {
          // be equal to 
			artificial[i][Artificial_variable++] = 1;		// Add an artificial variable 
			SetZero(artificial, i, Artificial_variable - 1);  // Ensure that the coefficients for the remaining rows of the column are 0
		}

		if (expression[i] == 2) {
          // Greater than or equal to 
			artificial[i][Artificial_variable++] = 1;	// Subtract a relaxation variable , Plus an artificial variable 
			loose[i][Loose_variable++] = -1;
			SetZero(artificial, i, Artificial_variable - 1);
			SetZero(loose, i, Loose_variable - 1);
		}
	}

	total_variable = Loose_variable + Remain_variable + Artificial_variable + m;  // Increase the number of three variables and the number of variables of the original objective function （m） Make up the total number of variables 
	Merge(loose, remain, artificial, b);		// Merge the coefficient sum corresponding to the increased variable into the original matrix coefficient 
	Initial_base(); // Initial set base variable , The corresponding subscript exists a Array 
	Initial_test(); // Calculate the initial inspection number 
	Print_head(); // Print header 
}

void Simplex() {
                // Simplex algorithm 
	int in;	// Base variable 
	int out; // Out of base variable 
	int temp = 0;

	while (1) {
         // Loop to find the optimal solution 
		Base_solution(); // Find the basic feasible solution 
		Print_factor(); // Print the intermediate results （ coefficient matrix ） And inspection number 
		iteration_Result(); // Output solution group   The non base variable is 0  The solution of each iteration and the value of the objective function 
		if (!test_number()) in = Min_test(); // Find the subscript of the minimum inspection number , The subscript corresponding to the commutation base 
		else {
    
			cout << "—————————————————————————————————————————————————————\n";
			if (Artificial_variable != 0) Is_solution();    // Judge whether there is a feasible solution 
			Duojie();   // It is necessary to determine multiple optimal solutions 

			if (!non) {
    		// When there is no case that there is no feasible solution , Then the optimal solution is output .
				if (Duo == 1) {
    
					FinalResult();	// Output final results （ Optimal objective function value ）
				}
				else {
    		// Represents the case where there is a unique solution 
					cout << " There is a unique optimal solution " << endl;
					FinalResult();
				}
			}
			cout << "\n**************************************************************************************************************" << endl;
			return;
		}

		if (Is_unbounded(in)) {
             // Judge the unbounded situation 
			cout << "—————————————————————————————————————————————————————\n";
			printf(" The problem is unbounded \n!");
			cout << "\n**************************************************************************************************************" << endl;
			return;
		}
		out = ExchangeOut(&temp, in); // Find the commutative base 
		Main_update(in, temp);  // Main element line 、 Main element column update 
		Other_update(in, temp); // Update and transform other row and column elements 
		swap(a[in], a[out]);   // Because the base variables in and out are exchanged , So the array that stores their Subscripts a The values in are also exchanged 
	}
}

int main() {
    
	int expression[maxn];// Store input symbols （ Greater than or equal to ）
	float b[maxn]; // The right value of the equation 

	Input(b, expression);      // Enter the question 
	Normal(b, expression);     // Turn into standard 
	Simplex();                 // Solving process of simplex method 

	system("pause");
	return 0;
}

The results of the case