第二章线性规划的对偶理论
2.1 写出下列线性规划问题的对偶问题
max z=2x1+2x2－4x3
x1 + 3x2 + 3x3 ≤30
4x1 + 2x2 + 4x3≤80
x1、x2，x3≥0
解：其对偶问题为
min w=30y1+ 80y2
y1+ 4y2≥2
3y1 + 2y2 ≥2
3y1 + 4y2≥－4
y1、y2≥0
2.2 写出下列线性规划问题的对偶问题
min z=2x1+8x2－4x3
x1 + 3x2－3x3 ≥30
－x1 + 5x2 + 4x3 = 80
4x1 + 2x2－4x3≤50
x1≤0、x2≥0，x3无限制
解：其对偶问题为
max w=30y1+80 y2+50 y3
y1－y2 + 4 y3≥2
3y1+5y2 + 2y3≤8
－3y1 + 4y2－4y3 =－4
y1≥0，y2无限制，y3≤0
2.3已知线性规划问题
max z=x1+2x2+3x3+4x4
x1 + 2x2 + 2x3 +3x4≤20
2x1 + x2 + 3x3 +2x4≤20
x1、x2，x3，x4≥0
其对偶问题的最优解为y1*=6/5，y2*=1/5。试用互补松弛定理求该线性规划问题的最优解。
解：其对偶问题为
min w=20y1+ 20y2
y1 + 2y2≥1 （1）
2y1 + y2 ≥2 （2）
2y1 +3y2≥3 （3）
3y1 +2y2≥4 （4）
y1、y2≥0
将y1*=6/5，y2*=1/5代入上述约束条件，得（1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。又因y1*>0，y2*>0，故原问题的两个约束条件应取等式，所以
2x3*+3x4* = 20
3x3* +2x4* = 20
解得x3* = x4* = 4。故原问题的最优解为
X*=（0，0，4，4）T
2.4用对偶单纯形法求解下列线性规划
min z=4x1+2x2+6x3
2x1 +4x2 +8x3 ≥24
4x1 + x2 + 4x3≥8
x1、x2，x3≥0
解将问题改写成如下形式
max（－z）=－4x1－2x2－6x3
－2x1－4x2 －8x3 + x4=－24
－4x1－x2－4x3+x5 =－8
x1、x2，x3，x4，x5≥0
显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正侧基。整个问题的计算过程列在表2—7中。
最后一个单纯形表中，已得到一个可行的正侧解，因而得到问题的最优解为
X*=（0，4，4）T
最优值为z*=32
2.5设某线性规划问题的初始单纯形表和最优单纯形表分别为
现在要问：
（1）c3在什么范围内变化，表中最优解不变？
（2）c3从3变为8，求新的最优解
解（1）由于在最优单纯形表中，c3为非基变量的价格系数，因此其变化仅会影响到检验数σ3=－4，因此当Δc3≤－σ3=4时，表中最优解不变。
（2）当c3从3变为8时，则表中的检验数σ3从—4变为1，即表中的最优解将发生变化，用单纯形法求解得到如表2—11中所示的新的最优解。
即新的最优解为X=（0，160/3，20/3）。
2.6某工厂在计划期内要安排甲、乙两种产品，已知生产一件产品所消耗的A、
B、C三种原材料的数量以及单位产品的利润如下表所示：
若x1、x2分别表示工厂生产甲、乙产品的数量，则使工厂获得最大利润的生产计划数学模型为：
max z=5x1+4x2
x1 +3x2 ≤90
2x1 + x2≤80
x1 + x2≤45
x1、x2，x3≥0
用单纯形法求解该问题时，其初始单纯形表和最优单纯形表分别如表2—13和3—14所示，试分析使最优基不变的b3的变化范围。
解 由表2—13和表2—14可知，当B=（p 3，p 1，p 2）时，有
????
?
?
?---=-21
01105211
B
????
? ??=-1035
25
1
b B 当下式成立时，最优基不变。
010355250
21
01105211035
25333
3
1
1≥????
?
?
??+?-?-=????? ???????? ?
?---+????? ?
?=?+--b
b b b b B b B
即 25－5Δb 3≥0，35－Δb 3≥0，10+Δb 3≥0 解不等式有
－5≤Δb 3≤5 此外，以B -1的第三列各元素去除最优单纯形表中右端常数项对应各列，用公式可直接求出Δb 3，即
??????----≤?≤??????-525,1
35
min 210max b
同样可得 －5≤Δb 3≤5
因此，不影响最优基的b 3的变化范围是[40，50]。
2.7 在例2.11的生产计划问题中：（1）若生产产品甲的工艺结构发生了改进，
这时关于它的技术向量变为p 1‘
=（1，2，1/2）T ，试分析对原最优计划有什么影响；（2）若该厂除了生产前两种产品外，拟开发新产品丙，已知产品丙每件消耗A 、B 、C 原材料各为2、4、1kg ，每件可获利润8千元。问该厂是否应该生产该产品和生产多少？
解 （1）由于产品甲生产工艺的改进，这样原最优单纯形表中的第1列将会发生改变，具体为
??
??
?
??=????? ??????? ?
?---=-02/12/12/11121
0110
521'
11p B
代入原最优单纯形表中得到
将第1列化为单位向量，并用对偶单纯形法迭代一次得到如表2—16所示的新的最优生产计划。
（2）设新产品的产量为x 3‘（件），其技术系数向量为p 3‘
=（2，4，1）T ，由表2—14可求出
σ3‘= c 3’－C B B -1p j ‘
= 8－（0，1，3）（2，4，1）T =1>0
即安排生产产品丙是有利的。
对应x 3‘
在最优单纯形表中的列向量为
??
??
?
??-=????? ??????? ?
?---=-23514221
0110
521'
11p B
代入到最优表2—14中，并用单纯形法迭代一次得新的最优表2—17。
由表2—17，得最优解
X*=（20，20，5）T
即该工厂生产产品甲、乙、丙分别为20，20，5件，可使工厂获得最大利润220千元。
2.8红旗商场是个中型的百货商场，它对售货人员的需求经过统计分析如表2—18所示。为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作需要又使配备的售货人员的人数最少？（只建模型，不求解）
表2—18
解：设x1为星期一开始上班的人数，x2为星期二开始上班的人数， (x7)
期日开始上班的人数。我们的目标是要求售货人员的总数最少。因为每个售货员都工作五天，休息两天，所以我们只要计算出连续工作五天的售货人数，也就计算出了售货员的总数。我们把连续工作五天的售货员按照开始工作的时间分成7类，各类的人数分别为x1，x2，…，x7，即有
目标函数：min x1+x2+x3+x4+x5+x6+x7.
我们再按照每天所需售货员的人数写出约束条件，例如星期日需要28人，我们知道商场中的全休售货员中除了星期一开始上班和星期二开始上班的人外都应该上班，即有x3+x4+x5+x6+x7≥28，这样我们就建立了如下的数学模型：
目标函数：min x1+x2+x3+x4+x5+x6+x7
x3+x4+x5+x6+x7≥28
x4+x5+x6+x7+x1≥15
x5+x6+x7+x1+x2≥24
x6+x7+x1+x2+x3≥25
x7+x1+x2+x3+ x4≥19
x1+x2+x3+x4+x5≥31
x2+x3+x4+x5+x6≥28
x1、x2、x3、x4、x5、x6、x7≥0
运筹学作业2（第二章部分习题）答案 2．4 给出线性规划问题 123412341234min 2356232.. 2330,1,2,3,4 j z x x x x x x x x s t x x x x x j =+++?+++≥? -+-+≤-??≥=? （1）写出其对偶问题；（2）用图解法解对偶问题；（3）利用（2）的结果及根据对偶问 题性质写出原问题的最优解。 解：（1）原问题的对偶问题为： 12 12121212 12max 2322 23.. 35 36 0,0 w y y y y y y s t y y y y y y =--≤??+≤?? -≤??+≤??≥≤? 或者等价变形为： 12 12121212 12max 232223..3536 0,0 w y y y y y y s t y y y y y y =++≤??-≤?? +≤??-≤??≥≥? （2）用图解法求解对偶问题 12 12121212 max 2322 23.. 3536 w y y y y y y s t y y y y =++≤??-≤?? +≤??-≤ 如图示，可行区域为四边形OABC ，最优顶点为B 点，即(1.6,0.2)y * =， 3.8w * =
（3）利用互补松紧定理及（2）的结果求解原问题： 设原问题的最优解为( )1 23 4x x x x x ** ***=。 由于121.60, 0.20y y * * =>=>，故在最优解()12 3 4x x x x x ** * **=处有： 1234 1234232 2330,1,2,3,4j x x x x x x x x x j ******** * ?+++=??-+-+=-??≥=?? 又因对偶问题第4个约束方程为：1.6-0.6=1<6，故40x * =，代入上式得到： 123 123232 230,1,2,3,4j x x x x x x x j ****** * ?++=??-+-=-??≥=?? 原问题有无穷多个最优解。令30x *=得到解为1 1.6x *=，20.2x *= 即()1.60.200x * =， 3.8z * = 2．8题解答见课堂讲解。 2．9 用对偶单纯形法求解下列线性规划问题： （2） 123 123123123min 524324 .. 63510,,0z x x x x x x s t x x x x x x =++++≥?? ++≥??≥? , 解：先将原问题进行标准形化： 1231234123512345max()524324 .. 63510,,,,0 z x x x x x x x s t x x x x x x x x x -=---++-=?? ++-=??≥? 选45,x x 为基变量，并将问题化为： 1231234123512345max()524324 .. 63510,,,,0z x x x x x x x s t x x x x x x x x x -=------+=-?? ---+=-??≥? 列表计算如下：
课程名称：对偶单纯形法 一、教学目标 在对偶单纯形法的学习过程中，理解和掌握对偶问题；综合运用线性规划和对偶原理知识对对偶单纯形法与单纯形法进行对比分析，了解单纯形法和对偶单纯形法的相同点和不同点，总结出各自的适用范围；掌握对偶单纯形法的求解过程；并能运用对偶单纯形法独立解决一些运筹学问题。 二、教学内容 1) 对偶单纯形法的思想来源(5min) 2) 对偶单纯形法原理(5min) 3) 总结对偶单纯形法的优点及适用情况(5min) 4) 对偶单纯形法的求解过程(10min) 5) 对偶单纯形法例题(15min) 6) 对比分析单纯形法和对偶单纯形法(10min) 三、教学进程： 1）讲述对偶单纯形法思想的来源： 1954年美国数学家C.莱姆基提出对偶单纯形法（Dual Simplex Method ）。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。 2）讲述对偶单纯形法的原理 A.对偶问题的基本性质 依照书第58页，我们先介绍一下对偶问题的六个基本性质： 性质一：弱对偶性 性质二：最优性。如果 x j （j=1...n)原问题的可行解，y j 是其对偶问题可 行解，且有 ∑=n j j j x c 1 =∑=m i i i y b 1 ，则x j 是原问题的最优解，y j 是其对偶问题的最
优解。 性质三：无界性。如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）无可行解。 性质四：强对偶性。如果原问题有最优解，则其对偶问题也一定有最优解。 性质五：互补松弛型。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。 性质六：线性规划的原问题及其对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w. B.对偶单纯形法（参考书p64页） 设某标准形式的线性规划问题，对偶单纯形表中必须有c j -z j ≤0（j=1...n),但b i (i=1...m)的值不一定为正，当对i=1...m ，都有b i ≥0时，表中原问题和对偶问题均为最优解，否则通过变换一个基变量，找出原问题的一个目标函数值较小的相邻的基解。 3）为什么要引入对偶单纯形法 从理论上说原始单纯形法可以解决一切线性规划问题，然而实际问题中，由于考虑问题的角度不同，变量设置的不同，便产生了原问题及其对偶问题，对偶问题是原问题从另外一个角度考虑的结果。用对偶单纯形法求解线性规划问题时，当约束条件为“≥”时，不必引入人工变量，使计算简化。 例如，有一线性规划问题： min ω =12 y 1 +16y 2 +15 y 3 约束条件 ?? ?? ???≥=≥+≥+0)3,2,1(3522 423121 i y y y y y i
运 筹 学 考 卷 1 / 51 / 5
考试时间: 第十六周 题号一二三四五六七八九十总分 评卷得分 ： 名 一、单项选择题。下列每题给出的四个答案中只有一个是正确的，将表示正确 姓 答案的字母写这答题纸上。（10 分, 每小题2 分） 1、使用人工变量法求解极大化线性规划问题时，当所有的检验数j 0 ，在 线 基变量中仍含有非零的人工变量，表明该线性规划问题（） A. 有唯一的最优解； B. 有无穷多个最优解； C. 无可行解； D. 为无界解 2、对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中（）： 号 A．b 列元素不小于零B．检验数都大于零 学 C．检验数都不小于零D．检验数都不大于零 3、在产销平衡运输问题中，设产地为m 个，销地为n 个，那么基可行解中非 零变量的个数（） 订 A. 不能大于(m+n-1)； B. 不能小于(m+n-1)； C. 等于(m+n-1)； D. 不确定。 4、如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足（） A. d 0 B. d 0 C. d 0 D. d 0,d 0 5、下列说法正确的为（） ： 业 A．如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解 专 B．如果线性规划的对偶问题无可行解，则原问题也一定无可行解 装 C．在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原 问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数 D．如果线性规划问题原问题有无界解，那么其对偶问题必定无可行解 ： 院
学 2 / 52 / 5
二、判断下列说法是否正确。正确的在括号内打“√”，错误的打“×”。（18 分，每 小题2 分） 1、如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。（） 2、单纯形法计算中，如不按最小比列原则选取换出变量，则在下一个解中至少有一 个基变量的值为负。（） 3、任何线性规划问题存在并具有惟一的对偶问题。（） 4、若线性规划的原问题有无穷多最优解，则其最偶问题也一定具有无穷多最优解。 （）5、运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之 一：有惟一最优解，有无穷多最优解，无界解，无可行解。（） 6、如果运输问题的单位运价表的某一行（或某一列）元素再乘上那个一个常数k ， 最有调运方案将不会发生变化。（） 7、目标规划模型中，应同时包含绝对约束与目标约束。（） 8、线性规划问题是目标规划问题的一种特殊形式。（） 9、指派问题效率矩阵的每个元素都乘上同一常数k，将不影响最优指派方案。（） 三、解答题。（72 分） max z 3x 3x 1 2 1、（20分）用单纯形法求解 x x 1 2 x x 1 2 4 2 ；并对以下情况作灵敏度分析：（1）求 6x 2 x 18 1 2 x 0, x 0 1 2 5 c 的变化范围；（2）若右边常数向量变为2 b ，分析最优解的变化。 2 20 2、（15 分）已知线性规划问题： max z x 2x 3x 4x 1 2 3 4 s. t. x 2x 2x 3x 20 1 2 3 4 2x x 3x 2x 20 1 2 3 4 x x x x , , , 0 1 2 3 4 其对偶问题最优解为y1 1.2, y2 0.2 ，试根据对偶理论来求出原问题的最优解。
第二章 对偶问题与灵敏度分析 一、写出下列线性规划的对偶问题 1、P89,2.1(a) 321422min x x x Z ++= s.t ???????≥=++≤++≥++.,0,;534;332;2433213213 21321无约束 x x x x x x x x x x x x 解：原模型可化为 321422min x x x Z ++= s.t ????? ? ?≥=++≥≥++.,0,;534; 3-3--2-;24332 13 2 1 321321321无约束x x x y y y x x x x x x x x x 于是对偶模型为 321532max y y y W +-= s.t ???????≥≤+-≤+-≤+-.,0,;4334;243;223213213 21321无约束 y y y y y y y y y y y y 2、P89,2.1(b) 321365max x x x Z ++= s.t ???????≤≥≤++≥-+-=++.0,0,;8374;35;5223213213 21321x x x x x x x x x x x x 无约束 解：令033≥-='x x 原模型可化为 3 21365max x x x Z '-+=
s.t ????? ??≥'≥≤'+≤'='+.0,0,;83-74;3--5-;52-2321 3 21 3213 21321x x x y y y x x x x x x x x x 无约束 于是对偶模型为 321835min y y y W +-= s.t ?? ?????≥-≥---≥+-=++.0,,;332; 6752; 543213213 21321y y y y y y y y y y y y 无约束 或???????≥≤++≥+-=++.0,,;332;6752;54321321321321y y y y y y y y y y y y 无约束 二、灵敏度分析 1、P92, 2.11线性规划问题 213max x x Z += s.t ??? ??≥≤+≤+0,1025; 742 12121x x x x x x 最优单纯形表如下 C J 3 1 0 0 C B X B b x 1 x 2 x 3 x 4 3 x 1 4/3 1 0 2/3 -1/3 1 X 2 5/3 0 1 -5/3 4/3 j σ -1/3 -1/3 试用灵敏度分析的方法，分析： （1） 目标函数中的系数21,c c 分别在什么范围内变化，最优解不变？ （2） 约束条件右端常数项21,b b 分别在什么范围内变化，最优基保持不变？ 解：（1） 1c 的分析：要使得最优解不变，则需
习题 某厂利用A、B两种原料生产甲、乙、丙三种产品，已知单位产品所需的原料、利润及有关数据如表2—3所示。 产品甲产品乙产品丙拥有量原料A63545 原料B34530 单位利润415 （1）求使该厂获利最大的生产计划。 （2）若产品乙、丙的单位利润不变，当产品甲的单位利润在什么范围内变化时，最优解不变 （3）若原料A市场紧缺，除拥有量外一时无法购进，而原料B如数量不足可去市场购买，单价为，问该厂是否应该购买，且以购进多少为宜 解：（1）设产品甲的产量为x1，产品乙的产量为x2，产品丙的产量为x3. 目标函数为:Max z=4 x1 + x2+5 x3 约束条件：. 该线性规划模型为： 答：该厂获利最大的生产计划为产品甲产量为5，产品乙产量为0，产品丙产量为3，总利润为35。 （2）敏感性报告为：
答：如数据显示，产品甲的单位利润变化范围为：。 （3）敏感性报告为： 由敏感性报告显示原料B允许的增量为15，其影子价格为，又因为市场上原料B 单价为，此时，总利润为。 答：该厂可购买15。 习题 已知某工厂计划生产三种产品，各产品需要在设备A、B、C上加工，有关数据如表2—5所示。 产品A产品B产品C每月设备有效台时 设备A8210300 设备B1058400 设备C21310420 单位利润（千元）32 请分别回答下列问题： (1)如何充分发挥设备能力，才能使生产盈利最大 (2)为了增加产量，可借用其他工厂的设备B，若每月可借用60台时，租金为万 元，问借用设备B是否合算 (3)若另有两种新产品（产品4和产品5），其中生产每件新产品4需用设备A、 B、C各12、5、10台时，单位赢利千元；生产每件新产品5需用设备A、B、 C各4、4、12台时，单位赢利千元。如果设备A、B、C台时不增加，分别回答这两种新产品的投资在经济上是否合算 (4)对产品工艺重新进行设计，改进构造。改进后生产每件产品1，需用设备A、 B、C各9、12、4台时，单位赢利千元，问这对原生产计划有何影响
第三章线性规划对偶理论与灵敏度分析习题 一、思考题 1．对偶问题和对偶变量的经济意义是什么？ 2．简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？ 3．什么是资源的影子价格？它和相应的市场价格之间有什么区别？ 4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系？ 5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？ 6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）0>+k n x ，其经济意 义是什么？ 7．在线性规划的最优单纯形表中，松弛变量k n x +的检验数0>+k n σ（标准形为 求最小值），其经济意义是什么？ 8．将i j j i b c a ,,的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 将会出现什么变化？有多少种不同情况？如何去处理？ 二、判断下列说法是否正确 1．任何线性规划问题都存在且有唯一的对偶问题。 2．对偶问题的对偶问题一定是原问题。 3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。 4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。 5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。 6．已知在线性规划的对偶问题的最优解中，对偶变量0>* i y ，说明在最优生产计 划中，第i 种资源已经完全用尽。 7．已知在线性规划的对偶问题的最优解中，对偶变量0=*i y ，说明在最优生产计 划中，第i 种资源一定还有剩余。 8．对于i j j i b c a ,,来说，每一个都有有限的变化范围，当其改变超出了这个范围 之后，线性规划的最优解就会发生变化。 9．若某种资源的影子价格为u ，则在其它资源数量不变的情况下，该资源增加k 个单位，相应的目标函数值增加 u k 。 10．应用对偶单纯形法计算时，若单纯形表中某一基变量0第二章习题运筹学
第二章习题 12、对于下面的线性规划问题，以()632,,A A A B =为基写出相对应的典式。 ???? ? ?? ??=≥=+++-=++-=++-+-61,010 8341242723..2min 6 3215214321321 j x x x x x x x x x x x x t s x x x j 解：由题可以知： ???? ? ?????---=100834010042001213A []000121-=T C 取一个基()65 4 A A A B =，即：??????????-=183004021B 且???? ? ?????---=834042213N []012-=T B C []001=T N C 在matlab 中可以计算得到： ?? ????? ?????????--=-14740812104101 B []T b B b 39531-==- 1-=b C T B ?? ?? ??-=--832 1 4 51T N T B C N B C 由() N T N T B T B x C N B C b C Z --=-1可得典式的目标函数： 5418 3 21451x x x Z +---= 由b Nx B x N B =+-1可得：
???? ?? ???-=+---=+++=++-39474225 581214 5 34 121 6541 54 3152 1x x x x x x x x x x x 由此与题中线性规划问题相对应的典式为： ?? ????? ?? ????? ? =≥-=+---=+++=++-+---=6,,1,039 4742255 812145341 21..8321451min 65415431521541 j x x x x x x x x x x x x t s x x x Z j 14、用单纯形法求解线面的线性规划问题，并在平面上画出迭代点走过的路线。 ????? ??????≥≤≤+≤+≤+--=0 ,10443186052..2min 21221212121x x x x x x x x x t s x x z 解：由题先将题中线性规划问题化为标准形： ?? ??? ? ???? ?=≥=+=++=++=++--=6,,1,010*********..2min 625214213212 1 j x x x x x x x x x x x x t s x x z j 由此可写出A ，即为：????? ???? ???=10 0010 010********* 000152A
判断题 判断正误，如果错误请更正 第二章线形规划的对偶理论 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.增加一个约束,目标值不会比原来变好.
17增加一个变量, 目标值不会比原来变差. 18.减少一个非基变量, 目标值不变. 19.当Cj(j=1,2,3,……，n)在允许的最大范围内同时变化时，最优解不变。 选择题 在下列各题中，从4个备选答案中选出一个或从5个备选答案中选出2~5个正确答案。 第二章线性规划的对偶理论 1.如果决策变量数列相等的两个线规划的最优解相同，则两个线性规划 A约束条件相同 B目标函数相同 C最优目标函数值相同 D以上结论都不对 2.对偶单纯形法的最小比值规则是为了保证 A使原问题保持可行 B使对偶问题保持可行 C逐步消除原问题不可行性 D逐步消除对偶问题不可行性 3.互为对偶的两个线性规划问题的解存在关系 A若最优解存在，则最优解相同 B原问题 无可行解，则对偶问题也无可行解 C对偶问题无可行解，原问题可能无可行解 D一个问题无界，则另一个问题无可行解 E一个问题无可行解，则另一个问题具有无界解4.已知规范形式原问题（max）的最优表中的检验数为（λ1，λ2，……λn），松弛变量 的检验数为（λn+1,λn+2,……λn+m）,则对偶问题的最优解为 A—（λ1，λ2，…… λn） B （λ1，λ2，……λn） C —（λn+1,λn+2,……λn+m）D（λn+1,λn+2,…… λn+m） 5.原问题与对偶问题都有可行解，则 A原问题有最优解，对偶问题可能没有最优解B原 问题与对偶问题可能都没有最优解 C可能一个问题有最优解，另一个问题具有无界解D 原问题与对偶问题都有最优解 计算题 线性规划问题和对偶问题 对于如下的线性规划问题 min z = 3x 1 + 2x 2 +x 3
运筹学基础及应用 习题解答 习题一 P46 1.1 (a) 该问题有无穷多最优解，即满足2 1 0664221≤≤=+x x x 且的所有()21,x x ，此时目标函数值3=z 。 (b) 用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。 1.3 (a) (1) 图解法 4
最优解即为?? ?=+=+82594321 21x x x x 的解??? ??=23,1x ，最大值235=z (2)单纯形法 首先在各约束条件上添加松弛变量，将问题转化为标准形式 ???=++=+++++=8 25943 ..00510 max 421321 4321x x x x x x t s x x x x z 则43,P P 组成一个基。令021==x x 得基可行解()8,9,0,0=x ，由此列出初始单纯形表 21σσ>。5 839,58min = ?? ? ??=θ
02>σ，2328,1421min =??? ? ?=θ 0,21<σσ，表明已找到问题最优解0 , 0 , 2 3 1,4321= ===x x x x 。最大值 235 *=z (b) (1) 图解法 \\ 最优解即为?? ?=+=+5 24262121x x x x 的解??? ??=23,27x ，最大值217=z (2) 单纯形法 首先在各约束条件上添加松弛变量，将问题转化为标准形式 21=+x x 2621+x x
1234523124125 max 2000515.. 6224 5z x x x x x x x s t x x x x x x =+++++=?? ++=??++=? 则3P ，4P ，5P 组成一个基。令021==x x 得基可行解()0,0,15,24,5x =，由此列出初始单纯形表 21σσ>。245min ,,461θ? ?=-= ?? ? 02>σ，15 33min ,24,5 22θ??== ??? 新的单纯形表为
第三章线性规划对偶理论与灵敏度分析习题 一、 思考题 1． 对偶问题和对偶变量的经济意义是什么 2．简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么 3．什么是资源的影子价格它和相应的市场价格之间有什么区别 4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系 5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解 6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）0>+k n x ，其经济意 义是什么 7．在线性规划的最优单纯形表中，松弛变量k n x +的检验数0>+k n σ（标准形为 求最小值），其经济意义是什么 8．将i j j i b c a ,,的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 将会出现什么变化有多少种不同情况如何去处理 二、 判断下列说法是否正确 1．任何线性规划问题都存在且有唯一的对偶问题。 2．对偶问题的对偶问题一定是原问题。 3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。 4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。 5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。 6．已知在线性规划的对偶问题的最优解中，对偶变量0>*i y ，说明在最优生产计 划中，第i 种资源已经完全用尽。 7．已知在线性规划的对偶问题的最优解中，对偶变量0=*i y ，说明在最优生产计 划中，第i 种资源一定还有剩余。 8．对于i j j i b c a ,,来说，每一个都有有限的变化范围，当其改变超出了这个范围 之后，线性规划的最优解就会发生变化。 9．若某种资源的影子价格为u ，则在其它资源数量不变的情况下，该资源增加k 个单位，相应的目标函数值增加 u k 。 10．应用对偶单纯形法计算时，若单纯形表中某一基变量0运筹学第二章课后题
习题2.1 某厂利用A 、B 两种原料生产甲、乙、丙三种产品，已知单位产品所需的原料、利润及有关数据如表2—3所示。 产品甲 产品乙 产品丙 拥有量 原料A 6 3 5 45 原料B 3 4 5 30 单位利润 4 1 5 （1） 求使该厂获利最大的生产计划。 （2） 若产品乙、丙的单位利润不变，当产品甲的单位利润在什么范围内变化时， 最优解不变？ （3） 若原料A 市场紧缺，除拥有量外一时无法购进，而原料B 如数量不足可去 市场购买，单价为0.5，问该厂是否应该购买，且以购进多少为宜？ 解：（1）设产品甲的产量为x 1，产品乙的产量为x 2，产品丙的产量为x 3. 目标函数为:Max z =4 x 1 + x 2+5 x 3 约束条件：s.t.{ 6x 1+3x 2+5x 3≤45；3x 1+4x 2+5x 3≤30；x 1,x 2,x 3≥0； 该线性规划模型为： 答：该厂获利最大的生产计划为产品甲产量为5，产品乙产量为0，产品丙产量为3，总利润为35。
（2）敏感性报告为： 答：如数据显示，产品甲的单位利润变化范围为：[3，6]。 （3）敏感性报告为： 由敏感性报告显示原料B允许的增量为15，其影子价格为0.667，又因为市场上原料B单价为0.5，此时，总利润为37.5。 答：该厂可购买15。 习题2.3 已知某工厂计划生产三种产品，各产品需要在设备A、B、C上加工，有关数据如表2—5所示。 产品A产品B产品C每月设备有效台时 设备A8210300
设备B1058400 设备C21310420 单位利润（千元）32 2.9 请分别回答下列问题： (1)如何充分发挥设备能力，才能使生产盈利最大？ (2)为了增加产量，可借用其他工厂的设备B，若每月可借用60台时，租金为1.8 万元，问借用设备B是否合算？ (3)若另有两种新产品（产品4和产品5），其中生产每件新产品4需用设备A、 B、C各12、5、10台时，单位赢利2.1千元；生产每件新产品5需用设备A、 B、C各4、4、12台时，单位赢利1.87千元。如果设备A、B、C台时不增加， 分别回答这两种新产品的投资在经济上是否合算？ (4)对产品工艺重新进行设计，改进构造。改进后生产每件产品1，需用设备A、 B、C各9、12、4台时，单位赢利4.5千元，问这对原生产计划有何影响？解：（1）设每月产品A的产量为x1,产品B的产量为x2，产品C的产量为x3。 目标函数：Maxz=3x1+2x2+2.9x3 约束条件：s.t. {8x1+2x2+10x3≤300；10x1+5x2+8x3≤400；2x1+13x2+10x3≤420； x1,x2,x3≥0； 该线性规划模型为： 答：当产品1的产量为22，产品2的产量为23，产品3的产量为7时，工厂盈利最大，最大为13.5万元。 （2）其敏感性报告为：
运筹学作业2（第二章部分习题）答案 2．1 题 （P . 77） 写出下列线性规划问题的对偶问题： （1）123123123123123m ax 224..34223343500,z x x x s t x x x x x x x x x x x x =++? ? ++≥??++≤? ? ++≤? ≥≥??无约束，； 解：根据原—对偶关系表，可得原问题的对偶规划问题为： 123123123123123m ax 235..223424334,0,0w y y y s t y y y y y y y y y y y y =++??++≤??++≤? ?++=? ≥≤≤?? （2）111 1 m in ,1,,,1,,0,1,,;1,,m n ij ij i j n ij ij i j n ij ij j j ij z c x c x a i m c x b j n x i m j n ====?=? ? ? ==????==??≥==??∑∑∑∑ 解：根据原—对偶关系表，可得原问题的对偶规划问题为： 11m ax 1,,;1,,m n i i j j i j i j ij i w a u b v u v c i m j n u ==? =+???+≤? ?==? ??∑∑ j 无约束，v 无约束 2．2判断下列说法是否正确，为什么？ （1） 如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； 答：错。 因为：若线性规划的原问题存在可行解，且其对偶问题有可行解，则原问题和可行问题都将有最优解。但，现实中肯定有一些问题是无最优解的，故本题说法不对。
例如原问题 12 12212m ax 31..30,0z x x x x s t x x x =++≥??≤? ?≥≥?有可行解，但其对偶问题 12 11212m in 33..10,0w y y y s t y y y y =+≥??+ ≥??≤≥?无可行解。 （2） 如果线性规划的对偶问题无可行解，则原问题也一定无可行解； 答：错，如（1）中的例子。 （3） 在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或求极小，原问题可 行解的目标函数值一定不超过其对偶问题可行解的目标函数值。 答：错。正确说法是：在互为对偶的一对原问题与对偶问题中，求极大的问题可行解的目标函数值一定不超过求极小的问题可行解的目标函数值。 （4） 任何线性规划问题具有唯一的对偶问题。 答：正确。 2．5给出线性规划问题 123 123123123123m ax 221.. 22 0,0,0z x x x x x x x x x s t x x x x x x =+++-≤? ?-+=?? ++≥??≥≥≥? 写出其对偶问题；（2）利用对偶问题性质证明原问题目标函数值1z ≤ 解：（1）原问题的对偶问题为： 123 123123123123m in 22212.. 10,,0w y y y y y y y y y s t y y y y y y =++++≥? ?-+≤?? -++=? ?≥≤?无约束 （2）取()011T y =，既1230,1,0y y y ===，经验证，()011T y =是对偶问题的一个可行解，并且1w =。由对偶问题的性质可得1z w ≤= 2．9 用对偶单纯形法求解下列线性规划问题： （2）123 123123 123m in 524324..63510,,0z x x x x x x s t x x x x x x =++++≥??++≥??≥? ,
第二章线性规划的对偶理论 2.1 写出下列线性规划问题的对偶问题 max z=2x1+2x2－4x3 x1 + 3x2 + 3x3 ≤30 4x1 + 2x2 + 4x3≤80 x1、x2，x3≥0 解：其对偶问题为 min w=30y1+ 80y2 y1+ 4y2≥2 3y1 + 2y2 ≥2 3y1 + 4y2≥－4 y1、y2≥0 2.2 写出下列线性规划问题的对偶问题 min z=2x1+8x2－4x3 x1 + 3x2－3x3 ≥30 －x1 + 5x2 + 4x3 = 80 4x1 + 2x2－4x3≤50 x1≤0、x2≥0，x3无限制 解：其对偶问题为 max w=30y1+80 y2+50 y3 y1－y2 + 4 y3≥2 3y1+5y2 + 2y3≤8 －3y1 + 4y2－4y3 =－4 y1≥0，y2无限制，y3≤0 2.3已知线性规划问题 max z=x1+2x2+3x3+4x4 x1 + 2x2 + 2x3 +3x4≤20 2x1 + x2 + 3x3 +2x4≤20 x1、x2，x3，x4≥0 其对偶问题的最优解为y1*=6/5，y2*=1/5。试用互补松弛定理求该线性规划问题的最优解。 解：其对偶问题为
min w=20y1+ 20y2 y1 + 2y2≥1 （1） 2y1 + y2 ≥2 （2） 2y1 +3y2≥3 （3） 3y1 +2y2≥4 （4） y1、y2≥0 将y1*=6/5，y2*=1/5代入上述约束条件，得（1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。又因y1*>0，y2*>0，故原问题的两个约束条件应取等式，所以 2x3*+3x4* = 20 3x3* +2x4* = 20 解得x3* = x4* = 4。故原问题的最优解为 X*=（0，0，4，4）T 2.4用对偶单纯形法求解下列线性规划 min z=4x1+2x2+6x3 2x1 +4x2 +8x3 ≥24 4x1 + x2 + 4x3≥8 x1、x2，x3≥0 解将问题改写成如下形式 max（－z）=－4x1－2x2－6x3 －2x1－4x2 －8x3 + x4=－24 －4x1－x2－4x3+x5 =－8 x1、x2，x3，x4，x5≥0 显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正侧基。整个问题的计算过程列在表2—7中。
第二章补充作业习题： 用大M 法和两阶段法求解下面LP 问题： ?????? ?≥≥+-≥-+= 0, 3 232s.t.42min 212 12121x x x x x x x x z 解： 标准化为 ?????? ?≥=-+-=----=0,,, 3 232s.t.42max 43214 2 132121x x x x x x x x x x x x z （1）大M 法 引入人工变量65,x x ，得到下面的LP 问题 ?????? ?=≥=+-+-=+------=6,,1,0 3 2 32s.t.42max 6 4 2 15 3216521 j x x x x x x x x x Mx Mx x x z j 因为人工变量6x 为4>0，所以原问题没有可行解。
（2）两阶段法： 增加人工变量65,x x ，得到辅助LP 问题 ?????? ?=≥=+-+-=+----=6,,1,0 3 232s.t.max 6 4 2 15 32165 j x x x x x x x x x x x g j 初始表 因为辅助LP 问题的最优值为4>0，所以原问题没有可行解。 习2.1 解： 设1x 为每天生产甲产品的数量，2x 为每天生产乙产品的数量，则数学模型为
,518 320 2..200300max 211212121≥≤≤+≤++=x x x x x x x t s x x z 最优解为：()T X 4.8,2.3*=，最优值为：z = 2640。
（1） 最优解为：()T X 5.0,5.1*=，最优值为：z = 4.5。 （2） 无可行解
2.1 用图解法求解下列线性规划问题，并指出各问题具有唯一最优解、无穷多最优解、无界解还是无可行解。 （1）?????? ?≥≤-≤+≤++=0 ,84821234..2max 212121212 1x x x x x x x x t s x x z 解：首先划出平面直角坐标系 4 x 1 +3x 2 X 1 ?? ?=+=-1234842121x x x x 解：??? ??=1 4921x x 所以：2 111492max =+?=z 所以有唯一解 (2)?????? ?≥≤-≤+≤+-+=0 ,414234 223max 2121212121x x x x x x x x x x 解：
2=4 1 ?? ?=+=+-1423422121x x x x 解得：??? ????==413 2 521x x 所以:144 13 2253max =?+? =z 因为直线02321=+x x 与直线142321=+x x 平行， 所以有无穷多最优解，max z=14 （3） ??? ??≥≤+-≤-+=0,432 ..32max 2 121212 1x x x x x x t s x x z 解： （4） ??? ??≥-≤-≥-+=0,330 ..max 2 121212 1x x x x x x t s x x z
解： 2.2将下列线性规划问题化为标准形式 (1) s.t.?????≥≤≤-+-=++-+-=无约束 321 3 213 213 21,0,0624322min x x x x x x x x x x x x z (2)???????≤≥-=-+-≤+-≥--+=0 ,023213 2..23min 3213213 1323 21x x x x x x x x x x t s x x x z 无约束， 解：（1）令 011≥-=x x )0'','('''33333≥-=x x x x x 则上述形式可化为： )'''(32'2m ax 3321x x x x z --+= ??? ??≥=+--+=-++0 ,'',',,'6)'''('24 )'''('..43 321433213321x x x x x x x x x x x x x x t s （2）?????? ?≤≥-=-+-≤+-≥--+=0 ,023213 2..23min 32132131323 21x x x x x x x x x x t s x x x z 无约束， 解：令33'x x -= )0','','(322≥x x x 则上述形式可化为： ')'''(23m ax 3221x x x x z ----= ?????? ?≥=---=+--=+---0 ,,','',',2')'''(321')'''(3')'''(2..54322132215 3224322x x x x x x x x x x x x x x x x x x t s 2.3. 在下列线性规划问题中，找出所有基解，指出哪些是基可行解并分别代入目标函数，比较找出最优解。 （1） ??? ??? ?=≥=++=+=++=)4,3,2,1(0182312 24..53max 5214 2312 1j x x x x x x x x t s x z j
强对偶性，运筹学中的术语。如果x*是原问题的最优解，y*是对 各位读友大家好，此文档由网络收集而来，欢迎您下载，谢谢 强对偶性。强对偶性。运筹学中的术语。如果x*是原问题的最优解。对偶y*是对偶问题的最优解。那么有如下关系：cx*=y*b。 中文名,强对偶性。别称,cx*=y*b。应用学科,运筹学。 定律定义。矩阵形式的线性规划问题的原问题为：。 其对偶问题为：若原问题及其对偶问题均有可行解。则两者均具有最优解。且它们最优解的目标函数值相等：其中X*和Y*是最优解。T上标表示转置。 推导过程。由于原问题和对偶问题均有可行解。 根据弱对偶性的推论。原问题的目
标函数值具有上界。而对偶问题的目标函数值具有下界。因此不可能具有无界解的情况。而且“可行解”的前提也保证了没有无解的情况。所以两者都一定具有最优解。既然原问题有最优解。初始单纯形表进过若干步迭代变成最终单纯形表后。对偶其非基变量的检验数均小于等于0：。将上式变形。T≥CT。ATT≥CT。将此式与对偶问题的约束条件ATY≥CT做比较。 可以看出初始基变量Xs的检验数-CBB-1的相反数。若原问题是极小化问题Xs的检验数即为CBB-1。恰好是其对偶问题的一个可行解Y=T。由此可知。原问题有最优解时。其对偶问题有可行解使得对偶问题的可行解的目标函数值w等于原问题最优目标函数值z。w=YTb=CBB-1b=z存在两者的可行解。使得原问题和对偶问题的的目标函数值相等。由对偶问题的最优性。这时令两者的目标函数值相等的可行解均为最优解。即此时原问题和对偶问题它们最优
解下的目标函数值相等。 适用范围。无论原问题是极大化问题和极小化问题均适用。 定律定义推导过程 由于原问题和对偶问题均有可行解，根据弱对偶性的推论，原问题的目标函数值具有上界，而对偶问题的目标函数值具有下界，因此不可能具有无界解的情况，而且“可行解”的前提也保证了没有无解的情况，所以两者都一定具有最优解。 将上式变形，T≥CT，ATT≥CT，将此式与对偶问题的约束条件ATY≥CT做比较，可以看出初始基变量Xs的检验数-CBB-1的相反数，若原问题是极小化问题Xs的检验数即为CBB-1，恰好是其对偶问题的一个可行解Y=(CBB-1)T。由此可知，原问题有最优解时，其对偶问题有可行解使得对偶问题的可行解的目标函数值w等于原问题最优目标函数值z，w=YTb=CBB-1b=z 存在两者的可行解，使得原问题和