运筹学-第一章概要课件

1、运筹学Operations Research2016.9.7运筹学Operations Research2016.9.15 十月 20222一、运筹学（OR）发展简介运筹学在国外英国称为 Operational Research美国称为 Operations Research起源于二战期间的军事问题，如雷达的设置、运输船队的护航舰队的规模、反潜作战中深水炸弹的深度、飞机出击队型、军事物资的存储等。二战以后运筹学应用于经济管理领域（LP、计算机）1948年英国首先成立运筹学会；1952年美国成立运筹学会。1952年，Morse 和 Kimball出版运筹学方法1959年成立国际运筹学联合会11

2、十月 20222一、运筹学（OR）发展简介运筹学在国外15 十月 20223 运筹学在国内中国古代朴素的运筹学思想（田忌与齐王对马、丁渭修复皇宫）1956年成立运筹学小组1958年提出运输问题的图上作业法1962年提出中国邮路问题1964年华罗庚推广统筹方法我国于1982年加入国际运筹学联合会，并于1999年8月组织了第15届大会11 十月 20223 运筹学在国内15 十月 20224二、运筹学的特点及研究对象运筹学的定义运筹学为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法Morse 和 Kimball运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各

3、种问题，其方法是发展一个科学的系统模式，并运用这种模式预测、比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针和政策英国运筹学会运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理中国百科全书现代运筹学涵盖了一切领域的管理与优化问题，称为 Management Science11 十月 20224二、运筹学的特点及研究对象运筹学的定义15 十月 20225三、运筹学的工作步骤明确问题建立模型设计算法整理数据求解模型评价结果简化？满意？YesNoNo明确问题建立模型设计算法整理数据求解模型评价结果11 十

4、月 20225三、运筹学的工作步骤明确问题建立模型设15 十月 20226四、运筹学内容介绍 线性规划及单纯形法 对偶理论及灵敏度分析 运输问题 整数规划 动态规划 图与网络分析 存储论 排队论（随机服务理论） 决策论11 十月 20226四、运筹学内容介绍 线性规划及单纯形法成绩考评平时成绩 10%期中考核成绩 30%期末考试成绩 60%15 十月 20227成绩考评平时成绩 10%11 十月 20227Chapter 1 线性规划Linear Programming1.1 LP的数学模型 Mathematical Model of LP1.2 图解法 Graphical Method1.3

5、 标准型 Standard form of LP1.4 基本概念 Basic Concepts1.5 单纯形法 Simplex MethodChapter 1 线性规划1.1 LP的数学模型 1.1 线性规划的数学模型 Mathematical Model of LP 1.1 线性规划的数学模型 15 十月 2022101.1 线性规划的数学模型 Mathematical Model of LP 线性规划通常研究资源的最优利用、设备最佳运行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件

6、限制下，如何组织安排生产获得最好的经济效益（如产品量最多 、利润最大）。线性规划（Linear Programming,缩写为LP）是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。11 十月 2022101.1 线性规划的数学模型 Mat15 十月 202211【例1.1】最优生产计划问题。某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要要在设备A、B上加工，需要消耗材料C、D，按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表1.1所示。已知在计划期内设备的加工能力各为200台时，可供材料分别为360、300

7、公斤；每生产一件甲、乙、丙三种产品，企业可获得利润分别为40、30、50元，假定市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？1.1 线性规划的数学模型 Mathematical Model of LP1.1.1 应用模型举例11 十月 202211【例1.1】最优生产计划问题。某企业15 十月 202212 产品 资源 甲 乙 丙现有资源设备A 3 1 2 200设备B 2 2 4 200材料C 4 5 1 360材料D 2 3 5 300利润（元/件） 40 30 50表1.1 产品资源消耗1.1 线性规划的数学模型 Mathematical Model

