JPH02170268A - 割当て最適化方法、割当て最適化システム、及びその装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は、複数の資源利用者間で、資源を最適に割当て
る方法に関し、特に、割当て費用が非線形関数に従い、
割当てパラメータが線形に束縛されている物理的システ
ムにおける、改善された資源割当てを行なう方法、及び
その装置に関する。

〔従来技術の説明］ システムの資源割当て及びその最適化の必要性は、産業
及び技術分野の広い範囲で生じてきている。その例とし
ては、電話伝送システムにおける伝送機器の割当て、工
場における製品混合の制御、電話会社によるオペレータ
サービス等の特定の仕事の組を行なうための人の割当て
、在庫制御、産業機器の展開等が上げられる。

資源割当て及びその最適化に係る決定は、通常、種々の
決定変数に係るある種の束縛条件の影響を受ける。例え
ば、資源は、常にその入手可能性において制限されてお
り、さらに、ある場合には、その特定のアプリケーショ
ンにおける有用性も制限されている。よって、問題は、
資源を、束縛条件が満足され、同時に、割当てに係る費
用が最小となる、すなわち、割当てに由来する利益が最
大となるように割当てることである。最小化される費用
は、ユーザによって選択された、経費、遅延、効率の悪
さ等のあらゆる測度である。

この種の最適化問題を性格付けし、解決する一般的な方
法は、数学的なプログラミングモデルによるものである
。すなわち、システムに係る、最適化さるべき種々の資
源は、変数（各資源割当てにつき１変数）で表現され、
変数の集合はベクトルと見做され、最適化さるべきシス
テムに係る、希望された状態に対する解は、ある種の手
続きによる、前記ベクトルに対する値の評価によって導
出され、最後に、評価されたベクトルの成分の値は、割
当てられる資源の希望された値を表わしているとされる
。

上述のようにモデル化された場合、線形な関係よりなり
、リニア（線形）プログラミング（Ｌ　Ｐ）として知ら
れている問題及びその解のクラスに属する、物理的な最
適化問題は多数存在する。しかしながら、上述のように
モデル化された場合、ある種の線形な関係とある種の非
線形な関係とからなる、別の物理的最適化問題もかなり
多数存在する。これらはＬＰ問題ではない。例えば、航
空輸送業者によって輸送される積荷の総量は、当該業者
臼らが所有（ある費用で）している飛行機及び当該業者
が賃借（別な費用で）できる飛行機の容量を越えること
はできない。このような状況は、通常数学的には、不等
式によって表現される束縛条件の組としてモデル化され
、そのような状況においては、最小化さるべき費用関数
は、しばしば非線形である。例えば輸送業者が貸借機数
を増加させるにつれて（１機あたりの）貸借費用は減少
し、貸借可能な飛行機の供給がある点にまで減少すると
１機あたりの貸借コストは再び上昇し始める。この種の
関係は、コンベックス（ｃｏｎｖｅｘ−凸−）と呼称さ
れる。

以下の記述においては、資源割当ての結果が、オペレー
ティングパラメータが線形な束縛条件に従い、最小にさ
るべき費用関数が非線形であるような数学的モデルにな
るようなシステムは、“非線形関数−線形拘束″　（Ｎ
ＬＦＬＣ）システムと呼称される。特に重要なのは、２
次関数である費用関数によって特徴づけられる、ＮＬＦ
ＬＣシステム内のサブセットである。２次費用関数は凸
関数であり、当該関数上のあらゆる２点を結ぶ直線は当
該関数上の他の全ての点と交わらないという性質を有し
ている。この様子は第１図に示されている。第１図にお
いて、曲線ｌＯは、２変数Ｘ及びｙの関数を示している
。曲線ｌＯ上のあらゆる２点、例えば点１７及びｆｉｌ
ｌ、は直線１９によって結ばれるが、直線１９は、曲線
ｌＯと交差しない。よって曲線ｌＯは２次関数である。

他方、曲線４０は２次関数ではない。なぜなら、点３９
及び３８を結ぶ直線４６は、曲線４０上の他の２点と交
差するからである。しかしながら、点３９と点３７とを
結ぶ直線４７は、曲線４０との他の点では交わらない。

よって、曲線４０は２次関数的領域を有していると言う
ことができる。

ＮＬＦＬＣ問題としてモデル化されうる資源割当て問題
は、例えば、エヌ、カーマーカー（Ｎ、Ｋａｒｍａｒｋ
ａｒ）による米国特許箱４，７４４，０２８号のような
独創的な発明において記述されているような、従来技術
に係る線形プログラミング（Ｌ　Ｐ）に係るものと同一
の方法で図示することが可能である。

すなわち、資源割当てプロセスにおいて変化させられる
各々のパラメータは、多次元直交空間における次元とし
てみなされ、適切な解の組は、各々多次元空間における
面を記述する、当該システムの線形束縛条件によって規
定される体積内で見出される。互いに交差しあう多次元
平面の組が当該体積を形成する。互いに交差しあう多次
元平面によって形成された多次元表面は、しばしば“ポ
リトープ°と呼称され、その側面は、しばしば“ウオー
ル″と呼称される。一般に、ＮＬＦＬＣ問題に対する最
適解はポリトープのウオール上にあることは公知である
。このことは、最適解がポリトープの“頂点″に位置す
るＬＰ問題の場合（費用関数がパラメータの線形関数で
ある場合）と対照的である。

ＮＬＦＬＣ問題の解法についての従来技法の概要は、ビ
ー・イー・ジル（Ｐ、Ｅ、Ｇｉｌ＋）　、ダブリュー・
マレ−（Ｗ、Ｍｕｒｒａｙ）　、及び、エム・エイチ・
ライト（Ｍ、Ｈ，Ｖｒｌｇｈｔ）による“実際の最適イ
じ（アカデミツク・プレス（Ａｅａｄｅｍｌｃ　Ｐｒｅ
ｓｓ）社、１９８１年）に見出される。しかしながら、
これらの方法は、非常に大きな問題を解くことはできず
、これらの方法で解くことが可能な問題では、解に到達
するまでに比較的長い時間が必要である。簡単に述べれ
ば、動作中のプロセス、システム、あるいは装置の多少
なりとも連続的な制御を行なうために、中庸な規模の資
源割当て問題をリアルタイムデ（すなわち、十分に速く
）解くためには、これらの方法は適していない。その欠
点は、これらの方法は、最適割当て戦略に達する以前に
、多くのコンピュータタイムを消費する、という事実に
由来する。

