運(yùn)籌與決策復(fù)習(xí)題(已修改)
2025-01-19 00:12 本頁面
【正文】 復(fù) 習(xí) 課 一、 對于以下線性規(guī)劃問題 min z= x1 +2x2 2x1 +3x2 ≤ 12 (1) 3x1 +x2 ≤ 6 (2) x1 +3x2 ≥ 3 (3) x1 x2 ≥ 0 三個約束對應(yīng)的松弛變量分別為 x3， x4， x5；三個約束條件對應(yīng)的對偶變量分別為 w1， w2， w3。 這個問題可行域為（ EFHI）； 這個問題最優(yōu)解為（ F）； 這個問題基礎(chǔ)解為（ ABCDEFGHIJ）； 這個問題基礎(chǔ)可行解為（ EFHI）； G 點(diǎn)對應(yīng)的解中，大于 0 的變量為（ x1,x2），等于 0 的 變量為（ x3,x5），小于0 的變量為（ x4）； E 點(diǎn)對應(yīng)的基變量為（ x2,x3,x4），非基變量為（ x1,x5）； D 點(diǎn)對應(yīng)的基變量為（ x1,x3,x4），非基變量為（ x2,x5）； 從 E 到 F 的單純形疊代，進(jìn)基變量為（ x1），離基變量為（ x4）； **F 點(diǎn)對應(yīng)的對偶變量，大于 0 的是（ w3），等于 0 的是（ w1,w4,w5），小于 0的是（ w2）。 二、對于以上線性規(guī)劃問題 （ 1）寫出以上問題的對偶問題； （ 2）用單純形表求出這個問題和它的對偶問題的最優(yōu)解。 原料消耗 （噸 /件） 產(chǎn)品A 產(chǎn)品B 產(chǎn)品C 原料 限量 （噸） 原料甲 12 8 10 2400 原料乙 6 10 15 1500 原料丙 15 18 — 1800 原料丁 — 20 22 2022 產(chǎn)品利潤 120 180 210 x3=0 x2=0 x2 x4=0 3 2 1 0 1 2 3 4 5 6 6 5 4 3 2 1 A B C D E F G H J I x1 x1=0 x5=0 （萬元 /件） 三、一個工廠用四種原料生產(chǎn)三種產(chǎn)品，生產(chǎn)每種產(chǎn)品要消耗的各種原料數(shù)量（表中“ — ”表示相應(yīng)的產(chǎn)品不需要這種原料）、各種產(chǎn)品的利潤以及各種原料的限量如右表所示。 寫出原料限制條件下利潤最大化的線性規(guī)劃模型； 寫出以上問題的對偶問題； 已知利潤最大的線性規(guī)劃問題的最優(yōu)解是產(chǎn)品 A 生產(chǎn) 120 件 ，產(chǎn)品 B 不生產(chǎn)，產(chǎn)品 C 生產(chǎn) 52 件，用互補(bǔ)松弛關(guān)系求四種原料的影子價格（寫出單位）； 分別計算三種產(chǎn)品的機(jī)會成本（寫出單位）； 產(chǎn)品 B 對原料乙的消耗系數(shù)（ 10 噸 /件）降低到多少，產(chǎn)品 B 在最優(yōu)解中才能安排生產(chǎn)？ 四、對于以下運(yùn)輸問題 運(yùn)價（元 /噸） B1 B2 B3 B4 供應(yīng)量（噸） A1 9 12 10 8 240 A2 14 7 6 11 80 A3 5 13 15 20 180 需求量（噸） 90 120 130 160 （ 1） 求總運(yùn)費(fèi)最小的運(yùn)輸方案 （ 2） 求 c11=9 在什么范圍內(nèi)變化，最優(yōu) 解保持不變； （ 3） 求 c23=6 在什么范圍內(nèi)變化，最優(yōu)解保持不變。 五、求以下網(wǎng)絡(luò)的最小費(fèi)用流 b1=5 c15=5 b5=2 1 5 c13=2 c54=3 b3=4 b4=2 c12=3 3 4 c65=2 c34=0 c23=1 c46=5 2 6 b2=3 c26=3 b6=6 六、求以下網(wǎng)絡(luò)的最大流和最小割集 七、最短路徑問題 八、動態(tài)規(guī)劃 —— 資源分配問題 有資金 4 萬元，投資 A、 B、 C 三個項目，每個項目的投資效益與投入該項目的資金有關(guān)。三個項目 A、 B、 C 的投資效益（萬噸）和投入資金（萬元）的關(guān)系見下表： 效益（萬噸） 項 目 A B C 投入 資金 （萬元） 1 25 萬噸 18 萬噸 13 萬噸 2 32 萬噸 33 萬噸 32 萬噸 3 38 萬噸 45 萬噸 48 萬噸 4 43 萬元 54 萬元 62 萬元 求對三個項目的最優(yōu)投資分配，使總投資效益最大。 2 3 4 5 6 7 8 1 8 5 4 6 4 3 2 2 3 1 9 6 3 uij 6 7 8 5 10 11 12 9 2 3 4 1 3 4 7 6 2 5 1 4 8 6 3 7 2 4 1 9 8 九、動態(tài)規(guī)劃 —— 背包問題 有 5 萬元資金 ,用于購買 3 種設(shè)備 ,每種設(shè)備的單臺價格和單臺生產(chǎn)能力見下表： 設(shè) 備 A B C 價格 pk（萬元 /臺） 2 1 3 生產(chǎn)能力 qk（萬噸 /臺） 23 11 31 三種設(shè)備應(yīng)各購買多少臺，使總的生產(chǎn)能力最大？ 解答 二、 min z= x1 +2x2 2x1 +3x2 ≤ 12 3x1 +x2 ≤ 6 x1 +3x2 ≥ 3 x1 x2 ≥ 0 引進(jìn)松弛變量 min z= x1 +2x2 2x1 +3x2 +x3 =12 3x1 +x2 +x4 =6 x1 +3x2 x5 =3 x1 x2 x3 x4 x5 ≥ 0 第三個約束兩邊乘以 1 min z= x1 +2x2 2x1 +3x2 +x3 =12 3x1 +x2 +x4 =6 x1 3x2 +x5 =3 x1 x2 x3 x4 x5 ≥ 0 列出單純形表 z x1 x2 x3 x4 x5 RHS z 1 1 2 0 0 0 0 x3 0 2 3 1 0 0 12 x4 0 3 1 0 1 0 6 x5 0 1 [3] 0 0 1 3 先解決原始可行性，用對偶單純形法， x5離基， x2進(jìn)基 z x1 x2 x3 x4 x5 RHS z 1 1/3 0 0 0 2/3 2 x3 0 3 0 1 0 1 9 9/3 x4 0 [10/3] 0 0 1 1/3 5 15/10 x2 0 1/3 1 0 0 1/3 1 — 再解決對偶可行性，用單純形法， x1進(jìn)基， x4離基 z x1 x2 x3 x4 x5 RHS z 1 1/3 0 0 0 2/3 2 x3 0 3 0 1 0 1 9 x4 0 [1/3] 0 0 1/10 1/30 1/2 x2 0 1/3 1 0 0 1/3 1
公司管理相關(guān)推薦
鄂ICP備17016276號-1