1.9.4 線性規(guī)劃

　　線性規(guī)劃是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個(gè)重要分支，它是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法。線性規(guī)劃所研究的問題是：在線性約束條件下，使線性目標(biāo)函數(shù)達(dá)到最優(yōu)。為了解決實(shí)際問題，首先需要把它歸結(jié)為數(shù)學(xué)問題，即建立數(shù)學(xué)模型。線性規(guī)劃問題的數(shù)學(xué)模型是描述實(shí)際問題的抽象的數(shù)學(xué)形式。

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

　　建立數(shù)學(xué)模型的一般步驟：

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

　　2. 寫出目標(biāo)函數(shù)(求最大值或最小值);

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

　　標(biāo)準(zhǔn)形式及其特點(diǎn)

　　為便于今后求解，我們把線性規(guī)劃問題的數(shù)學(xué)模型規(guī)定統(tǒng)一的形式，稱之為標(biāo)準(zhǔn)形式，簡(jiǎn)稱標(biāo)準(zhǔn)型。線性規(guī)劃問題的標(biāo)準(zhǔn)形式也是單純形方法的基礎(chǔ)。

　　線性規(guī)劃問題的標(biāo)準(zhǔn)形式有以下特點(diǎn)：

　　1.目標(biāo)函數(shù)求最小值;

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

　　3.每個(gè)約束方程右邊的常數(shù)都是非負(fù)數(shù)，即.；

　　線性規(guī)劃問題數(shù)學(xué)模型的標(biāo)準(zhǔn)形式：

　　求

　　其中 均為常數(shù)。

　　化標(biāo)準(zhǔn)形式

　　(1)如果目標(biāo)函數(shù)求最大值，即。

　　只須令 ，便可將目標(biāo)函數(shù)求最大值轉(zhuǎn)化為求最小值，即求

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

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

　　線性規(guī)劃問題的一些重要概念

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

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

，則稱方陣B為線性規(guī)劃問題的一個(gè)基矩陣，簡(jiǎn)稱為基。

　　矩陣B中的每一列所對(duì)應(yīng)的m個(gè)變量稱為基變量，除基變量以外的n-m個(gè)變量，我們稱為非基變量。

　　(2)基礎(chǔ)解、基礎(chǔ)可行解、基礎(chǔ)最優(yōu)解

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

　　如果基礎(chǔ)解滿足非負(fù)限制，則稱它為基礎(chǔ)可行解。

　　使目標(biāo)函數(shù)取得最小值的基礎(chǔ)可行解，稱為基礎(chǔ)最優(yōu)解。

　　(3)可行基、最優(yōu)基

　　對(duì)應(yīng)于基礎(chǔ)可行解的基，稱為可行基。

　　對(duì)應(yīng)于基礎(chǔ)最優(yōu)解的基，稱為最優(yōu)基。

　　通過(guò)例題讓大家理解這幾個(gè)概念及基礎(chǔ)最優(yōu)解求出的過(guò)程。

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

　　2.重點(diǎn)和難點(diǎn)：

　　1) 存儲(chǔ)器部分：特別是cache和虛擬存儲(chǔ)器是重點(diǎn)的復(fù)習(xí)方面

　　2) 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)：計(jì)算機(jī)的安全和可靠性方面計(jì)算題目

　　3) 體系結(jié)構(gòu)其他知識(shí)：RISC和并行處理的技術(shù)

　　4) 數(shù)學(xué)部分

　　相關(guān)推薦：

　　2012年軟考系統(tǒng)分析師考試60天完美復(fù)習(xí)計(jì)劃

　　2012年軟件水平考試網(wǎng)絡(luò)工程師章節(jié)筆記講義匯總

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