北外奥鹏作业运筹学讲述

运筹学作业精讲第一单元某企业生产甲、乙两种产品，其单位利润分别为20元和30元。每生产一件甲产品需劳动力3个，原材料2千克，设备4小时；每生产一件乙产品需劳动力7个，原材料4千克，设备3小时。企业现有劳动力240个，原材料150千克，设备可用时间为250小时。问：如何安排生产计划，才能使所获总利润最大？写出线性规划模型；化成标准形式；用图解法进行求解。解：设x1和x2分别表示产品甲和乙的产量，这样可以建立如下的数学模型。目标函数：Max

20x1

+30

x2约束条件：s.t.3

x1

+7

x2

≤240（劳动力限制）2

x1

+4

x2

≤150（原材料限制）4

x1

+3

x2

≤250（设备限制）x1，x2≥0（非负约束）化为标准型：目标函数：Max

20x1

+30

x2约束条件：s.t.

3

x1

+

7

x2

+

x3

=

2402

x1

+

4x2

+

x4

=

1504

x1

+

3

x2

+

x5

=

250x1，x2，x3，x4，x5≥

0阴影部分为可行域，虚线为目标函数线。由图可知最优解为约束2和约束3的交点，解得坐标为（55,10），故最优生产计划为生产甲产品55件，乙产品10件，最大利润为

20×55+30×10=1400元。第二单元·产品··大号·中号·小号·可用资源量资源铝板(张)

·6·2·4·400劳力(小时)·4·8·6·360机器(台)·8·4·10·420····售价(元/个)

·

50

·40·30·某厂生产三种型号的铝锅，已知单耗数据如下。试制定最优生产计划使总收入最大。解：设x1、x2、x3分别表示大号、中号、小号铝锅的产量，这样可以建立如下的数学模型。目标函数：Max

50x1

+40

x2+30

x3约束条件：s.t.6x1

+2

x2+4

x3

≤400（铝板限制）4x1

+8

x2+6

x3

≤360（劳力限制）8x1

+4

x2+10

x3

≤420

（机器限制）x1，x2，x3≥0（非负约束）化为标准型：目标函数：Max

50x1

+40

x2+30

x3约束条件：s.t.6x1

+2x2+4

x3

+x44x1

+8

x2+

6

x3

+

x5

=

360=

4008x1

+4

x2+

10

x3

+

x6

=

420x1，x2，x3，x4，x5，x6≥

0使用单纯形法求解：···

·50·40·3

·

00·0·0··BC·

X·

b’

·

x

·

x

·

x1

2

3·x

·

x

·

xB456··0·x4

·

400·6·2·4

·

1·0·0

·

200/3·0·x5

·

360·4·8·6

·

0·1·0

·

90··

-z··0

·

50

·

40

·

3·0

·

0

·

0*00·x6

·

420·(8)·4·1

·

00·0·1

·

105/2··0·

x4·85

·0·

-1

·-

·7/1

·0

·-

·3---2/40·

x5·150

·0·

(6)

·1

·0

·1

·-

·215·得到最优解（40,25,0,110,0,0），最优值

3000。即应该生产大号铝锅40个，中号铝锅25个单位，小号铝锅产量为0（不生产），最大利润为3000元。이

문서는

나눔글꼴로

작성되었습니다.

기·

cj·

CB第·

三XB单·

元b’·-5·5·13·0·0

·θi·x1·x2·x3·x4·x5··5

·x

·

202·-1·1·3·1·0··0

·x

·

105·

·16

0

-2·-4·1··

-z·5线性规划··0·Max

z

=

–5

x1

+

5

x2

+

13

x3·

s.-1t00.

–01

2

3·

0

·

-2

·

-x

+

x

+

3

x

≤

2012

x1

+

4

x2

+

10

x3

≤

90x1,x2,x3

≥0的最优表为：分析在下列条件下，最优解分别有什么变化b2由90变为70。c1由-5变为-10。增加一个约束条件4

