第六章線性經(jīng)濟模型簡介投入產(chǎn)出模型簡介

6.1

單純形法6.3

線性規(guī)劃6.216.2線性規(guī)劃

一、規(guī)劃線性問題的數(shù)學(xué)模型二、線性規(guī)劃問題的標準形式

三、線性規(guī)劃問題的幾個基本概念

四、兩個變量線性規(guī)劃問題的圖解法2一、規(guī)劃線性問題的數(shù)學(xué)模型例1某工廠生產(chǎn)甲、乙兩種產(chǎn)品，要用A,B,C三種不同的原料，從工藝資料知道：每生產(chǎn)1件甲種產(chǎn)品，需用三種原料分別為1，1，0單位；生產(chǎn)1件乙種產(chǎn)品，需用三種原料為1，2，1單位；每天原料供應(yīng)的能力分別為6，6，3單位。又知道，每生產(chǎn)1件甲、乙產(chǎn)品，工廠利潤收入分別為3千元和4千元，問：工廠應(yīng)如何安排計劃，使一天的總利潤為最大？解：

為了解決這個問題，首先需要建立它的數(shù)學(xué)模型。建立數(shù)學(xué)模型一般要經(jīng)過以下四步：第一步，明確問題的條件。一般可以將問題的條件列成表格形式，如下表6－33第二步，明確問題的變量。為了做出決策，我們把決策中關(guān)鍵量設(shè)為未知量，這種變量稱為決策變量。本例中，設(shè)產(chǎn)品甲的日產(chǎn)量為件，產(chǎn)品乙的日產(chǎn)量為件。顯然，它們都是非負的，即4第三步，明確問題的目標。

該問題的目標是在現(xiàn)有條件下，追求最大的利潤。設(shè)該工廠一天獲得的總利潤為S，則依題意得

問題就是要求它的最大值，因此，目標函數(shù)為

第四步，明確問題的約束條件。由于每天的原料供應(yīng)限制，A種原料每天只能供給6個單位，所以一天生產(chǎn)甲、乙兩種產(chǎn)品所消耗A種原料不得超過6個單位，即

5第四步，明確問題的約束條件。由于每天的原料供應(yīng)限制，A種原料每天只能供給6個單位，所以一天生產(chǎn)甲、乙兩種產(chǎn)品所消耗A種原料不得超過6個單位，即

類似地，有

因此，對變量的限制為

約束條件

6綜合上述分析，我們可以寫出該問題的數(shù)學(xué)模型如下

約束條件

目標函數(shù)

7例2某建設(shè)工地，需要直徑相同、長度不同的成套鋼筋，

每套由7根2m長和2根7m長的鋼筋組成，今有15m長的鋼筋150根，問怎樣下料，才能使廢料最少？解：把一根15m長的鋼筋割成分別為7m和2m的兩種規(guī)格，有三種比較經(jīng)濟的方法，如表6－4所示。8S表示廢料的總長度。依題意，得把分別表示采用上述三種方法割料的15m長的鋼筋的根數(shù)，又由于每套由7根2m長，2根7m長的鋼筋組成，而2m長有根7m長有根，根據(jù)配套要求，有9問題的目標是廢料最少，總廢料長為

綜合上述討論，得到該問題的數(shù)學(xué)模型為：

10總結(jié)從以上兩例子可以看出，它們都屬于優(yōu)化問題，并具有以下共同特征：（1）每一個問題都可以用一組稱為決策變量的未知量來表示某種方案，這組未知變量的一組定值就代表一個具體方案。通常，要求這些未知量的取值是非負的。

（2）每個問題都存在一定的限制條件，這些限制條件都可能用決策變量的一組線性等式或線性不等式來表示。

（3）都有一個目標，并且這個目標可以表示為決策變量的線性函數(shù)，并按問題的要求，求這個目標函數(shù)的最大（?。┲?。11線性規(guī)劃問題的數(shù)學(xué)模型的定義一般地，這類問題都可用數(shù)學(xué)語言描述如下：求一組變量的值，使其滿足約束條件

并使函數(shù)

達到最大（?。┲?，其中

均為常數(shù)。這就是線性規(guī)劃問題的數(shù)學(xué)模型。12線性規(guī)劃問題的數(shù)學(xué)模型的一般形式是

簡記為13二、線性規(guī)劃問題的標準形式

定義1下述線性規(guī)劃問題的數(shù)學(xué)模型

稱為線性規(guī)劃問題的標準形式。14線性規(guī)劃問題的標準形式有以下特點：

1.求目標函數(shù)的最大值。2.所有的約束方程都用等式表示。3.所有的變量都是非負的。4.約束方程等式右邊的常數(shù)（稱為約束常數(shù)）都是非負的。15上述標準形式還可以簡寫為

16矩陣表示17化為標準形1.化小為大2.化不等式為等式松弛變量

松弛變量

183.化負為正4.化“無非負限制”為正第i個約束方程的兩邊同乘以—1

19例3試將下面的線性規(guī)劃問題化為標準形式：

解：20例4試將下面的線性規(guī)劃問題化為標準形式：

解：21三、線性規(guī)劃問題的幾個基本概念

定義2

在線性規(guī)劃問題中，滿足約束條件的解，稱為可行解。

一般來說，線性規(guī)劃問題可能有無窮多個可行解，也可能沒有可行解。使目標函數(shù)達到最大值或最小值的可行解，稱為最優(yōu)解。將最優(yōu)解代入目標函數(shù)，所得到的目標函數(shù)值，稱為最優(yōu)值。

22定義3在線性規(guī)劃問題

中，設(shè)約束方程AX=b中的系數(shù)矩陣A的秩r(A)=m,B是矩陣A中任一m×m階的非奇異矩陣,則稱B為該線性規(guī)劃問題的一個基。

23基向量、非基向量、基變量、非基變量

B的列向量稱為基向量

N的列向量稱為非基向量

基向量對應(yīng)的變量xj

稱為基變量

非基變量所對應(yīng)的變量稱為非基變量

24基本解、基本可行解、基可行解、最優(yōu)基可行解定義4

：在線性規(guī)劃問題中，非基變量取零值時所得到的解稱為基本解。如果基本解又滿足非負條件，則稱為基本可行解，簡稱基可行解。能使目標函數(shù)達到最優(yōu)的基可行解，稱為最優(yōu)基可行解。

基本可行解一定是基本解，也一定是可行解，但反之不成立。

25例5寫出下列線性規(guī)劃問題的所有基陣：

解：約束方程組的系數(shù)矩陣及各列向量分別為26知都是非奇異矩陣，所以都是這一問題的基。

27四、兩個變量線性規(guī)劃問題的圖解法

例6用圖解法求解下列線性規(guī)劃問題：解：（1）畫出可行域；（2）畫出等值線；（3）求出最優(yōu)解。28因此，方程的交點坐標為（4，2），該問題的最優(yōu)解為：