運(yùn)籌學(xué)-第2講

1、2022-5-61線性規(guī)劃與目標(biāo)規(guī)劃線性規(guī)劃與目標(biāo)規(guī)劃2022-5-62目目 錄錄1.1.線性規(guī)劃與單純形法線性規(guī)劃與單純形法2.2.對偶理論和靈敏度分析對偶理論和靈敏度分析3.3.運(yùn)輸問題運(yùn)輸問題4.4.目標(biāo)規(guī)劃目標(biāo)規(guī)劃2022-5-63q線性規(guī)劃(Linear Programming)是運(yùn)籌學(xué)的一個(gè)重要分支。q線性規(guī)劃在理論上比較成熟，在實(shí)用中的應(yīng)用日益廣泛與深入。它已是現(xiàn)代科學(xué)管理的重要手段之一。q線性規(guī)劃最常用的求解方法 單純形法單純形法(Simplex Method) 由丹捷格(G B Dantzig)提出(1947年)。線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型2022-5-

2、64線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型 1.1 1.1 問題的提出問題的提出例例1 1 生產(chǎn)計(jì)劃 某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)、兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時(shí)及A、B兩種原材料的消耗，如表所示。問題：工廠應(yīng)分別生產(chǎn)多少單位甲、乙產(chǎn)品才能使工廠獲利最多？ 如何用數(shù)學(xué)關(guān)系式描述這個(gè)問題？如何用數(shù)學(xué)關(guān)系式描述這個(gè)問題？2022-5-65線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q設(shè)x1 ，x2 分別表示計(jì)劃生產(chǎn)I，II產(chǎn)品的數(shù)量，稱它們?yōu)闆Q策變量決策變量。q生產(chǎn)x1 ，x2 的多少，受到資源擁有量的限制，即存在約約束條件束條件。 x1 +2x2 84 x1 164 x2

3、12q生產(chǎn)的產(chǎn)品不能是負(fù)值： x1 ，x2 0。q如何安排生產(chǎn)，使得利潤最大，這是目標(biāo)函數(shù)目標(biāo)函數(shù)。max z = 2 x1 + 3 x22022-5-66線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q因此該問題的數(shù)學(xué)模型為：因此該問題的數(shù)學(xué)模型為： ( 設(shè)生產(chǎn)甲產(chǎn)品 x1 個(gè)單位、生產(chǎn)乙產(chǎn)品 x2 個(gè)單位)q目標(biāo)函數(shù)目標(biāo)函數(shù): max z = 2 x1 + 3 x2q約束條件約束條件: x1 +2x2 84 x1 164 x2 12 x1 ，x2 0q這種模型實(shí)際上是一種約束限制下的最優(yōu)線性數(shù)學(xué)模型，稱為線性規(guī)劃。2022-5-67線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q例例2

4、 2 簡化的環(huán)境保護(hù)問題 靠近某河流有兩個(gè)化工廠，流經(jīng)第一化工廠的河流流量為每天500萬立方米，在兩個(gè)工廠之間有一條流量為每天200萬立方米的支流。q 第一化工廠每天排放含有某種有害物質(zhì)的工業(yè)污水2萬立方米，第二化工廠每天排放這種工業(yè)污水1.4萬立方米。q 從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有20%可自然凈化。根據(jù)環(huán)保要求，河流中工業(yè)污水的含量應(yīng)不大于0.2%。這兩個(gè)工廠都需各自處理一部分工業(yè)污水。第一化工廠處理工業(yè)污水的成本是1000元/萬立方米。第二化工廠處理工業(yè)污水的成本是800元/萬立方米。q 現(xiàn)在問在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使這兩個(gè)工現(xiàn)在問在滿足環(huán)

5、保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使這兩個(gè)工廠總的處理工業(yè)污水費(fèi)用最小。廠總的處理工業(yè)污水費(fèi)用最小。2022-5-68線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q 建模型之前的分析和計(jì)算建模型之前的分析和計(jì)算q 設(shè)設(shè)：第一化工廠每天處理工業(yè)污水量為x1 萬立方米，第二化工廠每天處理工業(yè)污水量為x2 萬立方米。112(2)250010000.8(2)(1.4)27001000 xxx經(jīng)第二工廠前的水質(zhì)要求：經(jīng)第二工廠后的水質(zhì)要求：此問題的線性規(guī)劃模型此問題的線性規(guī)劃模型： 目標(biāo)函數(shù)目標(biāo)函數(shù)：max z = 1000 x1 + 800 x2 約束條件約束條件：s.t. x1 1 0.

