運(yùn)籌學(xué)PPT教學(xué)完整課件(全面系統(tǒng)).ppt

運(yùn)籌學(xué) 1 緒論2 線性規(guī)劃建模及單純形法3 線性規(guī)劃問題的對偶與靈敏度分析4 運(yùn)輸問題5 動(dòng)態(tài)規(guī)劃6 排隊(duì)論7 決策分析8 圖與網(wǎng)絡(luò)分析 第一章緒論 運(yùn)籌學(xué)概況簡述 運(yùn)籌學(xué) OperationsResearch 直譯為 運(yùn)作研究 運(yùn)籌學(xué)是運(yùn)用科學(xué)的方法 如分析 試驗(yàn) 量化等 來決定如何最佳地運(yùn)營和設(shè)計(jì)各種系統(tǒng)的一門學(xué)科 運(yùn)籌學(xué)概況簡述 運(yùn)籌學(xué)能夠?qū)?jīng)濟(jì)管理系統(tǒng)中的人力 物力 財(cái)力等資源進(jìn)行統(tǒng)籌安排 為決策者提供有依據(jù)的最優(yōu)方案 以實(shí)現(xiàn)最有效的管理 通常以最優(yōu) 最佳等作為決策目標(biāo) 避開最劣的方案 運(yùn)籌學(xué)在工商管理中的應(yīng)用 生產(chǎn)計(jì)劃 生產(chǎn)作業(yè)的計(jì)劃 日程表的編排 合理下料 配料問題 物料管理等 庫存管理 多種物資庫存量的管理 庫存方式 庫存量等 運(yùn)輸問題 確定最小成本的運(yùn)輸線路 物資的調(diào)撥 運(yùn)輸工具的調(diào)度以及建廠地址的選擇等 運(yùn)籌學(xué)在工商管理中的應(yīng)用 人事管理 對人員的需求和使用的預(yù)測 確定人員編制 人員合理分配 建立人才評價(jià)體系等 市場營銷 廣告預(yù)算 媒介選擇 定價(jià) 產(chǎn)品開發(fā)與銷售計(jì)劃制定等 運(yùn)籌學(xué)在工商管理中的應(yīng)用 財(cái)務(wù)和會計(jì) 包括預(yù)測 貸款 成本分析 定價(jià) 證券管理 現(xiàn)金管理等 其他 設(shè)備維修 更新 項(xiàng)目選擇 評價(jià) 工程優(yōu)化設(shè)計(jì)與管理等 運(yùn)籌學(xué)的產(chǎn)生和發(fā)展 運(yùn)籌學(xué)思想的出現(xiàn)可以追溯到很早 田忌齊王賽馬 對策論 孫子兵法等都體現(xiàn)了優(yōu)化的思想 OperationalResearch 這一名詞最早出現(xiàn)在第二次世界大戰(zhàn)期間 美 英等國家的作戰(zhàn)研究小組為了解決作戰(zhàn)中所遇到的許多錯(cuò)綜復(fù)雜的戰(zhàn)略 戰(zhàn)術(shù)問題而提出的 運(yùn)籌學(xué)的產(chǎn)生和發(fā)展 戰(zhàn)后這些研究成果被應(yīng)用到生產(chǎn) 經(jīng)濟(jì)領(lǐng)域 并得到迅速發(fā)展 有關(guān)理論和方法的研究 實(shí)踐不斷深入 1947年美國數(shù)學(xué)家丹捷格 G B Dantzig 提出了求解線性規(guī)劃的有效方法 單純形法 運(yùn)籌學(xué)的產(chǎn)生和發(fā)展 數(shù)學(xué)對運(yùn)籌學(xué)的作用 是有關(guān)理論和方法的研究基礎(chǔ) 是建立運(yùn)籌學(xué)模型的工具 計(jì)算機(jī)的發(fā)展 促進(jìn)運(yùn)籌學(xué)的進(jìn)一步發(fā)展 高速 可靠的計(jì)算是運(yùn)籌學(xué)解決問題的基本保障 運(yùn)籌學(xué)的分支 線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃動(dòng)態(tài)規(guī)劃 多目標(biāo)規(guī)劃隨機(jī)規(guī)劃模糊規(guī)劃等 運(yùn)籌學(xué)的分支 圖與網(wǎng)絡(luò)理論存儲論排隊(duì)論決策論 對策論排序與統(tǒng)籌方法可靠性理論等 運(yùn)籌學(xué)方法使用情況 美1983 運(yùn)籌學(xué)方法在中國使用情況 隨機(jī)抽樣 運(yùn)籌學(xué)的推廣應(yīng)用前景 據(jù)美勞工局1992年統(tǒng)計(jì)預(yù)測 社會對運(yùn)籌學(xué)應(yīng)用分析人員的需求從1990年到2005年 其增長百分比預(yù)測為73 增長速度排到各項(xiàng)職業(yè)的前三位 運(yùn)籌學(xué)的推廣應(yīng)用前景 結(jié)論 運(yùn)籌學(xué)在國內(nèi)或國外的推廣應(yīng)用前景是非常廣闊的 工商企業(yè)對運(yùn)籌學(xué)應(yīng)用的需求是很大的 在工商企業(yè)推廣運(yùn)籌學(xué)方面有大量的工作要做 運(yùn)籌學(xué)解決問題的過程 1 提出問題 認(rèn)清問題 2 尋求可行方案 建模 求解 3 確定評估目標(biāo)及方案的標(biāo)準(zhǔn)或方法 途徑 4 評估各個(gè)方案 解的檢驗(yàn) 靈敏性分析等 運(yùn)籌學(xué)解決問題的過程 5 選擇最優(yōu)方案 決策 6 方案實(shí)施 回到實(shí)踐中 7 后評估 考察問題是否得到完滿解決 1 2 3 形成問題 4 5 分析問題 定性分析與定量分析相結(jié)合 構(gòu)成決策 如何學(xué)習(xí)運(yùn)籌學(xué)課程 學(xué)習(xí)運(yùn)籌學(xué)要把重點(diǎn)放在分析 理解有關(guān)的概念 思路上 在自學(xué)過程中 應(yīng)該多向自己提問 例如一個(gè)方法的實(shí)質(zhì)是什么 為什么這樣進(jìn)行 怎么進(jìn)行等 自學(xué)時(shí)要掌握三個(gè)重要環(huán)節(jié) 如何學(xué)習(xí)運(yùn)籌學(xué)課程 1 認(rèn)真閱讀教材和參考資料 以指定教材為主 同時(shí)參考其他有關(guān)書籍 一般每一本運(yùn)籌學(xué)教材都有自己的特點(diǎn) 但是基本原理 概念都是一致的 注意主從 參考資料會幫助你開闊思路 使學(xué)習(xí)深入 但是 把時(shí)間過多放在參考資料上 會導(dǎo)致思路分散 不利于學(xué)好 2 要在理解了基本概念和理論的基礎(chǔ)上研究例題 注意例題是為了幫助理解概念 理論的 作業(yè)練習(xí)的主要作用也是這樣 它同時(shí)還有讓你自己檢查自己學(xué)習(xí)的作用 因此 做題要有信心 要獨(dú)立完成 不要怕出錯(cuò) 因?yàn)?整個(gè)課程是一個(gè)整體 各節(jié)內(nèi)容有內(nèi)在聯(lián)系 只要學(xué)到一定程度 知識融會貫通起來 你自己就能夠?qū)λ鲱}目的正確性作出判斷 如何學(xué)習(xí)運(yùn)籌學(xué)課程 3 要學(xué)會做學(xué)習(xí)小結(jié) 每一節(jié)或一章學(xué)完后 必須學(xué)會用精煉的語言來概述該書所講內(nèi)容 這樣 你才能夠從較高的角度來看問題 更深刻地理解有關(guān)知識和內(nèi)容 這就稱作 把書讀薄 若能夠結(jié)合相關(guān)參考文獻(xiàn)并深入理解 把相關(guān)知識從更深入 廣泛的角度進(jìn)行論述 則稱為 把書讀厚 如何學(xué)習(xí)運(yùn)籌學(xué)課程 24 第二章線性規(guī)劃建模及單純形法 本章內(nèi)容重點(diǎn) 線性規(guī)劃模型與解的主要概念線性規(guī)劃的單純形法 線性規(guī)劃多解分析線性規(guī)劃應(yīng)用 建模 25 1 線性規(guī)劃的概念 例2 1 某工廠擁有A B C三種類型的設(shè)備 生產(chǎn)甲 乙兩種產(chǎn)品 每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù) 每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時(shí)數(shù)如下表所示 26 問題 工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤 解 設(shè)變量xi為第i種 甲 乙 產(chǎn)品的生產(chǎn)件數(shù) i 1 2 根據(jù)題意 我們知道兩種產(chǎn)品的生產(chǎn)受到設(shè)備能力 機(jī)時(shí)數(shù) 的限制 對設(shè)備A 兩種產(chǎn)品生產(chǎn)所占用的機(jī)時(shí)數(shù)不能超過65 于是我們可以得到不等式 3x1 2x2 65 對設(shè)備B 兩種產(chǎn)品生產(chǎn)所占用的機(jī)時(shí)數(shù)不能超過40 于是我們可以得到不等式 2x1 x2 40 1 線性規(guī)劃的概念 27 對設(shè)備C 兩種產(chǎn)品生產(chǎn)所占用的機(jī)時(shí)數(shù)不能超過75 于是我們可以得到不等式 3x2 75 另外 產(chǎn)品數(shù)不可能為負(fù) 即x1 x2 0 同時(shí) 我們有一個(gè)追求目標(biāo) 即獲取最大利潤 于是可寫出目標(biāo)函數(shù)z為相應(yīng)的生產(chǎn)計(jì)劃可以獲得的總利潤 z 1500 x1 2500 x2綜合上述討論 在加工時(shí)間以及利潤與產(chǎn)品產(chǎn)量成線性關(guān)系的假設(shè)下 把目標(biāo)函數(shù)和約束條件放在一起 可以建立如下的線性規(guī)劃模型 1 線性規(guī)劃的概念 28 目標(biāo)函數(shù)Maxz 1500 x1 2500 x2約束條件s t 3x1 2x2 652x1 x2 403x2 75x1 x2 0 1 線性規(guī)劃的概念 29 這是一個(gè)典型的利潤最大化的生產(chǎn)計(jì)劃問題 其中 Max 是英文單詞 Maximize 的縮寫 含義為 最大化 s t 是 subjectto 的縮寫 表示 滿足于 因此 上述模型的含義是 在給定條件限制下 求使目標(biāo)函數(shù)z達(dá)到最大的x1 x2的取值 1 線性規(guī)劃的概念 30 一般形式目標(biāo)函數(shù) Max Min z c1x1 c2x2 cnxn 約束條件 a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 1 線性規(guī)劃的概念 31 標(biāo)準(zhǔn)形式目標(biāo)函數(shù) Maxz c1x1 c2x2 cnxn 約束條件 A11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 1 線性規(guī)劃的概念 32 可以看出 線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個(gè)特點(diǎn) 目標(biāo)最大化 約束為等式 決策變量均非負(fù) 右端項(xiàng)非負(fù) 對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題 我們總可以通過以下變換 將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式 1 線性規(guī)劃的概念 33 1 極小化目標(biāo)函數(shù)的問題 設(shè)目標(biāo)函數(shù)為Minf c1x1 c2x2 cnxn則可以令z f 該極小化問題與下面的極大化問題有相同的最優(yōu)解 即Maxz c1x1 c2x2 cnxn但必須注意 盡管以上兩個(gè)問題的最優(yōu)解相同 但他們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號 即Minf Maxz 1 線性規(guī)劃的概念 34 2 約束條件不是等式的問題 設(shè)約束條件為ai1x1 ai2x2 ainxn bi可以引進(jìn)一個(gè)新的變量s 使它等于約束右邊與左邊之差s bi ai1x1 ai2x2 ainxn 顯然 s也具有非負(fù)約束 即s 0 這時(shí)新的約束條件成為ai1x1 ai2x2 ainxn s bi 1 線性規(guī)劃的概念 35 當(dāng)約束條件為ai1x1 ai2x2 ainxn bi時(shí) 類似地令s ai1x1 ai2x2 ainxn bi顯然 s也具有非負(fù)約束 即s 0 這時(shí)新的約束條件成為ai1x1 ai2x2 ainxn s bi 1 線性規(guī)劃的概念 36 為了使約束由不等式成為等式而引進(jìn)的變量s稱為 松弛變量 如果原問題中有若干個(gè)非等式約束 則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí) 必須對各個(gè)約束引進(jìn)不同的松弛變量 1 線性規(guī)劃的概念 37 例2 2 將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式Minf 3 6x1 5 2x2 1 8x3s t 2 3x1 5 2x2 6 1x3 15 74 1x1 3 3x3 8 9x1 x2 x3 38x1 x2 x3 0 1 線性規(guī)劃的概念 解 首先 將目標(biāo)函數(shù)轉(zhuǎn)換成極大化 令z f 3 6x1 5 2x2 1 8x3 38 其次考慮約束 有2個(gè)不等式約束 引進(jìn)松弛變量x4 x5 0 于是 我們可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題 Maxz 3 6x1 5 2x2 1 8x3s t 2 3x1 5 2x2 6 1x3 x4 15 74 1x1 3 3x3 x5 8 9x1 x2 x3 38x1 x2 x3 x4 x5 0 1 線性規(guī)劃的概念 39 3 變量無符號限制的問題 在標(biāo)準(zhǔn)形式中 必須每一個(gè)變量均有非負(fù)約束 當(dāng)某一個(gè)變量xj沒有非負(fù)約束時(shí) 可以令xj xj xj 其中xj 0 xj 0即用兩個(gè)非負(fù)變量之差來表示一個(gè)無符號限制的變量 當(dāng)然xj的符號取決于xj 和xj 的大小 1 線性規(guī)劃的概念 40 4 右端項(xiàng)有負(fù)值的問題 在標(biāo)準(zhǔn)形式中 要求右端項(xiàng)必須每一個(gè)分量非負(fù) 當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí) 如bi 0 則把該等式約束兩端同時(shí)乘以 1 得到 ai1x1 ai2x2 ainxn bi 1 線性規(guī)劃的概念 41 例2 3 將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式Minf 3x1 5x2 8x3 7x4s t 2x1 3x2 5x3 6x4 284x1 2x2 3x3 9x4 396x2 2x3 3x4 58x1 x3 x4 0 1 線性規(guī)劃的概念 42 解 首先 將目標(biāo)函數(shù)轉(zhuǎn)換成極大化 令z f 3x1 5x2 8x3 7x4 其次考慮約束 有3個(gè)不等式約束 引進(jìn)松弛變量x5 x6 x7 0 由于x2無非負(fù)限制 可令x2 x2 x2 其中x2 0 x2 0 由于第3個(gè)約束右端項(xiàng)系數(shù)為 58 于是把該式兩端乘以 1 于是 我們可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題 1 線性規(guī)劃的概念 43 Maxz 3x1 5x2 5x2 8x3 7x4s t 2x1 3x2 3x2 5x3 6x4 x5 284x1 2x2 2x2 3x3 9x4 x6 39 6x2 6x2 2x3 3x4 x7 58x1 x2 x2 x3 x4 x5 x6 x7 0 1 線性規(guī)劃的概念 44 2 線性規(guī)劃的圖解法 線性規(guī)劃的圖解法 解的幾何表示 對于只有兩個(gè)決策變量的線性規(guī)劃問題 可以二維直角坐標(biāo)平面上作圖表示線性規(guī)劃問題的有關(guān)概念 并求解 圖解法求解線性規(guī)劃問題的步驟如下 45 2 線性規(guī)劃的圖解法 1 建立直角坐標(biāo)系 分別取決策變量x1 x2為坐標(biāo)向量 46 2 線性規(guī)劃的圖解法 2 繪制可行域 對每個(gè)約束 包括非負(fù)約束 條件 作出其約束半平面 不等式 或約束直線 等式 各半平面與直線交出來的區(qū)域若存在 其中的點(diǎn)為此線性規(guī)劃的可行解 稱這個(gè)區(qū)域?yàn)榭尚屑蚩尚杏?然后進(jìn)行下步 否則若交為空 那么該線性規(guī)劃問題無可行解 47 2 線性規(guī)劃的圖解法 3 繪制目標(biāo)函數(shù)等值線 并移動(dòng)求解 目標(biāo)函數(shù)隨著取值不同 為一族相互平行的直線 首先 任意給定目標(biāo)函數(shù)一個(gè)值 可作出一條目標(biāo)函數(shù)的等值線 直線 然后 確定該直線平移使函數(shù)值增加的方向 最后 依照目標(biāo)的要求平移此直線 48 2 線性規(guī)劃的圖解法 結(jié)果若目標(biāo)函數(shù)等值線能夠移動(dòng)到既與可行域有交點(diǎn)又達(dá)到最優(yōu)的位置 此目標(biāo)函數(shù)等值線與可行域的交點(diǎn)即最優(yōu)解 一個(gè)或多個(gè) 此目標(biāo)函數(shù)的值即最優(yōu)值 否則 目標(biāo)函數(shù)等值線與可行域?qū)⒔挥跓o窮遠(yuǎn)處 此時(shí)稱無有限最優(yōu)解 49 2 線性規(guī)劃的圖解法 例2 4 某工廠擁有A B C三種類型的設(shè)備 生產(chǎn)甲 乙兩種產(chǎn)品 每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù) 每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時(shí)數(shù)如下表所示 50 2 線性規(guī)劃的圖解法 問題 工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤 用圖解法求解 解 設(shè)變量xi為第i種 甲 乙 產(chǎn)品的生產(chǎn)件數(shù) i 1 2 根據(jù)前面分析 可以建立如下的線性規(guī)劃模型 Maxz 1500 x1 2500 x2s t 3x1 2x2 65 A 2x1 x2 40 B 3x2 75 C x1 x2 0 D E 51 2 線性規(guī)劃的圖解法例題作圖 1 按照圖解法的步驟 1 以決策變量x1 x2為坐標(biāo)向量作平面直角坐標(biāo)系 52 2 線性規(guī)劃的圖解法 2 對每個(gè)約束 包括非負(fù)約束 條件作出直線 A B C D E 并通過判斷確定不等式所決定的半平面 各約束半平面交出來的區(qū)域即可行集或可行域如下圖陰影所示 53 2 線性規(guī)劃的圖解法例題作圖 2 第2步圖示 1 分別作出各約束半平面 2x1 x2 40 3x2 75 x1 0 X2 0 3x1 2x2 65 54 2 線性規(guī)劃的圖解法例題作圖 3 第2步圖示 2 各約束半平面的交 可行域 55 2 線性規(guī)劃的圖解法 3 任意給定目標(biāo)函數(shù)一個(gè)值 例如37500 作一條目標(biāo)函數(shù)的等值線 并確定該等值線平移后值增加的方向 向上移動(dòng)函數(shù)值增大 平移此目標(biāo)函數(shù)的等值線 使其達(dá)到既與可行域有交點(diǎn)又不可能使值再增加的位置 得到交點(diǎn) 5 25 T 即最優(yōu)解 此目標(biāo)函數(shù)的值為70000 56 2 線性規(guī)劃的圖解法例題作圖 4 第3步圖示作出目標(biāo)函數(shù)等值線 函數(shù)值增大 57 2 線性規(guī)劃的圖解法例題作圖 5 第3步圖示 2 求出最優(yōu)解 58 2 線性規(guī)劃的圖解法 根據(jù)上面的過程我們得到這個(gè)線性規(guī)劃的最優(yōu)解x1 5 x2 25 最優(yōu)值z 70000即最優(yōu)方案為生產(chǎn)甲產(chǎn)品5件 乙產(chǎn)品25件 可獲得最大利潤為70000元 59 2 線性規(guī)劃的圖解法 線性規(guī)劃的解有如下幾種情況 1 存在有限最優(yōu)解 唯一最優(yōu)解 無窮多個(gè)最優(yōu)解2 無有限最優(yōu)解 無界解 3 無可行解 可行域空 60 2 線性規(guī)劃的圖解法 例2 5 在例2 4的線性規(guī)劃模型中 如果目標(biāo)函數(shù)變?yōu)?Maxz 1500 x1 1000 x2那么 最優(yōu)情況下目標(biāo)函數(shù)的等值線與直線 A 重合 這時(shí) 最優(yōu)解有無窮多個(gè) 是從點(diǎn) 5 25 T到點(diǎn) 15 10 T線段上的所有點(diǎn) 最優(yōu)值為32500 如下圖所示 61 2 線性規(guī)劃的圖解法 無窮多解的情況 15 10 T 62 2 線性規(guī)劃的圖解法 例2 6 在例2 4的線性規(guī)劃模型中 如果約束條件 A C 變?yōu)?3x1 2x2 65 A 3x2 75 C 并且去掉 D E 的非負(fù)限制 那么 可行域成為一個(gè)上無界的區(qū)域 這時(shí) 沒有有限最優(yōu)解 如下圖所示 63 2 線性規(guī)劃的圖解法 無有限解的情況 64 2 線性規(guī)劃的圖解法 例2 7 在例2 4的線性規(guī)劃模型中 如果增加約束條件 F 為 x1 x2 40 F 那么 可行域成為空的區(qū)域 這時(shí) 沒有可行解 顯然線性規(guī)劃問題無解 如下圖所示 65 2 線性規(guī)劃的圖解法 無可行解的情況 66 根據(jù)以上例題 進(jìn)一步分析討論可知線性規(guī)劃的可行域和最優(yōu)解有以下幾種可能的情況1 可行域?yàn)榉忾]的有界區(qū)域 a 有唯一的最優(yōu)解 b 有無窮多個(gè)最優(yōu)解 2 可行域?yàn)榉忾]的無界區(qū)域 c 有唯一的最優(yōu)解 2 線性規(guī)劃的圖解法 67 d 有無窮多個(gè)最優(yōu)解 e 目標(biāo)函數(shù)無界 即雖有可行解 但在可行域中 目標(biāo)函數(shù)可以無限增大或無限減少 因而沒有有限最優(yōu)解 3 可行域?yàn)榭占?f 沒有可行解 原問題無最優(yōu)解 2 線性規(guī)劃的圖解法 68 可行解 可行解集 可行域 最優(yōu)解 最優(yōu)值基 基變量 非基變量基本解 基本可行解可行基 最優(yōu)基 熟悉下列一些解的概念 2 線性規(guī)劃解的概念 69 線性規(guī)劃的基 基本解與基本可行解在一般情況下 由于圖解法無法解決三個(gè)變量以上的線性規(guī)劃問題 對于n個(gè)變量的線性規(guī)劃問題 我們必須用解方程的辦法來求得可行域的極點(diǎn) 再來進(jìn)一步考察前例 例2 8把例2 1的線性規(guī)劃模型標(biāo)準(zhǔn)化 引入松馳變量x3 x4 x5 0 得到 2 線性規(guī)劃解的概念 70 Maxz 1500 x1 2500 x2s t 3x1 2x2 x3 65 A 2x1 x2 x4 40 B 3x2 x5 75 C x1 x2 x3 x4 x5 0用 D E F G H 分別表示x1 0 x2 0 x3 0 x4 0 x5 0 這里一共有8個(gè)約束條件 其中3個(gè)等式約束 2 線性規(guī)劃解的概念 71 一般情況下 等式約束的個(gè)數(shù)少于決策變量的個(gè)數(shù) 5個(gè)變量非負(fù)約束 與決策變量個(gè)數(shù)相同 每5個(gè)方程若線性無關(guān)可解得一個(gè)點(diǎn) 我們可以看到前例圖解法得到的區(qū)域中每兩條直線的交點(diǎn)與此例的各個(gè)方程有如下關(guān)系 見下圖 2 線性規(guī)劃解的概念 72 2 線性規(guī)劃解的概念 平面上各不等式約束半平面得交點(diǎn) 73 由上圖可以看出 直線A B的交點(diǎn)對應(yīng)于約束條件 A B C F G 的解 即 x 1 15 10 0 0 45 T直線A C的交點(diǎn)對應(yīng)于約束條件 A B C F H 的解 即 x 2 5 25 0 5 0 T直線A D的交點(diǎn)對應(yīng)于約束條件 A B C D F 的解 即 x 3 0 32 5 0 7 5 22 5 T 2 線性規(guī)劃解的概念 74 直線A E的交點(diǎn)對應(yīng)于約束條件 A B C E F 的解 即 x 4 65 3 0 0 10 3 75 T直線B C的交點(diǎn)對應(yīng)于約束條件 A B C G H 的解 即 x 5 7 5 25 7 5 0 0 T直線B D的交點(diǎn)對應(yīng)于約束條件 A B C D G 的解 即 x 6 0 40 15 0 45 T 2 線性規(guī)劃解的概念 75 直線B E的交點(diǎn)對應(yīng)于約束條件 A B C E G 的解 即 x 7 20 0 5 0 75 T直線C D的交點(diǎn)對應(yīng)于約束條件 A B C D H 的解 即 x 8 0 25 15 15 0 T直線C E無交點(diǎn) C E相互平行 直線D E的交點(diǎn)對應(yīng)于約束條件 A B C D E 的解 即 x 9 0 0 65 40 75 T 2 線性規(guī)劃解的概念 76 上圖各約束直線的交點(diǎn)是由以下方法得到 在標(biāo)準(zhǔn)化的等式約束中 令其中某兩個(gè)變量為零 得到其他變量的唯一解 這個(gè)解就是相應(yīng)交點(diǎn)的坐標(biāo) 如果某一交點(diǎn)的坐標(biāo) x1 x2 x3 x4 x5 T全為非負(fù) 則該交點(diǎn)就對應(yīng)于線性規(guī)劃可行域的一個(gè)極點(diǎn) 如A B A C B E C D和D E的交點(diǎn) 如果某一交點(diǎn)的坐標(biāo)中至少有一個(gè)分量為負(fù)值 如A D A E B C和B D的交點(diǎn) 則該交點(diǎn)不是可行域的極點(diǎn) 2 線性規(guī)劃解的概念 77 由上圖可知 A B交點(diǎn)對應(yīng)于x3 0 x4 0 在等式約束中令x3 0 x4 0 得到x1 15 x2 10 x5 45 即A B交點(diǎn)對應(yīng)于極點(diǎn)x x1 x2 x3 x4 x5 T 15 10 0 0 45 T 由于所有分量都為非負(fù) 因此A B交點(diǎn)是可行域的極點(diǎn) 又知 B C交點(diǎn)對應(yīng)于x4 0 x5 0 在等式約束中令x4 0 x5 0 得到x1 7 5 x2 25 x3 7 5 即B C交點(diǎn)對應(yīng)于點(diǎn)x x1 x2 x3 x4 x5 T 7 5 25 7 5 0 0 T 由于有負(fù)分量 因此B C交點(diǎn)不是可行域的極點(diǎn) 我們同樣可以討論其他交點(diǎn)的情況 2 線性規(guī)劃解的概念 78 下面討論線性規(guī)劃標(biāo)準(zhǔn)形式的基 基本解 基本可行解的概念 考慮線性規(guī)劃標(biāo)準(zhǔn)形式的約束條件 Ax b x 0其中A為m n的矩陣 n m 秩 A m b Rm 在約束等式中 令n維空間的解向量 x x1 x2 xn T 2 線性規(guī)劃解的概念 79 中n m個(gè)變量為零 如果剩下的m個(gè)變量在線性方程組中有唯一解 則這n個(gè)變量的值組成的向量x就對應(yīng)于n維空間Rn中若干個(gè)超平面的一個(gè)交點(diǎn) 當(dāng)這n個(gè)變量的值都是非負(fù)時(shí) 這個(gè)交點(diǎn)就是線性規(guī)劃可行域的一個(gè)極點(diǎn) 根據(jù)以上分析 我們建立以下概念 1 線性規(guī)劃的基 對于線性規(guī)劃的約束條件Ax b x 0 2 線性規(guī)劃解的概念 80 設(shè)B是A矩陣中的一個(gè)非奇異 可逆 的m m子矩陣 則稱B為線性規(guī)劃的一個(gè)基 用前文的記號 A p1 p2 pn 其中pj a1j a2j amj T Rm 任取A中的m個(gè)線性無關(guān)列向量pj Rm構(gòu)成矩陣B pj1 pj2 pjm 那么B為線性規(guī)劃的一個(gè)基 我們稱對應(yīng)于基B的變量xj1 xj2 xjm為基變量 而其他變量稱為非基變量 2 線性規(guī)劃解的概念 81 可以用矩陣來描述這些概念 設(shè)B是線性規(guī)劃的一個(gè)基 則A可以表示為A B N x也可相應(yīng)地分成xBx xN其中xB為m維列向量 它的各分量稱為基變量 與基B的列向量對應(yīng) xN為n m列向量 它的各分量稱為非基變量 與非基矩陣N的列向量對應(yīng) 這時(shí)約束等式Ax b可表示為 2 線性規(guī)劃解的概念 82 xBB N bxN或BxB NxN b如果對非基變量xN取確定的值 則xB有唯一的值與之對應(yīng)xB B 1b B 1NxN特別 當(dāng)取xN 0 這時(shí)有xB B 1b 關(guān)于這類特別的解 有以下概念 2 線性規(guī)劃解的概念 83 2 線性規(guī)劃問題的基本解 基本可行解和可行基 對于線性規(guī)劃問題 設(shè)矩陣B pj1 pj2 pjm 為一個(gè)基 令所有非基變量為零 可以得到m個(gè)關(guān)于基變量xj1 xj2 xjm的線性方程 解這個(gè)線性方程組得到基變量的值 我們稱這個(gè)解為一個(gè)基本解 若得到的基變量的值均非負(fù) 則稱為基本可行解 同時(shí)稱這個(gè)基B為可行基 2 線性規(guī)劃解的概念 84 矩陣描述為 對于線性規(guī)劃的解xBB 1bx xN0稱為線性規(guī)劃與基B對應(yīng)的基本解 若其中B 1b 0 則稱以上的基本解為一基本可行解 相應(yīng)的基B稱為可行基 2 線性規(guī)劃解的概念 85 我們可以證明以下結(jié)論 線性規(guī)劃的基本可行解就是可行域的極點(diǎn) 這個(gè)結(jié)論被稱為線性規(guī)劃的基本定理 它的重要性在于把可行域的極點(diǎn)這一幾何概念與基本可行解這一代數(shù)概念聯(lián)系起來 因而可以通過求基本可行解的線性代數(shù)的方法來得到可行域的一切極點(diǎn) 從而有可能進(jìn)一步獲得最優(yōu)極點(diǎn) 2 線性規(guī)劃解的概念 86 例2 9 考慮例2 8的線性規(guī)劃模型Maxz 1500 x1 2500 x2s t 3x1 2x2 x3 652x1 x2 x4 403x2 x5 75x1 x2 x3 x4 x5 0注意 線性規(guī)劃的基本解 基本可行解 極點(diǎn) 和可行基只與線性規(guī)劃問題標(biāo)準(zhǔn)形式的約束條件有關(guān) 2 線性規(guī)劃解的概念 87 32100A P1 P2 P3 P4 P5 2101003001A矩陣包含以下10個(gè)3 3的子矩陣 B1 p1 p2 p3 B2 p1 p2 p4 B3 p1 p2 p5 B4 p1 p3 p4 B5 p1 p3 p5 B6 p1 p4 p5 B7 p2 p3 p4 B8 p2 p3 p5 B9 p2 p4 p5 B10 p3 p4 p5 2 線性規(guī)劃解的概念 88 其中 B4 0 因而B4不是該線性規(guī)劃問題的基 其余均為非奇異方陣 因此該問題共有9個(gè)基 對于基B3 p1 p2 p5 令非基變量x3 0 x4 0 在等式約束中令x3 0 x4 0 解線性方程組 3x1 2x2 0 x5 652x1 x2 0 x5 400 x1 3x2 x5 75得到x1 15 x2 10 x5 45 對應(yīng)的基本可行解 x x1 x2 x3 x4 x5 T 15 10 0 0 45 T 于是對應(yīng)的基B3是一個(gè)可行基 2 線性規(guī)劃解的概念 89 類似可得到x 2 5 25 0 5 0 T 對應(yīng)B2 x 7 20 0 5 0 75 T 對應(yīng)B5 x 8 0 25 15 15 0 T 對應(yīng)B7 x 9 0 0 65 40 75 T 對應(yīng)B10 是基本可行解 而x 3 0 32 5 0 7 5 22 5 T 對應(yīng)B9 x 4 65 3 0 0 10 3 75 T 對應(yīng)B6 x 5 7 5 25 7 5 0 0 T 對應(yīng)B1 x 6 0 40 15 0 45 T 對應(yīng)B8 是基本解 2 線性規(guī)劃解的概念 90 因此 對應(yīng)基本可行解 極點(diǎn) 的B2B3B5B7B10都是可行基 這里指出了一種求解線性規(guī)劃問題的可能途徑 就是先確定線性規(guī)劃問題的基 如果是可行基 則計(jì)算相應(yīng)的基本可行解以及相應(yīng)解的目標(biāo)函數(shù)值 由于基的個(gè)數(shù)是有限的 最多個(gè) 因此必定可以從有限個(gè)基本可行解中找到最優(yōu)解 2 線性規(guī)劃解的概念 91 利用求解線性規(guī)劃問題基本可行解 極點(diǎn) 的方法來求解較大規(guī)模的問題是不可行的 單純形法的基本思路是有選擇地取基本可行解 即是從可行域的一個(gè)極點(diǎn)出發(fā) 沿著可行域的邊界移到另一個(gè)相鄰的極點(diǎn) 要求新極點(diǎn)的目標(biāo)函數(shù)值不比原目標(biāo)函數(shù)值差 3 單純形法 92 由上節(jié)的討論可知 對于線性規(guī)劃的一個(gè)基 當(dāng)非基變量確定以后 基變量和目標(biāo)函數(shù)的值也隨之確定 因此 一個(gè)基本可行解向另一個(gè)基本可行解的移動(dòng) 以及移動(dòng)時(shí)基變量和目標(biāo)函數(shù)值的變化 可以分別由基變量和目標(biāo)函數(shù)用非基變量的表達(dá)式來表示 同時(shí) 當(dāng)可行解從可行域的一個(gè)極點(diǎn)沿著可行域的邊界移動(dòng)到一個(gè)相鄰的極點(diǎn)的過程中 所有非基變量中只有一個(gè)變量的值從0開始增加 而其他非基變量的值都保持0不變 3 單純形法 93 3 單純形法 單純形法的基本過程 94 考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問題 Maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 x1c1b1a11a12 a1nx2c2b2a21a22 a2nx C B A xncnbnam1am2 amn 3 單純形法 95 這里 矩陣A表示為 A p1 p2 pn 其中pj a1j a2j amj T Rm 若找到一個(gè)可行基 無防設(shè)B p1 p2 pm 則m個(gè)基變量為x1 x2 xm n m個(gè)非基變量為xm 1 xm 2 xn 通過運(yùn)算 所有的基變量都可以用非基變量來表示 3 單純形法 96 3 單純形法 x1 b 1 a 1m 1xm 1 a 1m 2xm 2 a 1nxn x2 b 2 a 2m 1xm 1 a 2m 2xm 2 a 2nxn 2 11 xm b m a mm 1xm 1 a mm 2xm 2 a mnxn 把它們代入目標(biāo)函數(shù) 得z z m 1xm 1 m 2xm 2 nxn 2 12 其中 j cj c1a 1j c2a 2j cma mj 我們把由非基變量表示的目標(biāo)函數(shù)形式稱為基B相應(yīng)的目標(biāo)函數(shù)典式 97 單純形法的基本步驟可描述如下 1 尋找一個(gè)初始的可行基和相應(yīng)基本可行解 極點(diǎn) 確定基變量 非基變量以及基變量 非基變量 全部等于0 和目標(biāo)函數(shù)的值 并將目標(biāo)函數(shù)和基變量分別用非基變量表示 3 單純形法 98 2 在用非基變量表示的目標(biāo)函數(shù)表達(dá)式 2 12 中 我們稱非基變量xj的系數(shù) 或其負(fù)值 為檢驗(yàn)數(shù)記為 j 若 j 0 那么相應(yīng)的非基變量xj 它的值從當(dāng)前值0開始增加時(shí) 目標(biāo)函數(shù)值隨之增加 這個(gè)選定的非基變量xj稱為 進(jìn)基變量 轉(zhuǎn) 3 如果任何一個(gè)非基變量的值增加都不能使目標(biāo)函數(shù)值增加 即所有 j非正 則當(dāng)前的基本可行解就是最優(yōu)解 計(jì)算結(jié)束 3 單純形法 99 3 在用非基變量表示的基變量的表達(dá)式 2 11 中 觀察進(jìn)基變量增加時(shí)各基變量變化情況 確定基變量的值在進(jìn)基變量增加過程中首先減少到0的變量xr 滿足 min b i a ij a ij 0 b r a rj這個(gè)基變量xr稱為 出基變量 當(dāng)進(jìn)基變量的值增加到 時(shí) 出基變量xr的值降為0時(shí) 可行解就移動(dòng)到了相鄰的基本可行解 極點(diǎn) 轉(zhuǎn) 4 3 單純形法 100 如果進(jìn)基變量的值增加時(shí) 所有基變量的值都不減少 即所有a ij非正 則表示可行域是不封閉的 且目標(biāo)函數(shù)值隨進(jìn)基變量的增加可以無限增加 此時(shí) 不存在有限最優(yōu)解 計(jì)算結(jié)束 4 將進(jìn)基變量作為新的基變量 出基變量作為新的非基變量 確定新的基 新的基本可行解和新的目標(biāo)函數(shù)值 在新的基變量 非基變量的基礎(chǔ)上重復(fù) 1 3 單純形法 101 例2 10 用單純形法的基本思路解例2 8的線性規(guī)劃問題Maxz 1500 x1 2500 x2s t 3x1 2x2 x3 652x1 x2 x4 403x2 x5 75x1 x2 x3 x4 x5 0 3 單純形法 102 第一次迭代 1 取初始可行基B10 p3 p4 p5 那么x3 x4 x5為基變量 x1 x2為非基變量 將基變量和目標(biāo)函數(shù)用非基變量表示 z 1500 x1 2500 x2x3 65 3x1 2x2x4 40 2x1 x2x5 75 3x2當(dāng)非基變量x1 x2 0時(shí) 相應(yīng)的基變量和目標(biāo)函數(shù)值為x3 65 x4 40 x5 75 z 0 得到當(dāng)前的基本可行解 x 0 0 65 40 75 T z 0 這個(gè)解對應(yīng)于圖2 7的D E交點(diǎn) 3 單純形法 103 2 選擇進(jìn)基變量 在目標(biāo)函數(shù)z 1500 x1 2500 x2中 非基變量x1 x2的系數(shù)都是正數(shù) 因此x1 x2進(jìn)基都可以使目標(biāo)函數(shù)z增大 但x2的系數(shù)為2500 絕對值比x1的系數(shù)1500大 因此把x2作為進(jìn)基變量可以使目標(biāo)函數(shù)z增加更快 選擇x2為進(jìn)基變量 使x2的值從0開始增加 另一個(gè)非基變量x1保持零值不變 3 單純形法 104 3 確定出基變量 在約束條件x3 65 3x1 2x2x4 40 2x1 x2x5 75 3x2中 由于進(jìn)基變量x2在3個(gè)約束條件中的系數(shù)都是負(fù)數(shù) 當(dāng)x2的值從0開始增加時(shí) 基變量x3 x4 x5的值分別從當(dāng)前的值65 40和75開始減少 當(dāng)x2增加到25時(shí) x5首先下降為0成為非基變量 這時(shí) 新的基變量為x3 x4 x2 新的非基變量為x1 x5 當(dāng)前的基本可行解和目標(biāo)函數(shù)值為 x 0 25 15 15 0 T z 62500 這個(gè)解對應(yīng)于圖中的C D交點(diǎn) 3 單純形法 105 第二次迭代 1 當(dāng)前的可行基為B7 p2 p3 p4 那么x2 x3 x4為基變量 x1 x5為非基變量 將基變量和目標(biāo)函數(shù)用非基變量表示 z 62500 1500 x1 2500 3 x5x2 25 1 3 x5x3 15 3x1 2 3 x5x4 15 2x1 1 3 x5 3 單純形法 106 2 選擇進(jìn)基變量 在目標(biāo)函數(shù)z 62500 1500 x1 2500 3 x5中 非基變量x1的系數(shù)是正數(shù) 因此x1進(jìn)基可以使目標(biāo)函數(shù)z增大 于是選擇x1進(jìn)基 使x1的值從0開始增加 另一個(gè)非基變量x5保持零值不變 3 確定出基變量 在約束條件x2 25 1 3 x5x3 15 3x1 2 3 x5x4 15 2x1 1 3 x5 3 單純形法 107 中 由于進(jìn)基變量x1在兩個(gè)約束條件中的系數(shù)都是負(fù)數(shù) 當(dāng)x1的值從0開始增加時(shí) 基變量x3 x4的值分別從當(dāng)前的值15 15開始減少 當(dāng)x1增加到5時(shí) x3首先下降為0成為非基變量 這時(shí) 新的基變量為x1 x2 x4 新的非基變量為x3 x5 當(dāng)前的基本可行解和目標(biāo)函數(shù)值為 x 5 25 0 5 0 T z 70000 這個(gè)解對應(yīng)于圖中的A C交點(diǎn) 3 單純形法 108 第三次迭代 1 當(dāng)前的可行基為B2 p1 p2 p4 那么x1 x2 x4為基變量 x3 x5為非基變量 將基變量和目標(biāo)函數(shù)用非基變量表示 z 70000 500 x3 500 x5x1 5 1 3 x3 2 9 x5x2 25 1 3 x5x4 5 2 3 x3 1 9 x5 3 單純形法 109 2 選擇進(jìn)基變量 在目標(biāo)函數(shù)z 70000 500 x3 500 x5中 非基變量x3 x5的系數(shù)均不是正數(shù) 因此進(jìn)基都不可能使目標(biāo)函數(shù)z增大 于是得到最優(yōu)解 x 5 25 0 5 0 T 最優(yōu)目標(biāo)值為z 70000 這個(gè)解對應(yīng)于圖2 7的A C交點(diǎn) 我們也稱相應(yīng)的基B2 p1 p2 p4 為最優(yōu)基 計(jì)算結(jié)束 3 單純形法 110 3 單純形法 表格單純形法考慮 bi 0i 1 mMaxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 111 3 單純形法 加入松弛變量 Maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn xn 1 b1a21x1 a22x2 a2nxn xn 2 b2 am1x1 am2x2 amnxn xn m bmx1 x2 xn xn 1 xn m 0 112 顯然 xj 0j 1 n xn i bii 1 m是基本可行解對應(yīng)的基是單位矩陣 以下是初始單純形表 mm其中 f cn ibi j cj cn iaij為檢驗(yàn)數(shù)cn i 0i 1 mi 1i 1an i i 1 an i j 0 j i i j 1 m 3 單純形法 113 3 單純形法 例2 10 化標(biāo)準(zhǔn)形式 Maxz 1500 x1 2500 x2s t 3x1 2x2 x3 652x1 x2 x4 403x2 x5 75x1 x2 x3 x4 x5 0最優(yōu)解x1 5x2 25x4 5 松弛標(biāo)量 表示B設(shè)備有5個(gè)機(jī)時(shí)的剩余 最優(yōu)值z 70000 114 注意 單純形法中 1 每一步運(yùn)算只能用矩陣初等行變換 2 表中第3列的數(shù)總應(yīng)保持非負(fù) 0 3 當(dāng)所有檢驗(yàn)數(shù)均非正 0 時(shí) 得到最優(yōu)單純形表 3 線性規(guī)劃 115 一般情況的處理及注意事項(xiàng)的強(qiáng)調(diào) 主要是討論初始基本可行解不明顯時(shí) 常用的方法 要弄清它的原理 并通過例題掌握這些方法 同時(shí)進(jìn)一步熟悉用單純形法解題 考慮一般問題 bi 0i 1 m 3 單純形法 116 Maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 3 單純形法 117 大M法 引入人工變量xn i 0 i 1 m 及充分大正數(shù)M 得到 Maxz c1x1 c2x2 cnxn Mxn 1 Mxn ms t a11x1 a12x2 a1nxn xn 1 b1a21x1 a22x2 a2nxn xn 2 b2 am1x1 am2x2 amnxn xn m bmx1 x2 xn xn 1 xn m 0 3 單純形法 118 顯然 xj 0j 1 n xn i bii 1 m是基本可行解 對應(yīng)的基是單位矩陣 結(jié)論 若得到的最優(yōu)解滿足xn i 0i 1 m則是原問題的最優(yōu)解 否則 原問題無可行解 3 單純形法 119 兩階段法 引入人工變量xn i 0 i 1 m 構(gòu)造 Maxz xn 1 xn 2 xn ms t a11x1 a12x2 a1nxn xn 1 b1a21x1 a22x2 a2nxn xn 2 b2 am1x1 am2x2 amnxn xn m bmx1 x2 xn xn 1 xn m 0 3 單純形法 120 第一階段求解上述問題 顯然 xj 0j 1 n xn i bii 1 m是基本可行解 它對應(yīng)的基是單位矩陣 結(jié)論 若得到的最優(yōu)解滿足xn i 0i 1 m則是原問題的基本可行解 否則 原問題無可行解 得到原問題的基本可行解后 第二階段求解原問題 3 單純形法 121 例2 11 LP Maxz 5x1 2x2 3x3 x4s t x1 2x2 3x3 152x1 x2 5x3 20 x1 2x2 4x3 x4 26x1 x2 x3 x4 0 3 單純形法 122 Maxz 5x1 2x2 3x3 x4 Mx5 Mx6s t x1 2x2 3x3 x5 152x1 x2 5x3 x6 20 x1 2x2 4x3 x4 26x1 x2 x3 x4 x5 x6 0 大M法問題 LP M 3 單純形法 123 大M法 LP M 得到最優(yōu)解 25 3 10 3 0 11 T最優(yōu)目標(biāo)值 112 3 3 單純形法 124 第一階段問題 LP 1 Maxz x5 x6s t x1 2x2 3x3 x5 152x1 x2 5x3 x6 20 x1 2x2 4x3 x4 26x1 x2 x3 x4 x5 x6 0 兩階段法 3 單純形法 125 第一階段 LP 1 得到原問題的基本可行解 0 15 7 25 7 52 7 T 3 單純形法 126 第二階段把基本可行解填入表中 得到原問題的最優(yōu)解 25 3 10 3 0 11 T最優(yōu)目標(biāo)值 112 3 3 單純形法 127 注意 單純形法中1 每一步運(yùn)算只能用矩陣初等行變換 2 表中第3列 b列 的數(shù)總應(yīng)保持非負(fù) 0 3 當(dāng)所有檢驗(yàn)數(shù)均非正 0 時(shí) 得到最優(yōu)單純形表 若直接對目標(biāo)求最h 要求所有檢驗(yàn)數(shù)均非負(fù) 4 當(dāng)最優(yōu)單純形表存在非基變量對應(yīng)的檢驗(yàn)數(shù)為零時(shí) 可能存在無窮多解 3 單純形法 128 5 關(guān)于退化和循環(huán) 如果在一個(gè)基本可行解的基變量中至少有一個(gè)分量xBi 0 i 1 2 m 則稱此基本可行解是退化的基本可行解 一般情況下 退化的基本可行解 極點(diǎn) 是由若干個(gè)不同的基本可行解 極點(diǎn) 在特殊情況下合并成一個(gè)基本可行解 極點(diǎn) 而形成的 退化的結(jié)構(gòu)對單純形迭代會造成不利的影響 3 單純形法 129 可能出現(xiàn)以下情況 進(jìn)行進(jìn)基 出基變換后 雖然改變了基 但沒有改變基本可行解 極點(diǎn) 目標(biāo)函數(shù)當(dāng)然也不會改進(jìn) 進(jìn)行若干次基變換后 才脫離退化基本可行解 極點(diǎn) 進(jìn)入其他基本可行解 極點(diǎn) 這種情況會增加迭代次數(shù) 使單純形法收斂的速度減慢 在特殊情況下 退化會出現(xiàn)基的循環(huán) 一旦出現(xiàn)這樣的情況 單純形迭代將永遠(yuǎn)停留在同一極點(diǎn)上 因而無法求得最優(yōu)解 3 單純形法 130 在單純形法求解線性規(guī)劃問題時(shí) 一旦出現(xiàn)這種因退化而導(dǎo)致的基的循環(huán) 單純形法就無法求得最優(yōu)解 這是一般單純形法的一個(gè)缺陷 但是實(shí)際上 盡管退化的結(jié)構(gòu)是經(jīng)常遇到的 而循環(huán)現(xiàn)象在實(shí)際問題中出現(xiàn)得較少 盡管如此 人們還是對如何防止出現(xiàn)循環(huán)作了大量研究 1952年Charnes提出了 攝動(dòng)法 1954年Dantzig Orden和Wolfe又提出了 字典序法 3 單純形法 131 這些方法都比較復(fù)雜 同時(shí)也降低了迭代的速度 1976年 Bland提出了一個(gè)避免循環(huán)的新方法 其原則十分簡單 僅在選擇進(jìn)基變量和出基變量時(shí)作了以下規(guī)定 在選擇進(jìn)基變量時(shí) 在所有 j 0的非基變量中選取下標(biāo)最小的進(jìn)基 當(dāng)有多個(gè)變量同時(shí)可作為出基變量時(shí) 選擇下標(biāo)最小的那個(gè)變量出基 這樣就可以避免出現(xiàn)循環(huán) 當(dāng)然 這樣可能使收斂速度降低 3 單純形法 132 合理利用線材問題 如何下料使用材最少 配料問題 在原料供應(yīng)量的限制下如何獲取最大利潤 投資問題 從投資項(xiàng)目中選取方案 使投資回報(bào)最大 4 線性規(guī)劃應(yīng)用 建模 一 線性規(guī)劃 133 產(chǎn)品生產(chǎn)計(jì)劃 合理利用人力 物力 財(cái)力等 使獲利最大 勞動(dòng)力安排 用最少的勞動(dòng)力來滿足工作的需要 運(yùn)輸問題 如何制定調(diào)運(yùn)方案 使總運(yùn)費(fèi)最小 4 線性規(guī)劃應(yīng)用 134 數(shù)學(xué)規(guī)劃的建模有許多共同點(diǎn) 要遵循下列原則 1 容易理解 建立的模型不但要求建模者理解 還應(yīng)當(dāng)讓有關(guān)人員理解 這樣便于考察實(shí)際問題與模型的關(guān)系 使得到的結(jié)論能夠更好地應(yīng)用于解決實(shí)際問題 2 容易查找模型中的錯(cuò)誤 這個(gè)原則的目的顯然與 1 相關(guān) 常出現(xiàn)的錯(cuò)誤有 書寫錯(cuò)誤和公式錯(cuò)誤 4 線性規(guī)劃應(yīng)用 135 3 容易求解 對線性規(guī)劃來說 容易求解問題主要是控制問題的規(guī)模 包括決策變量的個(gè)數(shù)和約束條件的個(gè)數(shù) 這條原則的實(shí)現(xiàn)往往會與 1 發(fā)生矛盾 在實(shí)現(xiàn)時(shí)需要對兩條原則進(jìn)行統(tǒng)籌考慮 4 線性規(guī)劃應(yīng)用 136 建立線性規(guī)劃模型的過程可以分為四個(gè)步驟 1 設(shè)立決策變量 2 明確約束條件并用決策變量的線性等式或不等式表示 3 用決策變量的線性函數(shù)表示目標(biāo) 并確定是求極大 Max 還是極小 Min 4 根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性 4 線性規(guī)劃應(yīng)用 137 例2 12 某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下 人力資源分配的問題 設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段一開始時(shí)上班 并連續(xù)工作8h 問該公交線路怎樣安排司機(jī)和乘務(wù)人員 既能滿足工作需要 又配備最少司機(jī)和乘務(wù)人員 138 解 設(shè)xi表示第i班次時(shí)開始上班的司機(jī)和乘務(wù)人員數(shù) 這樣我們建立如下的數(shù)學(xué)模型 目標(biāo)函數(shù) Minx1 x2 x3 x4 x5 x6約束條件 s t x1 x6 60 x1 x2 70 x2 x3 60 x3 x4 50 x4 x5 20 x5 x6 30 x1 x2 x3 x4 x5 x6 0 人力資源分配的問題 139 例2 13 某工廠要做100套鋼架 每套用長為2 9m 2 1m 1 5m的圓鋼各一根 已知原料每根長7 4m 問 應(yīng)如何下料 可使所用原料最省 套裁下料問題 解 考慮下列各種下料方案 按一種邏輯順序給出 把各種下料方案按剩余料頭從小到大順序列出 140 假設(shè)x1 x2 x3 x4 x5分別為上面前5種方案下料的原材料根數(shù) 我們建立如下的數(shù)學(xué)模型 目標(biāo)函數(shù) Minx1 x2 x3 x4 x5約束條件 s t x1 2x2 x4 1002x3 2x4 x5 1003x1 x2 2x3 3x5 100 x1 x2 x3 x4 x5 0 套裁下料問題 141 例2 14 明興公司生產(chǎn)甲 乙 丙三種產(chǎn)品 都需要經(jīng)過鑄造 機(jī)加工和裝配三個(gè)車間 甲 乙兩種產(chǎn)品的鑄件可以外包協(xié)作 亦可以自行生產(chǎn) 但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量 數(shù)據(jù)如下表 問 公司為了獲得最大利潤 甲 乙 丙三種產(chǎn)品各生產(chǎn)多少件 甲 乙兩種產(chǎn)品的鑄造中 由本公司鑄造和由外包協(xié)作各應(yīng)多少件 生產(chǎn)計(jì)劃的問題 142 解 設(shè)x1 x2 x3分別為三道工序都由本公司加工的甲 乙 丙三種產(chǎn)品的件數(shù) x4 x5分別為由外協(xié)鑄造再由本公司機(jī)加工和裝配的甲 乙兩種產(chǎn)品的件數(shù) 生產(chǎn)計(jì)劃的問題 143 求xi的利潤 利潤 售價(jià) 各成本之和可得到xi i 1 2 3 4 5 的利潤分別為15 10 7 13 9元 這樣我們建立如下數(shù)學(xué)模型 目標(biāo)函數(shù) Max15x1 10 x2 7x3 13x4 9x5約束條件 s t 5x1 10 x2 7x3 80006x1 4x2 8x3 6x4 4x5 120003x1 2x2 2x3 3x4 2x5 10000 x1 x2 x3 x4 x5 0 生產(chǎn)計(jì)劃的問題 144 例2 15 永久機(jī)械廠生產(chǎn) 三種產(chǎn)品 均要經(jīng)過A B兩道工序加工 假設(shè)有兩種規(guī)格的設(shè)備A1 A2能完成A工序 有三種規(guī)格的設(shè)備B1 B2 B3能完成B工序 可在A B的任何規(guī)格的設(shè)備上加工 可在任意規(guī)格的A設(shè)備上加工 但對B工序 只能在B1設(shè)備上加工 只能在A2與B2設(shè)備上加工 數(shù)據(jù)如下表 問 為使該廠獲得最大利潤 應(yīng)如何制定產(chǎn)品加工方案 生產(chǎn)計(jì)劃的問題 145 解 設(shè)xijk表示第i種產(chǎn)品 在第j種工序上的第k種設(shè)備上加工的數(shù)量 利潤 銷售單價(jià) 原料單價(jià) 產(chǎn)品件數(shù) 之和 每臺時(shí)的設(shè)備費(fèi)用 設(shè)備實(shí)際使用的總臺時(shí)數(shù) 之和 生產(chǎn)計(jì)劃的問題 146 這樣我們建立如下的數(shù)學(xué)模型 Max0 75x111 0 7753x112 1 15x211 1 3611x212 1 9148x312 0 375x121 0 5x221 0 4475x122 1 2304x322 0 35x123s t5x111 10 x211 6000 設(shè)備A1 7x112 9x212 12x312 10000 設(shè)備A2 6x121 8x221 4000 設(shè)備B1 4x12