數(shù)據(jù)模型——線性規(guī)劃(已修改)
2025-08-13 16:51 本頁面
【正文】 線性規(guī)劃 Linear Programming 線性規(guī)劃及單純形法 ?線性規(guī)劃問題及數(shù)學(xué)模型 ?圖解法 ?單純形法原理 ?單純形法計算步驟 ?單純形法進(jìn)一步討論 ?其他應(yīng)用例子 線性規(guī)劃問題 ? 問題的提出 ? 線性規(guī)劃問題的數(shù)學(xué)模型 ? 線性規(guī)劃概念和模型 問題的提出 例 1 美佳公司計劃制造 Ⅰ 、 Ⅱ 兩種家電產(chǎn)品 。 已知各制造一件時分別占用的設(shè)備 A， B的臺時 、 調(diào)試工序時間及每天可用于這兩種家電的能力 、 各售出一件時的獲利情況 ， 如表 11所示 。 問該公司應(yīng)制造兩種家電各多少件 ， 使獲取的利潤為最大 。 表 11 項目 Ⅰ Ⅱ 每天可用能力 設(shè)備 A （ h ） 0 5 15 設(shè)備 B （ h ） 6 2 24 測試工序（ h ） 1 1 5 利潤 （ 元 ） 2 1 數(shù)學(xué)模型 例 1中先用變量 x1和 x2分別表示美佳公司制造家電 Ⅰ 和 Ⅱ 的數(shù)量 。 這時該公司可獲取的利潤為 (2x1+x2)元 ，令 z=2x1+x2， 因問題中要求獲取的利潤為最大 ， 即 max z。 z是該公司能獲取的利潤的目標(biāo)值 ，它是變量 x1， x2的函數(shù) ， 稱為 目標(biāo)函數(shù) 。 x1， x2的取值受到設(shè)備 A、 B和調(diào)試工序能力的限制 ， 用于描述限制條件的數(shù)學(xué)表達(dá)式稱為 約束條件 。 由此例 1的數(shù)學(xué)模型可表為： 數(shù)學(xué)模型 () ???????????????????0,52426155..2m ax212121221xxxxxxxtsxxz目標(biāo)函數(shù) 約束條件 () () () max: maximize的縮寫， “ 最大化 ” ， . subject to的縮寫， “ 受限制于 …… ” 問題的提出 例 2 捷運公司在下一年度的 1~4月的 4個月內(nèi)擬租用倉庫堆放物資 。 已知各月份所需倉庫面積列于表 12。 倉庫租借費用隨合同期而定 ， 期限越長 ， 折扣越大 ， 具體數(shù)字見表 13。 租借倉庫的合同每月初都可辦理 ，每份合同具體規(guī)定租用面積和期限 。 因此該廠可根據(jù)需要 ， 在任何一個月初辦理租借合同 。 每次辦理時可簽一份合同 ， 也可簽若干份租用面積和租借期限不同的合同 ，試確定該公司簽訂租借合同的最優(yōu)決策 ，目的是使所付租借費用最小 。 月 份 1 2 3 4 所需倉庫面積 15 10 20 12 表 12 單位： 100m2 表 13 合同租賃期限 1 個月 2 個月 3 個月 4 個月 合同期內(nèi)的租費 2 8 0 0 4 5 0 0 6 0 0 0 7 3 0 0 單位：元 /100m2 數(shù)學(xué)模型 例 2中若用變量 xij表示捷運公司在第 i(i=1,…,4) 個月初簽訂的租借期為 j(j=1,…,4) 個月的倉庫面積的合同。因 5月份起該公司不需要租借倉庫，故 x24， x33， x34， x42， x43， x44均為零。該公司希望總的租借費用為最小，故有如下數(shù)學(xué)模型： 目標(biāo)函數(shù) 約束條件 . ijm in a 0 ( i = 1 , .. , m 。 j = 1 , .. , n )1 1 2 1 3 1 4 1 1 2 2 2 3 21 3 2 3 1 41 1 1 2 1 3 1 41 2 1 3 1 4 2 1 2 2 2 31 3 1 4 2 2 2 3 3 1 3 21 4 2 3 3 2 4 1z = 2 8 0 0 ( x + x + x + x ) + 4 5 0 0 ( x + x + x )+ 6 0 0 0 ( x + x ) + 7 3 0 0 xx + x + x + x 1 5x + x + x + x + x + x 1 0x + x + x + x + x + x 2 0x + x + x + x 1 2? ??????????? ??min： minimize ， “最小化” 概念和模型 定義 ： 對于求取一組變量 xj(j=1,2,…..,n)，使之既滿足線性約束條件，又使具有線性的目標(biāo)函數(shù)取得極值的一類最優(yōu)化問題稱為線性規(guī)劃問題。 max（ 或 min） nn xcxcxcZ ???? ??2211? ??????????????????????????????自由,00,),(),(),(..2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats???????概念和模型 一般形式： max（ 或 min） ? ??????????????????????????????自由,00,),(),(),(..2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats???????nn xcxcxcZ ???? ??2211目標(biāo)函數(shù) 約束條件 非負(fù)約束 稱為決策變量 ),2,1( njxj ??稱為價值系數(shù)或目標(biāo)函數(shù)系數(shù) ),2,1( njcj ??稱為資源常數(shù)或約束右端常數(shù) ),2,1( mibi ??稱為技術(shù)系數(shù)或約束系數(shù) ija 0 ( i = 1 , . . , m 。 j = 1 , . . , n )?概念和模型 緊縮形式： max（ 或 min） ???njjj xcZ1????????????????）（ njxmibxatsxcjnjijijnjjj,2,10),..,1(),(..zm a x 11?概念和模型 矩陣形式： max（ 或 min） 稱為決策變量向量 稱為價值系數(shù)向量或目標(biāo)函數(shù)系數(shù)向量 稱為資源常數(shù)向量或約束右端常數(shù)向量 稱為技術(shù)系數(shù)或約束系數(shù)矩陣 CX?Z???????0XbAXts ),(..???????????????nxxxX?21),( 21 ncccC ?????????????????mnmmnnaaaaaaaaaA??????212222111211???????????????mbbbb?21標(biāo)準(zhǔn)形式 標(biāo)準(zhǔn)型的主要特征： ① 目標(biāo)最大； ② 約束等式； ③ 變量非負(fù)； ④ 右端非負(fù) 。 nn xcxcxcZ ???? ?2211m a x??????????????????????0,..2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats??????標(biāo)準(zhǔn)型 標(biāo)準(zhǔn)型的緊縮形式： ???njjj xcZ1m a x???????????njxmibxatsjnjijij,2,10,2,1.. 1??標(biāo)準(zhǔn)型的矩陣形式： CXZ ?m a x?????0.. XbAXts標(biāo)準(zhǔn)型 標(biāo)準(zhǔn)型的向量形式： ???njjj xcZ1m a x??????????njxbxptsjnjjj,2,10
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1