割平面法求解整数规划问题实验报告

运筹学与最优化MATLAB 编程

实验报告

割平面法求解整数规划问题

一、 引言：

通过对MATLAB 实践设计的学习，学会使用MATLAB 解决现实生活中的问题。该设计是在MATLAB 程序设计语言的基础上，对实际问题建立数学模型并设计程序，使用割平面法解决一个整数规划问题。经实验，该算法可成功运行并求解出最优整数解。 二、 算法说明：

割平面法有许多种类型，本次设计的原理是依据Gomory 的割平面法。Gomory 割平面法首先求解非整数约束的线性规划，再选择一个不是整数的基变量，定义新的约束，增加到原来的约束中，新的约束缩小了可行域，但是保留了原问题的全部整数可行解。

算法具体设计步骤如下：

1、首先，求解原整数规划对应的线性规划

,*)(min x c x f =???≥≤0

..x b

Ax t s ，设最优解为x*。

2、如果最优解的分量均为整数，则x*为原整数规划的最优解；否则任选一个x*中不为整数的分量，设其对应的基变量为x p ，定义包含

这个基变量的切割约束方程con j

j ij p b x r x =+∑，其中x p 为非基变量。

3、令][ij ij ij r r r -=，][con con con b b b -=，其中[]为高斯函数符号，表示不大于某数的最大整数。将切割约束方程变换为

∑∑-=-+j

j

ij con con j

j ij p x r b b x r x ][][，由于0

1<-∑j

j ij con x r b ，因为自变量为整数，则∑-j

j ij con x r b 也为整数，所以进一

步有0≤-∑j

j ij con x r b 。

4、将切割方程加入约束方程中，用对偶单纯形法求解线性规划

??

?

?

???≥≤-≤=∑00..,*)(min x x r b b Ax t s x c x f j j ij con ，然后在转入步骤2进行求解，直到

求出最优整数解停止迭代。 三、 程序实现：

程序设计流程图如图1，具体设计代码(见附录)。

图1

四、 算例分析：

已知AM 工厂是一个拥有四个车间的玩具生产厂商，该厂商今年新设计出A 、B 、C

、D 、E 、F 六种玩具模型，根据以前的生产情况及市场调查预测，得知生产每单位产品所需的工时、每个车间在一季度的工时上限以及产品的预测价格，如下表所示。问：每种设计产品在这个季度各应生产多少，才能使AM 工厂这个季度的生产总值达到最大？

整数规划割平面法

割平面法 求解整数规划问题： Max Z=3x 1+2x 2 2x 1+3x 2?14 4x 1+2x 2?18 x 1,x 2?0，且为整数 解：首先，将原问题的数学模型标准化，这里标准化有两层含义：（1）将不等式转化为等式约束，（2）将整数规划中所有非整数系数全部转化为整数，以便于构造切割平面。从而有： Max Z=3x 1+2x 2 2x 1+3x 2+x 3=14 2x 1+x 2+x 4=9 x 1,x 2?0，且为整数 利用单纯形法求解，得到最优单纯形表，见表1： 表1

最优解为：x 1=13/4, x 2=5/2, Z=59/4 根据上表，写出非整数规划的约束方程，如： x 2+1/2x 3-1/2x 4=5/2 (1) 将该方程中所有变量的系数及右端常数项均改写成“整数与非负真分数之和”的形式，即： (1+0)x 2+(0+1/2)x 3+(-1+1/2)x 4=2+1/2 把整数及带有整数系数的变量移到方程左边，分数及带有分数系数的变量称到方程右边，得： x 2 - x 4-2 =1/2-(1/2x 3+1/2x 4) (2) 由于原数学模型已经“标准化”，因此，在整数最优解中，x 2和x 4也必须取整数值，所以(2)式左端必为整数或零，因而其右端也必须是整数。又因为x 3,x 4?0，所以必有：

由于(2)式右端必为整数，于是有： 1/2-(1/2x 3+1/2x 4)?0 (3) 或 x 3+x 4?1 (4) 这就是考虑整数约束的一个割平面约束方程，它是用非基变量表示的，如果用基变量来表示割平面约束方程，则有： 2x 1+2x 2?11 (5) 从图1中可以看出，(5)式所表示的割平面约束仅割去线性规划可行域中不包含整数可行解的部分区域，使点E(3.5，2)成为可行域的一个极点。 图1 在(3)式中加入松弛变量x 5，得： -1/2x 3-1/2x 4+x 5=-1/2 (6) 将(6)式增添到问题的约束条件中，得到新的整数规划问题： Max Z=3x 1+2x 2 2x 1+3x 2+x 3=14 2x 1+x 2+x 4=9

整数规划实验报告例文

整数规划实验报告例文 篇一：实验报告整数规划 一、实验名称：整数规划问题和动态规划问题 二、实验目的： 熟练使用Spreadsheet建立整数规划、动态规划模型，利用excel建立数学模型，掌握求解过程，并能对实验结果进行分析及评价 三、实验设备 计算机、Excel 四、实验内容 （一）整数规划 1、0-1整数规划 其中，D11=F2;D12=F3;D13=F4;D14=F5; B11=SUMPRODUCT($B$9:$E$9,B2:E2); B12=SUMPRODUCT($B$9:$E$9,B3:E3); B13=SUMPRODUCT($B$9:$E$9,B4:E4); B14=SUMPRODUCT($B$9:$E$9,B5:E5); H8==SUMPRODUCT($B$9:$E$9,B6:E6); 用规划求解工具求解：目标单元格为$H$8,求最大值，可变单元格为$B$9:$E$9，约束条件为 $B$11:$B$14<=$D$11:$D$14;$B$9:$E$9=二进制。在【选项】

果，实现最大利润为140. 2、整数规划 其中，D11=D2;D12=D3; B11=SUMPRODUCT($B$8:$C$8,B2:C2);B12=SUMPRODUCT($B$8:$ C$8,B3:C3); F7=SUMPRODUCT($B$8:$C$8,B4:C4); 用规划求解工具求解：设置目标单元格为F7,求最大值，可变单元格为$B$8:$C$8,约束条件为 $B$11:$B$12<=$D$11:$D$12;$B$8:$C$8=整数。在【选项】菜单中选择“采用线性模型”“假定非负”。即可进行求解得结果，实现最大利润为14. 3、指派问题 人数跟任务数相等： 其中， F11=SUM(B11:E11);F12=SUM(B12:E12);F13=SUM(B13:E13);F14=SU M(B14:E14); B15=SUM(B11:B14);C15=SUM(B11:B14);D15=SUM(B11:B14);E15=SU M(B11:B14); H11,H12,H13,H14,B17,C17,D17,E17单元格值均设为1. 用规划求解工具求解：设置目标单元格为$B$8,求最小值，可变单元格为$B$11:$E$14,约束条件为$B$11:$E$14=二进制； $B$15:$E$15=$B$17:$E$17;$F$11:$F$14=$H$11:$H$14. 在【选

第五章 整数规划练习题答案教程文件

第五章整数规划练习 题答案

精品资料 仅供学习与交流，如有侵权请联系网站删除 谢谢2 第五章 整数规划练习题答案 一. 判断下列说法是否正确 1. 用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是 该问题目标函数值的下界。( ) 2. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。( ) 3. 用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。( ) 4. 指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。( ) 二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问 应如何分配这五项工作，并求得最大产值。 答案： 设原矩阵为A ，因求极大问题，令B=[M-a ij ]，其中M=Max {a ij }=10，则： 16425105 3140 42132 510425 1042 4003B 13752102641015406241515130450203057470574704646111 -???? ?? ? ? ? ? ? ? ? ? ? =→→- ? ? ?- ? ? ? ? ? ??????? --- m 4n 5 l m 44213421324324315415452352346464646=<===???? ? ??? ? ? ? ?→→????→?? ? ? ?? ? ? ? ???????0 3102340031 15406020303535?? ? ? ? ? ? ??? 31234311546233535??? ?? ? ?→ ?? ? ??? m=5=n ，得最优解。解矩阵*00 01000100X 00 0010100010000?? ? ? ?= ? ? ??? 。

割平面法

题目：割平面法及其数值实现 院系：数理科学与工程学院应用数学系 专业：数学与应用数学 姓名学号：*** 1****** *** 1****** *** 1****** *** 1****** 指导教师：张世涛 日期：2015 年 6 月11 日

整数规划与线性规划有着密不可分的关系，它的一些基本算法的设计都是从相应的线性规划的最优解出发的。整数规划问题与我们的实际生活有着密切的联系，如合成下料问题、建厂问题、背包问题、投资决策问题、旅行商问题、生产顺序表问题等都是求解整数模型中的著名问题。所以要想掌握生活中这些解决问题的方法，研究整数规划是必然的路径。用于解决整数规划的方法主要有割平面法，分支定界法，小规模0-1规划问题的解法，指派问题和匈牙利法。本文重要对整数规划中经常用的割平面法加以介绍及使用Matlab 软件对其数值实现。 割平面法从线性规划问题着手,在利用单纯型法的时候,当约束矩阵中出现分数,给出一种"化分为整"的方法。然后在割平面方法来解决整数线性规划的理论基础上,把"化分为整"的方法进行到底，直到求解出最有整数解。 关键词：最优化；整数规划；割平面法；数值实现；最优解；Matlab软件。 Abstract The integer programming are closely related to the linear programming. Some of the basic algorithms of the former are designed from the optimal solution of the corresponding linear programming. What’s more, our daily life has a close relationship with it as well, such as synthesis problem, plant problem, knapsack problem, investment decision problem, traveling salesman problem and production sequence table problems. They are famous questions in solving integer model. So, to study the integer programming is the inevitable way to master the methods of solving these problems in life. The methods used in solving the integer programming include cutting plane method, branch and bound method, and solving the problem of small-scale 0-1 programming, assignment problem and Hungarian method. In this paper, we introduce the cutting plane method and use Matlab to get its numerical implementation in the integer programming. Cutting plane method, giving us a "integrated" method when we meet the constraint matrix scores in the use of simplex method, starts from the linear programming problem. Then, based on the theory of cutting plane method to solve the integer linear programming, we use “integrated” method until the most integer solution is solved. Keywords:Optimization; Integer programming; Cutting plane method; Numerical implementation; Optimal solution; Matlab software.

初中物理实验报告单完整版86599

初中物理实验报告单 年级：八年级姓名：日期：地点：物理实验室 实验名称：探究平面镜成像的特点 一、实验目的 观察平面镜成像的情况，找出成像的特点。 二、实验仪器和器材. 同样大小的蜡烛一对，平板玻璃一块，方座支架(或玻璃板支架)，白纸- 张，三角板一对，刻度尺一把。 三、实验原理： 光的反射规律 四、实验步骤或内容： (1)检查器材。 (2)在桌上铺上白纸，在白纸上竖直的放上平板玻璃，在纸上记录玻璃板的位置。 (3)把点燃的蜡烛放在玻璃板前。 (4)移动未点燃的蜡烛，在玻璃板后让它跟点燃的蜡烛的像重合。 (5)观察两根蜡烛的位置、像与物的大小并记录。 (6)移动点燃的蜡烛，重复实验步骤(4)、( 5)两次。 (6)找出平面镜成像的特点及像的位置跟物体和平面镜的位置的关系。 (7)整理器材、摆放整齐。 五、实验记录与结论 1?记录数据

2.实验结论 (1)平面镜成像的大小与物体的大小相 等。 (2)像到平面镜的距离与物体 到平面镜的距离相等。 初中物理实验报告单 年级：八年级姓名：日期 1、15地点：物理实验室 实验名称：探究凸透镜成像的特点 一、实验目的 探究凸透镜成放大和缩小实像的条件。 二、实验仪器和器材. 光具座，标明焦距的凸透镜，光屏，蜡烛，火柴，废物缸。 三、实验原理： 凸透镜成像的规律 四、实验步骤或内容： (1)检查器材，了解凸透镜焦距，并记录。 (2)把凸透镜、光屏安装在光具座上，位置基本正确。将点燃的蜡烛，安装在光具座上，通过调节，使透镜、光屏和烛焰中心大致在同一高度。 (3)找出2倍焦距点，移动物体到2倍焦距以外某处，再移动光屏直到屏幕上成倒立、缩小的、清晰的实像时为止，记下此时对应的物距 （4）找出2倍焦距点，移动物体到2倍焦距以内且大于1倍焦距某处，再移动光屏直到屏幕上成倒立、放大的、清晰的实像时为止，记下此时对应的物1。

应用LINDO软件求解整数规划

2012——2013学年第一学期 合肥学院数理系 实验报告 课程名称：运筹学 实验项目：应用LINDO软件求解整数规划 实验类别：综合性□设计性□√验证性□ 专业班级： 10级数学与应用数学（1）班 姓名：汪勤学号： 1007021004 实验地点： 35-612 实验时间： 2012-11-29 指导教师：管梅老师成绩：

一.实验目的 1、熟悉LINDO软件的求解整数规划功能。 2、学习应用LINGO软件求解整数规划问题。 3、熟练掌握LINGO软件的操作。 二.实验内容 1、某班有男同学30人,女同学20人,星期天准备去植树。根据 经验,一天中,男同学平均每人挖坑20个,或栽树30棵,或给 25棵树浇水,女同学平均每人挖坑10个,或栽树20棵,或给 15棵树浇水。问应怎样安排,才能使植树(包括挖坑、栽树、 浇水)最多。建立该问题的数学模型，并求其解。 2、求解线性规划： 12 12 12 2 12 max2 2512 28 .. 010 , z x x x x x x s t x x x =+ +≥ ? ?+≤ ? ? ≤≤ ? ??为整数 3、在高校篮球联赛中,我校男子篮球队要从８名队员中选择平均身高最高的出场阵容,队员的号码、身高及擅长的位置如下表： 同时，要求出场阵容满足以下条件：

⑴ 中锋最多只能上场一个。 ⑵ 至少有一名后卫 。 ⑶ 如果１号队员和４号队员都上场，则６号队员不能出场 ⑷ ２号队员和６号队员必须保留一个不出场。 问应当选择哪5名队员上场,才能使出场队员平均身高最高? 试写出上述问题的数学模型，并求解。 三. 模型建立 1、()36 12345625143625max 2515302030202010..2515302001,...,6i z x x x x x x x x x x x x s t x x x x x i =+++≤??++≤??+≤+??+≤+?≥=??且为整数 2、12 1212212max 2251228..010,z x x x x x x s t x x x =++≥??+≤??≤≤???为整数 3、 ()()123456781267814626811max 1.92 1.9 1.88 1.86 1.85 1.83 1.8 1.7851 121..5011,2,...8j j j z x x x x x x x x x x x x x x x x x x s t x x j = = ++++++++≤??++≥??++≤?+≤? ??=??==?∑或 四. 模型求解（含经调试后正确的源程序）

整数规划(割平面法)

割平面法 求解整数规划问题： Max Z=3x1+2x2 2x1+3x2?14 4x1+2x2?18 x1,x2?0，且为整数 解：首先，将原问题的数学模型标准化，这里标准化有两层含义：（1）将不等式转化为等式约束，（2）将整数规划中所有非整数系数全部转化为整数，以便于构造切割平面。从而有：Max Z=3x1+2x2 2x1+3x2+x3=14 2x1+x2+x4=9 x1,x2?0，且为整数 利用单纯形法求解，得到最优单纯形表，见表1： 表1

最优解为：x1=13/4, x2=5/2, Z=59/4 根据上表，写出非整数规划的约束方程，如：x2+1/2x3-1/2x4=5/2 (1) 将该方程中所有变量的系数及右端常数项均改写成“整数与非负真分数之和”的形式，即：(1+0)x2+(0+1/2)x3+(-1+1/2)x4=2+1/2 把整数及带有整数系数的变量移到方程左边，分数及带有分数系数的变量称到方程右边，得：x2 - x4-2 =1/2-(1/2x3+1/2x4) (2) 由于原数学模型已经“标准化”，因此，在整数最优解中，x2和x4也必须取整数值，所以(2)式左端必为整数或零，因而其右端也必须是整数。又因为x3,x4?0，所以必有： 1/2-(1/2x3+1/2x4)<1 由于(2)式右端必为整数，于是有： 1/2-(1/2x3+1/2x4)?0 (3) 或 x3+x4?1 (4) 这就是考虑整数约束的一个割平面约束方程，它是用非基变量表示的，如果用基变量来表示割平面约束方程，则有： 2x1+2x2?11 (5)

从图1中可以看出，(5)式所表示的割平面约束仅割去线性规划可行域中不包含整数可行解的部 分区域，使点E，2)成为可行域的一个极点。 图1 在(3)式中加入松弛变量x5，得： -1/2x3-1/2x4+x5=-1/2 (6) 将(6)式增添到问题的约束条件中，得到新的整数规划问题： Max Z=3x1+2x2 2x1+3x2+x3=14 2x1+x2+x4=9 -1/2x3-1/2x4+x5=-1/2 x i?0，且为整数，i=1,2,…,5 该问题的求解可以在表1中加入(6)式，然后运用对偶单纯形法求出最优解。具体计算过程见表2： 表2

