IE10_OR05 CH1 线性规划及单纯形法5

第1页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学第5讲目录CH1线性规划及单纯形法§1.1线性规划问题及其数学模型§1.2线性规划问题的解§1.3线性规划的单纯形法1.3.1单纯形法的基本思路1.3.2确定初始基可行解1.3.3最优性检验1.3.4基可行解的转换1.3.5单纯形法的步骤§1.4单纯形表§1.5单纯形法应用的几个问题§1.6线性规划建模举例西南科技大学制造学院IE系小结：线性规划求解流程图（P35)第3页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学§1.5单纯形法应用的几个问题1.5.1大M法和两阶段单纯形法1.5.2退化第4页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学1.5.2退化若用θ规则确定换出变量时，有时存在两个以上的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。当出现退化解时，会出现循环。1974年勃兰特(Bland)提出了一种简便规则：(1)选取j0中下标最小的非基变量xk为换入变量k=min(j|j0)(2)当按θ规则计算存在两个和两个以上最小比值时，始终选取下标最小的基变量换出变量。第5页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学§1.6线性规划建模举例线性规划技术应用广泛：军事、工业、农业…财富500强公司中，有85%使用线性规划技术帮助决策．企业决策：生产计划、运输、财务、营销…建模步骤：1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（x1，x2，…，xn），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件第6页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学线性规划求解工具简介ExcelSolverLindoLinearInteractiveandDiscreteOptimizer字首的缩写，即“交互式的线性和离散优化求解器”LingoLinearInteractiveandGeneralOptimizer字首的缩写，即“交互式的线性和通用优化求解器”Matlab……第7页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学LINDO,可以用来求解线性规划(LP--LinearProgramming)、整数规划(IP--IntegerProgramming)和二次规划(QP--QuadraticProgramming)问题.这套软件包由美国芝加哥大学的LinusScharge教授于1980年前后开发，专门用于求解最优化问题，后经不断完善和扩充，并成立LINDO公司进行商业化运作，取得了巨大的成功。全球《财富》杂志500强的企业中，一半以上使用该公司产品，其中前25强企业中有23家使用该产品。该软件包功能强大，版本也很多，而我们使用的只是演示版（试用版），演示版与正式版功能基本上是类似的，只是能够求解问题的规模受到限制，总变量数不超过30个，这在我们目前的使用过程中，基本上是足够。第8页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学初试LINDOLINDO中己假设所有的变量都是非负的,所以非负约束条件不必再输入到计算机中;LINDO也不区分变量中的大小写字符;约束条件中的“=”及“=”可用“”及“”代替.解决一个简单的线性规划（LP）问题23431035120maxzxyxys.t.xyx,y《其Lindo程序为：例现在我们用Lindo软件来求解这个模型，单击工具栏中的图标，便得到以下运行状态窗口：Lindo求解器运行状态窗口各项的含义名称含义Status显示当前求解状态：Optimal表示已经达到最优解；其他可能的显示：Feasible，Infeasible，UnboundedIterations显示迭代次数Infeasibility约束不满足的量；0表示这个解是可行的Objective显示当前解的目标函数值BestIP显示整数规划当前解的最佳标函数值：N/A表示无答案或无意义IPBound显示整数规划的界Branches显示分支定界算法已经计算的分支数：N/A表示无答案或无意义ElapsedTime显示计算所用时间：0：00说明计算太快，用时还不到0.05SUpdateTime显示控制和刷新本界面的时间间隔InterruptSolver中断求解程序Close关闭该窗口添加Lindo求解器显示结果如下•单纯行法迭代两次得到最优解•最优目标值•最优解各变量的值•对偶价格•影子价格：表示该非基变量增加一个单位而其他变量不变时目标函数减少的量（对max型问题）•松弛变量的值【紧约束】•单纯行法进行两次迭代①变量以字母开头、不区分大小写，变量名可不超过8个字符；②变量不能出现在约束条件的右端，右端只能是常数；变量与系数之间可以有空格，但绝对不能有任何运算符；③Lindo中不接受”（）“和逗号”，“等任何运算符号（除非在注释语句中）；④模型中的表达式应当经过化，如不能出现（X+1）2+2X2+3Y，而应该写成3X2+2X+3Y+1；⑤模型中已假定所有变量非负，可在模型的”end“语句后面用命令”free“取消变量的非负假定，其用法是在”free“后面跟变量名；⑥在模型的”end“语句后面可以用命令”SUB“设定变量的上界，用命令”SLB“设定变量的下界；⑦Lindo中以“！”开始的是说明语句，说明语句也以“;”结束。使用Lindo软件的一些注意事项：第13页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学例有一家具制造车间,制造书桌(DESK)、桌子(TABLE)、椅子(CHAIR),所用原料及木工、漆工的数据如表1所示.每个书桌每个桌子每个椅子资源总数木料8单位6单位1单位48单位漆工4单位2单位1.5单位20单位木工2单位1.5单位0.5单位8单位成品单价60单位30单位20单位表1第14页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学若要求桌子的生产量不超过5件,问如何安排三种产品的产量可使收入最大?用分别表示书桌、桌子、椅子的生产量.建立LP模型:321,,xxx321203060maxxxxZ05,,85.05.12205.12448683221321321321xxxxxxxxxxxxxLPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1)280.00000VARIABLEVALUEREDUCEDCOSTXI2.000000.000000X2.0000005.000000X38.000000.000000ROWSLACKORSURPLUSDUALPRICES2)24.000000.0000003).00000010.0000004).00000010.0000005)5.000000.000000LINDO在2次迭代后得到最优解。最优目标值802321xxx最优解带有松弛变量的最优解500248027654321xxxxxxx检验数第16页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学例1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?班次时间所需人数16：00——10：0060210：00——14：0070314：00——18：0060418：00——22：0050522：00——2：002062：00——6：0030Ⅰ人力资源分配的问题解：设xi表示第i班次时开始上班的司机和乘务人员数,这样建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6约束条件：s.t.x1+x6≥60x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30x1,x2,x3,x4,x5,x6≥0班次时间所需人数16：00——10：0060210：00——14：0070314：00——18：0060418：00——22：0050522：00——2：002062：00——6：0030第18页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学例2．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？时间所需售货员人数星期日28星期一15星期二24星期三25星期四19星期五31星期六28解：设xi(i=1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6+x7约束条件：s.t.x1+x2+x3+x4+x5≥28x2+x3+x4+x5+x6≥15x3+x4+x5+x6+x7≥24x4+x5+x6+x7+x1≥25x5+x6+x7+x1+x2≥19x6+x7+x1+x2+x3≥31x7+x1+x2+x3+x4≥28x1,x2,x3,x4,x5,x6,x7≥0时间所需售货员人数星期日28星期一15星期二24星期三25星期四19星期五31星期六28第20页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学例3．某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？甲乙丙资源限制铸造工时(小时/件)51078000机加工工时(小时/件)64812000装配工时(小时/件)32210000自产铸件成本(元/件)354外协铸件成本(元/件)56--机加工成本(元/件)213装配成本(元/件)322产品售价(元/件)231816Ⅱ生产计划的问题解：设x1,x2,x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。求xi的利润：利润=售价-各成本之和:产品甲全部自制的利润=23-(3+2+3)=15产品甲铸造外协，其余自制的利润=23-(5+2+3)=13产品乙全部自制的利润=18-(5+1+2)=10产品乙铸造外协，其余自制的利润=18-(6+1+2)=9产品丙的利润=16-(4+3+2)=7可得到xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。甲乙丙资源限制铸造工时(小时/件)51078000机加工工时(小时/件)64812000装配工时(小时/件)32210000自产铸件成本(元/件)354外协铸件成本(元/件)56--机加工成本(元/件)213装配成本(元/件)322产品售价(元/件)231816通过以上分析,可建立如下的数学模型:目标函数：Max15x1+10x2+7x3+13x4+9x5约束条件：5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0甲乙丙资源限制铸造工时(小时/件)51078000机加工工时(小时/件)64812000装配工时(小时/件)32210000自产铸件成本(元/件)354外协铸件成本(元/件)56--机加工成本(元/件)213装配成本(元/件)322产品售价(元/件)231816第23页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学例4某工厂要做100套