線形計画法とは

定義

目的関数と制約条件がいずれも 1 次式 (線形) で表される最適化問題を解く手法。生産計画、輸送計画、配合問題など、限られた資源を配分して利益最大化や費用最小化を行う場面で広く使われる。シンプレックス法や内点法などのアルゴリズムで解く。

ITパスポート・基本情報での出題ポイント

基本情報では、処理手順、計算量、データの保持方法を読み取る問題で出ます。ITパスポートでも、探索やソート、ビット演算の基本的な意味を問われることがあります。手順を図や小さな例で追えるようにすると安定します。

よく問われるパターン

• 入力例に対して、処理後の値や並びを追跡する。
• データ構造の特徴から、探索・挿入・削除に向く用途を選ぶ。
• 計算量や停止条件など、処理効率に関する説明の正誤を問う。

関連する過去問

• ITパスポート 2024年 (令和6年) 問14ある商品の販売量と気温の関係が一次式で近似できるとき,予測した気温から商品の販売量を推定する手法として,適切なものは...関連: 線形計画法
• 基本情報技術者 令和3年度 科目A 修了認定試験 問77工場で、ある原料から生産している 3 種類の製品 A、B 及び C の単位量当たりの製造時間、原料所要量及び利益額を...関連: 線形計画法
• 基本情報技術者 令和2年度 科目A 修了認定試験 問52プロジェクトの日程計画を作成するのに適した技法はどれか。関連: 線形計画法
• 基本情報技術者 令和元年度 秋期 午前 問76製品 X 及び Y を生産するために2種類の原料 A, B が必要である。製品1個の生産に必要となる原料の量と調達可...関連: 線形計画法
• 情報セキュリティマネジメント 科目A 問41プロジェクトの日程計画を作成するのに適した技法はどれか。関連: 線形計画法

関連用語(アルゴリズム・データ構造)

• オートマトンおーとまとん
• 基数変換きすうへんかん
• 逆ポーランド記法ぎゃくぽーらんどきほう
• 逆ポーランド表記法ぎゃくぽーらんどひょうきほう
• クイックソートくいっくそーと
• 再帰呼出しさいきよびだし

間違えやすい用語との違い

線形計画法と同じ「アルゴリズム・データ構造」の用語では、オートマトン、基数変換、逆ポーランド記法などが近い文脈で問われます。扱うデータの並び、更新のしやすさ、探索の速さ、手順の停止条件を分けて比較してください。