実数 についての次の線形計画問題を考える。
スラック変数 を導入し、原点 を初期基底解として単体法で解け。入る変数は目的関数の係数（被約費用）が最大の非基底変数とする。最適解 と最適値 を、組 の形でこの順に答えよ。
単体法
辞書（またはシンプレックス表）を作り、被約費用の符号で入る変数を、最小比テストで出る変数を決めてピボットをくり返せる。最適性の判定までたどり、線形計画問題の最適値と最適解を求められる
前提
- 端点（基底解）の列挙による最適解 （大学数学 最適化・線形計画法）
この技能までの道筋（50 技能）
読み込み中…
右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
一覧で見る（前提が先）
- 三角形の角の大きさ （算数 平面図形）
- 対頂角と平行線の同位角・錯角 （中学数学 平面図形）
- 三角形の外角と角の組み合わせ （中学数学 平面図形）
- 小数の四則計算 （算数 計算と数のきまり）
- 分数のたし算・ひき算 （算数 計算と数のきまり）
- 分数のかけ算・わり算 （算数 計算と数のきまり）
- 小数と分数のまじった計算 （算数 計算と数のきまり）
- 逆算（□ を求める） （算数 計算と数のきまり）
- 正負の数の加法・減法 （中学数学 数と式）
- 四則の混じった計算の順序 （算数 計算と数のきまり）
- 正負の数の乗除・累乗と四則混合 （中学数学 数と式）
- 分配法則を使った計算のくふう （算数 計算と数のきまり）
- 文字式の計算（同類項・分配法則） （中学数学 数と式）
- 1 次方程式の解き方 （中学数学 方程式）
- 二等辺三角形の角 （中学数学 平面図形）
- 平行四辺形と特別な四角形の性質 （中学数学 平面図形）
- 三角形・四角形の面積 （算数 平面図形）
- 約数の見つけ方 （算数 整数の性質）
- 素因数分解と約数の個数 （算数 整数の性質）
- 平方根の意味と根号の簡単化 （中学数学 数と式）
- 三平方の定理 （中学数学 相似と三平方の定理）
- 乗法公式による展開 （中学数学 数と式）
- 折り返した図形の角と長さ （中学数学 平面図形）
- 三平方の定理と平面図形 （中学数学 相似と三平方の定理）
- 最大公約数と最小公倍数 （算数 整数の性質）
- 比の性質と簡単な比 （算数 割合と比）
- 相似な三角形と長さの比 （算数 平面図形）
- 三角形の相似条件と対応する辺の長さ （中学数学 相似と三平方の定理）
- 平行線と線分の比 （中学数学 相似と三平方の定理）
- 2点間の距離と内分点・外分点 （数学II 図形と方程式）
- 比例・反比例の式とグラフ （中学数学 関数）
- 関数 の式と変域 （中学数学 関数）
- 因数分解 （中学数学 数と式）
- 平方完成と 2 次関数のグラフ （数学I 2次関数）
- 円の方程式 （数学II 図形と方程式）
- 連立方程式の解き方（加減法・代入法） （中学数学 方程式）
- 1 次関数の式の求め方 （中学数学 関数）
- 直線の方程式 （数学II 図形と方程式）
- 不等式の表す領域 （数学II 図形と方程式）
- 点と直線の距離 （数学II 図形と方程式）
- 2 次不等式 （数学I 2次関数）
- 円と直線の位置関係と弦の長さ （数学II 図形と方程式）
- 2直線の平行・垂直 （数学II 図形と方程式）
- 円の接線 （数学II 図形と方程式）
- 領域における最大・最小 （数学II 図形と方程式）
- ベクトルの演算と成分 （数学C ベクトル）
- 行列の和・積と 2 次の逆行列 （大学数学 線形代数）
- 線形計画問題の定式化と標準形 （大学数学 最適化・線形計画法）
- 掃き出し法と連立 1 次方程式 （大学数学 線形代数）
- 端点（基底解）の列挙による最適解 （大学数学 最適化・線形計画法）
説明
単体法（シンプレックス法）は、線形計画問題の最適解を、実行可能領域の端点（基底解）を隣へ隣へとたどって求める方法です。端点をすべて列挙する方法では、変数や制約が増えると調べる端点の数が急に増えます。単体法では、目的関数の値が良くなる方向の隣の端点にだけ移り、それ以上良くならないことを確かめたところで止まります。そのため、大きな問題でも少ない手間で最適値と最適解が得られます。
なぜそうしてよいのか
最大化問題 （制約は 、、）を考えます。各制約にスラック変数 を入れて等式 にします。このように、一部の変数（基底変数）と を、残りの変数（非基底変数）の 1 次式で表したものを辞書と呼びます。非基底変数をすべて 0 にすると、基底変数の値は定数項そのものになります。これは制約のいくつかを等号にした連立 1 次方程式の解、つまり基底解です。定数項がすべて 以上なら、この基底解は実行可能で、実行可能領域の端点になります。
辞書の の式に現れる非基底変数の係数を被約費用と呼びます。ある非基底変数の被約費用が正なら、その変数を 0 から増やすと が増えます。ただし増やすにつれて、その変数の係数が負である行の基底変数が減っていきます。 を下回らない範囲でしか増やせないので、増やせる上限は各行の「定数項 ÷ 係数の絶対値」の最小値です（最小比テスト）。上限に達したとき 0 になった基底変数を非基底側に移し、増やした変数を基底側に移します。これがピボットです。辞書を作り直すと、隣の端点の辞書が得られます。
すべての被約費用が 以下になったとします。非基底変数はどれも 以上なので、どの実行可能解でも （ の式の定数項）が成り立ちます。いまの基底解はこの値をちょうど達成しているので、最適解です。一方、被約費用が正の変数について、その変数の係数が負の行が 1 つもないことがあります。このときはその変数をいくらでも増やせて となり、問題は非有界（最適解なし）です。
手順
スラック変数 を入れて、初期辞書 、 を作る（すべての であることを確認する）
の式で係数（被約費用）が正の非基底変数を 1 つ選び、入る変数とする（係数が最大のものを選ぶのが普通）。正の係数がなければ最適なので終了する
最小比テストを行う。入る変数の係数が負である行だけについて「定数項 ÷ 係数の絶対値」を計算し、最小になる行の基底変数を出る変数とする。該当する行がなければ非有界として終了する
ピボットを行う。出る変数の行を入る変数について解き、それを他のすべての行と の式に代入して、新しい辞書を作る
手順 2 に戻ってくり返す。終了したら非基底変数を 0 とおき、各行の定数項から最適解を、 の定数項から最適値を読み取る
例題
、、、 のもとで、 を最大化する。単体法を用いて、最大値と、そのときの を順に組 で求めよ。
例題の解答
手順 1：スラック変数 を入れて、初期辞書を作る。
定数項はすべて 以上なので、これは端点 を表している。
手順 2（1 回目）：被約費用は と で、どちらも正である。係数が最大の を入る変数にする。
手順 3： の係数が負の行は 3 本とも該当する。比は の行が 、 の行が 、 の行が で、最小は である。よって が出る変数になる。
手順 4： の行を解いて とし、他の式に代入する。
この辞書は端点 、 を表している。
手順 2（2 回目）： の被約費用が なので、 を入る変数にする。
手順 3： の係数が負の行は の行と の行である。比は の行が 、 の行が で、最小は である。よって が出る変数になる。
手順 4： の行を解いて とし、代入する。
手順 5： の式の被約費用は と で、どちらも 以下なので最適である。非基底変数を とおくと、、、 となる。（実際、 だから、どの実行可能解でも が成り立つ。）
答え:
よくある誤り
最小比テストで、入る変数の係数が や正の行まで比に含めてしまう誤り。そのような行の基底変数は入る変数を増やしても減らないので、上限を与えません。たとえば の行は比の計算から除きます。正しくは、係数が負の行だけで「定数項 ÷ 係数の絶対値」の最小値をとります。
比が最大の行や、定数項が最大の行の変数を出す変数に選んでしまう誤り。上の例の 1 回目で （比 ）を出すと、 となり で実行不可能になります。正しくは比が最小の行（、比 ）を選びます。
シンプレックス表（ のように 行を移項した形）で符号を取り違える誤り。表の 行の を見て「負だから最適」と判断してしまうことがあります。表では辞書と符号が逆になり、最大化なら 行に負の数が残っている間は改善でき、すべて 以上になったら最適です。
ピボットの後、 の式や他の行への代入を忘れる誤り。上の例の 1 回目の後、 のまま を残すと、正しい が得られず、被約費用を正しく判定できません。正しくは、入る変数を新しい基底変数の式で置き換え、すべての式を非基底変数だけで表します。
この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。
入口の問題
実数 についての次の線形計画問題を考える。
スラック変数を導入して初期辞書（またはシンプレックス表）を作り、単体法で解け。入る変数は目的関数の係数が最大の非基底変数とし、出る変数は最小比テストで決めること。最適解 と最適値 を、組 の形でこの順に答えよ。実数 についての次の線形計画問題を考える。
スラック変数 を加えて初期辞書を作り、単体法（入る変数には目的関数の行で係数が正のもののうち最大のものを選ぶ）で解け。最適解 と最適値 を、組 の形で答えよ。