記事一覧
数理最適化（双対問題と双対定理①）
今回は双対定理についてまとめていきます。
最適化問題でよく登場してきます。
相対問題とは主問題（元の解くべき問題）に対し、新たに定義した表裏の関係にある問題のことを双対問題と呼びます。
主問題が以下の場合を考えます。
目的関数
$$
最大化 c^{\top}x
$$
制約条件
$$
ax \leq b\\
x \geq 0
$$
これの、双対問題は、以下となります。
目的関数
数理最適化（単体法②）
今回は例題を解きながら単体法の解き方の流れを見ていきます。
例題を解いてみる単体法の概略を知るために、オペレーションズリサーチ学会の入門解説を使って、流れを見ていきたいと思います。
例題
目的関数を最小化する。
$$
u = −x_1 − x_2\\
$$
制約条件
$$
2x_1 + x_2 \leq 6\\
x_1 + 3x_2 \leq 8\\
x_1 \geq 0, x_
数理最適化（単体法①）
単体法（Simplex method）についてまとめていきたいと思います。
単体法は、線形計画問題を解くための方法の1つです。
長年にわたって使用されている実用的な方法です。
単体法が使われる理由・高速に解を見つけることができる
・アルゴリズムが理解しやすい
・さまざまな制約条件や目的関数に対応できる
線形計画問題は、目的関数と呼ばれる線形関数を最大化または最小化する問題です。
この問題のキー
数理最適化（線形計画問題④）
区分線形凸関数最小化問題の定式についてまとめていきます。
定式区分線形凸関数最小化問題の定式はこちらです。
$$
min f(x) = \displaystyle\max_{i=1,2…,m-1} \lbrace{\cfrac{f(a_{i+1}) - f(a_i)}{a_{i+1} - a_i}(x - a_i) + f(a_i)} \rbrace\\
a_1 \leq x \leq a
数理最適化（線形計画問題③）
今日は非線形計画問題を線形計画問題で近似して解くということについてまとめていきたいと思います。
非線形計画問題非線形計画問題は、非線形計画関数の最小化もしくは最大化を解く問題です。
非線形関数とは
非線形関数は、一次関数（直線）ではない関数のことです。
例えば、二次関数のような直線ではない関数です。
凸関数（とつかんすう）
二次関数のように上下どちらかに出っ張った関数です。
山形の関数を
数理最適化（線形計画問題②）
線形計画問題の定式化をいくつか見ていきたいと思います。
生産計画問題・○○製造会社は、複数の製品を生産している
製造会社の清算効率を最大化し、コストを最小化したいという問題です。
問題
・M：製品の数
・T：製造会社の生産可能な総時間
・R：利用可能な総資源量
・ci：製品 i の単位時間当たりのコスト
・di：製品 i の需要量
・pi：製品 i 1個当たりの販売価格
・ti：製品 i 1
数理最適化（線形計画問題①）
線形計画問題は、次の特徴を持つ最適化問題です。
・目的関数が線形
・変数が0以上
・全ての制約条件が線形の等式、不等式で表現できる
・目的関数を最大化、または最小化する問題
線形とは一次関数を示します。
一次関数とは、y = ax + b の形で表される関数です。
変数 x に対して、係数（定数）のみを掛けている関数です。
ナップサック問題が線形問題です。
品物Aと品物Bをナップサックに入れる
数理最適化（モデリング言語とソルバー）
組み合わせ問題を深堀していく前に、モデリング言語とソルバーというものについてまとめてみます。
（勉強していたらこの言葉が出てきたので、何だろうと思い調べました）
モデリング言語数理最適化問題を「人が書きやすく・わかりやすい」形式で表現するための言語です。
モデリング言語の種類
モデリング言語の種類もいくつかあります。
・AMPL
・PuLP
・PICOS
・Pyomo
・CVXOPT
・Ju
数理最適化（組み合わせ最適化）
今回は組み合わせ最適化についてまとめていきます。
私がこれから解決していきたい問題が組み合わせ問題なので、初めにこちらを調べていきたいと思います。
組み合わせ最適化とはあらためておさらいです。
組み合わせ最適化は、離散的な値を取る最適化問題のことを指します。
離散的な値とは、[0, 1, 3, ・・・] というようにとびとびの数値のことを言います。
有名な問題に、ナップサック問題というのがありま