8、of LP11 十月 202212 产品 产品 资源 甲 乙 丙现有资源设备A 3 1 2 200设备B 2 2 4 200材料C 4 5 1 360材料D 2 3 5 300利润（元/件） 40 30 5015 十月 202213【解】设x1、x2、x3 分别为甲、乙、丙三种产品的产量数学模型为：1.1 线性规划的数学模型 Mathematical Model of LP最优解X=(50,30,10);Z=3400 产品 设备A 3 15 十月 202214线性规划的数学模型由决策变量 Decision variables 目标函数Objective function约束条件Constrai

9、nts构成。称为三个要素。其特征是：1解决问题的目标函数是多个决策变量的 线性函数，通常是求最大值或 最小值；2解决问题的约束条件是一组多个决策变量 的线性不等式或等式。怎样辨别一个模型是线性规划模型？1.1 线性规划的数学模型 Mathematical Model of LP11 十月 202214线性规划的数学模型由决策变量 Dec练习:饼干生产问题15 十月 20221545利润（百元/吨）1122 烘箱512 成形机1553 搅拌机每天现有工时 II型饼干 I 型饼干资源单位时耗 小时/吨 产品为充分利用现有资源，该厂应如何制定生产计划，使获利最大？练习:饼干生产问题11 十月 202

10、21545利润（百元/吨 设X1表示I型饼干日产量，X2表示II型饼干日产量（单位为吨），z表示I型和II型饼干所创造的日总利润15 十月 202216目标： max z = 5X1 +4X2约束条件： 3X1 +5X2 15 （搅拌机的限制） 2X1 + X2 5 （成形机的限制） 2X1 +2X2 11 （烘箱的限制） X1 0 ， X2 0 设X1表示I型饼干日产量，X2表示II型饼干日产量（单练习：运输问题15 十月 202217 应如何调运电机，即满足用户需要，又使总的运费最少？运价（元/台）B1B2B3供应量A1152118200A2202516150需求量（台）1008090B3

11、120练习：运输问题11 十月 202217 应如何调运电机 设Xij表示从仓库Ai调到商场Bj的调拨数，（i=1,2;j=1,2,3）以台为单位，则有以下LP模型： 15 十月 202218minZ=15x11+21x12+18x13+20 x21+25x22+16x23S.T. x11+x12+x13200 x21+x22+x23150 x11+x21=100 x12+x22=80 x13+x2390 x13+x23120 xij0（i=1,2;j=1,2,3）(严格设Xij应取整数值，这点暂不讨论) 设Xij表示从仓库Ai调到商场Bj的调拨数，（i=1,15 十月 2022191.1.2

12、 线性规划的一般模型一般地，假设线性规划数学模型中，有m个约束，有n个决策变量xj, j=1,2,n，目标函数的变量系数用cj表示, cj称为价值系数。约束条件的变量系数用aij表示，aij称为工艺系数。约束条件右端的常数用bi表示，bi称为资源限量。则线性规划数学模型的一般表达式可写成为了书写方便，上式也可写成： 1.1 线性规划的数学模型 Mathematical Model of LP11 十月 2022191.1.2 线性规划的一般模型为了书15 十月 202220在实际中一般xj0,但有时xj0或xj无符号限制。1.1 线性规划的数学模型 Mathematical Model of

13、LP11 十月 202220在实际中一般xj0,但有时xj015 十月 202221线性规划一般模型的结构目标函数 ：max，min约束条件：,=,变量符号：0, unr,0说明：线性规划模型由三部分构成：目标函数、约束条件和变 量符号。任何实际问题严格来讲是非线性的。在实际建模时应 明确什么样的特性使我们可以做出线性性质的假定。第二章 线性规划11 十月 202221线性规划一般模型的结构说明：第二章 15 十月 202222【例1.2】某商场决定：营业员每周连续工作5天后连续休息2天，轮流休息。根据统计，商场每天需要的营业员如表1.2所示。表1.2 营业员需要量统计表商场人力资源部应如何安

14、排每天的上班人数，使商场总的营业员最少。 星期需要人数星期需要人数一300五480二300六600三350日550四4001.1 线性规划的数学模型 Mathematical Model of LP11 十月 202222【例1.2】某商场决定：营业员每周连15 十月 202223【解】 设xj(j=1，2，7)为休息2天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为 1.1 线性规划的数学模型 Mathematical Model of LP星期需要人数星期需要人数一300五480二300六600三350日550四40011 十月 202223【解】 设xj(j=1，2，7)1

