1、冶金實驗基礎優化設計-線性規劃一、線性規劃1、基本概念 1、 變量-基本參數 2 、約束-對變量取值的限制 3、目標函數方案優劣的標準函數 2、線性規劃的數學模型 例1 產品 煤 電力 工作日 利潤 A 9t 4kw 3 7(千元) B 5t 5kw 10 12(千元) 條件限制 煤共有 360 t 電力 200 kw 工作日 300 個 A、 B兩種產品各生產多少噸獲利最大? 用 X1A產品的生產數(變量) x2B產品的生產數(變量) f 目標函數(利潤) 則 maxf=7x1+12x2 st. 9x1+5x2=360 4x1+5x2=200 3x1+10 x2=0; x2=0例2 兩個煤廠

2、 A1 -產煤量60 t/月 A2-產煤量100t/月 供應3個用煤區 B1-需求量50t/月 B2-需求量70t/月 B3-需求量40t/月 距離 B1 10km B1 4km A1 B2 5km A2 B2 8km B3 6km B3 12km 問題:如何分配用煤量使得運輸量(即t.km)達到最小? 決策變量xij x- 煤量 i=1,2 - 煤廠 j=1,2,3 -用煤區 運輸量-f 目標函數 則: minf=10 x11+5x12+6x13+4x21+8x22+12x23 滿足供求平衡 x11+x12+x13=60 （A1-煤量） x21+x22+x23=100 需求平衡 x11+x2

3、1=50 x12+x22=70 x13+x23=40 xij=0 i=1,2 ;j=1,2,3 化鐵爐熔煉鑄鐵配料的最優化問題材料cSiMnCr價格變量生鐵4.22.250.8058X1高硅鐵015.04.510.0120X2硅鐵1#045.000128X3硅鐵2#042.000120X4母合金1#018.0600200X5母合金2#030.09.020.0260X6母合金3#025.033.08.0238X7碳化硅1530.000160X8廢鋼1#0.400.9039X9廢鋼2#0.100.3030X10廢鋼3#0.100.3033x11約束條件為：3.2C%3.5, 2.7Si%3.0 ,

4、 1.4Mn1.60.3Mn0.45 , SiC0.01噸，廢鋼1#0.3噸廢鋼2#0.3噸，廢鋼3#0.3噸，廢鋼總量0.3噸裝料總質量為1噸要求在滿足上述約束條件的情況下，使每噸裝入料的成本為最低。線性規劃問題的數學模型歸納為:Max(Min)Z=C1X1+C2X2+.+CnXn s.t. 11x11+12X12 1nX1n=）b1 21X21+22X222nX2n=）b2 m1Xm1+m2Xm2mnXmn =) bm Xi=0 i =1, 2 , . , n用矩陣表示為: Max. Z =CX約束 AX=B X=0 其中 mnm2m12n22211n1211a . a a . . . a

5、 a aa . a aA X=x1 x2 . xnT B=b1b2 . bmT C=c1c2 . cnT 一般的線性規劃問題轉化為標準形式 1.約束條件的標準化- 松弛變量法 假設約束條件有不等式約束 ai1x1+ . +ailXl =bj 引入非負變量 X l+1, X l+2 則以上兩不等式與下邊兩式等價等 ai1X1+ . +ailXl+ Xl+1 = bi Xl+1 = 0 aj1X1+ . +ajlxjl -Xl+2 =bj Xl+2 =0 2. 自由變量的標準化 標準形中要求每個決策變量均為非負數、即所有變量大于零。 在線性規劃問題中，若部分變量沒有非負數得限制，稱這類決策變量為自

6、由變量。 若 Xs 為自由變量 引入變量Xs =0; Xs=0 用 Xs = Xs - X 代換 自由變量Xs轉化為非負數限制的變量Xs 、Xs。 3.目標函數的標準化 max f (x1,x2, xn)= - min- f (x1,x2, xn) 線性規化問題的圖解法圖解法的步驟: 1. 確定滿足各約束的點域 2. 找出可行域 3. 觀察目標函數的變化 4.求解, 確定最優值x1=3x1+2x2=fx2 - x1=2例 1 min f = x1 + 2X2 . ，= 約束條件滿足的區域 D 目標函數 f=x1+2x2 f 值由大變小，取得最優解 f=1x1+x2=113x1x2例2 maxf

7、=7x1+12x2 s.t. 9x1+5x2=360 l1 4x1+5x2=200 l2 3x1+10 x2=0,x2=0 7x1+12x2=fx1x2111213目標函數的等值線向右上方移動時, 其值增大; 最優解為: x1=20 ; x2=24 maxf=7*20+12*24=428單純形法 基本思想： 根據線性規化的標準形，先求得一個基可行解（頂點），判斷是否 為問題的最優解或判斷問題無解 ，再轉換到另一個基可行解，并使目標函數值 減小。重復以上過程，直到求得問題的最優解。例1 maxf=7x1+12x2 s.t. 9x1+5x2 =360 4x1+5x2 =200 3x1+10 x2=

8、0 ; x2=0步驟:1.引進松弛變量x3 x4 x5,將目標函數乘以-1，把數學模型化為標準形式. minf* =-7x1-12x2 s.t. 9x1+5x2+x3=360 4x1+5x2+x4=200 3x1+10 x2+x5=300 xj=0 , j=1, 2, ., 5 2.求初始基可行解： 先選x3,x4,x5為基變量,并用非基變量表 示基變量: x3=360-9x1-5x2 x4=200-4x1-5x2 x5=300-3x1-10 x2 令 x1=x2=0 , 得基可行解, x (1)=(0,0,360,200,300) ;f1* =0 .3. 最優性判斷: 從目標函數f*可知,增

9、加x2的值,其f*還可減少, 因此x(1)不是最優解.4. 檢查比值: 把系數最小的非基礎變量作為換入基礎變量（x2）； 對方程中的常數項與相應的換入變量正比值進行檢查，得到最小比 值的方程中的基礎變量為換出變量（x5）。當x2增加時, x3 x4 x5相應減少, 當x2超過30時, x5就變為負值,違背條件x5=0 選取x2為基變量代替x5, 用非基變量x5. x1表示基變量x2 x3 x4:5.重復第3步,將x2=30-3/10 x1-1/10 x5代入目標函數得f*=-360-17/5x1+6/5x5. 由此可見,增加x1的值,還能使f*的值進一步減少. 因此x (2)也不是最優解. 6

10、.重復第4、5步, 檢查比值、換基迭代. 7.取得最優解, x=(20,24, 60,0,0)時, f*取值最小,則f= - f*取值最大. f 的最大值為428. 5.換基迭代 x2=30-3/10 x1-1/10 x5 x3=210-15/2x1+1/2x5 x4=50-5/2x1+1/2x5 令x1=x5=0 , 得基可行解, x(2)=(0,30,210,50,0), f2*=-7*0-12*30=-360 例2 求解線性規劃問題 max f=5x1+4x2+8x3 s.t. x1+2x2+x3=6 -2x1+x2= -4 5x1+3x2=0 j=1, 2, 3 解： 1. 引進松弛變

11、量x4, x5，將問題標準化，得： min f*= -5x1 - 4x2 - 8x3 s.t. x1+2x2+x3=6 -2x1+x2-x4=-4 5x1+3x2+x5=15 xj=0 j=1, 2, 3, 4, 5 2. 換基迭代 從表2.1計算(檢查比值)判斷, 選x1為基變量, 選x4退出基變量, 得到: x1=2+0. 5x2-0. 5x4 x3=4 - 2. 5x2-0. 5x4 x5=5 - 2. 5x2 - 5. 5x4 F* x1 x2 x3 x4 x5 1 5 4 8 0 0 -42 0 1 -0. 5 0 0. 5 0 2 x1 0 0 2. 5 1 0. 5 0 4 x3 0 0 2.5 0 5. 5 1 5 x5 3. 從單純形表中可知: 所有非基礎變量系數均大于或等于零, 則 x1=2, x2=0, x3=4, f =42 是原問題的最優基礎可行解.選x4, x5為基變量, 得初始單純形表2.1 f* x1 x2 x3 x4 x5 1 5 4 8 0 0 0 0 1 2 1 0 0 0 0 -2 1 0 -1 0 4 x4 0 5 3 0 0 0 15 x5 基可行解為x(0)=(0, 0, 0, 4, 15 ), f0*=0 .輸入原始