跳到主要內容

發表文章

目前顯示的是 三月, 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]\]
觀察上式,為三個變數兩個拘束條件,故可以任意其中一個變數可被任意給定。另外我們發現$A$中的第一個column 與 第三個 co…

[最佳化] 淺談線性規劃(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問題:一般而言一旦線性規劃問題確立;使用者可以直接透過 MATLAB 指令 linprog 指令進行求解。此指令使用方法…

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

給定任意實數 $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)}\\
{\begin{array}{*{20}{c}}

[七藝] 古希臘追求成為真正自由人的七門必修科目

古希臘/羅馬人認為人雖有肉體上自由更要追求心靈上自由。其追求心靈自由的方法是要透過學習七門學問(七藝 Libral Arts)後方可成為真正的自由人:

其七門學科如下:

文法(Grammar)修辭(Rhetoric)辯證(Dialectic)算術(Arithmetic)幾何(Geometry)天文(Astronomy)音樂(Music)

現代所稱的博雅教育即為探討落實上列七門基本文理學科來落實教育通才 (非專才)。