設計・品質管理のテーマ一覧へ

基礎科目・設計・品質管理

線形計画と最適化

よく出る高校

7問H24・H25・H28・H30・R1・R1再・R6

原料や時間の上限のもとで利益を最大にする計算と，最適化の用語（双対問題・パレート解など）が出ます。

よく出る形

  • 原料・時間などの使用上限のもとで，2つの製品の生産量を決めて利益を最大にする（計算）
  • 線形計画・凸計画・整数計画・多目的最適化の用語の穴埋めや正誤
  • 毎回，表の数字が変わる。用語の問題は定番の記述の1か所を反対にした文がまざる

覚えること

  • 最適化は「決定変数（自分で決める数）」「目的関数（最大・最小にしたい量）」「制約条件（守る条件）」でできている
  • 線形計画問題：目的関数も制約条件もすべて一次式。代表的な解き方はシンプレックス法。2変数なら図で解ける（図解法）
  • 線形計画の最適解は，制約で囲まれた領域（実行可能領域）の角（頂点）のどれかにある。最大でも最小でも同じ
  • 目的関数の等高線が最適側の辺と平行なら，その辺の上のどの点も最適解になり，1つに定まらない
  • 双対問題：制約条件と変数の役割を入れかえた，もう1つの問題。主問題に最適解があれば双対問題にもあり，最適値は等しい（双対定理）
  • 凸計画問題：局所的最適解（近くの中でいちばんよい点）がそのまま大域的最適解（全体でいちばんよい点）になる
  • 凸でない問題では，勾配法で求めた解が局所的最適解にとどまり，大域的最適解とは限らない
  • 整数計画問題：変数が整数だけ。大きな問題は遺伝的アルゴリズムなどで近似解を求める
  • トレードオフ：一方をよくすると他方が悪くなる関係。その中で「全部を同時にはよくできない解」がパレート解
  • パレート解は1つではなく集まり。その中からどれを選ぶかは，意思決定する人が決める
  • 栄養素の必要量のように下限（〜以上）がある問題は，制約が ≧ になり，費用を最小にする

解き方

  • 製品の量を x，y として，制約を一次式（上限は ≦，下限は ≧）で，利益や費用を Z ＝ ax ＋ by で書く
  • 制約の線どうしの交点（頂点）と，x ＝ 0・y ＝ 0 の端の点を出す
  • 各頂点がすべての制約を守っているか確かめ，Z を計算して，最大（または最小）のものを選ぶ
  • 例：x＋2y≦12，3x＋y≦15，x＋y≦7，Z ＝ 300x ＋ 200y。頂点 (5,0)→1,500，(4,3)→1,800，(2,5)→1,600，(0,6)→1,200。最大は (4,3) の1,800

ひっかけ

  • 線形計画を，目的関数だけ一次式ならよい，としない。制約条件も一次式
  • 交点を出したら，ほかの制約を破っていないか必ず確かめる。破る点は選べない
  • 「常に1つに定まる」「同時に最もよくなる」のような言い切りは疑う
  • シンプレックス法とコンプレックス法，双対問題と逆問題，トレードオフとトレードオンの言葉のすりかえに注意
このテーマの想定問題を解く

想定問題：1・2・3

このテーマの過去問（このサイトに解説がある 3問）

X で共有LINE で送る

平成に出た同じテーマ（4問）

このサイトにはまだ解説がありません。年度と題だけです。