6、8x1 + x2 1.6 x1 2 x2 1.4 x1 , x2 02022-5-69線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q 從以上兩例可以看出，其共同特征：從以上兩例可以看出，其共同特征：(1) 每一個(gè)線性規(guī)劃問題都用一組決策變量決策變量 表示某一方案，這組決策變量的值就代表一個(gè)具體方案，一般這些變量取值是非負(fù)且連續(xù)的；(2) 存在有關(guān)的數(shù)據(jù)，同決策變量構(gòu)成互不矛盾的約束條件約束條件，這些約束條件可以用一組線性等式或線性不等式來表示； (3) 存在一個(gè)要求達(dá)到的目標(biāo)，它可用決策變量及其有關(guān)的價(jià)值系數(shù)構(gòu)成的的線性函數(shù)(稱為目標(biāo)函數(shù)目標(biāo)函數(shù))來表示。按問題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大

7、化或最小化。 滿足以上三個(gè)條件的數(shù)學(xué)模型稱為線性規(guī)劃線性規(guī)劃的數(shù)學(xué)模型。nx,x ,x212022-5-610線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q線性規(guī)劃問題是線性規(guī)劃問題是在一組線性等式或不等式的約束之下，求一在一組線性等式或不等式的約束之下，求一個(gè)線性函數(shù)的最大值或最小值的問題。個(gè)線性函數(shù)的最大值或最小值的問題。q它由以下部分它由以下部分組成：組成： 目標(biāo)函數(shù)目標(biāo)函數(shù) max z 或或 min f 約束條件約束條件 s. t. (subject to) 滿足于滿足于 決策變量決策變量 用符號用符號 xj 等來表示可控制的因素。等來表示可控制的因素。2022-5-611線性規(guī)劃

8、問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q線性規(guī)劃模型的一般形式線性規(guī)劃模型的一般形式q目標(biāo)函數(shù)目標(biāo)函數(shù): max（min）z = c1 x1 + c2 x2 + + cn xn q約束條件約束條件： s. t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0 cj(j=1,2, ,n)稱為價(jià)值系數(shù)價(jià)值系數(shù)； aij稱為技術(shù)系數(shù)技術(shù)系數(shù)； bi稱為限額系限額系數(shù)數(shù)。2022-5-612線性規(guī)劃問題及

9、其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型1.2 圖解法圖解法q對于含有兩個(gè)決策變量含有兩個(gè)決策變量的線性規(guī)劃模型，可以利用圖解法(Graph Method)求解。q圖解法是解線性規(guī)劃的一種簡便、直觀的方法，對于理解線性規(guī)劃的基本概念和基本原理也是很有幫助的。q定義：定義：q可行解：可行解：滿足所有約束條件的向量稱為線性規(guī)劃問題的可行解。q可行域：可行域：全體可行解的集合稱為線性規(guī)劃問題的可行域。q最優(yōu)解：最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最優(yōu)值的可行解，稱為線性規(guī)劃的最優(yōu)解。2022-5-613線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型0124164223221212121x ,xxxxxxxzmaxq例

10、1中，所有約束條件作為半平面所圍成的范圍如圖中陰影部分所示。陰影部分中的每一個(gè)點(diǎn)(包括邊界點(diǎn))都是這個(gè)線性規(guī)劃問題的可行解。q對于例1，考察其約束條件所圍成的范圍，作圖如下：可行域可行域2022-5-614線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q考察目標(biāo)函數(shù) max z = 2 x1 + 3 x2q將目標(biāo)函數(shù)化為點(diǎn)斜式坐標(biāo)： x2=-(2/3) x1 +z/3表示一簇平行線33212zxx最優(yōu)解最優(yōu)解q由于在同一條直線上的所有點(diǎn)的目標(biāo)函數(shù)取同樣的值，故稱為等值線。2022-5-615q解聯(lián)立方程組: x1 + 2x2 = 8 4x1 = 16 q得最優(yōu)解為： x1 = 4， x2 =

