南农工-工管162-rambo运筹学实验报告20181128-Bai-Di

1、实验报告册课程名称：运筹学实验指导老师：班 级：姓 名：学 号：学 期： 20 18 20 19 学年 第 1 学期南京农业大学工学院教务处印 实 验 目 录实验一：软件介绍及线性规划实验二：线性规划灵敏度分析实验三：线性规划对偶问题实验四：运输问题实验五：目标规划实验六：整数规划及指派问题实验七：图与网络分析实验一：软件介绍及线性规划1.简述LINGO软件的功能特点。（1）简单的模型表示 LINGO 可以将线性、非线性和整数问题迅速得予以公式表示，并且容易阅读、了解和修改。LINGO的建模语言允许使用汇总和下标变量以一种易懂的直观的方式来表达模型，非常类似在使用纸和笔。模型更加容易构建，更容

2、易理解，因此也更容易维护。 （2）方便的数据输入和输出选择 LINGO 建立的模型可以直接从数据库或工作表获取资料。同样地，LINGO 可以将求解结果直接输出到数据库或工作表。能够在选择的应用程序中生成报告. （3）强大的求解器 LINGO拥有一整套快速的,内建的求解器用来求解线性的,非线性的(球面&非球面的),二次的,二次约束的,和整数优化问题.您甚至不需要指定或启动特定的求解器,因为LINGO会读取方程式并自动选择合适的求解器. （4）. 交互式模型或创建Turn-key应用程序 能够在LINGO内创建和求解模型,或能够从自己编写的应用程序中直接调用LINGO.对于开发交互式模型,LING

3、O提供了一整套建模环境来构建,求解和分析模型.对于构建turn-key解决方案,LINGO提供的可调用的DLL和OLE界面能够从用户自己写的程序中被调用.LINGO也能够从Excel宏或数据库应用程序中被直接调用. 2. 手工求解下面的线性规划问题并用Lingo验证。 Max Z= 3x1+ x3S.T. x1 +x2 +x3 4 2x1 +x2 -x3 1 3x2 +x3 = 9 x1，x2，x3 03. 工业原料的合理利用：要制作100套钢筋架子，每套有长2.9米、2.1米和1.5米的钢筋各一根。已知原材料长7.4米，应如何切割使用原材料最省？请建立该问题的数学模型，并用Lingo软件求解

4、（写出程序），并解释状态窗口的含义。 编程如下：min=7.4*(x1+x2+x3+x4+x5);2*x1+x2+x3=100;2*x2+x3+3*x4=100;x1+x3+4*x5=100;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);关于上图的含义解释如下：(1) Model(模型) LP(线性规划) Linear programming；(2) State(状态) Global Opt(整体最优解) Global optimal solution；(3) Objective，目标函数值为695.6，由于处于最优解状态，所以这里表示最优值为695.6；(4

5、) Infeasibility 0，不可行性0，表示此时有可行解，否则没有可行解；(5) Iteration 4，表示迭代了4步求得最优解；(6) Extended Solver Status，表示扩展的解的状况，主要用于整数规划和非线性规划；(7) Variables，表示变量，Total 5，表示总决策变量5个，非线性(Nonlinear)变量是0个和整数(Integer)变量是5个；(8) Constraints，表示约束，Total 4，表示包括目标函数一共4个约束，非线性(Nonlinear)约束0个；(9) Nonzeros，表示非零系数，Total 14，表示包括目标函数和约束条

6、件中变量的非零系数14个，右端常数项不算。实验二：线性规划灵敏度分析1.简述灵敏度分析的步骤。2.某车间有甲、乙两台机床，用于加工3种工件。假设这两台机床的台时数分别为70和80小时，3种工件需要加工的数量分别为30、50和40件。用不同机床加工单位工件所用的台时数和加工费用不同（见下表）。机车类型加工台时（小时/件）加工费用（元/件）台时上限/小时123123甲0.41.11.01391070乙0.51.21.31112880问题：（1）怎样安排加工任务，才能既满足加工数量要求，又使总的费用最少？请建立该问题的数学模型，并用LINGO软件求解（写出程序），并解释状态窗口的含义。（2）三种工件

7、的最低市场定价是多少？（3）如果加工费用增加，是否会改变加工计划？（4）在现有加工能力下，是否可适当增加产品数量？（1）设甲乙机车加工1，2，3工件的数量为xi件（i=1，6）建模如下：编程如下：min=13*x1+9*x2+10*x3+11*x4+12*x5+8*x6;x1+x4=30;x2+x5=50;x3+x6=40;0.4*x1+1.1*x2+x3=70;0.5*x4+1.2*x5+1.3*x6=80;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);关于上图的含义解释如下：1Model(模型) LP(线性规划) Linear progra

