《運(yùn)籌學(xué) 復(fù)習(xí)練習(xí)題》由會(huì)員分享,可在線閱讀,更多相關(guān)《運(yùn)籌學(xué) 復(fù)習(xí)練習(xí)題(5頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、串講練習(xí)題
1. 某公司生產(chǎn)的產(chǎn)品A,B,C和D都要經(jīng)過下列工序:刨、立銑、鉆孔和裝配。已知每單位產(chǎn)品所需工時(shí)及本月四道工序可用生產(chǎn)時(shí)間如下表所示:
刨
立銑
鉆孔
裝配
A
0.5
2.0
0.5
3.0
B
1.0
1.0.
0.5
1.0.
C
1.0
1.0
1.0
2.0
D
0.5
1.0
1.0
3.0
可用生產(chǎn)時(shí)間(小時(shí))
1800
2800
3000
6000
又知四種產(chǎn)品對(duì)利潤(rùn)貢獻(xiàn)及本月最少銷售需要單位如下:
產(chǎn)品
最少銷售需要單位
元/單位
A
100
2
B
600
3
C
500
2、
1
D
400
4
問該公司該如何安排生產(chǎn)使利潤(rùn)收入為最大?(建立模型)
2.已知線性規(guī)劃問題
min z=2x1-x2+2x3
-x1+x2+x3=4
-x1+x2-x3≤6
x1≤0,x2≥0,x3無約束
(1) 寫出其對(duì)偶問題并化為標(biāo)準(zhǔn)型式。
(2) 用單純形法求出原問題的最優(yōu)解。
3.應(yīng)用對(duì)偶問題性質(zhì),求出下面問題的最優(yōu)解。
4.某混合飼料場(chǎng)為某種動(dòng)物配置飼料。已知此動(dòng)物的生長(zhǎng)速
3、度與飼料中的三種營(yíng)養(yǎng)成分甲、乙、丙有關(guān),且每頭動(dòng)物每天需要營(yíng)養(yǎng)甲85g、乙5g、丙15g?,F(xiàn)有五種飼料中都含有這三種營(yíng)養(yǎng)成分,每種飼料每公斤所含營(yíng)養(yǎng)成分及每種飼料成本如下表所示。求既滿足動(dòng)物生長(zhǎng)需要又使成本最低的飼料配方。
飼料
營(yíng)養(yǎng)甲/g
營(yíng)養(yǎng)乙/g
營(yíng)養(yǎng)丙/g
成本/元
1
0.50
0.10
0.08
2
2
2.00
0.06
0.70
6
3
3.00
0.04
0.35
5
4
1.50
0.15
0.25
4
5
0.80
0.20
0.02
3
5.京成畜產(chǎn)品公司計(jì)劃在市區(qū)的東西南北四區(qū)建立銷售門市部,擬議中有1
4、0個(gè)位置可供選擇,考慮到各地區(qū)居民的生活水平及居民居住密集度,規(guī)定:在東區(qū)由三個(gè)點(diǎn)至多選擇兩個(gè);在西區(qū)由兩個(gè)點(diǎn)中至少選一個(gè);在南區(qū)由兩個(gè)點(diǎn)中至少選一個(gè);在北區(qū)由三個(gè)點(diǎn)中至少選兩個(gè)。各點(diǎn)的設(shè)備投資及每年可獲利潤(rùn)由于地點(diǎn)不同都是不一樣的,預(yù)測(cè)情況如下表。但投資總額不能超過720萬元,問應(yīng)選擇哪幾個(gè)銷售點(diǎn)可使年利潤(rùn)為最大。
投資額
100
120
150
80
70
90
80
140
160
180
利潤(rùn)
36
40
50
22
20
30
25
48
58
61
6.已知下表為求解某線性規(guī)劃問題的最終單純形
5、表,表中為松弛變量,問題的約束條件為形式。
5/2
0
1/2
1
1/2
0
5/2
1
-1/2
0
-1/6
1/3
0
-4
0
-4
-2
(1) 寫出原線性規(guī)劃問題的數(shù)學(xué)模型;
(2) 寫出原問題的對(duì)偶問題;
(3) 直接由上表寫出對(duì)偶問題的最優(yōu)解。
7.已知線性規(guī)劃問題
max z=2x1+x2
5x2≤15
6x1+2x2≤24
x1+x2 ≤5
6、 x1,x2≥0
(1)寫出其對(duì)偶問題并化為標(biāo)準(zhǔn)型式;
(2)用單純形法求出原問題的最優(yōu)解;唯一最優(yōu)解
(3)根據(jù)最終單純形表寫出其對(duì)偶問題的最優(yōu)解,三種資源的影子價(jià)格各為多少并說明其涵義;
(4)若第三種資源增加3單位,問最優(yōu)解有何變化,資源的影子價(jià)格變?yōu)槎嗌佟?
8.運(yùn)輸問題
課后習(xí)題3.3(1)(2)
9.指派問題 課后習(xí)題5.7
10.最小樹問題 課后習(xí)題10.4,10.5
11.最短路問題 課后習(xí)題10.6 10.7
12.最大流問題:10.12,10.13
部分答案:
2.解:(1)其對(duì)偶問題為: 化成標(biāo)準(zhǔn)型式為:
7、
(2)原問題的準(zhǔn)標(biāo)準(zhǔn)型為:
用大M法求解
Cj
-2 -1 2 -2 M 0
θ
cB
xB
b
x2 x4 x5 x6 x7
M
0
X6
x7
4
6
[1] 1 1 -1 1 0
1 1 -1 1 0 1
4
6
檢驗(yàn)數(shù)σ
-2-M –1-M 2-M M-2 0 0
-2
0
X7
4
2
1 1 1 -1 1 0
0
8、 0 -2 [2] -1 1
-
1
檢驗(yàn)數(shù)σ
0 1 0 -4 M+2 0
-2
-2
X5
5
1
1 1 0 0 1/2 1/2
0 0 -1 1 -1/2 1/2
檢驗(yàn)數(shù)σ
0 1 0 0 M 2
所以,原問題的最優(yōu)解為:
4.解:設(shè)為每千克混合飼料中所含5種飼料的重量
目標(biāo)函數(shù)為:
約束條件有:
6.解:(1)首先設(shè)a、b、c表示對(duì)應(yīng)原模型的價(jià)值系數(shù),則由檢驗(yàn)數(shù)的計(jì)算
9、公式,得
解此方程組,得:a=6,b=-2,c=10
再由單純形表與原模型標(biāo)準(zhǔn)型的特點(diǎn),得
有這兩個(gè)關(guān)系式,可得:所以:愿問題的模型為:
(2)由原問題的模型,得到其對(duì)偶問題模型:
(3)由對(duì)偶理論,從原問題的最終單純形表中,直接得到對(duì)偶問題的最優(yōu)解:
7.(2)唯一最優(yōu)解
(3)其對(duì)偶問題的最優(yōu)解為:
第一種資源影子價(jià)格為0,第二種資源為1/4,第三種資源為1/2
其含義為:每增加一個(gè)單位的第一種資源,最優(yōu)值不會(huì)增加,每增加一個(gè)單位的第二種資源,最優(yōu)值增加1/4,每增加一個(gè)單位的第三種資源,最優(yōu)值會(huì)增加1/2。所以要想增加最優(yōu)值,可
10、以增加第二和第三種資源。
(4)第三種資源增加三個(gè)單位,=
新最優(yōu)解為:
13.有七個(gè)城市V1,V2,…,V7其公路網(wǎng)如下圖所示,弧旁數(shù)字為該段公路的長(zhǎng)度,有一批貨物要從V1運(yùn)到V7,試用迪克斯特拉算法或雙標(biāo)號(hào)法求出走那條路距離最短。
用狄克斯特拉算法或雙標(biāo)號(hào)法標(biāo)號(hào) (7分)
得到最短路路徑:V1—V3—V4—V5—V7(2分)
最短路路權(quán):10(1分)
14.幾個(gè)工地之間建立一個(gè)局域網(wǎng),由于條件不同,各工地間相連的費(fèi)用不同,如下圖所示,求A,B,C,D,E間的最小連線方案。(10分)
工地A
工地B
工地C
工地D
工地E
A
0
7
11
5
3
B
7
0
10
14
4
C
11
10
0
13
7
D
5
14
13
0
6
E
3
4
7
6
0
由對(duì)稱表格畫出連通圖(4分)
由破圈法或避圈法得到最小樹(4分),最小權(quán)和22(2分)