1、（一）选择填空题1下面给出某线性规划问题的单纯形初表和终表（Min 型）：CB XB B-1b0 1 -3 0 2 0x1 x2 x3 x4 x5 x60 x1 70 x4 120 x6 101 3 -1 0 2 00 -2 4 1 0 00 -4 3 0 8 1 j CB XB B-1b x1 x2 x3 x4 x5 x6x2 x6 2/5 0 1/10 01/5 1 3/10 01 0 -1/2 1 j (1)初表的出基变量为 ，进基变量为 。1*)2(B最 优 基 逆(3)填完终表。 *)4(X最 优 解 *5y对 偶 问 题 最 优 解(6)若原问题增加一个新的非负变量，则对偶问题的最
2、优目标值将（变大、不变、变小） 。 （2007）1用图解法解线性规划时，以下几种情况中不可能出现的是（ ） 。A可行域（约束集合）有界，无有限最优解（或称无解界）B可行域（约束集合）无界，有唯一最优解C可行域（约束集合）是空集，无可行解D可行域（约束集合）有界，有多重最优解 （2006） 2根据线性规划的互补松弛定理，安排生产的产品机会成本一定（ ）利润。A 小于 B 等于 C 大于 D 大于等于 （2006）1用大 M 法求解 Max 型线形规划时，人工变量在目标函数中的系数均为_，若最优解的_中含有人工变量，则原问题无解。 （2005）1. 设线性规划问题 有最优解 和影子价格 ,则线性规
3、划问题0maxbAc*x*y的最优解= ，影子价格= 。02maxbxAc（2004）3. 某工程公司拟从 1、2、3、4 四个项目中选择若干项目。若令 410，个 项 目 未 选 中， 第 个 项 目 被 选 中， 第 iixi请用 的线性表达式表示下列要求：（1）若项目 2 被选中，则项目 4 不能被选中： i（2）只有项目 1 被选中，项目 3 才能被选中： 。 （2004）一、简答（18%）（1）请简述影子价格的定义。（2）在使用单纯型表求解型线性规划时，资源的影子价格在单纯型表的什么位置上？（3）写出影子价格的数学表达式并用其定义加以验证（4）试述运输问题中检验数的经济意义（2003
4、）线性规划原问题中约束的个数与其对偶问题中的 个数相等。若原问题第 j 个约束为等式，则对偶问题第 j 个 自由。 （2002）1 设线性规划问题 max:cx|Axbx0有最优解，且最优解值 z0；如果 c 和 b 分别被 v1所乘，则改变后的问题 （也有、不一定有）最优解；若有最优解，其最优解 (大于、小于、等于)z。 （2002 ）1下列数学模型中 是线性规划模型。(2001)3214max)xZ0,5637.321xts 32954867minax)( 31321 xxxZb0,589635.321xts2下列图形（阴影部分）中 是凸集。(2001)（a） （b） （c）3标准形式的线
5、性规划问题，其可行解 是基本可行解，最优解 是可行解，最优解 能在可行域的某顶点达到。(2001)（a）一定 （b）不一定 （c）一定不4目标函数取极小（min Z）的线性规划问题可以转化为目标函数取极大 b 的线性规划问题求解，原问题的目标函数值等于 。(2001)（a）max Z （b）max（-Z） （c）-max（-Z） （d）-max Z（a）最小元素法 （b）比回路法1. 线性规划单纯形算法的基本步骤是：（1） （2） (3) 每次迭代保持解的 ，改善解值的 。对偶单纯形法每次迭代保持解的 ，改善解值的 。 （2000）2. 设有线性规划问题 ，有一可行基 B（为 A0,|,min
6、XbARXCf中的前 m 列） ，记相应基变量为 ，价格系数为 CB，相应于非基变量为 XN，价格系数为CN，则相应于 B 的基本可行解为 X= ；用非基变量来表示基变量的表达式为XB= ；用非基变量表示目标函数的表达式为 f= ，B 为最优基的条件是 。 （2000）3. 线性规划（Min 型）问题有多重最优解时，其最优单纯形表上的特征为： （2000）6. 某足球队要从 1，2，3，4，5 号五名队员中挑选若干名上场。令54321ii0，号 不 上 场 ，第 号 上 场第ix请用 xi 的线性表达式表示下列要求：（1）从 1，2，3 中至多选 2 名： （2）如果 2 号和 3 号都上场，
7、则 5 号不上场： （3）只有 4 号上场,1 号才上场：(2000)1某工程公司拟从四个项目中选择若干项目，若令 , 1,24.0iixi第 个 项 目 被 选 中第 个 项 目 末 被 选 中请用 xi 的线性表达式表示下列要求：（1）从 1，2，3 项目中至少选择一个： ，（2）只有项目 2 被选中，项目 4 才能被选中 。 （1999）2考虑线形规划问题 123123max54.,0Zxst用单纯型法求解，得其终表如下：Cj 5 12 4 0 -MCB XB B-1b x1 x2 x3 x4 x512 x2 8/55 x1 9/50 1 -1/5 2/5 -1/51 0 7/5 1/5
8、 2/5j0 0 -3/5 -29/5 -M+ 2其中 x4 位松弛变量，x 5 为人工变量。（1）上述模型的对偶模型为 ，（2）对偶模型的最优解为 ，（3）当两种资源分别单独增加一个单位时，目标函数值分别增加 和 ，（4）最优基的逆矩阵 1B（5）如果原问题增加一个变量，则对偶问题的可行域将可能变大还是变小？（1999）1下面给出某线形规划的单纯形初表（表 1）与某一中间表（表 2） （Min 型）：表 1CB XB B-1b 0 1 -3 0 2 0x1 x2 x3 x4 x5 x60 x1 70 x4 120 x6 101 3 -1 0 2 00 -2 4 1 0 00 -4 3 0 8
9、 1j表 2x2x62/5 0 1/10 4/5 1/5 1 3/10 2/5 1 0 -1/2 10j1) 初表的出基变量为_，进基变量为_。2) 填完表 2，该表是否是终表?_。若是，最优值 _*Z3) 此线形规划对偶问题的最优解 _*Y（二）线性规划建模二（20 分） 、某化学制药厂有 m 种有害副产品，它们的数量为 bi（i=1，m ） 。按照规定，必须经过处理，制成 n 种无害物后才能废弃。设 aij 为每制成一单位第j（j=1，n）种无害物可以处理掉第 i 种有害物的数量，cj 为制成一单位第 j 种无害物的费用。1 现欲求各无害物的产量 xj 以使总的处理费用为最小，请写出此问题
10、的线性规划模型；2 写出此问题的对偶规划模型，并解释对偶规划模型的经济意义。 （2007）二（10%） 、某大型企业每年需要进行多种类型的员工培训。假设共有需要培训的需求（如技术类、管理类）为 6 种，每种需求的最低培训人数为 ai，i=1,6, 可供选择的培训方式（如内部自行培训、外部与高校合作培训）有 5 种，每种的最高培训人数为 bj, j=1,5。又设若选择了第 1 种培训方式，则第 3 种培训方式也要选择。记 xij 为第 i 种需求由第 j 方式培训的人员数量， z 为培训总费用。费用的构成包括固定费用和可变费用，第 j种方式的固定费用为 hj（与人数无关） ，与人数 xij 相应
11、的可变费用为 cij（表示第 j 方式培训第 i 种需求类型的单位费用） 。如果以成本费用为优化目标，请建立该培训问题的结构优化模型（不解） 。 （2006）1.某厂使用 A、B 两种原料生产甲、乙、丙三种产品，有关数据见下表：A B 生产成本（万元/吨） 销售价格（万元/吨）甲乙丙1.0 0.50.4 0.60.6 0.58518302035原料成本（万元/吨） 5 7 原料可用数量（吨） 350 460 （1）请写出使总销售利润最大的线性规划模型（其中甲、乙、丙产产量分别记为 x1,x2,x3,约束依 A,B 原料次序）:(2)写出此问题的对偶规划模型（2003）三、 （10%）某服装厂制
12、造大、中、小三种尺寸的防寒服，所用资源有尼龙绸、尼龙棉、劳动力和缝纫设备。缝制一件防寒服所需各种资源的数量如表（单位已适当给定） 。不考虑固定费用，则每种防寒服售出一件所得利润分别为 10、12、13 元，可用资源分别为：尼龙绸1500 米，尼龙棉 1000 米，劳动力 4000，设备 3000 小时。此外，每种防寒服不管缝制多少件，只要做都要支付一定的固定费用：小号为 100 元，中号为 150 元，大号为 200 元。现欲制定一生产计划使获得的利润为最大，请写出其数学模型（不解） 。(2002)型号资源 小 中 大尼龙绸 16 18 19尼龙棉 13 15 16劳动力 4 45 5缝纫设备
13、 28 38 42（三）互补松弛应用二（8%） 、线性规划问题121212max3846,0zx已知其最优解 x1，x 2 0，而第 1，4 两种资源（相应于第 1，4 两约束）均有余量，应用互补松弛定理求出原问题和对偶问题的最优解。 （2005）（四）灵敏度分析三（25%） 、派公司是一个生产高尔夫器材的小型公司，近期推出了高、中价位的高尔夫袋新产品（标准袋和高档袋） ，经销商对此产品十分感兴趣，并订购了派公司下 3 个月的全部产品。该高尔夫袋的生产过程主要包括 4 道工序：切割并印染原材料、缝合、成型（插入支撑架和球棒分离装置等） 、检验和包装。有关数据如表 1。派公司须决定标准袋和高档袋
14、各生产多少可使公司的总利润最大。表 1时间单耗 产品（小时）工序标准袋 高档袋 3 个月内最大生产能力（小时）切割印染 7/10 1 630缝合 1/2 5/6 600成型 1 2/3 708检验包装 1/10 1/4 135产品单位利润（美元） 10 9 (1) 写出此问题的线性规划模型，约束依表 1 中次序；(2) 引入松弛变量（依约束次序）后用单纯形法计算得某单纯形表如表 2，请填完表中空白，并判断其是否终表，如果是，请写出最优生产计划、最大利润和资源剩余；表 2CB XB B-1b10 9 0 0 0 0x1 x2 x3 x4 x5 x69 x2 2520 x4 12010 x1 54
15、00 x6 181 1.875 0 -1.3125 00 -0.9375 1 0.15625 00 -1.25 0 1.875 00 -0.34375 0 0.140625 1j -6.9375(3) 写出此问题的对偶问题的模型，及对偶的最优解与最优值；(4) 写出成型时间的影子价格，求使该影子价格不变的成型时间的变化范围；(5) 若标准袋的利润可能发生变化，则其在何范围内变化时，可使原最优计划不改变？图示说明其几何意义。 （2005）二（23%） 、某公司生产家用的清洁产品，为了在高度的市场竞争中增加市场份额，公司决定进行一次大规模的广告行动。表 1 给出了公司准备做广告的三种产品名称、估计
16、每做一单位广告（一个广告标准批量）使每种产品的市场份额增加量、公司拟定的广告后每种产品市场份额增加量的最低目标和两种可选的广告方式的单价。表 1单位增量 广告种类产品电视 印刷媒体 广告后市场份额最低增 量去污剂 0% 1% 3%液体洗涤剂 3% 2% 18%洗衣粉 -1% 4% 4%广告单位成本（万元） 100 200其中洗衣粉的市场份额出现负值是由于液体洗涤剂的份额增加会造成洗衣粉份额的减少。现公司需拟定使广告总费用最少的广告计划，即决定电视和印刷媒体的广告数量（分别记为 x1 和 x2） 。1. 请写出此问题的线性规划模型（约束依表 1 中产品的次序） ，并将模型化为标准型。2. 用（M
17、in 型）单纯形法求解此问题，得单纯形终表如表 2.表 2100 200 0 0 0 M M MCB XB B-1b x1 x2 x3 x4 x5 x6 x7 x80 x5 4 1/3 1 14/3 -1/3 -1100 x1 4 -1/3 0 -2/3 1/3 0200 x2 3 0 0 1 0 0 j 400/3 100/3 M-400/3 M-100/3 M（1）请填完表中空白；（2）由表指出最优广告计划并求出相应的最低广告费用，此最优计划使每种产品的市场份额最低增量目标达成情况如何？3. 写出此问题的对偶问题模型，由表 2 求出对偶最优解 Y*,并解释 Y*的实际意义。（2004）(3
18、)考虑线性规划问题Min z=-4x1+x2+30x3-11x4-2x5+3x6+10x7 -2x1+6x3+2x4-3x6+x7=20-4x1+x2+7x3+x4-x6=10-5x3+3x4+x5-x6=60Xj0(j=1,2,7) 用单纯型法求解,初表及终表如下: 初表-4 1 30 -11 -2 3 10CB XB B-1bX1 x2 x3 x4 x5 x6 x7-2 0 6 2 0 -3 1-4 1 7 1 0 -1 00 0 -5 3 1 -1 0检验数 终表-4 x1 5/445/23 x6 15/2-7/24 0 1/24 1/121/12 1 5/12 -1/61/4 0 1/
19、4 -1/2检验数 1.填完初表和终表中各空白,并说明所得最优解是否是唯一的,为什么?2.考虑当 b 变为 时,对最优解有什么影响?当 b 变为 时,对最优解是否有影18360 18460响?3.对偶问题最优解?（2003）二、 （17%）已知线性规划问题max z = (c1+t1) x1 + c2x2 + c3x3 + 0x4 + 0x5)5(0. 253221 1，j tbaatsj当 t1=t2=0 时，用单纯形法求得最终表如下：X1 X2 X3 X4 X5X3 5/2 0 1/2 1 1/2 0X4 5/2 1 1/2 0 1/6 1/3Cj-Zj 0 4 0 4 2要求：1.确定
20、c1,c2,c3,b1,b2,a11,a12,a13,a21,a22,a23的值；2当 t2=0 时，t 1在什么范围内变化上述最优解不变；3当 t1=0 时，t 2在什么范围内变化上述最优基不变。(2002)采（ 行 政 管 理 约 束 ）（ 劳 动 力 约 束 ）技 术 服 务 约 束划 模 型 ， 并产 量 的 线 性 规了 使 总 利 润 最 大 的 产 品据 公 司 实 际 情 况 ， 建 立管 理 ， 公 司 经 理 助 理 根 力 和 行 政种 资 源 ： 技 术 服 务 ， 动需 要种 产 品 ：分 ） 某 公 司 生 产二 、 （ 30625410)(.max 3,38321
21、 21xtsZx用单纯形法求得最优表格如下：10 6 4 0 0 0 QjC8 X8C8b X8 X1 X2 X3 X4 X5 X66 X2 400/6 0 1 5/6 10/6 -1/6 010 X1 200/6 1 0 1/6 -4/6 1/6 00 X5 100 0 0 4 -2 0 1-Z 4400/6 0 0 -8/3 -10/3 -2/3 0 qj在向总经理汇报时，总经理提出以下问题：1 公司 3 中资源的影子价格各是多少？2 若要现行解保持最优，则产品 X 1的单位利润不得低于何值？3 若产品 X3值得生产的话，它的单位利润应是多少？4 制造部门提出要生产一种新产品，该单位产品要
22、技术服务 1 小时，劳动力 4 小时，行政管理 3 小时。销售部门预测这种产品出售时可获 8 元的单位利润，管理部门是否考虑应将此新产品投产？现请帮助经理助理回答以上问题。 （2001）二（20）12112 s.t axb , 0Mzc有 一 线 性 规 划 为设 为引入的松弛变量。得到最优43,X单纯形表如上表，要求：（1）利用最优解求 c1,c2.（2）利用最优解求 b1,b2（3） 能变化多少而不至影响最优解；当 时求最优解；C12C（4）假定用 b+ 代替 b,其中 ,求出使最优基保持不变的 的范围.)(1（5）求出各资源的剩余量和影子价格。(1997) BX 12X34 解12 1
23、0 3 -1 0 1 -1 112J 0 0 -3 -1 -8（五）证明题三（15 分） 、考虑下面两个线性规划：00)()( XXbAbACzMinICzMinI 约 束 条 件约 束 条 件（2007）)()( * II的 最 优 解 ， 试 证 ：是的 最 优 解 ，是已 知三（11%） 、考虑线性规划问题（ P）max0zCAbX1若 X1,X2 均为（P）的可行解， ，证明 也是（P）的可行1,21)(X解；2写出（P）的对偶模型（仍用矩阵式表示） 。 （2006）2对偶模型 minTwbYAC无 限 制三（10%） 、证明线性规划中的互补松弛定理：设（ P）maxz=CX,X X|AX b,X 0,(D)minu=Yb,Y YA b,Y 0,若 分别是（P） （D ）的可行解， 分别是其相应,XY,sXY的松弛变量，则 是（P） ， （D）的最优解的充要条件是： ；并解释互,Y 0s补松弛定理的经济意义。 （2004）四、(21%) 试证明线性规划原问题中第 J 个约束扩大 K 倍,其对偶规划最优解中第 J 个变量将缩小 K 倍（2003）二、 （12%）有三个线性规划：0X bA)(约 束 条 件 CzMin0X bA)(约 束 条 件 CzMin() 0MinzCXAb约 束 条 件 已知： ， ， ） 的 最 优 解（是 ） 的 最 优 解（是 ）是 （ Y
