跳到主要內容

發表文章

目前顯示的是 3月, 2011的文章

[最佳化] 淺談線性規劃(1)- Feasible solution and Basic solution

延續上一篇 [最佳化] 淺談線性規劃(0)- Standard form of Linear Programming ,這次要跟大家介紹 線性規劃(LP)問題的求解。由先前介紹我們知道,對任意含有線性不等式拘束的LP問題都可以將其轉換成標準型式的LP問題。亦即含有 等式拘束的LP問題。 \[\begin{array}{l} \min {c^T}x\\ s.t.\\ \left\{ \begin{array}{l} Ax = b,\\ x \ge 0 \end{array} \right. \end{array}\]其中 $A$ 為 $m \times n$ 矩陣且 $n>m$, $rank(A) = m$,$A$ 沒有全為零的column$;b \geq 0$, 在介紹之前要先介紹兩種解的概念 ============================ Definition: (Feasible solution and Basic solution) 一個向量 $x \in \mathbb{R}^n$ 稱作 可行解(Feasible solution) ,如果其滿足拘束條件,亦即 $x \geq 0$ 且 $Ax=b$ 一個向量 $x \in \mathbb{R}^n$ 稱作對 $Ax=b$ 的 基本解( Basic Solution) ,若 $x$中 nonzero component 對應到$A$矩陣的線性獨立 Columns。 ============================ 先給個例子看看這兩種解有甚麼不同 Example 考慮下列拘束條件 $Ax=b$: \[\left[ {\begin{array}{*{20}{c}} 1&2&{ - 2}\\ 1&3&{ - 2} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{x_1}}\\ {{x_2}}\\ {{x_3}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} 1\\ 1 \end{array}} \right]\] 觀察上式,為三個變數兩個拘束條件,故可以任意其中

[最佳化] 淺談線性規劃(0)- Standard form of Linear Programming

這次要介紹最佳化中一類 重要問題 線性規劃(Linear Programming, LP): 什麼是線性規劃? 簡單說就是 目標成本函數(Cost function)為線性,且約束條件為線性不等式;欲求解最佳解 (最大or最小化)。亦即: \[\begin{array}{*{20}{l}} {\min {c^T}u}\\ {s.t.}\\ {\left\{ {\begin{array}{*{20}{l}} {Au \le b,}\\ {u \ge 0} \end{array}} \right.} \end{array} \]上式稱為一般 或者 典型LP問題 (Canonical form)。這種典型的線性規劃(LP)問題可以改寫成 LP 標準式 (Standard form)  如下: ======================== 令 $x \in \mathbb{R}^n$, \[\begin{array}{l} \min {c^T}x\\ s.t.\\ \left\{ \begin{array}{l} Ax = b,\\ x \ge 0 \end{array} \right. \end{array}\]其中 $A$ 為 $m \times n$ 矩陣且 $n>m$, $rank(A) = m$,$A$ 沒有全為零的column$;b \geq 0$, ======================== Comments: 1. $x \in \mathbb{R}^n$,亦即我們有 $n$個變數,$A$為$m \times n$矩陣表示我們有$m$個拘束條件。$rank(A)=m$,暗示 $n>m$ (n 變數 多於 m 拘束條件) 確保nontrivality,因為如果$n =m$,則我們不需要最佳化問題因為此問題存在唯一解 $x = A^{-1}b$或者無解。 2. $rank(A)=m$ 確保 rows 是線性獨立(也就是各個拘束條件各自獨立)。 3. $c^T x = c_1 x_1 + c_2 x_2 + ... + c_n x_n$ 但注意到,並不是每一個LP問題都符合上面的標準形式,故我們需要將其改寫轉換。 4. 關於求解LP問題: 一般而言一旦線性規劃問題確立;使

[基礎數學] 三角函數極座標與卡式座標互換等式

給定任意實數 $a,b, \omega$ 則對任意 $t$ 而言, \[ a \cos (\omega t) + b \sin (\omega t) = A \cos (\omega t - \phi) \]其中 $A = \sqrt{a^2 + b^2}$ 且 $\phi = \tan^{-1}(b/a)$ Proof: 首先定義複數 $z := a - bi$ 則存在 $A= \sqrt{a^2 + b^2}$ 與 $\phi = \tan^{-1}(b/a)$ 使得 $z = A e^{-i \phi}$ 接著我們觀察 \[\begin{array}{*{20}{l}} \begin{array}{l} A{e^{i\left( {\omega t - \phi } \right)}} = {e^{i\left( {\omega t} \right)}} \cdot \left( {A{e^{ - i\left( \phi  \right)}}} \right)\\ \begin{array}{*{20}{c}} {}&{}&{}&{} \end{array} = \left( {\cos \left( {\omega t} \right) + i\sin \left( {\omega t} \right)} \right)z \end{array}\\ {\begin{array}{*{20}{c}} {}&{}&{}&{} \end{array} = \left( {\cos \left( {\omega t} \right) + i\sin \left( {\omega t} \right)} \right)\left( {a - bi} \right)}\\ {\begin{array}{*{20}{c}} {}&{}&{}&{} \end{array} = a\cos \left( {\omega t} \right) - bi\cos \left( {\omega t} \right) + ai\sin \left( {\omega t} \right) + b\sin \left( {\omega t} \right)}\\ {\be