15、5 十月 2022241X10C1404=3001042X267C2301=30013X3146C3350=35004X4170C4400=40005X597C5480=48006X6120C6600=60007X717C7550=5500最优解：Z617（人）11 十月 2022241X10C1404=300104215 十月 202225【例1.3】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是1.5，1，0.7（m），这些轴需要用同一种圆钢来做，圆钢长度为4 m。现在要制造1000辆汽车，最少要用多少圆钢来生产这些轴？ 【解】这是一个条材下料问题 ，设切口宽度

16、为零。 设一根圆钢切割成甲、乙、丙三种轴的根数分别为y1，y2，y3,则切割方式可用不等式1.5y1+y2+0.7y34表示，求这个不等式关于y1，y2，y3的非负整数解。象这样的非负整数解共有10组，也就是有10种下料方式，如表1.3所示。表13 下料方案 方案规格 1234 5678910需求量y1(根) 221 11 0 00001000y2 102 10 4 32101000y3 010 23 0 12451000余料（m）00.30.5 0.1o.4 00.30.60.20.51.1 线性规划的数学模型 Mathematical Model of LP11 十月 202225【例1.

17、3】合理用料问题。某汽车需要15 十月 202226设xj(j=1,2,10)为第j种下料方案所用圆钢的根数。则用料最少数学模型为:求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长的，最后切割最短的，不能遗漏了方案 。如果方案较多，用计算机编程排方案，去掉余料较长的方案，进行初选。1.1 线性规划的数学模型 Mathematical Model of LP 方案规格 1234 5678910需求量y1(根) 221 11 0 00001000y2 102 10 4 32101000y3 010 23 0 12451000余料（m）

18、00.30.5 0.1o.4 00.30.60.20.511 十月 202226设xj(j=1,2,10)为第j种15 十月 2022271X15002X203X304X405X506X662.57X708X809X925010X100Z812.51.1 线性规划的数学模型 Mathematical Model of LP11 十月 2022271X15002X203X304X4015 十月 202228【例1.4】配料问题。某钢铁公司生产一种合金，要求的成分规格是：锡不少于28%，锌不多于15%，铅恰好10%，镍要界于35%55%之间，不允许有其他成分。钢铁公司拟从五种不同级别的矿石中进行冶

19、炼，每种矿物的成分含量和价格如表1.4所示。矿石杂质在冶炼过程中废弃，现要求每吨合金成本最低的矿物数量。假设矿石在冶炼过程中，合金含量没有发生变化。表1.4 矿石的金属含量 合金矿石锡%锌%铅%镍%杂质费用（元/t ）1251010253034024000303026030155206018042020040202305851517551901.1 线性规划的数学模型 Mathematical Model of LP11 十月 202228【例1.4】配料问题。某钢铁公司生产15 十月 202229解: 设xj（j=1,2，5）是第j 种矿石数量，得到下列线性规划模型 注意，矿石在实际冶炼时金

20、属含量会发生变化，建模时应将这种变化考虑进去，有可能是非线性关系。配料问题也称配方问题、营养问题或混合问题，在许多行业生产中都能遇到。1.1 线性规划的数学模型 Mathematical Model of LP矿石锡%锌%铅%镍%杂质费用（元/t ）12510102530340240003030260301552060180420200402023058515175519011 十月 202229解: 设xj（j=1,2，5）是15 十月 2022301X102X20.33333X304X40.58335X50.6667最优解：Z=347.51.1 线性规划的数学模型 Mathematical

21、 Model of LP11 十月 2022301X102X20.33333X30415 十月 202231【例1.5】投资问题。某投资公司在第一年有200万元资金，每年都有如下的投资方案可供考虑采纳：“假使第一年投入一笔资金，第二年又继续投入此资金的50%，那么到第三年就可回收第一年投入资金的一倍金额”。投资公司决定最优的投资策略使第六年所掌握的资金最多。第五年：x7/2+x9=x8+2x5第一年：x1+x2=200(万元)第二年：(x1/2 +x3)+x4=x2第三年(x3/2+x5)+x6=x4+2x1第四年：(x5/2+x7)+x8=x6+2x3到第六年实有资金总额为x9+2x7，整理