線形プログラムを解くための既知の方法に関する計算上
の困難を克服するためにエヌ・ケー・カーマーカーは、
前掲の米国特許第４，７４４．０２８号に記載されてい
る新たな方法を発明した。この方法に従って、適切な開
始点がポリトープの内部から選択され、当該ポリトープ
の最適頂点に向かって局所的に最大変化をする方向に一
連の移動がなされる。この、最急“降下”の方向は、最
適化されているパラメータ（変数））に依存しない。計
算可能な大きさの刻みがその方向にとられ、希望されて
いる最適頂点に充分近い点に到達するまで、当該プロセ
スが反復される。カーマーカーによるアルゴリズムの１
つの特徴的な側面は、前述の手続きが変換された空間内
で実行され、その結果が各反復毎に元の空間に逆変換さ
れることである。

カーマーカーによって実行された変換（“射影（プロジ
ェクティブ）”変換と呼ばれるが、問題に係る束縛条件
に関するものであることに留意することは重要である。

費用関数に関しては、何ら特別な変換はなされていない
（必要でないから）。

射影変換によって費用関数の線形性は保存されている。

しかしながら、この方法は、−殻内なＮＬＦＬＣ問題の
最適化には適していない。なぜなら、非線形費用関数に
おいては、“降下方向°　（勾配）が、最適化さるべき
パラメータ（変数）の関数となるからである。射影変換
あるいはその変形（例えば、アフィンスケーリング）は
、この状況を変えることができない。

［発明の概要］ 本発明は、一部ヴアンプルベイ（Ｖａｎｄｅｒｂｅｌ）
による米国特許第４．７４４．０２６号（１９８８年５
月ｌＯ日付）において記述されたものと同様な方法で、
資源割当て問題の解を得る方法に関するものである。詳
細に述べれば、資源割当て問題が反復法により解かれ、
各反復毎に、アフィンスケーリングに先立って変換が実
行される。当該変換は、前述の問題を、モデル化された
システムを、（楕円装置用表面を有する）５費用関数か
ら（球面装置用関数を有する）球面形式へ変換するため
に、変換することによって解消する。−度変換されると
、アフィンスケーリングが実行され、反復が継続される
。

当該変換を行なうために、ポリトープにおける最適点の
検索が、球面の特徴的な幾何学的性質ゆえに、非常に効
率的に行われる。当該変換を行なわないと検索が非常に
非効率的になるばかりでなく、ある場合には不完全なも
のとなる。

ＬＰの場合に経験するものと同様、ある場合には、最適
解を含まない、当該ポリトープのウオールに“魅かれる
”可能性がある。この本質的困難は、“魅かれた”解を
誤ったウオールから費用曲面に沿ってより良い位置へ“
押出す“ことによって克服されている。この手続きによ
り、解の検索が大幅に高速化される。

既に述べたように、ＱＰ　（２次関数）問題は、−殻内
なＮＬＦＬＣ問題の特別な場合である。ＱＰ問題におい
ては、費用関数は比較的ゆっくり、かつ、予測可能なよ
うに変化するが、−殻内なＮＬＦＬＣ問題においては、
費用表面の特性は、各点毎に急激に変化する。このよう
に変化する費用関数の存在下で改善された費用割当てを
実現するために、直線検索動作が、局所最適点をステッ
プ毎に追跡して、選択された方向での最小費用を飛び越
えてしまうステップが行われないことを保証するために
、実行される。

［実施例の説明］ 「タスク」 以下の記述においては、まずＱＰ問題が取上げられる。

なぜなら、ＱＰ問題はより理解が容易で、かつ、ＮＬＦ
ＬＣ問題のうちの重要なサブセットであるからである。

その後、その結果が、ＮＬＦＬＣ問題の一般形に拡張さ
れ、いくつかの修正が行なわれる。さらに、簡単のため
、かつ、人間の知覚の限界を考慮して、添付図面は、全
て、２次元のもののみに限定されている。しかしながら
、実際の問題における次元数（決定変数の数）は、数百
でも数千でも、さらには、数百万でもかまわない。さら
に、−殺性を失うことなく、費用の最小かのみが議論さ
れているが、利益を最大にすることも同様に処理されう
る、ということが理解されている。

第２図は、システムの全ての機能状態の組を包含する２
次元ポリトープ１１を表わしている。当該ポリトープ内
の各点は、割当てに係る、とりうる状態に対応している
。よってポリトープ１１内部の点Ｉ４は、とりつる点で
ある。第２図において、楕円輪郭１２及び１３は、定置
用表面である。すなわち、表面１３上の全ての点（例え
ば、状態１５）に係る割当ての費用は一定である。

さらに、当該費用は、表面１２上の全ての点（例えば、
状態１４）に係る割当ての費用より小さい。

第２図のシステムに関連した試みは、割当て費用が最小
（最内部の楕円に対応する）かつ、同時に、実際に到達
しうる（ホトリーブ内部にある）状態に到達することで
ある。このようにして到達された状態が当該割当てタス
クに対する最適解であり、第２図においては点１６であ
る。点１６は、何ら束縛条件を与えない場合の最適割当
てであることに留意されたい。これはＱＰ問題における
非常に特別な場合であり、この踵のものの発生は、実生
活における物理的資源割当て問題においては非常に稀で
ある。

より現実的なＱＰ問題が第３図に示されている。

束縛条件を与えない場合の最適値２１はとりえない。

なぜなら点２１はポリトープ２４の外部にあるからであ
る。よって、第３図のシステムに対する最適状態は、ポ
リトープ２４のウオール２３上に位置する点２２である
。費用の最適値は、楕円２５に係る費用である。

本発明に係る方法は、とりうる初期点２６より開始され
、ステップ２９．３０等において動径方向に、しかし、
常にポリトープ２４の内部に存在しながら（すなわち、
実現可能性を保ちながら）、各々最適実現可能点２２に
接近していく状態２７．２８等に進む。

ｆＱＰ状況」 標準なベクトル記法を用いて、代表的なＱＰ間、題は以
下の様に表現されうる： ＡＩ　＝　ｂ およびＸ≧０という正定値束縛条件の下である。

ここで、Ｘは、“解ベクトル“と呼称されるｎ成分ベク
トル、Ｑは、“費用マトリックス”と呼称される、（少
なくとも半玉定値の）ｎＸｎ行列、Ｃは“費用ベクトル
”と呼称されるｎ成分のベクトル、Ａは“束縛条件マト
リックス“と呼称されるｍｘｎ行列、及び、ｂは、束縛
条件制限を示す、ｍ成分のベクトルである。

上述のＱＰ問題の表現は、一般には、“標準形式”と呼
称されている。ジル等による前掲書を参照されたい。

