下载文档原格式
运筹学练习题一、填空题1、线性规划模型有三种参数，其名称分别为_ 、 _ 和 。
2、一个模型是m 个约束，n 个变量，则它的对偶模型为 个约束， 个变量。
3、动态规划是解决 最优化问题的一种理论和方法。
4、在运输问题中，一个空格只存在______闭回路，计算闭回路的目的是要计算解中_______。
5、若线性规划问题最优解不唯一，则在最优单纯形表上的非基变量的检验数___________。
6、为求解销量大于产量的运输问题，可虚设一个产地A m+1，它的销量等于_ 。
二、单项选择题1．使用人工变量法求解极大化线性规划问题时，当所有的检验数0≤j σ，在基变量中仍含有非零的人工变量，表明该线性规划问题（ ）。
A ．有唯一的最优解；B ．有无穷多个最优解；C ．为无界解；D ．无可行解。
2．一个极大化的线性规划问题用单纯形法求解，若对所有的检验数0≤j σ，但对某个非基变量j x ，有0=j σ，则该线性规划问题（ ）。
A ．有唯一的最优解；B ．有无穷多个最优解；C ．为无界解；D ．无可行解。
3．在用对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中（ ）。
A ．b 列元素不小于零； B ．检验数都大于零； C ．检验数都不小于零； D ．检验数都不大于零。
4．在运输问题中，每次迭代时，如果有某基变量的解值等于零，则该运输问题（ ）。
A ．无最优解；B ．有无穷多个最优解；C ．有唯一最优解；D ．出现退化解。
5．若一个产销平衡运输问题的数据表的各元素都乘以常数k （k.>0）得到一个新的数据表，这一新数据表对应着一个新的产销平衡运输问题，则（ ）。
A ．新问题与原问题有相同的最优解；B ．新问题最优目标值大于原问题最优目标函数值；C ．新问题最优解等于原问题最优解加上k ；D ．新问题最优解小于原问题最优解。
6．如果要使目标规划实际实现值达到或超过目标值，则相应的偏差变量应满足（ ）。
P1 11. 判断下列说法是否正确：（a）图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的；（b）线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大；（c）线性规划问题的每一个基解对应可行域的一个顶点；（d）如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点；（e）对取值无约束的变量，通常令x j=x j′-x j〞，其中x j′≥0 , x j〞≥0 ,在用单纯形法求得的最优解中有可能同时出现x j′>0, x j〞>0 ；（f）用单纯形法求解标准形式的线性规划问题时，与бj >0对应的变量都可以被选作换入变量；（g）单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负；（h）单纯形法计算中，选取最大正检验数бk对应的变量x k作为换入变量，将使目标函数值得到最快的增长；（i）一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果；（j）线性规划问题的任一可行解都可以用全部基可行解的线性组合表示；（k）若x1，x2分别是某一线性规划问题的最优解，则X=λ1X1+λ2X 2 也是该线性规划问题的最优解，其中λ1 , λ2为正的实数；（l ）线性规划用两阶段法求解时，第一阶段的目标函数通常写为min z=(ai ai ix x ∑为人工变量)，但也可以写为min z=i ai ik x ∑，只要所有k i 均为大于零的常数；（m ）对一个有 n 个变量 m 个约束的标准形的线性规划问题，其可行域的顶点恰好为C m n 个；（n ）单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解；（o ） 线性规划问题的可行解如为最优解 ，则该可行解一定是可行解；（p ） 若线规划问题具有可行解，切其可行域有界，则该线性规划问题最多具有有限个数的最优解；（q ）线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值，则该顶点处的目标函数值达到最优。
习题一1.1 用图解法求解下列线性规划问题，并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。
(1) min z ＝6x1＋4x2(2) max z ＝4x1＋8x2st. 2x1＋x2≥1 st. 2x1＋2x2≤103x1＋4x2≥1.5 －x1＋x2≥8x1, x2≥0 x1, x2≥0(3) max z ＝x1＋x2(4) max z ＝3x1－2x2st. 8x1＋6x2≥24 st. x1＋x2≤14x1＋6x2≥－12 2x1＋2x2≥42x2≥4 x1, x2≥0x1, x2≥0(5) max z ＝3x1＋9x2(6) max z ＝3x1＋4x2st. x1＋3x2≤22 st. －x1＋2x2≤8－x1＋x2≤4 x1＋2x2≤12x2≤6 2x1＋x2≤162x1－5x2≤0 x1, x2≥0x1, x2≥01.2. 在下列线性规划问题中，找出所有基本解，指出哪些是基本可行解并分别代入目标函数，比较找出最优解。
(1) max z ＝3x1＋5x2(2) min z ＝4x1＋12x2＋18x3st. x1＋x3＝4 st. x1＋3x3－x4＝32x2＋x4＝12 2x2＋2x3－x5＝53x1＋2x2＋x5＝18 x j≥0 （j＝1, (5)x j≥0 （j＝1, (5)1.3. 分别用图解法和单纯形法求解下列线性规划问题，并对照指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点。
(1) max z ＝10x1＋5x2st. 3x1＋4x2≤95x1＋2x2≤8x1, x2≥0(2) max z ＝100x1＋200x2st. x1＋x2≤500x1≤2002x1＋6x2≤1200x1, x2≥01.4. 分别用大M法和两阶段法求解下列线性规划问题，并指出问题的解属于哪一类：(1) max z ＝4x1＋5x2＋x3(2) max z ＝2x1＋x2＋x3st. 3x1＋2x2＋x3≥18 st. 4x1＋2x2＋2x3≥42x1＋x2≤4 2x1＋4x2≤20x1＋x2－x3＝5 4x1＋8x2＋2x3≤16x j≥0 （j＝1,2,3）x j≥0 （j＝1,2,3）(3) max z ＝ x 1＋ x 2 (4) max z ＝x 1＋2x 2＋3x 3－x 4 st. 8x 1＋6x 2≥24 st. x 1＋2x 2＋3x 3＝154x 1＋6x 2≥－12 2x 1＋ x 2＋5x 3＝202x 2≥4 x 1＋2x 2＋ x 3＋ x 4＝10x 1, x 2≥0 x j ≥0 （j ＝1, (4)(5) max z ＝4x 1＋6x 2 (6) max z ＝5x 1＋3x 2＋6x 3 st. 2x 1＋4x 2 ≤180 st. x 1＋2x 2＋ x 3≤183x 1＋2x 2 ≤150 2x 1＋ x 2＋3x 3≤16 x 1＋ x 2＝57 x 1＋ x 2＋ x 3＝10x 2≥22 x 1, x 2≥0，x 3无约束 x 1, x 2≥01.5 线性规划问题max z ＝CX ，AX ＝b ，X ≥0，如X*是该问题的最优解，又λ＞0为某一常数，分别讨论下列情况时最优解的变化：（1） 目标函数变为max z ＝λCX ；（2） 目标函数变为max z ＝（C ＋λ）X ；（3） 目标函数变为max z ＝C X ，约束条件变为AX ＝λb 。
第一章线性规划1．1将下述线性规划问题化成标准形式1)min z＝－3x1＋4x2－2x3＋5 x4－x2＋2x3－x4＝－24xst. x1＋x2－x3＋2 x4 ≤14－2x1＋3x2＋x3－x4 ≥2x1，x2，x3≥0，x4无约束2)min z ＝2x1－2x2＋3x3＋x2＋x3＝4－xst. －2x1＋x2－x3≤6x1≤0 ，x2≥0，x3无约束1．2用图解法求解LP问题，并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解。
1)min z＝2x1＋3x24x1＋6x2≥6st2x1＋2x2≥4x1，x2≥02)max z＝3x1＋2x22x1＋x2≤2st3x1＋4x2≥12x1，x2≥03)max z＝3x1＋5x26x1＋10x2≤120st5≤x1≤103≤x2≤84)max z＝5x1＋6x22x1－x2≥2st－2x1＋3x2≤2x1，x2≥01．3找出下述LP问题所有基解，指出哪些是基可行解，并确定最优解（1）min z＝5x1－2x2＋3x3＋2x4x1＋2x2＋3x3＋4x4＝7st2x1＋2x2＋x3 ＋2x4＝3x1，x2，x3，x4≥01．4 分别用图解法与单纯形法求解下列LP 问题，并对照指出最优解所对应的顶点。
1) maxz ＝10x 1＋5x 23x 1＋4x 2≤9 st 5x 1＋2x 2≤8 x 1，x 2≥02) maxz ＝2x 1＋x 2 3x 1＋5x 2≤15 st 6x 1＋2x 2≤24 x 1，x 2≥01．5 分别用大M 法与两阶段法求解下列LP 问题。
1) minz ＝2x 1＋3x 2＋x 3 x 1＋4x 2＋2x 3≥8 st 3x 1＋2x 2 ≥6 x 1，x 2 ，x 3≥02) max z ＝4x 1＋5x 2＋ x 3. 3x 1＋2x 2＋ x 3≥18 St. 2x 1＋ x 2 ≤4x 1＋ x 2－ x 3＝53) maxz ＝ 5x 1＋3x 2 +6x 3 x 1＋2x 2 －x 3 ≤ 18 st 2x 1＋x 2 －3 x 3 ≤ 16 x 1＋x 2 －x 3＝10 x 1，x 2 ，x 3≥01231231231231234)max 101512539561515.25,,0z x x x x x x x x x st x x x x x x =++++≤⎧⎪-++≤⎪⎨++≥⎪⎪≥⎩1．61.7某班有男生30人，女生20人，周日去植树。
二、填空选择题：（每空格2分，共16分）1、线性规划的解有划的唯一最优解、无穷多最优解、无界解和无可行解四种。
2、在求运费最少的调度划的运划的输问题中，如划的果某划的一非基变量的检验数为4，则说明如果在该空格中增加一个运量运费将增加划的4 。
3、“如果线性规划的原问题存在可行解，则其对划的偶问题一定存在可行解”，这句话对还是划的错？错4、如果某一整数规划：MaxZ=X划的1+X2划的X1+9/1划的2≤1/3X1,X2≥0且均为整数所对应的线性规划（松弛问题）的最优划的解为X1=3/2，X2=10/3，MaxZ=6/29，我们现在划的要对X1进行分枝，划的应该分为X1≤1和X1≥2。
5、在用逆向解法求动态规划时，f k(s k)的含义是：从第k个阶段到第n个阶段的最优解。
6.假设某线性规划的可行解的集合为D，而其所对应的整数规划的可行解集合为B，那么D 和B的关系为 D 包含 B7.已知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条问：（1）写出B-1=⎪⎪⎪⎭⎫⎝⎛---13/20.3/1312(2)对偶问题的最优解： Y＝（5，0，23，0，0）T8. 线性规划问题如果有无穷多最优解，则单纯形计算表的终表中必然有___某一个非基变量的检验数为0______；9. 极大化的线性规划问题为无界解时，则对偶问题_无解_________；10. 若整数规划的松驰问题的最优解不符合整数要求，假设Xi =bi不符合整数要求，INT（bi ）是不超过bi的最大整数，则构造两个约束条件：Xi≥INT（bi）＋1 和 Xi≤INT（bi），分别将其并入上述松驰问题中，形成两个分支，即两个后继问题。
11. 知下表是制订生产计划问题的一张LP 最优单纯形表（极大化问题，约束条问：(1)对偶问题的最优解： Y ＝(4,0,9,0,0,0)T （2）写出B -1=⎪⎪⎪⎭⎫ ⎝⎛611401102二、计算题（60分）1、已知线性规划（20分）MaxZ=3X 1+4X 2 1+X 2≤5 2X 1+4X 2≤12 3X 1+2X 2≤81,X 2≥02）若C 2从4变成5，最优解是否会发生改变，为什么？3）若b 2的量从12上升到15，最优解是否会发生变化，为什么？4）如果增加一种产品X 6，其P 6=(2,3,1)T ，C 6=4该产品是否应该投产？为什么？ 解：1)对偶问题为Minw=5y1+12y2+8y3 y1+2y2+3y 3≥3y1+4y2+2y 3≥4 y1,y2≥02)当C 2从4变成5时， σ4=-9/8 σ5=-1/4由于非基变量的检验数仍然都是小于0的，所以最优解不变。
最全运筹学习题及答案共1 页运筹学习题答案）1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。
（1）max z?x1?x25x1+10x2?50x1+x2?1x2?4x1，x2?0（2）min z=x1+1.5x2x1+3x2?3x1+x2?2x1，x2?0（3）+2x2x1-x2?-0.5x1+x2x1，x2?0（4）max z=x1x2x1-x2?03x1-x2?-3x1，x2?0（1）（图略）有唯一可行解，max z=14（2）（图略）有唯一可行解，min z=9/4（3）（图略）无界解（4）（图略）无可行解1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。
共2 页（1）min z=-3x1+4x2-2x3+5x4 4x1-x2+2x3-x4=-2x1+x2+3x3-x4?14 -2x1+3x2-x3+2x4?2x1，x2，x3?0，x4无约束（2zk?i??xk?1mxik?（1Max s. t .-4x1xx1,x2共3 页(2)解：加入人工变量x1，x2，x3，…xn，得：Max s=(1/pk)? i?1n?k?1m?ikxik-Mx1-Mx2-…..-Mxnm（1）max z=2x1+3x2+4x3+7x4 2x1+3x2-x3-4x4=8x1-2x2+6x3-7x4=-3x1,x2,x3,x4?0(2)max z=5x1-2x2+3x3-6x4共4 页x1+2x2+3x3+4x4=72x1+x2+x3+2x4=3x1x2x3x4?0（1）解：系数矩阵A是：?23?1?4??1?26?7? ??令A=(P1，P2，P3，P4)P1与P2线形无关，以（P1，P2有2x1+3x2=8+x3+4x4x1-2x2=-3-6x3+7x4令非基变量x3，x4解得：x1=1；x2=2基解0，0)T为可行解z1=8(2)同理，以（P=（45/13，0，-14/13，0)T是非可行解；3以（P1，P4X(3)=，，7/5)T是可行解，z3=117/5；(4)以（P2，P=（，45/16，7/16，0)T是可行解，z4=163/16；3以（P2，P4）为基，基解X(5)0，68/29，0，-7/29)T是非可行解；(6)TX以（P4，P）为基，基解=（0，0，-68/31，-45/31是非可行解；)3最大值为z3=117/5；最优解X(3)=（34/5，0，0，7/5)T。
《运筹学》习题集重点课程建设小组2010.3第一章 线性规划1、将下列线性规划问题化为标准型(1) max Z = 3x 1+ 5x 2- 4x 3+ 2x 4⎪⎪⎩⎪⎪⎨⎧≥=+≥+≤++0x , x , x 9 5x -3x -4x x -13 2x -2x 3x -x 18 3x x -6x 2x s.t.421432143214321 (2) min f = 3x1+ x2+ 4x3+ 2x4 ≤ 1⎪⎪⎩⎪⎪⎨⎧≤≥=++≥+≤+0x 0, x , x 15 2x 3x -4x 2x 7- x -2x 2x -3x 51- 2x - x -3x 2x s.t. 4214214321 43213 (3) min F=x1+x2+x3+x4⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥+≥+≥+≥+0x ,x ,x ,x 7x x 8x x 6x x 5x x s.t.432143222141 (4) 3213m in x x x F -+=⎪⎪⎩⎪⎪⎨⎧≤≤≥≥0x ,x ,x 4x +5x +x -22x +x -3x +x +x ..32132121321t s2、用图解法求解下列线性规划问题⎪⎪⎩⎪⎪⎨⎧≥≤≤≤+=0x ,x 3 x 122x +3x 6 x -2x ..max )1(211212121t s X X Z⎪⎩⎪⎨⎧≥≥≥++-=0 x ,x 155x -3x 56 7x 4x ..3min )2(21212121t s x x Z3、用单纯形法求解以下线性规划问题⎪⎩⎪⎨⎧≥≤+≤+=0x ,x 5 x x -3 3x -2x ..23max )1(21212121t s x x Z⎪⎩⎪⎨⎧≥≤=++-=0 x ,x ,x 12 x -2x 124x 3x x ..2max )2(3213232132t s x x Z （３） max z = x 1 +2 x 2 +3 x 3（４） max z = 3x 1 + x 2（５） max z = 5x 1 + 2 x 2 + 4 x 34、试用大M 法或两阶段求下述线性规划问题的最优解和最优值（只做一题即可）x 1 + x 2 ≤4－x 1 + x 2 ≤2 6x 1 + 2x 2≤18 x １ ，x 2 ≥0s.t. x 1 + 2x 2 + 3x 3≤84x 1 + 5x 3≤12 x 1，x 2 ，x 3 ≥0 s.t. 3 x 1 + x 2 + 2 x 3 ≤ 4 6 x 1 + 3 x 2 + 5 x 3 ≤ 10 x 1，x 2，x 3 ≥ 0s.t.（３） max z = 3x 1 – 3 x 2x 1 + x 2 ≥12x 1 + 3x 2 ≤6x 1，x 2 ≥0（4）32122max x x x z +-=s.t.⎪⎪⎩⎪⎪⎨⎧≥≥-≥+-≥++0,,022263213231321x x x x x x x x x x5、写出下列问题的对偶规划（3）s.t.⎪⎩⎪⎨⎧≥≤-+-≥++-+=0,,12222max 32132132121x x x x x x x x x x x Z （4）⎪⎩⎪⎨⎧≥=+-≥+-++-=0,,6242..2min 32121321321x x x x x x x x t s x x x f6、考虑如下线性规划（1）写出对偶规划。
运筹学练习题1、 用图解法求下列线性规划问题：⎪⎩⎪⎨⎧≥≥+≥++=0,42366432min 21212121x x x x x x x x z2、用单纯形法求下列线性规划问题：1212312123max 10534952 8,,0z x x x x x x x x x x =+++=⎧⎪+≤⎨⎪≥⎩ 3、 线性规划问题0,,max ≥==X b AX CX z ,设)0(X为问题的最优解。
若目标函数中用*C 代替C 后，问题的最优解变为*X ，证明：0)*)(*()0(≥--X X C C4、某饲养场饲养动物出售，设没头动物每天至少需700g 蛋白质、30g 矿物质、100g 维生素。
要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。
（只建立模型，不求解）5、 某医院护士值班班次、每班工作时间及各班所需护士数如下表，每班护士值班开始向病房报到，试决定：（1） 若护士上班后连续工作8h ，该医院最少需要多少名护士？ （2） 若除22：00上班的护士连续工作8h 外（取消第6班），其它护士班次由医院排定上6、⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≤++≤++≤+≤+++++=)4,3,2,1(096628342max 321432214214321j x x x x x x x x x x x x x x x x z j要求：（1）写出对偶问题；（2）已知对偶问题的最优解为)0,4,2,2(*=X ，试根据对偶理论直接求出对偶问题的最优解。
7、下表给出了各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解：10个井位的代号为12310,,s s s s ，相应的钻井费用为1210,,,c c c ，并且井位选择上要满足下列限制条件：①选择了1s 和7s 就不能选择钻探8s ；反过来也一样；②选择了3s 或4s 就不能选5s ；反过来也一样；③在5678,,,s s s s 中最多只能选两个；试建立这个问题的整数规划模型。
案例1，原始问题：某公司现有三条生产线，由于原有产品出现销售量下降的情况，管理部门决定调整公司的产品线，停产不赢利的产品以释放产能来生产两种新产品。
其中，生产甲产品要占用生产线1和生产线3的部分产能，产品乙需要占用生产线2和3的部分产能。
管理部门需要考虑下列问题：1、公司是否应该生产这两种产品2、若生产，则两种产品的数量如何确定数据：运筹小组与管理部门研究后去顶，两种产品的数量如何确定以使产品的总利润最大因此，需要如下的信息：1、每条生产线的可得生产能力是多少2、生产每一单位产品需要每条生产线多少生产能力3、每种产品的单位利润是多少生产部门和财务部门经过分析，提出如下数据：模型：1、要做出什么决策（决策变量）2、做出的决策会有哪些条件限制（约束条件）3、这些决策的全部评价标准是什么（目标函数）max z=3x1+5x2st. x1<=42x2<=123x1+2x2<=18x1,x2>=0决策：x1=2,x2=6, z=3600生产时间信息：按模型所确定的生产方案需要生产线2和3的所有时间，只有生产线1有2小时的剩余。
1、用单纯形表求解以下线性规划问题（1）max z=x1-2x2+x3.x1+x2+x3≤122x1+x2-x3≤6-x1+3x2≤9x1,x2,x3≥0解：标准化，将目标函数转变成极小化，引进松弛变量x4,x5,x60,得到：z’min-x1+2x2-x3=.x1+x2+x3+x4=122x1+x2-x3+x5= 6-x1+3x2+x6= 9x1,x2,x3,x4,x5,x6≥0列出初始单纯形表z’x1x2x3x4x5x6RHSz’x412/1x5--x6--选取x3为进基变量，确定x4为离基变量z’x1x2x3x4x5x6RHSz’x312/1x518/3x6--得到最优解（x1, x2, x3, x4, x5, x6）=（0, 0, 12, 0, 18, 9），min z’=-12，max z=12由于其中非基变量x1在目标函数中的系数为0，x1进基，x5离基，可以得到另一最优解：z’x1x2x3x4x5x6RHSz’x3x1x6新的最优解为（x1,x2,x3,x4,x5,x6）=（6, 0, 6, 0, 0, 15），min z’=-12，max z=12原问题最优解的全体为：x x x x x x 123456001201891606001566066018156⎡⎣⎢⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥⎥=⎡⎣⎢⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥⎥+-⎡⎣⎢⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥⎥=-+-⎡⎣⎢⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥⎥λλλλλλ()，（0≤≤1），都有max z=12（2） max z= x 1 +3x 2 +4x 3. 3x 1 +2x 2 ≤13 x 2 +3x 3 ≤172x 1 +x 2 +x 3 =13x 1,x 2,x 3≥0解：将目标函数转化成极小化，引进松弛变量x 4，x 5，x 6≥0，得到min z’= -x 1 -3x 2 -4x 3. 3x 1 +2x 2 +x 4 =13 x 2 +3x 3 +x 5 =17 2x 1 +x 2 +x 3 =13x 1,x 2,x 3,x 4,x 5,≥0引进人工变量x 60，构造辅助问题：minz’’= x 6. 3x 1 +2x 2 +x 4 =13 x 2 +3x 3 +x 5 =172x 1+x 2+x 3+x 6=13x1,x2,x3,x4,x5,x6≥0列出辅助问题的系数矩阵表：z’x1x2x3x4x5x6RHS’z’’x4x5x6消去基变量x6在目标函数中的系数，并开始单纯形叠代：z’x1x2x3x4x5x6RHS’z’’x413/3 x5--x613/2 x1进基，x4离基，z’x1x2x3x4x5x6RHS’z’’x1--x517/3x613/3 x3进基，x6离基，z’x1x2x3x4x5x6RHS’z’’x1x5x3辅助问题已经获得最优解，且min z’’=0，因而可以转入第二阶段，其系数矩阵表为：z’x1x2x3x4x5RHSz’x1x5x3消去基变量x1，x3在目标函数中的系数：z’x1x2x3x4x5RHSz’x113/2x54/2x3--x2进基，x5离基z’x1x2x3x4x5RHSz’x1x2x3得到原问题的最优解：（x1, x2, x3）=（3, 2, 5），min z’=-29，max z=293、用对偶单纯形法求解以下问题(1)min z=4x1+6x2+18x3.x1+3x3≥3x2+2x3≥5x1,x2,x3≥0引进松弛变量x4、x5≥0min z=4x1+6x2+18x3.-x1-3x3+x4=-3-x2-2x3+x5=-5x1,x2,x3，x4，x5≥0列出单纯形表zx4x54/118/3x 4离基，x 1进基z x 1 x 56/16/2x 5离基，x 3进基z x 1x 324x 1离基，x 2进基z x 2 x 3最优解为x 1=0，x 2=3，x 3=1，x 4=0，x 5=0，min z=36某工厂用甲、乙、丙三种原料生产A,B,C,D 四种产品，每种产品消耗原料定额以及（1） 求使总利润最大的生产计划和按最优生产计划生产时三种原料的耗用量和剩余量；（2） 求四种产品的利润在什么范围内变化，最优生产计划不会变化 （3） 求三种原料的影子价格和四种产品的机会成本，并解释最优生产计划中有的产品不安排生产的原因。
（4） 在最优生产计划下，哪一种原料更为紧缺如果甲原料增加120吨，这时紧缺程度是否有变化(1)利润最大化的线性规划模型为： max z= 25x 1 +12x 2 +14x 3 +15x 4 . 3x 1 +2x 2+x 3 +4x 4 ≤2400 2x 1 +2x 3+3x 4 ≤3200 x 1 +3x 2 +2x 4 ≤1800x 1,x 2,x 3,x 4≥0单纯形表为： z x 1 x 2 x 3 x 4 x 5 x 6 x 7 RHS zx 5 x 6 x 7x 1进基，x 5离基 z x 1 x 2 x 3x 4x 5 x 6 x 7 RHS zx 1 x 6x7x3进基，x6离基z x1x2x3x4x5x6x7RHS Arrayzx1x3x7x2进基，x1离基z x1x2x3x4x5x6x7RHSzx2x3x7最优解为：x1=0，x2=400，x3=1600，x4=0，x5=0，x6=0，x7=600，max z=27200即最优生产计划为：产品A：不生产；产品B：400万件；产品C：1600万件；产品D：不生产，最大利润：27200万元。
原料甲：耗用2400吨，没有剩余；原料乙：耗用3200吨，没有剩余；原料丙：耗用1200吨，剩余600吨。
（2）产品A利润变化范围：-C -25+-12 -14 -15 0 0 0 0z x 1 x 2 x 3 x 4 x 5 x 6 x 7 RHS -C B z 1 -1- 0 0 -21 -6 -4 0 -27200 -12 x 2 0 1 1 0 5/4 1/2 -1/4 0 400 -14 x 3 0 1 0 1 3/21/2 0 1600 0x 7-2-7/4 -3/23/41600-1-≤0，≥-1，-c 1’=-c 1+≥-25-1=-26，即c 1≤26（万元/万件） 产品B 利润变化范围：-C-25-12+-14-15z x 1 x 2 x 3 x 4 x 5 x 6 x 7 RHS -C Bz1-1--21+5/4-6+1/2-4-1/4 0-27200+400-12+x 2115/41/2-1/40 400-14 x 3 0 1 0 1 3/2 0 1/2 0 1600 0x 7-2-7/4-3/23/41600--≤-+≤-+≤--≤⎧⎨⎪⎪⎩⎪⎪102154061204140δδδδ///，δδδδ≥-≤≤≥-⎧⎨⎪⎪⎩⎪⎪18451216/，-1≤≤12，-13≤-12+≤0，-13≤-c 2’≤0， 即：0≤c 2’≤13。
产品C 利润的变化范围：-C-25-12-14+-15zx 1x 2x 3x 4x 5x 6x 7RHS-C B z 1 -1-0 0 -21+3/2-6 -4+1/20 -27200+1600-12 x 2 0 1 1 0 5/4 1/2 -1/4 0 400 -14+x 3113/21/21600x 7 0 -2 0 0 -7/4 -3/2 3/4 1 600--≤-+≤-+≤⎧⎨⎪⎩⎪10213204120δδδ//，δδδ≥-≤≤⎧⎨⎪⎩⎪1148 -1≤≤8，-15≤-14+≤-6，-15≤-c 3’≤-6，6≤c 3’≤15 产品D 的变化范围-C-25-12-14-15+z x 1 x 2 x 3 x 4 x 5 x 6 x 7 RHS -C Bz1-1-21--6-4-27200-12 x 2 0 1 1 0 5/4 1/2 -1/4 0 400 -14 x 3 0 1 0 1 3/2 0 1/2 0 1600 0x 7-2-7/4-3/23/41600-21-≤0，≥-21，-15+≥-36，-c 4’≥-36，c 4’≤36。
（3） 求三种原料的影子价格和四种产品的机会成本 由最优单纯形表可知，原料甲、乙、丙的影子价格分别为：6万元/吨、4万元/吨、0万元/吨。
产品A 、B 、C 、D 的机会成本分别为：26万元/万件、12万元/万件、14万元/万件、36万元/万件。
产品A 、D 在最优解中不安排生产的原因是机会成本大于利润。
（4） 在最优解中，原料甲的影子价格（6万元/吨）最大，因此这种原料最紧缺。
如果原料A 增加120吨，最优单纯形表的右边常数成为：B b -'=--⎡⎣⎢⎢⎢⎤⎦⎥⎥⎥+⎡⎣⎢⎢⎢⎤⎦⎥⎥⎥=⎡⎣⎢⎢⎢⎤⎦⎥⎥⎥+-⎡⎣⎢⎢⎢⎤⎦⎥⎥⎥=⎡⎣⎢⎢⎢⎤⎦⎥⎥⎥≥11214001203234124001203200180040016006006000180100016004200///// 因此最优基保持不变，影子价格不变，原料的紧缺程度不变。
一、以下集合中，哪些是凸集，哪些不是凸集（1） {(x 1,x 2)| x 1+x 2≤1}是凸集 （2） {(x 1,x 2,x 3)| x 1+x 2≤1,x 1-x 3≤2} 是凸集 （3） {(x 1,x 2)| x 1-x 2=0}是凸集（4） {(x 1,x 2,x 3)| x 1≥x 2,x 1+x 2+x 3≤6} 是凸集 （5） {(x 1,x 2)| x 1=1,|x 2|≤4}是凸集 （6） (x 1,x 2,x 3)| x 3=|x 2|, x 1≤4}不是凸集。
