線性規(guī)劃與單純形法

1、1、 選擇填空1. 2. 3. 4. 5. 6. 7. 8. 9. 10.2、 判斷正誤1. 2. 3. 4. 5. 6. 7. 8. 9. 10.3、 將下列問題化為標準型1.解 令，在約束1中引入非負的松弛變量，約束2兩邊同乘以-1。整理得： 即：2. Min Z=-x1+5x2-2x3s.t. x1 +x2 - x3 6 2x1 - x2 +3x3 5 x1 + x2 = 10 x1 0, x2 0, x3符號不限解 首先，令對變量x3進行處理，令x3 = x3- x4;再令x2 = - x2。然后對目標函數(shù)和約束條件進行標準化。 Max Z=x1+5x2+2x3-2x4s.t. x1

2、- x2 - x3+x4+x5 = 6 2x1 + x2 +3x3 - 3x4 -x6 = 5 x1 - x2 = 10 x1, x2, x3, x4, x5, x6 04、 用圖解法求解下列線性規(guī)1. min Z= - x1+2x2s.t. x1 - x2 -2 x1 +2x2 6 x1, x2 0E-2 -1 0 1 2 3 4 5 6 7 8 x1x2 6 5 4 3 2 1 x1 - x2 -2x1 +2x2 6解 畫圖如下：根據(jù)上圖，最優(yōu)解為X*=（x1, x2）T =（6, 0）T，最優(yōu)值為-6。2.Max Z= - x1+2x2s.t. x1 - x2 -2 x1 +2x2 6

3、x1, x2 0E-2 -1 0 1 2 3 4 5 6 7 8 x1x2 6 5 4 3 2 1 x1 - x2 -2x1 +2x2 6解 畫圖如下：根據(jù)上圖，最優(yōu)解為，最優(yōu)值為。5、 用單純形法求解下列線性規(guī)劃1. Max Z=3x1+5x2s.t. x1 4 2x2 12 3x1 +2x2 18 x1, x2 0解 首先，標準化后線性規(guī)劃如下：（1）Max Z=3x1+5x2+0x3+0x4+0x5s.t. x1 + x3 = 4 2x2 + x4 = 12 3x1 +2x2 + x5 = 18 x1, x2, x3, x4, x5, x6 0再用表格單純形法求解如下：（一、按照第一個正

4、檢驗數(shù)對應(yīng)非基變量進基的方法）CBXBcjb xj3 5 0 0 0x1 x2 x3 x4 x5j000x3 x4 x5412181 0 1 0 00 2 0 1 03 2 0 0 14/118/3-Z03 5 0 0 0 300x1 x4 x541261 0 1 0 00 2 0 1 00 2 -3 0 1 12/2 6/2-Z-12 0 5 -3 0 0305x1 x4 x24631 0 1 0 00 0 3 1 -10 1 -3/2 0 1/2 4/1 6/3-Z-27 0 0 9/2 0 -5/2305x1 x3 x22261 0 0 -1/3 1/30 0 1 1/3 -1/30 1

5、 0 1/2 0-Z-36 0 0 0 -3/2 -1（二、按照最大正檢驗數(shù)對應(yīng)非基變量進基的方法）CBXBcjb xj3 5 0 0 0x1 x2 x3 x4 x5j000x3 x4 x5412181 0 1 0 00 2 0 1 03 2 0 0 112/218/2-Z03 5 0 0 0 050x3 x2 x54661 0 1 0 00 1 0 1/2 03 0 0 -1 1 4/1 6/3-Z-12 3 0 0 -5/2 0053x3 x2 x12620 0 1 1/3 -1/30 1 0 1/2 01 0 0 -1/3 1/3 -Z-36 0 0 -3 -3/2 -1因此，最優(yōu)解為X

6、* =（2, 6, 2, 0, 0）T，最優(yōu)值為Zmax=36。2. Max Z=2x1- x2+x3s.t. 3x1+x2+x3 60 x1-x2+2x3 10 x1 +x2-x3 20 x1, x2, x3 0解 首先，標準化后線性規(guī)劃如下：（1）Max Z=2x1-x2+x3s.t. 3x1+x2+x3+x4 = 60 x1-x2+2x3+x5 = 10 x1 +x2-x3 +x6 = 20 x1, x2, x3, x4, x5, x6 0再用表格單純形法求解如下：CBXBcjb xj2 -1 1 0 0 0x1 x2 x3 x4 x5 x6j000x4 x5 x66010203 1 1