ＱＰ問題に係る全ての実在関数及び全ての束縛関係は、
“弛緩”及び“余剰“変数として知られているものを利
用して、簡潔な代数操作によってこの形式に還元されう
る。これ等の技法は、従来技術において公知であり、例
えば、前掲の、ヴアンテルベイによる米国特許節４．７
４４，０２６号に記載されている。

第２図に示された特別のＱＰ問題（束縛条件を課さない
場合の最小値がポリトープの内部に存在する）の場合に
は、最適解及びそれに対応する費用は、 Ｘ、１．−　＝　Ｑ−’　ｃ により容易に計算され、直接 を計算すればよい。

ＱＰ問題の一般的な場合（束縛条件を課さない場合の最
小値がポリトープの外部に存在する）には、カーマーカ
ーによってなされたのと同様に、費用関数の勾配に従う
ことによって求められうる。

しかしながら、この手続きは、以下に示されるような理
由で非効率的である。

第４図において、直線３２及び３３は、定置用表面３５
及び３６にそれぞれ直交している勾配（すなわち検索方
向）である。勾配の概念のみに従って進む場合には、解
は、ある状態、例えば３０、から開始して勾配（３２）
に従って別な状態、例えば３１．へ進む。状態３１は、
勾配の変化に関連する基準に基づいて選択される： より詳細に述べれば、現在の方向（３２）が他の定置用
表面、例えば、３６に接しているという決定に基づいて
いる。この条件が検出されると、新たな勾配が計算され
、解が状態３１から次の状態、例えば点４８で表わされ
る状態へ進む。目的は、このようにして最適点３４に到
達することである。しかしながら、以上より観察される
ように、この手続きは最適点に到達する以前にか゛なり
“ジクザク”運動をしてしまう。

本発明は、上述の問題点を、楕円（多次元の場合は、楕
円体）費用関数輪郭を円形（多次元の場合には球形）費
用関数輪郭に変形することによって克服する。よって、
第５図において、球面の特別な幾何学的性質により、検
索方向４１常に輪郭４２．４３．４４等に直交しており
、当該検索方向は、最適状態４５に近接した方向である
ように設定されている。

上述の考えを数学的に翻訳すると、変数Ｘ（解ベクトル
）の ？＝Ｌ”ｘ への変換となる。ここで、Ｌは費用関数ＱにＱ＝ＬＬ。

のように関係しているベクトルである。ｘ＞Ｏではある
が、ｘｌは何ら拘束をうけていないことに留意されたい
。

この変換に引き続いて、当該問題全体が、現在の状態（
点）を束縛条件ウオールから共通距離μだけ離れた点ヘ
マッピングすることによって、スケリング（アフィンス
ケーリング）される。ここで、μは正のスカラーである
。このプロセスは、数学的には、積′１５−１ｘによっ
て表現される。ここで、Ｄは、対角要素が（１／μ）ｘ
ｌに設定された対角行列である。第６図には、スケーリ
ング前及びスケーリング後のポリトープが示されており
、元の（スケーリング前の）ポリトープ５１内の現在の
状態５５が、スケーリング後のポリトープ５２内の状態
５６にマツピングされており、第１現象内のウオールか
ら距離μの位置におかれている。

ある種の数学的操作によって、状ＢＸＯからの、割当て
費用を最小にするための移動方向（ステップ方向）が、 δｘ、、＝−（１−ＨＡ”（ＡＨＡＴ）−１ＡＳＨ（Ｑ
ｘ’−ｃ）　　（７）で表現されることが示される。こ
こでＨは（λＱ＋　Ｄ−２）−１に等しく、Ｄｘ　　は
ｘ０成分を対角成分とする対角行列、及びλは正の“ス
ケーリングパラメータであり、μｍ２に設定されている
ことが望ましい。

次になすべきことは、ＸＯからδＸ　方向へのステップ
（移動）の大きさを決定するステップ長を計算すること
である。

１つの束縛条件は、もちろん、ポリトープのウオールの
存在である。ステップ長は、この束縛条件により、最近
接束縛条件ウオールへの距離の９７％に相当する で制限されている。しかしながら、別の束縛条件は、費
用関数表面の曲率に関係している。第４図に示されてい
るように、δＸ　の方向へ進む間に、費用の減少がスト
ップし、増加しはじめる点に達する。この点を越えて進
むことは、明らかに賢明ではないので、選択された方向
に沿って最小費用に達するためのステップ長を評価する
別な値が計算される。当該ステップ長は、 である。実際のステップ長は、もちろん、前記２者のう
ちの小さい方、すなわち、α−ｍＩｎ（α１１α２）で
ある。新しい状Ｂｘ１は、 ｘ’　−１−ａ＆ｐ、　　　　　　　（１０）を計算す
ることによって得られる。下降方向δＸｐへの表現は、
“零空間°定式化、と呼称される。

なぜなら、当該表現は、勾配（ＱＸｏ−Ｃ）をへの空間
に射影することによって得られるからである。当該表現
の代替表現は、“範囲空間“定式化である。前記２種の
定式化間の唯一の差異は、射影行列の作られ方である。

ＱＰアルゴリズムを範囲空間定式化したものにおいては
、検索方向は、δ％＝−ＺＴ（Ｚ（ＩＱ＋Ｄ−２７）Ｚ
Ｔ）−’Ｚ（Ｑｘ’−ｃ）、（１１）で与えられる。こ
こで、２は、Ａの“直交補空間“行列と呼称される行列
であり、あらゆるベクトルＶに対して、ＡＺＴｖ−０と
いう条件を満たす。

Ｚを作るためには、まず行列Ａを［Ｂ　Ｉ　Ｎｌで表現
する。ここで、Ｂ及びＮは、それぞれｍＸｍ及びｍｘ　
（ｎ−ｍ）の次元のの行列である。その後、 Ｚ−［（−Ｂ−１Ｎ）”　Ｉ　１１　　　　　　（１２
）に従ってＺが計算される。ここで、■は、ｍ次元の“
単位行列”である。パラメータλは、当該アルゴリズム
の収束がより速くなるように調整されうる。（ＬＰｆ、
１題の場合には、スケーリング操作は、ステップ長αｌ
に完全に吸収されてしまい、その結果、スケーリング操
作は有効ではなくなることが示されうる。）当該調整の
方法は、λに関する“検索″を行なうことであるが、λ
の値を変える度毎に逆行列を求めなければならない、と
いうことに留意されたい。それゆえ、あるλ０の近傍で
毎回逆行列を求めることなくλを調整するためには、以
下の反復が有用である。

