20251125_線形最適化問題LP： 単体法
A:x,B:y
x+3y<=9
x+y<=4
2x+y<=6
x=(1,1,2),y=(3,1,1)
max(2x+3y)
導入：生産計画問題
目的関数：線形関数
制約条件：線形等式/線形不等式
制約条件を満たすxを実行可能解と呼ぶ（LPに限らず）
実行可能解の集合を実行可能集合と呼ぶ
実行可能解を持たない問題：実行不可能な問題
最適解：実行可能解のうち、目的関数が最大/最小のもの
最適解により得られる目的関数値を最適値と呼ぶ
線形計画問題の一般化：不等式標準形
不等式標準形において、最適解がある
⇒ 最適解は実行可能集合の頂点
線形計画問題の一般化：等式標準形
(0にする操作を他の名前をつける)
何が起こったの
20251202_組合せ最適化
整数線形計画
入れるか入れないかの問題
貪欲法
ナップサック問題の下界と上界