8、mming；2State(状态) Global Opt(整体最优解) Global optimal solution；3Objective，目标函数值为1100，由于处于最优解状态，所以这里表示最优值为1100；4Infeasibility 0，不可行性0，表示此时有可行解，否则没有可行解；5Iteration 3，表示迭代了3步求得最优解；6Extended Solver Status，表示扩展的解的状况，主要用于整数规划和非线性规划；7Variables，表示变量，Total 6，表示总决策变量6个，非线性(Nonlinear)变量是0个和整数(Integer)变量是6个；8Constra

9、ints，表示约束，Total 6，表示包括目标函数一共6个约束，非线性(Nonlinear)约束0个；9Nonzeros，表示非零系数，Total 18，表示包括目标函数和约束条件中变量的非零系数18个，右端常数项不算。（2）通过求解模型可得：1号工件只在乙上加工，加工费11元，因此最低价格为11元；2号工件只在甲上加工，加工费9元，因此最低价格为9元；同理3号工件最低价格为8元。（3）对于甲机车而言，当2号工件加工费用改变时，计划才改变； 对于乙机车而言，当1号和3号工件加工费用改变时，计划才改变；（4）甲机车台时上限为70小时，当前利用台时50*1.1=55小时70 ； 乙机车台时上限为

10、80小时，当前利用台时30*0.5+40*1.3=67小时80 ； 由于甲乙机车都还有可利用台时，因此可以增加产品数量。实验三：线性规划对偶问题1.简述原问题与对偶问题的关系。每一个线性规划问题，即原问题，都有一个与之对应的线性规划问题，即对偶问题。原问题与对偶问题的解是对应的，得出一个问题的解，另一个问题的解也就得到了。并且原问题与对偶问题在形式上存在很简单的对应关系： 1.原问题目标函数求极大化,对偶问题则是极小化； 2.原问题目标函数中的系数是对偶问题约束条件中的右端常数,而原问题约束条件中的右端常数则是对偶问题中目标函数的系数； 3.原问题和对偶问题的约束条件的符号方向相反； 4.原问

11、题约束条件系数矩阵转置后即为对偶问题的约束条件的系数矩阵； 5.原问题的约束方程数对应于对偶问题的变量数,而原问题的变量数对应于对偶问题的约束方程数； 6.对偶问题的对偶问题是原问题它们存在着简单的矩阵转置，系数变换的关系。2.简述对偶问题的基本性质。并对互补松弛性定理进行证明。3.简述影子价格的含义。影子价格是根据资源在生产中做出的贡献而做出的估价，这种估价不是资源的市场价格。它反映了在最优经济结构中，在资源得到最优配置的前提下，资源的边际使用价值。单纯形表中松弛变量所对应的检验数的相反数是在该经济结构中的影子价格，也可以说对偶问题的最优解是结构中的影子价格。影子价格越大，说明这种资源越是相

12、对紧缺；影子价格越小，说明这种资源相对不紧缺。如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0。实验四：运输问题1.简述运输问题表上作业法的基本步骤。2. 用LINGO求解6个发点8个收点的最小费用运输问题，产销单位运价如下表：B1B2B3B4B5B6B7B8产量A16267425960A24953858255A35219743351A47673927143A52395726541A65522814352销量3537223241324338编程如下：sets:as/a1.a6/: capacity;bs/b1.b8/: demand;links(as,bs): cost, vol

