文档介绍：GUIZHOU UNIVERSITY
实践报告
题 目：线性规划与整数规划
Matlab编程与应用举例
指导教师:王凯
学 院:理学院
专 业:数学与应用数学
组 员：张超 0907010283 **********
彭 勇 0907010167 **********
龙昭昌 0907010262 **********
张永勇 0907010264 **********
梁 鹏 0907010273 **********
分 工：彭勇资料收集；梁鹏、张永勇上网、查阅
相关书籍；龙昭昌、张超论文整合，编写
2011年7月12号
一、问题描述及分析
问题描述：某厂每日八小时的产量不低于1800件。为了在进行质
量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速
度25件/小时，正确率98%,计时工资4元/小时；二级检验员的标 准为：速度
15件/小时，正确率95%,计时工资3元/小时。检验员 每错检一次，工厂要损失2元。现有可供厂方聘请的检验员人数为一 级8人和二级10人，伪是总检验费用最省，该工厂应聘请一级、二 级检验员各多少名？
问题分析：由问题描述中我们可知，要使总检验费用最省，主要与 聘请一级、二级检验员的数目有关,在单向对于一级或二级检验员时, 总费用随它们成正比。不过它们可以相互谐调，各自有增有减。况且 我们知道该工厂每日的产量不低于1800件，并且由于一级、二级检 验员的水平有所差异，我们也得从他的检验速度及正确率对他们进行 评估，即一个人对该公司的价值。这样我们就可以得到它们的从有选 择，不过一级、二级检验员的人数有限，因此还得控人考虑。
二、原理与方法
整数规划
整数规划问题的应用意义
整数规划是规划论中近30年才发展起来一个重要分支。 主要是由于经济管理中的大量问题抽象为模型时，人们发现许 多量具有不可分割性，因此当它们被作为变量引入到规划中时 ,常要求满足取整条件。如生产计划中，生产机器多少台（整 数）；人力资源管理中，招聘员工多少人（整数）；运输问题中 ,从一个港口到另一个港口的集装箱调运数量（整数）；另外， 运作管理中的决策问题：如工厂选址、超市选址、人员的工作 指派、设备购置和配置等。
其规划模型中往往须引入逻辑变量（即变量仅取0或I两 个值）来反映冲突因素和抉择。因此，这些问题的规划模型不同于 前述的线性规划范畴，而属于一种新的类型——整数规划。可以毫不
夸张地说，整数规划在实践中有比线性规划更为广泛的应用空间。
2.
整数规划一般形式
max Z（或 min Z）=乏 cjxj
五—=S （z = - -m）
* /=i
Xj 00 = ---n）部分或者全部为整敷
纯整数规划、全整数规划、混合整数规划、。-1整敏 规划。
纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变
量和剩余变量可以不要求取整数）o
全整数规划：除所有决策变量要求取非负整数外，系数 如和常数灰
也要求取整数（这时引进的松弛变量和剩余变量也必须是整数）。
混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可
以取非负实数。
0 — 1整数规划：所有决策变量只能取0或1两个整数。
从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需
在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。
但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定 就是最优解，有时甚至不能保证所得倒的解是整数可行解。
分枝定界法
分枝定界法(branch and bound)是一种求解非线性整数规划问题的 常用算法。这种方法不但可以求解纯整数规划，还可以求解混合整数 规划问题。分枝定界法的步骤如下：
Stepl放宽或取消原问题的某些约束条件，如求整数解的条件。如果 这是求出的最优解是原问题的可行解，那么这个解就是原问题的最优 解，计算结束。否则这个解的目标函数值是原问题的最优解的上界(求 极大值时)。
Step 2将放宽了某些约束条件的替代问题分成若干子问题，要求 各子问题的解集合的并集要包含原问题的所有可行解，然后对每个子 问题求最优解。这些子问题的最优解中的最优者若是原问题的可行 解，则它就是原问题的最优解，计算结束。否则它的目标函数值就是 原问题的一个新的上界。另外，各子问题的最优解中，若有为原问题 的可行解的，选这些可行解的最大的目标函数值，它就是原问题最优 解的一个下界。
Step 3对最优解的目标函数值已小于这个下界的问题，其可行解中 必无原问题的最优解，可以放弃。对最优解的目标函数值大于这个下 界的子问题，都先保