运筹学例题及答案

(一)线性规划建模与求解B.样题: 活力公司准备在 5小时内生产甲、乙两种产品。

甲、乙两种产品每生产1单位分别消耗2小时、1小时。

又根据市场需求信息，乙产品的产量应该至少是甲产品产量 的3倍。

已知甲、乙两种产品每销售1单位的利润分别为 3百元和1百元。

请问：在5小时内，甲、乙两种产品各生产多少单位，才能够使得总销售利润最大？要求：1、建立该问题的线性规划模型。

2、用图解法求出最优解和最大销售利润值， 并写出解的判断依据。

如果不存在最优解，也请说明理由。

解: 1、(1)设定决策变量：设甲、乙两种产品分别生产 X]、X 2单位 _____________max z=2 X 1+X 2 _________________________________12X 1 亠X 2 乞5 s.t X 2 _3X !X,X 2 _01所示，其中可行域用阴影部分 目标函数只须画出其中一条等值线，求解过程如下：1•各个约束条件的边界及其方向如图 1中直线和箭头所示，其中阴影部分为可 行域，由直线相交可得其顶点 A(5,0)、 B(1,3)和 0(0,0)。

2. 画出目标函数的一条等值线 CD :2x 什X 2=0，它沿法线向上平移，目标函数 值z 越来越大。

3. 当目标函数平移到线段 AB 时时，z ⑵目标函数：.(3)约束条件如下:2、该问题中约束条件、目标函数、可行域和顶点见图 标记，不等式约束条件及变量约束要标出成立的方向， 顶点用大写英文字母标记。

-2 -1X 2> 3 X 4 B(1,3)3图1X25；A(5,O)T Max z 。

1MaX 2结论：本题解的情形是：无穷多最优解，理由:目标函数等值线z=2 X1+X2与约束条件2 X]+x?w 5的边界平行。

甲、乙两种产品的最优产量分别为(5,0)或(1,3)单位；最大销售利润值等于_5_百元。

(二)图论问题的建模与求解样题A.正考样题(最短路问题的建模与求解，清华运筹学教材编写组第三版267-268页例13)某企业使用一台设备，每年年初，企业都要做出决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。

《运筹学》试题及参考答案一、填空题（每空2分，共10分）1、在线性规划问题中，称满足所有约束条件方程和非负限制的解为可行解。

2、在线性规划问题中，图解法适合用于处理变量为两个的线性规划问题。

3、求解不平衡的运输问题的基本思想是设立虚供地或虚需求点，化为供求平衡的标准形式。

4、在图论中，称无圈的连通图为树。

5、运输问题中求初始基本可行解的方法通常有最小费用法、西北角法两种方法。

二、（每小题5分，共10分）用图解法求解下列线性规划问题：1）max z =6x 1+4x 2⎪⎪⎩⎪⎪⎨⎧≥≤≤+≤+0781022122121x x x x x x x ，解：此题在“《运筹学》复习参考资料.doc ”中已有，不再重复。

2）min z =－3x 1+2x 2⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤-≤-≤+-≤+0,137210422422121212121x x x x x x x x x x 解：可行解域为abcda ，最优解为b 点。

⑴⑵⑶⑷⑸⑹、⑺由方程组⎩⎨⎧==+02242221x x x 解出x 1=11，x 2=0∴X *=⎪⎪⎭⎫⎝⎛21x x =（11，0）T∴min z =－3×11+2×0=－33三、（15分）某厂生产甲、乙两种产品，这两种产品均需要A 、B 、C 三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：AB C 甲94370乙46101203602003001）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分）2）用单纯形法求该问题的最优解。

