经济管理学院《运筹学》结课论文
整数规划问题的求解分析
整数规划问题的求解分析
摘要：整数规划是NP困难]1[的经典问题之一，本文讨论了整数规划问题中分支定界法与割平面法的基本原理和求解过程以及算法思想，当在决策变量和约束条件很多时,用常规的求解法效率很低，针对此种缺陷,提出了遗传算法，实现了快速解决整数规划的问题。
关键词：整数规划；分支定界法；割平面法；遗传算法
1 引言
整数规划(IP)]2[是运筹学领域里的一个重要分支,是规划论中研究决策变量取整数的一类较新、较特殊的线性规划，且大多数的组合优化问题都可以写成一个IP，如背包、旅行商、最短路、选址、分配和生产与存储计划问题等要求决策变量的取值为整数它的求解方法，目前来讲主要有割平面法、分枝定界法以及逐步完善的遗传算法。下面就它们的解法和差异加以讨论。
2 割平面法
2.1 割平面方法思想
割平面法是由高莫瑞(R E Gomory)1958年提出的，故又称为Gomory的割平面法。它的基本思想是：不断增加线性约束条件(几何术语称为割平面)将原规划问题的可行域切割掉一部分，使其切割掉的部分只包含非整数解，没有切割掉任何整数可行解，直到切割后得到的可行域有一个整数坐标的极点恰好是问题的最优解为止。]3[
2.2 割平面方法步骤
(1)先不考虑变量的取整约束，用单纯形法求解相应的线性规划问题，如果该问题没有可行解或最优解已是整数则停止，否则转下步。
在求解相应的线性规划时，首先要将原问题的数学模型进行标准化。这里的“标准化”有两个含义：第一是将所有的不等式约束全部转化成等式约束，这是因为要采用单纯形表进行计算的缘故。第二是将整数规划中所有非整数系数全部转换成整数，这是出于构造“切割不等式”的需要。]4[
(2)求一个“切割不等式”及添加到整数规划的约束条件中去，即对上述线
性规划问题的可行域进行“切割”，然后返回步骤1。
3 分支定界法
3.1 分支定界法思想
分枝定界法可用于解纯整数或混合的整数规划问题，由于这方法灵活且便于计算机求解, 所以现在它已是解整数规划的重要方法。]5[设有最大化的整数规划问题 A，与他相应的线性规划为问题 B，从解问题 B 开始，若其最优解不符合 A 的整数条件，那么 B 的最优目标函数必是 A 的最优目标函数Z*的上界，
记作
-
Z；而 A 的任意可行解的目标函数值将是Z*的一个下界
-
Z_。分枝定界法
就是将 B 的可行域分成子区域( 称为分枝) 的方法。逐步减小
-
Z和增大Z_, 最
终求到z*。
3.2 分支定界法步骤]5[
第一步：先不考虑整数约束,变成一般线性规划问题，求出最优解，记为X*(0)；
第二步：若X*(0)刚好是整数解，则该整数解就是原整数规划的最优解；否则，转入下一步；
第三步：对原问题进行分枝寻求整数最优解。选取非整数解X*(0)的一个非整数分量x*i=bi，以该非整数分量的相邻整数[bi]和[bi]+1为边界将原问题分枝为两个子问题，并抛弃这两个整数之间的非整数区域：
（1）在原线性规划模型中添加分枝约束xi≤[bi]，构成第一个子问题；
（2）在原线性规划模型中添加分枝约束xi≥[bi]+1，构成第二个子问题；
第四步：对上面两个子问题求出最优解。若某个子问题的解是整数解，则停止该子问题的分枝，并且把它的目标函数值与上一步求得的最优整数解对应的目标函数值比较以决定取舍；否则，对该子问题继续进行分枝。
第五步：重复第三、第四步直至获得原问题最优整数解为止。
其缺点为必须在每个节点解一个完整的线性规划。在大型问题中这将很费时，但在目前来讲，它在解决实践问题上还是最有效的，但不是说每个整数规划都能用它来解。请看下面的例子。
求:
“分枝”为整数规划最优解的出现创造条件，而“定界”则提高了搜索的效率。经验表明，优先选择较小的、不符合整数要求的变量进行分枝；并在可能的情况下，根据对实际问题的了解,事先选择一个合理的“界限”，可以更好地发挥分枝定界法的优点。
此例具体解题过程如下图所示：
4 割平面法与分枝定界法比较
综合前面所述,我们从它面的实质、解题步骤、适用对象解题算法等方面作了介绍，我们不能泛泛而谈谁优谁劣，各有千秋。
4.1割平面法与分枝定界法思想]6[
割平面法与分枝定界法它们的相同点都是对可行域进行切割，舍去一部分非整数解域，使剩下的子域包含原整数规划的所有可行域；所不同的是，割平面法剩下的子域仍然为一个，而分枝定界法剩下的是两枝。
4.2割平面法与分支定界法对问题的结构
割平面法对问题的结构以及求解结果都有较高要求，即要区分纯整数和混合整数问题，不同的类有不同的切割方程，而分枝定界法它可以对纯整数和混合整数问题直接使用。割平面法在添加相应割平面后要改变计算方法———用对偶单纯形法求解，而分枝定界法不需改变计算方法，便于计算机编程计算。割平面法在作切割后剩下的仍为一个子域，后继计算为一个较小子域上的整数规划，而分枝定界法在作切割后形成了两个分枝，后继计算便为两个较小子域上的整数规划，随着分枝增多，计算量较大。因此，当我们遇到一个较复杂的整数规划时，常常将两种方法结合起来使用，效果更好。
5 整数规划的遗传算法]
7[ 5.1 染色体编码方式
基本遗传算法采用二进制编码方法。对于一般函数优化问题,由于其定义域一般为实数域,因此常采用如下形式的染色体编码方式:
染色体(个体)X= (X1,X2,…,Xn)→ 对于整数规划问题，一部分变量定义域为数，一部分变量定义域为整数。对整数变量而言，较为合理的编码方式应采用二进制编码。
染色体(个体)X= (X1，X2,…,Xr ，Xr+ 1，…Xn) → X1
X2 … Xn X1 X2 … Xr Br+1 … Bn
其中X1，…，Xr 为实数编码方式，而Bi(i=r+ 1，…，n)为对应于整数Xi(i=r+ 1，…，n)的二进制串编码。下面介绍一种整数的二进制串编码方法。 设整数Xk(k=r+ 1，…，n)∈[0，M k ]，按如下算法对M i 进行分解： N 0= 0 ；X=M k ；p= 0
do p=p+ 1；
N p = int[log2(x+ 1)]；
x=x- 2N P + 1 while x> 0；
显然,按上述算法产生的p 个整数N J (j= 1, 2,…,p)满足Mk= (2n1-1)+ (2n2-1)+…+(2np-1)。即Mk 可由p 个位数分别为N j (j= 1, 2，…，p)的二进制数相加而得到。因此,X k 可由(n1+n2+…+N p )个二进制串B k 表示。
5.2适应值的定义及比例变换
对问题(1)，采用如下的罚函数将其转换为无约束最优化问题：
Min F(X)=f(x)+∑=11))(,0max(m i i x g +α)(1
1x h m i i ∑=
其中α为大的正数 目标函数对应的适应值采用如下的形式:
Fitness=F max -F ij
其中，F ij 为第i 代中第j 个个体的目标函数值,F max 为第i 代中目标函数的最大值。
5.3 遗传算法的控制参数和变量
5. 3. 1 复制算子
每当一个个体被选择杂交，它的期望拷贝数就减0. 5，而当一个串被选择复制，它的期望拷贝数就减少；当一个个体的期望拷贝数降到0以下，这个个体就失却了被选择的机会。为保证算法的收敛性，采用最优选择的方法将父代中适应值最大的个体强制性地复制给子代。
5. 3. 2 杂交算子
杂交算子采用线性组合与一点杂交相结合的方式,即如果个体Xs 、Xt 被选择杂交,则产生子代个体。
5. 3. 3 变异算子
变异率Pm的大小与群体规模及染色体长度有关,根据笔者经验,一般取不超
过10/N*L(其中N为群体规模,L为串长)为宜。变异算子采用非一致变异算子与
单点变异相结合的变异方式。
6总结
算法对于只有部分变量取整数的混合整数规划问题,只需修改相应变量的整数限制即可求解，用现代进化算法求解传统的优化问题具有其独到的优势,遗传算法以其适应性广,无需背景知识,搜索能力强等优点被广泛应用于各类优化问题中并基于适应值来选择染色体,这就使得该算法不受搜索空间的限制性假设的约束,不必要求诸如连续、可导和凸性等假设,因而使得它在求解各类最优化问题时具有广泛的适应性。
参考文献
[1] 马振华,陈景良,刘坤林,等.现代应用数学手册,运筹学与最优化理论卷[M].北京:清华大学出版社,1999.
[2] 宁伟华,陈绍顺.求解整数规划的混合遗传算法[J].空军工程大学学报,2004,12(06):80-83.
[3] 刘勇，康立山，陈毓屏.非数值并行算法——遗传算法[M ].北京:科学出版社, 1997.
[4] 熊义杰.解ILP的割平面法的收敛性问题[J].运筹与管理，2003,12（02）：36-38.
[5] 苟格.整数规划中的割平面法与分枝定界法比较[J].达县师范高等专科学校学报，2005,03（02）：18-21.
[6] 连海峰.整数规划中的割平面法与分枝定界法研究[J].数学的实践与认识，2011,06（11）：81-90.
[7] 陈永忠.整数规划的遗传算法[J].交通部上海船舶运输科学研究所学报，2000,06（23）:42-26.
动态规划法实现有向图的最短路径实验 实验题目： 设计一个求解有向图，单源最短路径的算法 实验目的： 1）了解，并掌握分支限界算法思想 2）会编写常见算法。 实验要求： 1.编写实验代码 2.分析算法时间和空间复杂度 实验主要步骤： 1 算法代码 package suanfa; publicclass ShortPath{ privatestatic Integer M = Integer.MAX_VALUE; publicstaticvoid main(String[]args){ int[][]c={{M,4,2,3,M,M,M,M,M,M}, {M,M,M,M,9,8,M,M,M,M}, {M,M,M,M,6,7,8,M,M,M}, {M,M,M,M,M,4,7,M,M,M}, {M,M,M,M,M,M,M,5,6,M}, {M,M,M,M,M,M,M,8,6,M}, {M,M,M,M,M,M,M,6,5,M}, {M,M,M,M,M,M,M,M,M,7}, {M,M,M,M,M,M,M,M,M,3}, {M,M,M,M,M,M,M,M,M,M}}; shortPath(10,c); } publicstaticvoid shortPath(int n,int[][]c){ int[] cost=newint[n];//cost[i]存储i到n-1的子问题的最短路径值 int[] path=newint[n];//path[i]存储状态，使cij+cost[i]最小的j值 //对数组cost[n]和path[n]进行初始化 for(int i=0;i
整数规划实验报告例文 篇一：实验报告整数规划 一、实验名称：整数规划问题和动态规划问题 二、实验目的： 熟练使用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. 在【选
动态规划： 【1】.矩阵乘法链，最小乘法次数。 一、问题描述 给定一个矩阵序列
运用动态规划模型解决物流配送中的最短路径问题 王嘉俊 （盐城师范学院数学科学学院09（1）班） 摘要：随着现代社会的高速发展，物流配送成为了连接各个生产基地的枢纽，运输的成本问题也成为了企业发展的关键。运费不但与运量有关，而且与运输行走的线路相关。传统的运输问题没有考虑交通网络，在已知运价的条件下仅求出最优调运方案，没有求出最优行走路径。文中提出“网络上的物流配送问题“，在未知运价，运量确定的情况下，将运输过程在每阶段中选取最优策略，最后找到整个过程的总体最优目标，节省企业开支。 关键词：动态规划，数学模型，物流配送,最优路径 1 引言 物流配送是现代化物流系统的一个重要环节。它是指按用户的订货要求, 在配送中心进行分货、配货, 并将配好的货物及时送交收货人的活动。在物流配送业务中, 合理选择配送径路, 对加快配送速度、提高服务质量、降低配送成本及增加经济效益都有较大影响。物流配送最短径路是指物品由供给地向需求地的移动过程中, 所经过的距离最短(或运输的时间最少, 或运输费用最低) , 因此, 选定最短径路是提高物品时空价值的重要环节。[1] 经典的Dijkstra 算法和Floyd 算法思路清楚,方法简便,但随着配送点数的增加,计算的复杂性以配送点数的平方增加,并具有一定的主观性。我国学者用模糊偏好解试图改善经典方法[]5,取得了较好的效果。遗憾的是,模糊偏好解本身就不完全是客观的。文献[]6详细分析了经典方法的利弊之后,提出将邻接矩阵上三角和下三角复制从而使每条边成为双通路径,既适用于有向图也适用于无向图, 但复杂性增加了。为了避免上述方法存在的不足,本文以动态规划为理论,选择合理的最优值函数,用于解决物流配送最短路径问题。 动态规划是解决多阶段决策过程最优化问题的一种数学方法。1951年美国数学家Bellman（贝尔曼）等人根据一类多阶段决策问题的特性，提出了解决这类问题的“最优性原理”，并研究了许多实际问题，从而创建了最优化问题的一种新方法——动态规划。 动态规划在工程技术、管理、经济、工业生产、军事及现代控制工程等方面都有广泛的应用，而且由于动态规划方法有其独特之处，在解决某些实际问题时，显得更加方便有效。由于决策过程的时间参数有离散的和连续的情况，故决
整数规划的数学模型及解的特点 整数规划IP (integer programming)：在许多规划问题中，如果要求一部分或全部决策变量必须取整数。例如，所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记IP 。 松弛问题(slack problem)：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。 若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integer linear programming)。 一、整数线性规划数学模型的一般形式 ∑==n j j j x c Z 1 min)max(或 中部分或全部取整数n j n j i j ij x x x m j n i x b x a t s ,...,,...2,1,...,2,10 ),(.211 ==≥=≥≤∑= 整数线性规划问题可以分为以下几种类型 1、纯整数线性规划(pure integer linear programming)：指全部决策变量都必须取整数值的整数线性规划。有时，也称为全整数规划。
2、混合整数线性规划(mixed integer liner programming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。 3、0—1型整数线性规划(zero —one integer liner programming)：指决策变量只能取值0或1的整数线性规划。 1 解整数规划问题 0—1型整数规划 0—1型整数规划是整数规划中的特殊情形，它的变量仅可取值0或1，这时的 ???? ? ????≥≤+≥+≤-+=且为整数0,5210453233max 2121212121x x x x x x x x x x z
● 例：动态规划解最短路径问题： 步骤(1)、(2)已实现。 最优子结构：从起点到终点的最短路径包含了该路径 上各点到终点的最短路径。 递归公式：设v 为图中一个顶点，v 1, v 2,…, v m 为v 的 直接后继，cost(v)表示v 到终点的最短路径 长度，c[u, w]表示边
设有向网G含n个顶点，用邻接矩阵c[1..n, 1..n]表示，起点为s，终点为t 。 有关信息的保存： 数组cost[1..n]: 存储子问题的解。 （cost[i]表示从顶点i到终点t的最短路径长 度。） 数组succ[1..n]: 存储最短路径的有关信息。 （succ[i]表示顶点i到终点t的最短路径上顶 点i的直接后继。） 原问题的最优值为cost[s]。 (1) 自底向上的迭代算法 关键：根据递归公式确定迭代顺序（即子问题的求解顺序）。 原则：计算cost[i]时，顶点i的所有后继的cost值应先计算。 计算顺序：按图G的逆拓扑排序顺序。 算法SHORTEST_ROUTE_LEN1 输入：有向网G的顶点数n, 邻接矩阵c[1..n, 1..n], 起点s和终点t , 1<=s, t<=n。
输出：G的从起点s到终点t的最短路径长度cost[s]和最短路径有关信息的数组succ[1..n]。 //对图G拓扑排序，结果存于数组a[1..n] 中。 toposort(c, n, a) j=n while a[j]< >t j=j-1 //找出j使得a[j]=t 。 for i=j+1 to n cost[a[j]]=∞//排除无关的顶 点。 cost[t]=0 //从终点开始迭代。 while a[j]< >s j=j-1; k=a[j]; i0=0 ; min=∞ for i=1 to n if c[k, i]+cost[i] 实验二Ｅｘcel解决整数规划问题 一、问题的提出 某公司拟用集装箱托运甲、乙两种货物,这两种货物每件的体积、重量、获得利润以及托运所受限制如下表所示: 二模型得出 分析：这个问题是一个整数规划问题, 故应该确定决策变量、目标函数及约束条件。 设X1,X2分别为甲乙两种货物托运的件数,显然,X1,X2是非负的整数,这是一个纯整数规划问题，根据问题的要求可知 对于货物总体积的托运限制最大不得超过1365立方英尺,故应有约束条件: 195 Ｘ１+２7３Ｘ２≦1365 对于货物总重量的托运限制为最大不得超过140千克,故应有约束条件为: 4X1+40Ｘ２≦１40 同时有：Xｉ≥0，ｉ=1,2 希望货物托运的配置,使得可获得利润最大,即求W=2Ｘ1+3X2 的最大值 由分析可得如下模型: ＭaxＷ=2X1+3X2 (所获利润最大）约束条件如下 195 X1+2７3 X２≦1365 4X1+40X2≦１40 X i≥0, ｉ＝1,2 Ｘ1≦4 三、模型求解 1．建立规划求解工作表（如下图所示） ⑴．在可变单元格（B４:C４)中输入初始值（１，1） ⑵．在上图有关单元格输入如下公式 单元格地址公式 Ｃ６ =B２*B4+Ｃ2*C４ Ｃ７ =B3＊B4+C3＊C４ C8 =B5*Ｂ4+C5*C4 ⑶.求最佳组合解： ①．选取[工具]→［规划求解…]出现如下对话窗： ②．在“设置目标单元格”窗口，输入C8。 ③．选定“最大值”选项。 ④．在可变单元格中输入B4：C4。 ⑤．选取“添加”，出现“添加约束”窗口,在“添加约束”窗口输入: 单元格引用位置运算符号约束值 B4：Ｃ4 int 单击“添加”,再输入以下约束条件: B4：C４ >= 0 单击“添加”,再输入以下约束条件： B４ >＝ 4 单击“添加”，再输入以下约束条件： C6 <= １365 单击“添加”,再输入以下约束条件： C7 ＜= １40,单击“确定” ⑥在“规划求解参数”窗口，选择“求解。” ⑦选择“确定”,（计算结果如下表所示） ⑧在“规划求解结果”对话框中选定保存“规划求解结果”，单击“确定”。 于是我们就得到如下运算结果报告 四、报告分析 表1 Microｓｏｆt Excel ９.0 运算结果报告 目标函数的初值：当变量X＝(１，1）时目标函数的值。 目标函数的终值：经过运算后的目标函数的最优值。 此表说明函数的最优值为14。 表2可变单元格式 从此表看出我们的最优解（终值）为(4，2）。 -- 《管理运筹学》实验报告 实验日期： 2016年 04月 21日—— 2016 年 05 月 18 日 班级2014级04班姓名杨艺玲学号56 实验 管理运筹学问题的计算机求解 名称 实验目的： 通过实验学生应该熟练掌握“管理运筹学”软件的使用，并能利用“管理运筹学”对具体问题进行问题处理，且能对软件处理结果进行解释和说明。 实验所用软件及版本： 管理运筹学 实验过程：（含基本步骤及异常情况记录等) 一、实验步骤（以P31页习题1 为例） 1.打开软件“管理运筹学” 2.在主菜单中选择线性规划模型，屏幕中会出现线性规划页面 3.在点击“新建”按钮以后，按软件的要求输入目标函数个数和约束条件个数，输入目标函数级约束条件的歌变量的系数和b值，并选择好“≤”、“≥”或“＝”，如图二所示，最后点击解决 4.注意事项： （1）输入的系数可以是整数、小数，但不能是分数，要把分数化为小数再输入。（2）输入前要合并同类项。 当约束条件输入完毕后，请点击“解决”按钮，屏幕上讲显现线性规划问题的结果，如图所示 5.输出结果如下 5.课后习题： 一、P31习题1 某家具公司生产甲、乙两种型号的组合柜，每种组合柜需要两种工艺（制白坯和油漆）.甲型号组合柜需要制白坯6工时，油漆8工时：乙型号组合柜需要制白坯12工时，油漆4工时.已知制白坯工艺的生产能力为120工时/天，油漆工艺的生产能力为64工时/天，甲型号组合柜单位利润200元，乙型号组合柜单位利润为240元. 约束条件： 问题： （1）甲、乙两种柜的日产量是多少这时最大利润是多少 答：由实验过程中的输出结果得甲组合柜的日产量是4个，乙的事8个。 （2）图中的对偶价格的含义是什么 答： 对偶价格的含义是约束条件2中，每增加一个工时的油漆工作，利润会增加元。 （3）对图中的常数项范围的上、下限的含义给予具体说明，并阐述如何使用这些信息。 答：当约束条件1的常数项在48~192范围内变化，且其他约束条件不变时，约束条件1的对偶价格不变，仍为；当约束条件2的常数项在40~180范围内变化，而其他约束条件的常数项不变时，约束条件2的对偶价格不然，仍为。 （4）若甲组合柜的利润变为300，最优解不变为什么 . 0,0,6448,120126; 240200 z max ≥≥≤+≤++=y x y x y x y x 算法综合实验报告 学号： 1004111107 姓名：黄琼莹 一、实验内容： 分别用动态规划、贪心及分支限界法实现对TSP问题（无向图）的求解，并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。 二、程序设计的基本思想、原理和算法描述： （包括程序的数据结构、函数组成、输入/输出设计、符号名说明等） 1、动态规划法 (1)数据结构： 利用二进制来表示集合，则集合S可由一个十进制数x相对应，此x所 对应的二进制数为y，如果y的第k位为1，则表示k存在集合S中。 例如： 集合S={0，1}（其子集合为{}{0}{1}{01}），我们用二进制数11（所对应 十进制数为3）表示S，11中右手边第1个数为1表示0在集合S中， 右手边第二个数为1表示1在集合S中，其他位为0表示其它数字不在 集合S中；同理, 集合S={0,2}（其子集合为{}{0}{2}{02}可用二进制数101（所对应十进制 数为5）表示（右手边第1个数为1表示0在集合S中，右手边第二个 数为0表示1不在集合S中，右手边第3个数为1表示2在集合S中， 则说明0，2在集合中，1不在集合中。 (2)函数组成 getmin():获得该数组的最小值； getJ()：根据2进制j和j中1的个数找下一个j getnextj():返回下一个j的十进制数 (3)输入/输出设计 本题通过键盘进行输入，通过屏幕进行输出 由于题目的输入要求是：第一行输入一个整数n（2<=n<=10），接下来的n行，每行输入n-1个整数，表示i与除了自己之外的所有点之间的距离，按点的编号从小到大顺序输入 可以设计两个for循环来实现数据的输入，外层for循环实现一行一行地输入，内层for循环实现某一行中数据的输入 5 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 (4)符号名说明 N：节点数，即城市的数目 matr[20][20]：存邻接矩阵 d[20][40000]={0}：存动态填表数据 min：花费的最小值，即答案 jlist[20]：存放j的二进制数组 V[20]：标记节点是不是被访问过 tmpres[20]:存放结果的数组 (5)算法描述 假设从顶点i出发，令d(i,V’)表示从顶点i出发经过V’中各个顶点一次且仅一次，最后回到出发点i的最短路径的长度，开始时，V’=V-{i}，于是，旅行商问题的动态规划函数为： d(i,V’) = min{c ik + d(k,V’-{k})} (k∈V’) 1) d(k,{}) = c ki (k ≠ i) 2) 简单来说,就是用递归表达:从出发点0到1号点,假设1是第一个,则剩下的路程就是从1经过剩下的点最后回到0点的最短路径. 所以当V’为空的时候, d(k,{}) = c ki (k ≠ i), 找的是最后一个点到0点的距离.递归求解1之后,再继续求V’之中剩下的点,最后找出min. 如果按照这个思想直接做,对于每一个i都要递归剩下的V中所有的点,所以这样的时间复杂度就近似于N!,其中有很多重复的工作. 可以从小的集合到大的集合算,并存入一个二维数组,这样当加入一个节点时,就可以用到之前的结果,如四个点的情况: 邻接矩阵: node 0 1 2 3 0 5 3 2 运筹学实验报告(一) 实验要求：学会在Excel 软件中求解。 实验目的：通过小型线性规划模型的计算机求解方法。 熟练掌握并理解所学方法。 实验内容： 题目： 某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下； 设司机和乘务人员分别在各时间区段一开始上班，并连续工作八小时，问该公交线 路至少配备多少名司机和乘 务人员。列出这个问题的线 性规划模型。 解：设Xj 表示在第j 时间区段开始上班的司机和乘务人员数 班次 时间 所需人数 1 6:00-10:00 60 2 10:00-14:00 70 3 14:00-18:00 60 4 18:00-22:00 50 5 22:00-2:00 20 6 2:00-6:00 30 。 6-10 10-14 14-18 18-22 22-2 2-6 1 X1--- X1 2 X2--- X2 3 X3--- X3 4 X4--- X4 5 X5--- X5 6 X6 X6--- 60 70 60 50 20 30 所需人 数 Min z=x1+x2+x3+x4+x5+x6 St: x1+x6>=60 X1+x2>=70 X2+x3>=60 X3+x4>=50 X4+x5>=20 X5+x6>=30 Xj>=0,xj为整数， j=1,2,3,4,5,6 过程： 工作表[Book1]Sheet1 报告的建立: 2011-9-28 19:45:01 目标单元格(最小值) 单元格名字初值终值 $B$1 min 0 150 可变单元格 单元格名字初值终值 $B$3 x 0 45 $C$3 x 0 25 $D$3 x 0 35 $E$3 x 0 15 $F$3 x 0 15 $G$3 x 0 15 结果：最优解X=(45,25,35,15,15,15)T 目标函数值z=150 小结：1.计算机计算给规划问题的解答带来方便，让解答变得简洁； 最短路径动态规划问题及其程序设计 林旭东 (深圳大学管理学院,广东深圳518060) [摘要]本文以最短路径问题为例,在给出佛洛伊德算法的基础上,设计了求解该算法的计算程序,这样可大大提高最短路径计算的效率。 [关键词]最短路径; 动态规划; 程序设计 1 佛洛伊德算法 已知有n个顶点的有向图,佛洛伊德算法能够求解出每一对顶点之间的最短路径。假设使用邻接矩阵d ( i, j)来对图进行存储, d ( i, j)表示υi 到υj 之间的距离,可是该距离不一定是最短距离。佛洛伊德算法的基本思想是:为求顶点υi→υj 之间的最短距离,需要进行n次试探。首先将υ0 加入路[收稿日期] - 12 - 22[作者简介]林旭东(1972 - ) ,男, 湖北武汉人,深圳大学管理学院副教授,博士后,主要研究方向:数量模型与决策分析。径,考虑路径υi →υ0 →υj 是否存在,如果存在,则比较υi →υj和υi →υ0 →υj 的路径长度,取长度短的路径作为υi →υj 的路径,记作(υi ,υj ) 。接着在路径上再增加一个顶点υ1 ,比较υi→υ1 →υj 和(υi ,υj )的路径长度, 取长度短的路径作为(υi ,υj) 。不断将顶点υ2 ,υ3 , .,υn - 1加入进行试探, 最后得到的(υi ,υj )必定为υi →υj 的最短路径。若使用数组dk ( i, j)表示加入顶点k后,最短路径长度的变化情况,使用数组pk ( i, j)表示加入顶点k后,最短路径上顶点的变化情况,这样佛洛伊德算法就会产生一组d 0 ( i, j) ,d1 ( i, j) , ., dn - 1 ( i, j)和一组p0 ( i, j) , p1 ( i, j) , ., pn - 1 ( i, j) 。 R2 = 01314 014 01286 0 01197 01263 01394 01146 《管理运筹学》实验报告 实验日期：2016年04月21日——2016年05月18日 实验目的： 通过实验学生应该熟练掌握“管理运筹学 3.0”软件的使用，并能利用“管理运筹学 3.0” 对具体问题进行问题处理，且能对软件处理结果进行解释和说明。实验所用软件及版本：管理运筹学3.0 实验过程：（含基本步骤及异常情况记录等―） 一、实验步骤（以P31页习题1为例） 1?打开软件“管理运筹学3.0” 2?在主菜单中选择线性规划模型，屏幕中会出现线性规划页面 3?在点击“新建”按钮以后，按软件的要求输入目标函数个数和约束条件个数，输入目标函数级约束条件的歌变量的系数和b值，并选择好“w”、“》”或“二”, 如图二所示，最后点击解决 班级2014级04班姓名杨艺玲学号2014190456实验 名称 管理运筹学问题的计算机求解 n 幵 目标的数 娈童个数约束条件个数 芙 遇出 保存解决关于 X 4?注意事项： (1)输入的系数可以是整数、小数，但不能是分数，要把分数化为小数再输入。 (2)输入前要合并同类项。 当约束条件输入完毕后，请点击“解决”按钮，屏幕上讲显现线性规划问题的结果, 如 图所示 D tiff 0% 关于遇出 变童个数约朿条件个数F目标的数3V 标淮北结杲: 上一曲 5.输出结果如下 me車最优解如下***#尊1林*祜除目标函数最优值知2?20 变1 最优解相差値 XI 4.00 0.00 X2 8.00 0100 釣束松弛颅11余变量对偶价格 01. 00 16. 5€ 0.00 13.33 目标函数系数范園: 娈1下限当前值上限 XI 120. 30 200.00430. 00 X2 100. 0D 240.00400.00 常数【页范園； 的束T眼当前值上限 143.00120 00152.00 240.00 64.00 160.00 5.课后习题： 一、P31习题1 某家具公司生产甲、乙两种型号的组合柜，每种组合柜需要两种工艺（制白坯和油漆）.甲型号组合柜需要制白坯6工时，油漆8工时：乙型号组合柜需要制白坯12工时，油漆4工时.已知制白坯工艺的生产能力为120工时/天，油漆工艺的生产能力为64工时/天，甲型号组合柜单位利润200元，乙型号组合柜单位利润为240 元. max z = 200x 240y; 约束条件：6x，12心2°, 8x +4y 兰64, x 一0, y -0. 问题： （1）甲、乙两种柜的日产量是多少？这时最大利润是多少？ 答：由实验过程中的输出结果得甲组合柜的日产量是4个，乙的事8个 最短路径问题 下图给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路长度。 现在，我们想从城市a到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？设DiS［x］为城市x到城市E的最短路径长度（x表示任意一个城市）； map[i，j]表示i，j两个城市间的距离，若map[i，j]=0，则两个城市不通； 我们可以使用回溯法来计算DiS［x］： var S：未访问的城市集合； function search(who{x})：integer； {求城市who与城市E的最短距离} begin if Who＝E Then Search←0 {找到目标城市} Else begin min←maxint；{初始化最短路径为最大} for i 取遍所有城市 Do if（map[Who，i]＞0{有路}）and（i S{未访问}） then begin S←S－[i]；{置访问标志} j←map[Who，i]+ search(i)； {累加城市E至城市Who的路径长度} S←S＋[i]； {回溯后，恢复城市i未访问状态} if j＜min Then min←j； {如果最短则记下} end；{then} search←min；{返回最短路径长度} End；{else} End；{search} begin S←除E外的所有城市； Dis[a]←search（a）；{计算最短路径长度} 输出Dis[a]； end．{main} 这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外，其他城市都要访问，所以时间复杂度为O（n！），这是一个“指数级”的算法。那么，还有没有效率更高的解题方法呢？ 实验二Excel解决整数规划问题 一、问题的提出 某公司拟用集装箱托运甲、乙两种货物,这两种货物每件的体积、重量、获得利润以及托运所受限制如下表所示： 二模型得出 分析:这个问题是一个整数规划问题, 故应该确定决策变量、目标函数及约束条件。 设X1，X2分别为甲乙两种货物托运的件数,显然, X1，X2是非负的整数,这是一个纯整数规划问题,根据问题的要求可知 对于货物总体积的托运限制最大不得超过1365立方英尺,故应有约束条件: 195 X1＋273 X2≦1365 对于货物总重量的托运限制为最大不得超过140千克,故应有约束条件为: 4 X1＋40 X2≦140 同时有：X i≥0, i=1,2 希望货物托运的配置,使得可获得利润最大,即求W＝2X1+3X2 的最大值 由分析可得如下模型： MaxW=2X1+3X2 （所获利润最大）约束条件如下 195 X1＋273 X2≦1365 4 X1＋40 X2≦140 X i≥0, i=1,2 X1≦4 三、模型求解 1．建立规划求解工作表（如下图所示） ⑴．在可变单元格（B4：C4）中输入初始值（1，1） ⑵．在上图有关单元格输入如下公式 单元格地址公式 C6 =B2*B4+C2*C4 C7 =B3*B4+C3*C4 C8 =B5*B4+C5*C4 ⑶．求最佳组合解： ①．选取[工具]→[规划求解…]出现如下对话窗： ②．在“设置目标单元格”窗口，输入C8。 ③．选定“最大值”选项。 ④．在可变单元格中输入B4：C4。 ⑤．选取“添加”，出现“添加约束”窗口，在“添加约束”窗口输入： 单元格引用位置运算符号约束值 B4：C4 int 单击“添加”，再输入以下约束条件： B4:C4 >= 0 单击“添加”，再输入以下约束条件： B4 >= 4 单击“添加”，再输入以下约束条件： C6 <= 1365 单击“添加”，再输入以下约束条件： C7 <= 140,单击“确定” ⑥在“规划求解参数”窗口，选择“求解。” ⑦选择“确定”，（计算结果如下表所示） ⑧在“规划求解结果”对话框中选定保存“规划求解结果”，单击“确定”。 于是我们就得到如下运算结果报告 四、报告分析 表1 Microsoft Excel 9.0 运算结果报告 目标函数的初值：当变量X=（1，1）时目标函数的值。 目标函数的终值：经过运算后的目标函数的最优值。 此表说明函数的最优值为14。 表2 可变单元格式 从此表看出我们的最优解（终值）为（4,2）。 2012——2013学年第一学期 实验报告 课程名称：运筹学 实验项目：求解线性规划问题 实验类别：综合性□设计性□√验证性□专业班级： 姓名：学号： 实验地点： 实验时间： 指导教师：成绩： 一.实验目的 1、熟悉LINGO 软件的使用方法、功能； 2、学会用LINGO 软件求解一般的线性规划问题。 二.实验内容 1、某班有男同学30人,女同学20人,星期天准备去植树。根据经验,一天中,男同学平均每人挖坑20个,或栽树30棵,或给25棵树浇水,女同学平均每人挖坑10个,或栽树20棵,或给15棵树浇水。问应怎样安排,才能使植树(包括挖坑、栽树、浇水)最多。建立该问题的数学模型，并求其解。 2、求解线性规划： 12 1212212max 2251228..010 ,z x x x x x x s t x x x =++≥??+≤??≤≤???为整数 3、在高校篮球联赛中,我校男子篮球队要从８名队员中选择平均身高最高的出场 ⑴ 中锋最多只能上场一个。 ⑵ 至少有一名后卫 。 ⑶ 如果１号队员和４号队员都上场，则６号队员不能出场 ⑷ ２号队员和６号队员必须保留一个不出场。 问应当选择哪5名队员上场,才能使出场队员平均身高最高? 试写出上述问题的数学模型，并求解。 三. 模型建立 1建立模型为：设需要男生挖坑x1人，栽树x2人，浇水x3人，女生挖坑x4人，栽树x5人，浇水x6人,则建立的数学模型为： 14 12345614252536max 2010302020103020302025150,1,2,3,4,5,6=+++=??++=??+=+??+=+??>==?且为整数 i z x x x x x x x x x x x x x x x x x i 2.建立模型为：设j x =1表示第j 号队员上场，j x =0第j 号队员不上场,j=1,2,3,4,5,6,7,8. 12345678) 126781462612345678max 1/5(1.92 1.90 1.88 1.86 1.85 1.83 1.80 1.781121501,1,2,3,4,5,6,7,8. =++++++++<=??++>=??++<=?+<=??+++++++=?===?j j 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 orx j 四. 模型求解（含经调试后正确的源程序） 1、(1)编写程序如下 model : max =20*x1+10*x4; x1+x2+x3=30; x4+x5+x6=20; 20*x1+10*x4-30*x2-20*x5=0; 30*x2+20*x5-25*x3-15*x6=0; @gin(x1); @gin(x2); @gin(x3); @gin(x4); @gin(x5); @gin(x6); end （2）编写程序如下: model : max =x1+2*x2; 2*x1+5*x2>12; x1+2*x2<8; x2<10; @gin(x1); 〈运筹学〉补充例题 例题 1.1 某工厂可以生产产品A和产品B两种产品。生产单位产品A和B所需要的机时、人工工时的数量以及可利用资源总量由下表给出。这两种产品在市场上是畅销产品。该工厂经理要制订季度的生产计划，其目标是使工厂的销售额最大。 产品A 产品B 资源总量 机器（时） 6 8 120 人工（时） 10 5 100 产品售价（元） 800 300 MAX 800X1 +300X2 ST 6X1 +8X2 <= 120 10X1 +5X2 <= 100 X1, X2 >=0 例题 1.2该工厂根据产品A和产品B的销售和竞争对手的策略，调整了两种产品的售价。产品A和B的价格调整为600元和400元。假设其它条件不变，请你帮助该工厂经理制订季度的生产计划，其目标仍然是使工厂的销售额最大。 X 600X1 +400X2 ST 6X1 +8X2 <= 120 10X1 +5X2 <= 100 X1, X2 >=0 例题 1.3由于某些原因，该工厂面临产品原料供应的问题。因此，工厂要全面考虑各种产品所需要的机时、人工工时、原材料的资源数量及可用资源的总量、产品的售价等因素。有关信息在下表中给出。 产品A 产品B 资源总量 机器（时） 6 8 120 人工（时） 10 5 100 原材料(公斤) 11 8 130 产品售价（元） 600 400 MAX 600X1 +400X2 ST 6X1 +8X2 <= 120 10X1 +5X2 <= 100 11X1 +8X2 <= 130 X1, X2 >=0 例题 1.４随着企业改革的不断深化，该企业的经理的管理思想产生了变化，由原来的追求销售额变为注重销售利润，因此，要考虑资源的成本。工厂的各种产品所需要的机时、人 《管理运筹学》实验报告实验日期： 2016年 04月 21日—— 2016 年 05 月 18 日 3.在点击“新建”按钮以后，按软件的要求输入目标函数个数和约束条件个数，输入目标函数级约束条件的歌变量的系数和b值，并选择好“≤”、“≥”或“＝”，如图二所示，最后点击解决 4.注意事项： （1）输入的系数可以是整数、小数，但不能是分数，要把分数化为小数再输入。（2）输入前要合并同类项。 当约束条件输入完毕后，请点击“解决”按钮，屏幕上讲显现线性规划问题的结果，如图所示 5.输出结果如下 5.课后习题： 一、P31习题1 某家具公司生产甲、乙两种型号的组合柜，每种组合柜需要两种工艺（制白坯和油漆）.甲型号组合柜需要制白坯6工时，油漆8工时：乙型号组合柜需要制白坯12工时，油漆4工时.已知制白坯工艺的生产能力为120工时/天，油漆工艺的生产能力为64工时/天，甲型号组合柜单位利润200元，乙型号组合柜单位利润为240元. 约束条件： 问题： （1）甲、乙两种柜的日产量是多少？这时最大利润是多少？ 答：由实验过程中的输出结果得甲组合柜的日产量是4个，乙的事8个。 . 0,0,6448,120126;240200 z max ≥≥≤+≤++=y x y x y x y x （2）图中的对偶价格13.333的含义是什么？ 答： 对偶价格13.333的含义是约束条件2中，每增加一个工时的油漆工作，利润会增加13.33元。 （3）对图中的常数项围的上、下限的含义给予具体说明，并阐述如何使用这些信息。 答：当约束条件1的常数项在48~192围变化，且其他约束条件不变时，约束条件1的对偶价格不变，仍为15.56；当约束条件2的常数项在40~180围变化，而其他约束条件的常数项不变时，约束条件2的对偶价格不然，仍为13.333。 （4）若甲组合柜的利润变为300，最优解不变？为什么？ 答：目标函数的最优值会变，因为甲组合柜的利润增加，所以总利润和对偶价格增加；甲、乙的工艺耗时不变，所以甲、乙的生产安排不变。 二、学号题 约束条件： 无约束条件 （学号）学号43214321432143214321 0 0,30 9991285376)(53432max x x x x x x x x x x x x x x x x x x x x z ≤≥≤-+-+≥-+-+=-++-+++=??????????????-≥?-?-?-?-?-7606165060~5154050~414 )30(40~313)20(30~21210 20~11 10~1）（学号）（学号）（学号学号学号）（学号不变学号规则 例1 求解下列整数规划的最优解： ()123 123max 45634510..01,2,3,j j Z x x x x x x s t x j x =++++???=??≤≥为整数. 解 （1）建立动态规划模型： 阶段变量：将给每一个变量j x 赋值看成一个阶段，划分为3个阶段，且阶段变量k=1,2,3. 设状态变量k s 表示从第k 阶段到第3阶段约束右端最大值，则10.j s = 设决策变量k x 表示第k 阶段赋给变量k x 的值(1,2,3)k =. 状态转移方程：2113223,4.s s x s s x =-=- 阶段指标：111122223333(,)4,(,)5,(,)6.u s x x u s x x u s x x === 基本方程； ()(){}()3113,2,1044 ()max ,()0.s k k k k k k k k k k x a f s u s x f s f s ++??=?????? ?=+???=?≤≤ 其中1233,4, 5.a a a === （1） 用逆序法求解： 当3k =时， ()(){}{}33333443330055max 6max 6,s s x x f s x f s x ???? ?? ?? ?????? ?? =+=≤≤≤ 而{}[]30,1,2,3,4,5,6,7,8,9,10.s x ∈表示不超过x 的最大整数。因此，当30,1,2,3,4s =时， 30x =；当35 ,67,89s =时，3x 可取0或1；当310s =时，3x 可取0，1，2，由此确定()33. f s 现将有关数据列入表4.1中 表4.1中. 动态规划之最短路径问题源代码 #include "stdio.h" #include "conio.h" #define n 16 /*图的顶点数*/ #define k 7 /*图的段数*/ #define l 30 #define MAX 100 typedef int NodeNumber;/*节点编号*/ typedef int CostType;/*成本值类型*/ CostType cost[n][n]; NodeNumber path[k]; NodeNumber cur=-1; void creategraph(CostType *cost[n][n]) /*创建图的成本矩阵*/ { int i,j,x,y,value; for(i=0;i用excel解决整数规划问题
运筹学线性规划实验报告
贪心、分支限界、动态规划解决最短路径问题
运筹学实验报告1
最短路径Floyd算法动态规划问题及其程序设计样本
运筹学线性规划实验报告
动态规划-最短路径问题
用excel解决整数规划问题
运筹学实验报告
整数规划例题
运筹学线性规划实验报告
动态规划例1 求解下列整数规划的最优解
动态规划之最短路径源代码
相关主题
文本预览