哈尔滨工程大学：《运筹学基础》课程教学资源（PPT课件讲稿）第一章 线性规划

第1章线性规划- 4.线性规划模型的标准形式 (1)变量:所有变量均x≥0 (2)目标函数:为取“max形式 (3)约束条件:全部约束方程均为“=”连接 (4)约束右端项:b≥0 非标准形式情况有 ★变量:x≤0,或x无约束 ★目标函数:min 约束条件:“≤”或“≥” 约束右端项:b<0 2021年2月21日 经济管理学院

2021年2月21日 经济管理学院 ---第 1 章 线性规划--- -12- 4. 线性规划模型的标准形式 （1）变量：所有变量均xj≥0 （2）目标函数：为取“max”形式 （3）约束条件：全部约束方程均为“=”连接 （4）约束右端项：bi≥ 0 非标准形式情况有 变量： xj≤0 ,或xj无约束 目标函数：min 约束条件：“≤”或“≥” 约束右端项： bi <0

第1章线性规划- LP的标准化: (1)变量:若xs0,令x=x,x20 若ⅹ无约束,则令xx一x",x20,x20 (2)目标函数:若求minz,则令z′=-z,等价于求max(z') 即有minz=-max(-z) (3)约束方程:当“≤”时,引进松 弛( slack)变量+x;2 如x1+x2≤3→x1+x2+x2=3 当“≥”时,引进剩余( surplus)变 量 如x1+2x2≥4→x1+2x2x=4 4)约束右端项:当b<0,则不等式 max 两端同乘(-1) 2021年2月21日 经济管理学院

2021年2月21日 经济管理学院 ---第 1 章 线性规划--- -13- LP的标准化： （1）变量：若 xj0，令 xj=-xj  ，xj 0 若 xj无约束，则令 xj= xj －xj  ，xj 0，xj 0 x z z zmin z = - z z  max （3）约束方程：当“”时，引进松 弛（slack）变量+xs； 如 x1+x23  x1+x2+ x3=3 当 “”时，引进剩余（surplus）变 量 - xs； 如 x1+2x2 4  x1+2x2－x4=4 （2）目标函数：若求 min z，则 令 z  = -z，等价于求 max （z ） 即有 min z= - max （- z） （4）约束右端项：当bi < 0，则不等式 两端同乘（- 1）

第1章线性规划- 例:将下述LP模型标准化: obj. Min Z=2X1- X2+3X3 X1+2x2+4x2≤6 3x1-2x2+x3=4 2x1-X2-3X3≥5 X1≥0,x2无符号限制,x3≤0 解:设 0 x3≥0,x1≥0,x5≥0,则有 ob Max z'=-2x1+( )+3x3 x1+2(x2 )-4x3+x4=6 3X1-2( 2x1-(X )+3X3x5=5 X1≥0,X2≥0 0,x3′≥0,x4≥0,x5≥0 2021年2月21日 经济管理学院 14-

2021年2月21日 经济管理学院 ---第 1 章 线性规划--- -14- 例：将下述LP模型标准化： obj. Min z=2x1 - x2+3x3 st. x1+2 x2+4x3  6 3x1 - 2x2+ x3 = 4 2x1 - x2 - 3x3 5 x1  0, x2无符号限制, x3  0 解：设 z= - z, x2= x2  - x2   , x2  0 , x2   0, x3= - x3  , x3  0 ，x40, x50, 则有 obj. Max z= -2x1 + (x2  - x2   ) + 3x3  st. x1+2(x2  - x2   ) - 4x3 +x4=6 3x1 - 2(x2  - x2   ) - x3 =4 2x1 - (x2  - x2  ) + 3x3 -x5=5 x1 0, x2  0, x2   0, x3 0, x4 0, x5 0

第1章线性规划- 复习思考题 1.什么是模型结构的三要素? 2.什么是线性规划模型?能举岀线性规划模型的例子 吗? 3.LP模型中目标函数系数、约束条件系数、约束右端 项的含义指的是什么?通常以什么符号表示? 4.LP模型的一般表示方法有几种飛式?能否写出这些 形式? 5.什么是线性规划模型的标准形式?为何提出标准形 式?你能否把一个线性规划模型的非标准形式转化为标 准飛式? 2021年2月21日 经济管理学院

2021年2月21日 经济管理学院 ---第 1 章 线性规划--- -15- 复习思考题： 1. 什么是模型结构的三要素？ 2. 什么是线性规划模型？能举出线性规划模型的例子 吗？ 3. LP模型中目标函数系数、约束条件系数、约束右端 项的含义指的是什么？通常以什么符号表示？ 4. LP模型的一般表示方法有几种形式？能否写出这些 形式？ 5. 什么是线性规划模型的标准形式？为何提出标准形 式？你能否把一个线性规划模型的非标准形式转化为标 准形式？

第1章线性规划- 1.1.3简单线性规划模型的建立 步骤: 1)分析问题:确定决策内容、要实现的目标以及所受 到的限制条件 (2)具体构造模型:选择合适的决策变量、确定目标函 数的表达式、约束条件的表达式,分析各变量取值的符号 限制。 2021年2月21日 经济管理学院 16-

2021年2月21日 经济管理学院 ---第 1 章 线性规划--- -16- 1.1.3 简单线性规划模型的建立 步骤： （2）具体构造模型：选择合适的决策变量、确定目标函 数的表达式、约束条件的表达式，分析各变量取值的符号 限制。 （1）分析问题：确定决策内容、要实现的目标以及所受 到的限制条件