第一節(jié)線性規(guī)劃的模型與圖解法一線性規(guī)劃問題及其數(shù)學(xué)模課件

第一節(jié)線性規(guī)劃的模型與圖解法一、線性規(guī)劃問題及其數(shù)學(xué)模型在生產(chǎn)管理和經(jīng)營活動中經(jīng)常需要解決：如何合理地利用有限的資源，以得到最大的效益。

例1.1

某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源?，F(xiàn)將有關(guān)數(shù)據(jù)列表如下：

試擬訂使總收入最大的生產(chǎn)方案。資源單耗產(chǎn)品資源甲乙資源限量煤電油9445310360200300單位產(chǎn)品價格

712

線性規(guī)劃模型的三要素3.約束條件：為實(shí)現(xiàn)優(yōu)化目標(biāo)需受到的限制，用決策變量的等式或不等式表示；1.決策變量：需決策的量，即待求的未知數(shù)；2.目標(biāo)函數(shù)：需優(yōu)化的量，即欲達(dá)的目標(biāo)，用決策變量的表達(dá)式表示；目標(biāo)函數(shù)：總收入，記為z,則z=7x1+12x2，為體現(xiàn)對其追求極大化，在z的前面冠以極大號Max；決策變量：甲、乙產(chǎn)品的計劃產(chǎn)量，記為；在本例中約束條件：分別來自資源煤、電、油限量的約束，和產(chǎn)量非負(fù)的約束，表示為解：設(shè)安排甲、乙產(chǎn)量分別為,總收入為，

則模型為：線性規(guī)劃模型的一般形式：（以MAX型、約束為例）決策變量：目標(biāo)函數(shù)：約束條件：則模型可表示為模型一般式的矩陣形式記回顧例1.1的模型其中表示決策變量的向量；表示產(chǎn)品的價格向量；表示資源限制向量；表示產(chǎn)品對資源的單耗系數(shù)矩陣。一般地

中稱為決策變量向量，稱為價格系數(shù)向量,

稱為技術(shù)系數(shù)矩陣,稱為資源限制向量。問題：為什么A稱為技術(shù)系數(shù)矩陣？二、線性規(guī)劃模型的圖解法圖解法是用畫圖的方式求解線性規(guī)劃的一種方法。它雖然只能用于解二維（兩個變量）的問題，但其主要作用并不在于求解，而是在于能夠直觀地說明線性規(guī)劃解的一些重要性質(zhì)。（1）做約束的圖形

先做非負(fù)約束的圖形；再做資源約束的圖形。

以例1.1為例，其約束為

各約束的公共部分即模型的約束，稱可行域。1.圖解法的步驟（2）做目標(biāo)的圖形對于目標(biāo)函數(shù)任給二不同的值，便可做出相應(yīng)的二直線，用虛線表示。以例1.1為例，其目標(biāo)為，分別令

，做出相應(yīng)的二直線，便可看出增大的方向。（3）求出最優(yōu)解將目標(biāo)直線向使目標(biāo)優(yōu)化的方向移，直至可行域的邊界為止，這時其與可行域的“切”點(diǎn)即最優(yōu)解。

如在例1.1中，是可行域的一個角點(diǎn)，

經(jīng)求解交出的二約束直線聯(lián)立的方程可解得

由圖解法的結(jié)果得到例1.1的最優(yōu)解，還可將其代入目標(biāo)函數(shù)求得相應(yīng)的最優(yōu)目標(biāo)值。說明當(dāng)甲產(chǎn)量安排20個單位，乙產(chǎn)量安排24個單位時，可獲得最大的收入428。2.由圖解法得到線性規(guī)劃解的一些特性（1）線性規(guī)劃的約束集（即可行域）是一個凸多面體。（2）線性規(guī)劃的最優(yōu)解（若存在的話）必能在可行域的角點(diǎn)獲得。

因為，由圖解法可知，只有當(dāng)目標(biāo)直線平移到邊界時，才能使目標(biāo)