1、第三節(jié)第三節(jié) 線性規(guī)劃的標(biāo)準(zhǔn)形式線性規(guī)劃的標(biāo)準(zhǔn)形式n為什么要轉(zhuǎn)化為標(biāo)準(zhǔn)形式？為什么要轉(zhuǎn)化為標(biāo)準(zhǔn)形式？n標(biāo)準(zhǔn)形式的特點(diǎn)：標(biāo)準(zhǔn)形式的特點(diǎn)：n1、目標(biāo)函數(shù)求最大值（max）；（不一定）n2、所有的約束條件均由等式表示（=）；n3、所有的決策變量限于非負(fù)值（xj0）；n4、每一個(gè)約束條件等式的右端常數(shù)均為非負(fù)值（bi0)。 （不一定） 數(shù)學(xué)模型如下 0,.max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcS改造方法（改造方法（1）n、若目標(biāo)函數(shù)求最小值，則在函數(shù)式前加上“”號(hào)，轉(zhuǎn)化為求最大值。轉(zhuǎn)化后目標(biāo)函

2、數(shù)的最優(yōu)解不變，最優(yōu)值差一個(gè)符號(hào)最優(yōu)解不變，最優(yōu)值差一個(gè)符號(hào)。n例：jjxcFminjjxcFSminmax改造方法（改造方法（2）n2、若約束條件中，某些常數(shù)項(xiàng)bi為負(fù)數(shù)，則可先在約束條件等式或不等式兩邊乘上“-1”，使得bi0。n例： 3jijxa3jijxa改造方法（改造方法（3）n3、若約束條件不等式符號(hào)為“”，則在不等式左邊加上一個(gè)非負(fù)變量（稱為松弛變量松弛變量），把不等式改為等式。n例：ijijbxaimmjjijbxxa11新設(shè)一個(gè)非負(fù)變量改造方法（改造方法（4）n4、若約束條件不等式符號(hào)為“”，則在不等式左邊減去一個(gè)非負(fù)變量（稱為剩余變量剩余變量），不等式改為等式。n例：iji

3、jbxaimmjjijbxxa11新設(shè)一個(gè)非負(fù)變量改造方法（改造方法（5）n5、若約束條件中，某些決策變量沒有非負(fù)要求：nxj0，則令新變量xj=-xj；nxj無符號(hào)限制，則可增設(shè)兩個(gè)非負(fù)變量Vk0,Uk0，令原變量Xk=Vk-Uk，代入原線性規(guī)劃問題的目標(biāo)函數(shù)及約束條件。例1無符號(hào)限制43214321432143214321,0,0,02232142224.5243minxxxxxxxxxxxxxxxxtsxxxxF步驟1：min max43215243minxxxxF43215243minmaxxxxxFS步驟2：bi02244321xxxx2244321xxxx步驟3：“” “=“n引入

4、新變量(松弛變量）x50，將約束條件不等式變?yōu)榈仁健?424321xxxx14254321xxxxx+ 松弛變量松弛變量步驟4： “” “=”n引入新變量（剩余變量）x60，將約束條件不等式變?yōu)榈仁健?2324321xxxx223264321xxxxx 剩余變量剩余變量步驟5：滿足變量非負(fù)條件n設(shè)新變量x70，令x7=-x2，帶入目標(biāo)函數(shù)和約束條件中。n設(shè)兩個(gè)新變量x80， x90， 令x4=x8-x9，帶入目標(biāo)函數(shù)和約束條件中。 整理得整理得：整理后數(shù)學(xué)模型為：9 , 8 , 7 , 6 , 5 , 3 , 1, 022232142224. .0055243max69837159837198

5、3716598371jxxxxxxxxxxxxxxxxxxtsxxxxxxxSj松弛變量與剩余變量松弛變量與剩余變量n概念：n松弛變量：在線性規(guī)劃模型中，如果約束條件為“”，則在不等式左邊加入一個(gè)非負(fù)變量，這個(gè)非負(fù)變量成為松弛變量。n剩余變量：在線性規(guī)劃模型中，如果約束條件為“”，則在不等式左邊減去一個(gè)非負(fù)變量，這個(gè)非負(fù)變量成為剩余變量。理解松弛變量的實(shí)際含義n例：某工廠在計(jì)劃期內(nèi)要安排甲、乙兩種產(chǎn)品的生產(chǎn)。生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗以及資源的限制如下表：n工廠每生產(chǎn)一單位甲產(chǎn)品可獲利50元，每生產(chǎn)一單位乙產(chǎn)品可獲利100元，問工廠應(yīng)分別生產(chǎn)多少單位產(chǎn)品甲和產(chǎn)品乙才能使

6、得獲利最多？甲產(chǎn)品乙產(chǎn)品資源限制設(shè)備11300臺(tái)時(shí)原料A21400kg原料B01250kg建立數(shù)學(xué)模型：n設(shè)甲、乙兩種產(chǎn)品的產(chǎn)量分別為x1、x2：0,02504002300.10050max212212121xxxxxxxtsxxFDBC圖解法30021 xx400221 xx2502x10020030040010020030040001005021xxOA可行解域?yàn)镺ABCD最優(yōu)解為B點(diǎn)（50，250）最優(yōu)解的解釋n最優(yōu)解x1=50，x2=250表示甲產(chǎn)品生產(chǎn)50個(gè)單位，乙產(chǎn)品生產(chǎn)250個(gè)單位時(shí)，獲利最大。n此時(shí)，資源利用情況資源利用情況為（代入約束條件）：n設(shè)備臺(tái)時(shí)利用量=1*50+1*2

7、50=300=資源限制量n原料A使用量=2*50+1*250=350最低要求125n原料加工時(shí)數(shù)=2*250+100=600=最高限制n進(jìn)一步計(jì)算剩余變量和松弛變量:nX3=0，表示正好達(dá)到最低要求；nX4=125，表示超出最低要求，多購進(jìn)125噸；nX5=0，表示工時(shí)數(shù)被全部利用。n關(guān)于松弛變量和剩余變量的信息也可以從圖解法中獲得。另外，DBC松弛變量x3=0,x4=50,x5=030021 xx400221 xx2502x10020030040010020030040001005021xxOA可行解域?yàn)镺ABCD最優(yōu)解為B點(diǎn)（50，250）132松弛變量x3=0,x4=50,x5=0n最優(yōu)解在B點(diǎn)。B點(diǎn)是第1、第3個(gè)約束條件對(duì)應(yīng)的直線的交點(diǎn)，所以第1、第3個(gè)約束條件加入的松弛變量為0，而第2個(gè)約束條件加入的松弛變量不為0（與B點(diǎn)還有一點(diǎn)距離）。剩余變量X3=0,X4=125，松弛變X5=035021 xx1251x600221 xx10020030040050060010020030040050003221 xxBAC可行解域?yàn)锳BC最優(yōu)解為C點(diǎn)（250，100）12