LinearFractionalOptimization

LinearFractionalOptimization[f,cons,vars]

線形制約 cons に従って線形分数目的関数 f を最小化する変数 vars の値を求める.

LinearFractionalOptimization[{α,β,γ,δ},{a,b}]

線形不等式制約 に従って線形分数関数を最小化するベクトル を求める.

LinearFractionalOptimization[{α,β,γ,δ},{a,b},{aeq,beq}]

線形等式制約 を含む.

LinearFractionalOptimization[{α,β,γ,δ},,{dom1,dom2,}]

が領域 domiにあるものとする.domiIntegersまたはRealsである.

LinearFractionalOptimization[,"prop"]

解のどの特性"prop"を返すべきか指定する.

詳細とオプション

  • 線形分数最適化は線形分数計画法(LFP)および混合整数線形分数計画法(MILFP)としても知られている.
  • 線形分数最適化は,実変数,整数変数あるいは複素変数で大域的に効率よく解くことができる凸最適化問題である.
  • 線形分数最適化は主問題を解く を求める. »
  • 最小化
    制約条件
    ただし
  • 混合整数線形部分最適化は,問題を解く および を求める.
  • 最小化
    制約条件
    ただし
  • LinearFractionalOptimizationは,目的関数が実数値のときは内部的に実変数 に変換して x in TemplateBox[{}, Complexes]^nの問題を解く.ただし,である,
  • 変数指定 vars は,次のいずれかの形式で変数を与える要素のリストでなければならない.
  • v名前が で次元が推測される変数
    vReals実数のスカラー変数
    vIntegers整数のスカラー変数
    vComplexes複素数のスカラー変数
    v幾何学領域 に制限されたベクトル変数
    vVectors[n,dom]またはのベクトル変数
    vMatrices[{m,n},dom]またはの行列変数
  • 制約条件 cons は以下で指定できる.
  • LessEqualスカラー不等式
    GreaterEqualスカラー不等式
    VectorLessEqualベクトル不等式
    VectorGreaterEqualベクトル不等式
    Equalスカラー等式またはベクトル等式
    Element凸領域または領域要素
  • LinearFractionalOptimization[f,cons,vars]のとき,f または cons で使われるパラメータを定義するために,制約条件には parval の形式のパラメータ等式が含まれるかもしれない.ただし,parvars には含まれず,val は数値または数値配列である.
  • 主最小化問題には関連する最大化問題(ラグランジュ双対問題)がある.双対最大値は常に主最小値以下なので,下界を与える.双対マキシマイザは,制約条件に対する最小値の感度変化を含む,主問題についての情報を与える.
  • 線形分数最適化のラグランジュ双対問題は以下で与えられる. »
  • 最大化
    制約条件
    ただし
  • 線形分数最適化については,強双対性が常に成り立つ.つまり,主最小化問題に解があれば双対最大化問題にも解があり,双対最大値は主最小値に等しい.
  • 可能な解の特性"prop"には以下がある.
  • "PrimalMinimizer"目的関数を最小化する変数値のリスト
    "PrimalMinimizerRules" を最小化する変数の値 vars={v1,}
    "PrimalMinimizerVector"を最小化するベクトル
    "PrimalMinimumValue"最小値
    "DualMaximizer" を最大化するベクトル
    "DualMaximumValue"双対最大値
    "DualityGap"双対最適値と主最適値の差(強双対性により0)
    "Slack"
  • 制約条件スラックベクトル
  • "ConstraintSensitivity"
    制約条件の摂動に対する の感度
    "LinearFractionalObjectiveCoefficients" における係数
    "LinearInequalityConstraints"
    線形不等式制約の行列およびベクトル
    "LinearEqualityConstraints"
    線形等式制約の行列およびベクトル
    {"prop1","prop2",} いくつかの解の特性
  • 双対最大値 を介して および と関連がある.
  • 次は,使用可能なオプションである.
  • MaxIterationsAutomatic使用する最大反復回数
    Method Automatic使用するメソッド
    PerformanceGoal$PerformanceGoalパフォーマンスのどの局面について最適化するか
    Tolerance Automatic内部計算の許容度
    WorkingPrecision Automatic内部計算の精度
  • オプションMethod->method を使って使用するメソッドを指定することができる.次は使用可能なメソッドである.
  • Automaticメソッドを自動的に選択する
    "Simplex"シンプレックス法
    "RevisedSimplex"改訂シンプレックス法
    "InteriorPoint"内点法(機械精度のみ)
    "CLP"COINライブラリ線形計画法(機械精度のみ)
    "MOSEK"商用MOSEK線形最適化ソルバ
    "Gurobi"商用Gurobi線形最適化ソルバ
    "Xpress"商用Xpress線形最適化ソルバ
  • WorkingPrecision->Automaticのときは,機械精度でしか使えないメソッドが指定されていない限り,入力引数の精度から自動的に精度が取られる.機械精度でしか使えないメソッドには機械精度が使用される.
  • 求める解の分母が正か負のどちらであるか先験的に分かっているなら,分母の正または負と等しい定数 a または b を含むことでLinearFractionalOptimizationが解をより速く計算できるようになる.

