[理學(xué)]第三版運(yùn)籌學(xué)總復(fù)習(xí)(編輯修改稿)
2024-11-15 00:59 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 際 恩 陸 2021/11/10 16 ④ 按單純形法進(jìn)行基變換運(yùn)算，建立新的計(jì)算表，返回步驟②。 ⑤ 當(dāng) k=K時(shí)，計(jì)算結(jié)束。表中的解即為滿意解。否則置k=k+1，返回步驟②。 解線性規(guī)劃問(wèn)題的單純形法的計(jì)算步驟： ① 建立初始單純形表，計(jì)算出所有變量的檢驗(yàn)數(shù)。 ② 在非基變量檢驗(yàn)數(shù)中找到最大的正數(shù) σj，它所對(duì)應(yīng)的 變量 xj 作為換入基的變量。 ③ 對(duì)于所有 aij 0 計(jì)算 bi /aij ，其中最小的元素 θ 所對(duì) 應(yīng)的基變量 xi 作為換出基的變量。 ④ 建立新單純形表，重復(fù)上述步驟②、③，直到所有 檢驗(yàn)數(shù)都小于等于零。 際 恩 陸 2021/11/10 17 判斷下列說(shuō)法是否正確 ⑴ 線性規(guī)劃問(wèn)題是目標(biāo)規(guī)劃問(wèn)題的一種特殊形式； ⑵ 正偏差變量應(yīng)取正值，負(fù)偏差變量應(yīng)負(fù)值； ⑶ 目標(biāo)規(guī)劃模型中，應(yīng)同時(shí)包含系統(tǒng)約束（絕對(duì)約束）與目標(biāo)約束； ⑷ 當(dāng)目標(biāo)規(guī)劃問(wèn)題模型中存在 x1+x2+d=4的約束條件，則該約束為系統(tǒng)約束。 ⑶ 目標(biāo)規(guī)劃模型中，應(yīng)同時(shí)包含系統(tǒng)約束（絕對(duì)約束）與目標(biāo)約束； √ 際 恩 陸 2021/11/10 18 第五章 整數(shù)規(guī)劃 [本章學(xué)習(xí)要求 ] ⒈ 熟悉分支定界法和割平面法的原理及其應(yīng)用； ⒉ 掌握求解 01規(guī)劃問(wèn)題的隱枚舉法； [主要概念及算法 ] 求解整數(shù)規(guī)劃的常用方法 ⒊ 掌握求解指派問(wèn)題的匈牙利法。 ⑴ 分支定界法： 設(shè)有最大化的整數(shù)規(guī)劃問(wèn)題 A，與它相應(yīng)的線性規(guī)劃問(wèn)題為問(wèn)題 B，從解問(wèn)題 B開(kāi)始，若其最優(yōu)解不符合 A的整數(shù)條件，那么 B的最優(yōu)目標(biāo)函數(shù)必是 A的最優(yōu)目標(biāo)函數(shù) z*的上界，記作 ，而 A的任意可行解的目 z際 恩 陸 2021/11/10 19 標(biāo)函數(shù)值將是 的一個(gè)下界 ，分支定界法就是將 B的可行域分成子區(qū)域的方法，逐步縮小 和增大 ，最終求得 。 *z zz z*z 用分支定界法求解最大化整數(shù)規(guī)劃問(wèn)題的步驟如下： ① 解與整數(shù)規(guī)劃問(wèn)題 A相應(yīng)的線性規(guī)劃問(wèn)題 B，可能得到以下幾種情況之一： a） B沒(méi)有可行解， A也沒(méi)有可行解，停止計(jì)算。 b） B有可行解，并符合問(wèn)題 A的整數(shù)條件，則此最優(yōu)解為 A的最優(yōu)解，停止計(jì)算。 c） B有可行解，但不符合問(wèn)題 A的整數(shù)條件，把它的目標(biāo)函數(shù)記為 。z際 恩 陸 2021/11/10 20 ② 用觀察法找問(wèn)題 A的一個(gè)整數(shù)可行解，求得其目標(biāo)函數(shù)值，并記作 ，以 表示問(wèn)題 A的最優(yōu)目標(biāo)函數(shù)值，則 。 z *zzzz ?? * 然后進(jìn)行迭代： a）分支，在 B的最優(yōu)解中選取一個(gè)不符合整數(shù)條件的變量 xj，其值為 bj。 構(gòu)造兩個(gè)約束條件： ? ?? ? ②bx①bxjjjj1??? 其中 為不超過(guò) 的最大整數(shù)。 ? ?jb jb際 恩 陸 2021/11/10 21 將這兩個(gè)約束條件分別加入問(wèn)題 B，求兩個(gè)后繼規(guī)劃問(wèn)題 B1和 B2。不考慮整數(shù)整數(shù)約束條件求解這兩個(gè)后繼問(wèn)題 b）定界，以每個(gè)后繼問(wèn)題為一分支標(biāo)明求解的結(jié)果。 第一步：先不考慮整數(shù)約束，變成一般的線性規(guī)劃問(wèn)題，用圖解法或單純形法求解其最優(yōu)解 X(0)*； 第二步：若求得的最優(yōu)解 X(0)*,剛好就是整數(shù)解，則該整數(shù)就是原整數(shù)規(guī)劃的最優(yōu)解，否則轉(zhuǎn)下步； 第三步：對(duì)原問(wèn)題進(jìn)行分支尋求整數(shù)最優(yōu)解。 選取非整數(shù)解 的一個(gè)非整數(shù)分量 ，其小數(shù)部分為 ，以該非整數(shù)部分的相鄰整數(shù) 和 的為邊界將原問(wèn)題分支為兩個(gè)子問(wèn)題，并拋棄這兩個(gè)整數(shù)之間的非整數(shù)區(qū)域； *)0(X ii bX ?*id ii db ?1?? ii db際 恩 陸 2021/11/10 22 i）在原線性規(guī)劃模型中添加分支約束 ，構(gòu)成第一個(gè)子問(wèn)題。 iii dbx ?? ii）在原線性規(guī)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1