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

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

2、其计算步骤单纯形法的计算步骤 *Page 4 of 37 2-1 单纯形法及其计算步骤例2-1 用单纯形法求解例1-1解：例1-1标准化后的模型为：列出初始单纯形表如下： Cj 2 3 0 0 0 CBXB x1 x2 x3 x4 x5 b 0 0 0 x3 x4 x5 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 8 16 12 cjzj 2 3 0 0 0 08/2=412/4=3*Page 5 of 37 2-1 单纯形法及其计算步骤例2-1 用单纯形法求解例1-1 Cj 2 3 0 0 0 CBXB x1 x2 x3 x4 x5 b 0 0 3 x3 x4 x2 1 0

3、1 0 1/2 4 0 0 1 0 0 1 0 0 1/4 2 16 3 cjzj 2 0 0 0 3/4 9 Cj 2 3 0 0 0 CBXB x1 x2 x3 x4 x5 b 0 0 0 x3 x4 x5 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 8 16 12 cjzj 2 3 0 0 0 08/2=412/4=32/1=216/4=4*Page 6 of 37 2-1 单纯形法及其计算步骤例2-1 用单纯形法求解例1-1 Cj 2 3 0 0 0 CBXB x1 x2 x3 x4 x5 b 0 0 3 x3 x4 x2 1 0 1 0 1/2 4 0 0 1 0 0

4、 1 0 0 1/4 2 16 3 cjzj 2 0 0 0 3/4 9 Cj 2 3 0 0 0 CBXB x1 x2 x3 x4 x5 b 2 0 3 x1 x4 x2 1 0 1 0 1/2 0 0 4 1 2 0 1 0 0 1/4 2 8 3 cjzj 0 0 2 0 1/4 138/2=43/1/4=122/1=216/4=4*Page 7 of 37 2-1 单纯形法及其计算步骤例2-1 用单纯形法求解例1-1 Cj 2 3 0 0 0 CBXB x1 x2 x3 x4 x5 b 2 0 3 x1 x4 x2 1 0 1 0 1/2 0 0 4 1 2 0 1 0 0 1/4 2

5、 8 3 cjzj 0 0 2 0 1/4 138/2=43/1/4=12 Cj 2 3 0 0 0 CBXB x1 x2 x3 x4 x5 b 2 0 3 x1 x5 x2 1 0 1 1/4 0 0 0 2 1/2 1 0 1 1/2 1/8 0 4 4 2 cjzj 0 0 3/2 1/8 0 14*Page 8 of 37 2-2 人工变量处理方法为了构造单纯形表的初始基，在有些情况下需要在模型中加入人工变量。人工变量是实际问题原模型中美有的人为的虚拟变量，因而在最终解中人工变量必须等于零，即最终应为非基变量。为确保这一点，有两种方法可以实现。大M法在目标函数中给每一个人工变量设定一个

