IE10OR05 CH1 线性规划及单纯形法

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 线性规划建模举例,小结：线性规划求解流程图（P35),1.5 单纯形法应用的几个问题,1.5.1 大M法和两阶段单纯形法 1.5.2 退化,1.5.2退化,若用规则确定换出变量时，有时存在两个以上的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解

2、。当出现退化解时，会出现循环。 1974年勃兰特(Bland)提出了一种简便规则： (1) 选取j0中下标最小的非基变量xk为换入变量k=min(j| j0) (2)当按规则计算存在两个和两个以上最小比值时，始终选取下标最小的基变量换出变量。,1.6 线性规划建模举例,线性规划技术应用广泛：军事、工业、农业 财富500强公司中，有85%使用线性规划技术帮助决策企业决策：生产计划、运输、财务、营销 建模步骤： 1.理解要解决的问题，了解解题的目标和条件； 2.定义决策变量（ x1 ，x2 ， ，xn ），每一组值表示一个方案； 3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；

3、4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件,线性规划求解工具简介,Excel Solver Lindo Linear Interactive and Discrete Optimizer字首的缩写，即“交互式的线性和离散优化求解器” Lingo Linear Interactive and General Optimizer字首的缩写，即“交互式的线性和通用优化求解器” Matlab ,LINDO,可以用来求解线性规划(LP-Linear Programming )、整数规划( IP -Integer Programming )和 二次规划(QP-Quadratic

4、Programming )问题. 这套软件包由美国芝加哥大学的Linus Scharge教授于1980年前后开发，专门用于求解最优化问题，后经不断完善和扩充，并成立LINDO公司进行商业化运作，取得了巨大的成功。全球财富杂志500强的企业中，一半以上使用该公司产品，其中前25强企业中有23家使用该产品。 该软件包功能强大，版本也很多，而我们 使用的只是演示版（试用版），演示版与正式版功能基本上是 类似的，只是能够求解问题的规模受到限制，总变量数不超过30个，这在我们目前的使用过程中，基本上是足够。,初试 LINDO,LINDO 中己假设所有的变量都是非负的,所以非负约束条件不必再输入到计算机中

5、; LINDO 也不区分变量中的大小写字符 ; 约束条件中的“=” 可用“” 代替.,解决一个简单的线性规划（LP）问题,其Lindo程序为：,例,现在我们用Lindo软件来求解这个模型，单击工具栏中的 图标，便得到以下运行状态窗口：,添加Lindo求解器,显示结果如下,单纯行法迭代两次得到最优解,最优目 标值,最优解各变量 的值,对偶价格,影子价格： 表示该非基变量增加一个单位而其他变量不变时目标函数减少的量（对max型问题）,松弛变量的值【紧约束】,单纯行法进行两次迭代,变量以字母开头、不区分大小写，变量名可不超过8个字符； 变量不能出现在约束条件的右端，右端只能是常数；变量与系数之间可以

6、有空格，但绝对不能有任何运算符； Lindo中不接受”（）“和逗号 ”，“等任何运算符号（除非在注释语句中）； 模型中的表达式应当经过化，如不能出现 （X+1）2 + 2X2 + 3Y，而应该写成3X2+2X+3Y+1； 模型中已假定所有变量非负，可在模型的 ”end“语句后面用命令”free“取消变量的非负假定，其用法是在”free“后面跟变量名； 在模型的 ”end“语句后面可以用命令”SUB“设定变量的上界，用命令”SLB“设定变量的下界； Lindo中以“！”开始的是说明语句，说明语句也以“ ;” 结束。,使用Lindo软件的一些注意事项：,例 有一家具制造车间,制造书桌(DESK)、

7、桌子(TABLE)、 椅子(CHAIR), 所用原料及木工、漆工的数据如表1所示 .,表 1,若要求桌子的生产量不超过 5 件,问如何安排三种产品的 产量可使收入最大 ?,用 分别表示书桌、桌子、椅子的生产量.建立LP 模型 :,LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 280.00000 VARIABLE VALUE REDUCED COST XI 2.000000 .000000 X2 .000000 5.000000 X3 8.000000 .000000 ROW SLACK OR SURPLUS DUAL PRICES

8、 2) 24.000000 .000000 3) .000000 10.000000 4) .000000 10.000000 5) 5.000000 .000000,LINDO在2次迭代后得到最优解。,最优目标值,最优解,带有松弛变量的最优解,检验数,例1某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?, 人力资源分配的问题,解：设 xi 表示第i班次时开始上班的司机和乘务人员数,这样建立如下的数学模型。 目标函数： Min x1 + x