11、 2， q記為: (x1 , x2)T =(4，2)T或者q最優(yōu)目標(biāo)值為： z = 14。 q以上最優(yōu)解和最優(yōu)值說明該廠的最優(yōu)生產(chǎn)計(jì)劃方案是：生以上最優(yōu)解和最優(yōu)值說明該廠的最優(yōu)生產(chǎn)計(jì)劃方案是：生產(chǎn)產(chǎn)4件產(chǎn)品件產(chǎn)品I，生產(chǎn)，生產(chǎn)2件產(chǎn)品件產(chǎn)品II，可得到最大利潤為，可得到最大利潤為14元。元。 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型1242xx 2022-5-616用圖解法求解線性規(guī)劃的基本步驟：用圖解法求解線性規(guī)劃的基本步驟：q畫可行域：畫可行域：分別取決策變量 x1 ，x2 為坐標(biāo)向量建立直角坐標(biāo)系。q化目標(biāo)函數(shù)等值線：化目標(biāo)函數(shù)等值線：對每個(gè)不等式(約束條件)，先取其等式在坐標(biāo)系

12、中作直線，然后確定不等式所決定的半平面。 若各半平面交出來的公共區(qū)域存在，顯然，其中的點(diǎn)滿足所有的約束條件，稱這樣的點(diǎn)為此線性規(guī)劃的可行解，全體可行解的集合稱為可行集或可行域。若這樣的公共區(qū)域不存在，則該線性規(guī)劃問題無可行解。q找最優(yōu)解：找最優(yōu)解：任意給定目標(biāo)函數(shù)一個(gè)確定的值，作出對應(yīng)的目標(biāo)函數(shù)等值線，并確定該族等值線平行移動時(shí)目標(biāo)函數(shù)值增加的方向。然后平移目標(biāo)函數(shù)的等值線，使其達(dá)到既與可行域有交點(diǎn)又不可能使值再增加的位置(有時(shí)交于無窮遠(yuǎn)處，此時(shí)稱無有限最優(yōu)解）。此時(shí)，目標(biāo)函數(shù)等值線與可行域的交點(diǎn)即此線性規(guī)劃的最優(yōu)解（一個(gè)或多個(gè)），此目標(biāo)函數(shù)的值即最優(yōu)值。線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及

13、其數(shù)學(xué)模型2022-5-617線性規(guī)劃問題的解可能出現(xiàn)的幾種情況：線性規(guī)劃問題的解可能出現(xiàn)的幾種情況：q有唯一的最優(yōu)解；有唯一的最優(yōu)解；q存在無窮多最優(yōu)解存在無窮多最優(yōu)解( (多重最優(yōu)解多重最優(yōu)解) )；線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型目標(biāo)函數(shù) max z=2 x1 +4 x2 q其最優(yōu)解為線段Q2Q3上的所有點(diǎn)，即(x1 , x2)T| x1 +2 x2=8，2 x1 42022-5-618q無界解：無界解：可行域無邊界，目標(biāo)函數(shù)值可增大(減小)到無窮大(無窮小)，實(shí)際上這類問題無最優(yōu)解；q無可行解。無可行解。線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型12121212m

14、ax242,0zxxxxxxx xq 在目標(biāo)函數(shù)等值線向右上方移動的過程中，上端無邊界，取不到最大值，即無界解。2022-5-619q無可行解：無可行解：當(dāng)存在矛盾的約束條件時(shí)，可行域?yàn)榭占?，無可行解，故無最優(yōu)解。q如果在例1的數(shù)學(xué)模型中增加一個(gè)約束條件: max z = 2 x1 + 3 x2線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q 可行域的交集為空集，故無可行解。85 . 121xx2022-5-620線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q注：注：q當(dāng)線性規(guī)劃問題的可行域非空時(shí)，它是有界的或無界的凸當(dāng)線性規(guī)劃問題的可行域非空時(shí)，它是有界的或無界的凸多邊形；多邊形；q若

15、線性規(guī)劃問題存在最優(yōu)解，則一定在有界可行域的某個(gè)若線性規(guī)劃問題存在最優(yōu)解，則一定在有界可行域的某個(gè)頂點(diǎn)得到；頂點(diǎn)得到；q若在兩個(gè)頂點(diǎn)同時(shí)得到最優(yōu)解，則它們連線上的任意一點(diǎn)若在兩個(gè)頂點(diǎn)同時(shí)得到最優(yōu)解，則它們連線上的任意一點(diǎn)都是最優(yōu)解，即有無窮多個(gè)最優(yōu)解。都是最優(yōu)解，即有無窮多個(gè)最優(yōu)解。2022-5-621線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型1.3 線性規(guī)劃問題的標(biāo)準(zhǔn)形式線性規(guī)劃問題的標(biāo)準(zhǔn)形式q以下形式的線性規(guī)劃模型稱為標(biāo)準(zhǔn)形以下形式的線性規(guī)劃模型稱為標(biāo)準(zhǔn)形(M1)：q目標(biāo)函數(shù)目標(biāo)函數(shù)： max z = c1 x1 + c2 x2 + + cn xn q 約束條件約束條件： s. t.