例題

すべて開くすべて閉じる

  (3)

に従ってを最小化する:

実行可能領域上の関数のプロット上でミニマイザを表示する:

に従ってを最小化する:

入力を行列ベクトル形式で指定する:

行列ベクトル形式を使って解く:

に従ってを最小化する:

同等の行列ベクトル表現を使う:

スコープ  (33)

基本的な用法  (17)

制約条件 に従ってを最小化する:

制約条件に従ってを最小化する:

に従ってを境界としてを最小化する:

VectorLessEqualを使っていくつかのLessEqual不等式制約を一度に表現する:

v<=を使ってベクトル不等式をコンパクトな形で入力する:

スカラー不等式を使った同等の形:

VectorGreaterEqualを使っていくつかの GreaterEqual不等式制約を一度に表現する:

v>=を使ってベクトル不等式をコンパクトな形で入力する:

スカラー不等式を使った同等の形:

Equalを使っていくつかの不等式条件を一度に表現する:

いくつかのスカラー方程式を使った同等の形:

スカラー不等式とベクトル不等式を組み合せて制約条件を指定する:

に従ってを最小化する.ベクトル変数 を使う:

スカラー変数を使った同等の形:

ベクトル変数とベクトル不等式を使って問題を指定する:

Indexedを使ってベクトル変数の成分,例えば にアクセスする:

定数パラメータ方程式を使って目的関数と制約条件の係数を指定する:

定数パラメータ方程式を使っていくつかの制約条件の係数を指定する:

に従ってを最小化する:

必要なときは,Vectors[n]を使ってベクトル変数の次元を指定する:

NonNegativeReals ()を使って非負の制約条件を指定する:

ベクトル不等式を使った同等の形:

NonPositiveReals ()を使って非正の制約条件を指定する:

ベクトル不等式を使った同等の形:

スカラー,ベクトル,行列を指定することで,に従って を最小化する:

行列ベクトル形式を使って解く:

変数と不等式を使った同等の形:

制約条件に従って関数を最小化するベクトルを求めようとする:

実行可能な領域に特異値があるので,最小値は非有界である:

整数変数  (4)

Integersを使って整数領域制約を指定する:

Vectors[n,Integers]を使ってベクトル変数についての整数領域制約を指定する:

NonNegativeIntegers ()を使って非負の整数領域制約を指定する:

ベクトル不等式を使った同等の形:

NonPositiveIntegers ()を使って非正の整数領域制約を指定する:

ベクトル不等式を使った同等の形:

複素変数  (2)

Complexesを使って複素変数を指定する:

Vectors[2,Complexes]を使ってベクトル変数上に複素領域を指定する:

主モデル特性  (3)

に従ってを最小化する:

主ミニマイザをベクトルとして得る:

最小値を得る:

記号入力を使って最適化問題を解く:

最適化問題の行列ベクトル入力を抽出する:

行列ベクトル入力を使って記号入力の結果を回復する:

最小化問題に関連したスラックを求める:

主ミニマイザと制約行列を得る:

不等式制約 のためのスラックは となるようなベクトル である:

等式制約 のためのスラックは となるようなベクトル である:

等式スラック は一般にゼロベクトルである:

双対モデル特性  (3)

に従ってを最小化する:

双対問題はに従って を最大化する:

