數(shù)據(jù)模型——線性規(guī)劃-文庫吧
2025-07-17 16:51 本頁面
【正文】 .. 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)解的過程 。 求解的思路是：先將約束條件加以圖解 ， 求得滿足約束條件的解的集合 （ 即可行域 ） ， 然后結(jié)合目標(biāo)函數(shù)的要求從可行域中找出最優(yōu)解 。 圖解法 例 1 運(yùn)用圖解法，以求出 最優(yōu) 生產(chǎn)計(jì)劃（ 最優(yōu)解 ）。 () ???????????????????0,52426155..2m ax212121221xxxxxxxtsxxz() () () 圖解法 由于線性規(guī)劃模型中只有兩個(gè)決策變量，因此只需建立平面直角坐標(biāo)系就可以進(jìn)行圖解了。 ， 標(biāo)出 坐標(biāo)原點(diǎn) , 坐標(biāo)軸的指向 和 單位長(zhǎng)度 。 ，找出可行域。 。 。 圖 解 法 () ???????????????????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è) 基 。 B 是由 m個(gè)線性獨(dú)立的列向量組成 ),( 21 mrrr pppB ??),2,1( mjx rj ??基向量 基變量 非基變量： 其余變量 解 的 概 念 AX=BXB+NXN=b 令 非基變量 XN=0 得 BXB=b 和特解 XB =B1b 結(jié)合 XN=0 稱為對(duì)應(yīng)于 B的 基本解； 基本解個(gè)數(shù) =基的個(gè)數(shù) ≤Cnm 基可行解 可行的基本解 XB≥0 XN=0 可行基 ：對(duì)應(yīng)于基可行解的基 ??????????NBTn XXxxxX ),(21 ?A=（ B | N） 解的概念 最優(yōu)基 ： 對(duì)應(yīng)的基本可行解也是最優(yōu) 基本可行解個(gè)數(shù) ≤基的個(gè)數(shù) ≤Cnm 基本可行解的非零分量均為正分量， 其正分量個(gè)數(shù) ≤ m。 退化的基本可行解 ： 基本可行解的非零分量個(gè)數(shù)小于m時(shí)，也就是在基本可行解中一個(gè)或多于一個(gè)的基變量取零值時(shí) 凸 集 及 其 頂 點(diǎn) 基本概念： 凸集 ——設(shè) K是 n維歐氏空間的一個(gè)點(diǎn)集 ，若任意兩點(diǎn) X（ 1） ∈ K， X（ 2） ∈ K的連線上的一切點(diǎn)： αX（ 1） +（ 1α） X（ 2） ∈ K （ 0α1） ， 則稱 K為 凸集 。 凸 集 的 概 念 頂點(diǎn) ——設(shè) K是凸集， X?K； 若 K中不存在兩個(gè)不同的點(diǎn) X（ 1） ? K， X（ 2） ? K 使 X=αX（ 1） +（ 1α） X（ 2） （ 0α1） 則稱 X為 K的一個(gè) 頂點(diǎn) （也稱為極點(diǎn)或角點(diǎn)）。 凸 集 的 概 念 凸集 凸集 不是凸集 頂點(diǎn) 基 本 定 理 若線性規(guī)劃問題有最優(yōu)解，一定存在一個(gè)基可行解（可行域頂點(diǎn)）是最優(yōu)解。 定理 1 引理 定理 2 定理 3 若線性規(guī)劃問題存在可行解，則該問題的可行解集（即可行域）是凸集。 線性規(guī)劃問題的可行解 x＝ (x1, x2,…, xn)為基可行解的充要條件是 x的正分量所對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的。 線性規(guī)劃問題的基可行解 x對(duì)應(yīng)線性規(guī)劃問題可行域 (凸集 )的頂點(diǎn) 解的幾何意義 猜想 1 線性規(guī)劃的可行域是凸集； 猜想 2 最優(yōu)解若存在 ， 則可以在可行域的頂點(diǎn)上得到； 猜想 3 可行域的頂點(diǎn)的個(gè)數(shù)是有限的； 猜想 4 若有兩個(gè)最優(yōu)解，則其連線上的點(diǎn)也是最優(yōu)解，即最優(yōu)解有無窮多個(gè) 猜想 5 對(duì)于標(biāo)準(zhǔn)型的線性規(guī)劃 X是可行域頂點(diǎn)的充分必要條件是 X是基本可行解。 幾個(gè)事實(shí) 1 ． 基本可行解不一定都是最優(yōu)解， 最優(yōu)解也不一定都是基本解 2 ． 如果有兩個(gè)基本可行解是最優(yōu)解， 則兩解的凸組合也都是最優(yōu)解。 3 ． 如果最優(yōu)解不唯一， 則會(huì)有多個(gè)基本可行解是最優(yōu)解，它們必然在同一個(gè)面上。 4 ． 行解個(gè)數(shù)有限，可以在基可行解中尋找最優(yōu)解。 剩余的問題是如何判斷一個(gè)基可行解是最優(yōu)解， 如果不是則如何從一個(gè)基可行解轉(zhuǎn)到另一個(gè)基可行解。 線性規(guī)劃及單純形法 ?線性規(guī)劃問題及數(shù)學(xué)模型
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1