2017--2018物理实验报告单

年级：八年级姓名：日期：地点：物理实验室 实验名称：用刻度尺测量长度 一、实验目的 练习正确使用毫米刻度尺测量长度，正确记录测量结果；练习估测到分度值的下一位。 二、实验仪器和器材． 毫米刻度尺，三角板（2块），物理课本，硬币，约30cm长细铜丝，铅笔。 三、实验原理：． 长度测量的一些特殊方法。 四、实验步骤或内容：． 1.检查器材,观察刻度尺的量程和分度值，零刻度线是否磨损。 2.用毫米刻度尺测物理课本的长和宽，记录要求估读到分度值的下一位。 3.用毫米刻度尺和三角板测硬币的直径，记录要求同上。 4.测细铜丝直径，记录要求同上。 5.整理器材。 五、实验记录与结论 1.刻度尺的量程 mm，刻度尺的分度值 mm，零刻线是否磨损。 2.记录数据： 物理课本长 mm，宽 mm。硬币的直径 mm。细铜丝的线圈长度 mm，线圈圈数，细铜丝的直径 mm。

固体熔化时温度的变化规律 实验目的： 实验器材： 实验设计： 一、提出问题: 二、猜想或假设： 三、进行实验： （1）把装有海波的试管（高度约3cm）放在盛有热水（稍低于熔点，海波的熔点是48℃）的大烧杯里。试管内装有温度计和搅拌器（玻璃棒），随时搅拌海波，并每半分钟记录一次温度。 （2）等海波的温度接近熔点时，稍减慢加热速度。注意观察海波的变化：试管壁开始→海波逐渐温度海波全部熔化后温度。 实验现象： （1）开始加热时，海波物态，温度计示数逐渐 （2）在一定的海波开始融化，熔化过程中热，但温度计示数，海波处于态。 （3）当海波全部熔化完毕，继续加热，温度计示数。 实验结论：