（10分）解：1）建立线性规划数学模型：设甲、乙产品的生产数量应为x 1、x 2，则x 1、x 2≥0，设z 是产品售后的总利润，则max z =70x 1+120x 2s.t.⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤+0300103200643604921212121x x x x x x x x ，2）用单纯形法求最优解：加入松弛变量x 3，x 4，x 5，得到等效的标准模型：max z =70x 1+120x 2+0x 3+0x 4+0x 5s.t.⎪⎪⎩⎪⎪⎨⎧=≥=++=++=++5,...,2,1,03001032006436049521421321j x x x x x x x x x x j 列表计算如下：四、（10分）用大M 法或对偶单纯形法求解如下线性规划模型：min z =5x 1＋2x 2＋4x 3⎪⎩⎪⎨⎧≥≥++≥++0,,10536423321321321x x x x x x x x x 解：用大M 法，先化为等效的标准模型：max z /=－5x 1－2x 2－4x 3s.t.⎪⎩⎪⎨⎧=≥=-++=-++5,...,2,1,010********214321j y x x x x x x x x j增加人工变量x 6、x 7，得到：max z /=－5x 1－2x 2－4x 3－M x 6－M x 7s.t⎪⎩⎪⎨⎧=≥=+-++=+-++7,...,2,1,010*********2164321j x x x x x x x x x x x j大M 法单纯形表求解过程如下：五、（15分）给定下列运输问题：（表中数据为产地A i 到销地B j 的单位运费）B 1B 2B 3B 4s iA 1A 2A 312348765910119108015d j82212181）用最小费用法求初始运输方案，并写出相应的总运费；（5分）2）用1）得到的基本可行解，继续迭代求该问题的最优解。

运筹学典型题型案例集第一章线性规划1 生产计划问题（（摘自王治祯环境应用数学309页））某企业为了搞好综合利用，用三种废品生产三种副产品，生产情况和利润见下表，求最佳利润。

解：设ABC三种产品的产量为X1X2X3Max Z =5X1+8X2+2X310X1+5X2+3 X3<=4006X1+10X2+2 X3<=4004X1+5X2+4X3<=200经过求解X1=34.23，X2=8.19X3=5.37最大利润为274.412 投资问题解：用Xij表示第i年初（i=1，2，3）给项目j（A，B，C，D）的投资金额。

第一年资金量：30万，可投项目：A、B；故：X1A+X1B＜=30。

第二年资金量：1.2*X1A，可投项目：A、C；故：X2A+X2C＜=1.2*X1A。

第三年资金量：1.2*X2A+1.5*X1B，可投项目：A、B、D；故：X3A+X3B+X3D＜=1.2*X2A+1.5*X1B。

其它条件：X1B＜=20；X2C＜=15；X3D＜=10。

目标：第三年底收益最大。

因投资X3B在第3年底不能收回，故无收益。

则目标函数为：f(x)=0.2*（X1A+ X2A + X3A）+0.5*X1B+0.6* X2C+0.4* X3D LINGO Model如下：max =0.2*(X1A+ X2A + X3A)+0.5*X1B+0.6* X2C+0.4* X3D;X1A+X1B<=30;X2A+X2C<=1.2*X1A;X3A+X3B+X3D<=1.2*X2A+1.5*X1B;@bnd(0,X1B,20); @bnd(0,X3B,20); @bnd(0,X2C,15); @bnd(0,X3D,10);运行结果如下：Global optimal solution found.Objective value: 27.50000Total solver iterations: 2Variable Value Reduced CostX1A 12.50000 0.000000X2A 0.000000 0.6000000E-01X3A 16.25000 0.000000X1B 17.50000 0.000000X2C 15.00000 -0.1000000X3D 10.00000 -0.2000000X3B 0.000000 0.2000000Row Slack or Surplus Dual Price1 27.50000 1.0000002 0.000000 0.80000003 0.000000 0.50000004 0.000000 0.2000000投资计划解释：第一年年初投资A项目12.5万元，投资B项目17.5万元；第二年年初投资C项目15万元；第三年年初投资A项目16.25万元，投资D项目10万元；第三年年年末可获最大收益27.5万元。

第4章 目标规划4.6 公司决定使用1000万元新产品开发基金开发A ，B ，C 三种新产品。

经预测估计，开发A ，B ，C 三种新产品的投资利润分别为5％，7％，10％。

由于新产品开发有一定风险，公司研究后确定了下列优先顺序目标： 第一，A 产品至少投资300万元；第二，为分散投资风险，任何一种新产品的开发投资不超过开发基金总额的35％； 第三，应至少留有10％的开发基金，以备急用； 第四，使总的投资利润最大。

试建立投资分配方案的目标规划模型。