7、 1 0 01 -1 2 0 1 01 1 -1 0 0 160/310/120/1-Z02 -1 1 0 0 0 020x4 x1 x63010100 4 -5 1 -3 01 -1 2 0 1 00 2 -3 0 -1 1 30/4 10/2-Z-200 1 -3 0 -2 002-1x4 x1 x2101550 0 1 1 -1 -21 0 1/2 0 1/2 1/20 1 -3/2 0 -1/2 1/2-Z-250 0 -3/2 0 -3/2 -1/2因此，最優(yōu)解為X* =（15, 5, 0, 10, 0, 0）T，最優(yōu)值為Zmax=25。6、 表格單純形法計算題1. （2）初始線性規(guī)

8、劃模型如下：Max Z=5x1+20x2+25x3s.t. 2x1+x2 40 2x2+x3 30 3x1 -1/2x3 15 x1, x2, x3 0（3）用單純形法求出最優(yōu)解及相應(yīng)的最優(yōu)值。解（按照最大檢驗數(shù)對應(yīng)非基變量進基的方法）CBXBcjb xj5 20 25 0 0 0x1 x2 x3 x4 x5 x6j000x4 x5 x64030152 1 0 1 0 00 2 1 0 1 03 0 -1/2 0 0 130/1-Z05 20 25 0 0 0 0250x4 x3 x64030302 1 0 1 0 00 2 1 0 1 03 1 0 0 1/2 1 40/230/3-Z-75

9、05 -30 0 0 -25 00255x4 x3 x12030100 1/3 0 1 -1/3 -2/30 2 1 0 1 01 1/3 0 0 1/6 1/3-Z-8000 -95/3 0 0 -155/6 -5/37、 用大M法和兩階段法求解下列線性規(guī)劃1. min Z= x1+2x2s.t. -x1 +2x2 2 x1 3 x1, x2 0解 標準化并引入人工變量x5后，線性規(guī)劃模型如下：Max Z=-x1-2x2-Mx5s.t. -x1+2x2 -x3 +x5 = 2 x1 +x4 = 3x1, x2, x3, x4, x5 0用大M法求解如下：CBXBcjb xj-1 -2 0 0

10、 -M x1 x2 x3 x4 x5 j-M 0x5 x4 23-1 2 -1 0 1 1 0 0 1 0 2/2-Z2M-1-M -2+M -M 0 0 -2 0x2 x4 13-1/2 1 -1/2 0 1/2 1 0 0 1 0 -Z2 -2 0 -1 0 1-M從表中可以看出，最優(yōu)解X* =（0, 1, 0, 3）T，最優(yōu)值為Zmax=-2。因此，原問題最優(yōu)解X* =（0, 1, 0, 3）T，最優(yōu)值為Zmin=2。用兩階段法求解如下：第一階段：標準化并引入人工變量x5，對人工變量進行優(yōu)化線性規(guī)劃模型如下：Max W=-x5s.t. -x1+2x2 -x3 +x5 = 2 x1 +x4

11、 = 3 x1, x2, x3, x4, x5 0CBXBcjb xj0 0 0 0 -1 x1 x2 x3 x4 x5 j-1 0x5 x4 23-1 2 -1 0 1 1 0 0 1 0 2/2-W2-1 2 -1 0 0 0 0x2 x4 13-1/2 1 -1/2 0 1/2 1 0 0 1 0 -Z0 0 0 0 0 -1由于人工變量x5=0，故可以劃去該列，以x2， x4為基變量進行第二階段的計算。第二階段：Max Z=-x1-2x2s.t. -1/2x1+x2 -1/2x3 = 1 x1 +x4 = 3 x1, x2, x3, x4 0由于上表中所有非基變量的檢驗數(shù)小于等于0，因

12、此，原問題已經(jīng)達到最優(yōu)解，即X* =（0, 1, 0, 3）T，最優(yōu)值為Zmin=2。2. Max Z=x1+2x2+3x3-x4s.t. x1+2x2+3x3 = 15 2x1+x2+5x3 = 20 x1 +2x2+x3+x4 = 10 x1, x2, x3, x4 0解 首先，標準化并引入人工變量x5, x6后,線性規(guī)劃如下：（1）Max Z=x1+2x2+3x3-x4-Mx5-Mx6s.t. x1+2x2+3x3+x5 = 15 2x1+x2+5x3+x6 = 20 x1 +2x2+x3+x4 = 10 x1, x2, x3, x4 0用大M法求解如下：CBXBcjb xj1 2 3

13、-1 -M -Mx1 x2 x3 x4 x5 x6 j-M -M-1x5 x6x4 1520101 2 3 0 1 0 2 1 5 0 0 1 1 2 1 1 0 0 15/320/510/1-Z35M+102+3M 4+3M 4+8M 0 0 0 -M 3-1x5 x3x4 346-1/5 7/5 0 0 1 -3/5 2/5 1/5 1 0 0 1/5 3/5 9/5 0 1 0 -1/5 15/720/130/9-Z3M-62/5-M/5 0 0 0 16/5+7M/5 -4/5-8M/52 3-1x2 x3 x415/725/715/7-1/7 1 0 0 5/7 -3/7 3/7 0

