lttaaa線性規(guī)劃(已修改)
2025-08-16 09:30 本頁(yè)面
【正文】 線 性 規(guī) 劃(Linear Programming)線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型線性規(guī)劃問(wèn)題的求解方法線性規(guī)劃的圖解法線性規(guī)劃的單純形法單純形法的進(jìn)一步討論線性規(guī)劃模型的應(yīng)用 為了完成一項(xiàng)任務(wù)或達(dá)到一定的目的，怎樣用最少的人力、物力去完成或者用最少的資源去完成較多的任務(wù)或達(dá)到一定的目的，這個(gè)過(guò)程就是規(guī)劃。例一、有一正方形鐵皮，如何截取 x 使容積為最大？xa此為無(wú)約束極值問(wèn)題一、 線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型（ 一）、問(wèn)題的提出 設(shè) 備產(chǎn) 品 A B C D 利 潤(rùn) （元） Ⅰ 2 1 4 0 2 Ⅱ 2 2 0 4 3 有 效 臺(tái) 時(shí) 12 8 16 12 例二、已知資料如下表所示，問(wèn)如何安排生產(chǎn)才能使利潤(rùn)最大？或如何考慮利潤(rùn)大，產(chǎn)品好銷。模 型 max Z = 2x1 + 3x2 x1 ≥ 0 , x2 ≥ 0. 2x1 + 2x2 ≤ 12 x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12此為帶約束的極值問(wèn)題問(wèn)題中總有未知的變量，需要我們?nèi)ソ鉀Q。 要求：有目標(biāo)函數(shù)及約束條件，一般有非負(fù)條件存在，由此組成規(guī)劃數(shù)學(xué)模型。 如果在規(guī)劃問(wèn)題的數(shù)學(xué)模型中，變量是連續(xù)的（數(shù)值取實(shí)數(shù)）其目標(biāo)函數(shù)是有關(guān)線性函數(shù)（一次方），約束條件是有關(guān)變量的線性等式或不等式，這樣，規(guī)劃問(wèn)題的數(shù)學(xué)模型是線性的。反之，就是非線性的規(guī)劃問(wèn)題（其中一個(gè)條件符合即可）。（二）、數(shù)學(xué)模型 目標(biāo)函數(shù)：約束條件：①②③線性規(guī)劃數(shù)學(xué)模型的一般形式也可以記為如下形式 ：目標(biāo)函數(shù)：約束條件：如將上例用表格表示如下：設(shè)變量 產(chǎn) 品 j 設(shè) 備 i 有效臺(tái) 時(shí) 利 潤(rùn) 向 量 形 式：矩陣形式：規(guī)劃確定型隨機(jī)型靜態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃線 性規(guī) 劃非線性規(guī)劃 整數(shù)規(guī)劃 非整數(shù)規(guī)劃整數(shù)規(guī)劃非整數(shù)規(guī)劃規(guī)劃類型一 般 有兩種方法圖 解 法單純形法兩個(gè)變量、直角坐標(biāo)三個(gè)變量、立體坐標(biāo)適用于任意變量、但需將一般形式變成標(biāo)準(zhǔn)形式二、線性規(guī)劃問(wèn)題的求解方法（一）、求解方法解的概念 ⑴ 可行解：滿足約束條件 ② 、 ③ 的解為可行解。所有解的集合為可行解的集或可行域。 ⑵ 最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。 ⑶ 基： B是矩陣 A中 mn 階非奇異子矩陣（∣ B∣≠0 ）， 則 B是一個(gè)基。則稱 Pj ( j = 1 2 … … m) 為基向量?！? Xj 為基變量，否則為非基變量。（二）、線性規(guī)劃問(wèn)題的解 ⑷ 基本解：滿足條件 ② ，但不滿足條件 ③ 的所有解，最多為 個(gè)。 ⑸ 基本可行解：滿足非負(fù)約束條件的基本解，簡(jiǎn)稱基可行解。 ⑹ 可行基：對(duì)應(yīng)于基可行解的基稱為可行基。非可行解可行解基解基可行解解的基本定理⑴ 線性規(guī)劃問(wèn)題的可行域是凸集（凸多邊形）。凸集 凸集 不是凸集頂 點(diǎn)⑵ 最優(yōu)解一定是在凸集的某一頂點(diǎn)實(shí)現(xiàn)（頂點(diǎn)數(shù)目不超過(guò) 個(gè)）⑶ 先找一個(gè)基本可行解，與周圍頂點(diǎn)比較，如不是最大，繼續(xù)比較，直到找出最大為止。解的情況唯 一 解無(wú) 窮 解無(wú) 界 解無(wú)可行解有最優(yōu)解無(wú)最優(yōu)解 建立直角坐標(biāo) ，圖中陰影部分及邊界上的點(diǎn)均為其解，是由約束條件來(lái)反映的。例一、⑴⑵⑶⑷三、圖 解 法0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 ⑴⑵⑶⑷作 圖∴ 最 優(yōu) 解： x1 = 4 x2 = 2 有唯一最優(yōu)解， Z = 14x2 x1(4 2)⑴⑵⑶⑷ 例二、 例三、⑴⑵⑶無(wú)窮多最優(yōu)解⑴⑵ 無(wú)界解x1x1x2 x2 ⑴⑵x1x2 無(wú)可行解例四、練習(xí) 1 效 產(chǎn) 品機(jī)床 率 A B 機(jī)床臺(tái)數(shù) Ⅰ 30 40 40 Ⅱ 55 30 40 Ⅲ 23 37 20 某車間用三種不同型號(hào)的機(jī)床 Ⅰ 、 Ⅱ 、 Ⅲ ，加工 A、B兩種零件，機(jī)床臺(tái)數(shù)、生產(chǎn)效率如表所示。問(wèn)如何合理安排機(jī)床的加工任務(wù)，才能使生產(chǎn)的零件總數(shù)最多？某工廠生產(chǎn) A A2 兩種產(chǎn)品， 每件可獲利潤(rùn) 120元。每個(gè)產(chǎn)品都經(jīng)過(guò)三道工序，資料如表所示。工廠應(yīng)如何安排生產(chǎn)計(jì)劃使獲得的總利潤(rùn)最多？試寫(xiě)出此問(wèn)題的數(shù)學(xué)模型。 工 產(chǎn) 品工序 時(shí) A1 A2可用工 時(shí) Ⅰ 3 2 800 Ⅱ 2 3 800 Ⅲ 1 1 350
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1