線形計画法
PyomoというPythonライブラリを使って線形計画問題を解く方法をまとめた。 本記事では、Pyomoの導入方法と、問題の記述方法について示す。 目次 はじめに ライブラリのインストール 対象とする線形計画問題 Pyomoのソースコード ソースコードの解説 問題のオブジェクトの作成 変数の定義 目的関数の定義 制約条件の定義 ソルバの指定と最適化 最適化結果の評価 参考
Optimization Night で H. Paul Williams, Model Building in Mathematical Programming, 5th Edition, Wiley, 2013. の輪読会をしているので、そのメモです。 宿題（12.1 Food manufacture 1） はじめの1時間は宿題（12.1 Food manufacture 1）の答え合わせと議論になった。 僕の答案はColaboratoryで共有。 はじめ一部の条件の解釈を間違えていたけど、それ以外はだいたい正しそう（Colaboratoryは修正済）。 典型的な線形計画問題なので、英語の…
はじめに 甲南大学の知能情報学部の講義について，学べることや感想を書いていきます．あくまでも，僕が受けた授業についてのみ書いていることにご注意ください． また，講義の内容については，各講義のシラバスが最も正確であり，最も信憑性が高いということを明記します． なお，記事の内容は僕が講義を受けた時点の内容なので，いまあなたが見ている年度では大きく異なる場合があります．そういう意味で，必ずシラバスを確認してください． あと，4年の初めに書いているので，1年次の科目とか正直うろ覚です．それと基礎共通科目は書いてません．ごめんよ はじめに 1年次に受けたもの 体育 英語（読み） 英語（聞き） 英語（話す…
◀︎ 前へ｜次へ ▶︎️ 最適化問題に関する次の（ア）から（エ）の記述について，それぞれの正誤の組合せとして，最も適切なものはどれか。 線形計画問題とは，目的関数が実数の決定変数の線形式として表現できる数理計画問題であり，制約条件が線形式であるか否かは問わない。 定変数が2変数の線形計画問題の解法として，図解法を適用することができる。この方法は2つの決定変数からなる直交する座標軸上に，制約条件により示される（実行）可能領域，及び目的関数の等高線を描き，最適解を図解的に求める方法である。 制約条件付きの非線形計画問題のうち凸計画問題については，任意の局所的最適解が大域的最適解になるといった性質を…
◀︎ 前へ｜次へ ▶︎️ 計画・設計の問題では，合理的な案を選択するために，最適化の手法が用いられることがある。これについて述べた次の文章の に入る用語の組合せとして，最も適切なものはどれか。ただし，以下の文中で，「案」を記述するための変数を設計変数と呼ぶこととする。 最適化問題の中で，目的関数や制約条件がすべて設計変数の線形関数で表現されている問題を線形計画問題といい， ア などの解法が知られている。設計変数，目的関数，制約条件の設定は必ずしも固定的なものでなく，主問題に対して イ が定義できる場合，制約条件と設計変数の関係を逆にして与えることができる。 また，最適化に基づく意思決定問題で，…
こんにちわ、からすさんです。お題通りに生協のメニューをコスパ良く選んでみました。 じゃあまずどういうことかってことを以下にまとめてみました。 １食分の食品群（赤、緑、黄）を１食でちゃんと満たす １食に２品同じものが選ばれない 食品群の他にも脂質や塩分の条件をつけくわえれる 以上の３点を満たしかつ値段を最小にしてくれるコスパのいいメニューを選びましょう！ 問題設定 以下のような問題を最適化問題で表していきます。 １品１回まで選択可 食品群（赤、緑、黄）はそれぞれ（２点、１点、５点）以上とする。（これは男版） 任意の栄養も調整可 以上を踏まえて今回解いていく最適化問題は次の通りです。 これは、線形…
線形計画問題が楕円体法などによって多項式時間で解けることは有名です．しかし，例えばある問題のLP表現において，制約式の個数がその問題の入力長に関して指数個あった場合，その問題は普通の楕円体法では多項式時間で解くことはできません．では，そのようなLPが（元の問題の入力長に関する）多項式時間で解ける場合はあるのでしょうか？ 実は，分離問題と呼ばれる問題が多項式時間で解けるなら，LPは制約式の個数にはよらない多項式時間で解くことができます．多面体$P$（多面体とは，$\mathbb{R}^n$におけるいくつかの線形不等式によってつくられる領域のことです．例えば，LPの実行可能領域は多面体です）に対す…
本記事では、線形計画問題に対する主双対内点法 (primal-dual interior point method) についてまとめた。目次 はじめに 内点法 主双対内点法 主双対内点法のアルゴリズム 最適性条件 解の更新 パス追跡法 参考
本記事では、最適化でよく用いられる双対問題についてまとめた。 また、サポートベクターマシンにおける双対問題についても少し触れている。目次 線形計画問題の標準形 双対問題 弱双対定理 双対定理 サポートベクターマシンと双対定理 参考