（省）　　　　ｏ　　　　（ｎ−１）　　　　（０）　
　　　Ｑここで、ｇ　　鐸ＰＱｇ、ｇ　　　■ＰｇＯ１
ＰＯは、λ　を用いて計算された射影行列Ｃｌ−１（Ａ
　　（ＡＨＡ”　）−１Ａ］　Ｈｌ及び、ｇ０は、ｘｏ
において計算された、費用関数の勾配であり、ここでは
、ＱｘＯ−ｃである。

さらに、ある場合には、当該アルゴリズムの逐次解が束
縛条件ウオールの近傍にあることがありうる。そのよう
な状況下では、当該アルゴリズムの収束が遅くなる。こ
のような状況が生じた場合には、ポテンシャル検索メリ
ットが、解を現時点の費用関数表面上で再び中心に置く
ために用いられうる。第７図において、６１はポリトー
プであり、状！！６２らは、ウオール６５近傍の８４へ
到達するために、６３方向の移動がなされる。最適点は
状態６６である。なされるべきことは、状態６４を、定
費用軌跡６７に沿って、状態６８等のより良い位置へ移
すためにスライドさせることである。これが所謂ポテン
シャル検索である。

ポテンシャル検索の背後にある本質的な概念は、解をウ
オールから離れた所へ押出す“ブツシュベクトル″を作
ることである。もちろん、当該ブツシュベクトルによっ
て描かれる軌跡は、可能性を維持しつつ、定置用でなけ
ればならない。

当該押し出しは、Ｘ　における射影された垂線ｎ　を評
価することによって実行される。ここで、Ｘ　は、ウオ
ールから押し出されるべき点である。

Ｘ　を費用が不変であるようにＸ　によって描かｔ　　
　　　　　　　　　　　　　　　　　　　　　　。

れた軌跡とすると、 ｎ、　＝　Ｚ”（ＺＱＺ０′）’　Ｚｇｏ　　　　　　
（１４）及び、 ｖｐ　＝　ＣＺＴ（Ｚｎ２０′）−’　Ｚｖ６　　　　
　　（１５）によってｎ　及びＶ　を計算することがで
きる。

ｖｐ ここで、 （ａ）　ＺはＡＺ”ｖ−０があらゆるベクトルＶに対し
て成り立つような行列である、 （ｂ）ｇｏは、ｘＯにおける曲面の勾配（ｄ）　Ｈ−（
λＱ＋Ｄ−２）、及び、（ｅ）　ｖ　　はｓ　　ｖＯＨ
＝ＸｏＨ″″１−βｋＩ（ｉ　＝　１．２．・＝ｎ　）
として得られる「カーマーカー・ブツシュ・ベクトル」
である。

ここで、 （ＸｔＳ）が最小となるように実行されうる。例えば、
第８図において、７１は球状費用関数を表わし、７２及
び７３は、状態７５に関する射影された垂線及び射影さ
れたブツシュベクトル、及び曲線７４は定費用軌跡を表
わしている。

「ＮＬＦＬｃへの一般化」 本発明に係るＱＰアルゴリズムは、費用関数が２次関数
ではないが、凸であるようなシステムにおけるＮＬＦＬ
Ｃ問題に対して一般化されつる。

従ってタスクは、 である。

αをＩＩ　Ｑ　１１とするとき（１１ ルムを表わす）、軌跡 １１はスペクトルノ ｘ、　＝　句＋　（Ｃｏｓａｔ　−１）ｎｐ　＋　（Ｓ
ｉｎ　０１）Ｖ。

に沿った検索は、“ポテンシャル関数。

ｍｉｎ　　ｆ（ｘ）　　　　　　　　　（１７）として
表わされる。ただし、線形束縛条件の組Ａｘ　＝　ｂ Ｘ≧０ の下である。

ｇ　（ｘ）を、Ｘにおけるｆ　（ｘ）の勾配（すなわち
、　　（ｘ）−ｇ　（ｘ））　、Ｇ　（ｘ）をＸにお本
発明に係るＱＰアルゴリズムにおけるＱをＧ（ｘ）で、
かつ、Ｑｚ−ｃをｇ　（ｘ）で、それぞれ置換すること
によって、ＮＬＦＬＣ問題を解くための新たなアルゴリ
ズムが得られる。しかしながら、前記ＱＰアルゴリズム
とは異なり、Ｑの項がベクトルＸに依存し、このために
、ステップ長α２に対する前記表式（９）が無効となる
。よって、ＮＬＦＬＣ問題の場合には、高速な“線検索
メリット″によって決定される。当該メリットにおいて
は、下降ステップ長は、下降方向におけるｆ（ｘ０）の
逐次評価によって決定される。

上述の線検索と組合わせることによって、本発明に係る
ＮＬＦＬＣ問題解決法アルゴリズムは、以下のように表
現される： 開始可能な解ｘ０に沿って、０くβく１及び０くγく１
なる２定数β及びγを選択する。その後、Ｑ及びＱ　　
Ｏ−ｃをそれぞれＧ（ｘｏ）及びｇ（Ｘｏ）で置換して
計算する。（９）式におけるα２を、ＱがＧ　（ｘｏ　
）で置換された場合のポテンシャルステップ長の推定値
として用いる。最後に、真のステップ長を、 ｆ（ｘ’　−ｃｏｘ、）≦ｆ（ｘ’）　−１０ｇ”（ｘ
’島（１９）が満たされるように決定する。ここで、α
−ｍｉｎ（−β１．αｔ）　　　　　　（２０）であり
、項α１は式（８）によって与えられ、ｈは、（１９）
を満足する（ゼロを含む）第１正整数である。

本発明に係る線検索アルゴリズムは、充分に弱い仮定の
下で収束する（最適解に達する）ことが示される。

当該手続きの残りの部分は、ポテンシャル検索に関する
以下に示される差異を除いて、前記ＱＰアルゴリズムと
同一である。当該ポテンシャル検索を実行する場合には
、ｆ　（ｘ）を２次関数で近似したものに基づいて経路
を再び中心に据える。

この再中心化法は、実現可能性を維持するものであるが
ｆ　（ｘ）を一定には保たない。例えば、第９図におい
て、状態８１は８ｚ方向に状態８３へ移される。その後
、この解は、ｆ　（ｘ）の２次関数による近似に基づい
て、定置用表面８５に沿って押出される。実際の定置用
表面は８４でありｆ　（ｘ）の近似の軌跡に沿った押し
出しは、軌跡８４及び８５の間の差（この場合には、距
離８６）が所定の値、例えば、δＪを超過した時点で中
止される。その後、新たな反復が開始される。

最後に、本発明に係る新たなアルゴリズム（ＱＰ及びＮ
ＬＦＬＣに対する）における終了基準は、εをある固定
された正の微小数とするときにが満たされることであり
、かつ、 である。