水的沸腾 实验目的： 实验器材： 实验步骤： ①在烧杯里放入适量，将烧杯放在石棉网上，然后把插入 水里。 ②把酒精灯点着，给烧杯加热。 ③边观察边记录。 ④做好实验后，把器材整理好。 观察记录： ①水温在60℃以下时，随着水温不断升高，杯底上气泡，有少量 气泡。 ②水温在60℃～90℃之间时，杯底气泡逐渐减少，气泡上升逐渐。 ③在90℃～100℃之间时，小气泡上升越来越。 ④水时，大量气泡迅速上升，温度在不变。 ⑤移走酒精灯，停止。 实验结论： ①沸腾是在液体和同时进行的现象。 ②水在沸腾时，温度。

数学建模实验报告3 线性规划与整数规划、

数学建模与实验课程实验报告 实验名称三、线性规划与整数规划实验地点日期2014-10-28 姓名班级学号成绩 【实验目的及意义】 [1] 学习最优化技术和基本原理，了解最优化问题的分类； [2] 掌握规划的建模技巧和求解方法； [3] 学习灵敏度分析问题的思维方法； [4] 熟悉MATLAB软件求解规划模型的基本命令； [5] 通过范例学习，熟悉建立规划模型的基本要素和求解方法。 通过该实验的学习，使学生掌握最优化技术，认识面对什么样的实际问题，提出假设和 建立优化模型，并且使学生学会使用MATLAB、Lingo软件进行规划模型求解的基本命令， 并进行灵敏度分析。解决现实生活中的最优化问题是本科生学习阶段中一门重要的课程，因 此，本实验对学生的学习尤为重要。 【实验要求与任务】 根据实验内容和步骤，完成以下实验，要求写出实验报告（符号说明—模型的建立—模型 的求解（程序）—结论） A组 高校资金投资问题 高校现有一笔资金100万元，现有4个投资项目可供投资。 项目A：从第一年到底四年年初需要投资，并于次年年末回收本利115%。 项目B：从第三年年初需要投资，并于第5年末才回收本利135%，但是规定最大投资总 额不超过40万元。 项目C：从第二年年初需要投资，并于第5年末才回收本利M%，但是规定最大投资总 额不超过30万元。(其中M为你学号的后三位+10) 项目D：五年内每年年初可以买公债，并于当年年末归还，并可获得6%的利息。 试为该校确定投资方案，使得第5年末他拥有的资金本利总额最大。 该校在第3年有个校庆，学校准备拿出8万元来筹办，又应该如何安排投资方案，使得 第5年末他拥有的资金本利总额最大。 B组题 1)最短路问题, 图1中弧上的数字为相邻2点之间的路程，求从1到7的最短路。 图1 图 2 r为你的学号后2位+10 其中 1 2)最大车流量, 图1中弧上的数字为相邻2点之间每小时的最大车流量。求每小时1到7最大

