第1章_线性规划

运筹学Operations ResearchChapter 1 线性规划Linear Programming1.1 LP的数学模型 Mathematical Model of LP1.2 图解法 Graphical Method1.3 标准型 Standard form of LP1.4 基本概念 Basic Concepts1.5 单纯形法 Simplex Method第 1章 线性规划* 2线性规划基本概念线性规划问题的数学模型和标准型线性规划问题的解可行解基本解基本可行解最优解线性规划问题的几何意义求解方法图解法单纯形法修正单纯形法基本单纯形法人工变量法大 M法两阶段法经济管理中的几类问题的线性规划模型本章框架本章框架1.1 数学模型 Mathematical Model一、线性规划应用举例二、线性规划的一般模型三、线性规划模型的特征Chapter1 线性规划第 1章 线性规划* 41. 1 线性规划的数学模型 Mathematical Model of LP线性规划通常研究资源的最优利用、设备最佳运行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多 、利润最大）。线性规划 （ Linear Programming,缩写为 LP） 是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。第 1章 线性规划* 5【例 1.1】最优生产计划问题。某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要要在设备 A、 B上加工，需要消耗材料 C、 D， 按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表 1.1所示。已知在计划期内设备的加工能力各为 200台时，可供材料分别为 360、 300公斤；每生产一件甲、乙、丙三种产品，企业可获得利润分别为 40、30、 50元，假定市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？1.1 线性规划的数学模型 Mathematical Model of LP1.1.1 应用模型举例第 1章 线性规划* 6产品 资源 甲乙 丙 现有资源设备 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 of LP第 1章 线性规划* 7【解】设 x1、 x2、 x3 分别为甲、乙、丙三种产品的产量数学模型为：1.1 线性规划的数学模型 Mathematical Model of LP产品资源甲 乙 丙 现有资源设备 A 3 1 2 200设备 B 2 2 4 200材料 C 4 5 1 360材料 D 2 3 5 300利润（元 /件） 40 30 50最优解 X=(50,30,10)； Z=3400第 1章 线性规划* 8【例 1.2】某商场决定：营业员每周连续工作 5天后连续休息 2天，轮流休息。根据统计，商场每天需要的营业员如表 1.2所示。表 1.2 营业员需要量统计表商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。 星期 需要人数 星期 需要人数一 300 五 480二 300 六 600三 350 日 550四 4001.1 线性规划的数学模型 Mathematical Model of LP第 1章 线性规划* 9【解】 设 xj(j=1， 2， ， 7)为休息 2天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为 1.1 线性规划的数学模型 Mathematical Model of LP星期需要人数星期需要人数一 300 五 480二 300 六 600三 350 日 550四 400第 1章 线性规划* 101 X1 0 C1 404 = 300 1042 X2 67 C2 301 = 300 13 X3 146 C3 350 = 350 04 X4 170 C4 400 = 400 05 X5 97 C5 480 = 480 06 X6 120 C6 600 = 600 07 X7 17 C7 550 = 550 0最优解：Z 617（ 人）第 1章 线性规划* 111、定义？所谓线性规划就是求一个线性函数在一组线性约束条件下极值的问题。2、构成？线性规划的数学模型由 决策变量 （ Decision variables）、 目标函数（ Objective function） 及约束条件（ Constraints） 构成。称为三个要素 。3、特征？（ 1）一组决策变量；（ 2）一个线性目标函数；（ 3）一组线性约束条件1.1 线性规划的数学模型 Mathematical Model of LP小结第 1章 线性规划* 121.1.2 线性规划的一般模型一般地，假设线性规划数学模型中，有 m个约束，有 n个决策变量 xj, j=1,2, n， 目标函数的变量系数用 cj表示 , cj称为 价值系数 。约束条件的变量系数用 aij表示， aij称为 工艺系数 。约束条件右端的常数用 bi表示， bi称为 资源限量 。则线性规划数学模型的一般表达式可写成1.1 线性规划的数学模型 Mathematical Model of LP第 1章 线性规划* 13在实际中一般 xj0,但有时 xj0或 xj无符号限制。1.1 线性规划的数学模型 Mathematical Model of LP为了书写方便，上式也可写成： 第 1章 线性规划* 141.什么是线性规划，掌握线性规划在管理中的几个应用例子2.线性规划数学模型的组成及其特征3.线性规划数学模型的一般表达式。作业：教材 P31 T 2， 3， 4， 5， 61.1 线性规划的数学模型 Mathematical Model of LP下一节：图解法1.2 图解法 Graphical Method一、图解法的含义二、图解法的步骤三、图解法的几种可能结果四、图解法的几何意义Chapter1 线性规划第 1章 线性规划* 16二、图解法的步骤：1.求可行解集合。 分别求出满足每个约束包括变量非 负要求的区域，其交集就是可行解集合，或称为 可行域 ；2.绘制目标函数图形。 先过原点作一条矢量指向点（ c1,c2)， 矢量的方向就是目标函数增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；3.求最优解。 依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是 最优解。一般地，将目标函数直线放在可行域中求最大值时直线沿着矢量方向移动； 求最小值时沿着矢量的反方向移动。1.2 图解法The Graphical Method一、图解法？用几何作图的方法求线性规划的解。第 1章 线性规划* 17x1x2O 10 2030 4010203040(3,4)(15,10) 最优解 X=(15,10)最优值 Z=85例 1.71.2 图解法The Graphical Method第 1章 线性规划* 182 4 6 x1x2246最优解 X=(3,1)最优值 Z=5(3,1)min Z=x1+2x2例 1.8(1,2)1.2 图解法The Graphical Method第 1章 线性规划* 1924 6 x1x2246X（ 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)=(2,2) 1.2 图解法The Graphical Method第 1章 线性规划* 202 4 6 x1x2246(1,2)无界解 (无最优解 )max Z=x1+2x2例 1.10第 1章 线性规划* 21x1x2O 10 20 30 40102030405050无可行解即无最优解max Z=10x1+4x2例 1.111.2 图解法The Graphical Method第 1章 线性规划* 22三、由以上例题可知，线性规划的解有 4种形式 ：1.有唯一最优解 (例 1.7例 1.8)2.有多重解 (例 1.9)3.有无界解 (例 1.10)4.无可行解 (例 1.11)1、 2 情形为有最优解3、 4 情形为无最优解1.2 图解法The Graphical Method第 1章 线性规划* 23四、由图解法得到的启示 可行域是有界或无界的凸多边形。 若线性规划问题存在最优解，它一定可以在可行域的顶点得到。 线性规划可行域顶点的个数有限个。 若两个顶点同时得到最优解，则其连线上的所有点都是最优解。1.2 图解法The Graphical Method第 1章 线性规划* 241.通过图解法了解线性规划有几种解的形式2.作图的关键有三点（ 1）可行解区域要画正确（ 2）目标函数增加的方向不能画错（ 3）目标函数的直线怎样平行移动作业：教材 P34 T7 1.2 图解法The Graphical Method下一节：线性规划的标准型第 1章 线性规划* 25复习思考题 1、线性规划问题的一般形式有何特征？ 2、建立一个实际问题的数学模型一般要几步？ 3、两个变量的线性规划问题的图解法的一般步骤是什么？ 4、图解法有何优点和不足？ 5、求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 6、图解法对解一般线性规划问题有什么启发？1.3 线性规划的标准型Standard form of LP一、线性规划的标准型二、线性规划的标准化Chapter1 线性规划第 1章 线性规划* 27在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。1.3 线性规划的标准型Standard form of LP线性规划问题的标准型为 :1.目标函数求最大值（或求最小值）2约束条件都为等式方程3变量 xj非负4常数 bi非负第 1章 线性规划* 28max(或 min)Z=c1x