數(shù)據(jù)模型——線性規(guī)劃-全文預(yù)覽
【正文】 條件，又使具有線性的目標(biāo)函數(shù)取得極值的一類最優(yōu)化問題稱為線性規(guī)劃問題。 每次辦理時(shí)可簽一份合同 ， 也可簽若干份租用面積和租借期限不同的合同 ，試確定該公司簽訂租借合同的最優(yōu)決策 ，目的是使所付租借費(fèi)用最小 。 已知各月份所需倉庫面積列于表 12。 這時(shí)該公司可獲取的利潤為 (2x1+x2)元 ，令 z=2x1+x2， 因問題中要求獲取的利潤為最大 ， 即 max z。 線性規(guī)劃 Linear Programming 線性規(guī)劃及單純形法 ?線性規(guī)劃問題及數(shù)學(xué)模型 ?圖解法 ?單純形法原理 ?單純形法計(jì)算步驟 ?單純形法進(jìn)一步討論 ?其他應(yīng)用例子 線性規(guī)劃問題 ? 問題的提出 ? 線性規(guī)劃問題的數(shù)學(xué)模型 ? 線性規(guī)劃概念和模型 問題的提出 例 1 美佳公司計(jì)劃制造 Ⅰ 、 Ⅱ 兩種家電產(chǎn)品 。 表 11 項(xiàng)目 Ⅰ Ⅱ 每天可用能力 設(shè)備 A （ h ） 0 5 15 設(shè)備 B （ h ） 6 2 24 測(cè)試工序（ h ） 1 1 5 利潤 （ 元 ） 2 1 數(shù)學(xué)模型 例 1中先用變量 x1和 x2分別表示美佳公司制造家電 Ⅰ 和 Ⅱ 的數(shù)量 。 由此例 1的數(shù)學(xué)模型可表為： 數(shù)學(xué)模型 () ???????????????????0,52426155..2m ax212121221xxxxxxxtsxxz目標(biāo)函數(shù) 約束條件 () () () max: maximize的縮寫， “ 最大化 ” ， . subject to的縮寫， “ 受限制于 …… ” 問題的提出 例 2 捷運(yùn)公司在下一年度的 1~4月的 4個(gè)月內(nèi)擬租用倉庫堆放物資 。 因此該廠可根據(jù)需要 ， 在任何一個(gè)月初辦理租借合同 。該公司希望總的租借費(fèi)用為最小，故有如下數(shù)學(xué)模型： 目標(biāo)函數(shù) 約束條件 . ijm in a 0 ( i = 1 , .. , m 。 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.. 1?其中： ???????????????mjjjjaaap?21標(biāo)準(zhǔn)化 把一般的 LP化成標(biāo)準(zhǔn)型的過程稱為線性規(guī)劃問題的標(biāo)準(zhǔn)化 方法： 1 目標(biāo)標(biāo)準(zhǔn)化 min Z 等價(jià)于 max ( Z ) max Z’=∑cjxj 2 化約束為等式 加松弛變量、減剩余變量 3 變量非負(fù)化 做變換 或 4 右端非負(fù) jj xx ???jjj xxx ????? 0???jx0??jx標(biāo)準(zhǔn)化 標(biāo)準(zhǔn)化舉例： 321 32m i n xxxZ ???1 2 3 3 4 6m a x 2 2 3 3 0 0Z x x x x x x? ????? ? ? ? ? ? ? ???????????????????取值無約束321321321321,0,0632442392..xxxxxxxxxxxxts1 2 3 3 41 2 3 3 51 2 3 31 2 3 3 4 62 2 93 2 2 4..4 2 3 3 6, , , , , 0x x x x xx x x x xstx x x xx x x x x x? ? ???? ? ? ? ??? ? ???? ? ? ? ???? ???? ? ? ???? ??? ???線性規(guī)劃及單純形法 ?線性規(guī)劃問題及數(shù)學(xué)模型 ?圖解法 ?單純形法原理 ?單純形法計(jì)算步驟 ?單純形法進(jìn)一步討論 ?其他應(yīng)用例子 圖解法 線性規(guī)劃的圖解法就是用幾何作圖的方法分析并求出其最優(yōu)解的過程 。 ， 標(biāo)出 坐標(biāo)原點(diǎn) , 坐標(biāo)軸的指向 和 單位長度 。 圖 解 法 () ???????????????????0,52426155..2m ax212121221xxxxxxxtsxxz() () () 圖解法 (a)可行域有界 (b)可行域有界 (c)可行域無界 唯一最優(yōu)解 多個(gè)最優(yōu)解 唯一最優(yōu)解 (d)可行域無界 (e)可行域無界 (f)可行域?yàn)榭占? 多個(gè)最優(yōu)解 目標(biāo)函數(shù)無界 無可行解 線性規(guī)劃及單純形法 ?線性規(guī)劃問題及數(shù)學(xué)模型 ?圖解法 ?單純形法原理 ?單純形法計(jì)算步驟 ?單純形法進(jìn)一步討論 ?數(shù)據(jù)包絡(luò)分析 ?其他應(yīng)用例子 單純形法原理 ? 線性規(guī)劃問題的解的概念 ? 凸集及其頂點(diǎn) ? 幾個(gè)基本定理 解 的 概 念 可行解 ： 變量滿足所有約束條件的一組值 可行解集 ： 所有可行解構(gòu)成的集合 可行域 ： 可行解集構(gòu)成 n維空間的區(qū)域 ?????0xbAX}0{ ??? xb,Ax|xD??????????????）（ njxmibxatsxcjnjijijnjjj,2,10), . . ,1(..zm a x 11?線性規(guī)劃問題 解的概念 最優(yōu)解： 使得目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解 最優(yōu)值： 最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值 目的： 求最優(yōu)解和最優(yōu)值 求解方法： 單純形法 CXZ ?m a x?????0.. XbAXts解的概念 先研究 AX=b 設(shè) 系數(shù)矩陣 A是 m n矩陣，秩為 m， B是 A中 m m階非奇異子矩陣（即 |B|≠0）， 則稱 B是線性規(guī)劃問題的一個(gè) 基 。 凸 集 的 概 念 凸集 凸集 不是凸集 頂點(diǎn) 基 本 定 理 若線性規(guī)劃問題有最優(yōu)解，一定存在一個(gè)基可行解（可行域頂點(diǎn)）是最優(yōu)解。 幾個(gè)事實(shí) 1 ． 基本可行解不一定都是最優(yōu)解， 最優(yōu)解也不一定都是基本解 2 ． 如果有兩個(gè)基本可行解是最優(yōu)解， 則兩解的凸組合也都是最優(yōu)解。 線性規(guī)劃及單純形法 ?線性規(guī)劃問題及數(shù)學(xué)模型 ?圖解法 ?單純形法原理 ?單純形法計(jì)算步驟 ?單純形法進(jìn)一步討論 ?數(shù)據(jù)包絡(luò)分析 ?其他應(yīng)用例子 單 純 形 算 法 ? 理論方法 ? 算法步驟 ? 單純形表 ? 算例 基 本 可 行 解 定 義 令 ),( NBA ?
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1