x1

+3

x2

+6

x3

≤50。解：（1）由最优基不变的条件Max{-bi/βir½βir>0}≤Dbr≤Min{-bi/βir½βir<0}得-10=-10/1≤Db2b2由90变为70，超出了允许变化范围，继续计算或者由B-1(b+Db)=(20,-10)T可以知道最优基发生变化，继续迭代。c1由-5→-10，Dc1

=-5<0=-s1，不影响最优解。·

cj·

CB·

X

·

b’B·

-5

·

5

·

13

·

0

·

0·

x

·

x

·

x

·

x

·

x1

3

52

4·

5

·

x

·

20

·

-1·

1

·

3

·

1

·

02·

0

·5x

·-10

·

16

·

0·

(-

·

-·12)

4·

0

·

0·

-z

·

-

·

-100

2

5·

-

·

0·5z*·=90x。·

5

2

1

0最优解变为x1

=0，·x2

=5·，x3

=·5，x·4

=0，·x5

=0，最优值-

3/2）c1是2

非基变量的系3数，最优解不变5的条件2

是：Dc1≤

-

s1，3·

1

·

x

·

5

·

-8

13·

0

· ·

2·

-1/24

x1

+

3

x2

+

6

x3

+

x6

=

50（3）增加一个约束条件4

x1

+3

x2

+6

x3

≤350，原最优解不满足这个约束。·

··

·

·

··

Ci

-5

5

1

0

0

0·引入·松弛变量，得到填入最优单纯形表，进一步求解，得到最优3

解为X=(0，10，10/3)T，最优值·

··

·

·

·

·CB

XB

b

x1

x2

x

x4

x5

x6·为5

28·0/3x。·

··

·

·

··

20

-1

1

3

1

0

0·2x5

·

10

·

160··0

·

-

·

-42·1

·

0··-z·-·0·0·-·-5·0·01002·

5·

x2·20·-1·

1·3·1·

0·0·

0·

x5·10·16·

0·-·-4·

1·020·x6

·

50

·

4·3

·

6

·

0·0

·

1·0·x6

·

-

·

7·0·(-·-3·0·1103)·-z·-100·0·0·2-·-5·0·0·

5·x2·10·6·1·0·-2·0·1·

0·x5·50·34·0·0·-2·1·-/3/32/3第四单元对于以下的运输问题，若各个销地少得到1个单位的产品，将要求得到赔偿，金额分别为9、12、6、12，问如何组织运输，才能使总费用最低。（建立运输模型，用最小元素法求初始解，并求出最优解）解：总产量为99+55+110=264，总销量44+88+88+77=297，产销不平衡且供不应求，增加一个虚拟产地A4，其产量为297-264=33。由虚拟产地运往销地的费用即为赔偿金额。因此可以建立运输模型如下：使使用用最最小小元元素素法法求求初始始解解说明：每次选择最小元素，因此依次选择3（x33）、6（x22）、

9（x41）、12（x11）、15（x14）、21（x32）、33（x12）。）得到初始解x11=11，x12=11，x14=77，x22=55，x32=22，

x33=88，x41=33，其余运量为0，总运费为3003。··

B1·B2·B3·B4·

A1··1211··3311··9：(

)··1577·30·6·18·27·

A2·(

)·55·(

)·(

)·24·21·3·30·

A3·(

)·22·88·(

)·9·12·6·12·

A4·33·(

)·(

)·(

)·

销量·44·88·88·77·

余额·11,

0·33,·0/·0/11·产量·余额·99·88,11·55·0/·110·22,0/·33·0/·297···使用用位位势势计计算算各各非非基基变变量量检检验数数，，填填入括括号号中中：··

B1

·

B2

·

B3

·

B4

·

产量

·

位势ui·

A1··1211法··3311··9(-6)··1577·99·0·30·6·18·27·

