fork download 
  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.  
  25. class SimplexSolver {
  26. private:
  27.     // Tableau representation (includes objective function, constraints and RHS)
  28.     std::vector<std::vector<double>> tableau;
  29.  
  30.     // Keep track of basic variables for solution extraction
  31.     std::vector<int> basicVars;
  32.  
  33.     // Number of decision variables (excluding slack/surplus variables)
  34.     int numVars;
  35.  
  36.     // Number of constraints
  37.     int numConstraints;
  38.  
  39.     // Total variables (including slack/surplus)
  40.     int totalVars;
  41.  
  42.     // Flag to track if problem is solved
  43.     bool isSolved;
  44.  
  45.     // Flag to track if problem is unbounded
  46.     bool isUnbounded;
  47.  
  48.     // Flag to track if problem is infeasible
  49.     bool isInfeasible;
  50.  
  51.     // Current iteration count
  52.     int iteration;
  53.  
  54. public:
  55.     // Constructor for the simplex solver
  56.     SimplexSolver() : isSolved(false), isUnbounded(false), isInfeasible(false), iteration(0) {}
  57.  
  58.     // Method to set up the problem from user input
  59.     void setupProblem() {
  60.         std::cout << "======= Enter Linear Programming Problem =======" << std::endl;
  61.  
  62.         // Get number of decision variables
  63.         std::cout << "Enter number of variables: ";
  64.         std::cin >> numVars;
  65.  
  66.         // Get number of constraints
  67.         std::cout << "Enter number of constraints: ";
  68.         std::cin >> numConstraints;
  69.  
  70.         // Calculate total variables (decision + slack)
  71.         totalVars = numVars + numConstraints;
  72.  
  73.         // Initialize the tableau with zeros
  74.         // Rows = constraints + objective function row
  75.         // Columns = variables + slack variables + RHS
  76.         tableau.resize(numConstraints + 1, std::vector<double>(totalVars + 1, 0.0));
  77.  
  78.         // Initialize basicVars to keep track of basic variables (initially slack variables)
  79.         basicVars.resize(numConstraints);
  80.         for (int i = 0; i < numConstraints; i++) {
  81.             basicVars[i] = numVars + i;
  82.         }
  83.  
  84.         // Get objective function coefficients
  85.         std::cout << "\n======= Objective Function (Maximization) =======" << std::endl;
  86.         std::cout << "Enter coefficients of the objective function:" << std::endl;
  87.  
  88.         for (int j = 0; j < numVars; j++) {
  89.             std::cout << "Coefficient of x" << j+1 << ": ";
  90.             std::cin >> tableau[numConstraints][j];
  91.             // Negate the coefficients for standard form (we'll use bottom row for reduced costs)
  92.             tableau[numConstraints][j] = -tableau[numConstraints][j];
  93.         }
  94.  
  95.         // Get constraints
  96.         std::cout << "\n======= Constraints =======" << std::endl;
  97.         for (int i = 0; i < numConstraints; i++) {
  98.             std::cout << "Constraint " << i+1 << ":" << std::endl;
  99.  
  100.             // Get coefficients for each variable in this constraint
  101.             for (int j = 0; j < numVars; j++) {
  102.                 std::cout << "Coefficient of x" << j+1 << ": ";
  103.                 std::cin >> tableau[i][j];
  104.             }
  105.  
  106.             // Add slack variables (identity matrix part)
  107.             tableau[i][numVars + i] = 1.0;
  108.  
  109.             // Get RHS (b value)
  110.             std::cout << "Right-hand side (b" << i+1 << "): ";
  111.             std::cin >> tableau[i][totalVars];
  112.  
  113.             // Check for potential infeasibility at the beginning
  114.             if (tableau[i][totalVars] < 0) {
  115.                 std::cout << "Warning: Negative RHS detected, the problem might be infeasible!" << std::endl;
  116.             }
  117.         }
  118.  
  119.         std::cout << "\nInitial simplex tableau has been created!" << std::endl;
  120.     }
  121.  
  122.     // Method to set up the problem from test case vectors
  123.     void setupFromTestCase(
  124.             const std::vector<double>& objectiveCoeffs,
  125.             const std::vector<std::vector<double>>& constraintCoeffs,
  126.             const std::vector<double>& rhsValues) {
  127.  
  128.         numVars = objectiveCoeffs.size();
  129.         numConstraints = rhsValues.size();
  130.         totalVars = numVars + numConstraints;
  131.  
  132.         // Initialize the tableau with zeros
  133.         tableau.resize(numConstraints + 1, std::vector<double>(totalVars + 1, 0.0));
  134.  
  135.         // Initialize basicVars
  136.         basicVars.resize(numConstraints);
  137.         for (int i = 0; i < numConstraints; i++) {
  138.             basicVars[i] = numVars + i;
  139.         }
  140.  
  141.         // Set objective function (negate for standard form)
  142.         for (int j = 0; j < numVars; j++) {
  143.             tableau[numConstraints][j] = -objectiveCoeffs[j];
  144.         }
  145.  
  146.         // Set constraint coefficients and RHS values
  147.         for (int i = 0; i < numConstraints; i++) {
  148.             // Set coefficients for decision variables
  149.             for (int j = 0; j < numVars; j++) {
  150.                 tableau[i][j] = constraintCoeffs[i][j];
  151.             }
  152.  
  153.             // Set slack variable (1 for current constraint)
  154.             tableau[i][numVars + i] = 1.0;
  155.  
  156.             // Set RHS
  157.             tableau[i][totalVars] = rhsValues[i];
  158.         }
  159.  
  160.         std::cout << "Initial simplex tableau has been created from input data!" << std::endl;
  161.     }
  162.  
  163.     // Method to print the current tableau
  164.     void displayTableau() const {
  165.         std::cout << "\n======= Simplex Tableau (Iteration " << iteration << ") =======" << std::endl;
  166.  
  167.         // Print header row with variable names
  168.         std::cout << std::setw(5) << "Basic";
  169.         for (int j = 0; j < numVars; j++) {
  170.             std::cout << std::setw(10) << "x" + std::to_string(j+1);
  171.         }
  172.         for (int j = 0; j < numConstraints; j++) {
  173.             std::cout << std::setw(10) << "s" + std::to_string(j+1);
  174.         }
  175.         std::cout << std::setw(10) << "RHS" << std::endl;
  176.  
  177.         // Print divider
  178.         std::cout << std::string(5 + 10 * (totalVars + 1), '-') << std::endl;
  179.  
  180.         // Print constraint rows
  181.         for (int i = 0; i < numConstraints; i++) {
  182.             // Show which variable is basic in this row
  183.             if (basicVars[i] < numVars) {
  184.                 std::cout << std::setw(5) << "x" + std::to_string(basicVars[i]+1);
  185.             } else {
  186.                 std::cout << std::setw(5) << "s" + std::to_string(basicVars[i]-numVars+1);
  187.             }
  188.  
  189.             // Print coefficients
  190.             for (int j = 0; j < totalVars + 1; j++) {
  191.                 std::cout << std::setw(10) << std::fixed << std::setprecision(2) << tableau[i][j];
  192.             }
  193.             std::cout << std::endl;
  194.         }
  195.  
  196.         // Print objective function row (Z row)
  197.         std::cout << std::setw(5) << "Z";
  198.         for (int j = 0; j < totalVars + 1; j++) {
  199.             std::cout << std::setw(10) << std::fixed << std::setprecision(2) << tableau[numConstraints][j];
  200.         }
  201.         std::cout << std::endl;
  202.     }
  203.  
  204.     // Method to find the entering variable (most negative coefficient in bottom row)
  205.     int findEnteringVariable() const {
  206.         int enteringVar = -1;
  207.         double minCoeff = -1e-10; // Small epsilon to handle floating-point errors
  208.  
  209.         // Check bottom row (objective function coefficients)
  210.         for (int j = 0; j < totalVars; j++) {
  211.             if (tableau[numConstraints][j] < minCoeff) {
  212.                 minCoeff = tableau[numConstraints][j];
  213.                 enteringVar = j;
  214.             }
  215.         }
  216.  
  217.         return enteringVar;
  218.     }
  219.  
  220.     // Method to find the leaving variable (smallest positive ratio)
  221.     int findLeavingVariable(int enteringVar) {
  222.         int leavingVar = -1;
  223.         double minRatio = std::numeric_limits<double>::max();
  224.  
  225.         for (int i = 0; i < numConstraints; i++) {
  226.             // We only consider positive coefficients in the entering column
  227.             if (tableau[i][enteringVar] > 1e-10) {
  228.                 double ratio = tableau[i][totalVars] / tableau[i][enteringVar];
  229.                 if (ratio < minRatio && ratio >= 0) {
  230.                     minRatio = ratio;
  231.                     leavingVar = i;
  232.                 }
  233.             }
  234.         }
  235.  
  236.         // If no positive ratio is found, the problem is unbounded
  237.         if (leavingVar == -1) {
  238.             isUnbounded = true;
  239.         }
  240.  
  241.         return leavingVar;
  242.     }
  243.  
  244.     // Method to perform pivoting (Gaussian elimination)
  245.     void pivot(int enteringVar, int leavingRow) {
  246.         // Keep track of which variable becomes basic
  247.         basicVars[leavingRow] = enteringVar;
  248.  
  249.         // Get the pivot element
  250.         double pivotElement = tableau[leavingRow][enteringVar];
  251.  
  252.         // Normalize the pivot row (make pivot element 1)
  253.         for (int j = 0; j <= totalVars; j++) {
  254.             tableau[leavingRow][j] /= pivotElement;
  255.         }
  256.  
  257.         // Update all other rows to make the pivot column zeros except at pivot position
  258.         for (int i = 0; i <= numConstraints; i++) {
  259.             if (i != leavingRow) {
  260.                 double multiplier = tableau[i][enteringVar];
  261.                 for (int j = 0; j <= totalVars; j++) {
  262.                     tableau[i][j] -= multiplier * tableau[leavingRow][j];
  263.                 }
  264.             }
  265.         }
  266.     }
  267.  
  268.     // Method to solve the linear program using the Simplex method
  269.     void solve() {
  270.         while (true) {
  271.             iteration++;
  272.             displayTableau();
  273.  
  274.             // Find entering variable (most negative coefficient in objective row)
  275.             int enteringVar = findEnteringVariable();
  276.  
  277.             // If no negative coefficients, the solution is optimal
  278.             if (enteringVar == -1) {
  279.                 isSolved = true;
  280.                 break;
  281.             }
  282.  
  283.             // Find the leaving variable
  284.             int leavingRow = findLeavingVariable(enteringVar);
  285.  
  286.             // If there's no valid leaving variable, the problem is unbounded
  287.             if (isUnbounded) {
  288.                 std::cout << "The problem is unbounded!" << std::endl;
  289.                 break;
  290.             }
  291.  
  292.             // Perform pivot operation
  293.             pivot(enteringVar, leavingRow);
  294.         }
  295.  
  296.         // If the problem is solved, display the result
  297.         if (isSolved) {
  298.             std::cout << "Optimal solution found!" << std::endl;
  299.             displaySolution();
  300.         }
  301.     }
  302.  
  303.     // Method to extract and display the final solution
  304.     void displaySolution() const {
  305.         std::cout << "\n======= Solution =======" << std::endl;
  306.         for (int i = 0; i < numVars; i++) {
  307.             double value = 0;
  308.             // Check if variable is basic
  309.             for (int j = 0; j < numConstraints; j++) {
  310.                 if (basicVars[j] == i) {
  311.                     value = tableau[j][totalVars];
  312.                     break;
  313.                 }
  314.             }
  315.             std::cout << "x" << i+1 << " = " << value << std::endl;
  316.         }
  317.  
  318.         // Display objective function value (Z value)
  319.         double objValue = tableau[numConstraints][totalVars];
  320.         std::cout << "Objective value (Z) = " << -objValue << std::endl;
  321.     }
  322. };
  323.  
  324. int main() {
  325.     SimplexSolver solver;
  326.  
  327.     // Uncomment to manually enter problem data
  328.     // solver.setupProblem();
  329.  
  330.     // Set up from a test case
  331.     solver.setupFromTestCase(
  332.             {5, 4}, // Objective function coefficients (Maximize Z = 3x1 + 2x2)
  333.             {{6, 4}, {1, 2},{-1,1},{0,1}}, // Constraint coefficients
  334.             {24,6,1,2} // RHS values (5 for constraint 1, 12 for constraint 2)
  335.     );
  336.  
  337.     // Solve the problem
  338.     solver.solve();
  339.  
  340.     return 0;
  341. }
  342.  
  343. /*   /\_/\
  344. *   (= ._.)
  345. *   / >  \>
  346. */
  347.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin 