14、 1 0 -1/7 2/7 6/7 0 0 1 -9/7 4/7 25/315/6-Z-90/76/7 0 0 0 231x2 x3 x15/25/25/20 1 0 1/6 1/2 -1/3 0 0 1 -1/2 1/2 0 1 0 0 7/6 -3/2 2/3 -Z-150 0 0 -1 -M-1 -M從表中可以看出，最優(yōu)解X* =（5/2, 5/2, 5/2, 0, 0, 0）T，最優(yōu)值為Zmax=15。用兩階段法求解如下： Min W=x5+x6CBXBcjb xj0 0 0 0 1 1x1 x2 x3 x4 x5 x6 j1 10x5 x6x4 1520101 2 3 0 1 0 2

15、 1 5 0 0 1 1 2 1 1 0 0 15/320/510/1-W-35 -3 -3 -8 0 0 0 1 00x5 x3x4 346-1/5 7/5 0 0 1 -3/5 2/5 1/5 1 0 0 1/5 3/5 9/5 0 1 0 -1/5 15/720/130/9-W-3 1/5 -7/5 0 0 0 8/5000x2 x3 x415/725/715/7-1/7 1 0 0 5/7 -3/7 3/7 0 1 0 -1/7 2/7 6/7 0 0 1 -9/7 4/7 25/315/6-W00 0 0 0 1 1從表中可以看出，第一階段的最優(yōu)解X* =（0, 15/7, 25/7

16、, 15/7, 0, 0）T，最優(yōu)值為Wmin=0。轉(zhuǎn)入第二階段求解如下：CBXBcjb xj1 2 3 -1 x1 x2 x3 x4 j2 3-1x2 x3 x415/725/715/7-1/7 1 0 0 3/7 0 1 0 6/7 0 0 1 25/315/6-Z-90/76/7 0 0 0 2 31x2 x3 x15/25/25/20 1 0 1/6 0 0 1 -1/2 1 0 0 7/6 -Z-150 0 0 -1 s.t.3. Max Z=3x1- x2-x3 x1-2x2+x3 11 -4x1+x2+2x3 3 -2x1 +x3 = 1 x1, x2, x3 0解 首先，標準化

17、并引入人工變量x6, x7后,線性規(guī)劃如下：Max Z=3x1-x2-x3-Mx6-Mx7 s.t. x1-2x2+x3 +x4 = 11 -4x1+x2+2x3 -x5+x6 = 3 -2x1 +x3+x7 = 1 x1, x2, x3, x4, x5, x6, x7 0用大M法求解如下：CBXBcjb xj3 -1 -1 0 0 -M -Mx1 x2 x3 x4 x5 x6 x7j0 -M-Mx4 x6 x711311 -2 1 1 0 0 0-4 1 2 0 -1 1 0-2 0 1 0 0 0 1 3/1-Z4M3-6M M-1 3M-1 0 -M 0 0 0 -1-Mx4 x2 x7

18、1731-7 0 5 1 -2 2 0-4 1 2 0 -1 1 0-2 0 1 0 0 0 117/53/21/1-Z3+M-1-2M 0 M+1 0 -1 1-M 00 -1-1x4 x2 x312113 0 0 1 -2 2 -50 1 0 0 -1 1 -2-2 0 1 0 0 0 1 12/3-Z2 1 0 0 0 -1 1-M -1-M3 -1-1x1 x2 x34191 0 0 1/3 -2/3 2/3 -5/30 1 0 0 -1 1 -20 0 1 2/3 -4/3 4/3 -7/3-Z-2 0 0 0 -1/3 -1/3 1/3-M 2/3-M從表中可以看出，最優(yōu)解X* =

19、（4, 1,9, 0, 0, 0, 0）T，最優(yōu)值為Zmax=2。用兩階段法求解如下： Min W=x6+x7CBXBcjb xj0 0 0 0 0 1 1x1 x2 x3 x4 x5 x6 x7j0 11x4 x6 x711311 -2 1 1 0 0 0-4 1 2 0 -1 1 0-2 0 1 0 0 0 1 3/1-W-46 -1 -3 0 1 0 0 0 01x4 x2 x71731-7 0 5 1 -2 2 0-4 1 2 0 -1 1 0-2 0 1 0 0 0 117/53/21/1-W-12 0 -1 0 0 1 00 00x4 x2 x312113 0 0 1 -2 2 -

