3

目的関数内の最小関数を使用して LP を簡単に定式化しようとしています。目的関数は次のように進みます。

maximize sum( R(dvf * Df) ) - sum( min( tsp, ts'p ) * Csp - max(tsp-ts'p,0) * bsp )

R --> 収益関数 (この質問のこの部分は気にしません)

tsp は、パス p の発信元と宛先の組み合わせ s で送信しているトラックの数を示します。ts'p は逆ルートです。ここで s と p を合計します。

これから知る必要があるのは、LP の一部として設定する方法です。LP は目的ステートメント内で最小化および最大化関数を受け入れないためです。この質問によると、追加の変数を使用したビッグ M の定式化が必要ですが、実際にそれを行う方法については言及されていません。

事前にご協力いただきありがとうございます。

4

1 に答える 1

2

Big-M と一連の指標変数を使用してそれを行う方法を次に示します。

説明のためにルートのペアを 1 つだけ使用します。すべてのルートのペア (s,p) について同じことができます。それらを Tsp と呼び、その逆を Tps と呼びましょう。

IP の 2 つの決定変数の最小値を線形化する

読む目的関数の部分だけに注目しましょう Min(Tsp, Tps) * Cost_sp

最初に目的関数を次のように書き直します。 したがって、ルート spMin Xsp * Cspに新しい変数を導入しました。Xsp

Xsp = Tsp if Tsp is the minimum of Tsp and Tps
Xsp = Tps if Tps is the minumum of the two values

これは、追加の制約を介して強制できます。

Xsp = Tsp * Y + Tps * (1-Y)ここで、Y は 0 から 1 の標識変数です。

Tsp が大きい場合は Y を 1 に、Tsp が小さい場合は Y を 0 にします。

これを実現するために、制約を追加します。Tsp - Tps + M*y > 0 そのロジックを実行すると、Tsp が大きい場合、条件は自動的に満たされます。しかし、Tps が Tsp よりも大きい場合、制約を満たすために Y は値 1 を取らなければなりません。

目的関数に小さな価格を追加することで、その値を取る必要がある場合にのみ Y が 1 であることを保証できます。

すべてを一緒に入れて：

Objective Maximize Sum(p,s) Xsp * Csp - epsilon.Y

s.t.
     Xsp = Tsp * Y + Tps * (1-Y)
     Tsp - Tps + M*y > 0
     Y = {0,1}

目的関数がTsp と Tps の 2 つの値の最小値を取るようにします。

残りの作業を進めるのに役立つことを願っています。

于 2013-10-25T18:54:14.770 に答える