強双対性のために主最小値と双対最大値は一致する:

双対性ギャップ0.一般に,最適点で である:

主問題から抽出した制約行列を使って双対問題を構築する:

目的ベクトルと制約行列を抽出する:

双対問題は に従って を最大化する.Inactive[Times]を使って同等性制約におけるスレッド化を回避する:

解の特性を使って双対最大値を直接得る:

解の特性を使って双対マキシマイザを直接得る:

感度特性  (4)

"ConstraintSensitivity"を使って制約条件の緩和による最適値の変化を求める:

第1ベクトルは不等式感度で第2ベクトルは等式感度である:

新たな制約条件 を考える.ただし, は緩和である.新たな最適値の近似は以下のようになる:

緩和問題を解くことで直接比較する:

各感度は不等式制約または等式制約と関連している:

制約条件を抽出する:

不等式制約と関連する感度:

等式制約と関連する感度:

制約条件の緩和による最適値の変化は感度値に比例する:

最小値と制約感度を計算する:

制約条件が緩和している場合は,ゼロ感度は最小値を変えない:

負の感度は最適値を小さくする:

正の感度は最適値を大きくする:

"ConstraintSensitivity"は,問題の双対マキシマイザと関連している:

不等式感度 を満足する.ただし,は双対不等式マキシマイザである:

等式感度 を満足する.ただし,は双対等式マキシマイザである:

オプション  (8)

Method  (4)

MachinePrecisionのデフォルトメソッドは"CLP"である:

任意または無限のWorkingPrecisionのデフォルトメソッドは"Simplex"である:

MachinePrecision入力にはすべてのメソッドが使える:

"Simplex""RevisedSimplex"は任意精度および無限精度の入力に使える:

一般に,メソッドによって長所が異なる.これは,問題や実装によって異なる:

"Simplex""RevisedSimplex"は小さい密な問題に適している:

"InteriorPoint""CLP"は大きい疎な問題に適している:

最適解集合が一意ではない問題については,メソッドによって結果が異なることがある:

"InteriorPoint"は最適解集合の真ん中の解を与えることがある:

"Simplex"は常に最適解集合の角の解を返す:

Tolerance  (2)

Toleranceの設定を小さくするとより正確な結果が与えられる:

許容度を小さくして参照に使う最小値を計算する:

Toleranceの設定を変えて解を計算する:

許容度に対する誤差の変化を可視化する:

Toleranceの設定を小さくするとより正確な答が与えられるが,一般に計算時間は長くなる:

許容度を小さくすると時間がかかるようになる:

許容度の幅を狭くするとより正確な答が与えられる:

WorkingPrecision  (2)

厳密な入力は厳密な出力を与える:

MachinePrecisionを使って厳密ではない結果を得る:

LinearFractionalOptimizationはより高い作業精度で結果を計算することができる:

精度が入力引数の精度よりも低いとメッセージが出る:

アプリケーション  (16)

基本的なモデリング変換  (6)

に従ってを最大化する.目的関数を否定することで最大化問題を解く:

主最小値を否定して対応する最大値を得る:

に従ってを最小化する. とし,を使ってを線形関数に変換する:

この問題は を使っても変換できる:

に従ってを最小化する.なので,とすると,目的関数はに変換される:

に従ってを最小化する.なので, を使って目的関数を に変換する:

に従って を最小化する.ただし, は非減少関数である.代りにを最小化する.主ミニマイザ は両方の問題に対して同じである.に従って を最小化することを考える:

真の最小値は関数 を主最小値に適用することで得られる:

に従って を最小化する:

なので,および で問題を解く:

最適解は2つの解の変換された最小値である:

輸送問題  (1)

費用を最小化して利益を最大化することで,5つの商品の輸送単位数を選択する.各商品の1単位の輸送についての費用と利益は以下の通りである:

商品の各単位の重さと輸送可能な最大単位は以下の通りである:

トラックによる最小運用費用は1回の輸送につき2000ドルである.総輸送費用は以下の通りである:

トラックは,空の場合,最低でも1000ドルの利益を出す.総利益は以下の通りになる:

トラックは最大8000ポンド(約3600キロ)を運べる.トラックの制約条件は以下の通りである:

利益に対する費用の率を最小にすることによって求められる輸送する商品の最適な組合せは,以下の通りである:

生産計画  (1)

生産に際して費用を最小にして利益を最大にするような4つの製品の組合せを求める.各製品を1単位生産する際の費用と利益は以下の通りである:

各製品を生産するために,以下のような5つのリソースを組み合せなければならない:

使用可能な最大リソースは以下の通りである:

リソースと製品についての制約条件は以下の通りである:

この会社の最低操業費用は100ドルである.総製造費用は以下の通りである:

製品の販売による総利益は以下の通りである:

製造する最大単位を求めるために,費用と利益の割合を最小化する:

資源配分  (1)

ある会社が,都市のピーク時の需要を満たしつつ利益を最大にして費用を最小にするために3つの発電所から4つの都市に送らなければならない電力量を求める.各発電所からさまざまな都市への百万kwの電力の1時間あたりの送電費用は以下の通りである:

各都市に毎時百万キロワットの電力を売ることで各発電所が生み出す利益は以下の通りである:

は発電所 から都市 に送られる電力量とする.電力の総輸送費用は で,Inactive[Times]を使って構築できる:

電力会社の総利益は で,Inactive[Times]を使って構築できる:

都市のピーク時の需要量は,それぞれ毎時4500万kw, 2000万kw, 3000万kw, 3000万kwである:

発電所は最低でもそれぞれ毎時 3500万kw, 5000万kw, 4000万kwの電力が供給できる:

発電所は電力を供給するだけで,都市から電力を受け取ることはできない:

各発電所が各都市に送る電力の最適量は,費用と利益の割合を最小化することで求められる:

電力供給の内訳は以下の通りである:

混合問題  (1)

最大で鉛が60%で錫が35%の新たな合金を作るための,最小の費用で最大の利益をあげるような古い合金の組合せ方の割合を求める.この鋳物工場には錫と鉛を含む4種類の古い合金がある:

を合金 の総重量とする.新たな合金は古い合金を組み合せて作る:

4種類の合金のそれぞれ1ポンドを作る費用は以下の通りである:

新たな合金を作る費用は以下の通りである:

この鋳物工場は新たな合金を200ドルで販売する.工場の総利益は以下の通りである:

この鋳物工場は最高で鉛60%と錫35%を含む新たな合金を少なくとも15ポンド製造しなければならない:

この工場は,それぞれ12,15,16,10ポンドの古い合金にしかアクセスできない:

古い合金の最適な割合は,費用と利益の割合を最小にすることで求められる:

投資問題  (2)

株式と債券の購入費用が最小で投資利益が最大となるような$250,000の資産の2つの株式と債券への割当てを求める.は2つの株式への投資額,は債券への投資額とする:

電気・ガス株への投資額は4万ドルを超えてはならず,配当金は9%である:

債券への投資は少なくとも7万ドルで,利率は5%である:

2つの株式への投資合計は少なくとも投資総額の半額である:

電気株は年4%の配当で,投資に対する総合利回りは以下の通りである:

この投資に関連する費用は以下の通りである:

投資する最適額は費用と収益の割合を最小にすることで求められる:

総投資額と投資から受け取る年配当は以下の通りである:

費用を最小にして利益を最大にする投資の最適な組合せを求める.正味の現行価格と関連費用は以下の通りである:

を,投資 が選択された場合に となる決定変数とする.目的は費用を最小にして利益を最大にすることである:

最大で14000ドルが投資できる:

この最大化問題を解いて投資の最適な組合せを求める:

集合被覆問題  (3)

病院の救急救命室(ER)でリストにある処置を行うためにERに待機させなければならない医師の組合せを求める.各医師は特定数の処置しか行えないものとする:

各医師を待機させておくための(1時間あたりの)費用は以下の通りである:

を医師 が待機している場合に となるような決定ベクトルとする.目的は費用を最小にしてERで待機する医師数を最大にすることである:

少なくとも一人の医師が処置 を行わなければならない:

待機させるべき医師の組合せを求める:

6つの地区からなる都市に,各地区から15分以内の場所に消防署があるようにするために建設しなければならない消防署の最低数を求める.ある地区から隣の地区までの運転時間は以下の通りである:

各地区に消防署を建設する費用(100万ドル単位)は以下の通りである:

