==================================================================
●【非線形計画問題】●
==================================================================
▼1.1【非線形計画問題】【1変数関数の最小化】
▼1.2【非線形計画問題】【1変数関数の最小化問題に対するニュートン法】
▼1.3【非線形計画問題】【多変数関数の最小化】
▼1.4【非線形計画問題】【最急降下法】
▼1.5【非線形計画問題】【多変数関数の最小化問題に対するニュートン法】
▼1.6【非線形計画問題】【等式制約のみの非線形計画問題】
▼1.7【非線形計画問題】【不等式制約のみの非線形計画問題】
▼1.8【非線形計画問題】【一般の非線形計画問題】
2010年11月18日木曜日
【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次計画問題を解く主双対内点法】
●【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【基底解】【線形方程式系の基底解】
等式の数だけ基底変数を選び、そのほかは非基底変数（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.2【双対問題】【一般形の線形計画問題の双対問題の例】
例がある
▼2.1【双対定理】【弱双対定理と双対定理】
弱双対定理：両問題が実行可能ならば、主問題の目的関数値は、常に、双対問題の目的関数値より大きい。
双対ギャップ：両問題が実行可能な場合のみ、
（主問題の目的関数） - （双対問題の目的関数） = 双対ギャップ
という
主問題と双対問題に対して成り立つこと：
①弱双対定理
②両問題が実行可能ならば、それぞれ最適解を持つ
③主問題が実行可能で非有界ならば、双対問題は実行不能である
④それぞれの実行可能解で、主問題と双対問題の目的関数値が一致した場合、それが最適解。
双対定理：主問題が最適解を持つならば、双対問題も最適解を持ち、その最適値が等しい。
相補性条件：両問題の実行可能解において、主問題の解と双対問題のスラック変数の積（双対ギャップ）が「0」だから、必ずどちらかが「0」
▼2.2【双対定理】【主問題と双対問題の例】
例がある
▼2.3【双対定理】【分離定理】
やってない
2010年11月16日火曜日
【線形計画法】
==================================================================
●【線形計画問題】●
==================================================================
▼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つのパターンしかない：
①実行不能な場合
②実行可能ではあるが、非有界であるため最適解が存在しない場合
③実行可能であり、最適解が存在する場合
●【線形計画問題】●
==================================================================
▼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つのパターンしかない：
①実行不能な場合
②実行可能ではあるが、非有界であるため最適解が存在しない場合
③実行可能であり、最適解が存在する場合
2010年11月15日月曜日
【写像】【写像と対応】
関数：任意の実数x∈R に対して、ある計算結果を1つの実数として対応させる規則
e.g.
写像：集合Aの任意の元aに対して、関数fによって、集合Bの元bが定められる時の規則
f:A→B
像：元bのこと
e.g.
写像：集合Aの任意の元aに対して、関数fによって、集合Bの元bが定められる時の規則
f:A→B
像：元bのこと
2010年11月10日水曜日
【集合】【集合と部分集合】
集合：ある集まり
有限集合：元が有限の集合
無限集合：元が無限の集合
N：自然数
Z：整数
Q：有理数
R：実数
空集合：元がない集合
部分集合：A -> B のときのA
推移率：A -> B and B -> C <=> A -> C
真部分集合：AがすっぽりBに含まれるとき
開区間：境界があいまい (a,b)
閉区間：境界が明確 [a,b]
有限集合：元が有限の集合
無限集合：元が無限の集合
N：自然数
Z：整数
Q：有理数
R：実数
空集合：元がない集合
部分集合：A -> B のときのA
推移率：A -> B and B -> C <=> A -> C
真部分集合：AがすっぽりBに含まれるとき
開区間：境界があいまい (a,b)
閉区間：境界が明確 [a,b]
【命題と論理】【推論と証明】
推論：命題から命題を導き出すこと
証明：推論を繰り返す過程のこと
定理：新しく得られた命題
公理：定理を導く前提となる普遍的命題
十分条件：p -> q
必要条件：p <- q
必要十分条件：p <-> q
背理法
数学的帰納法
証明：推論を繰り返す過程のこと
定理：新しく得られた命題
公理：定理を導く前提となる普遍的命題
十分条件：p -> q
必要条件：p <- q
必要十分条件：p <-> q
背理法
数学的帰納法
【命題と論理】【命題関数と限定記号】
命題関数：集合Aのすべてのxに対して必ずp(x)の真偽が確かめられる命題
全称記号：∀、すべての
限定記号：∃、存在する
限定する変数の順序を入れ替えると、命題の意味が同じになるとは限らない
全称記号：∀、すべての
限定記号：∃、存在する
限定する変数の順序を入れ替えると、命題の意味が同じになるとは限らない
【命題と論理】【命題と論理記号】
命題：日本語が正しいかどうか決められるもの（regex 日本語 -> 文章）
真偽値、真理値：T or F
論理和：範囲を足したもの（ig. 1 + 1 > 0）
論理積：範囲を掛けたもの(ig 1 * 0 = 0)
A -> B
逆：B -> A
裏：not A -> not B
対偶：not B -> not B
双条件文：A <-> B
複合命題
真偽値、真理値：T or F
論理和：範囲を足したもの（ig. 1 + 1 > 0）
論理積：範囲を掛けたもの(ig 1 * 0 = 0)
A -> B
逆：B -> A
裏：not A -> not B
対偶：not B -> not B
双条件文：A <-> B
複合命題
登録:
投稿 (Atom)