20、50 1 0 0 -1 1 -2-2 0 1 0 0 0 1 -W0 0 0 0 0 0 1 1從表中可以看出，第一階段的最優(yōu)解X* =（0, 1, 1, 12, 0, 0, 0）T，最優(yōu)值為Wmin=0。轉(zhuǎn)入第二階段求解如下：CBXBcjb xj3 -1 -1 0 0 x1 x2 x3 x4 x5 j0 -1-1x4 x2 x312113 0 0 1 -2 0 1 0 0 -1 -2 0 1 0 0 12/3-Z-41 0 0 0 -1 3 -1-1x1 x2 x34191 0 0 1/3 -2/30 1 0 0 -10 0 1 2/3 -4/3-Z-20 0 0 -1/3 -1/3從表中可

21、以看出，最優(yōu)解X* =（4, 1,9, 0, 0, 0, 0）T，最優(yōu)值為Zmax=2。8、 線性規(guī)劃建模1. 某商店制定一種商品的712月進貨與銷售計劃。由于商店倉庫容量的限制，存貨不能超過500件。6月底已存貨100件，以后每月1日進貨一次。假設(shè)各月份該種商品買進及銷售單價如下表所示，問各月應(yīng)進貨、銷售各多少，才能是總收入最多？試列出線性規(guī)劃模型。月份7月8月9月10月11月12月買進單價元282425272323銷售單價元292426282225解設(shè)7-12月份進貨量分別為x11, x21, x31, x41, x51, x61; 銷售量分別為x12, x22, x32, x42, x5

22、2, x62。則最大化目標函數(shù)可以表示為各個月的銷售總收入與各個月進貨總成本的差額。而約束條件包括兩方面：月初庫存量、月末庫存量約束，庫存要求介于0，500區(qū)間，因此，模型構(gòu)造如下：Max Z =（29x12+24x22+26x32+28x42+22x52+25x62）-（28x11+24x21+25x31+27x41+23x51+23x61） s.t.x11 500-100 (或者400)100+x11-x12 0 (或者x12 100+ x11)x21 500-（100+x11-x12）100+x11-x12+x21-x22 0x31 500-（100+x11-x12+x21-x22）10

23、0+x11-x12+x21-x22+x31-x32 0x41 500-（100+x11-x12+x21-x22+x31-x32）100+x11-x12+x21-x22+x31-x32+x41-x42 0x51 500-（100+x11-x12+x21-x22+x31-x32+x41-x42）100+x11-x12+x21-x22+x31-x32+x41-x42+x51-x52 0x61 500-（100+x11-x12+x21-x22+x31-x32+x41-x42+x51-x52）100+x11-x12+x21-x22+x31-x32+x41-x42+x51-x52+x61-x62 0x11

24、, x21, x31, x41, x51, x61, x12, x22, x32, x42, x52, x62 03. 某廠生產(chǎn)A、B、C 三種產(chǎn)品，每種產(chǎn)品都要經(jīng)過甲、乙兩道工序。設(shè)該廠有兩種規(guī)格的設(shè)備，甲1和甲2可以完成甲工序；有3種規(guī)格的設(shè)備乙1、乙2、乙3能完成乙工序。每種設(shè)備完成每個產(chǎn)品的加工工時、每小時的費用以及每件產(chǎn)品的原料費用和銷售價格如表1.12所示，其中空缺位置表示該設(shè)備不能加工該種產(chǎn)品，要求安排最優(yōu)生產(chǎn)計劃，使該廠利潤最大。工序設(shè)備產(chǎn)品設(shè)備有效臺時設(shè)備加工費（元小時）ABC甲甲148050000.1甲2379110000.05乙乙106230000.08乙25056000

25、0.12乙363040000.07原料費（元件）0.30.50.8單價（元件）1.52.54甲1甲2乙1乙2乙3解：（1）決策變量：設(shè)A產(chǎn)品經(jīng)過甲乙兩道工序（5種規(guī)格）加工的產(chǎn)品數(shù)分別為；B產(chǎn)品經(jīng)過甲乙兩道工序（5種規(guī)格）加工的產(chǎn)品數(shù)分別為；C產(chǎn)品經(jīng)過甲乙兩道工序（5種規(guī)格）加工的產(chǎn)品數(shù)分別為；（2）目標函數(shù)：總利潤收益工時成本C1材料成本C2收益A產(chǎn)品數(shù)×單價B產(chǎn)品數(shù)×單價C產(chǎn)品數(shù)×單價 C1+C2(3)工時約束： （4）工序流程約束：甲工序加工的產(chǎn)品數(shù)乙工序加工的產(chǎn)品數(shù)（A、B、C） 則線性規(guī)劃模型為：9、 研究討論題第1章 常見錯誤總結(jié)：（1）表格單純形法簡便易行，但卻不習(xí)慣用。雖然思路十分明確，但還是不方便。單純形表格可以求最優(yōu)解，也可以進行敏感性分析。最優(yōu)表中有許多有用的信