解：由最小元素法求得上述运输问题的初始基可行解，其过程如下：第5章 整数规划5.6 用割平面法解下列整数规划： （2）min 215x x z +=st. ⎪⎪⎩⎪⎪⎨⎧≥≥+≥+≥+且为整数,0,8859321212121x x x x x x x x解：将上述整数规划问题化为标准形式，用单纯形法解松弛问题，求得最优单纯形表的过程为：max 543210005x x x x x w +++--='st. ⎪⎪⎩⎪⎪⎨⎧≥=-+=-+=-+且为整数,0,8859321521421321x x x x x x x x x x x约束条件两端乘“－1”得max 543210005x x x x x w +++--='st. ⎪⎪⎩⎪⎪⎨⎧≥-=+---=+---=+--且为整数,0,8859321521421321x x x x x x x x x x x列出单纯行表，并用对偶单纯形法求解步骤进行计算，其过程如下：因-10≤-4，所以选x选x 4将最优解代入目标函数，得目标值：min 22 z得由最小元素法求得上述运输问题的初始基可行解，其过程如下：5.9 解下列0-1型整数规划：5.11 解下列0-1型整数规划： 5.13 5.14 5.16。

《运筹学》试卷、（15分）用图解法求解下列线性规划问题max z = 3T:+4x2—两十2兀2 —8Xj + 2X2 < 12 + x2 <1S“ >0,x2 >0二、（20 分）下表为某求极大值线性规划问题的初始单纯形表及迭代后的表, 6为松弛变量，试求表中二至显的值及各变量下标怕至匸的值。