「プロセス」 民間企業の資源割当て状態を改善する等の企業の機能状
態を改善するプロセスは、まず、利用可能な資源を識別
し、資源割当て要求及び束縛条件を決定し、及び、当該
企業のおかれている特定の状況に対して意味を持つ、最
小化さるべき費用関数を選択することである。その後、
これらの情報の全ては、操作が容易となるようにシンボ
ル（変数）によって表現され、当該表現された変数に関
して、最小化タスクとしてのタスクが構成される。

このように構成され、かつ、束縛条件が線形でかつ費用
関数が凸であることが見出された場合には、本発明に係
る原理が有利に適用されうる。

このような場合には、本発明に係る方法の概略を示した
第１Ｏ図に従って、ブロック９１において、当該タスク
がＱＰあるいは一般的なＮＬＦＬＣタスクとして定式化
され、ブロック９２において、当該システムの初期の実
現可能な状態（ｘＯ）が選択され、スケーリングパラメ
ータλが選択される（ａ常、１．０）。これは“フェー
ズ１°問題と呼称される。束縛条件が線形であるので、
ＬＰの場合と同一の“フェーズ°　１操作を用いること
が可能である。このプロセスは、前述のアール・ジェイ
・ヴアンデルベイに係る米国特許節４，７４４，０２６
号に記載されている。もちろん、実際のシステムにおい
ては、初期状態の選択に係るタスクは自明である。なぜ
なら、当該企業の実際の状態が初期状態として選択され
うるからである。第１θ図において、ブロック９３は、
当該最適化問題がＱＰであるか、一般のＮＬＦＬＣであ
るかを検出するプロセスを表わしている。ＱＰ問題であ
る場合には、プロセスＡ（ブロック９４）が起動される
；他の場合にはプロセスＢ（ブロック９５）が起動され
る。

すなわち、ブロック９Ｂは、（非常に一般的にではある
が）全てのＮＬＦＬＣ問題を解く反復法を示している。

最後に、ブロック９７においては、当該企業を、当該シ
ステムの最適値の近傍に位置させるための、ブロック９
Ｂにおいて決定された割当てがなされる。プロセスＡ及
びＢは、第１１図及び第１２図により詳細に記述されて
いる。

第１１図において、ブロック１０１は、変数の個数（ｎ
）が束縛条件の個数（ｍ）よりも多いか否かを決定する
検出ステップである。（ｍ＞ｎ）の場合には、ブロック
１０３へ進んで、下降方向を決定するために、零空間定
式化を行なう。（ｒｎ＞ｎ）でない場合には、ブロック
１０２へ進んで範囲空間定式化を行なう。次に、前記２
種のステップ長（α　及びα２）がブロック１０４にお
いて計算され、ブロック１０５においては、前記計算さ
れたステップ長を用いて、前記下降方向へ、ＸＯからＸ
ｌへの移動がなされる。その後、ブロック１０６におい
て、最初に選択されたスケーリング値の調整がなされる
べきか否かが決定され、調整なされるべき場合には、ブ
ロック１０７に進んで調整が行なわれ、新たな方向が計
算され、及び、制御がブロック１０５へ再び移行する。

スケーリング値の調整が必要ないと決定された場合には
、制御はブロック１０８へと移行し、必要な場合には（
すなわちα−αｌの場合には）、前述されたように、解
を再び中心に位置させるために、ポテンシャル押し出し
がブロック１０８において実行される。最後に、ブロッ
ク１０９において、式（２１）及び（２２）によって表
現されているような収束条件がチエツクされる。当該条
件が満たされると、プロセスＡは終了する；当該条件が
満たされない場合には、制御が再びブロック１０１へと
移行する。上述のステップが前記収束条件を満たすまで
反復される。

プロセスＢはプロセスＡと非常に良く似ており、第１２
図に示されている。ブロック１１０においては、ｆ　（
ｘ）の２次関数による近似がなされる。ブロックｉｌｌ
　、　１１２　、及びｔｔａは、プロセスＡのブロック
１０１．１０２　、及び１０３と同一である。ブロック
１１４においては式（１９）によって定義されるように
ステップ長が計算され、ブロック１１２あるいは１１３
において得られた検索方向と共に利用される。

この操作は、実質的に式（２０）を用いる、ブロック１
１５において実行される。ブロック１１Ｇ及び１１７は
、プロセスＡのブロック１０Ｂ及び１０７とそれぞれ同
一である。ブロック１１８においては、実質的に式（１
４）から（１６）を用いる、第９図に関して既に記述さ
れた近似ポテンシャル押し出しが実行される。ブロック
１１９はブロック１０９と同一であり、プロセスＢはこ
れらの条件が満たされるまで反復される。

「装置」 第１３図は、本発明に従うプロセス制御システムを示し
た図である。当該プロセスは、電話通信システム、製造
プロセス、財政システム（ポートフォリオ管理システム
等）、（前述の）飛行機賃貸業、あるいは、他の、最小
化さるべき、かつ前述の凸関数的性質を有するあらゆる
産業的、技術的もしくは経済的プロセスでありうる。

費用関数評価デバイス１７０は、コンピュータ端末ある
いは他の個別のデバイスから１７１を介して費用データ
（割当て費用がいかに変化するか、に係る情報）を受信
する。デバイス１７０は、必要が固定されている必要は
なく、相異なった企業が、各々それ自体が最小にするこ
とを欲している、相異なった費用配置を選択する、とい
う事実を適応させることを目的にしている。デバイス１
７０は、入力情報を、費用関数表現にフィツトさせる。

ここで、考慮中のシステムに対する当該費用関数は、一
般に非線形であり、特に凸関数的である。当該情報は、
デバイス１７０によって、システムのあらゆる状態にお
けるフィツトされた費用関数の値を評価する、費用評価
器１７２に渡される。すなわち、当該システムの機能状
態が表現されたものが与えられると、デバイス１７２は
、与えられた費用関数に従って費用を計算する。費用を
計算するためには、デバイス１７２に対して、当該シス
テムの状態の記述が与えられなければならない。当該情
報はり−ド１７３を介してコントローラ１８５によって
与えられる。決定された費用はリード１７４を介してコ
ントローラ１８５に渡される。

同様に、制限レジスタ１１１３が、前記割当て変数に係
る物理的制限を記憶するために設けられている。これら
の制限は、費用データと同様にリード１８４を介してシ
ステムに入力される。