16、 a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn= bm x1 ，x2 ， ，xn 0.均為均為求最求最大值大值均為等均為等式約束式約束均為非負(fù)均為非負(fù)決策變量決策變量右端常數(shù)右端常數(shù)項(xiàng)項(xiàng)bi 02022-5-622線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個(gè)要求：線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個(gè)要求：q 目標(biāo)最大化目標(biāo)最大化q 約束方程為等式約束方程為等式q 決策變量為非負(fù)決策變量為非負(fù)q 右端項(xiàng)為非負(fù)右端項(xiàng)為非負(fù)2022-5-6

17、23線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型11max,1,2,0,1,2,njjjnijjijjzc xa xbimxjn目標(biāo)函數(shù)：約束條件：q線性規(guī)劃問題的幾種表示形式：線性規(guī)劃問題的幾種表示形式：qM1:qM1(向量和矩陣表示向量和矩陣表示):111122212max0,1,2,;1,2,njjjjjjnjmjnmzCXP xbxjnaxbaxbCc ccXPbjnaxb目標(biāo)函數(shù)：約束條件：2022-5-624線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型m ax.0zC XA XbX目 標(biāo) 函 數(shù) ：約 束 條 件 ：q線性規(guī)劃問題的幾種表示形式：線性規(guī)劃問題的幾種表示形式：

18、q矩陣表示矩陣表示:11112112112m12,;000,0,00(,);bb,;b,.nnmmnTnTmTnaaAP PPmnm naaCc ccb bbXxxx 系數(shù)矩陣：約束條件的維矩陣( )零向量：；目標(biāo)系數(shù)：價(jià)值向量資源向量：資源向量決策變量向量：2022-5-625線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)劃標(biāo)準(zhǔn)型的方法：q對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式:q1.極小化目標(biāo)函數(shù)的問題：極小化目標(biāo)函數(shù)的問題：q設(shè)目標(biāo)函數(shù)為設(shè)目標(biāo)函數(shù)為 min f = c1x1 + c2x2 + + cnxn (可以

19、可以)令令 z - f ， 則該極小化問題與下面的極大化問題有相同的最優(yōu)解，即則該極小化問題與下面的極大化問題有相同的最優(yōu)解，即 max z = - c1x1 - c2x2 - - cnxn 。 但必須注意，盡管以上兩個(gè)問題的最優(yōu)解相同，但他們最優(yōu)解但必須注意，盡管以上兩個(gè)問題的最優(yōu)解相同，但他們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號，即的目標(biāo)函數(shù)值卻相差一個(gè)符號，即 min f - max z 。2022-5-626線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)劃標(biāo)準(zhǔn)型的方法：q2. 約束條件不是等式的問題約束條件不是等式的問題： 設(shè)約束條件為設(shè)約束條件為 ai

20、1 x1 + ai2 x2 + + ain xn bi 可以引進(jìn)一個(gè)新的變量可以引進(jìn)一個(gè)新的變量 s ，使它等于約束右邊與左邊之差，使它等于約束右邊與左邊之差 s = bi (ai1 x1 + ai2 x2 + + ain xn ) 。 顯然，顯然，s 也具有非負(fù)約束，即也具有非負(fù)約束，即 s0 ，這時(shí)新的約束條件成為，這時(shí)新的約束條件成為 ai1 x1 + ai2 x2 + + ain xn + s = bi 。2022-5-627線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)劃標(biāo)準(zhǔn)型的方法：q2. 約束條件不是等式的問題約束條件不是等式的問題： 當(dāng)約束條

21、件為當(dāng)約束條件為 ai1 x1+ai2 x2+ +ain xn bi 時(shí)，類似地令時(shí)，類似地令 s = (ai1 x1+ai2 x2+ +ain xn) - bi 。 顯然，顯然，s 也具有非負(fù)約束，即也具有非負(fù)約束，即s0，這時(shí)新的約束條件成為，這時(shí)新的約束條件成為 ai1 x1+ai2 x2+ +ain xn - s = bi 。 2022-5-628線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)劃標(biāo)準(zhǔn)型的方法：q2. 約束條件不是等式的問題約束條件不是等式的問題：q為了使約束由不等式成為等式而引進(jìn)的變量為了使約束由不等式成為等式而引進(jìn)的變量s： q 當(dāng)