平面镜成像实验

探究平面镜成像特点 1.实验目得:探究平面镜成像特点。 2.实验器材:玻璃板(作平面镜)、2只大小相同得蜡烛、刻度尺、白纸 其它:笔、火柴 3.实验步骤 (1)将点燃得蜡烛A,放在玻璃板得一侧,在A一侧能观察到玻璃板另一侧A得像A′; 探究像与物得大小关系: (2)拿着另一只未点燃得蜡烛B在玻璃板另一侧来回移动,直到瞧上去B与A′重合,即B瞧上去好像被点燃了。此时,B得位置就就是像A′得位置。 ——等大 探究像与物到玻璃板得距离关系:

(3)用刻度尺量出A、B分别到镜面得距离,相等。 ——等距 记录数据: 探究平面镜成得像就是实像还就是虚像: (4)在A′一侧放一张白纸作屏幕,眼睛直接观察白纸,则瞧不到A得像A′,说明:平面镜成虚像。(将手放在A′处,感觉不烫,说明:平面镜成虚像。) 4、实验结论:平面镜成像得特点 (1)平面镜所成得像就是虚像; (2)像与物体得大小相等; (3)像与物体到平面镜得距离相等; (4)像与物体得连线与镜面垂直。 (2)(3)(4)对称 虚像:不就是实际光线会聚而成,能瞧见,但不能在屏幕上呈现得像。 注意事项:

