模型與圖解法課件

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

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

試擬訂使總收入最大的生產(chǎn)方案。資源單耗產(chǎn)品資源甲乙資源限量煤電油9445310360200300單位產(chǎn)品價(jià)格712例1某工廠可生產(chǎn)甲、乙兩種產(chǎn)2

線性規(guī)劃模型的三要素3.約束條件：為實(shí)現(xiàn)優(yōu)化目標(biāo)需受到的限制，用決策變量的等式或不等式表示；1.決策變量：需決策的量，即待求的未知數(shù)；2.目標(biāo)函數(shù)：需優(yōu)化的量，即欲達(dá)的目標(biāo)，用決策變量的表達(dá)式表示；

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

則模型為：解：設(shè)安排甲、乙產(chǎn)量分別為,總收入為5線性規(guī)劃模型的一個(gè)基本特點(diǎn)：

目標(biāo)和約束均為變量的線性表達(dá)式如果模型中出現(xiàn)如的非線性表達(dá)式，則屬于非線性規(guī)劃。線性規(guī)劃模型的一個(gè)基本特點(diǎn)：

目標(biāo)和約束均為6例2某市今年要興建大量住宅,已知有三種住宅體系可以大量興建，各體系資源用量及今年供應(yīng)量見(jiàn)下表：要求在充分利用各種資源條件下使建造住宅的總面積為最大(即求安排各住宅多少m2)，求建造方案。水泥(公斤/m2)4000(千工日)147000(千塊)150000(噸)20000(噸)110000(千元)資源限量3.5——18025120大模住宅3.0——19030135壁板住宅4.521011012105磚混住宅人工(工日/m2)磚(塊/m2)鋼材(公斤/m2)造價(jià)(元/m2)資源住宅體系例2某市今年要興建大量住宅,已知有三種住宅體系可以水泥7解:設(shè)今年計(jì)劃修建磚混、壁板、大模住宅各為

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

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

0.40.62.01.7牲畜每日每頭需要量00.10.20.1N0.100.10.2M每公斤含營(yíng)養(yǎng)成分ABCD飼料練習(xí)：某畜牧廠每日要為牲畜購(gòu)買(mǎi)飼料以使其獲取A、B、C、D四9解：設(shè)購(gòu)買(mǎi)M、N飼料各為，則解：設(shè)購(gòu)買(mǎi)M、N飼料各為，則10線性規(guī)劃模型的一般形式：（以MAX型、約束為例）決策變量：目標(biāo)函數(shù)：約束條件：線性規(guī)劃模型的一般形式：（以MAX型、約束為例）決策11則模型可表示為模型一般式的矩陣形式記則模型可表示為模型一般式的矩陣形式記12回顧例1的模型其中表示決策變量的向量；表示產(chǎn)品的價(jià)格向量；表示資源限制向量；表示產(chǎn)品對(duì)資源的單耗系數(shù)矩陣?；仡櫪?的模型其中13一般地

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

稱為技術(shù)系數(shù)矩陣,稱為資源限制向量。問(wèn)題：為什么A稱為技術(shù)系數(shù)矩陣？一般地

中稱為決策變量向量，稱為價(jià)格系數(shù)向量14二、線性規(guī)劃模型的圖解法圖解法是用畫(huà)圖的方式求解線性規(guī)劃的一種方法。它雖然只能用于解二維（兩個(gè)變量）的問(wèn)題，但其主要作用并不在于求解，而是在于能夠直觀地說(shuō)明線性規(guī)劃解的一些重要性質(zhì)。二、線性規(guī)劃模型的圖解法圖解法是用畫(huà)圖的方式求解線性規(guī)劃的一151.圖解法的步驟（1）做約束的圖形先做非負(fù)約束的圖形；再做資源約束的圖形。以例1為例，其約束為

1.圖解法的步驟（1）做約束的圖形以例1為例，其約束為16問(wèn)題：不等式的幾何意義是什么？怎樣做圖？問(wèn)題：不等式的幾何意義是什么？怎樣做圖？17（1）做約束的圖形

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

以例1為例，其約束為

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

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

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

經(jīng)求解交出的二約束直線聯(lián)立的方程可解得（3）求出最優(yōu)解20

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

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

練習(xí)：用圖解法求解

下面的線性規(guī)劃。22問(wèn)題：在上兩例中

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

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

——在邊界，而且是在某個(gè)頂點(diǎn)獲得。

線性規(guī)劃的可行域是一個(gè)什么形狀？問(wèn)題：在上兩例中——多邊形，而且是“凸”形的多邊形。232.由圖解法得到線性規(guī)劃解的一些特性（1）線性規(guī)劃的約束集（即可行域）是一個(gè)凸多面體。

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

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

因?yàn)?，由圖解法可知，只有當(dāng)目標(biāo)直線平移到邊界時(shí)，才能使目標(biāo)z達(dá)到最大限度的優(yōu)化。問(wèn)題：本性質(zhì)有何重要意義？——它使得在可行域中尋優(yōu)的工作由“無(wú)限”上升為“有限”，從而為線性規(guī)劃的算法設(shè)計(jì)提供了重要基礎(chǔ)。（2）線性規(guī)劃的最優(yōu)解（若存在的話）必能在可行域的角點(diǎn)獲得。25（3）線性規(guī)劃解的幾種情形①

