大学运筹学课程知识点总结.doc

1. 用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。
２。将下述线性规划问题化成标准形式。
　　（1)
　　 解:令,
3。分别用图解法和单纯形法求解下述线性规划问题,并对照指出单纯形表中的各基可行解对应图解法中的可行域的哪个顶点。
解:①图解法:
②单纯形法:将原问题标准化:
Cj
10
5
0
0
q
对应图解法中的点
CB
B
ｂ
x1
ｘ2
x3
x４
0
ｘ３
９
3
4
１
０
3
O点
0
ｘ4
8
［5]
2
0
１
8/５
sj
0
10
5
0
0

0
ｘ3
21/5
0
[1４/5]
1
-3/5
3／2
C点
１0
x１
８／5
1
2／５
0
1/5
4
sj
－16
０
1
0
-２

5
ｘ2
3/２
0
1
５／14
—３/1４

Ｂ点
1０
x1
１
1
0
－1/７
2／７

sj
35／2
０
０
—５/1４
-２5/1４

最优解为（1,3/2,0,0)，最优值Z＝３5/２.
单纯型法步骤：转化为标准线性规划问题;找到一个初始可行解,列出初始单纯型表；最优性检验，求cｊ－zj,若所有的值都小于0，则表中的解便是最优解,否则,找出最大的值的那一列，求出ｂi／aiｊ,选取最小的相对应的ｘij,作为换入基进行初等行变换,重复此步骤。
4.写出下列线性规划问题的对偶问题。
（1)
（2)
5。 给出线性规划问题
要求:（１)写出其对偶问题；（2）已知原问题最优解为,试根据对偶理论，直接求出对偶问题的最优解。
解：
(１)
(２)因为,第四个约束取等号,根据互补松弛定理得:
求得对偶问题的最优解为：，最优值min ｗ＝1６。
弱对偶性的推论：
(１) 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界;反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界
(２) 如原问题有可行解且目标函数值无界(具有无界解）,则其对偶问题无可行解;反之对偶问题有可行解且目标函数值无界,则其原问题无可行解。
注意：本点性质的逆不成立,当对偶问题无可行解时,其原问题或具有无界解或无可行解，反之亦然。
(3） 若原问题有可行解而其对偶问题无可行解,则原问题目标函数值无界;反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。
强对偶性(或称对偶定理)
若原问题及其对偶问题均具有可行解，则两者均具有最优解,且它们最优解的目标函数值相等。
互补松弛性
在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式;反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。
影子价格
资源的市场价格是其价值的客观体现,相对比较稳定,而它的影子价格则有赖于资
源的利用情况,是未知数。因企业生产任务、产品结构等情况发生变化,资源的影
子价格也随之改变．
影子价格是一种边际价格。
资源的影子价格实际上又是一种机会成本。随着资源的买进卖出，其影子价格也将
随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。
生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零;又当资源
的影子价格不为零时,表明该种资源在生产中已耗费完毕．
影子价格反映单纯形表中各个检验数的经济意义。
一般说对线性规划问题的求解是确定资源的最优分配方案,而对于对偶问题的求解则是确定对资源的恰当估价,这种估价直接涉及资源的最有效利用
对偶单纯型法:转化成标准的线性规划问题；确定换入基变量,ｂｉ小于０中的最小的那一排，再求（cｊ—zｊ）／aij,且aij〈0，找出最小值，这对应的ｘｉ便是换入基，若所有的bi都大于０,则找到了最优解
7　下列表分别给出了各产地和各销地的产量和销量,以及各产地至各销地的单位运价,试用表上作业法求最优解。
　　 　 　注意要基可行解的个数一定是行列变量数减一
销地
产地
Ｂ1
Ｂ２
B３
B4
产量
A1
４
1
4
6
8
A２
1
2
5
0
8
Ａ３
3
7
５
1
4
销量
6
5
６
3
２0
解:
(1)确定初始方案
西北角法:
销地
产地
B１
B2
Ｂ3
B4
产量
A1
６
2

８
A2

3
5

8
A３

1
3
4
销量
６
5
6
3
2０
最小元素法:
销地
产地
B1
B2
B3
B4
产量
A１

５
3

8
Ａ２
5

3
8
A3
1

3

4
销量
6
５
6
３
20
沃格尔法:
销地
产地
B1
B２
B３
Ｂ4
产量
行罚数
1
２
3
4
Ａ1

4

1

4

6
８

０
２
２

５

３

Ａ２

１

2

5

0
8
１
1

６

２

A3

3

７

5

１
４
1
２
4
４

3

１

销量
６
5
6
3
2０
列
罚
数
１
２
1
1
1
2

１
1
3

１
1
4

１

8。下表给出一个运输问题及它的一个解,试问:
（1)表中给出的解是否为最优解？请用位势法进行检验.
（２)若价值系数C24由1变为3，所给的解是否仍为最优解?若不是,请求出最优解。
(3)若所有价值系数均增加1,最优解是否改变?为什么?
(4)若所有价值系数均乘以2，最优解是否改变？为什么?
销地
产地
B１
Ｂ2
Ｂ3
B4
产量
Ａ1

