【シンプレックス法】

==================================================================
●【シンプレックス法】（単体法）●
==================================================================
線形計画問題の最適解が存在するならば、最適基底解が存在することを用いて解く

▼1.1【基底解】【基底解の例】
基底解：基底変数（解、等式の数だけ選べる）と、非基底変数（選ばれなかった変数）からなるベクトル

基底変数の係数は一次独立になるようにしなければならない


▼1.2【基底解】【線形方程式系の基底解】
等式の数だけ基底変数を選び、そのほかは非基底変数（0）にする
結果、一次独立になった場合は解なし


▼1.3【基底解】【標準形の線形計画問題の基底解】
実行可能基底解：非負条件を満たす基底解

①実行可能解が存在するならば、実行可能基底解が存在する。
②最適解が存在するならば、最適基底解が存在する。


▼1.4【基底解】【双対問題の基底解】

▼2.1【線形計画問題の辞書】【辞書の例】

▼2.2【線形計画問題の辞書】【辞書】

▼2.3【線形計画問題の辞書】【辞書の更新】

▼3.1【主シンプレックス法】【主シンプレックス法による例】
目的関数における非基底変数（x3,x4）の係数がすべて0以上ならば、この実行可能な基底解は最適解である
これ以外の時は、係数が負となる変数を1つ選ぶ
x1を選んだとする
等式を満たすように非基底変数の中で、x1のみ増加させると、基底変数の値は
～～～
となる、実行可能であるためのx1を定め、その時点でのx3を非基底変数とする代わりに
x1を基底変数とすることにより、実行可能な基底解を求める。

はじめの辞書さえ得られれば、同一の方法で最適解を求めることができる


▼3.2【主シンプレックス法】【初期実行可能基底解が得られる場合】

▼3.3【主シンプレックス法】【2段階シンプレックス法】
●1段階
①人工変数の和を目的関数とする人工問題を作る
②人工変数を基底変数とする辞書を求める
③目的関数の係数が「負」の非基底変数を一つ選び、選んだ非基底変数を0から増加させたとき、はじめて0 になる基底変数を定め、それを基底から交換する
④目的関数における非基底変数の係数がすべて0 以上になるまで繰り返す
⑤基底に人工変数が含まれていないので、この辞書の等式制約から人工変数をすべて消去する
●2段階
①これを元の問題の目的関数に代入する
③目的関数の係数が「負」の非基底変数を一つ選び、選んだ非基底変数を0から増加させたとき、はじめて0 になる基底変数を定め、それを基底から交換する
④目的関数における非基底変数の係数がすべて0 以上になるまで繰り返す

このプロセスによって最適解を求めることができる