【解決方法】線形最適化問題により予期しない nans が発生する

プログラミングQA

[ad_1]

こんにちは、私は n 個のアイテムを持っています。各アイテムには 3 つのプロパティがあります。 2 番目の 2 つのプロパティをいくつかの値 A と B と一致させ、最も低いプロパティに一致させたい[0]. 以下は、この問題を解決するための私の最善の試みです(「私が試したこと」を参照してください)

ただし、このコードは 0 で除算しているため、結果は nans になります。正しく動作するようにコードを変更するにはどうすればよいですか。次の結果が得られます。

C++
objective: 18.75
10 3 9: 1.25
5 5 7: 1.25
100 1 1: 0

私が試したこと:

<pre lang="C++">
#include <iostream>
#include <tuple>
#include <vector>

using namespace std;

typedef tuple<double, double, double> Item;

pair<double, vector<pair<Item, double>>> optimize(double A, double B, vector<Item> items) {
    int n = items.size();
    double obj_value = 0;
    vector<pair<Item, double>> quantities(n);

    // Iterate over all items
    for (int i = 0; i < n; i++) {
        // Get the item information
        double price = get<0>(items[i]);
        double X = get<1>(items[i]);
        double Y = get<2>(items[i]);

        // Calculate the solution value
        quantities[i] = make_pair(items[i], 0);
        obj_value += price * get<1>(quantities[i]);
    }

    // Constraint: sum of X * u = A
    double sum_X = 0;
    for (int i = 0; i < n; i++) {
        sum_X += get<1>(get<0>(quantities[i])) * get<1>(quantities[i]);
    }

    if (sum_X != A) {
        for (int i = 0; i < n; i++) {
            if (get<1>(get<0>(quantities[i])) == 0) {
                continue;
            }

            double ratio = A / sum_X; // 10 / 0

            get<1>(quantities[i]) *= ratio;
            obj_value *= ratio;
            break;
        }
    }

    //// Constraint: sum of Y * u = B
    double sum_Y = 0;
    for (int i = 0; i < n; i++) {
        sum_Y += get<2>(get<0>(quantities[i])) * get<1>(quantities[i]);
    }
    if (sum_Y != B) {
        for (int i = 0; i < n; i++) {
            if (get<2>(get<0>(quantities[i])) == 0) {
                continue;
            }
            double ratio = (double)B / sum_Y;
            get<1>(quantities[i]) *= ratio;
            obj_value *= ratio;
            break;
        }
    }

    return make_pair(obj_value, quantities);
}

int main() {
    vector<Item> items = {
        Item({10, 3, 9}),
        Item({5, 5, 7}),
        Item({100, 1, 1})
    };

    pair<double, vector<pair<Item, double>>> result = optimize(10, 20, items);

    cout << "# objective: " << result.first << endl;
    for (auto i : result.second) {
        cout << "# " << get<0>(i.first) << " " << get<1>(i.first) << " " << get<2>(i.first) << ": " << i.second << endl;
    }

    return 0;
}

[ad_2]

コメント

タイトルとURLをコピーしました