一章一節(jié)模型與圖解法

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

1、線性規(guī)劃的問題

在生產(chǎn)管理和經(jīng)營活動中經(jīng)常需要解決：如何合理地利用有限的資源，以得到最大的效益。

例1

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

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

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

則模型為：線性規(guī)劃模型的一個基本特點：

目標和約束均為變量的線性表達式如果模型中出現(xiàn)如的非線性表達式，則屬于非線性規(guī)劃。例2

某市今年要興建大量住宅,已知有三種住宅體系可以大量興建，各體系資源用量及今年供應量見下表：要求在充分利用各種資源條件下使建造住宅的總面積為最大(即求安排各住宅多少m2)，求建造方案。水泥(公斤/m2)4000(千工日)147000(千塊)150000(噸)20000(噸)110000(千元)資源限量3.5——18025120大模住宅3.0——19030135壁板住宅4.521011012105磚混住宅人工(工日/m2)磚(塊/m2)鋼材(公斤/m2)造價(元/m2)

資源住宅體系

解:

設今年計劃修建磚混、壁板、大模住宅各為

x1,x2,x3m2,z為總面積,則本問題的數(shù)學模型為:

前蘇聯(lián)的尼古拉也夫斯克城住宅興建計劃采用了上述模型，共用了12個變量，10個約束條件。練習：某畜牧廠每日要為牲畜購買飼料以使其獲取A、B、C、D四種養(yǎng)分。市場上可選擇的飼料有M、N兩種。有關數(shù)據(jù)如下：試決定買M與N二種飼料各多少公斤而使支出的總費用為最少？410售價

0.40.62.01.7牲畜每日每頭需要量00.10.20.1N0.100.10.2M每公斤含營養(yǎng)成分

ABCD飼料解：設購買M、N飼料各為，則3.線性規(guī)劃模型的一般形式：（以MAX型、約束為例）決策變量：目標函數(shù)：約束條件：則模型可表示為模型一般式的矩陣形式記回顧例1的模型其中表示決策變量的向量；表示產(chǎn)品的價格向量；表示資源限制向量；表示產(chǎn)品對資源的單耗系數(shù)矩陣。一般地

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

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

問題：不等式的幾何意義是什么？怎樣做圖？（1）做約束的圖形

先做非負約束的圖形；再做資源約束的圖形。

以例1為例，其約束為

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

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

如在例1中，是可行域的一個角點，

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

由圖解法的結果得到例1的最優(yōu)解，還可將其代入目標函數(shù)求得相應的最優(yōu)目標值。說明當甲產(chǎn)量安排20個單位，乙產(chǎn)量安排24個單位時，可獲得最大的收入428。練習：用圖解法求解

下面的線性規(guī)劃。

問題：在上兩例中

——

多邊形，而且是“凸”形的多邊形。

最優(yōu)解在什么位置獲得？

——

在邊界，而且是在某個頂點獲得。

線性規(guī)劃的可行域是一個什么形狀？2.由圖解法得到線性規(guī)劃解的一些特性（1）線性規(guī)劃的約束集（即可行域）是一個凸多面體。

凸多面體是凸集的一種。所謂凸集是指：集中任兩點的連線仍屬此集。試判斷下面的圖形是否凸集：

凸集中的“極點”，又稱頂點或角點，是指它屬于凸集，但不能表示成集中某二點連線的內(nèi)點。如多邊形的頂點。（2）線性規(guī)劃的最優(yōu)解（若存在的話）必能在可行域的角點獲得。

因為，由圖解法可知，只有當目標直線平移到邊界時，才能使目