运筹学复习提纲

运筹学

第一章 线性规划

数学规划（mathematical programming）是运筹学的一个主要分支，它是研究在一些给定的 条件下（即约束条件下），求的考察函数（即目标函数）在某种意义下的极值（极小或极大）。 对于数学规划，我们研究其中应用最为广泛的线性规划问题 线性规划模型为

max z = c1x1 + c2x2 + … + cnxn

s.t. a11x1 +a12x2 +…+a1nxn≤b1

a21x1 +a22x2 +…+a2nxn≤b2

………

am1x1+am2x2 +…+amn≤bm x1 ，x2 ，… ，xn ≥ 0

基本概念： （1）xn为决策变量

（2）am1x1+am2x2 +…+amn为目标函数，z为目标函数值 （3）约束条件：非负约束与函数约束

（4）参数：模型的参数是数学模型中的常数 （5）解：决策变量的任何一个取值称为模型的解

（6）满足所有约束条件的解称为可行解。反之，一个非可行解至少违反一个约束条件。全部可行解的集合称为可行域

（7）使目标函数达到最大值的可行解称为最优解，该目标函数值称为最优值。

★线性规划的标准形式： n max z = cjxj j?1

?n s.t. ?aijxj?bi(i?1,2,?m) ?j?1 ?xj?0(j?1,2,?n)?

①目标函数取极大化， ②约束条件全为等式， ③约束条件右端常数项均为非负值，④变量取值为非负。

对于非标准形式的线性规划问题，可通过下列方法化为标准形式： （1）目标函数求极小值。即min z=∑cjxj，令z'=-z即可。

（2）约束条件为不等式。当为―≤‖时，如x1≤4时，可添加x3≥0，使得x1+x3=4；当为―≥‖时，如6x1+4x2≥9，可添加x4≥0，使得6x1+4x2-x4=9。这里x3和x4是新加上去的变量，取值均为非负，加到原约束条件中去的目的是使不等式转化为等式。其中， x3称为松弛变量， x4一般称为剩余变量，其实质与x3相同，故也有统称为松弛变量的。松弛变量或剩余变量在目标函数中的系数均为零。 （3）变量xj≤0。令xj'=- xj 即可。

（4）取值无约束的变量x。令x=x'-x''，其中x'≥0，x''≥0。

例：将以下线性规划问题转化为标准形式 min f = -3 x1 + 5 x2 + 8 x3 - 7 x4 s.t. 2 x1 - 3 x2 + 5 x3 + 6 x4 ≤ 28 4 x1 + 2 x2 + 3 x3 - 9 x4 ≥ 39

?? 1

6 x2 + 2 x3 + 3 x4 ≤ - 58 x1 , x3 , x4 ≥ 0

解：首先，将目标函数转换成极大化： 令 z = －f = 3x1–5x2–8x3+7x4 ； 其次考虑约束，有3个不等式约束，引进松弛变量x5 ,x6 ,x7 ≥0 ； 由于x2无非负限制，可令x2=x2'-x2'',其中x2'≥0，x2''≥0 ； 由于第3个约束右端项系数为-58，于是把该式两端乘以-1 。 于是，我们可以得到以下标准形式的线性规划问题：

max z = 3x1–5x2'+5x2''–8x3 +7x4

s.t. 2x1–3x2'+3x2''+5x3+6x4+x5= 28 4x1+2x2'-2x2''+3x3-9x4-x6= 39 -6x2'+6x2''-2x3-3x4-x7 = 58

x1 ,x2',x2'',x3 ,x4 ,x5 ,x6 ,x7 ≥ 0 练习：把例1.1中的模型化成标准形式 max z = 3x1+5x2 s.t. x1 ≤ 4 2x2 ≤ 12 3x1+ 2x2 ≤ 18 x1 ≥ 0，x2 ≥ 0

解：标准形式为：

max z = 3x1+5x2+0x3 +0x4+0x5 s.t. x1 + x3 = 4 2x2 + x4 = 12 3x1+ 2x2 + x5 = 18

x1 ，x2 ，x3 ，x4 ，x5 ≥ 0 ★对偶问题

一般地，线性规划模型原问题的一般形式为

max z = c1x1 + c2x2 + … + cnxn

. s.t a11x1 +a12x2 +…+a1nxn≤b1

a21x1 +a22x2 +…+a2nxn≤b2

………

am1x1+am2x2 +…+amnxn≤bm x1 ，x2 ，… ，xn ≥ 0

其对偶问题的一般形式为

min w = b1y1 + b2y2 + … + bmym s.t. a11y1 +a21y2 +…+am1yn≥c1

a12y1 +a22y2 +…+am2yn≥c2

………

a1ny1+a2ny2 +…+amnym≥cm y1 ，y2 ，… ，ym ≥ 0

（1）将模型统一为―max，≤‖或―min，≥‖的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；

2

（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；

（3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。

例：写出原问题的对偶问题

max z = 1500x1 + 2500x2 s.t. 3x1 + 2x2 ≤ 65 2x1 + x2 ≤ 40 3x2 ≤ 75 x1 ,x2 ≥ 0

对偶问题为

min f = 65y1+ 40y2 + 75y3 s.t. 3y1+2y2 ≥1500 2y1+y2+3y3 ≥2500 y1, y2 , y3 ≥ 0

例 写出下面线性规划的对偶规划模型

maxz?x1?x2?5x3?7x4

x1?3x2?2x3?x4?25 ? ??2x4??60?2x1?7x3 ?2x?2x?4x?30123?

??5?x4?10,x1,x2?0,x3没有非负限制 ?解：先将约束条件变形为―≤‖形式 x1?3x2?2x3?x4?25???2x