第１３図のシステムは、さらに、当該企業に係る束縛条
件係数を動的に検出するセンサ１ｇＧ　、１８７・・・
、１８８を存している。例えば、航空会社においては、
相異なった位置における飛行機の数は、当然、時間と共
に変化し、機能している空港の数でさえも揺動する。セ
ンサ１８６−１８８がモニタするのはまさにこのような
“環境の１変化である。束縛条件センサ１８Ｂ−１８８
は、各々、対応する変化デテクタ、１８９．１９０・・
・、１９１を有している。当該デテクタは、対応するセ
ンサの出力の変化を検出する。これら各々のデテクタか
らの変化表示信号は、変化バス１９２に印加され、ＡＮ
Ｄゲート１９３へ導かれる。ゲート１９３に対しては、
さらに、リード１９４を介して、最適化手続きの終了を
示す信号がコントローラ１８５から与えられる。変化デ
テクタの各々の個別の出力ボートを通じて、センサＩＨ
−１８８の出力は、コントローラ１８５に印加される。

第１３図のコントローラ１８５は、望ましい具体例にお
いては、第１図から第９図までにおいて示された概念を
利用して第１０．１１及び１２図の流れ図をインプリメ
ントしたプログラムがストアされている、デジタルコン
ピュータである。コントローラ［８５は、第１０図から
第１２図までの流れ図によって記述された機能を実行す
るため、すなわち、第１図から第９図までの概念を具体
化するため、に設計された、配線による複合回路よりな
るものであってもよい。

第１３図のＮＬＦＬＣコントローラ１８５は、第３図、
第４図、あるいは第５図に示された非常に高速な手続き
を用いるため、レジスタ１９５−１９７に対する制御値
が非常に短時間のうちに利用可能となる。さらに、束縛
条件が変化すると、これらの変化がセンサ１８Ｂ−１８
８によってセンスされ、デテクタ１．８９−１９１によ
ってデテクトされて、一部ＡＮＤゲート１９３をイネー
ブルするために用いられる。第１０−１２図の手続きが
終了すると、コントトローラ１８５はプロセス制御信号
を生成して当該信号をレジスタ１９５−１９７へ伝達す
る。同時にコントローラ１８５はリード１９４上にイネ
ーブル信号を生成してＡＮＤゲート１９３へ伝達し、Ａ
ＮＤゲート１９３のイネーブルを完了する。その後全体
のプロセスが反復される。

現代の制御理論領域における、本発明が適用されうる代
表的な問題は、ロボットの制御等の、システムの確率論
的な制御である。この型の問題に係る記述は、ケイ・ジ
ェイφアストローム（Ｋ、Ｊ。

Ａｓｔｒｏｉ）及びビー・ウィッテンマルク（Ｂ、Ｗｅ
ｔｔｅｎｍａｒｋ）による“コンピュータによって制御
されたシステム゛　（プレンティスホール（Ｐｒｅｎｔ
ｉｃｅ　Ｈａｌｌ）社、１９８６年）という本に見出さ
れる。

本発明による利益をうけるその他の問題は、経済に係る
ポートフォリオマネージメント、電源供給会社の最適負
荷問題、及び最適スタッフ割当て問題である。

実際のＮＬＦＬＣ問題の大部分の場合、当該問題に係る
行列は本質的に過疎であり、過疎行列に係る技法が第１
０図から第１２図までに示された操作に用いられうろこ
とに留意されたい。

【図面の簡単な説明】

第１図は、ある関数の凸関数的性質を表わした図； 第２図は、ＱＰ問題における最適資源割当ての特別な場
合を示した図： 第３図は、ＱＰ問題における最適資源割当ての一般的な
場合を、本発明に係る新たなアルゴリズムの反復ステッ
プに沿って示した図； 第４図は、楕円型費用関数表面での方向検索に係る“ジ
グザグ１現象を示した図； 第５図は、球面型費用関数表面における計算の進展の様
子を示した図； 第６図は、アフィンスケーリングの概念を図示した図； 第７図は、ＱＰ問題における、費用関数表面上でのポテ
ンシャルの押し出しを示した図；第８図は、ポテンシャ
ル押し出しに用いられるね“射影直交″ベクトル及び“
射影押し出し゛ベクトルの概念を示した図； 第９図は、一般的なＮＬＦＬＣ問題を扱うための、ＱＰ
問題において用いられた押し出しに対する修正を示した
図； 第１０図は、ＱＰ問題を一般的なＮＬＦＬＣ問題から分
離し、それらを解く適切なプロセスを選択する手続きを
表わす一般的な流れ図； 第１１図は、本発明に係る新たなアルゴリズムを用いた
、ＱＰ問題を解く手続き（プロセスＡ）を表わす流れ図
； 第１２図は、本発明に係る新たなアルゴリズムを用いた
、一般的なＮＬＦＬＣ問題（ＱＰ問題以外）を解く手続
き（プロセスＢ）を表わす流れ図；及び、 第１３図は、第１図から第７図に示された概念を用いた
、資源割当て／制御システムのブロック図である。 出　願　人：アメリカン　テレフォン　アンドＦＩＧ、
　　６ ＦＩＧ、　　８ ＦＩＧ ＋１

Claims (12)

【特許請求の範囲】
1. （１）ある事業計画での産業設備（ｆａｃｉｌｉｔｉｅ
   ｓ）を、該設備の選択された割当てに係る費用を低減す
   るように割当てる方法であって、１組の束縛条件によっ
   て線形に束縛され、前記費用がある与えられた凸関数と
   して表現されるものにおいて、前記設備割当てに係る反
   復を有し、 各反復が、 関連する費用を有する潜在的設備割当てを受け取り、所
   定の停止基準が充足されない限り、次の反復のための潜
   在的設備割当てを作成するステップと； 前記受け取られた潜在的設備割当ての表現に作用して、
   該潜在的設備割当ての変換された表現を形成し、該潜在
   的設備割当ての変換された表現の成分が等しく（アフィ
   ンスケーリング）、かつ同一の関連費用を有する他の設
   備割当ての変換された表現の成分の２乗和が前記潜在的
   設備割当ての成分の２乗和に等しくする、スケーリング
   された球面変換を実行するステップと； 次の反復のための前記新たな潜在的設備割当てを生成す
   るために用いられる移動（ｔｒａｎｓｌａｔｉｏｎ）ベ
   クトルを作成するステップと； 前記移動ベクトルが所定のしきい値以下の時にプロセス
   を停止させる信号を作成するために、前記移動ベクトル
   の成分を試験するステップと；前記移動ベクトルが前記
   所定のしきい値以下でない時に、次の反復のための前記
   新たな潜在的設備割当てを作成するステップと； 前記移動ベクトルが前記所定のしきい値以下である場合
   に、最後に作成された新たな潜在的設備割当てを前記事
   業計画に適用するステップと；を有することを特徴とす
   る割当て最適化方法。