22、后得到下列线性规划模型 1.1 线性规划的数学模型 Mathematical Model of LP【解】设 x1：第一年的投资； x2：第一年的保留资金 x3：第二年新的投资； x4：第二年的保留资金 x5：第三年新的投资； x6：第三年的保留资金 x7：第四年新的投资 x8：第四年的保留资金 x9：第五年的保留资金 11 十月 202231【例1.5】投资问题。某投资公司在第15 十月 2022321.1 线性规划的数学模型 Mathematical Model of LP1X155.28462X2144.71553X3117.07324X405X552.03256X607X7208.13

23、018X809X90最优解：Z 416.26万元x1：第一年的投资； x2：第一年的保留资金 x3：第二年新的投资；x4：第二年的保留资金 x5：第三年新的投资； x6：第三年的保留资金 x7：第四年新的投资 x8：第四年的保留资金 x9：第五年的保留资金 11 十月 2022321.1 线性规划的数学模型 Mat15 十月 202233【例1.6】均衡配套生产问题。某产品由2件甲、3件乙零件组装而成。两种零件必须经过设备A、B上加工，每件甲零件在A、B上的加工时间分别为5分钟和9分钟，每件乙零件在A、B上的加工时间分别为4分钟和10分钟。现有2台设备A和3台设备B，每天可供加工时间为8小时。

24、为了保持两种设备均衡负荷生产，要求一种设备每天的加工总时间不超过另一种设备总时间1小时。怎样安排设备的加工时间使每天产品的产量最大。【解】 设x1、x2为每天加工甲、乙两种零件的件数，则产品的产量是设备A、B每天加工工时的约束为要求一种设备每台每天的加工时间不超过另一种设备1小时的约束为 1.1 线性规划的数学模型 Mathematical Model of LP11 十月 202233【例1.6】均衡配套生产问题。某产品15 十月 202234目标函数线性化。产品的产量y等价于整理得到线性规划模型 约束线性化。将绝对值约束写成两个不等式1.1 线性规划的数学模型 Mathematical M

25、odel of LP11 十月 202234目标函数线性化。产品的产量y等价于整15 十月 2022351.什么是线性规划，掌握线性规划在管理中的几个应用例子2.线性规划数学模型的组成及其特征3.线性规划数学模型的一般表达式。1.1 线性规划的数学模型 Mathematical Model of LP下一节：图解法11 十月 2022351.什么是线性规划，掌握线性规划在管1.2 图解法 Graphical Method1.2 图解法 15 十月 202237 通常用于求解含有两个决策变量的线性规划问题。 所求一般模型的线性规划问题无需化成标准模型。线性规划的图解法第二章 线性规划11 十月

26、202237 通常用于求解含有两个决策变量max z=5x1+4x2s.t. 3x1+ 5x2152x1+ x25 2x1+ 2x211x1 0, x2015 十月 202238目标函数等值线最优解0 x1x2Z=0Z=4OABCx2 = -5/4 x1 + 1/4 z(10/7,15/7) max z=110/75355/211/211/2可行域1.2 图解法The Graphical Methodmax z=5x1+4x211 十月 202238目标函15 十月 202239图解法的步骤：1.求可行解集合。分别求出满足每个约束包括变量非负要求的区域，其交集就是可行解集合，或称为可行域；2.

27、绘制目标函数图形。先过原点作一条矢量指向点（c1,c2)，矢量的方向就是目标函数增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；3.求最优解。依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是最优解。一般地，将目标函数直线放在可行域中 求最大值时直线沿着矢量方向移动 求最小值时沿着矢量的反方向移动1.2 图解法The Graphical Method11 十月 202239图解法的步骤：1.求可行解集合。分别15 十月 202240 x1x2O1020304010203040(3,4)(15,10)最优解X=(15,10)最优值Z=85练