22、不等式為當(dāng)不等式為“小于等于小于等于”時(shí)稱為時(shí)稱為“松弛變量松弛變量”；q 當(dāng)不等式為當(dāng)不等式為“大于等于大于等于”時(shí)稱為時(shí)稱為“剩余變量剩余變量”；q 如果原問題中有若干個(gè)非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式如果原問題中有若干個(gè)非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，必須對各個(gè)約束引進(jìn)不同的變量，有時(shí)也將它們統(tǒng)稱為時(shí)，必須對各個(gè)約束引進(jìn)不同的變量，有時(shí)也將它們統(tǒng)稱為松弛變量松弛變量。 2022-5-629線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)劃標(biāo)準(zhǔn)型的方法：q2. 約束條件不是等式的問題約束條件不是等式的問題：q補(bǔ)例：補(bǔ)例：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式

23、將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式 min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 15.7 4.1 x1 + 3.3 x3 8.9 x1 + x2 + x3 = 38 x1，x2，x3 0 q解：首先解：首先, 將目標(biāo)函數(shù)轉(zhuǎn)換成極大化：令將目標(biāo)函數(shù)轉(zhuǎn)換成極大化：令 z = -f = -3.6x1 + 5.2x2 - 1.8x32022-5-630線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)劃標(biāo)準(zhǔn)型的方法：q2. 約束條件不是等式的問題約束條件不是等式的問題：q其次考慮約束，有其

24、次考慮約束，有 2 個(gè)不等式約束，引進(jìn)松弛變量個(gè)不等式約束，引進(jìn)松弛變量 x4，x5 0。于是，我們可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題：于是，我們可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題： max z = - 3.6 x1 + 5.2 x2 - 1.8 x3 s. t. 2.3x1 + 5.2x2- 6.1x3 + x4 = 15.7 4.1x1 + 3.3x3 - x5 = 8.9 x1 + x2 + x3 = 38 x1，x2，x3，x4，x5 0 。2022-5-631線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)劃標(biāo)準(zhǔn)型的方法：q3. 變量無符號限制的問題

25、變量無符號限制的問題： 在標(biāo)準(zhǔn)形式中，必須每一個(gè)變量均有非負(fù)約束。當(dāng)某一個(gè)變在標(biāo)準(zhǔn)形式中，必須每一個(gè)變量均有非負(fù)約束。當(dāng)某一個(gè)變量量 xj 沒有非負(fù)約束時(shí)，可以令沒有非負(fù)約束時(shí)，可以令 xj = xj - xj” 其中其中 xj0， xj”0q即用兩個(gè)非負(fù)變量之差來表示一個(gè)無符號限制的變量，當(dāng)然即用兩個(gè)非負(fù)變量之差來表示一個(gè)無符號限制的變量，當(dāng)然 xj 的符號取決于的符號取決于xj 和和 xj” 的大小的大小。2022-5-632線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)劃標(biāo)準(zhǔn)型的方法：q4.右端項(xiàng)有負(fù)值的問題：右端項(xiàng)有負(fù)值的問題： 在標(biāo)準(zhǔn)形式中，要求右

26、端項(xiàng)必須每一個(gè)分量非負(fù)。當(dāng)某一個(gè)在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一個(gè)分量非負(fù)。當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí)，如右端項(xiàng)系數(shù)為負(fù)時(shí)，如 bi0，則把該等式約束兩端同時(shí)乘以，則把該等式約束兩端同時(shí)乘以-1，得到：，得到： - ai1 x1 - ai2 x2 - - ain xn = -bi 2022-5-633線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)劃標(biāo)準(zhǔn)型的方法：q補(bǔ)例補(bǔ)例 將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式 min f = -3 x1 + 5 x2 + 8 x3 - 7 x4 s. t. 2 x1 - 3 x2 + 5 x3 +

27、6 x4 28 4 x1 + 2 x2 + 3 x3 - 9 x4 39 6 x2 + 2 x3 + 3 x4 - 58 x1，x3，x4 02022-5-634線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)劃標(biāo)準(zhǔn)型的方法：q解：首先，解：首先，將目標(biāo)函數(shù)轉(zhuǎn)換成極大化將目標(biāo)函數(shù)轉(zhuǎn)換成極大化： 令令 z = -f = 3x15x28x3+7x4 ；q其次考慮約束，有其次考慮約束，有 3 個(gè)不等式約束，引進(jìn)個(gè)不等式約束，引進(jìn) 2 個(gè)松弛變量和個(gè)松弛變量和 1 個(gè)個(gè)剩余變量剩余變量 x5 , x6 , x7 0 ；q由于由于 x2 無非負(fù)限制，無非負(fù)限制，引入兩個(gè)