唯一最優(yōu)解②

多重最優(yōu)解③

無(wú)解④

無(wú)有限最優(yōu)解（無(wú)界解）（3）線性規(guī)劃解的幾種情形①唯一最優(yōu)解②多重最優(yōu)解③無(wú)26第一節(jié)線性規(guī)劃的模型與圖解法一、線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型在生產(chǎn)管理和經(jīng)營(yíng)活動(dòng)中經(jīng)常需要解決：如何合理地利用有限的資源，以得到最大的效益。第一節(jié)線性規(guī)劃的模型與圖解法在生產(chǎn)管理和經(jīng)營(yíng)27

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

試擬訂使總收入最大的生產(chǎn)方案。資源單耗產(chǎn)品資源甲乙資源限量煤電油9445310360200300單位產(chǎn)品價(jià)格712例1某工廠可生產(chǎn)甲、乙兩種產(chǎn)28

線性規(guī)劃模型的三要素3.約束條件：為實(shí)現(xiàn)優(yōu)化目標(biāo)需受到的限制，用決策變量的等式或不等式表示；1.決策變量：需決策的量，即待求的未知數(shù)；2.目標(biāo)函數(shù)：需優(yōu)化的量，即欲達(dá)的目標(biāo)，用決策變量的表達(dá)式表示；

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

則模型為：解：設(shè)安排甲、乙產(chǎn)量分別為,總收入為31線性規(guī)劃模型的一個(gè)基本特點(diǎn)：

目標(biāo)和約束均為變量的線性表達(dá)式如果模型中出現(xiàn)如的非線性表達(dá)式，則屬于非線性規(guī)劃。線性規(guī)劃模型的一個(gè)基本特點(diǎn)：

目標(biāo)和約束均為32例2某市今年要興建大量住宅,已知有三種住宅體系可以大量興建，各體系資源用量及今年供應(yīng)量見(jiàn)下表：要求在充分利用各種資源條件下使建造住宅的總面積為最大(即求安排各住宅多少m2)，求建造方案。水泥(公斤/m2)4000(千工日)147000(千塊)150000(噸)20000(噸)110000(千元)資源限量3.5——18025120大模住宅3.0——19030135壁板住宅4.521011012105磚混住宅人工(工日/m2)磚(塊/m2)鋼材(公斤/m2)造價(jià)(元/m2)資源住宅體系例2某市今年要興建大量住宅,已知有三種住宅體系可以水泥33解:設(shè)今年計(jì)劃修建磚混、壁板、大模住宅各為

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

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

0.40.62.01.7牲畜每日每頭需要量00.10.20.1N0.100.10.2M每公斤含營(yíng)養(yǎng)成分ABCD飼料練習(xí)：某畜牧廠每日要為牲畜購(gòu)買(mǎi)飼料以使其獲取A、B、C、D四35解：設(shè)購(gòu)買(mǎi)M、N飼料各為，則解：設(shè)購(gòu)買(mǎi)M、N飼料各為，則36線性規(guī)劃模型的一般形式：（以MAX型、約束為例）決策變量：目標(biāo)函數(shù)：約束條件：線性規(guī)劃模型的一般形式：（以MAX型、約束為例）決策37則模型可表示為模型一般式的矩陣形式記則模型可表示為模型一般式的矩陣形式記38回顧例1的模型其中表示決策變量的向量；表示產(chǎn)品的價(jià)格向量；表示資源限制向量；表示產(chǎn)品對(duì)資源的單耗系數(shù)矩陣?；仡櫪?的模型其中39一般地

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

稱為技術(shù)系數(shù)矩陣,稱為資源限制向量。問(wèn)題：為什么A稱為技術(shù)系數(shù)矩陣？一般地

中稱為決策變量向量，稱為價(jià)格系數(shù)向量40二、線性規(guī)劃模型的圖解法圖解法是用畫(huà)圖的方式求解線性規(guī)劃的一種方法。它雖然只能用于解二維（兩個(gè)變量）的問(wèn)題，但其主要作用并不在于求解，而是在于能夠直觀地說(shuō)明線性規(guī)劃解的一些重要性質(zhì)。二、線性規(guī)劃模型的圖解法圖解法是用畫(huà)圖的方式求解線性規(guī)劃的一411.圖解法的步驟（1）做約束的圖形先做非負(fù)約束的圖形；再做資源約束的圖形。以例1為例，其約束為

1.圖解法的步驟（1）做約束的圖形以例1為例，其約束為42問(wèn)題：不等式的幾何意義是什么？怎樣做圖？問(wèn)題：不等式的幾何意義是什么？怎樣做圖？43（1）做約束的圖形

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

以例1為例，其約束為

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

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

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

經(jīng)求解交出的二約束直線聯(lián)立的方程可解得（3）求出最優(yōu)解46

由圖解法的結(jié)果得到例1的最優(yōu)解，還可將其代入目標(biāo)函數(shù)求得相應(yīng)的最優(yōu)目標(biāo)值