1、上页上页上页上页下页下页下页下页返回返回返回返回第一章第一章 线性规划v 线性规划问题的提出线性规划问题的提出v线性规划的数学模型线性规划的数学模型v 线性规划问题的标准形式线性规划问题的标准形式（重点、难点）（重点、难点）继续继续继续继续返回返回返回返回第一节线性规划问题及其数学模型上页上页上页上页下页下页下页下页返回返回返回返回问题的提出 例例例例1 1 1 1 美佳公司计划制造美佳公司计划制造美佳公司计划制造美佳公司计划制造I I I I，IIIIIIII两种产品。已知各制造一两种产品。已知各制造一两种产品。已知各制造一两种产品。已知各制造一件时分别占用的设备件时分别占用的设备件时分别占
2、用的设备件时分别占用的设备A A A A，B B B B的台时、调试工序时间及每的台时、调试工序时间及每的台时、调试工序时间及每的台时、调试工序时间及每天可用于这两种产品的能力、各售出一件时的获利情天可用于这两种产品的能力、各售出一件时的获利情天可用于这两种产品的能力、各售出一件时的获利情天可用于这两种产品的能力、各售出一件时的获利情况，如表所示。问该公司应制造两种产品各多少件，况，如表所示。问该公司应制造两种产品各多少件，况，如表所示。问该公司应制造两种产品各多少件，况，如表所示。问该公司应制造两种产品各多少件，使获取的利润为最大。使获取的利润为最大。使获取的利润为最大。使获取的利润为最大。
3、上页上页上页上页下页下页下页下页返回返回返回返回产品产品I产品产品2如何安排生产如何安排生产使利润最大使利润最大？上页上页上页上页下页下页下页下页返回返回返回返回决策变量（决策变量（决策变量（决策变量（Decision variablesDecision variables）目标函数（目标函数（目标函数（目标函数（Objective functionObjective function）约束条件（约束条件（约束条件（约束条件（Constraint conditionsConstraint conditions）可行域（可行域（可行域（可行域（Feasible region)Feasible r
4、egion)最优解（最优解（最优解（最优解（Optimal solution)Optimal solution)基本概念基本概念问题中要确定的未知量，表问题中要确定的未知量，表问题中要确定的未知量，表问题中要确定的未知量，表明规划中的用数量表示的方明规划中的用数量表示的方明规划中的用数量表示的方明规划中的用数量表示的方案、措施，可由决策者决定案、措施，可由决策者决定案、措施，可由决策者决定案、措施，可由决策者决定和控制。和控制。和控制。和控制。它是决策变量的函数它是决策变量的函数它是决策变量的函数它是决策变量的函数指决策变量取值时受到的指决策变量取值时受到的指决策变量取值时受到的指决策变量取值
5、时受到的各种资源条件的限制，通各种资源条件的限制，通各种资源条件的限制，通各种资源条件的限制，通常表达为含决策变量的等常表达为含决策变量的等常表达为含决策变量的等常表达为含决策变量的等式或不等式。式或不等式。式或不等式。式或不等式。满足约束条件的决满足约束条件的决满足约束条件的决满足约束条件的决策变量的取值范围策变量的取值范围策变量的取值范围策变量的取值范围可行域中使目标可行域中使目标可行域中使目标可行域中使目标函数达到最优的函数达到最优的函数达到最优的函数达到最优的决策变量的值决策变量的值决策变量的值决策变量的值上页上页上页上页下页下页下页下页返回返回返回返回是问题中要确定的未知量，是问题中
6、要确定的未知量，是问题中要确定的未知量，是问题中要确定的未知量，表明规划中的用数量表示的表明规划中的用数量表示的表明规划中的用数量表示的表明规划中的用数量表示的方案、措施，可由决策者决方案、措施，可由决策者决方案、措施，可由决策者决方案、措施，可由决策者决定和控制。定和控制。定和控制。定和控制。第第1步步-确定决策变量确定决策变量设设 I的数量的数量 II的数量的数量 利润利润上页上页上页上页下页下页下页下页返回返回返回返回第第2步步-定义目标函数定义目标函数Max Z=x1+x2决策变量决策变量上页上页上页上页下页下页下页下页返回返回返回返回 Max Z=2 x1+1 x2系系 数数第第2步
7、步-定义目标函数定义目标函数上页上页上页上页下页下页下页下页返回返回返回返回对我们有对我们有何限制何限制?上页上页上页上页下页下页下页下页返回返回返回返回第第3步步-表示约束条件表示约束条件0 x1+5 x2 15 6 x1+2x2 241 x1+4 x2 5 x1、x2 0 0上页上页上页上页下页下页下页下页返回返回返回返回该计划的数学模型目标函数目标函数Max Z=2x1+x2约束条件约束条件5x2 15 6x1+2x2 24 x1+4x2 5 x1、x2 0 0 x1 x2上页上页上页上页下页下页下页下页返回返回返回返回线性规划问题的共同特征n n一组决策变量一组决策变量X X表示一个方
8、案表示一个方案,一般一般X X大大于等于零。于等于零。n n约束条件是线性等式或不等式。约束条件是线性等式或不等式。n n目标函数是线性的。目标函数是线性的。求目标函数最大求目标函数最大化或最小化化或最小化上页上页上页上页下页下页下页下页返回返回返回返回 线性规划模型的线性规划模型的一般一般形式形式 上页上页上页上页下页下页下页下页返回返回返回返回线性规划问题的标准形式n n标准形式为标准形式为:目标函数最大目标函数最大约束条件等式约束条件等式决策变量非负决策变量非负上页上页上页上页下页下页下页下页返回返回返回返回 n n 简写为简写为上页上页上页上页下页下页下页下页返回返回返回返回 n n用
9、向量表示用向量表示用向量表示用向量表示上页上页上页上页下页下页下页下页返回返回返回返回 n n用矩阵表示用矩阵表示用矩阵表示用矩阵表示C C价值向量价值向量b b资源向量资源向量X X决策变量向量决策变量向量上页上页上页上页下页下页下页下页返回返回返回返回 n nmin Z=CX min Z=CX 等价于等价于 max Zmax Z=-CX=-CXn n“”约束：加入非负松驰变量约束：加入非负松驰变量一般线性规划问题的标准形化一般线性规划问题的标准形化例：例：目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x
10、x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0上页上页上页上页下页下页下页下页返回返回返回返回 n nmin Z=CX min Z=CX 等价于等价于 max Zmax Z=-CX=-CXn n“”约束：加入非负松驰变量约束：加入非负松驰变量一般线性规划问题的标准形化一般线性规划问题的标准形化例：例：上页上页上页上页下页下页下页下页返回返回返回返回 n n“”约束：约束：减去非负剩余变量；减去非负剩余变量；例例例例 ：可正可负（即无约束）；可正可负（即无约束）；0,-=kkkkkxxxxx令Max上页上页上页上页下页下页下页下页返回返回返回返回 解解 ：标准形为上页上页上页上页下页下页下页下页返回返回返回返回练习练习 标准形化标准形化Max两边同乘（两边同乘（-1）上页上页上页上页下页下页下页下页返回返回返回返回练习练习 标准形化标准形化 解解 ：标准形为上页上页上页上页下页下页下页下页返回返回返回返回线性规划模型线性规划模型