1、选择玻璃板代替平面镜得目得就是:物体一侧能瞧到物体得像,同时还能瞧到代替物体得另 一个物体,便于确定像得位置。 2、试验要求玻璃板与桌面垂直。 3、实验时将光屏放在未点燃蜡烛得位置,从玻璃板上方瞧光屏,光屏上瞧不到像,说明平面镜 成得就是虚像。 4、实验中选择厚玻璃还就是薄玻璃？选择较薄得玻璃;因为厚玻璃板得两个面都可以当作反 射面,会出现两个像,影响到实验效果。 考试分析: 考情分析 考查内容2009年2010年2013年2014年2015年2016年二模题号分值题号分值题号分值题号分值题号分值题号分值平面镜成像得 规律以及探究 18 3 20 3 23 1 24 2 17 3 24 3 平面镜成像得 实验 说明题目一般会以作图、简单实验题得形式出现,一般比较简单,分值在3分左右。 平面镜成像主要就就是考察平面镜成像得特点以及实验,要熟练掌握平面镜成像得特点以及小结 实验步骤,明确具体实验步骤得目得。 练习: 1.某同学做“平面镜成像得特点”实验时,将一块玻璃板竖直架在一把直尺得上面,再取两段等 长得蜡烛A与B一前一后竖放在直尺上,点燃玻璃板前得蜡烛A,用眼睛进行观察,如右图所 示。在此实验中: (1)两段等长得蜡烛就是为了比较像与物得______关系; (2)直尺得作用就是便于比较像与物____________________关系; (3)移去蜡烛B,并在其所在位置上放一光屏,则光屏上_______接收到蜡烛 A得烛焰得像(填“能”或“不能”)。这说明平面镜成得就是_____像。(选填 “虚”或“实”)。 答案:大小;到平面镜距离;不能;虚。

第五章 整数规划练习题答案

第五章 整数规划练习题答案 一. 判断下列说法是否正确 1. 用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是 该问题目标函数值的下界。() 2. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。() 3. 用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。() 4. 指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。() 二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问 应如何分配这五项工作，并求得最大产值。 工作 工人 A & B C D E 甲 9 4 6 8 5 \ 乙 8 5 9 10 6 丙 9 7 3 ' 5 8 丁 4 8 6 9 5 戊 10 ； 5 3 6 3 答案： 设原矩阵为A ，因求极大问题，令B=[M-a ij ]，其中M=Max {a ij }=10，则： 16425105 3140 42 13251042510424003B 1 3752102 64 10 154062415151 3045 020305 7470574704646111-?????? ? ? ? ? ? ? ? ? ? =→→- ? ? ?- ? ? ? ? ? ??????? --- m 4n 5l m 4 4 21342132432431541545235234 6 4 64 6 4 6=<===? ??? ? ??? ? ? ? ?→→????→?? ? ??? ? ? ? ???? ? ? ? 031023 4003115406020303535?? ? ? ? ? ? ?? ? 31234311546233 5 3 5? ?? ?? ? ?→ ?? ? ?? ? m=5=n ，得最优解。解矩阵*0001000100X 0000101 00010000?? ? ? ?= ? ? ??? 。

