《运筹学》课堂作业及相应答案解析
- 格式:doc
- 大小:2.85 MB
- 文档页数:35
第二章 线性规划73P 4. 将下面的线性规划问题化成标准形式12312312312max 2..236230316x x x s t x x x x x x x x −+⎧⎪−+≥⎪⎪+−≤⎨⎪≤≤⎪⎪−≤≤⎩解:将max 化为 min , 3x 用45x x −代替,则1245124512451245min 2()..23()62()30316,0x x x x s t x x x x x x x x x x x x −+−−⎧⎪−+−≥⎪⎪+−−≤⎪⎨≤≤⎪⎪−≤≤⎪≥⎪⎩令221x x ′=+,则1245124512451245min12()..2(1)3()62(1)()30307,0x x x x s t x x x x x x x x x x x x ′−+−−−⎧⎪′−−+−≥⎪⎪′+−−−≤⎪⎨≤≤⎪⎪′≤≤⎪≥⎪⎩将线性不等式化成线性等式,则可得原问题的标准形式12451245612457182912456789min221..23342437,,,,,,,0x x x x s t x x x x x x x x x x x x x x x x x x x x x x ′−+−+−⎧⎪′−+−−=⎪⎪′+−++=⎪⎨+=⎪⎪′+=⎪′≥⎪⎩73P 5、用图解法求解下列线性规划问题:(1) 121212min 3..206122x x s t x x x x +⎧⎪+≥⎪⎨≤≤⎪⎪≥⎩解:图2.1的阴影部分为此问题的可行区域.将目标函数的等值线123x x c +=(c 为常数)沿它的负法线方向()13T−−,移动到可行区域的边界上.于是交点T),(812就是该问题的最优解,其最优值为36.75P 16. 用单纯形法求解下列线性规划问题:(1) 123123123123min 2..360210200,1,2,3j z x x x s t x x x x x x x x x x j ⎧=−−+⎪++≤⎪⎪−+≤⎨⎪+−≤⎪⎪≥=⎩解:将此问题化成标准形式123123412351236min 2..360210200,1,2,3,4,5,6j z x x x s t x x x x x x x x x x x x x j ⎧=−−+⎪+++=⎪⎪−++=⎨⎪+−+=⎪⎪≥=⎩以456,,x x x 为基变量,可得第一张单纯形表为以1x 为进基变量,5x 为离基变量旋转得以2x 为进基变量,6x 为离基变量旋转得1x 2x 3x 4x 5x 6x RHS z2 1 -1 0 000 4x 31 1 1 0060 5x 1-121010 6x 11 -1 0 01201x 2x 3x 4x 5x 6x RHS z0 3 -5 0 -20-204x 0 4 -5 1 -3030 1x 1-1 2 0 1010 6x 02-3-11101 注意单纯形表的格式!2 要用记号把转轴元标出来 3要记住在单纯形表的左边,用进基变量代替离基变量注(零行元素的获得):先将目标函数化成求最小值的形式,再把所有变量移到等式左边,常数移到等式右边。
《运筹学》习题答案一、单选题1.用动态规划求解工程线路问题时,什么样的网络问题可以转化为定步数问题求解()BA.任意网络B.无回路有向网络C.混合网络D.容量网络2.通过什么方法或者技巧可以把工程线路问题转化为动态规划问题?()BA.非线性问题的线性化技巧B.静态问题的动态处理C.引入虚拟产地或者销地D.引入人工变量3.静态问题的动态处理最常用的方法是?BA.非线性问题的线性化技巧B.人为的引入时段C.引入虚拟产地或者销地D.网络建模4.串联系统可靠性问题动态规划模型的特点是()DA.状态变量的选取B.决策变量的选取C.有虚拟产地或者销地D.目标函数取乘积形式5.在网络计划技术中,进行时间与成本优化时,一般地说,随着施工周期的缩短,直接费用是( )。
CA.降低的B.不增不减的C.增加的D.难以估计的6.最小枝权树算法是从已接接点出发,把( )的接点连接上CA.最远B.较远C.最近D.较近7.在箭线式网络固中,( )的说法是错误的。
DA.结点不占用时间也不消耗资源B.结点表示前接活动的完成和后续活动的开始C.箭线代表活动D.结点的最早出现时间和最迟出现时间是同一个时间8.如图所示,在锅炉房与各车间之间铺设暖气管最小的管道总长度是( )。
CA.1200B.1400C.1300D.17009.在求最短路线问题中,已知起点到A,B,C三相邻结点的距离分别为15km,20km,25km,则()。
DA.最短路线—定通过A点B.最短路线一定通过B点C.最短路线一定通过C点D.不能判断最短路线通过哪一点10.在一棵树中,如果在某两点间加上条边,则图一定( )AA.存在一个圈B.存在两个圈C.存在三个圈D.不含圈11.网络图关键线路的长度( )工程完工期。
CA.大于B.小于C.等于D.不一定等于12.在计算最大流量时,我们选中的每一条路线( )。
CA.一定是一条最短的路线B.一定不是一条最短的路线C.是使某一条支线流量饱和的路线D.是任一条支路流量都不饱和的路线13.从甲市到乙市之间有—公路网络,为了尽快从甲市驱车赶到乙市,应借用()CA.树的逐步生成法B.求最小技校树法C.求最短路线法D.求最大流量法14.为了在各住宅之间安装一个供水管道.若要求用材料最省,则应使用( )。
第十四次作业解答:P219 习题6_3):(1),(3),(5);3、建立下列问题的排队模型,画出系统的状态转移图并按要求求解。
(1)某理发店只有一名理发师,来理发的顾客按泊松分布到达,平均每小时4人,理发时间服从负指数分布,平均需6分钟。
①判断排队系统模型,画出系统的状态转移速度图;②理发店空闲的概率、店内有三个顾客的概率、店内至少有一个顾客的概率; ③在店内顾客平均数、在店内平均逗留时间; ④等待服务的顾客平均数、平均等待服务时间。
解: ① 依题意, 该问题是一个M/M/1等待制排队系统,系统容量和顾客源无限。
顾客到达按泊松流输入,==4人/小时,理发时间服从负指数分布,=10人/小时。
② 理发店空闲的概率:04110.610p λμ=-=-=。
店内有三个顾客的概率:3344()(1)0.03841010p =⨯-=。
店内至少有一个顾客的概率:010.4p -=。
③店内顾客平均数:40.66667104s L λμλ===--。
在店内的平均逗留时间:110.16667104ss eL W λμλ====--。
④等待服务的顾客平均数:2440.26667()10(104)e q s L L λλμμμλ⨯=-===-⨯-。
平均等待服务时间:0.06667()qq eL W λλμμλ===-。
(3)某加油站有一台油泵。
来加油的汽车按泊松流到达,平均每小时二十辆,但当加油站已有n 辆汽车时,新来汽车中将有一部分不愿意等待而离去,离去概率为n /4(n=0,1,2,3,4)。
油泵给一辆汽车加油所需要的时间为均值3分钟的负指数分布。
①画出排队系统的状态转移速度图; ②导出其平衡方程式;③求出系统的运行参数,,,,s q e s q L L W W λ。
解:根据题意,顾客按泊松流到达,λ=20辆/小时,服务时间服从负指数分布, μ=20辆/小时。
一个服务台1C =,系统容量为N=4,离去的概率为n /4。
运筹学第三版课后习题答案第一章:引论1.1 课后习题习题1a)运筹学是一门应用数学的学科,旨在解决实际问题中的决策和优化问题。
它包括数学模型的建立、问题求解方法的设计等方面。
b)运筹学可以应用于各个领域,如物流管理、生产计划、流程优化等。
它可以帮助组织提高效率、降低成本、优化资源分配等。
c)运筹学主要包括线性规划、整数规划、指派问题等方法。
习题2运筹学的应用可以帮助组织提高效率、降低成本、优化资源分配等。
它可以帮助制定最佳的生产计划,优化供应链管理,提高运输效率等。
运筹学方法的应用还可以帮助解决紧急情况下的应急调度问题,优化医疗资源分配等。
1.2 课后习题习题1运筹学方法可以应用于各个领域,如物流管理、生产计划、供应链管理、流程优化等。
在物流管理中,可以使用运筹学方法优化仓储和运输的布局,提高货物的运输效率。
在生产计划中,可以使用运筹学方法优化产品的生产数量和生产周期,降低生产成本。
在供应链管理中,可以使用运筹学方法优化订单配送和库存管理,提高供应链的效率。
在流程优化中,可以使用运筹学方法优化业务流程,提高整体效率。
习题2在物流管理中,可以使用运筹学方法优化车辆的调度和路线规划,以提高运输效率和降低成本。
在生产计划中,可以使用运筹学方法优化生产线的安排和产品的生产量,以降低生产成本和提高产能利用率。
在供应链管理中,可以使用运筹学方法优化供应链各个环节的协调和调度,以提高整体效率和减少库存成本。
在流程优化中,可以使用运筹学方法优化业务流程的排布和资源的分配,以提高流程效率和客户满意度。
第二章:线性规划基础2.1 课后习题习题1线性规划是一种数学优化方法,用于解决包含线性约束和线性目标函数的优化问题。
其一般形式为:max c^T*xs.t. Ax <= bx >= 0其中,c是目标函数的系数向量,x是决策变量向量,A是约束矩阵,b是约束向量。
习题2使用线性规划方法可以解决许多实际问题,如生产计划、供应链管理、资源分配等。
运筹学基础(中文版第10版)哈姆迪塔哈课后习题答案解析第一章线性规划模型1.1 线性规划的基本概念1.请解释线性规划模型的基本要素以及线性规划模型的一般形式。
答:- 线性规划模型的基本要素包括决策变量、目标函数、约束条件。
- 线性规划模型的一般形式如下:Max/Min Z = c₁x₁ + c₂x₂ + ... + cₙxₙSubject to:a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂...aₙ₁x₁ + aₙ₂x₂ + ... + aₙₙxₙ ≤ bₙx₁, x₂, ..., xₙ ≥ 01.2 线性规划模型的几何解释1.请说明线性规划模型的几何解释。
答:线性规划模型在几何上可以表示为一个多维空间中的凸多面体(可行域),目标函数为该多面体上的一条直线,通过不同的目标函数系数向量c,可以得到相应的最优解点。
通过多面体的边界和顶点,可以确定最优解点的位置。
如果可行域是无限大的,则最优解点可以在其中的任何位置。
1.3 线性规划模型求解方法1.简要说明线性规划模型的两种求解方法。
答:线性规划模型可以通过以下两种方法进行求解: - 图形法:根据可行域的几何特征,通过图形方法确定最优解点的位置。
- 单纯形法:通过迭代计算,逐步靠近最优解点。
单纯形法是一种高效的求解线性规划问题的方法。
第二章单变量线性规划2.1 单变量线性规划模型1.请给出单变量线性规划模型的一般形式。
答:Max/Min Z = cxSubject to:ax ≤ bx ≥ 02.2 图形解法及其应用1.请解释图形解法在单变量线性规划中的应用。
答:图形解法可以直观地帮助我们确定单变量线性规划模型的最优解。
通过绘制目标函数和约束条件的图像,可以确定最优解点的位置。
对于单变量线性规划模型,图形解法特别简单,只需要绘制一条直线和一条水平线,求解它们的交点即可得到最优解点的位置。
《运筹学》习题与答案(解答仅供参考)一、名词解释1. 线性规划:线性规划是运筹学的一个重要分支,它主要研究在一系列线性约束条件下,如何使某个线性目标函数达到最大值或最小值的问题。
2. 动态规划:动态规划是一种解决多阶段决策问题的优化方法,通过把原问题分解为相互联系的子问题来求解,对每一个子问题只解一次,并将其结果保存起来以备后续使用,避免了重复计算。
3. 整数规划:整数规划是在线性规划的基础上,要求决策变量取值为整数的一种优化模型,用于解决实际问题中决策变量只能取整数值的情形。
4. 马尔可夫决策过程:马尔可夫决策过程是一种随机环境下的决策模型,其中系统的状态转移具有无后效性(即下一状态的概率分布仅与当前状态有关),通过对每个状态采取不同的策略(行动)以最大化期望收益。
5. 最小费用流问题:最小费用流问题是指在网络流模型中,每条边都有一个容量限制和单位流量的成本,寻找满足所有节点流量平衡的同时使得总成本最小的流方案。
二、填空题1. 运筹学的主要研究对象是系统最优化问题,其核心在于寻求在各种(约束条件)下实现(目标函数)最优的方法。
2. 在运输问题中,供需平衡指的是每个(供应地)的供应量之和等于每个(需求地)的需求量之和。
3. 博弈论中的纳什均衡是指在一个博弈过程中,对于各个参与者来说,当其他所有人都不改变策略时,没有人有动机改变自己的策略,此时的策略组合构成了一个(纳什均衡)。
4. 在网络计划技术中,关键路径是指从开始节点到结束节点的所有路径中,具有最长(总工期)的路径。
5. 对于一个非负矩阵A,如果存在一个非负矩阵B,使得AB=BA=A,则称A为(幂等矩阵)。
三、单项选择题1. 下列哪项不是线性规划的标准形式所具备的特点?(D)A. 目标函数是线性的B. 约束条件是线性的C. 决策变量非负D. 变量系数可以为复数2. 当线性规划问题的一个基解满足所有非基变量的检验数都非正时,那么该基解(C)。
A. 不是可行解B. 是唯一最优解C. 是局部最优解D. 不一定是可行解3. 下列哪种情况适合用动态规划法求解?(B)A. 问题无重叠子问题B. 问题具有最优子结构C. 问题不能分解为多个独立子问题D. 子问题之间不存在关联性4. 在运输问题中,如果某条路线的运输量已经达到了其最大运输能力,我们称这条路线处于(A)状态。
《运筹学》作业答案作业一一、是非题:1.图解法与单纯形法虽然求解的形式不同,但从几何上理解,两者是一致的。
(√)2.线性规划问题的每一个基解对应可行解域的一个顶点。
(╳)3.如果线性规划问题存在最优解,则最优解一定可以在可行解域的顶点上获得。
(√)4.用单纯形法求解Max型的线性规划问题时,检验数Rj>0对应的变量都可以被选作入基变量。
(√)5.单纯形法计算中,如果不按最小比值规划选出基变量,则在下一个解中至少有一个基变量的值为负。
(√)6.线性规划问题的可行解如为最优解,则该可行解一定是基可行解。
(╳)7.若线性规划问题具有可行解,且可行解域有界,则该线性规划问题最多具有有限个数的最优解。
(╳)8.对一个有n个变量,m个约束的标准型线性规划问题,其可行域的顶点数恰好为mnC个。
(╳)9.一旦一个人工变量在迭代中变为非基变量后,该变量及相应列的数字可以从单纯形表中删除,而不影响计算结果。
(√)10.求Max型的单纯形法的迭代过程是从一个可行解转换到目标函数值更大的另一个可行解。
(√)二、线性规划建模题:1.某公司一营业部每天需从A、B两仓库提货用于销售,需提取的商品有:甲商品不少于240件,乙商品不少于80台,丙商品不少于120吨。
已知:从A仓库每部汽车每天能运回营业部甲商品4件,乙商品2台,丙商品6吨,运费200元/每部;从B仓库每部汽车每天能运回营业部甲商品7件,乙商品2台,丙商品2吨,运费160元/每部。
问:为满足销售量需要,营业部每天应发往A、B两仓库各多少部汽车,并使总运费最少解:设营业部每天应发往A、B两仓库各x1,x2部汽车,则有:12 121212min200160 47240 2280 621200(1,2)jW x xx xx xx xx j=++≥⎧⎪+≥⎪⎨+≥⎪⎪≥=⎩2.现有一家公司准备制定一个广告宣传计划来宣传开发的新产品,以使尽可能多的未来顾客特别是该企业计划用于此项广告宣传的经费预算是80万元,此外要求:①至少有200万人次妇女接触广告宣传;②电视广告费用不得超过50万元, ③电视广告至少占用三个单元一般时间和两个单元黄金时间, ④广播和报纸广告单元均不少于5个单元而不超过10个单元。
47页1.1b羅蕿用图解法找不到满足所有约束条件的公共范围,所以该问题无可行解薅47页1。
1d蒂无界解(b)衿1.2蕿约束方程的系数矩阵A=1234莇2112蚄P1P2P3P4,运筹作业肀最优解A=(01/220)T和(0011)T页13题肆49膃设Xij为第i月租j个月的面积羄minz=2800x11+2800x21+2800x31+2800x41+4500x12+4500x22+4500x32+6000x13+6000x23+7300x 14螁s.t.聿x11+x12+x13+x14≥15膃x12+x13+x14+x21+x22+x23≥10膀x13+x14+x22+x23+x31+x32≥20艿x14+x23+x32+x41≥12袇Xij≥0芃用excel求解为:薁用LINDO求解:羁LPOPTIMUMFOUNDATSTEP3薆OBJECTIVEFUNCTIONVALUE 蚇1)118400.0羂VARIABLEVALUEREDUCEDCOST 荿Z0.0000001。
000000虿X113.0000000。
000000螇X210。
0000002800。
000000莃X318。
0000000.000000肁X410.0000001100。
000000莈X120.0000001700.000000袆X220.0000001700。
000000螄X320.0000000。
000000蕿X130.000000400.000000膇X230。
0000001500。
000000袆X1412.0000000.000000袁ROWSLACKORSURPLUSDUALPRICES芁2)0。
000000—2800。
000000羆3)2.0000000.000000羆4)0。
000000—2800.000000节5)0。
000000-1700.000000蝿NO。
ITERATIONS=3罿答若使所费租借费用最小,需第一个月租一个月租期300平方米,租四个月租期1200平方米,第三个月租一个月租期800平方米,页14题肆50蚃设a1,a2,a3,a4,a5分别为在A1,A2,B1,B2,B3加工的Ⅰ产品数量,b1,b2,b3分别为在A1,A2,B1加工的Ⅱ产品数量,c1为在A2,B2上加工的Ⅲ产品数量。
第一部分绪论第二部分线性规划与单纯形法1 判断下列说法是否正确:(a)图解法同单纯形法虽然求解的形式不同,但从几何上理解,两者是一致的;(b)线性规划模型中增加一个约束条件,可行域的范围一般将缩小,减少一个约束条件,可行域的范围一般将扩大;(c)线性规划问题的每一个基解对应可行域的一个顶点;(d)如线性规划问题存在可行域,则可行域一定包含坐标的原点;(e)对取值无约束的变量x i,通常令其中,在用单纯形法求得的最优解中有可能同时出现(f)用单纯形法求解标准型的线性规划问题时,与对应的变量都可以被选作换入变量;(g)单纯形法计算中,如不按最小比值原则选取换出变量,则在下一个解中至少有一个基变量的值为负;(h)单纯形法计算中,选取最大正检验数δk对应的变量x k作为换入变量,将使目标函数值得到最快的增长;(i)一旦一个人工变量在迭代中变为非基变量后,则该变量及相应列的数字可以从单纯形表中删除,而不影响计算结果;(j)线性规划问题的任一可行解都可以用全部基可行解的线性组合表示;(k)若x1,x2分别是某一线性规划问题的最优解,则也是该线性规划问题的最优解,其中λ1,λ2可以为任意正的实数;(1)线性规划用两阶段法求解时,第一阶段的目标函数通常写为X ai为人工变量),但也可写为,只要所有k i均为大于零的常数;(m)对一个有n个变量、m个约束的标准型的线性规划问题,其可行域的顶点恰好为个;(n)单纯形法的迭代计算过程是从一个可行解转转换到目标函数值更大的另一个可行解;(o)线性规划问题的可行解如为最优解,则该可行解一定是基可行解;(p)若线性规划问题具有可行解,且其可行域有界,则该线性规划问题最多具有有限个数的最优解;(q)线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值,则该顶点处的目标函数值达到最优;(r)将线性规划约束条件的“≤”号及“≥”号变换成“=”号,将使问题的最优目标函数值得到改善;(s)线性规划目标函数中系数最大的变量在最优解中总是取正的值;(t)一个企业利用3种资源生产4种产品,建立线性规划模型求解得到的最优解中,最多只含有3种产品的组合;(u)若线性规划问题的可行域可以伸展到无限,则该问题一定具有无界解;(v)一个线性规划问题求解时的迭代工作量主要取决于变量数的多少,与约束条件的数量关系相对较小。
【答案】1.1(a)(b)(f)(g)(i)(J)(1)(q)(t)正确,(c)(d)(e)(h)(k)(m)(n)(o)(p) (r)(s)(U)(v)不正确。
2用图解法求解下列线性规划问题,并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。
【答案】(a)唯一最优解,z*=3,x1=1/2,x2=0;(b)无可行解;(c)有可行解,但max z无界;(d)无穷多最优解,z*=66。
x1x2x3x4X5x 3 dx4 2 x5 3 4—1a 2a1—5—31OOO1OO1c j一z j C1C2O O O【答案】1.25(a)d≥0,C1<0,C2<0;(b)d≥0,c1≤0,C2≤o,但c1,C2中至少一个为零;(c)d=0,或d>0,而c1>0且d/4—3/a2;(d)C1>0,3/a2<d/4;(e)C2>0,a1≤0;(f)x5为人工变量,且c1≤0,C2≤o。
3 某战略轰炸机群奉命摧毁敌人军事目标。
已知该目标有四个要害部位,只要摧毁其中之一即可达到目的。
为完成此项任务的汽油消耗量限制为48000 1、重型炸弹48枚、轻型炸弹32枚。
飞机携带重型炸弹时每升汽油可飞行2 km,带轻型炸弹时每升汽油可飞行3 km。
又知每架飞机每次只能装载一枚炸弹,每出发轰炸一次除来回路程汽油消耗(空载时每升汽油可飞行4 km)外,起飞和降落每次各消耗100 1。
有关数据如表1—17所示。
表1—17摧毁可能性要害部位离机场距离/km 每枚重型弹每枚轻型弹1 2 3 4 4504805406000.100.200.150.250.O80.160.120.20为了使摧毁敌方军事门标的可能性最大,应如何确定飞机轰炸的方案。
要求建立这个问题的线性规划模型。
【答案】用i=1,2分别代表重型和轻型炸弹,j=1,2,3,4分别代表四个要害部位, x ij为投到第J部位的i种型号炸弹的数量,则问题的数学模型为式中目标函数非线性,但rain z等价于max 1g(1/z),因此目标函数可改写为4用单纯形法求解下列线性规划(1)123123123max342312230,1,2,3jZ x x xx x xx x xx j=++⎧++≤⎪++≤⎨⎪≥=⎩C(j)34100R. H. S.Ratio Basis C(i)X1X2X3X4X5X402[3]11011/3 X501220133/2 C(j)-Z(j)341000X24[2/3]11/31/301/31/2 X50-1/304/3-2/317/3M C(j)-Z(j)1/30-1/3-4/30-4/3X1313/21/21/201/2X5001/23/2-1/215/2C(j)-Z(j)0-1/2-1/2-3/20-3/2(2)1234 123412341234max23553730 310 264200,1,,4jZ x x x x x x x xx x x xx x x xx j=+-+++-≤⎧⎪-++≤⎪⎨--+≤⎪⎪≥=⎩【解】单纯形表:C(j)21-35000R. H. S.Ratio Basis C(i)X1X2X3X4X5X6X7X50153-710030M X603-1[1]10101010 X702-6-1[4]001205 C(j)-Z(j)21-35000X509/2-11/25/40107/4 65M X605/2 [1/2] 5/4 0 01-1/4 5 10 X451/2 -3/2-1/4 1 00 1/45M C(j)-Z(j)-1/217/2 -7/4000 -5/4X5032 0 15 0111 -1 120 M X21 5 1 5/2 0 0 2 -1/2 10 10 X458 0 7/2 1 0 3 -1/2 20 M C(j)-Z(j)-43 0 -23 00-17 3因为λ7=3>0并且a i7<0(i=1,2,3),故原问题具有无界解,即无最优解。
线性规划的对偶理论与灵敏度分析2.1写出下列线性规划问题的对偶问题:【答案】2.2已知线性规划问题:用单纯形法求解得最终单纯形表如表2~2所示。
(a)求和b l,b2;(b)求表2—2【答案】【解析】(1)由题意可设初始单纯形表的增广矩阵为最终单纯形表的增广矩阵为对矩阵22()A B 作初等行变换,使其第4,5列组成单位矩阵由单纯形运算法则可知,1133()()A B A B =所以,111213212223129/2,1,4,5/2,1,2,8,5a a a a a a b b ======== (2)由检验数的计算式可知()()()1323232/230/200/224c c c c c c c -+=-⎧⎪--=⎨⎪--+=-⎩ 求解上述方程组得:1237,4,8c c c ===2.3已知线性规划问题:用单纯形法求得最终表如表28所示。
表2-3试用灵敏度分析的方法分别判断:(a)目标函数系数C1或c2分别在什么范围内变动,上述最优解不变;(b)当约束条件右端项b1,b2中一个保持不变时,另一个在什么范围内变化,上述最优基保持不变;(c)问题的目标函数变为时上述最优解的变化;(d)约束条件右端项由变为【答案】2.4 已知表2—4为求解某线性规划问题的最终单纯形表,表中x4,x5为松弛变量问题的约束为≤形式。
表2-4(a)写出原线性规划问题;(b)写出原问题的对偶问题;(c)直接由表2—4写出对偶问题的最优解。
【答案】(a)原线性规划问题如下:(a)原线性规划问题如下:(b)略;(c)对偶问题最优解为Y*=(4,2)。
2.5已知线性规划问题:用单纯形法求解时,其最优解见表2—7。
表2-5要求:(a)直接写出上述问题的对偶问题及其最优解。
(b)若问题中x2列的系数变为(3,2,3)T,试问表2~7中的解是否仍为最优解? (C)若增加一个新的变量x4,其相应系数为(2,3,2)T。
试问增加新变量后表2—7中的最优解是否发生变化?【答案】(a)其对偶问题为其最优解为(b)zz系数变化后,对偶问题第(2)个约束将相应变为2y1+3y2≥3,将y1*,一¥2*代入不满足,故原问题最优解将发生变化;(C)相应于新变量x4,因有,故原问题最优解将发生变化。
2.6已知线性规划问题:要求:(a)写出它的对偶问题;(b)应用对偶理论证明原问题和对偶问题都存在最优解。
【答案】(a)略;(b)容易看出原1"3题和其对偶问题均存在可行解,据对偶理论,两者均存在最优解。
第三部分运输问题3.6某玩具公司分别生产三种新型玩具,每月可供量分别为l 000件、2000件和2000件,它们分别被送到甲、乙、丙三个百货商店销售。
已知每月百货商店各类玩具预期销售量均为1500件,由于经营方面原因,各商店销售不同玩具的赢利额不同(见表3—6)。
又知丙百货商店要求至少供应C玩具l 000件,而拒绝进A种玩具。
求满足上述条件下使总赢利额为最大的供销分配方案。
甲乙丙可供量解:用16减去利润表上的数字,使之变成一个运输问题。
由于表3-6中产大于销,因此需要增添一个假想的销地“丁”,其运价为0,其销售量为500,由于C 玩具至少要供给丙百货商店1000件,故将C 玩具拆成两个玩具,如表3-6(1)所示。
利用位势法求出表3-6(2)中各空格的检验数,如表3-6(3)。
此问题的最优调运方案,表中将A 调拨给丁500件,表明玩具A 有500件销不出去。
3.7 已知某运输问题的产销平衡表与单位运价表如表3—7所示。
表 3-7(a)求最优调拨方案;(b)如产地Ⅲ的产量变为130,又B 地区需要的115单位必须满足,试重新确定最优 调拨方案。
解:第一步:用伏格尔法求初始可行解,求得的初始解,如表3A-3所示。
第二步:用位势法进行最优解的判断。
在对应于表3A-3的数字格处填入单位运价,并增加一行一列,在行中填入j v ,在列中填入i u 。
令10u =,按照i j ij u v c +=(,i j B ∈)求出所有的i u 和j v ,并依据()ij ij i j c u v σ=-+(,i j N ∈)计算所有空格处的检验数,计算结果如表3A-3(1)所示。
表3A-3(1)A B C D E i uⅠ 15 0 35 0 Ⅱ 15 15 10 Ⅲ0 15 15 20 j v10155205由表3A-3(1)可知,所有空格处的检验数均为非负。