考研运筹学试题及答案pdf下载

考研运筹学试题及答案pdf下载考研运筹学试题及答案一、选择题（每题2分，共30分）1.线性规划问题的标准形式要求（）A.目标函数求最大值，约束条件为等式，变量非负B.目标函数求最小值，约束条件为等式，变量非负C.目标函数求最大值，约束条件为不等式，变量无限制D.目标函数求最小值，约束条件为不等式，变量无限制答案：A解析：线性规划问题的标准形式通常要求目标函数求最大值，约束条件为等式，且所有变量非负。选项B虽然约束条件为等式且变量非负，但目标函数是求最小值，不符合标准形式。选项C和D的约束条件为不等式，不符合标准形式。因此，正确答案是A。2.在单纯形法中，检验数表示（）A.基变量的价值系数B.非基变量增加一个单位时目标函数的变化量C.基变量增加一个单位时目标函数的变化量D.约束条件的松弛量答案：B解析：在单纯形法中，检验数表示非基变量增加一个单位时目标函数的变化量。如果检验数为正，表示增加该非基变量可以使目标函数值增加；如果检验数为负，表示增加该非基变量会使目标函数值减少。因此，正确答案是B。3.对偶问题的对偶是（）A.原问题B.另一个对偶问题C.无解D.不确定答案：A解析：根据对偶理论，对偶问题的对偶就是原问题。这是对偶理论的基本性质之一。因此，正确答案是A。4.在运输问题中，基变量的个数是（）A.m+nB.m+n-1C.m×nD.m+n+1答案：B解析：在运输问题中，基变量的个数是m+n-1，其中m是供应点的个数，n是需求点的个数。这是由运输问题的特殊结构决定的。因此，正确答案是B。5.整数规划问题中，如果要求变量只能取0或1，这种规划称为（）A.纯整数规划B.混合整数规划C.0-1整数规划D.非线性整数规划答案：C解析：整数规划问题根据变量取值要求可分为多种类型。如果要求变量只能取0或1，这种规划称为0-1整数规划。纯整数规划要求所有变量都取整数值；混合整数规划要求部分变量取整数值；非线性整数规划的目标函数或约束条件是非线性的。因此，正确答案是C。6.动态规划的基本方程是（）A.最优性原理B.贝尔曼方程C.状态转移方程D.决策方程答案：B解析：动态规划的基本方程是贝尔曼方程，它基于最优性原理，表示最优策略具有这样的性质：无论初始状态和初始决策如何，其余的决策必须对于由初始决策所导致的状态构成最优策略。因此，正确答案是B。7.在图论中，欧拉回路是指（）A.包含图中所有顶点的回路B.包含图中所有边的回路C.包含图中所有顶点和边的回路D.从一个顶点出发回到该顶点的路径答案：B解析：在图论中，欧拉回路是指包含图中所有边的回路，且每个边恰好被访问一次。包含所有顶点的回路不一定是欧拉回路；包含所有顶点和边的回路不一定是简单的欧拉回路；从一个顶点出发回到该顶点的路径不一定是回路，也不一定包含所有边。因此，正确答案是B。8.排队论中，M/M/1模型的"1"表示（）A.顾客到达的间隔时间服从泊松分布B.服务时间服从指数分布C.只有一个服务台D.系统容量为1答案：C解析：在排队论中，M/M/1模型中的各个符号有特定含义：第一个M表示顾客到达的间隔时间服从泊松分布；第二个M表示服务时间服从指数分布；1表示只有一个服务台。因此，正确答案是C。9.存储论中，不允许缺货的经济订货批量模型假设（）A.需求率是常数B.订货提前期是常数C.不允许缺货D.以上都是答案：D解析：不允许缺货的经济订货批量模型通常假设需求率是常数、订货提前期是常数、不允许缺货。这些是该模型的基本假设条件。因此，正确答案是D。10.决策论中，完全不确定型决策问题是指（）A.自然状态完全确定B.自然状态完全不确定C.自然状态部分确定D.自然状态概率已知答案：B解析：在决策论中，完全不确定型决策问题是指自然状态完全不确定，即决策者不知道各种自然状态发生的概率，只能根据决策准则进行决策。自然状态完全确定是确定型决策问题；自然状态部分确定是风险型决策问题；自然状态概率已知也是风险型决策问题。因此，正确答案是B。11.对策论中，鞍点是指（）A.矩阵对策中的最大最小值点B.矩阵对策中的最小最大值点C.矩阵对策中最大最小值等于最小最大值的点D.矩阵对策中的任意均衡点答案：C解析：在对策论中，鞍点是指矩阵对策中最大最小值等于最小最大值的点。在鞍点处，局中人双方都有最优策略，且这些策略构成纳什均衡。最大最小值点和最小最大值点不一定是鞍点；任意均衡点也不一定是鞍点。因此，正确答案是C。12.线性规划的对偶问题中，原问题的基变量对应对偶问题的（）A.基变量B.非基变量C.松弛变量D.人工变量答案：B解析：根据对偶理论，线性规划的原问题和对偶问题之间存在对应关系：原问题的基变量对应对偶问题的非基变量，原问题的非基变量对应对偶问题的基变量。这种对应关系在对偶单纯形法中有重要应用。因此，正确答案是B。13.在目标规划中，优先级最高的目标应该（）A.首先满足B.最后满足C.根据实际情况决定D.不予考虑答案：A解析：在目标规划中，不同的目标通常被赋予不同的优先级，优先级最高的目标应该首先满足。这是目标规划的基本思想，即按照目标的重要性顺序进行优化。因此，正确答案是A。14.网络计划技术中，关键路径是指（）A.从开始节点到结束节点最长的路径B.从开始节点到结束节点最短的路径C.包含关键活动的路径D.总时差为零的活动的路径答案：A解析：在网络计划技术中，关键路径是指从开始节点到结束节点最长的路径。关键路径上的活动称为关键活动，它们的总时差为零，决定了整个项目的最短完成时间。包含关键活动的路径不一定是关键路径；总时差为零的活动的路径也不一定是关键路径。因此，正确答案是A。15.在灵敏度分析中，目标函数系数的允许变化范围是指（）A.保持当前最优解不变的范围B.保持当前最优基不变的范围C.保持当前最优目标函数值不变的范围D.保持当前对偶解不变的范围答案：B解析：在灵敏度分析中，目标函数系数的允许变化范围通常是指保持当前最优基不变的范围。在这个范围内，虽然最优解可能发生变化，但最优基保持不变，这有助于理解模型的稳定性。保持当前最优解不变的范围通常更小；保持当前最优目标函数值不变的范围和对偶解不变的范围与目标函数系数的允许变化范围不同。因此，正确答案是B。二、填空题（每空2分，共20分）1.线性规划问题的数学模型由三个要素组成：目标函数、约束条件和__________。答案：决策变量解析：线性规划问题的数学模型由三个基本要素组成：目标函数（需要优化的目标）、约束条件（限制决策变量的条件）和决策变量（问题中需要确定的变量）。决策变量是线性规划模型的核心，代表了问题中需要确定的未知量。2.单纯形法迭代过程中，如果所有检验数都__________，则当前解是最优解。答案：非正（或≤0）解析：在单纯形法迭代过程中，如果所有检验数都非正（即≤0），则当前解是最优解。这是因为检验数表示非基变量增加一个单位时目标函数的变化量，如果所有检验数非正，则任何非基变量的增加都不会使目标函数值增加，因此当前解已经是最优解。3.运输问题中，如果总供应量__________总需求量，则称为不平衡运输问题。答案：大于解析：运输问题中，如果总供应量大于总需求量，则称为供应量大于需求量的不平衡运输问题；反之，如果总供应量小于总需求量，则称为需求量大于供应量的不平衡运输问题。不平衡运输问题可以通过引入虚拟的供应点或需求点转化为平衡运输问题。4.整数规划问题中，如果要求所有变量都取整数值，这种规划称为__________整数规划。答案：纯解析：整数规划问题根据变量取值要求可分为纯整数规划和混合整数规划。纯整数规划要求所有变量都取整数值；混合整数规划要求部分变量取整数值，其他变量可以取连续值。此外，如果变量只能取0或1，则称为0-1整数规划。5.动态规划的基本思想是将多阶段决策问题转化为一系列__________问题。答案：单阶段解析：动态规划的基本思想是将多阶段决策问题转化为一系列单阶段问题，通过求解这些单阶段问题来得到原问题的最优解。这种方法利用了问题的最优子结构性质，即一个问题的最优解包含其子问题的最优解。6.在图论中，一个连通图中任意两点之间都有路径相连，这样的图称为__________图。答案：连通解析：在图论中，连通图是指一个图中任意两点之间都有路径相连的图。如果图中存在两点之间没有路径相连，则称为不连通图。连通性是图的基本性质之一，在许多图论算法和应用中都有重要意义。7.排队论中，M/M/c/c模型的第二个"c"表示__________。答案：系统容量解析：在排队论中，M/M/c/c模型中的各个符号有特定含义：第一个M表示顾客到达的间隔时间服从泊松分布；第二个M表示服务时间服从指数分布；第一个c表示有c个服务台；第二个c表示系统容量为c，即系统中最多有c个顾客（包括正在接受服务的顾客）。8.存储论中，经济订货批量（EOQ）模型的目标是使__________成本最小化。答案：总存储解析：经济订货批量（EOQ）模型的目标是使总存储成本最小化。总存储成本包括订货成本和存储成本，随着订货批量的增加，订货成本减少，但存储成本增加；反之亦然。EOQ模型通过平衡这两种成本，找到使总存储成本最小的最优订货批量。9.决策论中，风险型决策问题是指自然状态的概率__________的决策问题。答案：已知解析：在决策论中，根据自然状态的概率是否已知，决策问题可分为确定型决策问题、风险型决策问题和不确定型决策问题。风险型决策问题是指自然状态的概率已知的决策问题；不确定型决策问题是指自然状态的概率未知的决策问题；确定型决策问题是指自然状态完全确定的决策问题。10.对策论中，零和博弈是指一方的收益等于另一方的__________的博弈。答案：损失解析：在对策论中，零和博弈是指一方的收益等于另一方的损失的博弈，即博弈双方的总收益为零。在零和博弈中，一方的所得就是另一方的所失，双方的利益是完全对立的。与非零和博弈相比，零和博弈的分析更为简单，因为只需要考虑一方的收益即可。三、判断题（每题1分，共10分）1.线性规划问题的可行域一定是凸集。答案：正确解析：线性规划问题的可行域是由线性不等式或等式约束定义的集合，根据凸集的定义，线性规划问题的可行域一定是凸集。这是因为凸集的任意两点连线上的点仍然在集合内，而线性约束保证了这一性质。2.对偶问题的对偶一定是原问题。答案：正确解析：根据对偶理论，对偶问题的对偶就是原问题。这是对偶理论的基本性质之一，也是对偶理论在理论和应用上的重要基础。3.运输问题中，如果所有供应量和需求量都是整数，则最优解中所有变量的取值也一定是整数。答案：正确解析：运输问题具有整数解性质，即如果所有供应量和需求量都是整数，则最优解中所有变量的取值也一定是整数。这是由运输问题的特殊结构决定的，也是运输问题可以用单纯形法求解而不需要特殊整数规划方法的原因。4.整数规划问题可以通过简单地忽略整数约束，求解对应的线性规划问题，然后对结果取整得到最优解。答案：错误解析：整数规划问题不能通过简单地忽略整数约束，求解对应的线性规划问题，然后对结果取整得到最优解。这是因为取整后的解可能不满足约束条件，或者不是最优解。整数规划问题需要特殊的求解方法，如分支定界法、割平面法等。5.动态规划可以解决所有多阶段决策问题。答案：错误解析：动态规划可以解决具有最优子结构和无后效性的多阶段决策问题，但不能解决所有多阶段决策问题。有些多阶段决策问题可能不具备这些性质，或者状态空间过大，导致动态规划方法不可行。6.在图中，如果存在欧拉回路，则一定存在哈密顿回路。答案：错误解析：在图中，存在欧拉回路不一定存在哈密顿回路。欧拉回路要求遍历所有边且每边仅一次，而哈密顿回路要求遍历所有顶点且每顶点仅一次（除起点和终点外）。这两个概念是独立的，一个图可以有一个而没有另一个。7.排队论中，M/M/1模型的系统稳态概率与顾客到达率和服务率有关。答案：正确解析：在M/M/1模型中，系统稳态概率与顾客到达率和服务率有关。具体来说，系统中有n个顾客的稳态概率为ρ^n，其中ρ=λ/μ是顾客到达率与服务率的比值，称为系统利用率。只有当ρ<1时，系统才能达到稳态。8.存储论中，不允许缺货的经济订货批量模型假设需求是连续的。答案：错误解析：不允许缺货的经济订货批量模型通常假设需求是离散的，而不是连续的。该模型假设需求是恒定的，以固定的速率发生，但需求是离散的，即在特定的时间点上发生。9.决策论中，完全不确定型决策问题可以通过期望值准则进行决策。答案：错误解析：决策论中，完全不确定型决策问题是指自然状态的概率未知的决策问题，不能通过期望值准则进行决策。期望值准则适用于风险型决策问题，即自然状态的概率已知的决策问题。对于完全不确定型决策问题，需要采用其他准则，如最大最小准则、最大最大准则、最小最大后悔准则等。10.对策论中，所有矩阵对策都有纯策略纳什均衡。答案：错误解析：对策论中，并非所有矩阵对策都有纯策略纳什均衡。有些矩阵对策只有混合策略纳什均衡，而没有纯策略纳什均衡。例如，"石头、剪刀、布"游戏就是一个只有混合策略纳什均衡而没有纯策略纳什均衡的例子。四、计算题（每题10分，共40分）1.求解以下线性规划问题：maxz=2x₁+3x₂s.t.x₁+x₂≤42x₁+x₂≤6x₁,x₂≥0答案：（1）将线性规划问题转化为标准形式：maxz=2x₁+3x₂+0s₁+0s₂s.t.x₁+x₂+s₁=42x₁+x₂+s₂=6x₁,x₂,s₁,s₂≥0（2）建立初始单纯形表：基变量|x₁|x₂|s₁|s₂|b-------|----|----|----|----|----s₁|1|1|1|0|4s₂|2|1|0|1|6z|-2|-3|0|0|0（3）选择检验数最负的非基变量x₂作为入基变量，计算最小比值：min(4/1,6/1)=4，所以s₁出基。（4）进行行变换，使x₂列成为单位向量：将第一行除以1，得到新的第一行：x₁|x₂|s₁|s₂|b1|1|1|0|4用第二行减去新的第一行：x₁|x₂|s₁|s₂|b1|0|-1|1|2用z行加上3倍的新第一行：x₁|x₂|s₁|s₂|b1|0|3|0|12得到新的单纯形表：基变量|x₁|x₂|s₁|s₂|b-------|----|----|----|----|----x₂|1|1|1|0|4s₂|1|0|-1|1|2z|1|0|3|0|12（5）选择检验数最负的非基变量x₁作为入基变量，计算最小比值：min(4/1,2/1)=2，所以s₂出基。（6）进行行变换，使x₁列成为单位向量：将第二行除以1，得到新的第二行：x₁|x₂|s₁|s₂|b1|0|-1|1|2用第一行减去新的第二行：x₁|x₂|s₁|s₂|b0|1|2|-1|2用z行减去新的第二行：x₁|x₂|s₁|s₂|b0|0|4|-1|10得到新的单纯形表：基变量|x₁|x₂|s₁|s₂|b-------|----|----|----|----|----x₂|0|1|2|-1|2x₁|1|0|-1|1|2z|0|0|4|-1|10（7）检验所有检验数，发现没有负数，所以当前解是最优解：x₁=2,x₂=2,z=10因此，该线性规划问题的最优解为x₁=2,x₂=2，目标函数最大值为10。2.求解以下运输问题：供应点|供应量|需求点1|需求点2|需求点3-------|--------|--------|--------|--------供应点1|10|2|3|1供应点2|15|5|4|8需求量||12|8|5答案：（1）首先检查是否为平衡运输问题：总供应量=10+15=25总需求量=12+8+5=25总供应量等于总需求量，是平衡运输问题。（2）使用最小元素法求初始解：从最小的运费开始分配：-需求点3的最小运费是供应点1到需求点3的1，分配x₁₃=min(10,5)=5-更新供应点1剩余供应量：10-5=5-更新需求点3剩余需求量：5-5=0（已满足）-剩余最小运费是供应点1到需求点1的2，分配x₁₁=min(5,12)=5-更新供应点1剩余供应量：5-5=0（已满足）-更新需求点1剩余需求量：12-5=7-剩余最小运费是供应点2到需求点2的4，分配x₂₂=min(15,8)=8-更新供应点2剩余供应量：15-8=7-更新需求点2剩余需求量：8-8=0（已满足）-剩余唯一选择是供应点2到需求点1的5，分配x₂₁=min(7,7)=7-更新供应点2剩余供应量：7-7=0（已满足）-更新需求点1剩余需求量：7-7=0（已满足）初始解为：x₁₁=5,x₁₃=5x₂₁=7,x₂₂=8总运费=5×2+5×1+7×5+8×4=10+5+35+32=82（3）计算检验数：使用位势法计算检验数：设供应点1的位势为u₁，供应点2的位势为u₂需求点1的位势为v₁，需求点2的位势为v₂，需求点3的位势为v₃对于基变量，有：u₁+v₁=c₁₁=2u₁+v₃=c₁₃=1u₂+v₁=c₂₁=5u₂+v₂=c₂₂=4设u₁=0，则：v₁=2-u₁=2v₃=1-u₁=1u₂=5-v₁=3v₂=4-u₂=1计算非基变量的检验数：σ₁₂=c₁₂-(u₁+v₂)=3-(0+1)=2σ₂₃=c₂₃-(u₂+v₃)=8-(3+1)=4所有检验数都非负，因此当前解是最优解。（4）最优解为：x₁₁=5,x₁₃=5x₂₁=7,x₂₂=8总运费=82因此，该运输问题的最优解如上所示，最小总运费为82。3.求解以下0-1整数规划问题：maxz=3x₁+2x₂+5x₃s.t.2x₁+x₂+3x₃≤4x₁+2x₂+x₃≤3x₁,x₂,x₃∈{0,1}答案：（1）由于变量只能取0或1，可以使用枚举法求解：所有可能的组合共有2³=8种，列举如下：组合(x₁,x₂,x₃)|约束1:2x₁+x₂+3x₃≤4|约束2:x₁+2x₂+x₃≤3|目标函数值z=3x₁+2x₂+5x₃----------------|-------------------|-------------------|------------------------(0,0,0)|0≤4(满足)|0≤3(满足)|0(0,0,1)|3≤4(满足)|1≤3(满足)|5(0,1,0)|1≤4(满足)|2≤3(满足)|2(0,1,1)|4≤4(满足)|3≤3(满足)|7(1,0,0)|2≤4(满足)|1≤3(满足)|3(1,0,1)|5>4(不满足)|2≤3(满足)|-(1,1,0)|3≤4(满足)|3≤3(满足)|5(1,1,1)|6>4(不满足)|4>3(不满足)|-（2）从满足约束的组合中，选择目标函数值最大的组合：满足约束的组合有：(0,0,0)、(0,0,1)、(0,1,0)、(0,1,1)、(1,0,0)、(1,1,0)对应的目标函数值分别为：0、5、2、7、3、5最大目标函数值为7，对应的解为x₁=0,x₂=1,x₃=1（3）验证最优解：对于解x₁=0,x₂=1,x₃=1：约束1：2×0+1+3×1=4≤4，满足约束2：0+2×1+1=3≤3，满足目标函数值：3×0+2×1+5×1=7因此，该0-1整数规划问题的最优解为x₁=0,x₂=1,x₃=1，目标函数最大值为7。4.求解以下动态规划问题：某企业需要在4年内更新一台设备，每年年初都有两种选择：继续使用旧设备或购买新设备。设备在各年年初的购买价格、使用成本和残值如下表所示：年份|购买价格|使用成本|残值----|---------|---------|-----第1年|100|10|50第2年|110|12|50第3年|120|15|40第4年|130|18|30设备使用年限越长，使用成本越高。使用一年后设备的残值等于购买价格减去折旧。目标是使4年内的总成本（购买价格+使用成本-残值）最小。答案：（1）建立动态规划模型：阶段：按年份划分，共4个阶段（第1年到第4年）状态：设备的使用年限决策：继续使用或购买新设备状态转移：如果继续使用，使用年限加1；如果购买新设备，使用年限重置为1目标函数：最小化4年内的总成本设f_k(t)表示在第k年初设备已使用t年时，从第k年到第4年的最小总成本。则动态规划的基本方程为：f_k(t)=min{继续使用：c_k(t)+f_{k+1}(t+1),如果t+1≤设备最大使用年限购买新设备：p_k+c_k(1)-s_k+f_{k+1}(1)}其中c_k(t)表示第k年设备已使用t年的使用成本，p_k表示第k年购买新设备的价格，s_k表示第k年设备的残值。边界条件：f_5(t)=0，因为第5年不需要考虑成本。（2）从第4年开始逆向求解：第4年：如果继续使用：f_4(1)=c_4(1)=18f_4(2)=c_4(2)=18（假设使用成本与使用年限无关，实际上应更高）f_4(3)=c_4(3)=18f_4(4)=c_4(4)=18如果购买新设备：f_4(1)=min(f_4(1),p_4+c_4(1)-s_4+f_5(1))=min(18,130+18-30+0)=min(18,118)=18f_4(2)=min(f_4(2),p_4+c_4(1)-s_4+f_5(1))=min(18,118)=18f_4(3)=min(f_4(3),p_4+c_4(1)-s_4+f_5(1))=min(18,118)=18f_4(4)=min(f_4(4),p_4+c_4(1)-s_4+f_5(1))=min(18,118)=18第3年：如果继续使用：f_3(1)=c_3(1)+f_4(2)=15+18=33f_3(2)=c_3(2)+f_4(3)=15+18=33f_3(3)=c_3(3)+f_4(4)=15+18=33如果购买新设备：f_3(1)=min(f_3(1),p_3+c_3(1)-s_3+f_4(1))=min(33,120+15-40+18)=min(33,113)=33f_3(2)=min(f_3(2),p_3+c_3(1)-s_3+f_4(1))=min(33,113)=33f_3(3)=min(f_3(3),p_3+c_3(1)-s_3+f_4(1))=min(33,113)=33第2年：如果继续使用：f_2(1)=c_2(1)+f_3(2)=12+33=45f_2(2)=c_2(2)+f_3(3)=12+33=45如果购买新设备：f_2(1)=min(f_2(1),p_2+c_2(1)-s_2+f_3(1))=min(45,110+12-50+33)=min(45,105)=45f_2(2)=min(f_2(2),p_2+c_2(1)-s_2+f_3(1))=min(45,105)=45第1年：如果继续使用：f_1(1)=c_1(1)+f_2(2)=10+45=55如果购买新设备：f_1(1)=min(f_1(1),p_1+c_1(1)-s_1+f_2(1))=min(55,100+10-50+45)=min(55,105)=55（3）最优决策：从计算结果可以看出，无论何时购买新设备，总成本都是相同的。因此，可以采取任何策略。例如：-第1年购买新设备，第2年继续使用，第3年继续使用，第4年继续使用-第1年继续使用（假设已有1年设备），第2年继续使用，第3年继续使用，第4年继续使用-等等最小总成本为55。因此，该动态规划问题的最小总成本为55，可以采取任何设备更新策略。五、证明题（每题10分，共20分）1.证明：线性规划问题的可行域是凸集。证明：设线性规划问题的可行域为D={x|Ax≤b,x≥0}，其中A是m×n矩阵，b是m维向量。要证明D是凸集，需要证明对于任意x₁,x₂∈D，以及任意λ∈[0,1]，都有λx₁+(1-λ)x₂∈D。因为x₁∈D，所以Ax₁≤b，x₁≥0；因为x₂∈D，所以Ax₂≤b，x₂≥0。对于任意λ∈[0,1]，有：A(λx₁+(1-λ)x₂)=λAx₁+(1-λ)Ax₂≤λb+(1-λ)b=b且λx₁+(1-λ)x₂≥0（因为x₁≥0，x₂≥0，λ≥0，1-λ≥0）因此，λx₁+(1-λ)x₂∈D，所以D是凸集。证毕。2.证明：在运输问题中，如果所有供应量和需求量都是整数，则最优解中所有变量的取值也一定是整数。证明：运输问题可以表示为：min∑∑c_ijx_ijs.t.∑x_ij=a_i(i=1,2,...,m)∑x_ij=b_j(j=1,2,...,n)x_ij≥0其中a_i是供应点i的供应量，b_j是需求点j的需求量，且∑a_i=∑b_j。根据线性规划的基本定理，运输问题的系数矩阵A是全单模的，即A的任何子矩阵的行列式都是0、1或-1。这是因为运输问题的系数矩阵是由单位矩阵通过特定方式构成的。对于全单模矩阵，如果右端项b是整数的，则基本可行解也是整数的。这是因为基本可行解可以通过克莱姆法则求解，而克莱姆法则中涉及到的行列式计算会得到整数结果。在运输问题中，基本可行解对应于基变量，基变量的个数是m+n-1。由于系数矩阵A是全单模的，且右端项b是整数的（供应量和需求量都是整数），所以基本可行解中的基变量取值一定是整数的。非基变量的取值为0，也是整数。因此，最优解中所有变量的取值都是整数。证毕。六、应用题（每题10分，共20分）1.某工厂生产两种产品A和B，使用同一种原材料。生产一件产品A需要2单位原材料，一件产品B需要3单位原材料。工厂每天有100单位原材料可用。产品A的利润是5元/件，产品B的利润是7元/件。根据市场调查，每天至少需要生产10件产品A，产品B的产量不能超过30件。问：如何安排生产计划，使工厂的日利润最大？答案：（1）建立数学模型：设x₁为产品A的日产量，x₂为产品B的日产量。目标函数：maxz=5x₁+7x₂约束条件：2x₁+3x₂≤100（原材料限制）x₁≥10（产品A的最小产量）x₂≤30（产品B的最大产量）x₁,x₂≥0（非负约束）（2）求解线性规划问题：将约束条件标准化：2x₁+3x₂+s₁=100x₁-s₂=10x₂+s₃=30x₁,x₂,s₁,s₂,s₃≥0其中s₁、s₂、s₃是松弛变量。使用单纯形法求解较为复杂，这里采用画图法求解：约束条件对应的直线：2x₁+3x₂=100x₁=10x₂=30可行域的顶点：A(10,0)：x₁=10,x₂=0B(10,(100-2×10)/3=26.67)：x₁=10,x₂=26.67C((100-3×30)/2=5,30)：x₁=5,x₂=30（不满足x₁≥10）D(10,30)：x₁=10,x₂=30（不满足2x₁+3x₂≤100）可行域的顶点只有A点和B点。计算各顶点的目标函数值：A点：z=5×10+7×0=50B点：z=5×10+7×26.67=50+186.69=236.69最大值出现在B点，即x₁=10,x₂=26.67，z=236.69。由于产品B的产量必须是整数，我们需要考虑整数解：当x₂=26时：2×10+3×26=20+78=98≤100，满足原材料限制z=5×10+7×26=50+182=232当x₂=27时：2×10+3×27=20+81=101>100，不满足原材料限制所以x₂=26是可行解，但不是最优整数解。我们需要考虑x₁>10的情况。考虑x₁=11,x₂=26：2×11+3×26=22+78=100≤100，满足原材料限制z=5×11+7×26=55+182=237考虑x₁=12,x₂=25：2×12+3×25=24+75=99≤100，满足原材料限制z=5×12+7×25=60+175=235考虑x₁=13,x₂=24：2×13+3×24=26+72=98≤100，满足原材料限制z=5×13+7×24=65+168=233考虑x₁=14,x₂=23：2×14+3×23=28+69=97≤100，满足原材料限制z=5×14+7×23=70+161=231考虑x₁=15,x₂=23：2×15+3×23=30+69=99≤100，满足原材料限制z=5×15+7×23=75+161=236考虑x₁=16,x₂=22：2×16+3×22=32+66=98≤100，满足原材料限制z=5×16+7×22=80+154=234考虑x₁=17,x₂=22：2×17+3×22=34+66=100≤100，满足原材料限制z=5×17+7×22=85+154=239考虑x₁=18,x₂=21：2×18+3×21=36+63=99≤100，满足原材料限制z=5×18+7×21=90+147=237考虑x₁=19,x₂=20：2×19+3×20=38+60=98≤100，满足原材料限制z=5×19+7×20=95+140=235考虑x₁=20,x₂=20：2×20+3×20=40+60=100≤100，满足原材料限制z=5×20+7×20=100+140=240考虑x₁=21,x₂=19：2×21+3×19=42+57=99≤100，满足原材料限制z=5×21+7×19=105+133=238考虑x₁=22,x₂=18：2×22+3