13、ume;endsetsmin=sum(links: cost*volume);for(bs(J):sum(as(I): volume(I,J)=demand(J);for(as(I):sum(bs(J): volume(I,J)=0;GIN(x(j););FOR(num_l(l):d1(l)=0;d2(l)=0;);共有三级目标，需运行三次该程序。第一次运行时，取p（1）=1，p（2）=p（3）=0,z(1)与z(2)都取较大的值。得：Objective value : 0. , X(1) 16000.00， X(2) 0. 第二次运行时，取p（1）=0，p（2）=1，p（3）=0,z(1)=

14、0，z(2)取较大的值。得：Objective value : 0. , X(1) 0.， X(2) 16000.00 第三次运行时，取p（1）=0，p（2）=0，p（3）=0,z(1)=0，z(2)=0得： X(1) 9000，X(2) 70000， D2(3) 5000，D2(4)3000 则该厂生产A灯具9000套，B灯具7000套，可完成16000套的计划，且完成了销售指标元，生产时间需增加5000 min，包装时间需增加3000 min 。关于上图的含义解释如下：(10) Model(模型) LP(线性规划) Linear programming；(11) State(状态) Glo

15、bal Opt(整体最优解) Global optimal solution；(12) Objective，目标函数值为695.6，由于处于最优解状态，所以这里表示最优值为695.6；(13) Infeasibility 0，不可行性0，表示此时有可行解，否则没有可行解；(14) Iteration 4，表示迭代了4步求得最优解；(15) Extended Solver Status，表示扩展的解的状况，主要用于整数规划和非线性规划；(16) Variables，表示变量，Total 5，表示总决策变量5个，非线性(Nonlinear)变量是0个和整数(Integer)变量是5个；(17) C

16、onstraints，表示约束，Total 4，表示包括目标函数一共4个约束，非线性(Nonlinear)约束0个；(18) Nonzeros，表示非零系数，Total 14，表示包括目标函数和约束条件中变量的非零系数14个，右端常数项不算。实验六：整数规划及指派问题1.简述分支定界法和割平面法的基本原理。分枝定界法将问题分枝为子问题并对这些子问题定界，在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。用割平面法求解整数规划的基本思

17、路是：先不考虑整数约束条件，求松弛问题的最优解，如果获得整数最优解，即为所求，运算停止如果所得到最优解不满足整数约束条件，则在此非整数解的基础上增加新的约束条件重新求解这个新增加的约束条件的作用就是去切割相应松弛问题的可行域，即割去松弛问题的部分非整数解(包括原已得到的非整数最优解)而把所有的整数解都保留下来，故称新增加的约束条件为割平面当经过多次切割后，就会使被切割后保留下来的可行域上有一个坐标均为整数的顶点，它恰好就是所求问题的整数最优解即切割后所对应的松弛问题，与原整数规划问题具有相同的最优解。2. 列出数学模型并用LINGO求解，人员选拔问题：队员号码身高/m位置队员号码身高/m位置1

18、1.92中锋21.90中锋31.88前锋41.86前锋51.85前锋61.83后卫71.80后卫81.78后卫同时，要求出场阵容必须满足以下条件：（1）中锋只能有一个上场；（2）至少有一名后卫；（3）如果1号和4号队员都上场，则6号队员不能上场；（4）2号队员和6号队员必须至少保留一个不出场。如果要选择5个队员上场，总身高最高，请确定出场阵容。用lingo编程如下：MODEL:SETS:team/1.8/:a,x;ENDSETSDATA:a=1.92,1.90,1.88,1.86,1.85,1.83,1.80,1.78;ENDDATAmax=sum(team(i):a(i)*x(i);SUM(

19、team(i):x(i)=5;x(1)+x(2)=1;x(6)+x(7)+x(8)=1;x(1)+x(4)+x(6)=2;x(2)+x(6)=1;FOR(team(i):bin(x(i);END得第1、3、4、5、7位队员被选上，身高总和最大为 1.92 + 1.88 + 1.86 + 1.85 + 1.80 = 9.31（米）3.有一份说明书要分别译成英、日、德、俄四种文字，交给甲乙丙丁四个人去完成。因个人专长不同，他们完成翻译不同种文字所需要的时间（小时）也不同，如下表所示。问应如何分配，使四个人分别完成这四项任务的总时间为最少。请用LINGO软件求解（写出程序），并解释状态窗口的含义。甲

20、乙丙丁英文21097日文154148德文13141611俄文415139编程如下：MODEL:SETS:warehouses/wh1,wh2,wh3,wh4/:capacity;vendors/v1,v2,v3,v4/:demand;links(warehouses,vendors):cost,volume;ENDSETSmin=sum(links:cost*volume);for(vendors(J): sum(warehouses(I):volume(I,J)=demand(J);for(warehouses(I): sum(vendors(J):volume(I,J)=capacity(

21、I);DATA:capacity=1 1 1 1;demand=1 1 1 1;cost= 2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9;ENDDATAEND关于上图的含义解释如下：（1） Model(模型) LP(线性规划) Linear programming；（2） State(状态) Global Opt(整体最优解) Global optimal solution；（3） Objective，目标函数值为28，由于处于最优解状态，所以这里表示最优值为28；（4） Infeasibility 0，不可行性0，表示此时有可行解，否则没有可行解；（5）

22、Iterations 7，表示迭代了7步求得最优解；（6） Extended Solver Status，表示扩展的解的状况，主要用于整数规划和非线性规划；（7） Variables，表示变量，Total 16，表示总决策变量16个，非线性(Nonlinear)变量是0个和整数(Integer)变量是0个；（8） Constraints，表示约束，Total 9，表示包括目标函数一共9个约束，非线性(Nonlinear)约束0个；（9） Nonzeros，表示非零系数，Total 48，表示包括目标函数和约束条件中变量的非零系数48个，右端常数项不算实验七：图与网络分析1.（1）使用狄格斯屈拉

23、算法求最短路（2）请建立该问题的数学模型，并用LINGO软件求解（写出程序），并解释状态窗口的含义。MODEL:sets:cities/1,2,3,4,5,6/;roads(cities, cities)/1,2 1,3 2,3 2,4 3,4 3,5 4,5 4,6 5,6/: w, x;endsetsdata:w = 7 9 1 7 6 6 2 7 6 ;enddatan=size(cities);min=sum(roads: w*x);for(cities(i) | i #ne# 1 #and# i #ne# n:sum(roads(i,j): x(i,j) = sum(roads(j,i): x(j,i);sum(roads(i,j)|i #eq# 1 : x(i,j)=1;END关于上图的含义解释如下：（1） Model(模型) LP(线性规划) Linear programming；（2） State(状态) Global Opt(整体最优解) Global optimal solution；（