Standard input is empty
stdout 
Initial simplex tableau has been created from input data!

======= Simplex Tableau (Iteration 1) =======
Basic        x1        x2        s1        s2        s3        s4       RHS
---------------------------------------------------------------------------
   s1      6.00      4.00      1.00      0.00      0.00      0.00     24.00
   s2      1.00      2.00      0.00      1.00      0.00      0.00      6.00
   s3     -1.00      1.00      0.00      0.00      1.00      0.00      1.00
   s4      0.00      1.00      0.00      0.00      0.00      1.00      2.00
    Z     -5.00     -4.00      0.00      0.00      0.00      0.00      0.00

======= Simplex Tableau (Iteration 2) =======
Basic        x1        x2        s1        s2        s3        s4       RHS
---------------------------------------------------------------------------
   x1      1.00      0.67      0.17      0.00      0.00      0.00      4.00
   s2      0.00      1.33     -0.17      1.00      0.00      0.00      2.00
   s3      0.00      1.67      0.17      0.00      1.00      0.00      5.00
   s4      0.00      1.00      0.00      0.00      0.00      1.00      2.00
    Z      0.00     -0.67      0.83      0.00      0.00      0.00     20.00

======= Simplex Tableau (Iteration 3) =======
Basic        x1        x2        s1        s2        s3        s4       RHS
---------------------------------------------------------------------------
   x1      1.00      0.00      0.25     -0.50      0.00      0.00      3.00
   x2      0.00      1.00     -0.12      0.75      0.00      0.00      1.50
   s3      0.00      0.00      0.37     -1.25      1.00      0.00      2.50
   s4      0.00      0.00      0.12     -0.75      0.00      1.00      0.50
    Z      0.00      0.00      0.75      0.50      0.00      0.00     21.00
Optimal solution found!

======= Solution =======
x1 = 3.00
x2 = 1.50
Objective value (Z) = -21.00
https://ideone.com/7hIzo8
language:
C++ (gcc 8.3)
created:
7 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!