运筹学OR1-Ch2-LP解法课件.ppt

1、第二章第二章 线性规划解法线性规划解法Solution of Liner Programming2-1 单纯形法及其计算步骤单纯形法及其计算步骤2-2 人工变量处理方法人工变量处理方法2-3 改进单纯形法简介改进单纯形法简介2-4 LP的计算机求解的计算机求解2-5 案例分析案例分析2-1 单纯形法及其计算步骤单纯形法及其计算步骤1.单纯形表假定经过标准化及加入松弛变量和人工变量后的线性规划模型中，其约束方程中已经存在m个线性独立的单位列向量，一般形式可以表示为：1nn11m1m11bxaxax,2nn21m1m22bxaxax,mnnm1m1mmmbxaxax,将其系数矩阵A和资源列向量b写

2、在一个矩阵中，构成系数增广矩阵：mnmmmnmnmbaabaabaa,1,2,21,21,11,11000100012022年7月29日11时37分Page 2 of 37 1.单纯形表将系数增广矩阵及目标函数方程用一个表表示单纯形表。100001002-1 单纯形法及其计算步骤单纯形法及其计算步骤jnmjijiixabx1jijmiinmjjimiixaccbcz)(111jc1cmc1mcncBCBX1xmx1mxnxb1c2cmc1x2xmx1,1ma1,2ma1,mmana,1na,2nma,1b2bmb12mj1,11mimiimaccinmiinacc1imiibc12022年7月

3、29日11时37分Page 3 of 37 2-1 单纯形法及其计算步骤单纯形法及其计算步骤2.单纯形法的计算步骤 模型标准化找初始可行基确定初始基本可行解建初始单纯形表所有?0j同时 j0存在 pj0？得到最优解，停止无最优解，停止选择进基变量kjmax选择出基变量lklikiiabab)(min以主元素lka旋转迭代，得新的单纯形表图 2-1：单纯形计算过程示意图2022年7月29日11时37分Page 4 of 37 2-1 单纯形法及其计算步骤单纯形法及其计算步骤v例2-1 用单纯形法求解例1-1v解：例1-1标准化后的模型为：5432100032maxxxxxxz82321xxx16

4、441 xx12452 xx51,0jxj列出初始单纯形表如下：Cj23000CBXBx1 x2 x3 x4 x5b000 x3 x4 x512100400100400181612cjzj2300008/2=412/4=32022年7月29日11时37分Page 5 of 37 2-1 单纯形法及其计算步骤单纯形法及其计算步骤v例2-1 用单纯形法求解例1-1Cj23000CBXBx1 x2 x3 x4 x5b003 x3 x4 x210101/24001001001/42163cjzj20003/49Cj23000CBXBx1 x2 x3 x4 x5b000 x3 x4 x512100400

5、100400181612cjzj2300008/2=412/4=32/1=216/4=42022年7月29日11时37分Page 6 of 37 2-1 单纯形法及其计算步骤单纯形法及其计算步骤v例2-1 用单纯形法求解例1-1Cj23000CBXBx1 x2 x3 x4 x5b003 x3 x4 x210101/24001001001/42163cjzj20003/49Cj23000CBXBx1 x2 x3 x4 x5b203 x1 x4 x210101/20041201001/4283cjzj00201/4138/2=43/1/4=122/1=216/4=42022年7月29日11时37分

6、Page 7 of 37 2-1 单纯形法及其计算步骤单纯形法及其计算步骤v例2-1 用单纯形法求解例1-1Cj23000CBXBx1 x2 x3 x4 x5b203 x1 x4 x210101/20041201001/4283cjzj00201/4138/2=43/1/4=12Cj23000CBXBx1 x2 x3 x4 x5b203 x1 x5 x21011/400021/21011/21/80442cjzj003/21/80142022年7月29日11时37分Page 8 of 37 2-2 人工变量处理方法人工变量处理方法v为了构造单纯形表的初始基，在有些情况下需要在模型中加入人工变量

7、。人工变量是实际问题原模型中美有的人为的虚拟变量，因而在最终解中人工变量必须等于零，即最终应为非基变量。为确保这一点，有两种方法可以实现。1.大M法在目标函数中给每一个人工变量设定一个负系数M(M为任意大正数）。下式中yi(i=1m)为人工变量mnnMyMyMyxcxcxcz212211max11nn1111byxaxa22nn2121byxaxammnmn11mbyxaxaminjyxij1;1,0,02022年7月29日11时37分Page 9 of 37 2-2 人工变量处理方法人工变量处理方法大大M法法1.大M法例2-2：用大M法求解下列线性规划解：为确定初始基，引入人工变量x5,x6

8、，模型变成为43214235maxxxxxz41j0 x10 x2x3x4x210 x8xxx5j43214321,6543214235maxMxMxxxxxz61j0 x10 xx2x3x4x210 xx8xxx5j6432154321,2022年7月29日11时37分Page 10 of 37 2-2 人工变量处理方法人工变量处理方法大大M 法法v根据上述标准型列单纯形表如下：Cj5324MMCBXBx1 x2 x3 x4 x5 x6bMM x5 x65118102432011010cjzj7M+5M+4M+10M+0020M10/810/2Cj5324MMCBXBx1 x2 x3 x4

9、x5 x6b4M x4 x65/81/81/811/803/415/411/401/415/415/2cjzj3/4M+15/4M+11/4M+05/4M0515/2M10 22022年7月29日11时37分Page 11 of 37 2-2 人工变量处理方法人工变量处理方法大大M 法法v继续上述单纯形表计算Cj5324MMCBXBx1 x2 x3 x4 x5 x6b43 x4 x23/501/3011/5111/15012cjzj201/30105/3 10Cj5324MMCBXBx1 x2 x3 x4 x5 x6b53 x1 x2101/185/30113/181/35/35/3cjzj0

10、0-4/9-10/340/3最优解为：X*=(5/3，5/3，0，0，0，0）T Z=40/32022年7月29日11时37分Page 12 of 37 2-2 人工变量处理方法人工变量处理方法两阶段法两阶段法2.两阶段法对于含有人工变量的LP的标准型，因在最终解中所有人工变量必须都是非基变量而等于零。因而可以分成两个阶段来求解：第一阶段：判断原问题是否有解首先建立一个辅助LP规划，其目标函数取所有人工变量之和，并取其极小，约束条件为加入人工变量后的原约束。myyyw21min11nn1111byxaxa22nn2121byxaxammnmn11mbyxaxam1in1j0y0 xij;,20

11、22年7月29日11时37分Page 13 of 37 2-2 人工变量处理方法人工变量处理方法两阶段法两阶段法v对辅助线性规划问题的求解结果有两种情况：1)目标函数值等于零。它说明所有的人工变量都等于零，即所有的人工变量都变成了非基变量。同时也表明了原问题已得到了一个基本可行解它所对应的基恰好是一个单位阵。由此就可以转入第二阶段继续迭代。2)目标函数值大于零。它说明至少有一个人工变量不能从基变量中替换出来。于是，原问题没有可行解，停止计算。第二阶段：求原问题的最优解。对于上述第一种情况，在当前基中不含有人工变量，将目标函数变为原问题的目标函数，在单纯形表中将价值系数行换为原问题的价值系数。划

12、去人工变量所在的列即得到原问题的初始单纯形表。然后重新求检验数，继续迭代，直到求得原问题的最优解。2022年7月29日11时37分Page 14 of 37 2-2 人工变量处理方法人工变量处理方法两阶段法两阶段法v例2-3：用两阶段法解例2-2解：对原模型加入人工变量后，构造辅助线性规划如下：61j0 x10 xx2x3x4x210 xx8xxx5j6432154321,65minxxwCj000011CBXBx1 x2 x3 x4 x5 x6b11 x5 x65118102432011010cjzj75410002010/810/22022年7月29日11时37分Page 15 of 37

13、 2-2 人工变量处理方法人工变量处理方法两阶段法两阶段法v例2-3：用两阶段法解例2-2（续）Cj000011CBXBx1 x2 x3 x4 x5 x6b01 x4 x65/81/81/811/803/415/411/401/415/415/2cjzj3/415/411/405/4015/210 2Cj000011CBXBx1 x2 x3 x4 x5 x6b00 x4 x23/501/3012/151/301/5111/1501/154/1512cjzj00001105/3 10第一阶段结束，用此单纯形表换成原目标函数的价值系数，继续求解：2022年7月29日11时37分Page 16 of

14、 37 2-2 人工变量处理方法人工变量处理方法两阶段法两阶段法v例2-3：用两阶段法解例2-2（续）Cj5324CBXBx1 x2 x3 x4 x5 x6b43 x4 x23/501/3011/5111/15012cjzj000005/3 10Cj5324CBXBx1 x2 x3 x4 x5 x6b53 x1 x2101/185/30113/181/35/35/3cjzj00-4/9-10/340/3最优解为：X*=(5/3，5/3，0，0，0，0）T Z=40/32022年7月29日11时37分Page 17 of 37 2-2 人工变量处理方法人工变量处理方法两阶段法两阶段法v注意：退化

15、解的处理v当我们采用规则确定出基变量时，有可能存在两个或两个以上相同的最小值，选定其中一个所对应的基变量出基，这样，在得到的新的基本可行解中除了非基变量等于零之外，还有一个或一个以上的基变量等于零。这就出现了所谓退化解。在这种情况下，如果用单纯形表求解时处理不当，有可能出现死循环。为解决这一问题，已经提出了一些方法，如“摄动法”、“辞典序法”等等。还有一种简便的方法称为勃兰特法，其规则如下：1)选取中下标最小的非基变量进基；2)当按规则计算存在两个或两个以上最小值时，选取下标最小的基变量出基。0jjjzc2022年7月29日11时37分Page 18 of 37 2-3 改进单纯形法简介改进单