平面镜成像实验报告单

平面镜成像实验报告单 姓名班级 一、实验目的： 观察平面镜成像的特点。 二、实验器材： 棋子薄玻璃板（茶色）刻度尺格子纸（单位一CM） 三、实验方法：（科学探究七步骤） 提出问题→猜想假设→制定计划与设计实验→进行实验与收集数据→分析与论证→评估→交流合作 四、实验过程 1、检查实验器材是否齐全完好。 2、将白纸对折，画出玻璃板的位置。将白纸平铺在桌面上，放好玻璃板，注意将物体所在的玻璃板一面对齐所画的线上。 3、把物体放在玻璃板前某个位置。观察像的正倒。再取一光屏放到像的位置，绕过平面镜直接观察光屏，观察像的虚实。 4、将另一个相同的物体放到玻璃板后不停移动，直至和像重合，观察物像的大小关系。 5、在物体与像的同一位置用笔做上记号。再重复实验两次。并且观察物体离平面镜的距离是否影响像的大小。 6、取下物体和玻璃板，用笔连接每次实验中物与像的记号，观察物象连线与玻璃板的位置关系。再用刻度尺分别测量（注意估读）物与像到玻璃板的距离。将以上数据记在表格中。 7、整理实验器材，完成实验报告，总结规律，交流讨论。 五、总结规律： 平面镜成、的像；物体与像的连线与平面镜。 六、交流讨论： 1、实验时为什么用半透明的玻璃板代替生活中的镜子？ 2、实验中玻璃板应如何放置？如何验证是否放好？ 3、实验中光屏的作用是； 实验中用另一个相同的物体是为了比较物象的； 4、物体远离或靠近平面镜，像的位置如何变化？ 物体远离或靠近平面镜，像的大小如何变化？ 5、像的移动速度与物体的移动速度谁快谁慢？ 6、若将实验中的白纸换成带有小方格的纸有什么好处？ 7、本实验用三角方块代替蜡烛有何优点和缺点？ 七、你对本次实验还有什么疑惑或改进方法？

§3.2 Gomory 割平面法

§3.2 G o m o r y 割平面法 1、G o m o r y 割平面法的基本思想 ??? ?? ??≥=为整数向量x x b Ax t s x c T 0..min （P ） ?????≥=0..min x b Ax t s x c T （P 0） 称（P 0）为（P ）的松弛问题。记（P ）和（P 0）的可行区域分别为D 和D 0 , 则 （1）0D D ?； （2）若（P 0）无可行解，则（P ）无可行解； （3）（P 0）的最优值是（P ）的最优值的一个下界； （4）若（P 0）的最优解 0x 是整数向量，则 0x 是（P ）的最优解。 基本思想： （1）用单纯形法求解松弛问题（P 0），若（P 0）的最优解 0x 是整数向量， 则 0x 是（P ）的最优解。计算结束。 (2) 若（P 0）的最优解 0x 不是整数向量，则对松弛问题（P 0）增加一个 线性约束条件（称它为割平面条件）， 新增加的约束条件将（P 0）的行区域D 0割掉一块，且这个非整数向量 0x 恰在被割掉的区域内，而原问题（P ）的任何一个可行解（格点）都没有被割去。记增加了割平面的问题为（P 1）， 称（P 1）为（P 0）的改进的松弛问题。 （3）用对偶单纯形法求解（P 1），若（P 1）的最优解 1x 是整数向量，则 1x 是（P ）的最优解。计算结束。否则转（2）