A2·(45)·55·(30)·(39)·55·-27·24·21·3·30·

A3·(24)·22·88·(27)·110·-12·9·12·6·12·

A4·33·(-18)·(-6)·(0)·33·-3·

销量·44·88·88·77·297··

位势vj···12·33·15·15令u1=0，由基变量满足ui+vj=cij，依次得到各位势v1=12，v2=33，v4=15，u4=-3，u2=-27，u3=-12，v3=15，再根据公式sij

=cij

-ui

-vj计算各非基变量检验数。进行调整：选负检验数中最小的s42，那么x42为主元，作为进基变量。以x42为起点找一条闭回路x42、x41、x11、x12，取偶数标号格的最小运量11作为调整量，调整后运量为x42=11，x41=22，x11=22，x12=0（调整为非基变量），得到新的基本解，并重新用位势法计算检验数（令v2=0），如下表所示。14x

=77，所有有非非基基x2222==5555，，变变量量检检x3322==2222，，验数数均均非非x3333==8888，，负，，得得到到xx4411==2222，，最优优解解为为xx4422==1111x1111==2222，，其其余余运运为0，最小小的的总总运运费费为为2280055。。··B1·B2·B3·B4

·产量·位势ui·

A1x··1222·

33·

(18)·

9·

(12)··1577·99，·15量·

A2··30(27)·

6·

55··18(30)··27(21)·55·

6·24·21·3·30·

A3·(6)·22·88·(9)·110·21·9·12·6·12·

A4·22·11·(12)·(0)·33·12·

销量·44·88·88·77·297··

位势vj···-3·

0·-18·0第五单元有一个工厂要确定明年各季度的生产计划，通过订货了解到各季度对产品的需求量dk分别为4000件、3000件、4000件和4000件。又知，工厂生产该产品的季度固定成本为10万元（但如果在某季度中，该种产品1件也不生产，则不需支付固定成本费），单位产品的可变成本为50元，由于设备的能力所限，每季度最多只能生产5000件。若产品销售不出，则每件每季度的存贮费为8元。假设本年底无存货转入下年，明年末也不需要留有存货，问每季度的生产计划应如何安排（假设生产产量以千件为单位），才能使生产的总费用最省？解：首先建立动态规划模型（1）阶段k：每个季度作为一个阶段，k=1,2,3,4状态变量sk：第k个季度初的库存量（千件）决策变量uk：第k个季度的生产量（千件）状态转移方程：sk+1=sk+uk

-dk

(需求，千件)（即季度末库存量=季度初库存量+季度生产量-季度销售量或需求量）阶段指标：gk

(sk,uk)=生产成本C(uk)+库存成本E(sk)最优指标函数fk(sk)：第k个季度的状态为sk时从该季度至计划结束的最低总费用（万元）递推方程：fk

(sk)=min{gk

(sk,uk)+fk+1(sk+1)}终端条件：f5(s5)=0下面进行求解，采用逆序解法。（1）k=5，f5(s5)=0，因此库存·

s4（(说s4)4明：第4s季度的4,u4

)为4千件+f4

