fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <iostream>
  3. #include <string>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <fstream>
  8. #include <map>
  9. #include <set>
  10. #include <ctime>
  11. #include <memory>
  12. #include <thread>
  13. #include <chrono>
  14. #include <random>
  15. #include <regex>
  16. #include  <fstream>
  17. #include <array>
  18. #include <iostream>
  19. #include <vector>
  20. #include <iomanip>
  21. #include <limits>
  22. #include <algorithm>
  23. #include <string>
  24. #include <iostream>
  25. #include <vector>
  26. #include <iomanip>
  27.  
  28. using namespace std;
  29.  
  30. class Simplex {
  31. private:
  32.     vector<vector<double>> tableau;
  33.     int numConstraints;
  34.     int numVariables;
  35.  
  36. public:
  37.     Simplex(int variables, int constraints,
  38.             const vector<vector<double>>& A,
  39.             const vector<double>& B,
  40.             const vector<double>& C) {
  41.  
  42.         numVariables = variables;
  43.         numConstraints = constraints;
  44.  
  45.         // Initialize tableau: rows = constraints + 1, cols = variables + slack + RHS
  46.         tableau.resize(constraints + 1, vector<double>(variables + constraints + 1, 0.0));
  47.  
  48.         // Fill constraint rows
  49.         for (int i = 0; i < constraints; ++i) {
  50.             for (int j = 0; j < variables; ++j) {
  51.                 tableau[i][j] = A[i][j];
  52.             }
  53.             tableau[i][variables + i] = 1.0;  // slack variable
  54.             tableau[i].back() = B[i];
  55.         }
  56.  
  57.         // Fill objective function (negate for maximization)
  58.         for (int j = 0; j < variables; ++j) {
  59.             tableau[constraints][j] = -C[j];
  60.         }
  61.     }
  62.  
  63.     void printTableau() {
  64.         cout << fixed << setprecision(2);
  65.         for (const auto& row : tableau) {
  66.             for (double val : row) {
  67.                 cout << setw(10) << val << " ";
  68.             }
  69.             cout << endl;
  70.         }
  71.         cout << endl;
  72.     }
  73.  
  74.     void solve() {
  75.         while (true) {
  76.             int pivotCol = -1;
  77.             double minValue = 0;
  78.  
  79.             // Find entering variable (most negative)
  80.             for (int j = 0; j < tableau[0].size() - 1; ++j) {
  81.                 if (tableau[numConstraints][j] < minValue) {
  82.                     minValue = tableau[numConstraints][j];
  83.                     pivotCol = j;
  84.                 }
  85.             }
  86.  
  87.             if (pivotCol == -1) break; // Optimal
  88.  
  89.             // Find leaving variable
  90.             int pivotRow = -1;
  91.             double minRatio = 1e9;
  92.             for (int i = 0; i < numConstraints; ++i) {
  93.                 if (tableau[i][pivotCol] > 0) {
  94.                     double ratio = tableau[i].back() / tableau[i][pivotCol];
  95.                     if (ratio < minRatio) {
  96.                         minRatio = ratio;
  97.                         pivotRow = i;
  98.                     }
  99.                 }
  100.             }
  101.  
  102.             if (pivotRow == -1) {
  103.                 cout << "Unbounded solution." << endl;
  104.                 return;
  105.             }
  106.  
  107.             // Pivot
  108.             double pivot = tableau[pivotRow][pivotCol];
  109.             for (double& val : tableau[pivotRow])
  110.                 val /= pivot;
  111.  
  112.             for (int i = 0; i <= numConstraints; ++i) {
  113.                 if (i != pivotRow) {
  114.                     double factor = tableau[i][pivotCol];
  115.                     for (int j = 0; j < tableau[0].size(); ++j) {
  116.                         tableau[i][j] -= factor * tableau[pivotRow][j];
  117.                     }
  118.                 }
  119.             }
  120.  
  121.             cout << "Tableau after pivot:\n";
  122.             printTableau();
  123.         }
  124.  
  125.         cout << "Optimal value of Z = " << tableau[numConstraints].back() << endl;
  126.     }
  127. };
  128.  
  129. int main() {
  130.     int variables, constraints;
  131.  
  132.     cout << "Enter number of variables: ";
  133.     cin >> variables;
  134.  
  135.     cout << "Enter number of constraints: ";
  136.     cin >> constraints;
  137.  
  138.     vector<vector<double>> A(constraints, vector<double>(variables));
  139.     vector<double> B(constraints);
  140.     vector<double> C(variables);
  141.  
  142.     cout << "\nEnter coefficients of constraints (A matrix):\n";
  143.     for (int i = 0; i < constraints; ++i) {
  144.         cout << "Constraint " << i + 1 << ": ";
  145.         for (int j = 0; j < variables; ++j) {
  146.             cin >> A[i][j];
  147.         }
  148.     }
  149.  
  150.     cout << "\nEnter right-hand side (B vector):\n";
  151.     for (int i = 0; i < constraints; ++i) {
  152.         cout << "B[" << i + 1 << "]: ";
  153.         cin >> B[i];
  154.     }
  155.  
  156.     cout << "\nEnter coefficients of the objective function (C vector):\n";
  157.     for (int j = 0; j < variables; ++j) {
  158.         cout << "C[" << j + 1 << "]: ";
  159.         cin >> C[j];
  160.     }
  161.  
  162.     Simplex solver(variables, constraints, A, B, C);
  163.  
  164.     cout << "\nInitial Tableau:\n";
  165.     solver.printTableau();
  166.  
  167.     solver.solve();
  168.  
  169.     return 0;
  170. }
  171.  
  172. /*   /\_/\
  173. *   (= ._.)
  174. *   / >  \>
  175. */
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
2
2
1
2
1
2
2
2
2
2
stdout
copy 
Enter number of variables: Enter number of constraints: 
Enter coefficients of constraints (A matrix):
Constraint 1: Constraint 2: 
Enter right-hand side (B vector):
B[1]: B[2]: 
Enter coefficients of the objective function (C vector):
C[1]: C[2]: 
Initial Tableau:
      1.00       2.00       1.00       0.00       2.00 
      1.00       2.00       0.00       1.00       2.00 
     -2.00      -2.00       0.00       0.00       0.00 

Tableau after pivot:
      1.00       2.00       1.00       0.00       2.00 
      0.00       0.00      -1.00       1.00       0.00 
      0.00       2.00       2.00       0.00       4.00 

Optimal value of Z = 4.00
https://ideone.com/E84Lv9
language:
C++ (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!