割平面的生成： 对给定的（P ）， 用单纯形法求解它的松弛问题（P 0），得到（P 0）的最优基 本可行解 0x ，设它对应的基为 ),,(1m B B A A B Λ=， m B B x x ,,1Λ为 0x 的基变量，记基变量的下标集合为 S ，非基变量的下标集合为 S 。则松弛问题（P 0）的最优单纯形表为 ∑∈=+S j j j z x z 0ξ m i b x a x S j i j ij B i ,,1,Λ==+∑∈ （3.2.1） 为了使符号简便，令 000,,0z b a z x j j B ===ξ。如果 m i b i ,,1,0,Λ= 全 是整数，则 0x 是（P ）的最优解。计算结束。否则至少有一个 l b 不是整数 )0(m l ≤≤，设 l b 所对应的约束方程为 , ∑∈=+S j l j lj B b x a x l （3.2.2） 用 ][a 表示不超过实数 a 的最大整数，则 ,][, , ][l l l lj lj lj f b b S j f a a +=∈+= （3.2.3） 其中，lj f 是 lj a 的分数部分，有 S j f lj ∈<≤,10， l f 是 l b 的分数部分， 有 .10<≤l f 由于在（3.2.2）中的变量是非负的，因此有 ∑∑∈∈≤S j j lj S j j lj x a x a ][ （3.2.4） 所以由（3.2.2）得 , ][∑∈≤+S j l j lj B b x a x l （3.2.5） 因为在ILP 中 x 限制为整数向量，故（3.2.5）的左端为整数，所以右端用 l b 的整数部分去代替后，（3.2.5）式的不等式关系仍成立，即

运筹学整数规划

实验报告 课程名称：___ 运筹学 ____ 项目名称：整数规划问题_ 姓名：__专业：、班级：1班学号：同组成员：_ __ 1注：1、实验准备部分包括实验环境准备和实验所需知识点准备。 2、若是单人单组实验，同组成员填无。

例4.5设某部队为了完成某项特殊任务，需要昼夜24小时不间断值班，但每天不同时段所需要的人数不同，具体情况如表4-4所示。假设值班人员分别在各时间段开时上班，并连续工作8h。现在的问题是该部队要完成这项任务至少需要配备多少名班人员？ 解： 根据题意，假设用i x（i=1,2,3,4,5,6）分别表示第i个班次开始上班的人数， 每个人都要连续值班8h，于是根据问题的要求可归结为如下的整数规划模型：目标函数： i i x z 6 1 min = ∑ = 约束条件： ? ? ? ? ? ? ? ? ? ? ? = ≥） 且为整数（6 ... 1 ,0 x 30 >= x6 + x5 20 >= x5 + x4 50 >= x4 + x3 60 >= x3 + x2 70 >= x2 + x1 60 >= x6 + x1 i i model: sets: num/1,2,3,4,5,6/:b,x; endsets data: b=60,70,60,50,20,30; enddata [obj]min=@sum(num(i):x(i)); x(1)+x(6)>=60; x(1)+x(2)>=70; x(2)+x(3)>=60; x(3)+x(4)>=50; 2注：实验过程记录要包含实验目的、实验原理、实验步骤，页码不够可自行添加。

解： 目标函数： y3*2000-y2*2000-y1*5000-x3*200)-(300+x2*30)-(40+x1*280)-(400=z max 约束条件：???????y3 *300<=x3*2y2*300<=x2*0.5y1*300<=x1*32000<=x3*4+x2+x1*5 model : sets : num/1,2,3/:x,y; endsets [obj]max =(400-280)*x(1)+(40-30)*x(2)+(300-200)*x(3)-5000*y(1)-2000*y(2)-2000*y(3); 5*x(1)+x(2)+4*x(3)<=2000; 3*x(1)<=300*y(1); 0.5*x(2)<=300*y(2); 2*x(3)<=300*y(3); @for (num(i):x(i)>=0;@bin (y(i));); end

第章整数规划割平面法

第章整数规划割平面法 This manuscript was revised on November 28, 2020

割平面法 求解整数规划问题： Max Z=3x1+2x2 2x1+3x214 4x1+2x218 x1,x20，且为整数 解：首先，将原问题的数学模型标准化，这里标准化有两层含义：（1）将不等式转化为等式约束，（2）将整数规划中所有非整数系数全部转化为整数，以便于构造切割平面。从而有：Max Z=3x1+2x2 2x1+3x2+x3=14 2x1+x2+x4=9 x1,x20，且为整数 利用单纯形法求解，得到最优单纯形表，见表1： 表1

最优解为：x1=13/4, x2=5/2, Z=59/4 根据上表，写出非整数规划的约束方程，如：x2+1/2x3-1/2x4=5/2 (1) 将该方程中所有变量的系数及右端常数项均改写成“整数与非负真分数之和”的形式，即：(1+0)x2+(0+1/2)x3+(-1+1/2)x4=2+1/2 把整数及带有整数系数的变量移到方程左边，分数及带有分数系数的变量称到方程右边，得： x2 - x4-2 =1/2-(1/2x3+1/2x4) (2)由于原数学模型已经“标准化”，因此，在整数最优解中，x2和x4也必须取整数值，所以(2)式左端必为整数或零，因而其右端也必须是整数。又因为x3,x40，所以必有： 1/2-(1/2x3+1/2x4)<1 由于(2)式右端必为整数，于是有： 1/2-(1/2x3+1/2x4)0 (3) 或 x3+x41 (4)

这就是考虑整数约束的一个割平面约束方程，它是用非基变量表示的，如果用基变量来表示割平面约束方程，则有： 2x1+2x211 (5) 从图1中可以看出，(5)式所表示的割平面约束仅割去线性规划可行域中不包含整数可行解的部分区域，使点E，2)成为可行域的一个极点。 图1 在(3)式中加入松弛变量x5，得： -1/2x3-1/2x4+x5=-1/2 (6) 将(6)式增添到问题的约束条件中，得到新的整数规划问题： Max Z=3x1+2x2 2x1+3x2+x3=14 2x1+x2+x4=9 -1/2x3-1/2x4+x5=-1/2 x i 0，且为整数，i=1,2,…,5 该问题的求解可以在表1中加入(6)式，然后运用对偶单纯形法求出最优解。具体计算过程见表2： 表2

第五章 整数规划练习题答案