5(s4

5)4需4求·（2）uk=4·，0≤·s4≤4g，(us4=4·-s4，gs(5=ss4,+uu4-)d4

·f4量不(应s4超)过4且显然非负，·

u5

4所以有0≤s4≤4；年底不需要有库存，所以生产量u4

=4-*s4）0·

30·

30·

3008·

25.

·

25.8

·

25.806·

21.

·

21.6

·

21.60·

17.·

17.4

·

17.4·

0·

1·

2·

3·

4·4··3··2··1··0·04·

3.2·

3.2

·

3.2·

4·

3·

2·

1·

0（3）k=3，0≤s3≤5+5-4-3=3，s4=s3+u3-d3=s3+u3-4，Max(0,

4-s3)≤u3≤Min(5,

8-s3)（说明：前两季度总产量为5+5=10千件，需求量为

3+4=7千件，所以第3季度初最大库存量=10-7=3千件；

在产量需求方面，为了满足需求，至少生产d3-u3=4-u3，且最大产量为5千件，后两个季度总需求为4+4=8千件，产量不应该超过8-s3。因此有0≤s3≤3，Max(0,4-s3)≤

u3≤Min(5,8-s3)）（4）k=2，0≤s2≤5-4=1，s3=s2+u2-d2=s2+u2-3，Max(0,

3-s2)≤u2≤Min(5,11-s2)（5）k=1，s1=0，s2=s1+u1-d1=u1-4，4≤u1≤5最优解为s1=0,u1*=5,s2=1,u2*=5,s3=3,u3*=5,s4=4，u4*=0即前3个季度均生产5000件，第4个季度不生产，最低总费用为111.4万元。第六单元某企业生产甲、乙两种产品。生产一件甲产品需要使用劳动力4小时，能

源2个单位，销售利润为16万元；生产一件乙产品需要使用劳动力2小时，能源4个单位，销售利润为20万元。企业目前拥有劳动力可用时间22小时，能源20个单位。在制定生产计划时，决策者考虑下述4项目标：首先，乙

产品的产量不低于甲产品的产量；其次加班费用比较高，尽量不要加班；第三，尽可能充分利用能源，但是又不希望再购买；最后，利润尽量不少于112万元。求决策方案。（建立目标规划模型并用单纯形法求解）解：设x1、x2分别表示甲产品和乙产品的产，以建立如下的目标规划模型：1

1

2

2

3

3

3

4

4目标函数：Min

f=P

d

++P

d

++P

(d

-+d

+)+P

d

-1

1约束条件：

x1

﹣

x2

+

d

-

-

d

+

=

02

24

x1

+

2x2

+

d

-﹣

d

+

=

223

32

x1

+

4x2

+

d

-﹣

d

+

=

204

416x1

+

20

x2

+

d

-﹣d

+

=112i

ix1，x2，d

-，

d

+≥

0，i

=

1,

2,

3,

4（说明：目标1和2是不超过目标值，因此正偏差变量尽量小；目标3是恰好达到目标值，因此要求正、负偏差变量都尽量小；目标4要求不少于目标值，因此是负偏差变量尽量小）面用出单单纯形纯形表法进行，取d1-求解。、d2-d3

、d--为初

4始基变量。最小化问题转为基变量的检验数应该为0，最大理初化问题始基本，所以可行解目标函对应的数系数各级检均乘验数以-1；。于P1别为(P2优0，0，级对0，-1应目标，0，0函数中，0，0不含di-，0，，其0；0)检验数和(0，0只需取，0，系数负0，0，值，-1，0，0，0，0；0)。··x

·1x

·2d

·1d

·1d

·2d

·2d

·3d

·3d

·4d

·4R

·Hθ-+-+-+-+S········P

·1P

·2P

·30下·列0为·处·0由分0

·0

··0、0

·0

··0先-

·10

·0

·0

·、0

·0

·0

·-

·10

·0

·0

·-

·10

·0

·-

·10

·

0

·

0

·把·0

·

0

·

0·0

·

0

·

0P

·40

·0

·0

·0

·0

·0

·0

·0

·-

·10

··0d

·11

·-

·11

·-

·10

·0

·0

·0

·0

·0

··0-d

·4

·2

·0

·0

·1

·-

·0

·0

·0

·0

··2212-d

·2

·4

·0

·0

·0

·0

·1

·-

·0

·0

··2310-d

·1

·2

·0

·0

·0

·0

·0

·0

·1

·-

··146011-2P3优先级对应的目标函数中含d3-，所以其检验数需要把第3个约束行加P4取负优先级值的这对应一行上的目标，得到函数中4(2，4含d

-，，0，0所以，0，0其检验，0，-数需要2，0把第4，0；20个约束)。行加到取负值的这一行上，得到(16，20，0，0，0，0，0，0，0，-1；112

)。列目标规划的初始单纯形表如下：···x1·x2-

·

·d1

d1·d2·d2·d3·d3·d4·d4R

·θ+-+-+-+HS·P10·

到·0·0·-1·0·0·0·0·0·0·0··P2·0·0·0·0·0·-1·0·0·0·0·0··P3·2·4·0·0·0·0·0·-2·0·0·20···P416

·2

·0

·0

·0

·0

·0

·0

·0

·

-1

·1102······d11

·-1

·1

·

-1

·0

·

0

·0

·

0

·0

·

0

·0

·

----·d24

·2

·0

·

0

·1

·

-1

·0

·

0

·0

·

0

·22

·

11-·d32

·4*

·0

·

0

·0

·

0

·1

·

-1

·0

·

0

·20

·

5-·d416

·2

·0

·

0

·0

·

0

·0

·

0

·1

·

-1

·11

·

2-028/5下面（1）进行计k

=

1算。，在初始单纯形表中基变量为（d1-，d2-，d3

，-d4

)