を,地区 に消防署が建設された場合に となるような決定ベクトルとする.目的は消防署の数を最大にして費用を最小にすることである:

各地区から15分以内の場所に少なくとも1つの消防署がなければならない:

消防署を建設すべきである地区を求める:

総費用は以下の通りである:

ある会社がその6つの小売店に商品を供給するために建設しなければならない倉庫の最小数を求める.この会社は倉庫の候補地を5つ選んだ.各小売店に各倉庫から商品を供給するための費用は以下の通りである:

各倉庫の建設費用は以下の通りである(単位:百万):

を,倉庫 が建設されたなら となる決定変数とする.は倉庫 が小売店 に供給する商品の割合を表す.総費用は以下の通りである:

会社は,各倉庫の未使用部分を貸し出すことで百万ドルの利益を得ることを期待している:

すべての小売店がすべての商品を受け取らなければならない:

建設された倉庫のみが小売店に商品を供給できる:

5つの倉庫のどれを建設すべきかを求める:

建設する倉庫を求める:

小売店に商品を供給する倉庫は次の通りである:

巡回セールスマン問題  (1)

セールスマンが 都市をそれぞれ1回だけ通る経路を,移動距離が最短で移動費用の節約が最大となるようにして求める.場所を生成する:

都市 から都市 までの距離を とする. は,なら経路が都市 から都市 へ向かう決定変数である:

一つの都市から次の都市への移動費用の予算は15ドルである.料金は定額制で,2つの都市の距離が50マイル以内の場合は5ドル,それ以外の場合は10ドルである.節約合計は以下の通りである:

目的は距離を最小にして節約を最大にすることである:

セールスマンは厳密に1つの都市から来て厳密に1つの都市へ行くことができる:

セールスマンはある都市に来て同じ都市に行くことはできない:

セールスマンは1回のツアーですべての場所を回らなければならない:

決定変数ばバイナリ変数で,ダミー変数は である:

距離が最短となる経路を求める:

経路を抽出する:

移動距離は以下の通りである:

節約合計は以下の通りである:

特性と関係  (5)

LinearFractionalOptimizationは目的関数の大域的最小値を与える:

Minimizeは,線形分数最適化の大域的厳密結果も与える:

NMinimizeを使って大域メソッドを使って非厳密結果を得ることができる:

FindMinimumを使い,局所メソッドを使って非厳密結果を得ることができる:

LinearOptimizationLinearFractionalOptimizationの特殊ケースである:

考えられる問題  (6)

狭義不等式を使って指定された制約条件は満足されないことがある:

与えられる解はである:

空集合あるいは実行不可能な問題の最小値はと定義される:

ミニマイザはIndeterminateである:

非有界集合あるいは非有界問題の最小値はである:

ミニマイザはIndeterminateである:

混合整数問題についての双対関連の解特性は得られないかもしれない:

混合整数問題は機械精度でしか解けない:

複素数値を含む制約条件はベクトル不等式で指定しなければならない:

GreaterEqualあるいはLessEqualだけを使ってもうまくいかない:

Wolfram Research (2019), LinearFractionalOptimization, Wolfram言語関数, https://reference.wolfram.com/language/ref/LinearFractionalOptimization.html (2020年に更新).

テキスト

Wolfram Research (2019), LinearFractionalOptimization, Wolfram言語関数, https://reference.wolfram.com/language/ref/LinearFractionalOptimization.html (2020年に更新).

CMS

Wolfram Language. 2019. "LinearFractionalOptimization." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2020. https://reference.wolfram.com/language/ref/LinearFractionalOptimization.html.

APA

Wolfram Language. (2019). LinearFractionalOptimization. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/LinearFractionalOptimization.html

BibTeX

@misc{reference.wolfram_2024_linearfractionaloptimization, author="Wolfram Research", title="{LinearFractionalOptimization}", year="2020", howpublished="\url{https://reference.wolfram.com/language/ref/LinearFractionalOptimization.html}", note=[Accessed: 21-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_linearfractionaloptimization, organization={Wolfram Research}, title={LinearFractionalOptimization}, year={2020}, url={https://reference.wolfram.com/language/ref/LinearFractionalOptimization.html}, note=[Accessed: 21-November-2024 ]}