16、纯形法简介1.单纯形法的矩阵描述 用矩阵来描述单纯形法有助于对这一方法进一步的理解。0maxXbAXCXz0,00maxsssXXbIXAXXCXz标准化为求解此标准型线性规划问题，对上式作如下分解：),(),(NBIA),(),(NBSXXXX),(),(NBCC0C则上述标准型变为：NNBBTNBNBXCXCXXCCMaxZ),)(,(bNXBXXXNBNBTNB),)(,(0,NBXX2022年7月29日11时37分Page 19 of 37 2-3 改进单纯形法简介改进单纯形法简介单纯形法的矩阵描述 v对约束式移项得：v左乘B-1得：v代入目标函数得：v v若令非基变量 XN=0得：v

17、对LP的矩阵表述讨论：1)检验数：2)规则表达式：NBNXbBXNBNXBbBX11NNNBBXCNXBCbBCZ11NBNBXNBCCbBC)(11bBXB1bBCZB1NBCC1BN非基变量：0CCBBCCBB1BB基变量：1BBC松弛变量：ABCC1B整体表达：ljlijijiiPBbBPBPBbB)()(0)(|)()(min111112022年7月29日11时37分Page 20 of 37 2-3 改进单纯形法简介改进单纯形法简介单纯形法的矩阵描述 v对LP的矩阵表述讨论：3)矩阵单纯形表：将非基变量所对应的系数矩阵N分为N1和NS两部分，其中NS是对应于松弛变量的部分，则上述目标

