基本情報 2022 サンプル問題 問57：テクノロジ系に関する問題

答えは c「7,000円」 です。

X1個＝利益100円、Y1個＝利益150円。Yの方が儲かるけど、原料には限りがある（A原料100、B原料80）。

色々な組み合わせを試すと、X=40個・Y=20個のとき:

• A原料：2×40 + 1×20 = 100（ぴったり）
• B原料：1×40 + 2×20 = 80（ぴったり）
• 利益：100×40 + 150×20 = 4,000 + 3,000 = 7,000円

👉 覚え方：原料の上限ぴったりで全部使い切るとき、たいてい最大利益。

ほかの数字（5,000・6,000・8,000）は組み合わせで原料が足りなくなったり余ったりして、最大じゃない。

なぜこれが正解か

正解は c の 7,000円。これは典型的な線形計画法（LP：Linear Programming）の問題。

定式化

• 変数：X製品の生産数 x、Y製品の生産数 y
• 目的関数（最大化）：Z = 100x + 150y
• 制約条件：

- 原料A：2x + y ≤ 100

- 原料B：x + 2y ≤ 80

- x ≥ 0, y ≥ 0

解法

2制約の交点を求める：2x+y=100 と x+2y=80 を連立。

上式×2：4x+2y=200、下式：x+2y=80 → 引き算で 3x=120 → x=40, y=20

利益＝100×40 + 150×20 = 4,000 + 3,000 = 7,000円

他の頂点も確認

• (x=0, y=40)：利益=6,000円（A原料：40≤100 OK、B原料：80=80 OK）
• (x=50, y=0)：利益=5,000円（A原料：100=100 OK、B原料：50≤80 OK）
• (x=40, y=20)：利益=7,000円 ← 最大

覚え方・ひっかけ注意

LP問題は実行可能領域の頂点のいずれかで最適解になる（線形計画法の基本定理）。3〜4頂点の利益を計算して最大を選べばOK。「単価が高い方を優先」は通用しない（原料制約があるため）。

理論的背景

本問は線形計画問題（LP：Linear Programming）の標準形。

• 目的関数：max Z = 100x + 150y
• 制約：2x+y≤100, x+2y≤80, x,y≥0

線形計画法の基本定理：実行可能領域が有界な凸多角形である場合、目的関数の最適解はその多角形のいずれかの頂点（基底解）で達成される。よって全頂点で目的関数値を評価し最大を選べばよい。

解法アルゴリズム

1. 図式解法：制約直線を引き、実行可能領域を図示。等利益線（100x+150y=const）を平行移動させ、領域内の最遠点を求める。

2. シンプレックス法（Dantzig, 1947）：基底解を頂点間で移動しながら目的関数を改善。本問のような2変数なら頂点列挙で十分。

3. 内点法（Karmarkar法, 1984）：実行可能領域の内部を通って最適解に到達。大規模問題では多項式時間で解ける。

双対問題との関係

本問の双対問題は：

• min W = 100u + 80v
• 制約：2u + v ≥ 100、u + 2v ≥ 150、u,v ≥ 0

双対変数 u, v はそれぞれ原料A, Bのシャドウプライス（限界価値）を表す。最適解では強双対性により主問題の最適値と双対問題の最適値が一致（7,000円）。実務では「原料Aを1単位増やしたら利益はいくら増えるか」という感度分析に直結する。

関連分野

• オペレーションズ・リサーチ（OR）：生産計画、輸送問題、配車問題、ポートフォリオ最適化など実務応用。
• 整数計画法（IP）：変数が整数のみの場合。組合せ最適化問題で NP困難。
• 混合整数計画法（MIP）：実数・整数変数混在。
• 非線形計画法（NLP）：目的関数や制約が非線形。
• 動的計画法（DP）：多段階最適化。

試験での位置づけ

テクノロジ系（数理・OR）の頻出論点。基本情報技術者試験ではシンプレックス法のタブロー操作、双対定理、感度分析、輸送問題（北西隅法・最小費用法・ステッピングストーン法）まで出題される。

実務での扱い

生産計画ではERP（SAP・Oracle EBS）に組み込まれたAPS（Advanced Planning and Scheduling）モジュール、商用ソルバー（CPLEX・Gurobi・LINDO）、オープンソース（GLPK・PuLP・Pyomo）で大規模問題を解く。線形性が崩れる現実問題には MILP（混合整数線形計画）・メタヒューリスティクス（遺伝的アルゴリズム・焼きなまし法・タブーサーチ）も併用される。