1/21《管理运筹学》（第二版）课后习题参考答案第1章线性规划（复习思考题）1．什么是线性规划？线性规划的三要素是什么？答：线性规划（LinearProgramming，LP）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。2．求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误？答：（1）唯一最优解：只有一个最优点；（2）多重最优解：无穷多个最优解；（3）无界解：可行域无界，目标值无限增大；（4）没有可行解：线性规划问题的可行域是空集。当无界解和没有可行解时，可能是建模时有错。3．什么是线性规划的标准型？松弛变量和剩余变量的管理含义是什么？答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项0ib，决策变量满足非负性。如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。答：可行解：满足约束条件0XbAX，的解，称为可行解。基可行解：满足非负性约束的基解，称为基可行解。可行基：对应于基可行解的基，称为可行基。最优解：使目标函数最优的可行解，称为最优解。最优基：最优解对应的基矩阵，称为最优基。它们的相互关系如右图所示：5．用表格单纯形法求解如下线性规划。2/2132124maxxxxZs.t.0,,86238321321321xxxxxxxxx解：标准化32124maxxxxZs.t.0,,,,862385432153214321xxxxxxxxxxxxx列出单纯形表jc41200iBCBXb1x2x3x4x5x04x2[8]31102/805x8611018/6j4120041x1/413/8[1/8]1/80(1/4)/(1/8)05x13/26－5/41/4－3/41(13/2)/(1/4)j0－1/23/2-1/2023x28311005x6－2－20－11j－12－50－20故最优解为TX)6,0,2,0,0(*，即2,0,0321xxx，此时最优值为4*)(XZ．6．表1—15中给出了求极大化问题的单纯形表，问表中dccaa,,,,2121为何值及变量属于哪一类型时有：（1）表中解为唯一最优解；（2）表中解为无穷多最优解之一；（3）下一步迭代将以1x代替基变量5x；（4）该线性规划问题具有无界解；（5）该线性规划问题无可行解。表1—15某极大化问题的单纯形表3/21jc1c2c000iBCBXb1x2x3x4x5x03xd41a10004x2－1－501005x32a－3001j1c2c000解：（1）0,0,021ccd；（2）中至少有一个为零）（2121,0,0,0ccccd；（3）22134,0,0adac；（4）0,012ac；（5）1x为人工变量，且1c为包含M的大于零的数，234ad；或者2x为人工变量，且2c为包含M的大于零的数，0,01da．7．用大M法求解如下线性规划。321635maxxxxZs.t.0,,101632182321321321321xxxxxxxxxxxx解：加入人工变量，进行人造基后的数学模型如下：65432100635maxMxxxxxxZs.t.)6,,2,1(0101632182632153214321ixxxxxxxxxxxxxi列出单纯形表4/21jc53600－MiBCBXb1x2x3x4x5x6x04x1812110018/105x1621[3]01016/3－M6x1011100110/1j5+M3+M6+M00004x38/31/35/301－1/3038/563x16/32/31/3101/3016－M6x14/31/3[2/3]00－1/3114/2jM311M32100M312004x1－1/20011/2－5/2－63x3[1/2]0101/2－1/2632x71/2100－1/23/214j1/2000－3/2M2304x400111－351x610201－132x401－10－12j00－10－2－1－M故最优解为TX)0,0,4,0,4,6(*，即0,4,6321xxx，此时最优值为42*)(XZ．8．A，B，C三个城市每年需分别供应电力320，250和350单位，由I，II两个电站提供，它们的最大可供电量分别为400单位和450单位，单位费用如表1—16所示。由于需要量大于可供量，决定城市A的供应量可减少0～30单位，城市B的供应量不变，城市C的供应量不能少于270单位。试建立线性规划模型，求将可供电量用完的最低总费用分配方案。5/21...