=-（0，22，20，112)（2）；因为P1与P2优先级的检验数均已经为非正，所以这个单纯形表对P1与P2优（3）先级是下面最优单考虑P3纯形表优先级；，第二列的检验数为4最大，此为进基变量，计算相最小，于是取a32（标应的*号）比值bi为转/aij

写轴元进在q列行矩阵。通过行变换比较，得到新得到d3的单-对应形表的比值如下。··x

·1x

·2d

·1d

·1d

·2d

·2d

·3d

·3d

·4d

·4R

·Hθ-+-+-+-+S·P1·0·0·0·-1·0·0·0·0·0·0·0··P2·0·0·0·0·0·-1·0·0·0·0·0··P3·0·0·0·0·0·0·-1·-1·0·0·0··P4·6·0·0·0·0·0·-5纯·5·0·-1·12·····d

·3

·0

·1

·-

·0

·0

·1

·-

·0

·0

·5

·11-/21/41/40/3d

·3

·0

·0

·0

·1

·-

·-

·1

·0

·0

·1

·42-11/2/22x

·1

·1

·0

·0

·0

·0

·1

·-

·0

·0

·5

·12/2/41/40d

·6

·0

·0

·0

·0

·0

·-

·5

·1

·-

·1

·24*512-优（（4）计算下面相应的虑P4比值b/先级a

写，第一在q列列的检。通过验数为比较，6最大得到d

-，此为对应进基变的比值量，最小，于是取a41（标*i号）ij为转轴元进行矩阵行变换得4到新的单纯形表如下。··x1·x2考2·d1-·d1+·d2-·d2+·d3-·d3+·d4-·d4+·R

H

S·θ·P1·0·0·0·-1·0·0·0·0·0·0·0··P2·0·0·0·0·0·-1·0·0·0·0·0··P3·0·0·0·0·0·0·-1·-1·0·0·0··P4·0·0·0·0·0·0·0·0·-1·0·0··d1-·0·0·1·-1·0·0·3/2·-3/2·-1/4·1/4·2··d2-·0·0·0·0·1·-1·2·-2·-1/2·1/2·6··x2·0·1·0·0·0·0·2/3·-2/3·-1/12·1/12·4··x1/

6/61/前·

表·5·5）当1

的0

单·纯形0

各0

优·先0级0级的·的检0

验·

数-均·满足5

了·

最1优·条件-

，·

故2为·最优单纯形表。于是得到最优解x1=2，5

x2=4。/第七单元下图为一个交通运输网络图，道路（即弧）旁的权数表示该道路的容量和目前的运输量(cij,fij)，求出该交通运输网络的最大运输能力（即网络最大流）。解：第一次标号。首先给vs标号(0,+∞)；看vs：在弧(vs,v2)上，fs2=cs2=2，不具