运筹学作业参考解答 第1页（共14页） 第二章 线性规划
73P 4. 将下面的线性规划问题化成标准形式
123
123
123
12max2
..236
23
0316xxx
stxxx
xxx
xx−+⎧⎪−+≥⎪⎪+−≤⎨⎪≤≤⎪⎪−≤≤⎩
解：将max 化为 min， 3x用45xx−代替，则
1245
1245
1245
1245min2()
..23()6
2()3
0316,0xxxx
stxxxx
xxxx
xxxx−+−−⎧⎪−+−≥⎪⎪+−−≤⎪⎨≤≤⎪⎪−≤≤⎪≥⎪⎩ 令221xx′=+，则1245
1245
1245
1245min12()
..2(1)3()6
2(1)()3
0307,0xxxx
stxxxx
xxxx
xxxx′−+−−−⎧⎪′−−+−≥⎪⎪′+−−−≤⎪⎨≤≤⎪⎪′≤≤⎪≥⎪⎩
将线性不等式化成线性等式，则可得原问题的标准形式
1245
12456
12457
18
29
12456789min221
..2334
24
3
7
,,,,,,,0xxxx
stxxxxx
xxxxx
xx
xx
xxxxxxxx′−+−+−⎧⎪′−+−−=⎪⎪′+−++=⎪⎨+=⎪⎪′+=⎪′≥⎪⎩
73P 5、用图解法求解下列线性规划问题：
(1) 121212min3..206122xxstxxxx+⎧⎪+≥⎪⎨≤≤⎪⎪≥⎩
解：图2.1的阴影部分为此问题的可行区域.将
目标函数的等值线123xxc+=(c为常数)沿它的
负法线方向()13T−−，移动到可行区域的边界上.
于是交点T），（812就是该问题的最优解，其最优
值为36.
75P 16. 用单纯形法求解下列线性规划问题：
等值线
20 12 8 X1
oX2 法线方向
图2.1
运筹学作业参考解答 第2页（共14页） (1) 123
123
123
123min2
..360
210
20
0,1,2,3jzxxx
stxxx
xxx
xxx
xj⎧=−−+⎪++≤⎪⎪−+≤⎨⎪+−≤⎪⎪≥=⎩
解：将此问题化成标准形式
摘要
本文研究的是线性规划的可行点算法，一个由线性规划的内点算法衍生而来的算法．
线性规划的内点算法是一个在线性规划的可行域内部迭代前进的算法．有各种各样的
内点算法，但所有的内点算法都有一个共同点，就是在解的迭代改进过程中，要保持所有
迭代点在可行域的内部，不能到达边界．
当内点算法中的迭代点到达边界时，现行解至少有一个分量取零值．根据线性规划的
灵敏度分析理论，对线性规划问题的现行解的某些分量做轻微的扰动不会改变线性规划问
题的最优解．故我们可以用一个很小的正数赋值于现行锯中等于零的分量，继续计算，就可
以解出线陛规划问题的最优解．这种对内点算法的迭代点到达边界情况的处理就得到了线
性规划的可行点算法．它是一个在可行域的内部迭代前进求得线性规划的最优解的算法．
在此算法中，只要迭代点保持为可行点．
本文具体以仿射尺度算法和原始一对偶内点算法为研究对象，考虑这两种算法中迭代
点到达边界的情况，得到相对应的’仿射尺度可行点算法’和’原始．对偶可行点算法，．在用
理论证明线性规划的可行点算法的可行性的同时，我们还用数值实验验正了可行点算法在
实际计算中的可行性和计算效果．
关键词：线性规划，仿射尺度算法，原始一对偶内点算法，内点，可行点算法，步长
可行点．Ａｂｓｔｒａｃｔ
Ｔｈｉｓ
Ｄａｐｅｒｆｏｃｕｓｅｓ
ｏｎａｆｅａｓｉｂｌｅ
ｐｏｉｎｔａｌｇｏｒｉｔｈｍｆｏｒｌｉｎｅａｒ
ｐｒｏｇｒａｍｍｉｎｇ，ａｎａｌｇｏｒｉｔｈｍｄｅｒｉｖｅｄ
ｆｒｏｍ
ｔｈｅ
ｉｎｔｅｒｉｏｒ
ｐｏｉｎｔａｌｇｏｒｉｔｈｍｓｆｏｒ
ｌｉｎｅｚａ＂ｐｒｏｇｒａｍｍｉｎｇ．
Ｔｈｅｉｎｔｅｒｉｏｒ
ｐｏｉｎｔａｌｇｏｒｉｔｈｍｓｆｉｎｄｔｈｅ
ｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｏｆｔｈｅｌｉｎｅａｒ
ｐｒｏｇｒａｍｍｉｎｇ
ｂｙ
ｓｅａｒｃｈｉｎｇ
ｗｉｔｈｉｎｔｈｅｆｅａｓｍｌｅ
Ｔｅ譬ｉｏｎｏｆｔｈｅｌｉｎｅａｒ
ｐｒｏｇｒａｍｍｉｎｇ．Ｔｈｅｒｅ
ａｒｅａＵｋｉｎｄｓｏｆｉｎｔｅｒｉｏｒ
ｐｏｉｎｔａｌｇｏｒｉｔｈｌｒｍ
11 判 断 题
判断正误，如果错误请更正
第二章 线形规划的对偶理论
1. 原问题第i个约束是<=约束,则对偶变量yi>=0.
2. 互为对偶问题,或则同时都有最优解,或则同时都无最优解.
3. 原问题有多重解,对偶问题也有多重解.
4. 对偶问题有可行解,原问题无可行解,则对偶问题具有无界解.
5. 原问题无最优解,则对偶问题无可行解.
6. 设X,Y分别为｛minZ=CX｜AX>=b,X>=0｝ 和｛maxw=Yb｜YA<=C,Y>=0｝ 的可行解,则有(1)CX<=Yb;
(2)CX是w的上界;
(3)当X,Y为最优解,CX=Yb;
(4)当CX=Yb 时,有YXs+YsX=0;
(5)X为最优解且B是最优基时,则Y=CB-1是最优解;
(6)松弛变量Ys的检验数是λs,则X=-λs是基本解,若Ys是最优解, 则X=-λs是最优解.
7.原问题与对偶问题都可行,则都有最优解.
8.原问题具有无界解,则对偶问题可行.
9.若X,Y是原问题与对偶问题的最优解.则X=Y.
10.若某种资源影子价格为0,则该资源一定有剩余.
11影子价格就是资源的价格.
12.原问题可行对偶问题不可行,可用对偶单纯形法计算.
13.对偶单纯形法比值失效说明原问题具有无界解.
14.对偶单纯形法是直接解对偶问题的一种解法.
15.减少一个约束,目标值不会比原来变差.
16.增加一个约束,目标值不会比原来变好.
22 17增加一个变量, 目标值不会比原来变差.
18.减少一个非基变量, 目标值不变.
19.当Cj(j=1,2,3,……，n)在允许的最大范围内同时变化时，最优解不变。
选择题
在下列各题中，从4个备选答案中选出一个或从5个备选答案中选出2~5个正确答案。
第二章 线性规划的对偶理论
1. 如果决策变量数列相等的两个线规划的最优解相同，则两个线性规划 A约束条件相同
B目标函数相同 C最优目标函数值相同 D以上结论都不对
线性规划的基本的内容和线性规划数学模型
定义：
线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法，英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。
数学模型
(1)列出约束条件及目标函数 线性规划步骤
(2)画出约束条件所表示的可行域
(3)在可行域内求目标函数的最优解及最优值
解法求解线性规划问题的基本方法是单纯形法，现在已有单纯形法的标准软件，可在电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题。为了提高解题速度，又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。对于只有两个变量的简单的线性规划问题，也可采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解，但实用价值不大。通过图解法求解可以理解线性规划的一些基本概念。
对于一般线性规划问题： 图解法解线性规划问题
Min z=CX
S.T.
AX =b
X>=0
其中A为一个m*n矩阵。
若A行满秩
则可以找到基矩阵B，并寻找初始基解。
用N表示对应于B的非基矩阵。则规划问题1可化为：
规划问题2：
Min z=CB XB+CNXN
S.T. 线性规划法解题
B XB+N XN = b (1)
XB >= 0, XN >= 0 (2)
(1)两边同乘于B-1，得
XB + B-1 N XN = B-1 b
同时，由上式得XB = B-1 b - B-1 N XN，也代入目标函数，问题可以继续化为：
规划问题3：
Min z=CB B-1 b + ( CN - CB B-1 N ) XN