9、2 + x3 + x4 + x5 + x6 约束条件：s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 0,例2一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？,解：设 xi ( i = 1,2,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。 目标函数： Min x1 + x2 +

10、x3 + x4 + x5 + x6 + x7 约束条件： s.t. x1 + x2 + x3 + x4 + x5 28 x2 + x3 + x4 + x5 + x6 15 x3 + x4 + x5 + x6 + x7 24 x4 + x5 + x6 + x7 + x1 25 x5 + x6 + x7 + x1 + x2 19 x6 + x7 + x1 + x2 + x3 31 x7 + x1 + x2 + x3 + x4 28 x1,x2,x3,x4,x5,x6,x7 0,例3某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙

11、两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？,生产计划的问题,解：设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5 分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。求 xi 的利润：利润 = 售价 - 各成本之和: 产品甲全部自制的利润=23-(3+2+3)=15 产品甲铸造外协，其余自制的利润 =23-(5+2+3)=13 产品乙全部自制的利润 =18-(5+1+2)=10 产品乙

12、铸造外协，其余自制的利润 =18-(6+1+2)=9 产品丙的利润=16-(4+3+2)=7 可得到 xi （i = 1,2,3,4,5） 的利润分别为 15、10、7、13、9 元。,通过以上分析,可建立如下的数学模型: 目标函数： Max 15x1 + 10 x2 + 7x3 + 13x4 + 9x5 约束条件： 5x1 + 10 x2 + 7x3 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 12000 3x1 + 2x2 + 2x3 + 3x4 + 2x5 10000 x1,x2,x3,x4,x5 0,例4 某工厂要做100套钢架，每套用长为2.9 m,2.1 m,

13、1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？ 解： 共可设计下列5 种下料方案，见下表,设 x1,x2,x3,x4,x5 分别为上面 5 种方案下料的原材料根数。这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 约束条件： s.t. x1 + 2x2 + x4 100 2x3 + 2x4 + x5 100 3x1 + x2 + 2x3 + 3x5 100 x1,x2,x3,x4,x5 0,套裁下料问题,用“运筹学”软件计算得出最优下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。 即 x1

14、=30; x2=10； x3=0； x4=50； x5=0； 只需90根原材料就可制造出100套钢架。 注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。,投资问题,例5 某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项 目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第 一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额 不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140

15、%，但规 定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本 利155%，但规定最大投资额不能超过100万元。 据测定每万元每次投资的风险指数如右表： 问： a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？ b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？,解： 1）确定决策变量：连续投资问题 设 xij ( i = 15，j = 14)表示第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量： A x11 x21 x3

16、1 x41 x51 B x12 x22 x32 x42 C x33 D x24,2）约束条件： 第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是 x11+ x12 = 200； 第二年：B次年末才可收回投资，故第二年年初有资金1.1 x11，于是 x21 + x22+ x24 = 1.1x11； 第三年：年初有资金 1.1x21+ 1.25x12，于是 x31 + x32+ x33 = 1.1x21+ 1.25x12； 第四年：年初有资金 1.1x31+ 1.25x22，于是 x41 + x42 = 1.1x31+ 1.25x22； 第五年：年初有资金 1.1x41+ 1.25

17、x32，于是 x51 = 1.1x41+ 1.25x32； B、C、D的投资限制： xi2 30 ( i =1、2、3、4 )，x33 80，x24 100 3）目标函数及模型： a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33 = 1.1x21+ 1.25x12； x41 + x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32； xi2 30 ( i =1、2、3、4 )，x33 80，x24 1

18、00 xij 0 ( i = 1、2、3、4、5；j = 1、2、3、4）,投资问题,b)所设变量与问题a相同，目标函数为风险最小，有 Min f =x11+x21+x31+x41+x51+3(x12+x22+x32+x42)+4x33+5.5x24 在问题a的约束条件中加上“第五年末拥有资金本利在330万元”的条件， 于是模型如下： Min f = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33 = 1.1x21+

19、1.25x12； x41 + x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32； xi2 30 ( i =1、2、3、4 )，x33 80，x24 100 1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 330 xij 0 ( i = 1、2、3、4、5；j = 1、2、3、4）,投资问题,教材例题:P40P42 配料问题 生产存贮问题,第1章 线性规划与单纯形法 （小结）,1.线性规划的概念 （1）线性规划模型的构成 决策变量 目标函数：max(min) Z(是决策变量的线性函数） 约束条件：s.t. （满足于含决策变量的线性等式或不等式）,（2）一般形式：,max =c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn=b1 a21x1+a22