4

1

4

6
8

５

3

A2

１

2

６

1
10
8

2

A３

３

7

5

1
4

3

１

销量
8
5
6
3
2２
解：（1)
销地
产地
Ｂ1
B2
Ｂ3
Ｂ4
产量
uｉ
A1

4

1

4

6
8
0

５

3

A2

1

2

6

1
１0
１
８

2

A3

3

7

5

1
４
１

3

１

销量
8
5
6
３
２２

vj
0
1
4
０

空格检验数为：
４

６

０
1

２
5

所有检验数均大于等于零，该方案为最优方案。
(２)若价值系数C24由1变为３,
６

6

—２
—1

４
5

由于有检验数小于零，所以此方案不是最优方案。

5(-２)
3(+２)

8
(+２）

２(—2）

３(-2)
１(+2）
调整为:

3
5

8
２

１
３
空格检验数为:
4

６

1
2
２
５

所有检验数均小于等于零,该方案为最优方案。
。
(3)不改变，不影响检验数的大小．
(4）不改变,不影响检验数的符号。
解的最优性检验:
１。闭回路法:找各个非基变量的闭合回路，依次加减求检验数,是先减再加,若所有的检验数的值都全非负,那么此可行解是最优解。
２.位势法(对偶变量法)：增加位势列ui和位势行vj;计算位势,ui＋vj=基可行解的对应的运费,指定其中某一值为0,算出其他几位的值,填入表中;计算检验数,某非基变量对应的运费减对应的位势行和位势列,若检验数全为非负，则为最优解。
(检验数都是非基变量经过处理后的值，处理过程中应用的是基变量)
解的改进:1。以检验数小于0的xｉ为换入基（取最小的那个)
2. 找此xi的闭合回路,以ｘi为始沿顺逆时针方向把定点依次编号
3. 在所有偶数顶点中,找出运输量最少的顶点作为xｉ的换出变量
4. 将基数顶点的运输量增加ｘｊ，偶数顶点的运输量减少ｘj，重新得到一组新的方案
5. 进行解的最优性检验
９.公司决定使用１０0０万元新产品开发基金开发Ａ,B,C三种新产品。经预测估计，开发A,B,C三种新产品的投资利润分别为5%、7%、1０%。由于新产品开发有一定风险，公司研究后确定了下列优先顺序目标:
第一,Ａ产品至少投资300万元;
第二,为分散投资风险,任何一种新产品的开发投资不超过开发基金总额的35%;
第三,应至少留有1０%的开发基金，以备急用;
第四,使总的投资利润最大。
试建立投资分配方案的目标规划模型。
解，设A,B，Ｃ三种新产品的开发投资额分别为万元,目标规划模型为:
Pｌ是优先因子,关系为l越小，则有绝对的优先性，还有一种是相对的优先性,用权系数来表示
目标规划的一般格式;min{ｐｌd+或d－｝（要明白为什么是写d+或d—,mｉn里的d是要取值为零的，即若不等式要大于零时,则写d-)；必须要满足的绝对约束，还有目标约束；xｊ＞０,ｄ＋,ｄ->0
目标规划的图解法:先画绝对约束的可行域,然后按照优先性优先考虑某个目标约束,随着mｉｎ系数中d+或者d—的增大移动曲线，画出最合适的那条，直到最后
１0。用割平面法解下列整数规划:
(1)
解：引进松弛变量，将问题化为标准形式,用单纯形法解其松弛问题。
cｊ
1
1
0
0
q
ＣB
ＸＢ
b
x1
x２
ｘ３
ｘ4
0
x３
6
【２】
1
1
0
3
０
x４
２０
4
５
0
１
5
sｊ
1
１
0
0

１
x１
３
1
１/2
1/2
0
６
0
x４
8
0
【3】
—2
1
8／3
sj
0
1/2
-1／2
0

１
ｘ1
5/３
1
0
5/６
-1/6

1
x２
8/３
0
1
-2／3
1/3

sj
０
0
-１／６
－1/6

找出非整数解变量中分数部分最大的一个基变量（x２）,并写下这一行的约束:
将上式中的所有常数分写成整数与一个正的分数值之和得：
将上式中的分数项移到等式右端,整数项移到等式左端得:
得到割平面约束为:
引入松弛变量，得割平面方程为：
ｃｊ
１
1
0
0
０
CB
ＸB
b
ｘ1
ｘ２
x３
x４
x5
1
x１
5/3
1
0
5/6
-1／6
0
1
x２
8／3
0
1
—２／3
1／3
０
0
x５
—2/３
0
0
【—1/３】
-1/3
1
sj
0
0
—1/６
－1/6
0
sj/arj

1／２
1/２

1
x1
0
１
0
0
-１
5/2
１
x２
4
0
１
０
１
—２
0
x3
２
0
０
1
1
—3
sj
0
0
0
0
—1／2
最优解为，最优值为
s4=0,最优解不唯一?
1１。用分支定界法解下列整数规划
（１）
解：
最优解（3,１）,最优值ｚ=7。
12. 匈牙利解法:见课本1４5页
13.如图，是一仓库，是商店,求一条从到的最短路。
解：

P＝T＝0
Ｔ=¥
T=¥
Ｔ=¥
T=¥
Ｔ=¥
Ｔ＝¥
Ｔ=¥
T=¥
T＝¥

P＝T=2
Ｔ＝¥
Ｔ=11
T=¥
Ｔ=７
T=¥
Ｔ=４
Ｔ＝¥
T＝¥

Ｔ=13
T＝１1
Ｔ＝¥
T=7
T=¥
P=T＝4
T＝¥
T=¥

T＝１３
Ｔ=1１
T＝¥
P＝Ｔ=7
Ｔ=11

Ｔ＝13
Ｔ＝¥

Ｔ=13
Ｐ=Ｔ=１1
Ｔ=¥

T=１1

T=１3
T＝¥

T=13

T=1６

P=Ｔ=11

T=13
T＝¥

Ｐ=T=13

T=1６

T＝13
T=２0

T=16

Ｐ=T=１3
T=１9

P=Ｔ＝１６

T=１9

P=１９
最短路长为19。最短路为:０12９,0３29,0349,０１24９，０７89．
14.如图,发点,分别可供应10和15个单位,收点,可以接收1０和２5个单位，求最大流,边上数为。
最大流为２1
15.如图所示网络中，有向边旁数字为，表示容量,表示单位流量费用,试求到流值为六的最小费用流。
解：d(f)=3７
16. 图的生成树：
（一)避圈法
在图中任取一条边ｅ１，找一条与e１不构成圈的边e2,再找一条与{e１,e２}不构成圈的边e3。一般设已有｛ｅ1,ｅ2，…,ｅｋ},找一条与{e１,e2，…，eｋ}中任何一些边不构成圈的边ek＋1,重复这个过程，直到不能进行为止。
(二)破圈法