18、函数表述为：S1N1NBBX0XCXCZbBXBXNBX1S11N11BS1B1N11BN1BXBCXNBCCbBCZ)(bIXXNBXS1N1B2022年7月29日11时37分Page 21 of 37 2-3 改进单纯形法简介改进单纯形法简介单纯形法的矩阵描述 3)矩阵单纯形表：将上述式写成单纯形表的形式如下：非基变量基变量BX1NXSXI11NB1BbB1011NBCCBN1BCBbBCB1对应于松弛变量的矩阵为基矩阵的逆阵检 验数行2022年7月29日11时37分Page 22 of 37 2-3 改进单纯形法简介改进单纯形法简介改进单纯形法流程图改进单纯形法流程图2.改进单纯形法流程

19、图对于小型的线性规划模型用单纯形法，手工求解还是比较方便的，但我们也发现每次迭代都需计算很多无关的数字，对于大型的线性规划模型，不但手工解比较困难，就是借助计算机也会占用更多的空间和时间。为适应计算机计算的需要，提出一种改进的办法改进单纯形法 输入的原始数据有：),(21ncccCTmbbbb),(21mnmmnnaaaaaaaaaA2122221112112022年7月29日11时37分Page 23 of 37 2-3 改进单纯形法简介改进单纯形法简介改进单纯形法开始输入原始数据矩阵确定IBB100计算1kBBC计算NBCCKBN1?0计算bBK1及bBCKB1并输出停确定进基变量qx计算

20、qkPB1?01qkPB确定出基变量lx计算新基逆矩阵111klkBEB计算矩阵lE1 kk赋值 K=0是否是否图 2-2：改进单纯形法流程图2022年7月29日11时37分Page 24 of 37 2-3 改进单纯形法简介改进单纯形法简介改进单纯形法v运算过程中的主要矩阵有：lkEB,1TmqqqqkaaaPB),(2111000100011lqmqlqlqqlaaaaaE1mqlqqaaa01001011lqmqlqlqqaaaaaXq列变基前后Xl列变基前后变基后的Xl列2022年7月29日11时37分Page 25 of 37 2-4 线性规划的软件求解线性规划的软件求解vExcel

21、电子表格中的工具菜单中有一个“规划求解”选项，它可以通过简单的程序方法在一个表格中求解线性规划模型。v首先检查你的Excel工具菜单中是否有“规划求解”项，如果没有该项，则通过“加载宏”选项添加。1.在电子表格中建立线性规划模型在电子表格中建立线性规划模型把线性规划模型转化为Excel电子表格文件形式。其表现形式可以多种多样，但应保持模型的组织性、逻辑性、直观性、易操作性。为此，把制作表格的过程分成四个部分：数据、决策变量、数据、决策变量、目标方程、约束。目标方程、约束。1)数据部分：数据是模型处理的基础，原始数据通过计算而生成其他数据，为了便于数据的使用，应尽可能将数据集中安排在一个便于组织

