fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <limits>
  5.  
  6. using namespace std;
  7.  
  8. typedef vector<double> VD;
  9. typedef vector<VD> VVD;
  10. typedef vector<int> VI;
  11.  
  12. const double EPS = 1e-9;
  13.  
  14. struct Simplex {
  15.     int m, n;
  16.     VI B, N;
  17.     VVD D;
  18.  
  19.     Simplex(const VVD &A, const VD &b, const VD &c) :
  20.         m(b.size()), n(c.size()), B(m), N(n + 1), D(m + 2, VD(n + 2)) {
  21.  
  22.         for (int i = 0; i < m; ++i) B[i] = n + i;
  23.         for (int j = 0; j < n; ++j) N[j] = j;
  24.         N[n] = -1;
  25.  
  26.         for (int i = 0; i < m; ++i) {
  27.             for (int j = 0; j < n; ++j) D[i][j] = A[i][j];
  28.             D[i][n] = -1;
  29.             D[i][n + 1] = b[i];
  30.         }
  31.  
  32.         for (int j = 0; j < n; ++j) D[m][j] = -c[j];
  33.         D[m + 1][n] = 1;
  34.     }
  35.  
  36.     void pivot(int r, int s) {
  37.         double inv = 1.0 / D[r][s];
  38.         for (int i = 0; i < m + 2; ++i)
  39.             if (i != r)
  40.                 for (int j = 0; j < n + 2; ++j)
  41.                     if (j != s)
  42.                         D[i][j] -= D[r][j] * D[i][s] * inv;
  43.         for (int j = 0; j < n + 2; ++j)
  44.             if (j != s)
  45.                 D[r][j] *= inv;
  46.         for (int i = 0; i < m + 2; ++i)
  47.             if (i != r)
  48.                 D[i][s] *= -inv;
  49.         D[r][s] = inv;
  50.         swap(B[r], N[s]);
  51.     }
  52.  
  53.     bool bland_simplex(int phase) {
  54.         int x = phase == 1 ? m + 1 : m;
  55.         while (true) {
  56.             int s = -1;
  57.             for (int j = 0; j <= n; ++j) {
  58.                 if (N[j] == -1) continue;
  59.                 if (D[x][j] < -EPS && (s == -1 || N[j] < N[s])) s = j;
  60.             }
  61.             if (D[x][s] > -EPS) return true;
  62.             int r = -1;
  63.             for (int i = 0; i < m; ++i) {
  64.                 if (D[i][s] > EPS && (r == -1 || (D[i][n + 1] / D[i][s] < D[r][n + 1] / D[r][s] ||
  65.                     (D[i][n + 1] / D[i][s] == D[r][n + 1] / D[r][s] && B[i] < B[r])))) r = i;
  66.             }
  67.             if (r == -1) return false;
  68.             pivot(r, s);
  69.         }
  70.     }
  71.  
  72.     double solve(VD &x) {
  73.         int r = 0;
  74.         for (int i = 1; i < m; ++i)
  75.             if (D[i][n + 1] < D[r][n + 1]) r = i;
  76.         if (D[r][n + 1] < -EPS) {
  77.             pivot(r, n);
  78.             if (!bland_simplex(1) || D[m + 1][n + 1] < -EPS) return -numeric_limits<double>::infinity();
  79.             for (int i = 0; i < m; ++i)
  80.                 if (B[i] == -1) {
  81.                     int s = -1;
  82.                     for (int j = 0; j <= n; ++j)
  83.                         if (s == -1 || D[i][j] < D[i][s]) s = j;
  84.                     pivot(i, s);
  85.                 }
  86.         }
  87.         if (!bland_simplex(2)) return numeric_limits<double>::infinity();
  88.         x = VD(n);
  89.         for (int i = 0; i < m; ++i)
  90.             if (B[i] < n)
  91.                 x[B[i]] = D[i][n + 1];
  92.         return D[m][n + 1];
  93.     }
  94. };
  95.  
  96. int main() {
  97.     // Bài toán với các ràng buộc
  98.     VVD A = {{-1, 2}, {1, -1}, {-2, -1}, {1, 0}, {2, 1}, {1, 1}, {1, 2}, {0, 2}};
  99.     VD b = {-1, 2, -6, 5, 16, 12, 21, 10};
  100.     VD c = {3, 2};
  101.     VD x;
  102.  
  103.     Simplex simplex(A, b, c);
  104.     double result = simplex.solve(x);
  105.  
  106.     if (result == numeric_limits<double>::infinity())
  107.         cout << "Không giới hạn\n";
  108.     else if (result == -numeric_limits<double>::infinity())
  109.         cout << "Không khả thi\n";
  110.     else {
  111.         cout << "Giá trị tối ưu: " << result << "\n";
  112.         cout << "Giải pháp: ";
  113.         for (double v : x) cout << v << " ";
  114.         cout << "\n";
  115.     }
  116.  
  117.     return 0;
  118. }
  119.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Giá trị tối ưu: 11
Giải pháp: 3 1
https://ideone.com/qQy3X2
language:
C++14 (gcc 8.3)
created:
14 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!