2. （２）ある事業計画での産業設備（ｆａｃｉｌｉｔｉｅ
   ｓ）を、該設備の選択された割当てに係る費用を低減す
   るように割当てる方法であって、１組の束縛条件によっ
   て線形に束縛され、前記費用がある与えられた凸関数と
   して表現されるものにおいて、前記設備割当てに係る反
   復を有し、 各反復が、 潜在的設備割当てを受け取り、所定の停止基準が充足さ
   れない限り、次の反復のための潜在的設備割当てを作成
   するステップと； 潜在的設備割当ての表現（ベクトルｘ＾０）を変換して
   、変換された設備割当て表現の成分（ｘ＾０′の成分）
   の２乗和が一定値であり、前記変換された潜在的設備割
   当て（ｘ＾０′）の費用と同一の費用を有する変換され
   た他の設備割当ての表現（ｘ＾１′、ｘ＾２′、・・・
   、）の成分の２乗和が前記一定値と等しいように前記事
   業計画に対する球面費用関数を作成する変換ステップと
   ； 潜在的設備割当ての表現ｘ＾０を、ベクトルｘ＾０″で
   表現され同一スケーリングされた設備割当て（ベクトル
   ｘ＾０″の成分）を有するスケーリングされた潜在的設
   備割当てへ前記潜在的設備割当てを移動するために、ス
   ケーリングするステップと； 次の反復のための前記新たな潜在的設備割当てを生成す
   るために用いられる移動ベクトルを作成するステップと
   ； 前記移動ベクトルの成分を、前記移動ベクトルが所定の
   しきい値以下である場合に、プロセスを停止させる信号
   を作成するために試験するステップと； 前記移動ベクトルが前記所定のしきい値以下でない場合
   に、次の反復のための前記新たな潜在的設備割当てを作
   成するステップと； 前記移動ベクトルが前記所定のしきい値以下である場合
   に、最後に作成された新たな潜在的設備割当てを前記事
   業計画に対して適用するステップと； を有することを特徴とする割当て最適化方法。
3. （３）スケーリングされた球面変換を実行するステップ
   が、 潜在的設備割当ての表現を、前記事業計画に対する、変
   換された設備割当て表現の成分の２乗和が一定値であり
   、前記変換された潜在的設備割当ての費用と同一の費用
   を有する、変換された他の設備割当ての表現の成分の２
   乗和が前記一定値と等しいような、球面費用関数を作成
   するために変換するステップと； 潜在的設備割当ての表現ｘ＾０を、当該潜在的設備割当
   てを、スケーリングされた潜在的設備割当てへ移動する
   ためにスケーリングし、同一のスケーリングされた機能
   割当てを有するようにさせるステップと； を有することを特徴とする請求項１記載の割当て最適化
   方法。
4. （４）スケーリングされた球面変換を実行するステップ
   が、 潜在的設備割当ての表現ｘ＾０を、当該潜在的設備割当
   てを、スケーリングされた潜在的設備割当てへ移動する
   ためにスケーリングし、同一のスケーリングされた設備
   割当てを有するようにさせるステップと； 潜在的設備割当ての表現を前記事業計画に対する、変換
   された設備割当て表現の成分の２乗和が一定値であり、
   前記変換された潜在的設備割当ての費用と同一の費用を
   有する、変換された別の設備割当ての表現の成分の２乗
   和が前記一定値と等しいような、球面費用関数を作成す
   るために変換するステップと； を有することを特徴とする請求項１記載の割当て最適化
   方法。
5. （５）事業計画の設備を、当該事業計画を機能させるた
   めの、ある選択された前記設備の割当てに係る費用を低
   減するように割当てる、資源割当てシステムであって、
   前記設備の割当てが線形に束縛され、前記費用がある与
   えられた凸関数によって表現されているものにおいて、 前記設備の割当てに係る現在の状態を決定するＮ個（Ｎ
   は正整数）のセンサと； 前記設備の割当てを与える手段と； 前記センサに応答して、前記センサの出力信号を変更可
   能なメモリにストアし、それによって、前記設備の、Ｎ
   個の成分よりなるストアされた割当て状態を形成する手
   段と； 前記ストア手段に応答して、前記ストアされた割当て状
   態に対して、変換された割当て状態信号を形成し、前記
   変換された割当て状態信号の成分が等しく、同一費用を
   有する他の設備割当て状態の変換された表現の成分の２
   乗和が、前記変換された割当て状態の成分の２乗和に等
   しいような、スケーリングされた球面変換を実行する変
   換手段と； 前記変換手段に応答して、移動ベクトル信号を生成する
   移動手段と； 前記移動手段に応答して、前記移動ベクトル信号が所定
   のしきい値以下である場合にプロセス停止信号を作成す
   る比較手段と； 前記比較手段に応答して、改善された設備を割当て状態
   を作成し、当該設備割当て状態を前記変更可能メモリ内
   にストアする手段と； 前記プロセス停止手段に応答して、前記設備割当てを与
   える前記手段に対して、前記改善された設備割当て状態
   の最も新しいものを与える手段と；よりなることを特徴
   とする割当て最適化システム。
6. （６）最適化基準に従って、被制御プロセスの実行状況
   を最適化するシステムにおいて、 制御信号による制御信号の組に応答して、前記プロセス
   を制御するプロセス制御デバイスと；入力信号によって
   、前記プロセスの動作に影響を与える変化する状況をセ
   ンスする複数個のセンサと； 前記センサと前記プロセス制御デバイスとの間に配置さ
   れた、前記プロセス制御デバイスに与えられる制御信号
   を生成する非線形プログラミングコントローラ（ここで
   、前記制御信号の生成は前記最適化基準に従ってなされ
   、かつ、前記最適化基準は、前記入力信号の非線形凸関
   数である）と；を有し、 前記コントローラが、連続する、ある時点において確実
   に実現可能な制御信号の組を反復して識別し、制御信号
   に係る束縛条件が正規化された空間における、同様に正
   規化された最適化基準の最急勾配方向の各々のその時点
   における制御信号の組を選択することを特徴とする割当
   て最適化システム。