28、习例1.71.2 图解法The Graphical Method11 十月 202240 x1x2O102030401020315 十月 202241246x1x2246最优解X=(3,1)最优值Z=5(3,1)min Z=x1+2x2例1.8(1,2)1.2 图解法The Graphical Method11 十月 202241246x1x2246最优解X=(3,15 十月 202242246x1x2246X（2）（3,1）X（1）（1,3）(5,5)min Z=5x1+5x2例1.9有无穷多个最优解即具有多重解,通解为 01 当=0.5时=(x1,x2)=0.5(1,3)+0.5(3,1)

29、=(2,2) 1.2 图解法The Graphical Method11 十月 202242246x1x2246X（2）（3,15 十月 202243246x1x2246(1,2)无界解(无最优解)max Z=x1+2x2例1.101.2 图解法The Graphical Method11 十月 202243246x1x2246(1,2)无界解15 十月 202244x1x2O10203040102030405050无可行解即无最优解max Z=10 x1+4x2例1.111.2 图解法The Graphical Method11 十月 202244x1x2O102030401020315 十

30、月 202245由以上例题可知，线性规划的解有4种形式：1.有唯一最优解(例1.7例1.8)2.有多重解(例1.9)3.有无界解(例1.10)4.无可行解(例1.11)1、2情形为有最优解3、4情形为无最优解1.2 图解法The Graphical Method11 十月 202245由以上例题可知，线性规划的解有4种形15 十月 2022461.通过图解法了解线性规划有几种解的形式2.作图的关键有三点 (1)可行解区域要画正确 (2)目标函数增加的方向不能画错 (3)目标函数的直线怎样平行移动1.2 图解法The Graphical Method下一节：线性规划的标准型11 十月 20224

31、61.通过图解法了解线性规划有几种解的1.3 线性规划的标准型Standard form of LP1.3 线性规划的标准型15 十月 202248线性规划问题的标准型特点：(1) 目标函数求最大值（有时求最小值）(2) 约束条件都为等式方程，且右端常数项bi都大于或等于零(3) 决策变量xj为非负。11 十月 202248线性规划问题的标准型特点：15 十月 202249通常设A的秩r（A）= m，且m n。 即AX=b中所包含的 m个方程式彼此 独立，没有多余方程，且方程个数小 于未知量个数。11 十月 202249通常设A的秩r（A）= m，且m 15 十月 202250约束条件是不等式

32、转化为等式：“”约束 加上松弛变 量 “”约束 减去松弛变量极小化目标函数转化为极大化：目标函数系数变号变量没有符号限制（unr）转化为变量非负：没有符号限制的变量用两个非负变量的差表示变量为非正转化为变量非负用添加负号的变量替换原变量，设新变量为正右端资源向量为非正（b 0） 在资源向量所在方程式两边同乘负号 将一般型转化为标准型第二章 线性规划11 十月 202250约束条件是不等式转化为等式：“”约15 十月 202251【例1.12】将下列线性规划化为标准型 【解】（）因为x3无符号要求 ，即x3取正值也可取负值，标准型中要求变量非负，所以令 1.3 线性规划的标准型Standard

33、form of LP11 十月 202251【例1.12】将下列线性规划化为标准15 十月 202252 (3)第二个约束条件是号，在号 左端减去剩余变量(Surplus variable)x5，x50。也称松驰变量1.3 线性规划的标准型Standard form of LP(2) 第一个约束条件是号，在左端加入松驰变量 (slack variable) x4，x40,化为等式；(4)第三个约束条件是号且常数项为负数，因此在左边加入松驰变量x6，x60，同时两边乘以1。 （5）目标函数是最小值，为了化为求最大值，令Z=Z,得到max Z=Z，即当Z达到最小值时Z达到最大值，反之亦然。 11

34、十月 202252 (3)第二个约束条件是号，在号15 十月 202253综合起来得到下列标准型 1.3 线性规划的标准型Standard form of LP11 十月 202253综合起来得到下列标准型 1.3 线性15 十月 202254 当某个变量xj0时,令x/j=xj 。 当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束 将其化为两个不等式 再加入松驰变量化为等式。 1.3 线性规划的标准型Standard form of LP11 十月 202254 当某个变量xj0时,令x/15 十月 202255【例1.13】将下例线性规划化为标准型【解】 此题

35、关键是将目标函数中的绝对值去掉。令 则有1.3 线性规划的标准型Standard form of LP11 十月 202255【例1.13】将下例线性规划化为标准15 十月 202256得到线性规划的标准形式 1.3 线性规划的标准型Standard form of LP对于axb(a、b均大于零)的有界变量化为标准形式有两种方法。 一种方法是增加两个约束xa及xb 另一种方法是令x=xa，则axb等价于0 xba，增加一个约束xba并且将原问题所有x用x= x+a替换。11 十月 202256得到线性规划的标准形式 1.3 线性15 十月 2022571.如何化标准形式？ 可以对照四条标准逐

36、一判断！ 标准形式是人为定义的，目标函数可以是求最小值。2.图解法时不必化为标准型。3.单纯形法求解时一定要化为标准型。1.3 线性规划的标准型Standard form of LP下一节：基本概念11 十月 2022571.如何化标准形式？ 可以对照四条1.4 线性规划的有关概念Basic Concepts of LP1.4 线性规划的有关概念15 十月 202259线性规划问题的解线性规划问题求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。11 十月 202259线性规划问题的解线性规划问题求解线性15 十月 202260 可行解：满足约

37、束条件、的解为可行解。所有可行解的集合为可行域。 最优解：使目标函数达到最大值的可行解。 基：设A为约束条件的mn阶系数矩阵(mn)，其秩为m，B是矩阵A中m阶满秩子矩阵（B0），称B是规划问题的一个基。设：称 B中每个列向量Pj ( j = 1 2 m) 为基向量。与基向量Pj 对应的变量xj 为基变量。除基变量以外的变量为非基变量。11 十月 202260 可行解：满足约束条件、的解为15 十月 202261 基解：某一确定的基B，令非基变量等于零，由约束条件方程解出基变量，称这组解为基解。在基解中变量取非0值的个数不大于方程数m，基解的总数不超过 基可行解：满足变量非负约束条件的基本解，

38、简称基可行解。 可行基：对应于基可行解的基称为可行基。非可行解可行解基解基可行解11 十月 202261 基解：某一确定的基B，令非基变量15 十月 202262【例1.14】线性规划 求所有基矩阵。 【解】约束方程的系数矩阵为25矩阵 容易看出r(A)=2，2阶子矩阵有C52=10个，其中第1列与第3列构成的2阶矩阵不是一个基，基矩阵只有9个，即1.4 基本概念Basic Concepts 11 十月 202262【例1.14】线性规划 求所有基矩15 十月 202263 基、基变量、非基变量 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 =目标函数约束条件行列式0基矩阵右边

39、常数基变量: x2, x4, x7非基变量: x1 x3 x5 x6 x8 x9 x10 0基解： （0， x2 ，0 ， x4，0，0，x7，0，0，0）基可行解均0基： = （x2, x4, x7） 11 十月 202263 基、基变量、非基变15 十月 202264基本最优解、最优解、基本可行解、基本解、可行解的关系如下所示：基本最优解基本可行解可行解最 优 解基本解例如,B点和D点是可行解,不是基本解;C点是基本可行解;A点是基本最优解,同时也是最优解、基本可行解、基本解和可行解。1.4 基本概念Basic Concepts 11 十月 202264基本最优解、最优解、基本可行解、基本

40、15 十月 202265练习max z=x1+3x2Ds.t. x1+ x2+x3=6 B-x1+2x2 +x4=8 x4=0 C x3=0 x1, x2,x3,x40 x1=0 E O x2=0 A第二章 线性规划11 十月 202265练习max z=x1+3x215 十月 202266O451-1243123ABDCEHFIGx1Min z=2x1+3x2s.t. x1+ x24 （1） 2x1+5x2 10 （2） -x1+ x2 1 （3） x1，x2 0约束条件（1）、（2）、（3）的松弛变量或剩余 变量分别为x3、x4、x5x2=0 x3=0 x4=0 x5=0 x1=0以上问题

41、中，有 个基变量， 个非基变量；基解为 ；基可行解为 ；最优解为 。32Z=9Z=6A B C D E F G H I OC D HDx2练习11 十月 202266O451-1243123ABDCEH线性规划的可行域是凸集线性规划的最优解可以在极点上得到15 十月 202267凸集凸集不是凸集极点可行域的性质线性规划的可行域是凸集11 十月 202267凸集凸集不是凸15 十月 202268凸集：设E是n维欧氏空间的一点集，若X1和X2是E 中的任意两点，则必有E的连线上的一切点均 属于点集E，则称E为凸集。直观上讲：凸集是没有凹入部分，其内部没有空洞。 极点：设E是凸集，X属于E，若X不能

42、用不同的两点 X1和X2的线性组合表示为X = aX1 + (1-a) X2 (0a04010换出行将3化为15/311801/301/31011/3303005/304/3乘以1/3后得到103/51/518011/52/54001111 十月 202279cj3400icB基变量bx1x215 十月 202280最优解X=(18，4，0，0)T，最优值Z=70O20301040(3,4)X(3)=(18,4)最优解X=(18,4)最优值Z=70X(1)=(0,0)2010 x2x1301.5 单纯形法 Simplex MethodX(2)=(0,10)11 十月 202280最优解X=(1

43、8，4，0，0)T，最15 十月 202281【例1.16】 用单纯形法求解【解】将数学模型化为标准形式：不难看出x4、x5可作为初始基变量，单纯法计算结果如表 1.所示 。 1.5 单纯形法 Simplex Method11 十月 202281【例1.16】 用单纯形法求解【解】15 十月 202282Cj12100bCBXBx1x2x3x4x50 x423210150 x51/3150120j121000 x42x2j1x12x2j表151/3150120301713751/30902M2025601017/31/31250128/91/92/335/30098/91/97/3最优解X=(

44、25，35/3，0，0，0)T，最优值Z=145/31.5 单纯形法 Simplex Method11 十月 202282Cj12100bCBXBx1x2x练习题2 设X1表示I型饼干日产量，X2表示II型饼干日产量（单位为吨），z表示I型和II型饼干所创造的日总利润15 十月 202283目标： max z = 5X1 +4X2约束条件： 3X1 +5X2 15 （搅拌机的限制） 2X1 + X2 5 （成形机的限制） 2X1 +2X2 11 （烘箱的限制） X1 0 ， X2 0 练习题2 设X1表示I型饼干日产量，X2表示II型饼干日产 转化为标准模型 引入松弛变量s1 , s2 , s

45、3 0 15 十月 202284目标： max z = 5X1 +4X2约束条件： 3X1 +5X2 + s1 = 15 （搅拌机的限制） 2X1 + X2 + s2 = 5 （成形机的限制） 2X1 +2X2 + s3 = 11 （烘箱的限制） X1, X2, s1 , s2 , s3 0 转化为标准模型11 十月 202284目标： m15 十月 202285基变量CBX1X2S1S2S3b 比值54000S1035100155S202101055/2S30240011111/2 zjj cj-zj00000Z=05400011 十月 202285基变量CBX1X2S1S2S3b 比15

46、十月 202286基变量CBX1X2S1S2S3b 比值54000S1007/21-3/2015/215/7x1511/2005/25S30010-1166 zjj cj-zj55/205/20Z=25/203/20-5/2011 十月 202286基变量CBX1X2S1S2S3b 比15 十月 202287基变量CBX1X2S1S2S3b 比 值54000 x24012/7-3/7015/7x1510-1/75/7010/7S3000-2/7-4/7127/7 zjj cj-zj543/713/70Z=110/700- 3/7-13/70得到最优解，最优解为：（x1，x2，s1，s2，s3）

47、=（10/7，15/7，0，0，0，27/7）max z=110/711 十月 202287基变量CBX1X2S1S2S3b 比15 十月 202288【例1.18】求解线性规划【解】化为标准型1.5 单纯形法 Simplex Method11 十月 202288【例1.18】求解线性规划【解】化为15 十月 202289初始单纯形表为XBx1x2x3x4bx3x43221100114j11002=10, x2进基，而a120，a220且aik（i=1，2,m）则线性规划具有无界解1.5 单纯形法 Simplex Method11 十月 202293唯一最优解的判断：最优表中所有非基变15 十

48、月 202294 在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。1.5.2大M法1.5 单纯形法 Simplex Method11 十月 202294 在实际问题中有些模型15 十月 202295人工变量法如果约束条件全为“”，且右边常数全为非负，则引进的松弛变量就可以作为初始的基变量，得到一个初始的基础可行解。如果约束条件有“=” ，右边常数全为非负，则需要加上非负人工变量，建立辅助问题。如果约

49、束条件有“”，右边常数全为非负，则需要加上非负人工变量，建立辅助问题。11 十月 202295人工变量法15 十月 202296人工变量人工变量11 十月 202296人工变量人工变量15 十月 202297【例1.20】用大M法解 下列线性规划1. 大M 单纯形法1.5 单纯形法 Simplex Method引进松弛变量，使约束条件全为等式。引进人工变量，令人工变量在目标函数中的系数为大M （任意大的正数）用单纯形法求解，得到原问题的最优解。若基变量中有非零的人工变量，则该LP无可行解。11 十月 202297【例1.20】用大M法解 下列线性规15 十月 202298【解】首先将数学模型化

50、为标准形式式中x4，x5为松弛变量，x5可作为一个基变量，第一、三约束中分别加入人工变量x6、x7，目标函数中加入Mx6Mx7一项，得到人工变量单纯形法数学模型用前面介绍的单纯形法求解，见下表。 1.5 单纯形法 Simplex Method11 十月 202298【解】首先将数学模型化为标准形式式中15 十月 202299Cj32100MMbCBXBx1x2x3x4x5x6x7M0Mx6x5x74123121211000101000014101j3-2M2+M-1+2MM000M01x6x5x3632532001100010100381j5-6M5M0M00201x2x5x36/53/52/

51、51000011/53/52/50103/531/511/5j50000231x2x1x301010000111025/32/31331/319/3j0005-25/311 十月 202299Cj32100MMbCBXBx15 十月 2022100（1）初始表中的检验数有两种算法，第一种算法是利用第一、三约束将x6、x7的表达式代入目标涵数消去x6和x7，得到用非基变量表达的目标函数，其系数就是检验数；第二种算法是利用公式计算，如（2）M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；最优解X（31/3，13，19/3，0，0)T；最优值Z152/3注意：

52、1.5 单纯形法 Simplex Method11 十月 2022100（1）初始表中的检验数有两种算法，15 十月 2022101设有线性规划其中Amn且r(A)=m,X0应理解为X大于等于零向量，即xj0,j=1,2,n。1.5.3 计算公式1.5 单纯形法 Simplex Method11 十月 2022101设有线性规划其中Amn且r(A)15 十月 2022102不妨假设A（P1，P2，Pn）中前m个列向量构成一个可行基，记为B=(P1，P2，Pm)。矩阵A中后nm列构成的矩阵记为N（Pm+1,Pn）,则A可以写成分块矩阵A=（B，N）。对于基B，基变量为XB=（x1,x2，xm ）T, 非基变量为XN=(xm+1,xm+2,xn)T。则X可表示成 同理将C写成分块矩阵C=（CB，CN），CB=(C1,C2,Cm), CN=(Cm+1Cm+2，cn) 则AX=b可写成1.5 单纯形法 Simplex Method11 十月 2022102不妨假设A（P1，P2，Pn15 十月 2022103因为r（B）=m（或|B|0）所以B 1存在，因此可有 令非基变量XN=0，XB=B1b，由 B是 可行基的假设，则得到基本可行解X