0-1规划问题
一条装配线由一系列工作站组成，被装配或制造的产品在装配线上流动的过程中，每站都要完成一道或几道工序，假定一共有六道工序，这些工序按先后次序在各工作站上完成，关于这些工序有如下的数据：
工序 所需时间（分） 前驱工序
1 3 无
2 5 无
3 2 2
4 6 1，3
5 8 2
6 3 4
另外工艺流程特别要求，在任一给定的工作站上，不管完成哪些工序，可用的总时间不能超过10分钟，如何将这些工序分配给各工作站，以使所需的工作站数为最少？
1）模型分析与变量的假设
下面，我们先讨论工序与工作站的关系，并试图建立起该问题的0—1型整数规划模型。
对任一工序而言，它要么属于工作站j，要么不属于工作站j，故决策变量可定义为：
行 运 上 j 不在工作站 若工序 0行 运 上 在工作站 若工序 1ij ixij
这种定义，使我们能根据最优解中ijx的值来很快确定工序i与工作站j之间的隶属关系。
又因工序1，2，3所需的工作时间不超过10分钟，故工序1，2，3的工作可以在一个工作站上完成，此时，工序4，5，6只能分别在各自的工作站上工作，该可行解对应的工作站数为4个。也就是说，对最优解而言，该装配线上所需的工作站个数不会多于4个。因此，我们再定义变量如下：
jjwj 作站 工 要 需 不 中 解 优 若在最 0 站 作 工 要 需 中 解 优 若在最 1 至此，我们得到所需的目标函数为：
4321 maxwwwwz 2）再考虑该模型的约束条件：
（1） 每道工序均隶属于一个工作站，且每一工序都必须完成，故有以下六个约束：
6) 5, 4, 3, 2, ,1( 14321ixxxxiiii （2）在任一工作站上完成隶属工序所用的时间不能超过10分钟，故有以下四个约束：
实 验 报 告
课程名称：管理运筹学
学院：
专业班级：
姓名：
学号：
管理学院
课程名称 管理运筹学 实验项目名称 管理运筹学计算实验
指导教师 实验软件 Excel
实验地点 实验时间 2015.5.24
一、实验目的及要求
实验目的：掌握用Excel软件求解线性规划、灵敏度分析、运输问题，在今后的工作中可以熟练的对管理运筹学数学模型求解。
实验要求：
对于Excel软件，按照求解流程,求给出例题的求解过程，求解结果，并截图。
二、实验内容与步骤
O一1规划的Excel模型
0-1规划是整数规划的特殊情况，其Excel模型与一般的线性规划模型相同，只是增加了一个“决策变量必须为0或1”的约束条件。为了反映这一约束条件，在求解时应在Excel的“添加约束”对话框中添加关于决策变量取值为0或1的约束条件。在Excel的“添加约束”对话框中，用“bin(Binary)”表示0和1两者取其一，因此，只要在约束条件左边输入要求取0或1的决策变量的单元格地址，然后选择“bin”即可。下面以本章例5．10为例，来说明。一1规划的Excel模型求解过程，如图5—15所示。
可知最优解：X1=1，X2=0，X3=1，X4=0，X5=0，目标函数值fmax=4。与隐枚举法所得结果相同。
三、实验结果（结论）
四、对本实验的学习心得
对模型的建立有了初步的了解，使用Excel来求解线性规划问题，更方便。掌握用Excel软件求解线性规划、灵敏度分析、运输问题，在今后的工作中可以熟练的对管理运筹学数学模型求解。
五、教师评分
签名（盖章）：
注：可根据内容加页。
2013-2014（2）专业课程实践论文
题目：0-1规划的隐枚举法
一、算法理论
0—1规划在整数规划中占有重要地位，一方面因为许多实际问题，例如指派问题、选地问题、送货问题都可归结为此类规划，另一方面任何有界变量的整数规划都与0—1规划等价，用0—1规划方法还可以把多种非线性规划问题表示成整数规划问题，所以不少人致力于这个方向的研究。求解0—1规划的常用方法是分枝定界法，对各种特殊问题还有一些特殊方法。
线性模型中，当变量的取值只能是“0”或“1”时，称之为“0-1规划问题”。有种极其简单的解法，就是将变量取值为0或1的所有组合列出，然后分别代入目标函数，选出其中能使目标函数最优化的组合，即为最优解。但是真的这样会做很多无用功，浪费大量资源，所以，需要改进方法。本文主要介绍隐枚举法的应用原理，意在剖析其“隐”在何处。从而帮助读者更好地应用这种方法。
和线性规划问题一样，首先需要将模型标准化。标准化对0-1规划问题提出四点要求：
1.目标函数为最小优化
2.目标函数中变量的系数都为正
3.在目标函数中，变量按系数值从小到大排列，则约束函数中，变量的排列次序也做相应改变。
4.所有变量均为0或1
0-1线性规划的基本形式是
1minnjjjZcx 011,2,,..1,2,,jijjjxjmstaxbin或
二、算法框图
三、算法程序
function [intx,intf] = ZeroOneprog(c,A,b,x0)
%目标函数系数向量，c
%不等式约束矩阵，A
%不等式约束右端向量，b
%初始整数可行解，x0
%目标函数取最小值时的自变量值，intx
%目标函数的最小值，intf
sz = size(A);
if sz(2) < 3
[intx,intf] = Allprog(c,A,b); %穷举法
0—1型整数规划模型
1. 0—1型整数规划模型概述
整数规划指的是决策变量为非负整数值的一类线性规划，在实际问题的应用中，整数规划模型对应着大量的生产计划或活动安排等决策问题，整数规划的解法主要有分枝定界解法及割平面解法（这里不作介绍，感兴趣的读者可参考相关书籍）。在整数规划问题中，0—1型整数规划则是其中较为特殊的一类情况，它要求决策变量的取值仅为0或1，在实际问题的讨论中，0—1型整数规划模型也对应着大量的最优决策的活动与安排讨论，我们将列举一些模型范例，以说明这个事实。
0—1型整数规划的的数学模型为：
目标函数 nnxcxcxczMinMax2211)(
约束条件为：1 | 0 ) ,() ,() ,(22112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxa, , ,21
这里，0 | 1表示0或1。
2. 0—1型整数规划模型的解法
0—1型整数规划模型的解法一般为穷举法或隐枚举法，穷举法指的是对决策变量nxxx , , ,21的每一个0或1值，均比较其目标函数值的大小，以从中求出最优解。这种方法一般适用于决策变量个数n较小的情况，当n较大时，由于n个0、1的可能组合数为n2，故此时即便用计算机进行穷举来求最优解，也几乎是不可能的。隐枚举法是增加了过滤条件的一类穷举法，该法虽能减少运算次数，但有的问题并不使用。此时，就只能用穷举法了。
3. 应用实例
例1 工程上马的决策问题
1）问题的提出 某部门三年内有四项工程可以考虑上马，每项工程的期望收益和年度费用（千元）如下表所示：假定每一项已选定的工程要在三年内完成，是确定应该上马哪些工程，方能使该部门可能的期望收益最大。
工 程 费 用
期望收益
第1年 第2年 第3年
