任務一　線性規劃的概念

1.1　線性規劃問題及其數學模型

1.1.1　問題的提出

在生產管理和經營活動中經常提出一類問題，即如何合理地利用有限的人力、物力、財力等資源，以便得到最好的經濟效果。

例2-1-1　生產計劃問題　某工廠在計劃期內要安排甲、乙兩種產品的生產，生產單位產品所需要的設備臺時以及A、B兩種原材料的消耗以及資源的限制如表2-1-1所示，工廠每生產一件產品甲可獲利2元，每生產一件產品乙可獲利3元，問工廠應如何安排生產任務才能使獲利最多？

表2-1-1

1.1.2　數學模型的建立

線性規劃的研究對象是稀缺資源最優分配問題，即將有限的資源以最佳的方法，分配于相互競爭的活動之中。一般體現為在一定的資源條件下，如何合理使用，達到效益的最大化；或者在給定任務下，如何統籌安排，盡量降低成本，使資源消耗最小化。由于這些問題從本質上看很多都是線性的，所以我們稱之為線性規劃。

那么接下來我們建立例2-1-1的數學模型。

第一步，設定變量。題目中要求我們決策兩種產品的生產計劃，所以我們可以設生產產品甲、乙的數量分別為x1和x2。這些變量是由決策部門加以確定的，我們把它們稱為決策變量。決策變量的取值均為非負。

第二步，建立目標函數，即我們在具體問題中要達到的目標。在例2-1-1中，我們的目標是要獲得最大利潤，即

maxz＝2x1＋3x2

第三步，建立約束條件。約束條件是我們在安排規劃的過程中所受到的資源限制。在本例中，該生產計劃受到一系列現實條件的約束。

設備臺時數：生產所用的設備臺時不得超過所擁有的設備臺時，即

x1＋2x2≤8

原材料數：生產所用的兩種原材料A、B不得超過所擁有的原材料總數，即

4x1≤16

4x2≤12

非負約束：生產的產品數不可能為負值，即

x1，x2≥0

綜上所述，我們可以把該問題的數學模型表示為

例2-1-2　營養配餐問題　營養學家指出，成人良好的日常飲食應該至少提供0.075kg的碳水化合物、0.06kg的蛋白質、0.06kg的脂肪。1kg食物A含有0.105kg碳水化合物、0.07kg蛋白質、0.14kg脂肪，花費28元；而1kg食物B含有0.105kg碳水化合物、0.14kg蛋白質、0.07kg脂肪，花費21元。為了滿足營養專家指出的日常飲食要求，同時使花費最低，需要同時食用多少食物A和食物B？

解：設每天食用xkg食物A，ykg食物B，總成本為z，那么

minz＝28x＋21y

而這些食物中所含有的碳水化合物、蛋白質和脂肪都要達到需求，因此

1.2　線性規劃模型的概念

上述兩個例題雖然在內容上不盡相同，但其數學模型都有著共同的特征，它們都是要求一組變量（一般是非負的）在一組線性的約束條件下，使得一個線性的目標函數取得最大值或最小值。我們把這類問題統稱為線性規劃問題。

根據問題的性質，線性規劃有多種形式，目標函數有要求最大化的，也有要求最小化的；約束條件可以是不等式，也可以是等式；決策變量一般是非負的。因此，我們可以抽象出線性規劃的一般形式

其中，我們要達到的最大化或最小化的目標式稱為目標函數，下邊的方程組稱為約束條件，表明在規劃中將要受到的資源限制，求出的使目標達到最優的x1到xn的取值叫做最優解，把最優解代入目標函數求出的目標函數值稱為最優值。