7. （７）複数の物理的資源ユーザ間での、束縛条件Ａ＿ｉ
   ＿ｊｘ＿ｉ＝ｂ＿ｊ及びｘ＿ｉ≧０（ｉ＝１、ｎ；ｊ＝
   １、ｍ）に従う複数の資源ｘ＿ｉ（ｉ＝１、ｎ）によっ
   て特徴付けられた、商業活動を営む事業計画の機能状態
   を改善する方法において、 当該方法は、費用関数（１／２）ｘ＿ｉＱ＿ｉ＿ｊｘ＿
   ｉ−ｃ＿ｉｘ＿ｉ（ｉ＝１、ｎ；ｊ＝１、ｍ）を最適化
   することを目的とし、 （ａ）前記束縛条件を満たす初期割当てｘ＾０＝（ｘ＾
   ０＿１、ｘ＾０＿２、・・・、ｚ＾０＿ｎ）を選択する
   ステップと； （ｂ）定費用球面を作るためにＱ＝ＬＬ＾Ｔとして、ｘ
   ′＝Ｌ＾Ｔｘという変換を用いるステップと；（ｃ）ｘ
   ＾０を束縛条件ウォールから距離μの位置に配置するた
   めに、＠Ｄ＠＝ｄｉａｇ（１／μ）（ｘ＾０＿１、ｘ＾
   ０＿２、・・・、ｘ＾０＿ｎ）として、ｙ＝Ｄ＾−＾１
   ｘ′というスケーリングを用いるステップと； （ｄ）Ｄｘ＾０をｘ＾０の成分を有する対角行列、λ＝
   μ＾−＾２、及びＩを単位行列とするとき、Ｈ＝（λＱ
   ＋Ｄｘ＾０＾−＾２）＾−＾１として、関係式δｘ＿ｐ
   ＝−［Ｉ−ＨＡ＾Ｔ（ＡＨＡ＾Ｔ）＾−＾１Ａ］Ｈ（Ｑ
   ｘ＾０−ｃ）、 あるいは、行列Ａ−［ＢＮ］とするとき、Ｚ＝［（−Ｂ
   ＾−＾１Ｎ）＾ＴＩ］として、関係式δｘ＿ｐ＝−Ｚ＾
   Ｔ（Ｚ（λＱ＋Ｄ＾−＾２ｘ＾０）Ｚ＾Ｔ）＾−＾１Ｚ
   （Ｑｘ＾０−ｃ） を用いて下降方向δｘ＿ｐを計算するステップと；（ｅ
   ）▲数式、化学式、表等があります▼ 及び、▲数式、化学式、表等があります▼ とするとき、 ステップ長α＝ｍｉｎ（α＿１、α＿２）を計算するス
   テップと； （ｆ）ｘ＾１＝ｘ＾０−αδｘｐによって新たな割当て
   ｘ１を計算するステップと； （ｇ）費用の低減が最大となるようにλを調整するステ
   ップと； （ｈ）新たな定費用表面において、α＝α＿１である場
   合には、実施例の説明において記述されているアルゴリ
   ズムによるポテンシャル押し出しを用いて再中央配置を
   行なうステップと； （ｉ）基準▲数式、化学式、表等があります▼（εは固
   定された正 の小さな数）をテストするステップと； （ｊ）基準〔Ｉ−Ａ＾Ｔ（ＡＨＡ＾Ｔ）＾−＾１ＡＨ］
   ［Ｑｘ＾０−ｃ］≧０をテストするステップと；（ｋ）
   条件（ｉ）及び（ｊ）が満たされた場合には、当該反復
   法を停止するステップと、あるいは、（ｌ）ステップ（
   ｄ）に戻って、ｘ＾０をｘ＾１で置換して反復するステ
   ップと； （ｍ）条件（ｉ）が満たされた場合には、前記資源をｘ
   ＾１に従って割当てるステップと； よりなることを特徴とする割当て最適化方法。
8. （８）束縛条件Ａ＿ｉ＿ｊｘ＿ｉ＝ｂ＿ｊ及びｘ＿ｉ≧
   ０（ｉ＝１、ｎ；ｊ＝１、ｍ）に従う、産業上、経済上
   、あるいは技術上の資源を、複数の物理的ユーザ間で、
   一般的な凸非線形費用関数ｆ（ｘ）を最適化するように
   割当てる方法において、 （ａ）ｆ（ｘ）に関する２次関数近似を行ない、第７請
   求項のステップ（ａ）から（ｅ）までを実行するステッ
   プと； （ｂ）α＝ｍｉｎ（α＿２β＾ｈ、α＿１）とするとき
   （ｈは、前記線検索ルールを満たす（零を含む）第１正
   整数）、線検索ルールｆ（ｘ＾０−αδｘ＿ｐ）≦ｆ（
   ｘ＾０）−γαｇ＾Ｔ（ｘ＾０）δｘ＿ｐに従ってステ
   ップ長αを計算するステップと；（ｃ）請求項７のステ
   ップ（ｆ）に従って、新たな割当てを得るステップと； （ｄ）請求項７のステップ（ｇ）に従って、スケール調
   整をするステップと； （ｅ）請求項７のステップ（ｈ）に対して、実際の関数
   値とその２次近似との差も考慮して移動が停止される、
   という修正を行なった上で、それに従って定費用表面上
   での再中央配置を行なうステップと； （ｆ）請求項７のステップ（ｉ）、（ｊ）、（ｋ）及び
   （ｌ）にしたがって停止基準をテストするステップと； （ｇ）請求項７のステップ（ｍ）と同様に資源を分割す
   るステップと； よりなることを特徴とする割当て最適化方法。
9. （９）資源を複数のユーザ間で最適に割当てる装置にお
   いて、当該装置が、 前記ユーザ、前記資源の利用可能性、及び、前記資源の
   割当てに係る束縛条件、に係る情報を受け取る手段と； 請求項７又は請求項８に係るアルゴリズムを用いて、前
   記ユーザ間での前記資源の最適割当てを、反復して近似
   する手段と； 前記近似手段によって近似された、前記資源に係る割当
   ての最新のものに従って、前記資源を割当てる手段と； よりなることを特徴とする割当て最適化装置。
10. （１０）前記次の反復に対する新たな潜在的設備割当て
    を作成する前記ステップが、前記移動ベクトルの方向に
    沿った線検索を含むことを特徴とする請求項１記載の最
    適化方法。
11. （１１）前記次の反復に対する新たな潜在的設備割当て
    を作成する前記ステップが、さらに、前記移動ベクトル
    方向に沿って移動した位置に対応する潜在的設備割当て
    に係る費用よりも費用が高くないような潜在的設備割当
    てを識別するために前記移動ベクトルの方向に沿った線
    検索を含むことを特徴とする請求項１に記載の最適化方
    法。
12. （１２）前記次の反復に対する新たな潜在的設備割当て
    を作成する前記ステップが、さらに、前記移動ベクトル
    方向に沿って移動した位置に対応する潜在的設備割当て
    に係る費用よりも費用が高くなく、かつ、前記束縛条件
    のいずれに対しても、所定のしきい値より近くない潜在
    的設備割当てを識別するために、前記移動ベクトルの方
    向に沿った線検索を含むことを特徴とする請求項１記載
    の最適化方法。