22、的表格中；2022年7月29日11时37分Page 26 of 37 线性规划的软件求解线性规划的软件求解2)决策变量：决策变量通过名称等对元素加以区分，并将最优计算结果填入其中，为此，每一个单元格对应一个决策变量，并在决策变量的上面或旁边设置说明文字来进行标记，以便于区别。3)目标方程：该部分包括目标价值所必要的元素，目标方程中将含有数据部分的数据和未知的决策变量值（相应的单元格为值）。4)约束方程：通常将每一个约束分成LHS和RHS放在两格单元格中，通过相应的运算符号对其加以限制，任何常量和决策变量元素的结合均可加入到约束中，但对于每一个约束而言，LHS和RHS都必须非空（至少有一个元素）

23、，包括非负条件在内。一个较好的处理方法就是将LHS作为一列，而将RHS作为相邻的另一列。2022年7月29日11时37分Page 27 of 37 线性规划的软件求解线性规划的软件求解2.在电子表格中优化线性规划模型1)首先将基础数据、决策变量、目标方程、约束条件输入工作部中。2)在工具菜单中选择规划求解命令将出现规划求解参数窗口。在设置目标单元个未知输入目标单元格；选定最大或最小；在可变单元格中输入决策变量单元格；3)点击添加按钮出现添加约束对话框，在单元格引用位置输入约束的LHS，选择约束符号类型，在约束值位置输入相应的RHS，如此重复添加各个约束条件；4)点击选项按钮进入规划求解选项框，

24、选定采用线性模型和假定非负选项框，然后点击确定；5)点击求解按钮进入规划求解结果对话框，选定保存规划求解结果复选框，点击确定按钮则得到求解的结果。2022年7月29日11时37分Page 28 of 37 线性规划的软件求解线性规划的软件求解v管理运筹学软件1.0版使用说明：（演示例1）一、系统的进入与退出：1、在WINDOWS环境下直接运行main.exe文件，或者在DOS下UCDOS中文平台环境下运行，也可直接运行各可执行程序。2、退出系统的方法可以在主菜单中选退出项，也可按Ctrl+Break键直接退出。3、在WINDOWS环境下直接运行软件，如果出现乱码，那是因为启用了全屏幕方式，解决

25、办法是按ALT+ENTER键，即可转换成非全屏的界面（一般就会消除乱码，如果还是乱码，可以点击菜单的“汉”选项）；若要每次启动程序都没有乱码，则需要修改屏幕设置的相应属性。具体方法是：在非全屏界面下点击菜单的“属性”选项，再选择“窗口”选项，然后选中其中的“窗口”项，并取消“启动时恢复设置”项，这样就可保证每次运行软件时以非全屏方式显示。二、输入部分：1、线性规划、整数规划的目标函数和约束的输入必须按由小到大的序号顺序输入，同时约束变量必须放在运算 符的左侧。如（x1+x2-x3=0，不能输为x2-x3+x1=0；x1-x2+x3=0，不能输为x1+x3=x2）2、输入的约束中不包括=或或=2

26、,则输入 X12,而不是X1=2。2022年7月29日11时37分Page 29 of 37 线性规划的软件求解线性规划的软件求解结果考察：（演示例1）1、当目标函数的系数 ci 单一变化时，只要不超过其上、下限，最优解不变；2、当约束条件中右边系数 bj 变化时，当其不超过上、下限，对偶价格不变（最优解仍是原来几个线性方程的解）；3、当有多个系数变化时，需要进一步讨论。百分之一百法则：对于所有变化的目标函数决策系数（约束条件右边常数值），当其所有允许增加的百分比与允许减少的百分比之和不超过100%时，最优解不变（对偶价格不变，最优解仍是原来几个线性方程的解）*允许增加量=上限-现在值 c1

