情報科学 の 線形計画問題に関する解説。

株式会社 日立ソリューションズ

HITACHI Inspire the Next

  • ホーム
  • ソリューション・商品
  • 事例紹介
  • セミナー・展示会
  • ビジネスコラム
  • 企業情報
  • お問い合わせ

線形計画問題

読み方、または別称:せんけいけいかくもんだい

線形計画問題(せんけいけいかくもんだい)とは、最適化問題で目的関数が線型関数となる。そして、線形関数の等式と不等式で制約条件が記述できる問題のことである。行列やベクトルを使って表現すると、行列Aとベクトルb,cが与えられた時、Ax=b,x _0を満たしながらcTxを最小化するベクトルxを求める問題を指す。
これを標準型といい、制約条件に線形不等式を含んでいる問題も、スラック変数を加えると簡単に標準型に変換することが可能となる。また、最大化問題の場合は、目的関数の符号を反転させることで最小化問題となる。
線形計画問題を解くアルゴリズムとしては、1947年にG.B. Dantzig提案の「シンプレックス法」が有名である。これは、実用上は高速であり、ほとんど常に変数の数・制約条件の数の大きいほうのオーダーを反復する。
しかし、Dantzigが提唱したものは理論的には多項式時間アルゴリズムではなく、常に多項式時間で解かれるピボット規則の存在性も、未解決問題となっている。

ページトップへ戻る

話題の用語

ITと社会用語辞典

ワークロード

ワークロードとは、システムのパフォーマンスを適正な状態に保つための指標のこと。

インターネット用語辞典

ライフログ

ライフログとは、人間の活動の記録(行動履歴)をデジタルデータとして記録すること、およびその記録のことである。

ページトップへ戻る

情報漏洩防止ソリューション 「秘文」

ITのお悩みをソリュっと解決! 特命課ソリュートくんがいく!

『オムニチャネル』から商品を探すページです。日立ソリューションズは、コンサルティングからシステム構築、サポートとトータルソリューションをご提供するシステムインテグレーション企業です。

ページトップへ戻る