運(yùn)籌學(xué)-第2講線性規(guī)劃模型-在線瀏覽
2025-08-03 12:59本頁(yè)面
【正文】 般形式 ??????????????n, . . . ,2,1j0xm, . . . ,2,1ibxa.xczm a xjn1jijijn1jjj 線性規(guī)劃模型的標(biāo)準(zhǔn)形式 線性規(guī)劃化的標(biāo)準(zhǔn)化 (1) 目標(biāo)函數(shù) (2) 約束條件 ? ?xfz ?m i n ? ?xfz ??39。 ? 不等式 + 松弛變量 ? 不等式 剩余變量 = = max z = 3x1+5x2 寫(xiě)出例 標(biāo)準(zhǔn)形式 max z = 3x1+5x2 ????????????????)5,4,3,2,1j(0x18xx2x312xx24xxj5214231 . ????????????0x,x18x2x312x24x212121 . (3) 變量 ?????? jx令 0, 39。39。39。???jjjjjxxxxx0?jx令 039。???jjjxxx無(wú)符號(hào)限制3213221323210,0162569434m i nxxxxxxxxxxxxz?????????????0,162256944344m a x65439。339。1639。339。1439。339。39。3239。?????????????????xxxxxxxxxxxxxxxxxxxxxxz解 例 將下列線性規(guī)劃化成標(biāo)準(zhǔn)型 )0,(。39。339。339。1139。全部可行解的集合稱為 可行域。 ??????????????n, . . . ,2,1j0xm, . . . ,2,1ibxa.xczm a xjn1jijijn1jjj （ a） （ b） （ c） 線性規(guī)劃問(wèn)題的基本概念 基： 設(shè) Am n (nm)為約束方程組 (b)的系數(shù)矩陣，其秩為 m。不失一般性，設(shè) ? ?m21mm2m1mm22221m11211P,...,P,PaaaaaaaaaB ???????????????????B 中的每一個(gè)列向量 Pj（ j=1,2,…,m ）稱為 基向量 ，與基向量 Pj 對(duì)應(yīng)的變量 xj 稱為 基變量 。 基 B的 m個(gè)列向量是線性無(wú)關(guān)的。 基解 ：假設(shè)系數(shù)矩陣 A 的秩為 m，不妨設(shè) A 中前 m 個(gè)列向量線性獨(dú)立，方程可以寫(xiě)為 nmnn2n11m1mm1m21m1m21mmmm2m122m221211m2111xaaaxaaabbbxaaaxaaaxaaa???????????????????????????????????????????????????????????????????????????????令所有非基變量 xm+1=?=xn=0， 由 |B|≠0，根據(jù)克萊姆規(guī)則，可得 m個(gè)基變量的唯一解 xb=(x1,x2,…,x m) 加上所有取值為 0 的非基變量，得： x=(x1,x2,…,x m,0,…,0) 稱 x 為線性規(guī)劃問(wèn)題的基解。 ????????????????),j(xxxxxxxxj543210182312245214231 max z = 3x1+5x2 ?????????100230102000101A? ??????????100010001P,P,P 543基可行解 ： 滿足變量非負(fù)約束條件 (c)的基解稱為基可行解。 可行解 基 解 基可行解 令 x1=x2=0，解得 x3=4,x4=12,x5=18,則 x=(0,0,4,12,18)T是一個(gè)基解。 可行基往往不只一個(gè)。 最多可能有多少個(gè) ? 例：求下述線性規(guī)劃的基可行解 4,1014223m a x42132121????????????jxxxxxxxxxzjA= =( A1 , A2 , A3 , A4 ) 2 1 1 0 1 1 0 1 B1=( A3 , A4 )= X(1)=( 0 , 0 , 4 , 1 )T 基解 1 0 0 1 B2=( A1 , A4 )= X(2)=( 2 , 0 , 0 , 3 )T 基解 2 0 1 1 B3=( A1 , A2 )= X(3)=( 1 , 2 , 0 , 0 )T 基解 2 1 1 1 B4=( A2 , A3 )= X(4)=( 0 , 1 , 3 , 0 )T 基解 1 1 1 0 B5=( A1 , A3 )= X(5)=( 1 , 0 , 6 , 0 )T 基解 2 1 1 0 B6=( A2 , A4 )= X(6)=( 0 , 4 , 0 , 3 )T 基解 1 0 1 1 基可行解 解 幾何思路 圖解法的介紹 1. 確定 可行解集合 R， 即 可行
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1