INDEX of INDEX

■Operations Research
1. 線形計画問題
2. 双対問題と双対定理
3. シンプレックス法
4. 2次計画問題
5. 非線形計画問題

■Liner Algebra
1. 行列
2. 連立1次方程式
3. 行列式
4. n次元ベクトル空間
5. 線形空間
6. 線形写像
7. 行列の対角化
8. 2次形式

■Differential and Integral Calculus


■Mathematics of Engineering Ⅰ
1. 命題と論理
2. 集合
3. 写像
4. 集合族と選択公理
5. 同値関係と順序関係
6. 濃度と可算集合
7. ユークリッド空間の位相
8. 距離空間と位相関係
9. 点列と連続関数の性質
10. 代数の基礎
11. 凸関数の基礎
12. 多変数解析
13. 積分

【非線形計画問題】

==================================================================
●【非線形計画問題】●
==================================================================
▼1.1【非線形計画問題】【1変数関数の最小化】
▼1.2【非線形計画問題】【1変数関数の最小化問題に対するニュートン法】

▼1.3【非線形計画問題】【多変数関数の最小化】

▼1.4【非線形計画問題】【最急降下法】

▼1.5【非線形計画問題】【多変数関数の最小化問題に対するニュートン法】

▼1.6【非線形計画問題】【等式制約のみの非線形計画問題】

▼1.7【非線形計画問題】【不等式制約のみの非線形計画問題】

▼1.8【非線形計画問題】【一般の非線形計画問題】

【2次計画問題】

==================================================================
●【2次計画問題】●
==================================================================
2次の目的関数を最小化する問題のこと。
凸関数の場合だけ解くことができる。

▼1.1【2次計画問題】【2次計画問題の例】
(ポートフォリオ選択問題)が含まれる

▼1.2【2次計画問題】【制約のない凸2次計画問題】

▼1.3【2次計画問題】【線形等式制約のみを持つ凸2次計画問題】

▼1.4【2次計画問題】【凸2次計画問題の最適条件】

▼1.5【2次計画問題】【凸2次計画問題の双対問題と双対定理】

▼1.6【2次計画問題】【凸2次計画問題を解く主双対内点法】

【シンプレックス法】

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

▼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 以上になるまで繰り返す

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

【双対問題と双対定理】

==================================================================
●【双対問題と双対定理】●
==================================================================
▼1.1【双対問題】【双対問題の定義】
線形計画問題には、それと対をなす双対問題が存在し、元の問題を主問題と呼ぶ。

 

▼1.2【双対問題】【一般形の線形計画問題の双対問題の例】
例がある

▼2.1【双対定理】【弱双対定理と双対定理】
弱双対定理：両問題が実行可能ならば、主問題の目的関数値は、常に、双対問題の目的関数値より大きい。

双対ギャップ：両問題が実行可能な場合のみ、
（主問題の目的関数） - （双対問題の目的関数） = 双対ギャップ
という

主問題と双対問題に対して成り立つこと：
①弱双対定理
②両問題が実行可能ならば、それぞれ最適解を持つ
③主問題が実行可能で非有界ならば、双対問題は実行不能である
④それぞれの実行可能解で、主問題と双対問題の目的関数値が一致した場合、それが最適解。

双対定理：主問題が最適解を持つならば、双対問題も最適解を持ち、その最適値が等しい。

相補性条件：両問題の実行可能解において、主問題の解と双対問題のスラック変数の積（双対ギャップ）が「0」だから、必ずどちらかが「0」


▼2.2【双対定理】【主問題と双対問題の例】
例がある


▼2.3【双対定理】【分離定理】
やってない

【線形計画法】

==================================================================
●【線形計画問題】●
==================================================================
▼1.1【線形計画問題の例】【生産計画問題】
1日あたりの製品1と製品2の生産量をx1,x2とおいて、生産限界能力を制約条件にしたときに、利益（目的関数）を最大化する問題。


▼1.2【線形計画問題の例】【要素による表現とベクトルと行列を使った表現の例】

と、ベクトルと行列で一般形の線形計画問題を表すことができる。


▼2.1【線形計画問題の形】【標準形の線形計画問題】
目的関数：最適化する関数
制約条件：守るべき等式あるいは不等式
なお、等号なしの不等式制約を含む場合には、線形計画問題とは呼ばない。
線形計画問題：変数が1次元の場合の計画問題

実行可能解：制約条件を全て満たすベクトルx

最適解：実行可能解の中で目的関数を最適にするもの

最適値：最適解における目的関数の値

実行可能領域：実行可能解の集合で作られる領域


▼2.2【線形計画問題の形】【一般形の線形計画問題】
一般形の線形計画問題：
①最小化問題で
②制約条件が等式または不等式（このとき左辺>=右辺で無ければならない）で
③0以上の変数と、制約の付かない変数を持つ問題のこと

▼3.1【線形計画問題の同値変換】【変換の例】
例が記載されている

▼3.2【線形計画問題の同値変換】【同値変換】
同値変換ルール集
①目的関数に正の実数を×、もしくは＋する。
②maxの目的関数に「-1」を×してminにする。反対もOK。
③等式制約の両辺に0以外の実数を×、もしくは＋する。
④不等式制約の両辺に実数を×、もしくは＋する。
⑤不等式制約の両辺に「-1」を×して、不等号の向きを逆にする。
⑥不等式制約にスラック変数を導入し、等式制約に変換する。
⑦等式制約を2つの不等式制約に分割する。
⑧自由変数変数xをu-vに置き換える。
⑨

⑩等式制約から一つの変数を他の変数で表し、それを全ての式に代入することで一つの変数を消去する。


▼4【実行可能性と最適解の存在】
線形計画問題には3つのパターンしかない：
①実行不能な場合
②実行可能ではあるが、非有界であるため最適解が存在しない場合
③実行可能であり、最適解が存在する場合

【写像】【写像と対応】

関数：任意の実数x∈R に対して、ある計算結果を1つの実数として対応させる規則
e.g.

写像：集合Aの任意の元aに対して、関数fによって、集合Bの元bが定められる時の規則
f:A→B

像：元bのこと