第一章 L.P及单纯形法练习题答案
一、判断下列说法是否正确
1. 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，
可行域的范围一般将扩大。(?)
2. 线性规划问题的每一个基解对应可行域的一个顶点。(?)
3. 如线性规划问题存在某个最优解，则该最优解一定对应可行域边界上的一个点。(?) 4. 单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个基可行解中至少有
一个基变量的值为负。(?)
5. 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表
中删除，而不影响计算结果。(?)
6. 若X1、X2分别是某一线性规划问题的最优解，则X??1X1??2X2也是该线性规划问
题的最优解，其中?1、?2为正的实数。(?)
7. 线性规划用两阶段法求解时，第一阶段的目标函数通常写为MinZ??xai(xai为人工变
i量)，但也可写为MinZ??kixai，只要所有ki均为大于零的常数。(?)
i8. 对一个有n个变量、m个约束的标准型的线性规划问题，其可行域的顶点恰好为Cnm个。
(?)
9. 线性规划问题的可行解如为最优解，则该可行解一定是基可行解。(?)
10. 若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数
的最优解。(?)
二、求得L.P问题
MaxZ?2x1?3x2?8?x1?2x2?x3?4x?x4?16 ?1?4x2?x5?12??xj?0;j?1,2,,5?的解如下： X⑴=(0,3,2,16,0)T;
X⑵=(4,3,-2,0,0)T;
X⑶=(3.5,2,0.5,2,4)T;
X⑺=(4,2,0,0,4)T。
X⑷=(8,0,0,-16,12)T; =(4.5,2,-0.5,-2,4)T; X⑹=(3,2,1,4,4)T;
要求：分别指出其中的基解、可行解、基可行解、非基可行解。 答案：
1
基解：X⑴、X⑵、X⑷、X⑺，可行解：X⑴、X⑶、X⑹、X⑺，基可行解：X⑴、X⑺，非基可行解：．．X、X(或非基可行解：X、X、X、X、X)。 ．三、求解下列线性规划问题：
MinZ??5x1?4x2?x1?2x2?6?2x?x?4 ?s.t.?12?5x1?3x2?15??x1,x2?0⑶
⑹
⑵
⑶
⑷
⑸
⑹
答案：
MaxZ?5x1?4x2?x1?2x2?x3?6化为标准型：??2x1?x2?x4?4
s.t.??5x1?3x2?x5?15??x1,x2,x3,x4,x5?0得初始单纯形表并求解：
cj 5 b 6 4 15 0 4 2 5 -10 19/11 27/11 10/11 -175/11 4 x2 0 x3 0 x4 0 x5 CB XB x1 ?i 6 2? 3 8/5 0 0 0 0 5 0 0 5 4 0 5 4 x3 x4 x5 x3 x1 x5 x3 x1 x2 x4 x1 x2 1 2 5 5? 0 1 0 0 0 1 0 0 0 1 0 0 2 -1 3 4 5/2 -1/2 11/2 13/2? 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 11/7 -3/7 5/7 -5/7 T0 1 0 0 -1/2 1/2 -5/2 -5/2 7/11 3/11 -5/11 1 0 0 0 0 0 1 0 0 0 1 0 -5/11 1/11 2/11 -5/7 2/7 -1/7 -6/7 ?j?cj?zj — 10/11? 19/7? 9 ?j?cj?zj — ?j?cj?zj 5/11? -13/11 19/7 12/7 15/7 -120/7 ?j?cj?zj 120?121519?所有检验数?j?0，已得最优解：X*??,,0,,0?，MinZ??。
7777??
2
第二章 对偶理论与灵敏度分析练习题答案
1．判断下列说法是否正确：
(1) 任何线性规划问题存在并具有惟一的对偶问题；(?)
(2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；(?)
xj，?yi分别为标准形式的原问题与对偶问题的可行解，x*j，yi*分别为其最优解，则恒(3) 设?有?cj?xj??cjx*j??biyi*??bi?yi；(?)
j?1j?1i?1i?1nnmm(4) 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；(?) (5) 已知yi*为线性规划的对偶问题的最优解，若yi*?0，说明在最优生产计划中第i种资源已完全耗尽；(?)
(6) 已知yi*为线性规划的对偶问题的最优解，若yi*?0，说明在最优生产计划中第i种资源一定有剩余；(?)
(7) 若某种资源的影子价格等于k，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k；(?)
(8) 应用对偶单纯形法计算时，若单纯形表中某一基变量xi?0，又xi所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；(?)
(9) 若线性规划问题中的bi，cj值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；(?)
(10) 在线性规划问题的最优解中，如某一变量xj为非基变量，则在原来问题中，无论改变它在目标函数中的系数cj或在各约束中的相应系数aij，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化。(?)
2．下表是某一约束条件用“≤”连接的线性规划问题最优单纯形表格，其中x4、x5为松弛变量。
x1 x2 x3 x4 x5 5/2 0 1/2 1 1/2 0 5/2 1 -1/2 0 -1/6 1/3 σj 0 -4 0 -4 -2 要求：(1)写出原线性规划问题及其对偶问题的数学模型；(2)直接由表写出对偶问题的最优解； (3)其它条件不变时，约束条件右端项b1在何范围内变化，上述最优基不变。(4)若以单价2.5购入第一种资源是否值得，为什么？若有人愿意购买第二种资源应要价多少，为什么？ 答案：
3
XB x3 x1 ｂ
(1)注：该问题得解法非唯一，以下解法只是其中一种（各解法原理相同）。
由题意已知原线性规划问题目标函数为Max（因σj≤0为最优），且c4、c5为0（松弛变量目标函数系数为0）。
?1??1c??c??2?232?c1???4????c1?6?1???1根据?j?cj?CBB?1Pj知：?0???c3??c1???4，得：?c2??2
6??2?c?10??3??1?0???c1???2??3??111?022根据B?A|b????1?120?16?1013??012105?，得：?A|b???? 5?3?1101102???52则原线性规划问题的数学模型为： 其对偶问题的数学模型为：
MaxZ?6x1?2x2?10x3x2?2x3?5??s.t.?3x1?x2?x3?10?x,x,x?0?123
Min??5y1?10y23y2?6??y?y??2 ?2s.t.?1?2y1?y2?10??y1,y2?0(2)直接由表写出对偶问题得最优解为：Y*??4,2? (3)令原解xi?(XB)i?(B-1b)i?bi，得?br的变化范围为：
Max{?bi/air|air?0}??br?Min{?bi/air|air?0}，其中：air??B?1?。则：
iiir5151Max{??}??b1?Min{??(?)}，即?5??b1?15，则0?b1?20
2226(4)以单价2.5购入第一种资源是值得的，因其小于该资源“影子价格”（即2.5<4），可盈利；第二种资源应要价至少为2（影子价格），否则不如自己组织生产。
4
第三章运输问题、第四章目标规划练习题答案
一、判断下列说法是否正确
1．表上作业法实质上就是求运输问题的单纯形法。(?)
2．在运输问题中，只要任意给出一组含(m+n-1)个非零的{xij}，且满足?xij?ai，?xij?bj，
j?1nmi?1就可以作为一个初始可行解。(?)
3．建立目标规划模型时，正偏差变量应取正值，负偏差变量应取负值。(?) 4．线性规划问题是目标规划问题的一种特殊形式。(?) 二、用表上作业法求解下表最小运费方案
甲 乙 丙 丁 产量 产地 1 18 14 17 12 100 2 5 8 13 15 100 3 17 7 12 9 150 50 70 60 80 销量 答案：因该问题为产销不平衡问题，总产量350 (100+100+150)大于总销量260 (50+70+60+80)，故假想一销地“戊”，其销量为90 (350-260)，形成产销平衡问题，并用Vogel法求得初始解：
销地 产地 1 2 3 销量 甲 18 5 50 17 50，0 12 — — — — — 乙 14 8 50 7 20 70,20,0 1 1 1 7 — — 丙 17 13 12 60 60,0 1 1 1 5 5 — 丁 12 15 9 70 80 3 3 3 3 3 3 10 戊 90 0 0 0 90，0 0 0 — — — — 产量 100 10 100 50,0 差额 12 12 2 2 5 12 5 8 5 — — — 销地 150 7 7 2 2 3 9 130,70 差 额 用位势法求空格检验数： 1 2 3 vj
甲 18 5 50 17 13 11 4 4 乙 14 8 50 7 20 7 2 丙 17 13 0 12 60 12 丁 12 15 5 9 70 10 9 5
戊 90 2 3 -3 0 0 0 ui 3 1 0