课内实验-运筹学-整数规划-第三次
- 格式:doc
- 大小:862.50 KB
- 文档页数:5
运筹学实验报告学院:经济管理学院专业班级:工商11-2班姓名:***学号:************实验一线性规划一实验目的学习WinQSB软件的基本操作,利用Linear Programming功能求解线性规划问题。
掌握线性规划的基本理论与求解方法,重点在于单纯形法的应用以及灵敏度分析方法。
二、实验内容安装WinQSB软件,了解WinQSB软件在Windows环境下的文件管理操作,熟悉软件界面内容,掌握操作命令。
利用Linear Programming功能建立线性模型,输入模型,求解模型,并对求解结果进行简单分析。
三实验步骤1.将WinQSB文件复制到本地硬盘;在WinQSB文件夹中双击setup.exe。
2.指定安装WinQSB软件的目标目录(默认为C:\ WinQSB)。
3.安装过程需要输入用户名和单位名称(任意输入),安装完毕之后,WinQSB菜单自动生成在系统程序中。
4.熟悉WinQSB软件子菜单内容及其功能,掌握操作命令。
5.求解线性规划问题。
启动程序开始→程序→WinQSB→Linear and Integer Programming。
某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、D。
已知产品的规格要求,产品单价,每天能供应的原材料数量及原材料单价分别见下表1和2。
该厂应如何安排生产,使利润收入为最大?表1表2C P H 10010060652535(1)计算过程(1)利用WinQSB软件,根据建立的数据模型,设定完成后建立问题的电子表格;在电子表格中输入各个系数,保存。
如下图:点击菜单栏Solve and Analyze中的Solve the Problem项或者点击工具栏中的图标用单纯形法求解,查看求解得出的结果;(2)点击菜单栏Solve and Analyze中的Solve and Display Steps,查看单纯形法在求解该问题时的具体迭代步骤;点击菜单栏Solve and Analyze中的Graphic Method,用图解法求解,显示可行域。
实验三一、实验目的:1)进一步熟悉 Excel 规划求解工具,掌握 Excel 求解 0-1 整数规划问题;2)进一步熟悉 Matlab 软件,掌握 Matlab 求解 0-1 整数规划问题;3)用 Excel 和 Matlab 求解公司选址 0-1 规划问题。
二、实验器材1)PC机: 20 台。
2)Microsoft Excel 软件(具备规划求解工具模块): 20 用户。
3)Matlab 软件(具备优化工具箱):20 用户。
三、实验原理:公司选址属于 0-1 整数规划问题,通过对问题建立数学模型,根据 Excel 自身特点把数学模型在电子表格中进行清晰的描述,再利用规划求解工具设定相应的约束条件,最终完成对问题的寻优过程,具体可参见;在 Matlab 中,根据 Matlab提供的 0-1 整数规划求解函数,将数学模型转换成 0-1 整数规划求解函数可传递的数值参数,最终实现对问题的寻优求解过程,具体可参见中 bintprog 函数描述和示例。
四、实验内容和步骤:用 Excel 和 Matlab 完成下列公司选址问题。
某销售公司打算通过在武汉或长春设立分公司(也许在两个城市都设分公司)增加市场份额,管理层同时也计划在新设分公司的城市最多建一个配送中心,当然也可以不建配送中心。
经过计算,每种选择对公司收益的净现值列于下表的第四列、第五列中记录了每种选择所需的费用,总的预算费用不得超过20 万元。
决策编号问题决策变量净现值(万元)所需资金(万元)1 是否在长春设分公司x1 18 122 是否在武汉设分公司x2 10 63 是否在长春建配送中心x3 12 104 是否在武汉建配送中心x 4 8 4问:如何决策才能使总的净现值最大建立模型:设=0 表示不建立,=1 表示建立,i=1,2,3,4用z表示预算费用总的净现值。
则目标函数 maxz=18 +10 +12 +8先确立约束不等式:总的预算费用不得超过20 万元;设立的分公司数目大于等于 1;且建立配送中心数目一定要小于分公司数目。
运筹学综合实验报告本次实验中,我们使用了运筹学的方法来解决了一个经典的优化问题,即整数线性规划问题(Integer Linear Programming,简称ILP)。
一、实验目的本次实验的主要目的是熟悉ILP的求解过程,了解ILP在实际问题中的应用,以及掌握使用现代优化软件Gurobi来求解ILP的方法。
二、实验原理1. 整数线性规划问题整数线性规划问题是在所有线性规划问题中的一个非常重要的子集。
它将优化目标函数的线性组合与整数限制相结合。
一个典型的ILP问题可以被描述为:最大化(或最小化)目标函数:\max(\min) \sum_{j=1}^{n}c_j x_j满足如下的约束条件:\sum_{j=1}^{n}a_{ij} x_j \leq b_i,\ i=1,2,\cdots,mx_j \geq 0,\ j=1,2,\cdots,nx_j \in Z,\ j=1,2,\cdots,nx_j表示自变量,c_j表示目标函数中的系数,a_{ij}表示第i个约束条件中x的系数,b_i表示约束条件的右侧常数,m表示约束条件的数量,n表示变量的数量。
最后两个约束条件要求自变量只能是整数。
2. Gurobi优化软件Gurobi是一个商业优化软件,经过多年的发展,已成为当前最流行的数学优化软件之一。
Gurobi支持多种数学优化方法,包括线性规划、非线性规划、混合整数规划、二次规划等。
Gurobi使用了现代算法来实现高效的求解效果,是工业和学术界备受推崇的优化软件。
三、实验内容1. 利用Gurobi求解整数线性规划问题我们使用Gurobi来求解如下的整数线性规划问题:\max\ \ 2x_1 + 3x_2 + 7x_3满足如下的约束条件:x_1 + x_2 + x_3 \leq 6x_1 - x_2 + x_3 \leq 4x_1, x_2, x_3 \in Z,\ x_1 \geq 0,\ x_2 \geq 0,\ x_3 \geq 0我们使用Python代码来实现该问题的求解过程:```pythonimport gurobipy as gbmodel = gb.Model("integer linear programming")# Create variablesx1 = model.addVar(vtype=gb.GRB.INTEGER, name="x1")x2 = model.addVar(vtype=gb.GRB.INTEGER, name="x2")x3 = model.addVar(vtype=gb.GRB.INTEGER, name="x3")# Set objectivemodel.setObjective(2*x1 + 3*x2 + 7*x3, gb.GRB.MAXIMIZE)# Add constraintsmodel.addConstr(x1 + x2 + x3 <= 6)model.addConstr(x1 - x2 + x3 <= 4)# Optimize modelmodel.optimize()# Print resultsprint(f"Maximum value: {model.objVal}")print(f"x1 = {x1.x}")print(f"x2 = {x2.x}")print(f"x3 = {x3.x}")```运行该代码,得到的输出结果为:```Optimize a model with 2 rows, 3 columns and 6 nonzerosVariable types: 0 continuous, 3 integer (0 binary)Coefficient statistics:Matrix range [1e+00, 1e+00]Objective range [2e+00, 7e+00]Bounds range [0e+00, 0e+00]RHS range [4e+00, 6e+00]Found heuristic solution: objective 9.0000000Presolve time: 0.00sPresolved: 2 rows, 3 columns, 6 nonzerosVariable types: 0 continuous, 3 integer (0 binary)Root relaxation: objective 1.500000e+01, 2 iterations, 0.00 secondsNodes | Current Node | Objective Bounds | WorkExpl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time0 0 15.00000 0 1 9.00000 15.00000 66.7% - 0sH 0 0 14.0000000 15.00000 7.14% - 0s0 0 15.00000 0 1 14.00000 15.00000 7.14% - 0sExplored 1 nodes (2 simplex iterations) in 0.03 secondsThread count was 4 (of 4 available processors)Solution count 2: 14 9Optimal solution found (tolerance 1.00e-04)Best objective 1.400000000000e+01, best bound 1.400000000000e+01, gap 0.0000%Maximum value: 14.0x1 = 2.0x2 = 4.0x3 = 0.0```经过Gurobi的求解,我们得到了最大值为14,同时x_1=2, x_2=4, x_3=0时取到最优值。
《运筹学》实验报告指派问题班级:姓名:学号:指导教师:《运筹学》实验报告(一)一.实验目的熟练的掌握整数规划,0-1规划问题的数学模型的建立于求解和数据分析二.实验要求利用EXCEL软件求解整数规划和0-1规划模型三.实验准备Pc486微机、Windows环境、Excel软件四.实验内容及步骤实验内容:某公司面临5项任务,计划派甲、乙、丙、丁、戊分别去做。
由于戊临时被公司派往国外,因此公司只有让甲、乙、丙、丁中的一个人同时担任两项任务,其他三人仍旧单独完成一项任务。
各人完成相应任务时间如下表。
请为公司制定一个总工时最小的指派方案。
实验内容分析:本题中研究的是制定一个总工时最小的工作任务分配方案即本题是一个0-1规划问题。
又本题中是四个员工五个任务的不平衡的分配任务,所以可以有增加虚拟人物的方式来解决不平衡问题也可以直接用抽屉原则来解决不平衡问题。
方法一:(虚拟人物法)建立数学模型:变量:甲员工做A任务为X11,甲员工做B任务为X12,甲员工做C任务为X13,甲员工做D任务为X14,甲员工做E任务为X15,乙员工做A任务为X21,乙员工做B任务为X22,乙员工做C任务为X23,乙员工做D任务为X24,乙员工做E任务为X25,丙员工做A 任务为X31,丙员工做B任务为X32,丙员工做C任务为X33,丙员工做D任务为X34,丙员工做E任务为X35,丁员工做A任务为X41,丁员工做B任务为X42,丁员工做C任务为X43,丁员工做D任务为X44,丁员工做E任务为X45,虚拟员工做A任务为X51,虚拟员工做B任务为X52,虚拟员工做C任务为X53,虚拟员工做D任务为X54 ,虚拟员工做E任务为X55目标:总工时最小的人员安排方法约束:每人(包括虚拟人物)只能做一项任务即决策变量的0-1约束。
规划模型如下:MINZ(x)=25X11+29X12+31X13+42X14+37X15+39X21+38X22+26X23+20X24 +33X25+34X31+27X32+28X33+40X34+32X35+24X41+42X42+36X43+23X44+45X45+24X51+27X52+26X53+20X54+32X55X11+ X21+ X31+ X41+ X51=1X12+ X22+ X32+ X42+ X52=1X13+ X23+ X33+ X34+ X35=1X14+ X24+ X34+ X44+ X45=1X15+ X25+ X35+ X45+ X55=1 s.t. X11+ X12+ X13+ X14+ X15=1X21+ X22+ X23+ X24+ X25=1X31+ X32+ X33+ X34+ X35=1X41+ X42+ X43+ X44+ X45=1X51+ X52+ X53+ X54+ X55=1X ij=0或1(i=0-5,j=0-5)用EXCEL求解上式,过程如下:输入效率矩阵、方案矩阵和约束条件单元格公式:求解参数对话框如图所示:最终结果为:最小总工时131甲做A任务乙做C任务和D任务丙做E任务丁做B任务方法二:(抽屉原则法)建立数学模型:设甲员工做A任务为X11,甲员工做B任务为X12,甲员工做C任务为X13,甲员工做D任务为X14,甲员工做E任务为X15,乙员工做A任务为X21,乙员工做B任务为X22,乙员工做C任务为X23,乙员工做D任务为X24,乙员工做E任务为X25,丙员工做A任务为X31,丙员工做B任务为X32,丙员工做C任务为X33,丙员工做D任务为X34,丙员工做E任务为X35,丁员工做A任务为X41,丁员工做B任务为X42,丁员工做C任务为X43,丁员工做D任务为X44,丁员工做E任务为X45。
一、实验背景运筹学是一门应用数学的分支,它运用数学模型和算法来解决各种优化问题。
随着现代科技的发展,运筹学在各个领域的应用越来越广泛,如生产管理、物流运输、资源分配等。
为了提高学生运用运筹学知识解决实际问题的能力,我们开展了运筹学实训实验。
二、实验目的1. 熟悉运筹学的基本概念和常用方法;2. 掌握线性规划、整数规划、运输问题、目标规划等运筹学模型;3. 学会运用计算机软件解决实际问题;4. 培养学生的团队合作精神和创新意识。
三、实验内容本次实验主要包括以下内容:1. 线性规划:以生产计划问题为例,建立数学模型,并运用Excel规划求解器求解最优解。
2. 整数规划:以人员排班问题为例,建立数学模型,并运用Lingo软件求解最优解。
3. 运输问题:以物流配送问题为例,建立数学模型,并运用Lingo软件求解最优解。
4. 目标规划:以投资组合问题为例,建立数学模型,并运用Lingo软件求解最优解。
四、实验步骤1. 线性规划实验(1)问题分析:某企业需要生产甲、乙两种产品,已知生产甲、乙两种产品所需的原料、劳动力及设备等资源消耗量,以及产品的售价和利润。
(2)模型建立:根据问题分析,建立线性规划模型,目标函数为最大化利润,约束条件为资源消耗量不超过限制。
(3)求解:运用Excel规划求解器求解最优解。
2. 整数规划实验(1)问题分析:某公司需要安排员工值班,要求每天至少有3名员工值班,且员工值班时间不能超过一周。
(2)模型建立:根据问题分析,建立整数规划模型,目标函数为最小化员工值班成本,约束条件为员工值班时间不超过限制。
(3)求解:运用Lingo软件求解最优解。
3. 运输问题实验(1)问题分析:某物流公司需要将货物从A、B两个仓库运送到C、D两个销售点,已知各仓库的货物量、各销售点的需求量以及运输成本。
(2)模型建立:根据问题分析,建立运输问题模型,目标函数为最小化运输成本,约束条件为各仓库的货物量不超过需求量。
《运筹学》实验二整数规划问题(学生版)
运筹学实验二——整数规划
1、求以下整数规划问题的最优解(1)
(2)
≥≥+≤++=为整数
212121
2121,0,205462..x x x x x x x x t s x x MaxZ 2、求以下0,1规划问题的最优解
=≤+≤
+≤++≤-++-=1
0,,6
43
4422..5233
213
22
13213
21321或x x x x
x x x x x x x x x t s x x x MaxZ
3、某校组织4人篮球队,要从6人名单中选择总身高最高的首发阵容。
队员名单如表2-1所示。
表2-1
出场阵容必须满足下列约束条件:(1)至少有一个后卫;
(2)2号与5号队员中必须保留一个不出场;(3)中锋只能出一个;
(4)如果2号与4号两个人都出场,则6号不能出场。
≥≤+≤++=且取整数0,702075679..90402
1212121x x x x x x t s x x MaxZ
要求:(1)写出这个问题的整数规划模型;
(2)用WinQSB软件求出最优阵容。
4、有4个工人。
要指派他们分别完成4项工作。
每人做各项工作所消耗的时间(h) 如下表,问如何分派工作,使总的消耗时间最少?。
《运筹学》上机实验报告三(整数线性规划)实验名称:利用Gomory割平面法编程求解整数规划问题;利用分枝定界法编程求解整数规划问题实验目的:1. 学会软件lindo/lingo的安装及基本的操作;2. 对实际问题进行数学建模,并学会用数学软件Matlab或运筹软件Lindo/Lingo 对问题进行求解。
实验内容:1.用lindo/lingo 计算(学会输入、查看、运行、结果分析)max z = 20x1 + 10x25x1 + 4x2 ≤ 242x1 + 5x2 ≤ 13x1,x2 ≥ 0x1,x2取整数2.(指派问题)现在有A 、B、C、D、E五种任务,要交给甲、乙、丙、丁、戊去完成,每人完成一种任务,每个人完成每种任务所需要的时间如下表。
问应该如何安排个人完成哪项任务可使总的花费的时间最少?(建立数学模型,用数学软件求解该问题,写出结果并对运行结果加以说明)A B C D E任务人甲127979乙89666丙717121412丁15146610戊41071063.选址问题某跨国公司准备在某国建三个加工厂,现有8个城市供选择,每个城市需要的投资分别为1200万美元、1400万美元、800万美元、900万美元、1000万美元、1050万美元、950万美元、150万美元,但投资总额不能超过3400万美元,形成生产能力分别为100万台、120万台、80万台、85万台、95万台、100万台、90万台、130万台,由于需求的原因,要求:城市1和城市3最多选1个,城市3、城市4、城市5最多选两个,城市6和城市7最少选1个,问选择哪些城市建厂,才能使总的生产能力最大?(建立数学模型,用数学软件求解该问题,写出结果并对运行结果加以说明)整数变量定义LinDo一般整数变量:GIN <Variable>0-1整数变量: INT <Variable>LinGo一般整数变量: @GIN( variable_name);0-1整数变量:@BIN( variable_name);例如(1)Lindo运算程序max 3 x1+5 x2+4 x3subject to2 x1+3 x2<=15002 x2+4 x3<=8003 x1+2 x2 +5 x3<=2000endgin x1gin x3(2) max z = 3x1 - 2x2 + 5x3x1 + 2x2 - x3 ≤ 2x1 + 4x2 + x3 ≤ 4x1 + x2 ≤ 34x2 + x3 < 6x1,x2,x3 = 0或1lingo程序:max =3*x1 – 2*x2 + 5*x3;x1 + 2*x2 - x3 <= 2;x1 + 4*x2 + x3 <= 4;x1 + x2 <= 3 ; 4*x2 + x3< 6; @bin(x1);@bin(x2);@bin(x3);。
Max z=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10≤750
x1+x2+x3≤2
x4+x5≥1
x6+x7≥1
x8+x9+x10≥2
xj≥0
xj=0或1
二、EXCEL求解
(1)建立整数规划问题的电子表格
(2)对实际建立个数这一列添加函数SUMPRODUCT
(3)实际投资额添加函数SUMPRODUCT
(4)总利润添加函数SUMPRODUCT
(5)加载宏添加规划求解项,目标单元格为总利润N15,可变单元格为“是否选择”B13:K13,约束总投资小于750万元,A1 ,A2 ,A3 三个点至多选择两个;A4 ,A5 两个点中至少选一个;A6 ,A7 两个点中至少选一个;A8 ,A9 ,A10 三个点中至少选两个,并且xj为二进制。
(6)规划求解的结果如下:
EXCEL的最大年利润为255万元,选择A1,A4,A6,A8,A9,A10这六个位置建立销售中心可以使年利润最大化。
三、LINGO求解
(1)在主框架窗口输入约束条件及求最大值的函数,添加@bin(变量)使xj 为二进制变量。
(2)求解后得到与EXCEL一致结果
四、结果分析
用整数规划问题解决生活中关于选取不同地区建立销售中心使年利润最大化的问题,十分具有现实意义。
既考虑到了投资问题,还考虑到了不同地区的销售中心个数的分配。
可见运筹学对现实生活中的安排生产,分配资源具有重要的作用。
在规划求解的过程中,可以很方便的解决生产中的问题,可以节约运费、成本以及工人工资。
使得企业利用最少的资源、最简便的方法,达到最佳预期效果,收益最大化。
就本题而言,采用0-1型整数规划,对企业建立销售中心这一问题制定了科学合理的方案。
即在当X1=1,X2=0,X3=1,X4=0,X5=1,X6=1,X7=0,X8=1,X9=1,X10=0时,该规划取得最大利润,且最大利润为255万元。
在以后的学习及工作中,我们都能利用运筹学统筹规划,使自己的工作效率达到最大化。
成绩评定:
该生对待本次实验的态度□认真□良好□一般□比较差。
本次实验的过程情况□很好□较好□一般□比较差。