27、的允许增加量为 100-50=50 b1 的允许增加量为 325-300=25 *允许减少量=现在值-下限 c2 的允许减少量为 100-50=50 b3 的允许减少量为 250-200=50 *允许增加的百分比=增加量/允许增加量 *允许减少的百分比=减少量/允许减少量 2022年7月29日11时37分Page 30 of 37 2-5 案例分析案例分析案例1：贝德福德钢铁公司(NBS)采购问题的研究（教材P.238241)，NBS是一个位于宾夕法尼亚洲的贝福德钢材生产企业。焦煤是生产钢材的一种必不可少的原材料。NBS每年需1.01.5亿吨的焦煤，现在正是制定明年生产计划的时间。斯蒂芬考金斯

28、NBS公司煤炭供应经理，已经收到了八家煤矿公司关于明年需求的投标书。下表显示了这八家有可能获得煤炭供应订货单的煤炭供应商的有关信息。艾什贝德康艘丹比埃尔佛罗加斯豪伯价格（$/吨）49.550.061.063.566.571.072.580.0联合/非联合联合联合非联合联合非联合联合非联合非联合卡车/火车火车卡车火车卡车卡车卡车火车火车挥发性（%）1516182021222325生产能力3006005106555756804504902022年7月29日11时37分Page 31 of 37 案例分析案例分析v根据市场预测及对去年的生产特征的分析，NBS决定在未来一年里共接受1225千吨的焦煤供

29、应量，这些焦煤必须至少具有19%的挥发性。而且，为了抵消劳动关系中的不利因素，NBS决定从联合型（美国煤矿工人联合体）煤矿订购至少占总量的50%的焦煤。最后，斯蒂芬考金斯还必须考虑每年火车运煤的最大能力是650千吨，卡车运煤的最大运输能力是720千吨。v斯蒂芬考金斯对以下三个方面的问题比较感兴趣：a)NBS应从每个供应商那里订购多少焦煤才能保证用于焦煤采购的成本达到最少？b)NBS用于采购的总成本是多少？c)NBS用于采购的平均成本是多少？2022年7月29日11时37分Page 32 of 37 案例分析案例分析v焦煤供应问题的线性规划模型：v设NBS从艾什勒到豪伯特各个供应商的供应量分别为

30、A、B、C、D、E、F、G、H，则v总费用=49.5A+50B+61C+63.5D+66.5E+71F+72.5G+80Hv约束：供应量：A+B+C+D+E+F+G+H=1225供应商性质：A+B+D+FC+E+G+H卡车运力：B+D+E+F720火车运力：A+C+G+H650挥发性19%：4A3BC+2E+3F+4G+6H0(整理结果）生产能力：A300;B600;C510;D655;E575;F680;G450;H490非负条件：所有变量非负求解见Excel文件：线性规划案例1。2022年7月29日11时37分Page 33 of 37 案例分析案例分析案例2：杰姆斯托恩工具公司的生产计划

31、问题(MBA教材p.241243),求解见Excel文件：线性规划案例2杰姆斯托恩公司（GTC)是一个私人公司，以生产建筑工具在消费者和工业市场竞争中生存。位于华盛顿州西雅图的工厂是它的主要制造工厂，除此之外，GTC还操纵着其它七家分布于美国、加拿大和墨西哥的工厂。这些工厂生产的全部类型产品，包括钢钻、电锯、射钉枪和手动工具，如锤子、改锥、扳手和钳子。扳手和钳子是钢制的，制作过程包括用机械模生成工具模型，然后在装配机器上装配工具。生产扳手和钳子消耗钢材的总量和每天钢材的总量如下表：扳手钳子生产能力钢材（磅）1.51.027,000磅/天模型机械（小时）1.01.021,000小时/天装配机械（

32、小时）0.30.59,000小时/天需求量（个/天）15,00016,000利润（$/1000个）$130$1002022年7月29日11时37分Page 34 of 37 案例分析案例分析vGTC生产问题的线性规划模型v设钳子和扳手的日生产量分别为W、P，单位为千目标方程Max:130W+100P约束：钢材：1.5W+1.0P27模型：1.0W+1.0P21装配：0.3W+0.5P9需求量：W15;P16非负约束：W,P0求解见Excel文件：线性规划案例22022年7月29日11时37分Page 35 of 37 案例分析案例分析案例3：本章例1的求解。（见线性规划案例3）2022年7月29日11时37分Page 36 of 37 本章结束本章结束谢谢谢谢