作业一:
(1) Minf(X)=x 12+x 22+8
x 12-x 2≤0 -x 1- x 22+2=0 x 1, x 2≥0
解:该非线性规划转化为标准型为:
Minf(X)=x 12+x 22+8 g 1(X)= x 2- x 12≥0 g 2(X)= -x 1- x 22+2≥0 g 3(X)= x 1+x 22-2≥0 g 4(X)= x 1≥0 g 5(X)= x 2≥0
f(X), g 1
2 0 ∣H ∣= = =4>0
0 2 -2 0
∣g 1∣= = =0≥0
0 0
0 0 ∣g 2∣= = =0
x 2
2
x 1x 2 x 1x 2
x 12 2f(X) 2
f(X) 2f(X) 2f(X)
x 22
x 1x 2
x 1x 2 x 12
2g 1(X) 2g 1(X)
2
g 1(X)
2
g 1(X) x 22
x 1x 2 x 1x 2
x 12 2
g 2(X) 2g 2(X) 2g 2(X) 2g 2(X)
0-2
设数(0<<1),令C(x)=x2,指定任意两点a和b,则
C(a+(1-)b)= 2a2+(1-)2b2+2(1-)ab (1)
C(a)+(1-)C(b)= a2+(1-)b2 (2)
于是C(a+(1-)b)- (C(a)+(1-)C(b))=a2(2-)-b2(1-)+2(1-)ab
=(2-)(a-b)2≤0
所以C(a+(1-)b)≤C(a)+(1-)C(b)
故C(x)=x2为凸函数,从而g3(X)=x1+x22-2为凸函数。
从而可知f(X)为严格凸函数,约束条件g3(X)为凸函数,所以该非线性规划不是凸规划。
(2)Minf(X)=2x12+x22+x32-x1x2
x12+x22≤4
5 x1+ x3=10
x1, x2, x3≥0
解:该非线性规划转化为标准型为:
Minf(X)=2x12+x22+x32-x1x2
g1(X)=4- x12-x22≥0
g2(X)= 5 x1+ x3-10=0
g3(X)= x1≥0
g4(X)=X2≥0
g 5(X)=X 3≥0
f(X), g 1(X),g 2(X),g 3(X),g 4(X),g 5(X)的海赛矩阵的行列式分别为:
从而可知f(X)为严格凸函数,g 1(X)为严格凹函数,又g 2(X)为线性函数,所以该非线性规划是凸规划。 作业二:
分别用分数法和0.618法求函数 f(t)=t 2-6t+2
在区间[0,10]上的极小点,要求缩小后的区间长度不大于原区间长度的3%。 解:(1)分数法
∣H ∣=
线性规划建模及单纯形法 思考题 主要概念及内容: 线性规划模型结构(决策变量,约束不等式、等式,目标函数);线性规划标准形式; 可行解、可行集(可行域、约束集),最优解;基、基变量、非基变量、基向量、非基向量;基本解、基本可行解、可行基、最优基。 复习思考题: 1、线性规划问题的一般形式有何特征? 2、建立一个实际问题的数学模型一般要几步? 3、两个变量的线性规划问题的图解法的一般步骤是什么? 4、求解线性规划问题时可能出现几种结果,哪种结果反映建模时有错误? 5、什么是线性规划的标准型,如何把一个非标准形式的线性规划问题转化成标准形式。 6、试述线性规划问题的可行解、基本解、基本可行解、最优解、最优基本解的概念及它 们之间的相互关系。 7、试述单纯形法的计算步骤,如何在单纯形表上判别问题具有唯一最优解、有无穷多个 最优解、无界解或无可行解。 8、在什么样的情况下采用人工变量法,人工变量法包括哪两种解法? 9、大M 法中,M 的作用是什么?对最小化问题,在目标函数中人工变量的系数取什 么?最大化问题呢? 10、什么是单纯形法的两阶段法?两阶段法的第一段是为了解决什么问题?在怎样的情 况下,继续第二阶段? 作业习题 1、将下列线性规划问题化为标准型
(1)?????? ?≥=--+-≥-+-≤+-++-+=0 ,,953413 223183622453max 4214321432143214 321x x x x x x x x x x x x x x x x x x x z (2)?????? ?≤≥=+-+-≥-+--≤--++++=0 ,0,152342722351 232243min 4214321432143214 321x x x x x x x x x x x x x x x x x x x f 2、(1)求出下列不等式组所定义的多面体的所有基本解和基本可行解(极点): ??? ??≥≤++-≤++0,,124326 3323 21321321x x x x x x x x x (2)对下述线性规划问题找出所有基本解,指出哪些是基本可行解,并确定最优解. ??? ??? ?≥=-=+-+=+++++=)6,,1(00 310 24893631223max 615 32143213 21 j x x x x x x x x x x x x x x z j 3、用图解法求解下列线性规划问题 (1)???????≥≤≤+≤-+=0 ,31223622max 2112 12 12 1x x x x x x x x x z (2)?????≥≥-≥++-=0 ,155356 743min 2121212 1x x x x x x x x z 4、在以下问题中,列出所有的基,指出其中的可行基,基础可行解以及最优解。 ??? ??≥≤-+≤++-+=0,,44622max 3 21321321321x x x x x x x x x x x x z 5、用单纯形法求解以下线性规划问题 (1)??? ??≥≤+-≤-+=0,533223max 2 121212 1x x x x x x x x z (2)?????≥≤-=++-=0,,12212 432max 3 213 23213 2x x x x x x x x x x z 6、用大M 法及两阶段法求解以下线性规划问题
运筹学作业 王程 信管1302 130404026
目录 运筹学作业 (1) 第一章线性规划及单纯形法 (3) 第二章线性规划的对偶理论与灵敏度分析 (24) 第三章运输问题 (53) 第四章目标规划 (63) 第五章整数规划 (73) 第六章非线性规划 (85) 第七章动态规划 (94) 第八章图与网络分析 (97) 第九章网络计划 (99)
第一章 线性规划及单纯形法 1.1分别用图解法和单纯形法求下列线性规划问题,⑴指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解;⑵当具有限最优解时,指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。 12 1212121min 23466 s.t.324,0z x x x x x x x x =++≥??+≥??≥?() 12 12121,22max 3222 s.t.34120z x x x x x x x x =++≤?? +≥??≥? () 12 1212123max 105349 s.t.528 ,0 z x x x x x x x x =++≤?? +≤??≥?() 12 1212124max 5622 s.t.232,0 z x x x x x x x x =+-≥??-+≤??≥?() 解:⑴图解法: 当212133 x x z = -经过点61 55(,)时,z 最小,且有无穷多个最优解。 ⑵图解法:
1 x 该问题无可行解。 ⑶图解法: 当21125 x x z =-+经过点3 12(,)时,z 取得唯一最优解。 单纯形法: 在上述问题的约束条件中分别加入松弛变量34,x x , 化为标准型:
大连科技学院运筹学(Z)大作业LINGO软件在函数最大值中的运用 学院名称 专业班级 学生组号 学生姓名 指导教师 二〇一八年五月
实验LINGO软件在函数最大值中的运用 大作业目的 掌握LINGO软件求解函数最大值的基本步骤,了解LINGO软件解决函数最大值的基本原理,熟悉常用的函数最大值计算代码,理解函数最大值的迭代关系。 仪器、设备或软件 电脑,LINGO软件 大作业内容 1.LINGO软件求解函数最大值的基本原理; 2.编写并调试LINGO软件求解函数最大值的计算代码; 实施步骤 1.使用LINGO计算并求解函数最大值问题; 2.写出实验报告,并浅谈学习心得体会(选址问题的基本求解思路与方法及求解过程中出现的问题及解决方法)。 实施过程 有一艘货轮,分为前、中、后三个舱位,它们的容积与允许载重量如下表所示。现有三种商品待运,已知有关数据列于下表中。又为了航运安全,要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系。具体要求前、后舱分别与中舱之间的载重量比例偏差不超过15%,前、后舱之间不超过10%。问货轮应装载A、B、C各多少件,运费收入为最大?试建立这个问题的线性规 首先分析问题,建立数学模型: 确定决策变量 假设i=1,2,3分别代表商品A、B、C,8用j=1,2,3分别代表前、中、后舱,设决策变量x ij为装于j舱位的第i种商品的数量(件)。 确定目标函数
商品A 的件数为: 商品B 的件数为: 商品A 的件数为: 为使运费最高,目标函数为: 确定约束条件 前、中、后舱位载重限制为: 前、中、后舱位体积限制为: A 、 B 、 C 三种商品数量的限制条件: 各舱最大允许载重量的比例关系构成的约束条件: 且决策变量要求非负,即x ij ≥0,i=1,2,3;j=1,2,3。 综上所述,此问题的线性规划数学模型为: 111213x x x ++212223x x x ++313233x x x ++()()()111213212223313233 1000700600Max Z x x x x x x x x x =++++++++112131122232132333865200086530008651500 x x x x x x x x x ++≤++≤++≤112131122232132333105740001057540010571500 x x x x x x x x x ++≤++≤++≤1112132122233132336001000800 x x x x x x x x x ++≤++≤++≤1121311222321323331222321121311323338x 6x 5x 2 2(10.15)(1+0.15)38x 6x 5x 3 8x 6x 5x 11(10.15)(1+0.15)28x 6x 5x 2 8x 6x 5x 4 4(10.10)(1+0.10)38x 6x 5x 3++-≤≤++++-≤≤++++-≤≤++()()() 111213212223313233112131122232132333112131122232132333 1000700600865200086530008651500105740001057540010571500 Max Z x x x x x x x x x x x x x x x x x x x x x x x x x x x =++++++++++≤++≤++≤++≤++≤++≤
作业一: (1) Minf(X)=x 12+x 22+8 x 12-x 2≤0 -x 1- x 22+2=0 x 1, x 2≥0 解:该非线性规划转化为标准型为: Minf(X)=x 12+x 22+8 g 1(X)= x 2- x 12≥0 g 2(X)= -x 1- x 22+2≥0 g 3(X)= x 1+x 22-2≥0 g 4(X)= x 1≥0 g 5(X)= x 2≥0 f(X), g 1 2 0 ∣H ∣= = =4>0 0 2 -2 0 ∣g 1∣= = =0≥0 0 0 0 0 ∣g 2∣= = =0 x 2 2 x 1x 2 x 1x 2 x 12 2f(X) 2 f(X) 2f(X) 2f(X) x 22 x 1x 2 x 1x 2 x 12 2g 1(X) 2g 1(X) 2 g 1(X) 2 g 1(X) x 22 x 1x 2 x 1x 2 x 12 2 g 2(X) 2g 2(X) 2g 2(X) 2g 2(X)
0-2 设数(0<<1),令C(x)=x2,指定任意两点a和b,则 C(a+(1-)b)= 2a2+(1-)2b2+2(1-)ab (1) C(a)+(1-)C(b)= a2+(1-)b2 (2) 于是C(a+(1-)b)- (C(a)+(1-)C(b))=a2(2-)-b2(1-)+2(1-)ab =(2-)(a-b)2≤0 所以C(a+(1-)b)≤C(a)+(1-)C(b) 故C(x)=x2为凸函数,从而g3(X)=x1+x22-2为凸函数。 从而可知f(X)为严格凸函数,约束条件g3(X)为凸函数,所以该非线性规划不是凸规划。 (2)Minf(X)=2x12+x22+x32-x1x2 x12+x22≤4 5 x1+ x3=10 x1, x2, x3≥0 解:该非线性规划转化为标准型为: Minf(X)=2x12+x22+x32-x1x2 g1(X)=4- x12-x22≥0 g2(X)= 5 x1+ x3-10=0 g3(X)= x1≥0 g4(X)=X2≥0
《运筹学》作业 第2章 1.某公司计划生产两种产品,已知生产单位产品所需的三种原材料的消耗及所获的利润, 产品利润=40X+50Y 约束条件: X+2Y<=30 3X+2Y<=60 2Y<=24 X,Y>=0 用图解法得出安排生产产品1为15件,产品2为7.5件时工厂的获利最多,最大利润为975。 2.某公司计划生产两种产品,已知生产单位产品所需的两种原材料的消耗和人员需要及所获的利润,如下表所示。问应如何安排生产使该工厂获利最多?(建立模型,并用图解 产品利润=300X+500Y 约束条件: X<=4 2Y<=12 3X+2Y<=24 X,Y>=0 用图解法得出,该公司安排生产产品1为4件,产品2为6件时该工厂获利最大,最大利润为4200。 3. 下表是一个线性规划模型的敏感性报告,根据其结果,回答下列问题: 1)是否愿意付出11元的加班费,让工人加班; 答:不愿意付出11元加班费让工人加班。 2)如果工人的劳动时间变为402小时,日利润怎样变化? 答:日利润增加2×8=16
3)如果第二种家具的单位利润增加5元,生产计划如何变化? 答:因为允许的增加量是10,所以生产计划不变 Microsoft Excel 9.0 敏感性报告 工作表 [ex2-6.xls]Sheet1 报告的建立: 2001-8-6 11:04:02 可变单元 格 终递减目标式允许的允许的单元格名字值成本系数增量减量 $B$15 日产量(件)100 20 60 1E+30 20 $C$15 日产量(件)80 0 20 10 2.5 $D$15 日产量(件)40 0 40 20 5.0 $E$15 日产量(件)0 -2.0 30 2.0 1E+30 约束 终阴影约束允许的允许的单元格名字值价格限制值增量减量 $G$6 劳动时间(小时/件)400 8 400 25 100 $G$7 木材(单位/件)600 4 600 200 50 $G$8 玻璃(单位/件)800 0 1000 1E+30 200 4某公司计划生产两种产品,已知生产单位产品所需的三种原材料的消耗及所获的利润,如 解:设生产产品1为X件,生产产品2为Y件时,工厂获利最多 产品利润=25X+10Y 约束条件: 0.6X+0.5Y<=12000 0.4X+0.1Y<=4000 0.4Y<=6000 X,Y>=0
运筹学作业2(第二章部分习题)答案 2.4 给出线性规划问题 123412341234min 2356232.. 2330,1,2,3,4 j z x x x x x x x x s t x x x x x j =+++?+++≥? -+-+≤-??≥=? (1)写出其对偶问题;(2)用图解法解对偶问题;(3)利用(2)的结果及根据对偶问 题性质写出原问题的最优解。 解:(1)原问题的对偶问题为: 12 12121212 12max 2322 23.. 35 36 0,0 w y y y y y y s t y y y y y y =--≤??+≤?? -≤??+≤??≥≤? 或者等价变形为: 12 12121212 12max 232223..3536 0,0 w y y y y y y s t y y y y y y =++≤??-≤?? +≤??-≤??≥≥? (2)用图解法求解对偶问题 12 12121212 max 2322 23.. 3536 w y y y y y y s t y y y y =++≤??-≤?? +≤??-≤ 如图示,可行区域为四边形OABC ,最优顶点为B 点,即(1.6,0.2)y * =, 3.8w * =
(3)利用互补松紧定理及(2)的结果求解原问题: 设原问题的最优解为( )1 23 4x x x x x ** ***=。 由于121.60, 0.20y y * * =>=>,故在最优解()12 3 4x x x x x ** * **=处有: 1234 1234232 2330,1,2,3,4j x x x x x x x x x j ******** * ?+++=??-+-+=-??≥=?? 又因对偶问题第4个约束方程为:1.6-0.6=1<6,故40x * =,代入上式得到: 123 123232 230,1,2,3,4j x x x x x x x j ****** * ?++=??-+-=-??≥=?? 原问题有无穷多个最优解。令30x *=得到解为1 1.6x *=,20.2x *= 即()1.60.200x * =, 3.8z * = 2.8题解答见课堂讲解。 2.9 用对偶单纯形法求解下列线性规划问题: (2) 123 123123123min 524324 .. 63510,,0z x x x x x x s t x x x x x x =++++≥?? ++≥??≥? , 解:先将原问题进行标准形化: 1231234123512345max()524324 .. 63510,,,,0 z x x x x x x x s t x x x x x x x x x -=---++-=?? ++-=??≥? 选45,x x 为基变量,并将问题化为: 1231234123512345max()524324 .. 63510,,,,0z x x x x x x x s t x x x x x x x x x -=------+=-?? ---+=-??≥? 列表计算如下:
《 运筹学》综合练习题 第一章 线性规划及单纯形法 1、教材43页——44页1.1题 2、教材44页1.4题 3、教材45页1.8题 4、教材46页1.13题 5、教材46页1.14题 6、补充:判断下述说法是否正确 ● LP 问题的可行域是凸集。 ● LP 问题的基本可行解对应可行域的顶点。 ● LP 问题的最优解一定是可行域的顶点,可行域的顶点也一定是最优解。 ● 若LP 问题有两个最优解,则它一定有无穷多个最优解. ● 求解LP 问题时,对取值无约束的自由变量,通常令 "-'=j j j x x x ,其中∶ ≥"' j j x x ,在用单纯形法求得的最优解中,不可能同时出现 "' j j x x . ● 当用两阶段法求解带有大M 的LP 模型时,若第一阶段的最优目标函数值为零,则可 断言原LP 模型一定有最优解。 7、补充:建立模型 (1)某采油区已建有n 个计量站B 1,B 2…B n ,各站目前尚未被利用的能力为b 1,b 2…b n (吨液量/日)。为适应油田开发的需要,规划在该油区打m 口调整井A 1,A 2…A m ,且这些井的位置已经确定。根据预测,调整井的产量分别为a 1,a 2…a m (吨液量/日)。考虑到原有计量站富余的能力,决定不另建新站,而用原有老站分工管辖调整井。按规划要求,每口井只能属于一个计量站。假定A i 到B j 的距离d ij 已知,试确定各调整井与计量站的关系,使新建集输管线总长度最短。 (2)靠近某河流有两个化工厂(见附图),流经第一个工厂的河流流量是每天500万立方米;在两个工厂之间有一条流量为每天200万立方米的支流。第一个工厂每天排放工业污水2万立方米;第二个工厂每天排放工业污水1.4万立方米 。从第一个工厂排出的污水流到第二个工厂之前,有20%可自然净化。根据环保要求,河流中工业污水的含量不应大于0.2%,若这两个工厂都各自处理一部分污水,第一个工厂的处理成本是1000元/万立方米,第二个工厂的处理成本是800元
课程名称:对偶单纯形法 一、教学目标 在对偶单纯形法的学习过程中,理解和掌握对偶问题;综合运用线性规划和对偶原理知识对对偶单纯形法与单纯形法进行对比分析,了解单纯形法和对偶单纯形法的相同点和不同点,总结出各自的适用范围;掌握对偶单纯形法的求解过程;并能运用对偶单纯形法独立解决一些运筹学问题。 二、教学内容 1) 对偶单纯形法的思想来源(5min) 2) 对偶单纯形法原理(5min) 3) 总结对偶单纯形法的优点及适用情况(5min) 4) 对偶单纯形法的求解过程(10min) 5) 对偶单纯形法例题(15min) 6) 对比分析单纯形法和对偶单纯形法(10min) 三、教学进程: 1)讲述对偶单纯形法思想的来源: 1954年美国数学家C.莱姆基提出对偶单纯形法(Dual Simplex Method )。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解,直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性,而使不可行性逐步消失。因此在保持对偶可行性的前提下,一当基解成为可行解时,便也就是最优解。 2)讲述对偶单纯形法的原理 A.对偶问题的基本性质 依照书第58页,我们先介绍一下对偶问题的六个基本性质: 性质一:弱对偶性 性质二:最优性。如果 x j (j=1...n)原问题的可行解,y j 是其对偶问题可 行解,且有 ∑=n j j j x c 1 =∑=m i i i y b 1 ,则x j 是原问题的最优解,y j 是其对偶问题的最
优解。 性质三:无界性。如果原问题(对偶问题)具有无界解,则其对偶问题(原问题)无可行解。 性质四:强对偶性。如果原问题有最优解,则其对偶问题也一定有最优解。 性质五:互补松弛型。在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值为零,则该约束条件取严格等式;反之如果约束条件取严格不等式,则其对应的对偶变量一定为零。 性质六:线性规划的原问题及其对偶问题之间存在一对互补的基解,其中原问题的松弛变量对应对偶问题的变量,对偶问题的剩余变量对应原问题的变量;这些互相对应的变量如果在一个问题的解中是基变量,则在另一问题的解中是非基变量;将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w. B.对偶单纯形法(参考书p64页) 设某标准形式的线性规划问题,对偶单纯形表中必须有c j -z j ≤0(j=1...n),但b i (i=1...m)的值不一定为正,当对i=1...m ,都有b i ≥0时,表中原问题和对偶问题均为最优解,否则通过变换一个基变量,找出原问题的一个目标函数值较小的相邻的基解。 3)为什么要引入对偶单纯形法 从理论上说原始单纯形法可以解决一切线性规划问题,然而实际问题中,由于考虑问题的角度不同,变量设置的不同,便产生了原问题及其对偶问题,对偶问题是原问题从另外一个角度考虑的结果。用对偶单纯形法求解线性规划问题时,当约束条件为“≥”时,不必引入人工变量,使计算简化。 例如,有一线性规划问题: min ω =12 y 1 +16y 2 +15 y 3 约束条件 ?? ?? ???≥=≥+≥+0)3,2,1(3522 423121 i y y y y y i
第一章 导论 1.简述运筹学的定义。 运筹学利用计划方法和有关多学科的要求,把复杂功能关系表示成数学模型,其目的是通过定量分析为决策和揭露新问题提供数量根据。 2. 决策方法可以分为哪几类。 定性决策,定量决策,混合性决策。 3. 应用运筹学进行决策过程的步骤有哪些。 (1)观察待决策问题所处的环境;(2)分析和定义待决策的问题;(3)拟定模型;(4)选择输入资料;(5)提出解并验证它的合理性;(6)实施最优解。 实践能力考核选例 根据本章学习的内容,结合实际例子,说明在应用运筹学进行决策过程中的六个步骤有哪些? (1)观察待决策问题所处的环境;(2)分析和定义待决策的问题;(3)拟定模型;(4)选择输入资料;(5)提出解并验证它的合理性;(6)实施最优解。 第二章 预测 1.比较特尔斐法和专家小组法这两种定性预测法的特点。 特尔斐法的特点是:第一,专家发表意见是匿名的;第二,进行多次信息反馈;第三,由调研人员整理并归纳专家们的总结意见,将比较统一的意见和比较特殊的意见一起交给有关部门,以供他们决策。 专家小组法的优点是可以做到相互协商、相互补充;但当小组会议组织得不好时,也可能会使权威人士左右会场或多数人的意见湮没了少数人的创新见解。 2.简述指数平滑预测法的原理。 1()t t t t F F x F α+=+-,其中1t F +、t F 是1t +期、t 期的预测值,t x 是t 期的实际值,α是 平滑系数。 3.简述一元线性回归模型预测的过程。 先根据x 、y 的历史数据,求出a 和b 的值,建立起回归模型,再运用模型计算出不同的x 所相对的不同的y 值。 实践能力考核选例 应用简单滑动平均预测法,加权滑动平均预测法,指数平滑预测法,来预测中国2012年的居民消费指数(CPI )水平。(资料可由历年中国统计年鉴获得) (1)滑 动平均预测法:(1270.8+1191.8+1239.9+1265)/4=1241.875
《运筹学参考综合习题》 (我站搜集信息自编,非南邮综合练习题,仅供参考) 资料加工、整理人——杨峰(函授总站高级讲师) 可能出现的考试方式(题型) 第一部分填空题(考试中可能有5个小题,每小题2分,共10分) ——考查知识点:几个基本、重要的概念 第二部分分步设问题(即是我们平常说的“大题”,共90分) ——参考范围: 1、考两变量线性规划问题的图解法(目标函数为max z和min z的各1题) 2、考线性规划问题的单纯形解法(可能2个题目:①给出问题,要求建立线性规划模型,再用单纯形迭代表求解;②考查对偶问题,要求写出原问题的线性规划模型之后写出其对偶问题的线性规划模型,然后用大M法求解其对偶问题,从而也得到原问题的最优解) 3、必考任务分配(即工作指派)问题,用匈牙利法求解。 4、考最短路问题(如果是“动态规划”的类型,则用图上标号法;如果是网络分析的类型,用TP标号法,注意不要混淆) 5、考寻求网络最大流(用寻求网络最大流的标号法) 6、考存储论中的“报童问题”(用概率论算法模型解决) ——未知是否必考的范围: 1、运输规划问题(用表上作业法,包括先求初始方案的最小元素法和将初始方案调整至最优的表上闭回路法); 2、求某图的最小生成树(用破圈法,非常简单) ※考试提示:可带计算器,另外建议带上铅笔、直尺、橡皮,方便绘图或分析。
第一部分 填空题复习参考 一、线性规划部分: ㈠基本概念:定义:满足所有约束条件的解为可行解;可行解的全体称为可行(解)域。 定义:达到目标的可行解为最优解。 由图解法得到的三个结论:①线性规划模型的可行解域是凸集; ②如果线性规划模型有唯一的最优解的话,则最优解一定是凸集(可行解域)的角顶; ③任何一个凸集,其角顶个数是有限的。 ㈡有关运输规划问题的概念:设有m 个产地A i (i=1,2,…,m ),n 个销地B j (j=1,2,…,n ), A i 产量(供应量)S i ,B j 销量(需求量)d i ,若产、销平衡,则:∑∑===n j j m i i d s 1 1 二、网络分析中的一些常用名词: 定义:无方向的边称为边;有方向的边称为弧。 定义:赋“权”图称为网络。 定义:有向图中,若链中每一条弧的走向一致,如此的链称为路。闭链称为圈。闭回路又称为回路。 定义:在图G 中任两点间均可找到一条链,则称此图为连通图。无重复边与自环的图称为连通图。 定义:树是无圈的连通图。 树的基本性质:①树的任两点之间有且只有一条链; ②若图的任两点之间有且只有一条链,则此图必为树;
练习一 1.某厂接到生产A 、B 两种产品的合同,产品A 需200件,产品B 需300件。这两种 产品的生产都经过毛坯制造与机械加工两个工艺阶段。在毛坯制造阶段,产品 A 每件需要2小时,产品B 每件需要4小时。机械加工阶段又分粗加工和精加工两道 工序,每件产品A 需粗加工4小时,精加工10小时;每件产品B 需粗加工7小时,精 加工12小时。若毛坯生产阶段能力为1700小时,粗加工设备拥有能力为1000小时, 精加工设备拥有能力为3000小时。又加工费用在毛坯、粗加工、精加工时分别为 每小时3元、3元、2元。此外在粗加工阶段允许设备可进行 500小时的加班生产, 但加班生产时间内每小时增加额外成本元。 试根据以上资料,为该厂制订一个成 本最低的生产计划。 解:设正常生产A,B 产品数X 1,X 2,加班生产A,B 产品数X 3,X 4 min z 3(2x 1 2X 3 4X 2 4X 4 4X 1 4X 3 7X 2 7&) 7.5(4X 3 7X 4) 2(10X 1 10X 3 12X 2 12X 4) X 3 200 X 4 300 4x 2 1700 7x 2 1000 12x 2 3000 7x 2 500 0且为整数,i=1,2,3,4 2.对某厂I ,n,m 三种产品下一年各季度的合同预订数如下表所示。 该三种产品I 季度初无库存,要求在4季度末各库存150件。已知该厂每季度生产 工时为15000小时,生产I 、n 、m 产品每件分别需时2、4、3小时。因更换工艺装备, 产品I 在2季度无法生产。规定当产品不能按期交货时, 产品I , n 每件每迟交一个季 度赔偿20元,产品m 赔偿10元;又生产出来产品不在本季度交货的,每件每季度的 库存费用为5元。问:该厂应如何安排生产,使总的赔偿加库存的费用为最小 (要求 建立数学模型,不需求解)。 解:设X ij 为第j 季度产品i 的产量,S ij 为第j 季度末产品i 的库存量,d ij 为第j 季度 X 1 X 2 2为 s.t 4x , 10x 1 4X 1 X i 量,
练习一 1. 某厂接到生产A 、B 两种产品的合同,产品A 需200件,产品B 需300件。这两种产品的生产都经过毛坯制造与机械加工两个工艺阶段。在毛坯制造阶段,产品A 每件需要2小时,产品B 每件需要4小时。机械加工阶段又分粗加工和精加工两道工序,每件产品A 需粗加工4小时,精加工10小时;每件产品B 需粗加工7小时,精加工12小时。若毛坯生产阶段能力为1700小时,粗加工设备拥有能力为1000小时,精加工设备拥有能力为3000小时。又加工费用在毛坯、粗加工、精加工时分别为每小时3元、3元、2元。此外在粗加工阶段允许设备可进行500小时的加班生产,但加班生产时间内每小时增加额外成本4.5元。试根据以上资料,为该厂制订一个成本最低的生产计划。 解:设正常生产A,B 产品数12,x x ,加班生产A,B 产品数34,x x 13241324341324min 3(22444477)7.5(47)2(10101212)z x x x x x x x x x x x x x x =+++++++++++++.s t 132412121 2 12200300241700471000 10123000 475000i x x x x x x x x x x x x x +≥?? +≥??+≤? +≤??+≤?+≤?? ≥?且为整数,i=1,2,3,4 2. 对某厂I ,Ⅱ,Ⅲ三种产品下一年各季度的合同预订数如下表所示。 工时为15000小时,生产I 、Ⅱ、Ⅲ产品每件分别需时2、4、3小时。因更换工艺装备,产品I 在2季度无法生产。规定当产品不能按期交货时,产品I ,Ⅱ每件每迟交一个季度赔偿20元,产品Ⅲ赔偿10元;又生产出来产品不在本季度交货的,每件每季度的库存费用为5元。问:该厂应如何安排生产,使总的赔偿加库存的费用为最小(要求建立数学模型,不需求解)。 解:设x ij 为第j 季度产品i 的产量,s ij 为第j 季度末产品i 的库存量,d ij 为第j 季度产品
四、把下列线性规划问题化成标准形式: 2、minZ=2x1-x2+2x3 五、按各题要求。建立线性规划数学模型 1、某工厂生产A、B、C三种产品,每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量,单位产品的利润如下表所示: 根据客户订货,三种产品的最低月需要量分别为200,250和100件,最大月销售量分别为250,280和120件。月销售分别为250,280和120件。问如何安排生产计划,使总利润最大。 2、某建筑工地有一批长度为10米的相同型号的钢筋,今要截成长度为3米的钢筋90根,长度为4米的钢筋60根,问怎样下料,才能使所使用的原材料最省? 1.某运输公司在春运期间需要24小时昼夜加班工作,需要的人员数量如下表所示: 起运时间服务员数 2—6 6—10 10一14 14—18 18—22 22—2 4 8 10 7 12 4 每个工作人员连续工作八小时,且在时段开始时上班,问如何安排,使得既满足以上要求,又使上班人数最少? 五、分别用图解法和单纯形法求解下列线性规划问题.并对照指出单纯形迭代的每一步相当 于图解法可行域中的哪一个顶点。 六、用单纯形法求解下列线性规划问题: 七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类。 八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ=5x1+3x2,约束形式为“≤”,X3,X4为松驰变量.表中解代入目标函数后得Z=10 X l X2X3X4 —10 b -1 f g X3 2 C O 1 1/5 X 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,试应用对偶问题的性质求原问题的最优解。 七、用对偶单纯形法求解下列线性规划问题: 八、已知线性规划问题
运筹学部分课后习题解答P47 1.1 用图解法求解线性规划问题 a) 12 12 12 12 min z=23 466 ..424 ,0 x x x x s t x x x x + +≥ ? ? +≥ ? ?≥ ? 解:由图1可知,该问题的可行域为凸集MABCN,且可知线段BA上的点都 为最优解,即该问题有无穷多最优解,这时的最优值为 min 3 z=2303 2 ?+?= P47 1.3 用图解法和单纯形法求解线性规划问题 a) 12 12 12 12 max z=10x5x 349 ..528 ,0 x x s t x x x x + +≤ ? ? +≤ ? ?≥ ? 解:由图1可知,该问题的可行域为凸集OABCO,且可知B点为最优值点, 即 1 12 122 1 349 3 528 2 x x x x x x = ? += ?? ? ?? +== ?? ? ,即最优解为* 3 1, 2 T x ?? = ? ?? 这时的最优值为 max 335 z=1015 22 ?+?=
单纯形法: 原问题化成标准型为 121231241234 max z=10x 5x 349 ..528,,,0x x x s t x x x x x x x +++=?? ++=??≥? j c → 10 5 B C B X b 1x 2x 3x 4x 0 3x 9 3 4 1 0 0 4x 8 [5] 2 0 1 j j C Z - 10 5 0 0 0 3x 21/5 0 [14/5] 1 -3/5 10 1x 8/5 1 2/5 0 1/5 j j C Z - 1 0 - 2 5 2x 3/2 0 1 5/14 -3/14 10 1x 1 1 0 -1/7 2/7 j j C Z - -5/14 -25/14
No .1 线性规划 1、某织带厂生产A 、B 两种纱线和C 、D 两种纱带,纱带由专门纱线加工而成。 工厂有供纺纱的总工时7200h ,织带的总工时1200h 。 (1) 列出线性规划模型,以便确定产品的数量使总利润最大; (2) 如果组织这次生产具有一次性的投入20万元,模型有什么变化?对模型的 解是否有影响?(所谓一次性投入就是与产量无关的初始投资) 2、将下列线性规划化为极大化的标准形式 3、用单纯形法解下面的线性规划 ??? ??? ?≥≤++-≤++-≤-+++= ,0,,4205.021********* ..352)(m ax 3213213213213 21x x x x x x x x x x x x t s x x x x f No .2 两阶段法和大M 法 2、用大M 法解下面问题,并讨论问题的解。 ??? ??? ?≥≥++≤++-≤++++= ,0,,52151565935 ..121510)(max 3213213213213 21x x x x x x x x x x x x t s x x x x f 1、用两阶段法解下面问题: ??? ??≥≥+≥++=0,75 3802 ..64)(min 2 121212 1x x x x x x t s x x x f ?????? ?±≥≤+-=-+--≥-+++=不限 321321321321321 ,0,13|5719|169765 ..532)(m in x x x x x x x x x x x x t s x x x x f
No .3 线性规划的对偶问题 ?????-≤≤-≤≤≤≤-+-=8121446 2 ..834)(min 3213 21x x x t s x x x x f 2、写出下问题的对偶问题,解对偶问题,并证明原问题无可行解 3、用对偶单纯形法求下面问题 ??? ??≥≥+≥++=0,75 3802 ..64)(min 2 121212 1x x x x x x t s x x x f No .4 线性规划的灵敏度分析 原问题为max 型,x 4,x 5为松驰变量,x 6为剩余变量,回答下列问题: (1)资源1、2、3的边际值各是多少?(x 4,x 5是资源1、2的松驰变量,x 6是资 源3的剩余变量) (2)求C 1, C 2 和C 3的灵敏度范围; (3)求?b 1,?b 2的灵敏度范围。 1、写出下列线性规划问题的对偶问题: (1) ???????±≥≤=++≤+≥+-+-+=不限 432143231 4321321 ,0,,06 4 2 5 ..532)(max x x x x x x x x x x x x x t s x x x x f (2) ?????? ?≥≤+--≤-≤+--= ,0, 121 1 ..34)(m ax 212122121x x x x x x x t s x x x f
运筹学作业2(清华版第二章部分习题)答案
解:根据原一对偶关系表,可得原问题的对偶规划问题为: m n maxw a i U i i 1 j 1 b j V j U i V j C ij i 1,111 |,m; j 1,川 ,n 2. 2判断下列说法是否正确,为什么? (1)如果线性规划的原问题存在可行解,则其对偶问题也一定存在可行解; 答:错。 运筹学作业2 (第二章部分习题)答案 2. 1题(P. 77)写出下列线性规划问题的对偶问题: maxz 2x 1 2x 2 4x 3 s.t x 1 3x 2 4x 3 2 (1) 2x 1 x 2 3x 3 3 x 1 4x 2 3x 3 5 x 1 0, x 2 0,x 3无约束 解:根据原一对偶关系表,可得原问题的对偶规划问题为: maxw 2y 3y 2 5y 3 s.t y i 2y 2 y 3 2 3y i 讨2 4y3 2 4y i 3y 2 3y 3 4 y i 0 ,y 2 °』3 0 (2) min z qX j i 1 j 1 qX j a i ,i 1,|| ,m 1 CM b j , j 1,|| ,n 1 0,i 1,|||,m;j 1」|| m n n j 1 n j 1 ,n X j U i 无约束,v j 无约 束
因为:若线性规划的原问题存在可行解,且其对偶问题有可行解,则原问题和可行问题都将有最优解。但,现实中肯定有一些问题是无最优解的,故本题说法不对。 max z 3 X i X2 例如原问题X i X2 1有可行解,但其对偶问题 s.t. x2 3 X i 0, X2 0 min w y i 3 y 2 y i 3无可行解。 s.t. y i y2 i y i 0, y2 0 (2)如果线性规划的对偶问题无可行解,则原问题也一定无可行解; 答:错,如(i)中的例子。 (3)在互为对偶的一对原问题与对偶问题中,不管原问题是求极大或求极 小,原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函 数值。 答:错。正确说法是:在互为对偶的一对原问题与对偶问题中,求极大的问题可行解的目标函数值一定不超过求极小的问题可行解的目标函数值。 (4)任何线性规划问题具有唯一的对偶问题。 答:正确。 2. 5给出线性规划问题 max z X i 2 X2X3 X i X2 X3 2 X i X2 X3 i s.t. 2 X i X2 X 3 2 X i 0, X2 0, X3 0 写出其对偶问题;(2)禾I」用对偶问题性质证明原问题目标函数值z i
浙江大学远程教育学院 《运筹学》课程作业 姓名:姜胜超学号:715003322021 年级:15秋学习中心:宁波学习中心————————————————————————————— 第2章 1.某公司计划生产两种产品,已知生产单位产品所需的三种原材料的消耗及所获的利润, 产品1 产品2 可用的材料数 原材料A 原材料B 原材料C 1 3 2 2 2 30 60 24 单位产品获利40万元50万元 1. 产品利润为P(万元) 则P=40x+50y 作出上述不等式组表示的平面区域,即可行域:
由约束条件可知0ABCD 所在的阴影部分,即为可行域 目标函数P=40x+50y 是以P 为参数,-54 为斜率的一族平行线 y =- 5 4 x +50P (图中红色虚线) 由上图可知,目标函数在经过C 点的时候总利润P 最大 即当目标函数与可行域交与C 点时,函数值最大 即最优解C=(15,7.5),最优值P=40*15+50*7.5=975(万元) 答:当公司安排生产产品1为15件,产品2为7.5件时使工厂获利最大。 2. 某公司计划生产两种产品,已知生产单位产品所需的两种原材料的消耗和人员需要及所 获的利润,如下表所示。问应如何安排生产使该工厂获利最多?(建立模型,并用图解 产品1 产品2 可用的材料数 原材料A 原材料B 人时 1 0 3 0 2 2 4 12 24 单位产品获利 300万元 500万元 解:设生产产品1为x 件,生产产品2为y 件时,使工厂获利最多 产品利润为P (万元) 则 P=300x+500y 作出上述不等式组表示的平面区域,即可行域:
运筹学课程上机实践要求及内容(2) 一、实验教学的目的和要求 目的:借助运筹学软件的强大功能,通过小组的充分讨论,对管理实践中的实际问题进行建模、求解,并对求解结果进行分析(特别是敏感性分析),进而激发学生的学习兴趣和热情,克服对课程学习的“恐惧感”。 要求:熟练掌握LINGO、WinQSB等软件的基本功能和基本语法结构,能用软件对运筹学问题进行求解和分析。 二、请于第1次-第6次上机时间及平时完成。 三、作业务请写清学号、姓名、专业、班级,上机作业格式请用老 师提供的模版。 四、编写的代码请用记事本单独保存。 五、要求所有题目用LINGO和教材自带的求解软件各做一遍。并分 析解释求解的结果。 六、各题目中的A,B,C,D,E,F为参数,除特别规定外,请自 行设定,各个同学参数值不能相同,若发现完全一致的,作业以零分计。 A=1,B=2,C=2,D=4,E=4,F=1
第1题(线性规划) (1)介绍单纯型算法及其处理人工变量的两阶段法; (2)建立下列问题的数学模型并求解,讨论资源的影子价格; 某造纸厂拟生产漂白松木浆、包装纸(水泥、松木包装纸、松木本色纸)、漂白桦木纸和胶版纸等四种产品,单位产品所需资源情况见表1,市场上胶版纸的需求量不超过6000吨。(a)制订该造纸厂的生产计划;(b)若电的资源可用量下降10%,重新制订该造纸厂的生产计划。 (3)结合本题,谈谈你对线性规划的认识。 Hint: 若参数为5,5,5,5,5,5,则最优目标函数值为(a)167236800; (b)167236800。 解: (1)单纯形法是求解线性规划问题的通用方法。单纯形法的基本思想是:先找出 一个基本可行解,对它进行鉴别,看是否是最优解;若不是,则按照一定法则转 换到另一改进的基本可行解,再鉴别;若仍不是,则再转换,按此重复进行。因 基本可行解的个数有限,故经有限次转换必能得出问题的最优解。如果问题无最 优解也可用此法判别。 两阶段单纯形法也是一种人工变量法,它的算法可分为两个阶段:第一阶段,引 入人工变量,构造一个具有标准基的新线性规划,求解这个新线性规划,其结果