単純形アルゴリズムは線形計画問題を解く(『アルゴリズム導論』に基づいて実現する)

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MAXN  = 100;
const double INF = 999999.0;
const double EPS = 1e-9;
double b[MAXN]; //constraint in each equation
double x[MAXN]; //last result
double a[MAXN][MAXN]; //coefficient of each non-basic variable
double c[MAXN]; //coefficient of target function
int n; //denote number of non-basic variables as n
int m; //denote number of basic variables as m
int z; //target function
bool isBasic[MAXN]; //mark the basic

double b1[MAXN]; //constraint in each equation
double a1[MAXN][MAXN]; //coefficient of each non-basic variable
double c1[MAXN]; //coefficient of target function

void InitializeSimplex();
void Simplex();
void GetPivot(int leave, int enter);

int main() {

    //input a linear programming as slack form
    InitializeSimplex();
    Simplex();
    cout << "the optimal solution is " << z << endl;
    return 0;
}

void InitializeSimplex(){
    cin >> n >> m;
    memset(a, 0.0, sizeof(a));
    memset(isBasic, false, sizeof(isBasic));
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i+n];
        for (int j = 1; j <= n; j++) {
            cin >> a[i+n][j];
        }
        isBasic[i+n] = true;
    }
    z = 0;
}

void Simplex() {
    int z = 0;
    while (1) {
        //find s non-basic variable to enter.if all c[] are less than 0, break;
        bool flag = false;
        int enter = 0;
        for (int i = 1; i <= n+m; i++) {
            if (!isBasic[i] && c[i] > 0) {
                flag = true;
                enter = i;
                break;
            }
        }
        if (!flag) break;

        //find a basic variable to leave
        double minimalConstraint = INF;
        int leave = 0;
        for (int i = 1; i <= n+m; i++) {
            if (isBasic[i] && a[i][enter] > 0) {
                if (minimalConstraint > b[i] / a[i][enter]) {
                    minimalConstraint = b[i] / a[i][enter];
                    leave = i;
                }
            }
        }

        //unbounded
        if (fabs(minimalConstraint - INF) < EPS) {
            cout << "UNBOUNDED!" << endl;
            return;
        }
        else {
            // cout <