6、负系数M(M为任意大正数）。下式中yi (i=1m)为人工变量*Page 9 of 37 2-2 人工变量处理方法大M法大M法例2-2：用大M法求解下列线性规划解：为确定初始基，引入人工变量x5,x6，模型变成为*Page 10 of 37 2-2 人工变量处理方法大M 法根据上述标准型列单纯形表如下： Cj 5 3 2 4 M M CBXB x1 x2 x3 x4 x5 x6 b MM x5 x6 5 1 1 8 1 0 2 4 3 2 0 1 10 10 cjzj7M+ 5M+ 4M+ 10M+ 0 0 20M10/810/2 Cj 5 3 2 4 M M CBXB x1 x2 x3 x4

7、 x5 x6 b 4M x4 x6 5/8 1/8 1/8 1 1/8 0 3/4 15/4 11/4 0 1/4 1 5/4 15/2 cjzj3/4M+ 15/4M+ 11/4M+ 0 5/4M 0 515/2M10 2*Page 11 of 37 2-2 人工变量处理方法大M 法继续上述单纯形表计算 Cj 5 3 2 4 M M CBXB x1 x2 x3 x4 x5 x6 b 4 3 x4 x2 3/5 0 1/30 1 1/5 1 11/15 0 1 2 cjzj 2 0 1/3 0 105/3 10 Cj 5 3 2 4 M M CBXB x1 x2 x3 x4 x5 x6 b 5

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

9、的求解结果有两种情况： 目标函数值等于零。它说明所有的人工变量都等于零，即所有的人工变量都变成了非基变量。同时也表明了原问题已得到了一个基本可行解它所对应的基恰好是一个单位阵。由此就可以转入第二阶段继续迭代。 目标函数值大于零。它说明至少有一个人工变量不能从基变量中替换出来。于是，原问题没有可行解，停止计算。 第二阶段：求原问题的最优解。对于上述第一种情况，在当前基中不含有人工变量，将目标函数变为原问题的目标函数，在单纯形表中将价值系数行换为原问题的价值系数。划去人工变量所在的列即得到原问题的初始单纯形表。然后重新求检验数，继续迭代，直到求得原问题的最优解。 *Page 14 of 37 2-

10、2 人工变量处理方法两阶段法例2-3：用两阶段法解例2-2解：对原模型加入人工变量后，构造辅助线性规划如下： Cj 0 0 0 0 1 1 CBXB x1 x2 x3 x4 x5 x6 b 1 1 x5 x6 5 1 1 8 1 0 2 4 3 2 0 1 10 10 cjzj 7 5 4 10 0 0 2010/810/2*Page 15 of 37 2-2 人工变量处理方法两阶段法例2-3：用两阶段法解例2-2（续） Cj 0 0 0 0 1 1 CBXB x1 x2 x3 x4 x5 x6 b 0 1 x4 x6 5/8 1/8 1/8 1 1/8 0 3/4 15/4 11/4 0 1

11、/4 1 5/4 15/2 cjzj3/4 15/4 11/4 0 5/4 0 15/210 2 Cj 0 0 0 0 1 1 CBXB x1 x2 x3 x4 x5 x6 b 0 0 x4 x2 3/5 0 1/30 1 2/15 1/30 1/5 1 11/15 0 1/15 4/15 1 2 cjzj 0 0 0 0 1 1 05/3 10第一阶段结束，用此单纯形表换成原目标函数的价值系数，继续求解：*Page 16 of 37 2-2 人工变量处理方法两阶段法例2-3：用两阶段法解例2-2（续） Cj 5 3 2 4 CBXB x1 x2 x3 x4 x5 x6 b 4 3 x4 x2

12、 3/5 0 1/30 1 1/5 1 11/15 0 1 2 cjzj 0 0 0 0 05/3 10 Cj 5 3 2 4 CBXB x1 x2 x3 x4 x5 x6 b 5 3 x1 x2 1 0 1/18 5/3 0 1 13/18 1/3 5/3 5/3 cjzj 0 0 -4/9 -10/3 40/3最优解为：X* = (5/3，5/3，0， 0，0，0）T Z= 40/3*Page 17 of 37 2-2 人工变量处理方法两阶段法注意：退化解的处理当我们采用规则确定出基变量时，有可能存在两个或两个以上相同的最小值，选定其中一个所对应的基变量出基，这样，在得到的新的基本可行解中

13、除了非基变量等于零之外，还有一个或一个以上的基变量等于零。这就出现了所谓退化解。在这种情况下，如果用单纯形表求解时处理不当，有可能出现死循环。为解决这一问题，已经提出了一些方法，如“摄动法”、“辞典序法”等等。还有一种简便的方法称为勃兰特法，其规则如下：选取 中下标最小的非基变量进基； 当按规则计算存在两个或两个以上最小值时，选取下标最小的基变量出基。 *Page 18 of 37 2-3 改进单纯形法简介单纯形法的矩阵描述 用矩阵来描述单纯形法有助于对这一方法进一步的理解。 标准化为求解此标准型线性规划问题，对上式作如下分解：则上述标准型变为：*Page 19 of 37 2-3 改进单纯形

14、法简介单纯形法的矩阵描述 对约束式移项得：左乘B-1得：代入目标函数得： 若令非基变量 XN=0得：对LP的矩阵表述讨论：检验数：规则表达式：*Page 20 of 37 2-3 改进单纯形法简介单纯形法的矩阵描述 对LP的矩阵表述讨论：矩阵单纯形表：将非基变量所对应的系数矩阵N分为N1和NS两部分，其中NS是对应于松弛变量的部分，则上述目标函数表述为： *Page 21 of 37 2-3 改进单纯形法简介单纯形法的矩阵描述 矩阵单纯形表：将上述式写成单纯形表的形式如下：对应于松弛变量的矩阵为基矩阵的逆阵检验数行*Page 22 of 37 2-3 改进单纯形法简介改进单纯形法流程图改进单纯

15、形法流程图对于小型的线性规划模型用单纯形法，手工求解还是比较方便的，但我们也发现每次迭代都需计算很多无关的数字，对于大型的线性规划模型，不但手工解比较困难，就是借助计算机也会占用更多的空间和时间。为适应计算机计算的需要，提出一种改进的办法改进单纯形法 输入的原始数据有： *Page 23 of 37 2-3 改进单纯形法简介改进单纯形法*Page 24 of 37 2-3 改进单纯形法简介改进单纯形法运算过程中的主要矩阵有 ：Xq列变基前后Xl列变基前后变基后的Xl列*Page 25 of 37 2-4 线性规划的软件求解Excel电子表格中的工具菜单中有一个“规划求解”选项，它可以通过简单的

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

17、，每一个单元格对应一个决策变量，并在决策变量的上面或旁边设置说明文字来进行标记，以便于区别。目标方程：该部分包括目标价值所必要的元素，目标方程中将含有数据部分的数据和未知的决策变量值（相应的单元格为值）。约束方程：通常将每一个约束分成LHS和RHS放在两格单元格中，通过相应的运算符号对其加以限制，任何常量和决策变量元素的结合均可加入到约束中，但对于每一个约束而言，LHS和RHS都必须非空（至少有一个元素），包括非负条件在内。一个较好的处理方法就是将LHS作为一列，而将RHS作为相邻的另一列。*Page 27 of 37 线性规划的软件求解在电子表格中优化线性规划模型首先将基础数据、决策变量、目

18、标方程、约束条件输入工作部中。在工具菜单中选择规划求解命令将出现规划求解参数窗口。在设置目标单元个未知输入目标单元格；选定最大或最小；在可变单元格中输入决策变量单元格；点击添加按钮出现添加约束对话框，在单元格引用位置输入约束的LHS，选择约束符号类型，在约束值位置输入相应的RHS，如此重复添加各个约束条件；点击选项按钮进入规划求解选项框，选定采用线性模型和假定非负选项框，然后点击确定；点击求解按钮进入规划求解结果对话框，选定保存规划求解结果复选框，点击确定按钮则得到求解的结果。*Page 28 of 37 线性规划的软件求解管理运筹学软件1.0版使用说明：（演示例1）一、系统的进入与退出：1、

19、在WINDOWS环境下直接运行main.exe文件，或者在DOS下UCDOS中文平台环境下运行，也可直接运行各可执行程序。2、退出系统的方法可以在主菜单中选退出项，也可按Ctrl+Break键直接退出。3、在WINDOWS环境下直接运行软件，如果出现乱码，那是因为启用了全屏幕方式，解决办法是按ALT+ENTER键， 即可转换成非全屏的界面（一般就会消除乱码，如果还是乱码，可以点击菜单的“汉”选项）；若要每次启动程序都没有乱码，则需要修改屏幕设置的相应属性。具体方法是：在非全屏界面下点击菜单的“属性”选项，再选择“窗口”选项，然后选中其中的“窗口”项，并取消“启动时恢复设置”项，这样就可保证每次

20、运行软件时以非全屏方式显示。 二、输入部分：1、线性规划、整数规划的目标函数和约束的输入必须按由小到大的序号顺序输入，同时约束变量必须放在运算 符的左侧。如（x1+x2-x3=0，不能输为x2-x3+x1=0；x1-x2+x3=0，不能输为x1+x3=x2）2、输入的约束中不包括=或或=2,则输入 X12,而不是X1=2。*Page 29 of 37 线性规划的软件求解结果考察：（演示例1）1、当目标函数的系数 ci 单一变化时，只要不超过其上、下限，最优解不变；2、当约束条件中右边系数 bj 变化时，当其不超过上、下限，对偶价格不变（最优解仍是原来几个线性方程的解）； 3、当有多个系数变化时

21、，需要进一步讨论。百分之一百法则：对于所有变化的目标函数决策系数（约束条件右边常数值），当其所有允许增加的百分比与允许减少的百分比之和不超过100%时，最优解不变（对偶价格不变，最优解仍是原来几个线性方程的解） * 允许增加量 = 上限 - 现在值 c1 的允许增加量为 100 - 50 = 50 b1 的允许增加量为 325 - 300 = 25 * 允许减少量 = 现在值 - 下限 c2 的允许减少量为 100 - 50 = 50 b3 的允许减少量为 250 - 200 = 50 * 允许增加的百分比 = 增加量 / 允许增加量 * 允许减少的百分比 = 减少量 / 允许减少量 *Pag

22、e 30 of 37 2-5 案例分析案例1：贝德福德钢铁公司(NBS)采购问题的研究（教材P.238241)，NBS是一个位于宾夕法尼亚洲的贝福德钢材生产企业。焦煤是生产钢材的一种必不可少的原材料。NBS每年需1.01.5亿吨的焦煤，现在正是制定明年生产计划的时间。斯蒂芬考金斯NBS公司煤炭供应经理，已经收到了八家煤矿公司关于明年需求的投标书。下表显示了这八家有可能获得煤炭供应订货单的煤炭供应商的有关信息。艾什贝德康艘丹比埃尔佛罗加斯豪伯价格（$/吨）49.550.061.063.566.571.072.580.0联合/非联合联合联合非联合联合非联合联合非联合非联合卡车/火车火车卡车火车卡车

23、卡车卡车火车火车挥发性（%）1516182021222325生产能力300600510655575680450490*Page 31 of 37 案例分析根据市场预测及对去年的生产特征的分析，NBS决定在未来一年里共接受1225千吨的焦煤供应量，这些焦煤必须至少具有19%的挥发性。而且，为了抵消劳动关系中的不利因素，NBS决定从联合型（美国煤矿工人联合体）煤矿订购至少占总量的50%的焦煤。最后，斯蒂芬考金斯还必须考虑每年火车运煤的最大能力是650千吨，卡车运煤的最大运输能力是720千吨。斯蒂芬考金斯对以下三个方面的问题比较感兴趣：NBS应从每个供应商那里订购多少焦煤才能保证用于焦煤采购的成本达到最少？NBS用于采购的总成本是多少？NBS用于采购的平均成本是多少？*Page 32 of 37 案例分析焦煤供应问题的线性规划模型：设NBS从艾什勒到豪伯特各个供应商的供应量分别为A、B、C、D、E、F、G、H，则总费用=49.5A+50B+61C+63.5D+66.5E+71F+72.5G+80H约束：供应量：A+B+C+D+