3

GLPK-Java ライブラリの使用に関するドキュメントがあまりないことは既に知っていますが、とにかく質問します... (別のソルバーは使用できません)

スケジューリングに関する基本的な問題があります。いくつかの基本的な制約がある学期のコースへの学生。

問題の例は次のとおりです。

We consider {s1, s2} a set of two students. They need to take two
courses {c1, c2} during two semesters {t1, t2}.
We assume the courses are the same. We also assume that the students
cannot take more than one course per semester, and we'd like to determine the
minimum capacity X that must be offered by the classroom, assuming they
all offer the same capacity.

CPLEX 形式で与えられた例は次のようになります。

minimize X

subject to
y111 + y112 = 1
y121 + y122 = 1
y211 + y212 = 1
y221 + y222 = 1
y111 + y112 <= 1
y121 + y122 <= 1
y211 + y212 <= 1
y221 + y222 <= 1
y111 + y112 -X <= 0
y121 + y122 -X <= 0
y211 + y212 -X <= 0
y221 + y222 -X <= 0

end

glpsol コマンドを使用してソルバーを介してこれを実行し、解決することができますが、API を使用してこれを記述する必要があります。私は線形計画法を実際に扱ったことがなく、ドキュメントには何かが望まれています。これはせいぜい単純ですが、実際の問題は、18 コースのうち 12 コースを受講しなければならない 12 学期にわたる 600 人の学生を解決することであり、特定のクラスは特定の学期のみ利用可能であり、一部のコースには前提条件があります。

APIを使用して単純化された問題をコーディング例に変換するのに助けが必要です。非常に単純な問題が API 呼び出しにどのように対応するかがわかれば、より複雑な問題のアプリケーションを作成する方法を理解できると思います。

ライブラリの例から、列を設定していることがわかります。この場合は学期で、行は生徒です。

// Define Columns
GLPK.glp_add_cols(lp, 2);   // adds the number of columns
GLPK.glp_set_col_name(lp, 1, "Sem_1");
GLPK.glp_set_col_kind(lp, 1, GLPKConstants.GLP_IV);
GLPK.glp_set_col_bnds(lp, 1, GLPKConstants.GLP_LO, 0, 0);

GLPK.glp_set_col_name(lp, 2, "Sem_2");
GLPK.glp_set_col_kind(lp, 2, GLPKConstants.GLP_IV);
GLPK.glp_set_col_bnds(lp, 2, GLPKConstants.GLP_LO, 0, 0);

この時点で、行の制約を設定する必要があると思いますが、途方に暮れています。どんな方向性でも大歓迎です。

4

1 に答える 1

2

API を使用する場合、最適化の問題は基本的に問題のマトリックスで表されます。ここで、列は変数であり、行は制約です。問題では、y111、y112、...、および X を表す 9 つの列を定義する必要があります。

次に、使用する変数 (列) を設定することで、制約 (行) を続行できます。

GLPK.glp_set_row_name(lp, 2, "constraint1");
GLPK.glp_set_row_bnds(lp, 2, GLPKConstants.GLP_FX, 0, 1.0); // equal to 1.0
GLPK.intArray_setitem(ind, 1, 1); // Add first column at first position
GLPK.intArray_setitem(ind, 2, 2); // Add second column at second position    
// set the coefficients to the variables (for all 1. except X is -1. in the example)
GLPK.doubleArray_setitem(val, 1, 1.); 
GLPK.doubleArray_setitem(val, 2, 1.);
GLPK.glp_set_mat_row(lp, 1, 2, ind, val);

これは、y111 + y112 = 1制約を表します - 残り 11 です。

Java パッケージの GLPK には、GLPK 関数の優れたドキュメントを含む glpk のドキュメントも含まれている必要があります (これは、java の glpk でも利用できます)。lp.java の例も見てください。

于 2015-03-06T18:31:01.087 に答える