三、（15分）用图解法求解矩阵对策[2 5 -1 3 _A =其中[4 13 -2J四、（20分）（1）某项工程由8个工序组成，各工序之间的关系为试画出该工程的网络图。

（2）试计算下面工程网络图中各事项发生的最早、最迟时间及关键线路（箭线下的数字是完成该工序的所需时间，单位：天）五、（15分）已知线性规划问题maK z = 10工i + 24工？十20xj + 20^4+ 25x:］工1十工2十2X B十十5x s<19討彳2曲+ 4冏+3Xj 4- 2X4+ Xj < 57（勺“ Q=U3A5）其对偶问题最优解为-7' - ■■- :'- - ■，试根据对偶理论求原问题的最优解六、（15分）用动态规划法求解下面问题:MAX Z = x{+ x 3 =c匕i 八1,2"七、（30分）已知线性规划问题MAX 2 ■ 2毛一冷+叱心十呵十心三b ^t.i^ J 2 -P 2X 3<47i #x 2r x 3 王D用单纯形法求得最优单纯形表如下， 试分析在下列各种条件单独变化的情况下，最优解将如何变化。

（1） 目标函数变为山…--'---； （2） 约束条件右端项由」一变为一」； （3） 增加一个新的约束： "'八、（20分）某地区有A 、B 、C 三个化肥厂向甲、乙、丙、丁四个销地供应同一 种化肥，已知产地产量、销地需求量和各产地运往不同销地单位运价如下表，试 用最小元素法确定初始调运方案，并调整求最优运输方案《运筹学》试卷二、（20分）已知线性规划问题：min z - 2Z] +3龙立+2也兀]+ 2X2+3X3+ > 2sU - 2x x 4-J3一巧十？咒° 三-3gO（j 二12第）（a）写出其对偶问题；（b）用图解法求对偶问题的解；（c）利用（b）的结果及对偶性质求原问题的解。

《运筹学》第四章习题及答案一、思考题1．运输问题的数学模型具有什么特征？为什么其约束方程的系数矩阵的秩最多等于m，n,1？2．用左上角法确定运输问题的初始基本可行解的基本步骤是什么？ 3．最小元素法的基本思想是什么？为什么在一般情况下不可能用它直接得到运输问题的最优方案？4．沃格尔法（Vogel 法）的基本思想是什么？它和最小元素法相比给出的运输问题的初始基本可行解哪一个更接近于最优解？为什么？5．试述用闭回路法检验给定的调运方案是否最优的原理，其检验数的经济意义是什么？6．用闭回路法检验给定的调运方案时，如何从任意空格出发去寻找一条闭回路？这闭回路是否是唯一的？7．试述用位势法求检验数的原理、步骤和方法。

8．试给出运输问题的对偶问题（对产销平衡问题）。

9．如何把一个产销不平衡的运输问题（产大于销或销大于产）转化为产销平衡的运输问题。

10．一般线性规划问题应具备什么特征才可以转化为运输问题的数学模型？11．试述在表上作业法中出现退化解的涵义及处理退化解的方法。

二、判断下列说法是否正确1．运输问题模型是一种特殊的线性规划模型，所以运输问题也可以用单纯形方法求解。

2．因为运输问题是一种特殊的线性规划模型，因而求其解也可能出现下列四种情况：有唯一最优解；有无穷多个最优解；无界解；无可行解。

3．在运输问题中，只要给出一组（,,xijm，n,1）个非零的，且满足nmx,aijix,b,,ijjj,1 i,1，，就可以作为一个基本可行解。

4．表上作业法实质上就是求解运输问题的单纯形法。

5．按最小元素法或元素差额法给出的初始基本可行解，从每一空格出发都可以找到一闭回路，且此闭回路是唯一的。

6．如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k ，最优调运方案将不会发生变化。

7．如果运输问题单位运价表的某一行（或某一列）元素分别乘上一个常数k ，最优调运方案将不会发生变化。

8．用位势法计算检验数时，先从某一行（或列）开始，给出第一个位势的值，这个先给出的位势值必须是正的。

运筹练习题及答案运筹学是应用数学的一个分支，它主要研究如何在有限资源下，通过合理规划和决策来达到最优效果。

以下是一些运筹练习题及答案，供学习者练习和参考。

练习题1：线性规划问题某工厂生产A和B两种产品，每种产品都需要使用机器和劳动力。

生产1单位A产品需要1小时机器时间和2小时劳动力，生产1单位B产品需要2小时机器时间和1小时劳动力。

工厂每天有10小时机器时间和15小时劳动力。

如果A产品的利润是3元，B产品的利润是5元，问如何安排生产计划以使总利润最大化？答案：设生产A产品的数量为x，B产品的数量为y。

目标函数：最大化利润 Z = 3x + 5y约束条件：1. 机器时间：x + 2y ≤ 102. 劳动力时间：2x + y ≤ 153. 非负性：x ≥ 0, y ≥ 0通过图解法或单纯形法，我们可以得到最优解为x = 4, y = 3，此时最大利润为34元。

练习题2：整数规划问题一家公司需要安排10名员工在5个不同的部门工作。

每个部门至少需要1名员工，且每个员工只能在一个部门工作。

部门A需要至少3名员工，部门B需要至少2名员工，部门C需要1名员工，部门D和E 各需要至少1名员工。

问如何分配员工以满足所有部门的需求？答案：设部门A、B、C、D、E分别分配的员工数为x1, x2, x3, x4, x5。

目标函数：满足所有部门需求，无直接利润最大化。

约束条件：1. x1 + x2 + x3 + x4 + x5 = 102. x1 ≥ 33. x2 ≥ 24. x3 = 15. x4 = 16. x5 = 1通过枚举法或整数规划算法，我们可以得到一种分配方案为：部门A 分配3人，B分配2人，C、D、E各分配1人。

练习题3：网络流问题某公司有3个仓库和4个销售点，每个销售点每天对产品的需求量已知。

公司需要决定如何从仓库向销售点分配产品，以满足所有销售点的需求，同时使总运输成本最小。

答案：设仓库i向销售点j的运输量为x_ij，运输成本为c_ij。

1、课上讲过的练习和要求课下做过的练习1〕答案更正答案：更正答案：2〕答案：题：答案：更改〔4〕答案题：答案：更改〔5〕答案2、最后给的练习1〕紧前工作A — 3B A 3C A 4D A 6E B、C、D 6 答案：2〕紧前工作A — 4B — 3C A 8D A 7E B、C 9F B、C 12G D、E 2H D、E 5I G、F 6答案：3〕紧前工作A —7B — 5C A、B 10D C 7E C 3F D 2G D、E 5答案：二、决策分析1、最后给的练习1〕有一个公司方案买两种复印机，选好两种型号的复印机可以满足未来10年的需求，但第一种复印机购置价格2000元，每年耗材使用到达150元可以免费维修；第二种复印机购置价格3000元，维修费用不确定，估计40%的可能不用修理，40%的可能维修费100元，20%的可能性维修费200元。

问该公司应该选择哪种复印机？2〕一家大型轧钢厂考虑向一家新客户〔服装厂〕贷款，轧钢厂将客户还款情况分三类：严重拖欠、一般拖欠、按时还款；估计20%可能严重拖欠，50%可能一般拖欠，30%可能按时还款，如果制衣厂得到贷款后又严重拖欠，那么轧钢厂将损失25万，服装厂一般拖欠，轧钢厂获利10万，按时还款轧钢厂获利20万。

借款期1年，1年的存款基准利率为3.22%。

问轧钢厂是否给制衣厂贷款？结论是给企业贷款或再问：如果将获利合为一个，严重拖欠损失25万，而其他情况获利是14万，问A、无差概率B、EVPI三、线性规划线性规划的步骤：1〕确定决策变量；2〕列出约束条件；3〕写出目标函数。

图解线性规划：1〕决定线性规划问题的可行域；2〕求解线性和整数规划1、课堂练习1〕答案：极大化Z = 40 x1 + 50 x2约束x1 + 2x2 ≤40 小时(劳力限制) 4x1 + 3x2 ≤120 磅(粘土限制)x1 , x2 ≥0解x1 = 24个碗x2 = 8个杯收入= 1,360美元2〕答案：(包括量度单位(打数)和时间单位(周))X1 = 每周生产宇宙光的打数X2 = 每周生产射击手的打数MAX 8X1 + 5X2s.t.2X1 + 1X2 ≤1000 (塑料)3X1 + 4X2 ≤2400 (加工时间)X1 + X2 ≤700 (总产量)X1 –X2 ≤350 (混合限制)所有X ≥03〕某家工厂面临的生产问题是：♦生产4种男人领带♦使用3种材料(有限资源)决策:每月每种领带各生产多少?目标:极大化利润生产数据4〕邮局一周在不同天要求全日工作人数不同，如表1所列。

四、把以下线性计划问题化成标准形式：二、minZ=2x1-x2+2x3五、按各题要求。

成立线性计划数学模型一、某工厂生产A、B、C三种产品，每种产品的原材料消耗量、机械台时消耗量和这些资源的限量，单位产品的利润如下表所示：依照客户定货，三种产品的最低月需要量别离为200，250和100件，最大月销售量别离为250，280和120件。

月销售别离为250，280和120件。

问如何安排生产打算，使总利润最大。

2、某建筑工地有一批长度为10米的相同型号的钢筋，今要截成长度为3米的钢筋90根，长度为4米的钢筋60根，问如何下料，才能使所利用的原材料最省?1．某运输公司在春运期间需要24小时日夜加班工作，需要的人员数量如下表所示：起运时间服务员数2—66—1010一1414—1818—2222—248107124每一个工作人员持续工作八小时，且在时段开始时上班，问如何安排，使得既知足以上要求，又使上班人数最少?五、别离用图解法和单纯形法求解以下线性计划问题．并对照指出单纯形迭代的每一步相当于图解法可行域中的哪个极点。

六、用单纯形法求解以下线性计划问题：七、用大M法求解以下线性计划问题。

并指出问题的解属于哪一类。

八、下表为用单纯形法计算时某一步的表格。

已知该线性计划的目标函数为maxZ=5x1+3x2，约束形式为“≤”，X3，X4为松驰变量．表中解代入目标函数后得Z=10X l X2X3X4—10 b -1 f gX3 2 C O 1 1／5X l a d e 0 1(1)求表中a～g的值 (2)表中给出的解是不是为最优解?（1）a=2 b=0 c=0 d=1 e=4/5 f=0 g=－5 （2）表中给出的解为最优解第四章线性计划的对偶理论五、写出以下线性计划问题的对偶问题1．minZ=2x1+2x2+4x3六、已知线性计划问题应用对偶理论证明该问题最优解的目标函数值不大于25七、已知线性计划问题maxZ=2x1+x2+5x3+6x4其对偶问题的最优解为Y l﹡=4，Y2﹡=1，试应用对偶问题的性质求原问题的最优解。

运筹学例题解析(共6页) -本页仅作为预览文档封面，使用时请删除本页-(一)线性规划建模与求解B.样题：活力公司准备在5小时内生产甲、乙两种产品。

甲、乙两种产品每生产1单位分别消耗2小时、1小时。

又根据市场需求信息，乙产品的产量应该至少是甲产品产量的3倍。

已知甲、乙两种产品每销售1单位的利润分别为3百元和1百元。

请问：在5小时内，甲、乙两种产品各生产多少单位，才能够使得总销售利润最大要求：1、建立该问题的线性规划模型。

2、用图解法求出最优解和最大销售利润值，并写出解的判断依据。

如果不存在最优解，也请说明理由。

解：1、(1)设定决策变量： 设甲、乙两种产品分别生产x 1、x2单位 。

(2)目标函数： max z=2 x 1+x 2(3)约束条件如下：12211225..3,0+≤⎧⎪≥⎨⎪≥⎩x x s t x x x x2、该问题中约束条件、目标函数、可行域和顶点见图1所示，其中可行域用阴影部分标记，不等式约束条件及变量约束要标出成立的方向，目标函数只结论：本题解的情形是： 无穷多最优解 ，理由： 目标函数等值线z=2 x 1+x 2与约束条件2 x 1+x 2≤5的边界平行 。

甲、乙两种产品的最优产量分别为 (5,0)或(1,3)单位；最大销售利润值等于 5 百元。

（二）图论问题的建模与求解样题A.正考样题（最短路问题的建模与求解，清华运筹学教材编写组第三版267-268页例13）某企业使用一台设备，每年年初，企业都要做出决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。

但是变卖旧设备可以获得残值收入，连续使用1年、2年、3年、4年以上卖掉的设备残值分别为8万元、6万元、3万元和0万元。

试制定一个5年的更新计划，使总支出最少。

已知设备在各年的购买费与维修费如表2所示。

要求：（1）建立某种图论模型；（2）求出最少总支出金额。

解：（1）建立图论——最短路问题模型。

①设点Vi 表示第i年年初，虚设一个点V6，表示第五年年底；②弧(Vi , Vj)表示第i年初购进一台设备一直使用到第j年初(即第i-1年年底)再卖掉并获得残值收入；③弧(Vi , Vj)上的权数表示第i年初购进一台设备，一直使用到第j年初所需支付的购买、维修及抵扣残值收入以后的全部费用（单位：万元）。

运筹学试习题及答案运筹学试习题及答案《运筹学》复习试题及答案(一)一、填空题1、线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。

2、图解法适用于含有两个变量的线性规划问题。

3、线性规划问题的可行解是指满足所有约束条件的解。

4、在线性规划问题的基本解中，所有的非基变量等于零。

5、在线性规划问题中，基可行解的非零分量所对应的列向量线性无关6、若线性规划问题有最优解，则最优解一定可以在可行域的顶点(极点)达到。

7、线性规划问题有可行解，则必有基可行解。

8、如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其基可行解_的集合中进行搜索即可得到最优解。

9、满足非负条件的基本解称为基本可行解。

10、在将线性规划问题的一般形式转化为标准形式时，引入的松驰数量在目标函数中的系数为零。

11、将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左_端加入松弛变量。

12、线性规划模型包括决策(可控)变量，约束条件，目标函数三个要素。

13、线性规划问题可分为目标函数求极大值和极小_值两类。

14、线性规划问题的标准形式中，约束条件取等式，目标函数求极大值，而所有变量必须非负。

15、线性规划问题的基可行解与可行域顶点的关系是顶点多于基可行解16、在用图解法求解线性规划问题时，如果取得极值的等值线与可行域的一段边界重合，则这段边界上的一切点都是最优解。

17、求解线性规划问题可能的结果有无解，有唯一最优解，有无穷多个最优解。

18、19、如果某个变量Xj为自由变量，则应引进两个非负变量Xj , Xj,同时令Xj=Xj- Xj。

20、表达线性规划的简式中目标函数为ijij21、、(2、1 P5))线性规划一般表达式中，aij表示该元素位置在二、单选题1、如果一个线性规划问题有n个变量，m个约束方程(m行解的个数最为_C_。

′〞′A、m个B、n个C、CnD、Cm个2、下列图形中阴影部分构成的集合是凸集的是A mn3、线性规划模型不包括下列_ D要素。

以下是使用沃格尔法解决运筹学问题的例题：
例题：某部门有3个生产同类的工厂（产地），生产的产品由4个销售点（销地）出售，各工厂的生产量、各销售点的销售量（假定单位均为t）以及各工厂到各销售点的单位运价（元/t）示于下表中。

要求研究产品如何调运才能使总运费最小。

解法：
1.首先，我们使用沃格尔法来求解最小运费问题。

沃格尔法是一种基于线性
规划的算法，通过迭代和调整变量的值来找到最小运费。

2.我们将使用以下变量：xij表示从第i个产地到第j个销地的运量（t）。

3.根据题目，我们可以建立以下数学模型：
Minimize: z = 5x11 + 9x12 + 10x13 + 8x14 + 9x21 + 7x22 + 10x23 + 6x31 + 7x32 + 6x34
Subject to:
x11 + x12 + x13 + x14 = 7 (A1的生产量)
x21 + x22 + x23 = 1 (A2的生产量)
x31 + x32 + x34 = 3 (A3的生产量)
x11 + x21 + x31 = 3 (A1的销售量)
x12 + x22 + x32 = 8 (A2的销售量)
x13 + x23 = 5 (A3的销售量)
x14 = 6 (A4的销售量)
xij >= 0, i=1,2,3; j=1,2,3,4
4.使用沃格尔法进行迭代，找到最优解。

在每一次迭代中，我们根据当前的
解计算出新的运输方案，并更新运输量。

迭代过程一直持续到运输方案不
再发生变化为止。

5.最后，我们得到最优解，即最小的总运费。

一、填空题：（每空格2分，共16分）1、线性规划的解有唯一最优解、无穷多最优解、 无界解 和无可行解四种。

2、在求运费最少的调度运输问题中，如果某一非基变量的检验数为4，则说明 如果在该空格中增加一个运量运费将增加4 。

3、“如果线性规划的原问题存在可行解，则其对偶问题一定存在可行解”，这句话对还是错？ 错4、如果某一整数规划： MaxZ=X 1+X 2 X 1+9/14X 2≤51/14 -2X 1+X 2≤1/3 X 1,X 2≥0且均为整数所对应的线性规划（松弛问题）的最优解为X 1=3/2，X 2=10/3，MaxZ=6/29，我们现在要对X 1进行分枝，应该分为 X 1≤1 和 X 1≥2 。

5、在用逆向解法求动态规划时，f k (s k )的含义是： 从第k 个阶段到第n 个阶段的最优解 。

6. 假设某线性规划的可行解的集合为D ，而其所对应的整数规划的可行解集合为B ，那么D和B 的关系为 D 包含 B7. 已知下表是制订生产计划问题的一张LP 最优单纯形表（极大化问题，约束条问：（1）写出B -1=⎪⎪⎪⎭⎫ ⎝⎛---1003/20.3/1312(2)对偶问题的最优解： Y ＝（5，0，23，0，0）T8. 线性规划问题如果有无穷多最优解，则单纯形计算表的终表中必然有___某一个非基变量的检验数为0______；9. 极大化的线性规划问题为无界解时，则对偶问题_无解_________；10. 若整数规划的松驰问题的最优解不符合整数要求，假设X i =b i 不符合整数要求，INT （b i ）是不超过b i 的最大整数，则构造两个约束条件：Xi ≥INT （b i ）＋1 和 Xi ≤INT （b i ） ，分别将其并入上述松驰问题中，形成两个分支，即两个后继问题。

11. 知下表是制订生产计划问题的一张LP 最优单纯形表（极大化问题，约束条问：(1)对偶问题的最优解： Y ＝(4,0,9,0,0,0)T （2）写出B -1=⎪⎪⎪⎭⎫ ⎝⎛611401102二、计算题（60分）1、已知线性规划（20分） MaxZ=3X1+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的，所以最优解不变。