28、非負(fù)變量引入兩個(gè)非負(fù)變量，可令，可令 x2= x2- x2”, 其中其中 x20，x2”0 ；q由于第由于第 3 個(gè)約束右端項(xiàng)系數(shù)為個(gè)約束右端項(xiàng)系數(shù)為 -58，于是，于是把該式兩端乘以把該式兩端乘以 -1 。q于是，我們可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題：于是，我們可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題：2022-5-635線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)劃標(biāo)準(zhǔn)型的方法：qmax z = 3x1 5x2 + 5x2” 8x3 + 7x4 s. t. 2x1 3x2 + 3x2” + 5x3 + 6x4 + x5 = 28 4x1 + 2x2 - 2

29、x2” + 3x3 - 9x4 - x6 = 39 -6x2+ 6x2” - 2x3 - 3x4 - x7 = 5 x1，x2，x2”，x3，x4，x5，x6，x7 0 2022-5-636線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q課堂練習(xí)：課堂練習(xí)： 某公司由于生產(chǎn)需要，共需要某公司由于生產(chǎn)需要，共需要 A，B 兩種原料至少兩種原料至少 350 噸噸 ( A, B 兩種材料有一定替代性兩種材料有一定替代性)，其中，其中 A 原料至少購進(jìn)原料至少購進(jìn) 125 噸。但噸。但由于由于 A，B 兩種原料的規(guī)格不同，各自所需的加工時(shí)間也是不兩種原料的規(guī)格不同，各自所需的加工時(shí)間也是不同的，加工

30、每噸同的，加工每噸 A 原料需要原料需要 2 個(gè)小時(shí)，加工每噸個(gè)小時(shí)，加工每噸 B 原料需要原料需要 1 小時(shí)，而公司總共有小時(shí)，而公司總共有 600 個(gè)加工小時(shí)。又知道每噸個(gè)加工小時(shí)。又知道每噸 A 原料的原料的價(jià)格為價(jià)格為 2 萬元，每噸萬元，每噸 B 原料的價(jià)格為原料的價(jià)格為 3 萬元，試問在滿足生萬元，試問在滿足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購買產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購買 A，B 兩種原料，使得購進(jìn)成本最低？兩種原料，使得購進(jìn)成本最低？2022-5-637線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型AB總總 量量加工時(shí)間加工時(shí)間21600原料單

31、價(jià)原料單價(jià)23所需原料數(shù)所需原料數(shù)x1125x2350q求使購進(jìn)成本最低的求使購進(jìn)成本最低的 x1 和 x2。q解：解：問題的線性規(guī)劃模型為問題的線性規(guī)劃模型為 目標(biāo)函數(shù)：目標(biāo)函數(shù)： min f = 2 x1+3 x2 約束條件：約束條件： x1+ x2 350 x1 125 2 x1+ x2 600 x1 0 ， x2 0 。2022-5-638線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q用圖解法解此題。用圖解法解此題。x1x2600600100100300300 x1 =1252 x1+ x2 = 600 x1+ x2 =350解線性方程組解線性方程組 x1+ x2 =350 2 x

32、1+ x2 = 600得最優(yōu)解得最優(yōu)解 x1 = 250 x2 = 100最優(yōu)值最優(yōu)值 f = 800可行域可行域2022-5-639線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型q此例此例 的線性規(guī)劃標(biāo)準(zhǔn)型為的線性規(guī)劃標(biāo)準(zhǔn)型為 目標(biāo)函數(shù)：目標(biāo)函數(shù)： max z = -2 x1 - 3 x2 - 0s1 - 0s2- 0s3 約束條件：約束條件： x1+ x2 s1 =350 x1 s2 = 125 2 x1+ x2 + s3 = 600 x1 ， x2 ，s1， s2，s3 0 。約束條件約束條件松弛變量及剩余變量的值松弛變量及剩余變量的值原料 A 與原料 B 的總量s1= 0 原料 A 的數(shù)量s2 =125加工時(shí)間s3 = 02022-5-640線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及