第五章 整数规划练习题答案 一. 判断下列说法是否正确 1. 用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是 该问题目标函数值的下界。() 2. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。() 3. 用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。() 4. 指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。() 二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问 应如何分配这五项工作，并求得最大产值。 工作 工人 A B C D E 甲 9 4 6 8 5 乙 8 5 9 10 6 丙 9 7 3 5 8 丁 4 8 6 9 5 戊 10 5 3 6 3 答案： 设原矩阵为A ，因求极大问题，令B=[M-a ij ]，其中M=Max {a ij }=10，则： 16425105 3140 42 13251042510424003B 1 3752102 6410 1540 62 415151 3045 020305 7470574704646111-?????? ? ? ? ? ? ? ? ? ? =→→- ? ? ?- ? ? ? ? ? ??????? --- m 4n 5l m 4 4 21342132432431541545235234 6 4 64 6 4 6=<===? ??? ? ??? ? ? ? ?→→????→?? ? ??? ? ? ? ???? ? ? ? 031023 4003115406020303535?? ? ? ? ? ? ???

串并联电流电压规律探究实验报告单

探究串联电路中电流的规律 班级：小组成员： 【实验目标】 1.探究串联和并联电路的电压关系； 2、体验探究的过程，培养严谨的科学态度。 【实验器材】 电池组、电压表、三个小灯泡（其中两个规格相同）、开关、导线若干。 1.实验电路图： 2、实验步骤： ①按照电路图连接实物图； ②检查电路连接是否正确，若没有问题，方可闭合开关，使两个灯泡均发光。 ③将电流表分别串联在电路中的A点、B点、C点，并分别记录测量的电流值； ④换用另外的小灯泡再测1-3次。 A点的电流I A B点的电流I B C点的电流I C 第一次测量 第二次测量 第三次测量 分析实验数据，论证猜想与假设是否正确，你能总结出什么结论？ 实验结论： 实验结论： 【交流与评估】 1、实验设计有没有不合理的地方？操作中有没有失误？ 2.若通过两只灯泡的电流相等，两灯泡一定是串联吗？请通过实验得出结论。 指导教师：等级评价：

探究串联电路中电压的规律班级：小组成员： 【实验目标】 1、探究串联和并联电路的电压关系； 2、体验探究的过程，培养严谨的科学态度。 【实验器材】 电池组、电压表、三个小灯泡（其中两个规格相同）、开关、导线若干。 1、实验电路图： 2、实验步骤： ①按照电路图连接实物图； ②将电压表分别并联在电路中AB之间、BC之间、AC之间，并分别记录测量的 电压值； ③换用另外的小灯泡再测两次。 3.实验记录表格： 【分析与论证】分析实验数据，论证猜想与假设是否正确，你能总结出什么结论？ 实验结论： 【交流与评估】 1.实验设计有没有不合理的地方？操作中有没有失误？ 2.若两只灯泡两端的电压相等，两灯一定是并联吗？ 指导教师：等级评价： L 1 两端的电压U1/V L2两端的电压U2/V 总电压U/V 第一次测量 第二次测量 第三次测量

分支定界法和割平面法

分支定界法和割平面法 在上学期课程中学习的线性规划问题中，有些最优解可能是分数或消失，但现实中某些具体的问题，常要求最优解必须是整数，这样就有了对于整数规划的研究。 整数规划有以下几种分类：（1）如果整数规划中所有的变量都限制为（非负）整数，就称为纯整数规划或全整数规划；（2）如果仅一部分变量限制为整数，则称为混合整数规划；（3）整数规划还有一种特殊情形是0-1规划，他的变量取值仅限于0或1。本文就适用于纯整数线性规划和混合整数线性规划求解的分支定界法和割平面法，做相应的介绍。 一、分支定界法 在求解整数规划是，如果可行域是有界的，首先容易想到的方法就是穷举变量的所有可行的整数组合，然后比较它们的目标函数值以定出最优解。对于小型问题，变量数量很少，可行的整数组合数也是很小时，这个方法是可行的，也是有效的。而对于大型的问题，可行的整数组合数很大时，这种方法就不可取了。所以我们的方法一般是仅检查可行的整数组合的一部分，就能定出最有的整数解。分支定界法就是其中一个。 分枝定界法可用于解纯整数或混合的整数规划问题。在二十世纪六十年代初由Land Doig 和Dakin 等人提出。由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。 设有最大化的整数规划问题A ，与它相应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z *的上界，记作z ；而A 的任意可行解的目标函数值将是z *的一个下界z 。分枝定界法就是将B 的可行域分成子区域再求其最大值的方法。逐步减小z 和增大z ，最终求到z *。现用下例来说明： 例1 求解下述整数规划 219040Max x x z += ??? ??≥≥+≤+且为整数0,7020756792 12121x x x x x x 解 （1）先不考虑整数限制，即解相应的线性规划B ，得最优解为： 124.81, 1.82,356 x x z === 可见它不符合整数条件。这时z 是问题A 的最优目标函数值z *的上界，记作z 。而X 1=0，X 2=0显然是问题A 的一个整数可行解，这时0=z ，是z * 的一个下界，记作z ，即0≤z *≤356 。 （2）因为X 1X 2当前均为非整数，故不满足整数要求，任选一个进行分枝。设选X 1进行分枝，于是对原问题增加两个约束条件： [][]114.814, 4.8115 x x ≤=≥+= 于是可将原问题分解为两个子问题B 1和B 2（即两支），给每支增加一个约束条件并不影响问题A 的可行域，不考虑整数条件解问题B 1和 B 2 ，称此为第一次迭代。得到最优解