【运筹学】CH2 线性规划与单纯形法1——线性规划问题及其数学模型
目錄
運籌學緒論
前言
一、線性規劃問題及其數學模型
1.問題的提出
（1）【例1】
（2）【例2】?
（3）線性規劃的數學模型
（4）線性規劃問題模型的假設
2.圖解法（兩個決策變量）
3.線性規劃問題的標準形式
（1）標準形式
（2）如何轉化為標準型
4.線性規劃問題解的概念
（1）可行解
（2）基
（3）基可行解
（4）可行基
?二、線性規劃問題的幾何意義
1.基本概念
（1）凸集
（2）凸組合
（3）頂點
2.幾個定理
（1）【定理1】
（2）【引理1】
（3）【定理2】
（4）【引理2】
（5）【定理3】
3.線性規劃的解題思路
運籌學緒論
? ? ? ? 夫運籌帷幄之中，決勝千里之外。——史記《張良傳》
????????運籌學定義：
- 大英百科全書：運籌學是一門應用于管理有組織系統的科學，運籌學為掌管這類系統的人提供決策目標和數量分析的工具。
- 中國大百科全書：運籌學用數學方法研究經濟、民政和國防等部門在內外環境的約束條件下合理分配人力、物力、財力等資源，使實際系統有效運行的技術科學，它可以用來預測發展趨勢，指定行動規劃或優選可行方案。
- 辭海：運籌學主要研究經濟活動與軍事活動中能用數量來表達有關運用、籌劃與管理方面的問題，它根據問題的要求，通過數學的分析與計算，做出綜合性的合理安排，以達到較經濟、較有效地使用人力物力。
- 中國企業管理百科全書：運籌學應用分析、試驗、量化地方法，對經濟管理系統中人、財、物等有限資源進行統籌安排，為決策者提供有依據的最優方案，以實現最有效的管理。
????????學科主要分支
- 規劃理論：線性規劃、非線性規劃、運輸問題、整數規劃、動態規劃、目標規劃
- 圖論與網絡理論
- 排隊論
- 存儲論
- 決策論
- 對策論
- ……
????????運籌學模型
- 特點：模型方法的應用、多學科的綜合、系統的整體觀念
- 優點：符號語言、便于交流；事前分析、減少失誤；抽象反應實際、突出共性
前言
? ? ? ? 線性規劃是運籌學的一個重要分支。自1947年丹捷格提出了一般線性規劃問題求解的方法——單純形法之后，線性規劃在理論上趨向成熟，在實用中日益廣泛與深入。特別在電子計算機能處理成千上萬個約束條件和決策變量的線性規劃問題之后，線性規劃的適用領域更為廣泛了。從解決技術問題的最優化設計到工業、農業、商業、交通運輸業、軍事、經濟計劃和管理決策等領域線性規劃都可以發揮作用，它已成了現代科學管理的重要手段之一。查恩斯與庫伯繼丹捷格之后，于1961年提出了目標規劃，艾吉利提出了用優先因子來處理多目標問題，使目標規劃得到發展。30多年前，斯·姆·李與杰斯開萊尼應用計算機處理目標規劃問題，使目標規劃在實際應用方面比線性規劃更廣泛，更為管理者所重視。
? ? ? ? 線性規劃是一種合理利用資源、合理調配資源的應用數學方法。規劃就是利用某種數學方法使得有效資源的運用最優化；線性就是用來描述變量之間關系的函數是線性函數。
? ? ? ? 線性規劃部分與目標規劃包含內容有：線性規劃與單純形法、對偶理論與靈敏度分析、運輸問題、線性目標規劃四部分。
一、線性規劃問題及其數學模型
1.問題的提出
（1）【例1】
美佳公司計劃制造一、二兩種家電產品。已知各制造一件使分別占用的設施A,B的臺時、調試工序時間及每天可用于這兩種家電的能力、各售出一件時的獲利情況如表1-1所示。問該公司應制造兩種家電各多少件，使獲取的利潤最大。
【表1-1】
| 項目 | 一 | 二 | 每天可用能力 |
| 設備A(h) | 0 | 5 | 15 |
| 設備B(h) | 6 | 2 | 24 |
| 測試工序(h) | 1 | 1 | 5 |
| 利潤 | 2 | 1 |
? ? ? ? 先用分別表示美佳公司制造家電一、二的數量。這時該公司可獲得利潤為元，令?，因問題中要求獲取的利潤最大，即?。是該公司能獲取的利潤的目標值，它是變量的函數，稱為目標函數。的取值受到設備A,B和調試工序能力的限制，用于描述限制條件的數學表達式稱為約束條件。由此可得【例1】的數學模型：
目標函數?????????
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?約束條件????????
（2）【例2】?
捷運公司在下一年度的1-4月的4個月內擬租用倉庫堆放物資。已知各月份所需倉庫面積列于表1-2.倉庫租借費用隨合同期而定，期限越長，折扣越大，具體數字見表1-3。租借倉庫的合同每月初都可辦理，每份合同具體規定租用面積和期限。因此該廠可根據需要，在任何一個月初辦理租借合同。每次辦理時可簽一份合同，也可簽若干份租用面積和租界期限不同的合同，試確定該公司簽訂租借合同的最優決策，目的是使所付租界費用最小。
【表1-2（單位：）】
| 月份 | 1 | 2 | 3 | 4 |
| 所需倉庫面積 | 15 | 10 | 20 | 12 |
【表1-3（單位：元/）】?
| 合同租賃期限 | 1個月 | 2個月 | 3個月 | 4個月 |
| 合同期內的租費 | 2800 | 4500 | 6000 | 7300 |
? ? ? ? 若用變量表示捷運公司在第個月初簽訂的租借期為個月的倉庫面積的合同。因5月份起該公司不需要租界倉庫，故均為0。該公司希望總的租借費用最小，故有如下數學模型：
?
（3）線性規劃的數學模型
? ? ? ? 從上面兩例可以看出，它們都屬于一類優化問題，它們的共同特征有：
- 每一個問題都用一組決策變量表示某一方案，這組決策變量的值就代表一個具體方案。一般這種變量的取值是非負且連續的
- 要有建模的有關數據，如資源擁有量、消耗資源定額、創造新價值等，并構成互不矛盾的約束條件，這些約束條件可以用一組線性等式或先行不等式來表示
- 都有一個要求達到的目標，它可用決策變量及其有關的價值系數構成的線性函數（稱為目標函數）來表示。按問題的不同，要求目標函數實現最大化或最小化
? ? ? ? 滿足以上三個條件的數學模型稱為線性規劃的數學模型。
一般形式為：
目標函數?????????
????????（2-1）稱為目標函數；稱為價值系數；（2-3）稱為約束條件；稱為技術系數；稱為限額系數。?
?緊縮形式為：
????????
矩陣形式為：
????????
?稱為決策變量向量；稱為價值系數向量或目標函數系數向量；稱為技術系數或約束系數矩陣；稱為資源常數向量或約束右端常數向量。
（4）線性規劃問題模型的假設
- 比例性：是指每個決策變量在約束條件中與在目標函數中數值變化時，按對應的技術系數與價值系數嚴格地成比例變化。這里不存在實際經濟活動中的邊際效用遞減效應
- 可加性：即目標函數的總值是各組成部分值之和；第個約束關系中各組成部分值之和就是第項資源需求總值。決策變量是獨立的，決策變量之間不發生關聯，且不允許變量之間有交叉。如規劃廣告預期收益時不能選擇看球賽的觀眾為決策變量，看電影的觀眾為決策變量等
- 可分性：決策變量的值具有可分性，即允許非整數值
- 確定性：即都是確定的已知值
? ? ? ? 可見，線性規劃模型是實際經濟管理問題的抽象與近似。
2.圖解法（兩個決策變量）
? ? ? ? ?圖解法簡單直觀，有助于了解線性規劃問題求解的基本原理。陰影區域中的每一個點（包括邊界點）都是這個線性規劃問題的解（稱可行解），陰影區域稱為可行域。
? ? ? ? 對一般的線性規劃問題，求解結果還可能存在以下幾種情況：
- 唯一解
- 無窮多最優解（多重最優解，圖2-4）
- 無界解（圖2-5）：缺乏必要約束條件
- 無可行解：有矛盾的約束條件
? ? ? ? ?從圖解法可以直觀地看到，當線性規劃問題的可行域非空時，它是有界或無界凸多邊形。若線性規劃問題存在最優解，它一定在可行域的某個頂點得到；若在兩個頂點同時得到最優解，則他們的連線上的任意一點都是最優解，即有無窮多最優解。
? ? ? ? 圖解法雖然簡單、直觀，但當變量數多于三個以上時，他就無能為力了。后面要介紹另一種方法——單純形法。為了便于討論，我們先規定線性規劃問題的數學模型的標準形式。
3.線性規劃問題的標準形式
（1）標準形式
- 一般形式
????????
? ? ? ? 在標準型中規定約束條件的右端項，否則等式兩端乘“-1”.當某一個，表示出現退化。
- 向量和矩陣形式
????????
? ? ? ? 其中，,,。
- 矩陣形式
????????
? ? ? ? 其中，,。
（2）如何轉化為標準型
- ??
- 約束方程為不等式——：加入非負松弛變量；：減去非負剩余變量（也可稱為松弛變量），把不等式轉化為等式
- 取值無約束的變量，令
4.線性規劃問題解的概念
（1）可行解
? ? ? ? 滿足約束條件的解稱為線性規劃問題的可行解，其中使目標函數達到最大值的可行解稱為最優解。
（2）基
? ? ? ? 設A為約束方程組的m*n(m<n)維系數矩陣，其秩為m。B是矩陣A中m*m階非奇異子矩陣（），則稱B為線性規劃問題的一個基。這就是說，B是由m個線性獨立的列向量組成。為不失一般性，可設
稱為基向量。與基向量相應的變量稱為基變量，否則成為非基變量。?
? ? ? ? 因為A的秩為m，且m<n，故它有無窮多個解。假設前m個列向量線性獨立，可以得到
或?
方程組（2-7）的一個基為?
設是對應于這個基的基變量。現若令（2-7）中非基變量，這時變量的個數等于線性方程的個數。用高斯消去法，求出一個解。該解非零分量的數目不大于方程個數m，稱X為基解。由此可見，有一個基，就可以求出一個基解。
（3）基可行解
? ? ? ? 滿足非負條件的基解稱為基可行解。
（4）可行基
? ? ? ? 對應于基可行解的基，稱為可行基。約束方程組（2-2）具有基解的數目最多為個。一般基可行解的數目要小于基解的數目。注意，基解中的非零分量的數目小于m個時，該基解是退化的。
二、線性規劃問題的幾何意義
1.基本概念
（1）凸集
? ? ? ? 設是維歐氏空間的一點集，若任意兩點的連線上的所有點；則稱為凸集。
（2）凸組合
? ? ? ? 設是n維歐氏空間中的k個點。若存在，使得，則稱為的凸組合（當時，稱為嚴格凸組合）。
（3）頂點
? ? ? ? 設是凸集，；若K中不存在兩個不同的點使得，則稱為的一個頂點（也成為極點或角點）
2.幾個定理
（1）【定理1】
????????若線性規劃問題存在可行域，則其可行域一定是凸集。
（2）【引理1】
????????線性規劃問題的可行解為基可行解的充要條件是正分量所對應的系數列向量是線性獨立的。
（3）【定理2】
????????線性規劃問題的基本可行解對應于可行域的頂點
（4）【引理2】
????????設K是有界凸集，則任何一點可表示為K的頂點的凸組合。
（5）【定理3】
????????若可行域有界，線性規劃的目標函數一定可以在可行域的頂點上達到最優。
【注】綜合2、3可知，線性規劃問題若存在最優解，則最優解一定存在于基本可行解之中。
3.線性規劃的解題思路
? ? ? ? 線性規劃問題可以有無數個可行解，而有限個頂點對應的是基本可行解，最優解只可能在頂點（基本可行解）上達到，故只要在有限個基可行解中尋找最優解即可。
? ? ? ? 思路是：從線性規劃問題的一個基本可行解開始，轉換到另一個使目標函數值增大的基本可行解。反復迭代，直到目標函數值達到最大時，就得到了最優解。
?
總結
以上是生活随笔為你收集整理的【运筹学】CH2 线性规划与单纯形法1——线性规划问题及其数学模型的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 48-Elasticsearch-2(D
- 下一篇： windows10开启http代理服务