下载文档原格式
第二章习题12、对于下面的线性规划问题，以()632,,A A A B =为基写出相对应的典式。
⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=+++-=++-=++-+-61,0108341242723..2min 63215214321321 j x x x x x x x x x x x x t s x x x j 解：由题可以知：⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡---=100834010042001213A []000121-=TC取一个基()654A A AB =，即：⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-=183004021B 且⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡---=834042213N[]012-=T B C []001=TN C在matlab 中可以计算得到：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡--=-14740812104101B []T b B b 39531-==-1-=b C T B ⎥⎦⎤⎢⎣⎡-=--8321451T N T B C N B C 由()N TN T B T B x C N B C b C Z --=-1可得典式的目标函数：5418321451x x x Z +---=由b Nx B x N B =+-1可得：⎪⎪⎪⎩⎪⎪⎪⎨⎧-=+---=+++=++-3947422558121453412165415431521x x x x x x x x x x x 由此与题中线性规划问题相对应的典式为：⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎨⎧=≥-=+---=+++=++-+---=6,,1,039474225581214534121..8321451min 65415431521541 j x x x x x x x x x x x x t s x x x Z j14、用单纯形法求解线面的线性规划问题，并在平面上画出迭代点走过的路线。
⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥≤≤+≤+≤+--=0,10443186052..2min 21221212121x x x x x x x x x t s x x z 解：由题先将题中线性规划问题化为标准形：⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥=+=++=++=++--=6,,1,010*********..2min 6252142132121 j x x x x x x x x x x x x t s x x z j 由此可写出A ，即为：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=100010010*********000152A则可以得出()6543A A A AB =是一个单位矩阵，且()010441860＞Tb =，所以基B 是可行基，6543,,,x x x x 为基变量，21,x x 为非基变量。
判断题判断正误，如果错误请更正第二章线形规划的对偶理论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 = 3x1 + 2x2+x3. x1 + x2+ x3 ≤ 15 (1)2x1 - x2+ x3≥ 9 (2)-x1 + 2x2+2x3≤ 8 (3)x1 x2x3 ≥ 01、写出题目中线性规划问题的对偶问题；2、分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）；解答：1、写出题目中线性规划问题的对偶问题；解：max w = 15y1 + 9y2 + 8y3. y1 + 2y2- y3 ≤ 3 (1)y1 - y2+ 2y3≤ 2 (2)y1 + y2+ 2y3≤ 1 (3)y1≤0、 y2 ≥0、y3 ≤02、分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）；解：先将原问题化成以下形式，则有mi n z = 3x1 + 2x2 + x3. x1 + x2+ x3+ x4= 15 (1)-2x1 + x2- x3+ x5= -9 (2)-x1 + 2x2+2x3+x6= 8 (3)x1 x2x3x4x5x6 ≥ 0原始问题的最优解为（X1 X2 X3 X4 X5 X6）=（2，0，5，8，0，0），minz=11对偶问题的最优解为（y1 y2 y3 y4 y5 y6）=（0，7/5，-1/5，0，19/5，0），maxw=11对于以下线性规划问题max z = -x1 - 2x2. -2x1 + 3x2≤ 12 (1)-3x1 + x2≤ 6 (2)x1 + 3x2≥ 3 (3)x1≤ 0， x2≥ 01、写出标准化的线性规划问题；2、用单纯形表求出这个线性规划问题的最优解和最优的目标函数值；3、写出这个（极大化）线性规划问题的对偶问题；4、求出对偶问题的最优解和最优解的目标函数值；5、第（2）个约束右端常数b2=6在什么范围内变化，最优解保持不变。
运筹学第三版课后习题答案第一章：引论1.1 课后习题习题1a)运筹学是一门应用数学的学科，旨在解决实际问题中的决策和优化问题。
它包括数学模型的建立、问题求解方法的设计等方面。
b)运筹学可以应用于各个领域，如物流管理、生产计划、流程优化等。
它可以帮助组织提高效率、降低成本、优化资源分配等。
c)运筹学主要包括线性规划、整数规划、指派问题等方法。
习题2运筹学的应用可以帮助组织提高效率、降低成本、优化资源分配等。
它可以帮助制定最佳的生产计划，优化供应链管理，提高运输效率等。
运筹学方法的应用还可以帮助解决紧急情况下的应急调度问题，优化医疗资源分配等。
1.2 课后习题习题1运筹学方法可以应用于各个领域，如物流管理、生产计划、供应链管理、流程优化等。
在物流管理中，可以使用运筹学方法优化仓储和运输的布局，提高货物的运输效率。
在生产计划中，可以使用运筹学方法优化产品的生产数量和生产周期，降低生产成本。
在供应链管理中，可以使用运筹学方法优化订单配送和库存管理，提高供应链的效率。
在流程优化中，可以使用运筹学方法优化业务流程，提高整体效率。
习题2在物流管理中，可以使用运筹学方法优化车辆的调度和路线规划，以提高运输效率和降低成本。
在生产计划中，可以使用运筹学方法优化生产线的安排和产品的生产量，以降低生产成本和提高产能利用率。
在供应链管理中，可以使用运筹学方法优化供应链各个环节的协调和调度，以提高整体效率和减少库存成本。
在流程优化中，可以使用运筹学方法优化业务流程的排布和资源的分配，以提高流程效率和客户满意度。
第二章：线性规划基础2.1 课后习题习题1线性规划是一种数学优化方法，用于解决包含线性约束和线性目标函数的优化问题。
其一般形式为：max c^T*xs.t. Ax <= bx >= 0其中，c是目标函数的系数向量，x是决策变量向量，A是约束矩阵，b是约束向量。
习题2使用线性规划方法可以解决许多实际问题，如生产计划、供应链管理、资源分配等。
习题二2.1 写出下列线性规划问题的对偶问题(1) max z ＝10x1＋x2＋2x3(2) max z ＝2x1＋x2＋3x3＋x4st. x1＋x2＋2 x3≤10 st. x1＋x2＋x3 ＋x4≤54x1＋x2＋x3≤20 2x1－x2＋3x3＝－4x j≥0 （j＝1,2,3）x1－x3＋x4≥1x1，x3≥0，x2，x4无约束(3) min z ＝3x1＋2 x2－3x3＋4x4(4) min z ＝－5 x1－6x2－7x3st. x1－2x2＋3x3＋4x4≤3 st. －x1＋5x2－3x3≥15x2＋3x3＋4x4≥－5 －5x1－6x2＋10x3≤202x1－3x2－7x3 －4x4＝2＝x1－x2－x3＝－5 x1≥0，x4≤0，x2，，x3无约束x1≤0，x2≥0，x3无约束2.2 已知线性规划问题max z＝CX，AX=b，X≥0。
分别说明发生下列情况时，其对偶问题的解的变化：（1）问题的第k个约束条件乘上常数λ（λ≠0）；（2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上；（3）目标函数改变为max z＝λCX（λ≠0）；'x代换。
（4）模型中全部x1用312.3 已知线性规划问题min z＝8x1＋6x2＋3x3＋6x4st. x1＋2x2＋x4≥33x1＋x2＋x3＋x4≥6x3 ＋x4＝2x1 ＋x3 ≥2x j≥0（j＝1,2,3,4）(1) 写出其对偶问题；(2) 已知原问题最优解为x*＝（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。
2.4 已知线性规划问题min z＝2x1＋x2＋5x3＋6x4 对偶变量st. 2x1 ＋x3＋x4≤8 y12x1＋2x2＋x3＋2x4≤12 y2x j≥0（j＝1,2,3,4）对偶问题的最优解y1*=4；y2*=1，试对偶问题的性质，求出原问题的最优解。
2.5 考虑线性规划问题max z＝2x1＋4x2＋3x3st. 3x1＋4 x2＋2x3≤602x1＋x2＋2x3≤40x1＋3x2＋2x3≤80x j≥0 （j＝1,2,3）４７４８（1）写出其对偶问题（2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解；（3）用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解；（4）比较（2）和（3）计算结果。
运筹学作业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）1111m in ,1,,,1,,0,1,,;1,,m n ij ij i j n ij ij i j nij ij j j ij z c x c x a i m c x b j nx i m j n====⎧=⎪⎪⎪==⎪⎨⎪⎪==⎪⎪≥==⎪⎩∑∑∑∑ 解：根据原—对偶关系表，可得原问题的对偶规划问题为：11m ax 1,,;1,,m n i i j ji j i j ij i w a u b v u v c i m j n u ==⎧=+⎪⎪⎪+≤⎨⎪==⎪⎪⎩∑∑ j 无约束，v 无约束2．2判断下列说法是否正确，为什么？（1） 如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； 答：错。
因为：若线性规划的原问题存在可行解，且其对偶问题有可行解，则原问题和可行问题都将有最优解。
但，现实中肯定有一些问题是无最优解的，故本题说法不对。
例如原问题1212212m ax 31..30,0z x x x x s t x x x =++≥⎧⎪≤⎨⎪≥≥⎩有可行解，但其对偶问题1211212m in 33..10,0w y y y s t y y y y =+≥⎧⎪+≥⎨⎪≤≥⎩无可行解。
（2） 如果线性规划的对偶问题无可行解，则原问题也一定无可行解；答：错，如（1）中的例子。
第二章 对偶问题与灵敏度分析一、写出下列线性规划的对偶问题1、P89,(a)321422m in x x x Z ++=⎪⎪⎩⎪⎪⎨⎧≥=++≤++≥++.,0,;534;332;243321321321321无约束x x x x x x x x x x x x解：原模型可化为321422m in x x x Z ++=⎪⎪⎩⎪⎪⎨⎧≥=++≥≥++.,0,;534;3-3--2-;243321321321321321无约束x x x y y y x x x x x x x x x 于是对偶模型为321532m ax y y y W +-=⎪⎪⎩⎪⎪⎨⎧≥≤+-≤+-≤+-.,0,;4334;243;22321321321321无约束y y y y y y y y y y y y2、P89,(b)321365m ax x x x Z ++=⎪⎪⎩⎪⎪⎨⎧≤≥≤++≥-+-=++.0,0,;8374;35;522321321321321x x x x x x x x x x x x 无约束解：令033≥-='x x 原模型可化为321365m ax x x x Z '-+=⎪⎪⎩⎪⎪⎨⎧≥'≥≤'+≤'='+.0,0,;83-74;3--5-;52-2321321321321321x x x y y y x x x x x x x x x 无约束于是对偶模型为321835m in y y y W +-=⎪⎪⎩⎪⎪⎨⎧≥-≥---≥+-=++.0,,;332;6752;54321321321321y 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, 线性规划问题213m ax x x Z += ⎪⎩⎪⎨⎧≥≤+≤+0,1025;74212121x x x x x x最优单纯形表如下试用灵敏度分析的方法，分析：（1） 目标函数中的系数21,c c 分别在什么范围内变化，最优解不变（2） 约束条件右端常数项21,b b 分别在什么范围内变化，最优基保持不变解：（1） 1c 的分析：要使得最优解不变，则需⎪⎪⎩⎪⎪⎨⎧≤⨯-⨯+=≤⨯+⨯-=034131003513201413c c σσ 即 ⎪⎩⎪⎨⎧≤≥42511c c 所以：4251≤≤c 时可保持最优解不变。
运筹学II 练习题1 试判定下述非线性规划是否为凸规划：（1）()2212212212128020,0Min f X x x x x x x x x ⎧ =++⎪-≥⎪⎨--+=⎪⎪≥⎩（2）()22212312221221312324510,,0Min f X x x x x x x x x x x x x ⎧ =++-⎪+≤⎪⎨+=⎪⎪≥⎩（3） max 12()f x x =+X2212121..,0≤≥⎧+⎨⎩x x s t x x解 （1）()()()221221122212128020,0Min f X x x g X x x g X x x x x ⎧ =++⎪=-≥⎪⎨=--+=⎪⎪≥⎩()()()12,,f X g X g X 的海赛矩阵的行列式：()()()()2221122222122002f X f X x x x H f X f X x x x ∂∂∂∂∂==>0∂∂∂∂∂ ()()()()2211211212211221220000g X g X x x x g g X g X x x x ∂∂∂∂∂==≥∂∂∂∂∂()()()()222221122222222120002g X g X x x x g g X g X x x x ∂∂∂∂∂==≤0-∂∂∂∂∂ 知()f X 为严格凸函数，()1,g X 为凸函数，()2g X 为凹函数，所以不是一个凸规划问题。
（2）()()()()()22212312'222211211222131232440510,,0Min f X x x x x x g X x x g X x x g X x x x x x ⎧ =++-⎪=+≤⇔=-++≥⎪⎨=+=⎪⎪≥⎩ 同上有()()()12,,f X g X g X 的海赛矩阵的行列式410120002H -=->0122,0g -=-是凹函数，21000g =是凸函数，不是凸规划问题。
第二章线性规划的对偶理论2.1 写出下列线性规划问题的对偶问题max z=2x1+2x2－4x3x1 + 3x2 + 3x3 ≤304x1 + 2x2 + 4x3≤80x1、x2，x3≥0解：其对偶问题为min w=30y1+ 80y2y1+ 4y2≥23y1 + 2y2 ≥23y1 + 4y2≥－4y1、y2≥02.2 写出下列线性规划问题的对偶问题min z=2x1+8x2－4x3x1 + 3x2－3x3 ≥30－x1 + 5x2 + 4x3 = 804x1 + 2x2－4x3≤50x1≤0、x2≥0，x3无限制解：其对偶问题为max w=30y1+80 y2+50 y3y1－y2 + 4 y3≥23y1+5y2 + 2y3≤8－3y1 + 4y2－4y3 =－4y1≥0，y2无限制，y3≤02.3已知线性规划问题max z=x1+2x2+3x3+4x4x1 + 2x2 + 2x3 +3x4≤202x1 + x2 + 3x3 +2x4≤20x1、x2，x3，x4≥0其对偶问题的最优解为y1*=6/5，y2*=1/5。
试用互补松弛定理求该线性规划问题的最优解。
解：其对偶问题为min w=20y1+ 20y2y1 + 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* = 203x3* +2x4* = 20解得x3* = x4* = 4。
故原问题的最优解为X*=（0，0，4，4）T2.4用对偶单纯形法求解下列线性规划min z=4x1+2x2+6x32x1 +4x2 +8x3 ≥244x1 + x2 + 4x3≥8x1、x2，x3≥0解将问题改写成如下形式max（－z）=－4x1－2x2－6x3－2x1－4x2 －8x3 + x4=－24－4x1－x2－4x3+x5 =－8x1、x2，x3，x4，x5≥0显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正侧基。
内容题型 类型 知识点 难度来源线性规划 计算题 图解法 图解法1 运27p,2，2424. Kelso 运动器材公司制作两种棒球手套：普通型和捕手型。
公司的切割与印染部门有900小时的可工作时间，成型部门有300小时的可工作时间，包装和发货部门有 100小时的可工作时间。
每双手套的生产时间和利润贡献要求如下：假设公司希望实现总利润贡献最大，回答以下问题： a. 本题的线性规划模型是什么？b. 用图解法找到最优解。
此时每种手套各应该生产多少双？c. 在最优解时公司获得的总利润贡献是多少？d. 每个部门应该安排多少小时的生产时间？e. 每个部门的松弛时间是多少？a . 令 R —普通型手套的生产量； C —捕手型手套的生产量。
max 5R + 8C1R + 3/2C ≤900 切割与缝合1/2R + 1/3C ≤300b . 成 型1/8R + 1/4C ≤100 包装和发货R,C ≥ 0型 号生产时间 (小时)每双手套的利润贡献 (美元) 切割与缝合成 型 包装和发货 普通型 捕手型1 3/21/2 1/31/8 1/45 8900F600 C﹠S 最优解R=500，C=150 400 P﹠S600 800 900c. 5×500﹢8×150=＄3700d. C﹠S 切割与缝合1×500＋3/2×150=725F 成型1/2×500＋1/3×150=300P﹠S 包装和发货1/8×500＋1/4×150=100e.部门生产量使用量松弛切割与缝合900 725 175小时成型300 300 0小时包装和发货100 100 0小时。
第二章补充作业习题：用大M 法和两阶段法求解下面LP 问题：⎪⎪⎩⎪⎪⎨⎧≥≥+-≥-+=0,3232s.t.42min 21212121x x x x x x x x z解： 标准化为⎪⎪⎩⎪⎪⎨⎧≥=-+-=----=0,,,3232s.t.42max 432142132121x x x x x x x x x x x x z（1）大M 法引入人工变量65,x x ，得到下面的LP 问题⎪⎪⎪⎪⎨⎧=≥=+-+-=+------=6,,1,03232s.t.42max 642153216521 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,03232s.t.max 6421532165 j x x x x x x x x x x x g j初始表因为辅助LP 问题的最优值为4>0，所以原问题没有可行解。
习2.1 解：设1x 为每天生产甲产品的数量，2x 为每天生产乙产品的数量，则数学模型为,5183202..200300max 211212121≥≤≤+≤++=x x x x x x x t s x x z最优解为：()TX 4.8,2.3*=，最优值为：z = 2640。
（1）最优解为：()TX 5.0,5.1*=，最优值为：z = 4.5。
（2）无可行解有无穷多最优解，其中一个为：TX⎪⎭⎫⎝⎛=0,310*1，另一个为：()TX10,0*2=，最优值为：z = 20。
（4）无界解解：A B 资源限额 会议室 1 1 5 桌子 3 2 12 货架 3 6 18 工资2522设1x 为雇佣A 的天数，2x 为雇佣B 的天数，则数学模型为,186312235..2225min 2121212121≥≥+≥+≥++=x x x x x x x x t s x x z最优解为：()TX3,2*=，最优值为：z = 116。
第二章线性规划的对偶理论2.1 写出下列线性规划问题的对偶问题max z=2x1+2x2－4x3x1 + 3x2 + 3x3 ≤304x1 + 2x2 + 4x3≤80x1、x2，x3≥0解：其对偶问题为min w=30y1+ 80y2y1+ 4y2≥23y1 + 2y2 ≥23y1 + 4y2≥－4y1、y2≥02.2 写出下列线性规划问题的对偶问题min z=2x1+8x2－4x3x1 + 3x2－3x3 ≥30－x1 + 5x2 + 4x3 = 804x1 + 2x2－4x3≤50x1≤0、x2≥0，x3无限制解：其对偶问题为max w=30y1+80 y2+50 y3y1－y2 + 4 y3≥23y1+5y2 + 2y3≤8－3y1 + 4y2－4y3 =－4y1≥0，y2无限制，y3≤02.3已知线性规划问题max z=x1+2x2+3x3+4x4x1 + 2x2 + 2x3 +3x4≤202x1 + x2 + 3x3 +2x4≤20x1、x2，x3，x4≥0其对偶问题的最优解为y1*=6/5，y2*=1/5。
试用互补松弛定理求该线性规划问题的最优解。
解：其对偶问题为min w=20y1+ 20y2y1 + 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* = 203x3* +2x4* = 20解得x3* = x4* = 4。
故原问题的最优解为X*=（0，0，4，4）T2.4用对偶单纯形法求解下列线性规划min z=4x1+2x2+6x32x1 +4x2 +8x3 ≥244x1 + x2 + 4x3≥8x1、x2，x3≥0解将问题改写成如下形式max（－z）=－4x1－2x2－6x3－2x1－4x2 －8x3 + x4=－24－4x1－x2－4x3+x5 =－8x1、x2，x3，x4，x5≥0显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正侧基。
运筹学习题答案及注释2.3 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如表2-32所示，求表中各括弧内未知数的值。
注释：由题中初始单纯形表及、最终单纯形表，我们可以看出：在初始单纯形表中，先选x 1进基，选x 5出基，做变换；然后再选x 2进基，选x 6出基，做变换，则得到最终单纯形表。
2.7 给出线性规划问题。
max 432142x x x x z +++=st. ⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤++≤++≤+≤++0,,,966283432132143221421x x x x x x x x x x x x x x x要求：（1）写出其对偶问题；（2）已知原问题最优解为X*=（2，2，4，0），试根据对偶理论，直接求出对偶问题的最优解。
解：（1）其对偶问题为： min 43219668y y y y w +++=st. ⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥+≥++≥+++≥++0,,,9143224321314324321421y y y y y y y y y y y y y y y y（2）用单纯形法解原问题，将原问题化成标准形式如下：max 87654321000042x x x x x x x x z +++++++=st. ⎪⎪⎪⎩⎪⎪⎪⎨⎧≥=+++=+++=++=+++0,,,,,,,96628387654321832174326215421x x x x x x x x x x x x x x x x x x x x x x x因此，可得如下单纯形表：因1≥0，所以选x 进基，因（10/3）/（5/3）≤3/1≤（8/3）/（1/3），故选x 出基，则得所以，最优解为：X*=（2，2，4，0，0，0，0，1），代入目标函数得z =16。
其对偶问题得最优解为：X*=（4/5，3/5，1，0，0，0，0，4/5），代入目标函数得w =16。
2.9 用对偶单纯形法求解下列线性规划问题。
第二章线性规划的对偶理论2.1 写出下列线性规划问题的对偶问题max z=2x1+2x2－4x3x1 + 3x2 + 3x3 ≤304x1 + 2x2 + 4x3≤80x1、x2，x3≥0解：其对偶问题为min w=30y1+ 80y2y1+ 4y2≥23y1 + 2y2 ≥23y1 + 4y2≥－4y1、y2≥02.2 写出下列线性规划问题的对偶问题min z=2x1+8x2－4x3x1 + 3x2－3x3 ≥30－x1 + 5x2 + 4x3 = 804x1 + 2x2－4x3≤50x1≤0、x2≥0，x3无限制解：其对偶问题为max w=30y1+80 y2+50 y3y1－y2 + 4 y3≥23y1+5y2 + 2y3≤8－3y1 + 4y2－4y3 =－4y1≥0，y2无限制，y3≤02.3已知线性规划问题max z=x1+2x2+3x3+4x4x1 + 2x2 + 2x3 +3x4≤202x1 + x2 + 3x3 +2x4≤20x1、x2，x3，x4≥0其对偶问题的最优解为y1*=6/5，y2*=1/5。
试用互补松弛定理求该线性规划问题的最优解。
解：其对偶问题为min w=20y1+ 20y2y1 + 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* = 203x3* +2x4* = 20解得x3* = x4* = 4。
故原问题的最优解为X*=（0，0，4，4）T2.4用对偶单纯形法求解下列线性规划min z=4x1+2x2+6x32x1 +4x2 +8x3 ≥244x1 + x2 + 4x3≥8x1、x2，x3≥0解将问题改写成如下形式max（－z）=－4x1－2x2－6x3－2x1－4x2 －8x3 + x4=－24－4x1－x2－4x3+x5 =－8x1、x2，x3，x4，x5≥0显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正侧基。