?7x3?2x4?601?

?2x1?2x2?4x3?30?

?x4?10 ? ??x4?5?

??x1?0,x2?0,x3,x4没有非负限制

再根据对称形式的对应关系，直接写出对偶规划

minf?25y1?60y2?30y3?10y4?5y5

y1?2y2?2y3?1?

?3y ?2y3??11?? ?5??2y1?7y2?4y3 ?y1?2y2?y4?y5??7 ??,y2,y3,y4,y5?0 ?y1没有非负限制

灵敏分析详见老师课件

第二章 规划扩展

整数规划(Integer Programming)：一个规划问题中要求部分或全部决策变量是整数，则这个规划称为整数规划。 一、0－1变量的设置

3

例2.1（选址决策问题）随着业务发展，某制造公司必须建立1～2个新工厂：甲地或乙地，且新厂必须靠近密集的技术工人居住地区。此外，还考虑建一个仓库，若仓库与工厂设在同一地点，就可以节省运输费用。若不准备设立新厂，也就不需要建任何仓库。问题的关键是将新厂建在甲地还乙地，或同时在两地建厂；同时考虑建一个仓库，仓库必须建在与新厂所在的城市。这次扩张可使用的资金为1000万元。

表2.1 选址决策问题的数据表 决策序是或否 号 1 2 3 4 工厂在甲地 工厂在乙地 仓库在甲地 仓库在乙地 决策变量 x1 x2 x3 x4 净现值收益（百资本需求（百万万元） 元） 9 5 6 4 6 3 5 2 其中xj为0－1变量，表示为 1， 若决策j为是

xj＝ ( j＝1,2,3,4)

0， 若决策j为否

下面我们把选址决策问题中的要求用0－1变量的约束条件表示出来： ①互斥决策：

新建一个仓库，是在甲地还是乙地？可以用x3+x4≤1表示。它表示仓库选址的两个决策变量相互排斥，称类似此类的两个或多个互斥决策变量为互斥变量。 ②相依决策：

因为不设立新厂，也就不需要建任何仓库，所以仓库选址决策都是相依决策。相依决策的取值只能小于或等于其受约束的取值。如，对于工厂在甲地与仓库在甲地的决策可以表示为 x3≤x1，同理有x4≤x2 ③一致决策： 进一步，若以上两个相依决策是一种紧相关关系，也就是一致决策，表示同时建或同时不建，这种关系可以表示为: x3＝x1

再加上另一类我们熟悉的限制条件：投资总额不超过可得的资金限制，且目标函数是使得总净现值达到最大，则可得选址决策问题的数学模型为（以一百万元为单位） max z＝9x1+5x2+6x3+4x4 s.t. 6x1+3x2+5x3+2x4≤10 x3 + x4≤1 -x1 +x3 ≤0 -x2 + x4≤0 xj是0－1变量( j＝1,2,3,4)

选址决策问题中整数变量只能取0或1，我们称为0－1整数规则(binary programming，简记为BIP)。

练习：下面我们通过几道题，熟悉0－1变量的使用方法：

1.某公司拟从六个项目中选择若干项目，请用0－1变量表示下列关系： ①1，2，3项目中至少选择一个；

②若项目4被选中，则项目6不能被选中，反过来也一样。

4

x1+x2+x3≥1；x4+x6≤1

2.某足球队要从1，2，3，4，5号五名队员中挑选若干名队员上场，令 1， 第i号上场

xi＝ ( i＝1,2,3,4,5) 0， 第i号不上场 用xi的线性表达式表示下列要求： ①从1，2，3号中至少选2名； ②只有3号上场，4号才上场。 x1+x2+x3≥2；x4≤x3

特殊约束的处理：

④逻辑关系：比较典型的逻辑关系是if…then关系：若第一个约束成立，则第二个约束也必须成立；否则，若第一个约束不成立，第二个约束可以不成立。这种关系可以描述为： 若f(x)＜0成立，则g(x)≤0必须成立； 若f(x)＜0不成立，则g(x)无限制。

可以引入一个0－1变量y来完成这一逻辑关系： f(x)＞－M(1－y) g(x)≤My （ M为任意大的正数）

显然，若f(x)＜0，y不能为1，否则与第一式矛盾，所以有y＝0，第一个约束取为需要的形式；若f(x)≥0，y的取值已无关紧要，以任何值，第二个约束都可满足，所以，y的取值可由第一式控制， g(x)的取值不受任何限制。

例 试引入0－1变量将下列各题分别表达为一般线性约束条件 （1）x1+x2≤6或4x1+6x2≤10或2x1+4x2≤20 中只有一个成立 解：3个约束只有1个起作用 x1+x2≤6+y1M 4x1+6x2≤10+y2M 2x1+4x2≤20+y3M y1+y2+y3=2 yj=0或1，j=1,2,3 （2）x2取值0，1，3，5，7 解：右端常数是5个值中的1个

x2＝y1+ 3y2 +5y3+7y4

y1+ y2 +y3+y4≤1 yj=0或1，j=1,2,3,4 目标规划： 线性规划模型的特征是在满足一组约束条件下，寻求一个目标的最优解（最大值或最小值）。

若目标函数和约束条件都是线性的，就称为多目标线性规划(multi-objective linear programming).

下面引入与建立目标规划数学模型有关的概念． （1）正、负偏差变量d +，d -

我们用正偏差变量d + 表示决策值超过目标值的部分；负偏差变量d - 表示决策值不足目标值的部分。

（2）绝对约束和目标约束

我们把所有等式、不等式约束分为两部分：绝对约束和目标约束。

5

本文来源：https://www.bwwdw.com/article/489f.html