2

特定の時間にさまざまなポイント間を移動する必要があるオブジェクトのグループがあるという問題を解決しようとしています。

線形計画法の観点から、ほとんどの制約を形式化することができました。つまり、次のようになります。

object1FirstDepartureTime > X
object1FirstArrivalTime < Y
object1FirstArrivalTime - object1FirstDepartureTime > Z
object1SecondDepartureTime - object1FirstArrivalTime > A

などなど、すべてのオブジェクトとすべての到着/出発について同様です。目的関数は、移動にかかる時間を最小限または最大限にすることです。

私が抱えている問題は、もう 1 つの制約があることです。特定のオブジェクトは、移動中に他のオブジェクトを同伴する必要があります。たとえば、object1 には、object2、object3、または object4 が付随する可能性があります。これらのオブジェクト自体には、特定の到着または出発の制約があります。(おそらく混合整数の) 線形プログラムに、付随するオブジェクトの選択を処理させたいと思います。しかし、これを形式化しようとしている間、それを線形に保つ方法がわかりません。次のような混合整数制約を考えました

object2GoWIthObject1 + object3GoWithObject1 + object4GoWithObject1 < 2
object2GoWIthObject1, object3GoWithObject1, object4GoWithObject1 are all less than 2
object2GoWIthObject1, object3GoWithObject1, object4GoWithObject1 are all integers

しかし、「物体 2 が物体 1 を伴う場合、物体 1 とともに X 時刻に出発し、Y 時刻に到着する」という制約の表現方法がわかりません。これは、ブール変数 (オブジェクト 2 がオブジェクト 1 を伴う場合) に移動時間を乗算するため、非線形に見えます。

もちろん、「if...then...」ステートメントごとに異なる線形問題を作成することもできますが、60 個の付随するパスと 10 個の付随するオブジェクトを使用すると、10^60 個の線形プログラムを解決する必要があります。良い。

この線形計画法の問題を形式化して、「X は Y に付随するか?」という決定を行う方法について直感を持っている人がいるとします。問題自体で表現することができます。

4

2 に答える 2

2

はい、制約を処理するために配合を変更できます。これを達成するために、「Big-M」と新しい 0-1 を含む多くの標準的なトリックがあります。(Han の応答は、これを正しく示唆しています。)

特定の非線形制約に対応するために、新しい 0-1 変数 (「GoWith」変数など) を導入し、定式化に追加の線形制約を追加します。

あなたが述べた要件を考えてみましょう:オブジェクト 2 がオブジェクト 1 に付随する場合、オブジェクト 1 と共に時間 X に出発し、時間 Y に到着します。

Start1 >= X 
Arrive1 <= Y

は、オブジェクト 1 に対して既に設定されている制約です。

Object2 が Object1 と一緒に移動する場合は 1、それ以外の場合は Z12 = 0 であるバイナリ変数Z12を導入しましょう。

そう、

If Z12 = 1, then Start2 > X
If Z12 = 1 then Arrive2 < Y

これを次のように書き換えることができます。

Start2 - X >= 0 if Z12 =1
Start2 - X >= -M if Z12 =0, where M is a large number.

それらを 1 つの線形制約に結合します。

Start2 - X >= M(Z12-1)

この制約は、Z12 が 1 の場合は拘束力があり、それ以外の場合は自明に満たされます。

同様に、Object2 の到着を Object1 の到着と一致させるには、次のように記述します。

Arrive2 < Y if Z12=1
Arrive2 < M if Z12=0

になる

Arrive2 < Y + M(1-Z12), a linear constraint.

同様にバイナリ変数 Z13、Z14 などを導入することで、すべての制約を 1 つの線形定式化で処理できます。

IP の定式化で使用するその他の「トリック」は、http: //agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/new15.pdfにあります。

于 2012-01-10T07:48:59.790 に答える
0

1 つの方法は、次のような big-M メソッドを使用することです。

object1FirstDepartureTime - object2FirstDepartureTime > -M * object2GoWIthObject1
object1FirstDepartureTime - object2FirstDepartureTime < M * object2GoWIthObject1

M は十分に大きな定数です。big-M アプローチの問題は、LP 緩和が不十分になることです。

于 2011-12-21T20:16:49.540 に答える