0 序言
最近打算在CSDN上將自己學習本書的程序記錄下來，整個系列對于我來說更像是讀書筆記，同時也放在網上供大家閱讀，由于本人非數學科班出身，僅僅是對運籌優化方面有興趣而學習，因此對于某些定義的理解、把握以至于推導不甚精通，其中若有錯誤，還希望大家不吝指教，
本書第一章Introduction中內容我已略去，其主要原因是該章節內容比較基礎且多為介紹性的內容，基本上沒有理解性的內容，因此主要從第二章線性規劃圖解法開始寫，書中某些難度較高以至于不適合初學者學習的章節我也都會略過，
全書共12章，2至5章為線性規劃主要內容，分別為：
- 線性規劃圖解法
- 單純形法
- 對偶理論
- 靈敏度分析
在國內運籌學教材上普遍存在的內容，如：運輸問題、線性目標規劃、圖論、排隊論、存盤論等等，非本系列的重點，本系列主要重點是圍繞著 Introduction to Linear Optimization 展開討論的，因此如排隊論，存盤論等內容，本系列不會出現，而對于圖論、整數規劃等內容，也非本系列的重點，我本人也不會在此類章節上過多的費口舌，
國內部分高校本科所開設的運籌學這門課程，通常為一個學期結課，因此對于很多本科學習過運籌學的同學（非數學專業），通常都存在著困惑，學習完之后感覺這門學科好像很厲害，但是卻不明白其中的道理為何，本人也是如此，因此本系列最好的受眾就是對于運籌學有一些基礎的了解，但又不明其理、或是初學運籌學的同志們當作筆記閱讀，
在這里我再次宣告：本人非數學科班出身，僅僅是浩如煙海般的群眾的一部分，沒有接受過什么教育，本人對于運籌學的認知是非常淺薄的，僅僅因為興趣而為之，因此，若你是業界學術大佬，對于文章中的錯誤還望不吝指教，我再此再三感激；若你是與我一樣的初學者，我希望我們更是以一種同學的身份共同進步，
（宣告：本書絕大多數專有名詞我都會用中英文結合的方式來表示出，如：極點(extreme points)，但是當遇到過于簡單的專有名詞的時候，如：線性規劃圖解法(The geometry of linear programming)，我僅僅會表達中文意思，當遇到我自己認為沒有合適的中文名詞對應的專有名詞時，我會采用原書的英文表達方式，并附加我對其的一些理解）
1. 超平面，半空間和多面體
多面體的表示
我們先來看原書中的幾個定義：
Definition 2.1 A polyhedron is a set that can be described in the form {x ∈ Rn | Ax ≥b}, where A is an m*n matrix and b is a vector in Rm.
注：Rn與Rm分別代表n維和m維的歐式空間
從代數的角度理解多面體（polyhedron），即多面體是一個n維列向量 x 的集合，該集合中的所有元素 x 滿足線性方程組 Ax ≥b
若從幾何的角度理解多面體，不妨先從低維度的來看
我們以二維為例
假設在xOy平面內，存在如下集合
即該集合所表示的圖形如下圖綠色區域所示
當 x 的維數上升至3維時，一個多面體的形狀就變為了3維歐式空間中的“體”，當維數超過3維達到更高的n維時，便沒有直觀上的圖來描述了，因為我們所生活的世界就是3維歐式空間，
多面體的分類
不同的多面體根據其集合所包含的方程組不同，主要可以分為有界的（bounded）與無界的（unbounded），在上一個例子中展示出的多面體即為有界的，顯而易見，我們很容易給出一個無界的多面體的例子，如：
即為xOy坐標系的第一象限（圖略）
超平面與半空間的表示
Definition 2.2 Let a be a nonzero vector in Rn and let b be a saclar.
(a) The set {x ∈ Rn | a’x = b} is called a hyperplane.
(b) The set {x ∈ Rn | a’x ≥ b} is called a halfspace.
注：a’ 代表列向量 a 的轉置
超平面在2維情況下為一條直線，在3維情況下為一個平面，以此類推，
而半空間即為空間的一半，我們知道，在任意維數(n ≥ 1)情況下，其所構成的空間皆是無限的，如：一根直線，一個平面，一個體…
因此我們在平面上任意確定的一點，在平面上任意確定的一條線，在體內任意確定的一個平面，都可以將對應的空間劃分為兩半，因此我們稱其為半空間，而兩個半空間之間的界限，我們稱其為超平面，
2.凸集
Definition 2.3 A set S ? Rn is convex if for any x,y ∈ S, and any λ∈[0,1], we have λx + (1 - λ)y ∈ S.
凸集（convex sets）的定義是非常容易從幾何的角度去理解的，如上例所示的在二維歐式空間內的多面體：
從直觀上理解即：該多面體所構成的集合沒有“凹”的地方，即：集合內任意兩點（元素）的連線上的所有點（元素）仍在集合內，
一些定理
通過以上的一些定義，我們可以得到下述定理：
Theorem 2.1
(1) The intersection of convex sets is convex.
(2) Every polyhedron is convex set.
(3) A convex combination of a finite number of elements of a convex set *
證明略
小結
本節主要介紹了有關于多面體（polyhedron）與凸集（convex set）及其相關的知識，這一部分的內容是 LP 的基礎理論部分，或許在初學時不明白為何要出現這么多的“奇怪的”定理及定義，這說明你對于LP的理解仍不夠深入，簡單來說，美國前運籌學會主席S.Bonder認為，運籌學應在三個領域發展：
- 運籌數學
- 運籌學應用
- 運籌科學
而運籌數學時運籌學理論的支柱部分，有著嚴密的理論證明，固然給運籌學的高樓打下了堅實的地基，這在某一方面來說是好事，但是這一點也使得很多專家過于深入于運籌數學深處，而忘記運籌學的初衷——解決實際問題，忽略了多學科的橫向交叉聯系和解決實際問題的客觀需求，
而本節及后續幾節所敘述的內容，主要屬于運籌數學方向的內容，目的是為了保證運籌學的數學邏輯嚴密性，初學者對于這些定理不解其意也無妨大局，當學習到后面的內容時，再回過頭來看自然會恍然大悟，
我認為這些晦澀的基本理論的學習對于初學者不甚友好，因此我建議對于運籌理論認識尚淺的同學一定要多進行數形結合，不單單是從代數的角度理解，更是從一種幾何的角度去理解；而且初學時，切勿鉆牛角尖；這樣對于定理的學習大有裨益，
好比本節中所學的多面體與凸集，通過數形結合，可以很直觀的理解其所代表的含義，
參考文獻
[1] Dimitris Bertsimas,John N. Tsitsiklis . Introduction to Linear Optimization[M]. 1997: 42-46
[2] 運籌學教材撰寫組. 運籌學[M]. 清華大學出版社, 2012年第四版: 3-12
著作權歸原作者所有，未經原作者允許不得將本文內容用于任何商業或盈利目的，否則將視為侵權，轉載或者參考本文內容請注明來源及原作者，對于不遵守此宣告或者其他違法使用本文內容者，本人依法保留追究權等，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/263818.html
標籤：其他