GUIZHOU UNIVERSITY实践报告题 目线性规划与整数规划Matlab编程与应.docx

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