1.9.4 線性規劃

　　線性規劃是運籌學中研究較早、發展較快、應用廣泛、方法較成熟的一個重要分支，它是輔助人們進行科學管理的一種數學方法。線性規劃所研究的問題是：在線性約束條件下，使線性目標函數達到最優。為了解決實際問題，首先需要把它歸結為數學問題，即建立數學模型。線性規劃問題的數學模型是描述實際問題的抽象的數學形式。

　　線性規劃問題的數學模型是指求一組滿足一個線性方程組(或線性不等式組，或線性方程與線性不等式混合組)的非負變量，使這組變量的一個線性函數達到最大值或最小值的數學表達式。

　　建立數學模型的一般步驟：

　　1. 確定決策變量(有非負約束);

　　2. 寫出目標函數(求最大值或最小值);

　　3. 寫出約束條件(由等式或不等式組成)。

　　標準形式及其特點

　　為便于今后求解，我們把線性規劃問題的數學模型規定統一的形式，稱之為標準形式，簡稱標準型。線性規劃問題的標準形式也是單純形方法的基礎。

　　線性規劃問題的標準形式有以下特點：

　　1.目標函數求最小值;

　　2.約束條件中除決策變量外，其余條件均為等式;

　　3.每個約束方程右邊的常數都是非負數，即.；

　　線性規劃問題數學模型的標準形式：

　　求

　　其中 均為常數。

　　化標準形式

　　(1)如果目標函數求最大值，即。

　　只須令 ，便可將目標函數求最大值轉化為求最小值，即求

　　(2)引進松弛變量，將約束條件中的不等式化為等式(決策變量非負約束除外)。

　　(3)在約束條件為等式的前提下，如果某個方程右邊的常數是負數，則只須在方程兩邊乘以-1.

　　線性規劃問題的一些重要概念

　　(1)基、基變量、非基變量

　　如果矩陣B是約束方程系數矩陣A中的 階非奇異矩陣

，則稱方陣B為線性規劃問題的一個基矩陣，簡稱為基。

　　矩陣B中的每一列所對應的m個變量稱為基變量，除基變量以外的n-m個變量，我們稱為非基變量。

　　(2)基礎解、基礎可行解、基礎最優解

　　在約束方程組中，如果令各非基變量等于零，所得的解，稱為線性規劃問題的基礎解。

　　如果基礎解滿足非負限制，則稱它為基礎可行解。

　　使目標函數取得最小值的基礎可行解，稱為基礎最優解。

　　(3)可行基、最優基

　　對應于基礎可行解的基，稱為可行基。

　　對應于基礎最優解的基，稱為最優基。

　　通過例題讓大家理解這幾個概念及基礎最優解求出的過程。

　　線性規劃的解法一般有圖形法和單純形法。

　　2.重點和難點：

　　1) 存儲器部分：特別是cache和虛擬存儲器是重點的復習方面

　　2) 計算機系統結構：計算機的安全和可靠性方面計算題目

　　3) 體系結構其他知識：RISC和并行處理的技術

　　4) 數學部分

　　相關推薦：

　　2012年軟考系統分析師考試60天完美復習計劃

　　2012年軟件水平考試網絡工程師章節筆記講義匯總

　　2012年上半年軟件水平考試成績查詢匯總