目標函數和約束條件

在優化問題中，目標函數和約束條件佔據着重要的位置。目標函數是描述優化目標的函數，而約束條件則是問題的限制條件。本文將從多個方面對目標函數和約束條件進行詳細闡述。

一、目標函數

目標函數是描述優化問題中優化目標的函數，通常為一元或多元函數。在優化問題中，我們的目標是最小化或最大化目標函數的值。

目標函數的形式取決於問題的具體要求。比如，在線性規劃問題中，目標函數具有一個線性表達式，而在非線性規劃問題中，目標函數可能具有一個非線性表達式。

下面是一個求解最大化目標函數的例子：

/* 求解 f(x) = sin(x) / x 的最大值 */

#include 
#include 
using namespace std;

double f(double x) {
    return sin(x) / x;
}

int main() {
    double left = 0.1, right = 20.0;
    double eps = 1e-6;

    // 二分查找求最大值
    while (right - left > eps) {
        double mid = (left + right) / 2;
        double midmid = (mid + right) / 2;
        if (f(mid) < f(midmid)) {
            left = mid;
        } else {
            right = midmid;
        }
    }

    cout << "最大值為：" << f(left) << endl;    
    return 0;
}

二、約束條件

約束條件是指問題中所包含的限制條件，這些條件可能是等式約束條件或不等式約束條件。

等式約束條件用於限制變量之間的數值關係，比如 a + b + c = 10。

不等式約束條件用於限制變量的取值範圍，比如 a + b >= c。

下面給出一個帶有等式約束條件和不等式約束條件的線性規劃問題:

/* 求解如下線性規劃問題：
   maximize  z = 2x1 + 3x2 
   subject to: 
      x1 + x2 <= 12
      x1 <= 6 
      x2 = 0 
      x2 >= 0 
      x1 + x2 >= 4 
   */

#include 
#include 
#include 
#include 
using namespace std;

const double eps = 1e-6;

struct Simplex {
    vector<vector > a;
    vector idx;
    int n, m;

    Simplex(int n, int m) : n(n), m(m) {
        a.assign(n + 1, vector(m + 1, 0.0));
        idx.resize(n + m);
        for (int i = 0; i < n + m; i++) {
            idx[i] = i;
        }
    }

    void pivot(int r, int c) {
        swap(idx[n + r], idx[c]);
        double div = a[r][c];
        a[r][c] = 1;
        for (int i = 0; i <= m; i++) {
            a[r][i] /= div;
        }
        for (int i = 0; i <= n; i++) {
            if (i != r) {
                double mul = a[i][c];
                a[i][c] = 0;
                for (int j = 0; j <= m; j++) {
                    a[i][j] -= a[r][j] * mul;
                }
            }
        }
    }

    bool simplex(int phase) {
        int x = n + m;
        while (true) {
            int c = -1;
            for (int i = 0; i < m; i++) {
                if (phase == 1 && idx[i] == x) {
                    continue;
                }
                if (c == -1 || a[n][i] < a[n][c] - eps || (a[n][i] < a[n][c] + eps && idx[i] < idx[c])) {
                    c = i;
                }
            }
            if (c == -1) {
                break;
            }
            int r = -1;
            for (int i = 0; i  eps) {
                    if (r == -1 || a[i][m] / a[i][c] < a[r][m] / a[r][c] - eps 
                            || (a[i][m] / a[i][c] < a[r][m] / a[r][c] + eps && idx[i] < idx[r])) {
                        r = i;
                    }
                }
            }
            if (r == -1) {
                return false;
            }
            pivot(r, c);
        }
        return true;
    }

    double solve() {
        int r = 0;
        for (int i = 1; i < n; i++) {
            if (a[i][m] < a[r][m]) {
                r = i;
            }
        }
        if (a[r][m] < -eps) {
            pivot(r, m);
            if (!simplex(1) || a[n][m] < -eps) {
                return -numeric_limits::infinity();
            }
            for (int i = 0; i  eps && a[i][m] / abs(a[i][m]) == a[r][m] / abs(a[r][m])) {
                    pivot(i, m);
                }
            }
            r = n - 1;
            for (int i = 0; i  eps && (r == n - 1 || a[i][m] / a[i][n] < a[r][m] / a[r][n] - eps 
                        || (a[i][m] / a[i][n] < a[r][m] / a[r][n] + eps && idx[i] < idx[r]))) {
                    r = i;
                }
            }
        }
        if (!simplex(2)) {
            return numeric_limits::infinity();
        }
        return a[n][m];
    }
};

int main() {
    Simplex S(5, 3);
    S.a[0][0] = -2; S.a[0][1] = -3; S.a[0][2] = 0;
    S.a[1][0] = 1; S.a[1][1] = 1; S.a[1][2] = 1; S.a[1][3] = 12;
    S.a[2][0] = 1; S.a[2][1] = 0; S.a[2][2] = 0; S.a[2][3] = 6;
    S.a[3][0] = 0; S.a[3][1] = 1; S.a[3][2] = 0; S.a[3][3] = 7;
    S.a[4][0] = 0; S.a[4][1] = 0; S.a[4][2] = 1; S.a[4][3] = 4;
    S.a[5][0] = 0; S.a[5][1] = 0; S.a[5][2] = 0; S.a[5][3] = 0;
    double ans = S.solve();
    cout << "最大值為：" << -ans << endl;
    return 0;
}

三、總結

本文對目標函數和約束條件進行了詳細的介紹。目標函數和約束條件是優化問題的核心，對於不同類型的問題，需要選擇適當的目標函數和約束條件。