Karmarkar's algorithmとは? わかりやすく解説

Weblio 辞書 > 学問 > OR事典 > Karmarkar's algorithmの意味・解説 

カーマーカーのアルゴリズム

(Karmarkar's algorithm から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/02/28 10:04 UTC 版)

カーマーカーのアルゴリズム: Karmarkar's algorithm)とは1984年ナレンドラ・カーマーカーにより発見された線形計画問題の解法である。このアルゴリズムは、しばしば、カーマーカー法: Karmarkar's method)とも呼ばれる。また、このアルゴリズムを発明とする特許米国日本で出願され、請求特許は時折カーマーカー特許 (Karmarkar's patent) とも呼称される。

カーマーカーのアルゴリズムは、線形計画問題に対する多項式時間アルゴリズムで初めての実用的なものである。楕円体法も多項式時間アルゴリズムであるが、実用上の効率は良くない。

カーマーカーのアルゴリズムは内点法の一種である。内点法は、候補解を実行可能領域の境界に沿って更新する単体法とは異なり、実行可能領域の内部を通るよう更新する。この更新は解の精度を定数倍改善し、これを繰り返すことで最適解optimal solution)に収束する[1]

アルゴリズム

行列

例解

以下の線形計画問題を考える。

maximize
Optimization computes maxima and minima.
非線形(制約付き)
凸最適化
組合せ最適化
メタヒューリスティクス


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

カテゴリ一覧

すべての辞書の索引



Weblioのサービス

「Karmarkar's algorithm」の関連用語


2
14% |||||


Karmarkar's algorithmのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



Karmarkar's algorithmのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2025 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのカーマーカーのアルゴリズム (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS