数据处理与统计软件

第一章线性规划的数学模型在工农业生产、交通、财贸工作等各项经济活动中，必须提高经济效运筹学有规划论、排队论、对策论等许多分支。线性规划是其中的一个重要分支。早在20世纪30年代末就有人从等问题开始研究它。它在运筹学中是研究较早、发展较快、应用较广、比较成一个分支。它研究的问主（一）问地调运到各个销地，调运方案可以很多，应如何调运，才能使总的运费或（二）（三）（四）（五）（包括运费、加工费）（六）nn（一）问1A1A223271-1。问应如何调运，才使总运费最低？1-销地（工地（万块砖）销量（万块解xijAiBj砖的数量（单位：万块（i=12j=1，2，31-1-AiB1B2B3AiBjA1A2Bjx11x12x13xx

x11x21约束条件

x13x23xx

0(i

jx11,x12,x13,x21,x22,x23的值，使其满足约束条件，并使运价函数s50x1160x1270x1360x21110x22mA1，A2，……，Amn个销地1-…（吨…………销量（吨…n

表中：aiAi的产量（i=1，2，…，mbjBj的销量（j=1，2，…，n（i=12m； 解假定产销平衡（即aibjxijAiBj jj=1，2，…，n；xx11x12 x1nxm1xm2xmn x x 0i1, ,m;j1, ,s=c11x11+c12x12+…+cmnxmn（Σ,, xijai(i1,j (产地Ai发到各销地的发量总和等于Ai的产量,xijbj(j, (各产地发到销地Bj的发量总和等于Bj的销量,,m;j1, ,xij0i1,

scijj1

的值最小（总运费最少 如果没有产销平衡这一限制，当产大于销时（即aibi ,, xijai(i1,j (产地Ai发到各销地的发量总和不超过Ai的产量,xijbj(j, (各产地发到销地Bj的发量总和等于Bj的销量,,m;j1, ,xij0i1,

scijj1

的值最小（总运费最少（二）公斤）1-4所示，问应如何合理安排种植计划，才能使总产量最多（ 假定即aibi,即计划播种总面积等于土地面积 1- n

表中：aiAi的播种面积（i=1，2，…，mbjBj的亩数（j=1，2，…，ncijBjAi解xijBjAi的亩数（i=1，2，…，mj=12，…，n；件 ,j,

(在各地块上种植作物Ai的总亩数等于Ai的计划播种数,xij,

(j1, (在土地Bj上种植各种作物的总亩数等于Bj的面积,,m;j1, ,xij0i1,

scijj1

的值最大（总产量最多（2题-希问题，bi吨（i=1，2，…，nk吨原料可1n个地区所产原料的总数恰好能生产各地区所需该产品 aikbiAidi Ai设厂生产该产品的数量最多为ei吨，最少为fi吨（i=1，2，…，n。从Ai解（i，j=1，2，…，n，其（i，j2，…，n（i=1，2，…，n1-…数费……………xij、yij、zi（i，j=1，2，…，n）,xijai(i,j (从Ai运往各地原料总数以及Ai的留用数等于Ai的原料产量,,

(j1,

(从各地运往Aj的原料总数以及Aj的留用数等于在Aj设厂所需原料数,yijzi(i,j (由Ai运往各地的成品总数以及Ai的留用数等于Ai的产品数,yijbj(j, , ,fiziei(i1, (在Ai生产的成品数必须在fi至ei之间x0,y0,z 并且使目标函数scij(xijyijdizi的值最小（生产总费用最少（三）

j

nB1，B2，…，BnnA1，A2，…，An去做，每人只做AiBjcij(ij=1,2,…,n)。(ij1,2,…,n)xij(i,j=1,2,…,n)的,, xij (j1, ,xij ,j ,xij0或 (i,j, 并且使目标函数scijxiji1j分派问题是问题的特例。因为变量xij只取0和1，所以又称它为0-（四）A1，A2，…，AmB1，B2，…，Bnn个不同零件构成的机器。如果每架机器需要各种零件的数目成比例λ1:λ2:…:λn；AiBj的效率（每日生产零件数）cij。问应如何分配机床负荷，解设xij为机床Ai生产零件Bj的时（单位日（i=1,2,…,m; j=1,2,…,n,, j (机床Ai生产各种零件时间总和应等::cinxin1:2m: ci1xi1:ci2xi2约束条件

cincini1mn

ci1 ci2xi

(各机床一天生产各种零件总数，应成已定比例,m;j1, ,m;j1, m (生产零件时间不能为负数mci1并且使目标函数s 的值最大。特别地，当λ1:λ2::λn=1:1:1（即每架机器需要各种零件数目求一组变量xij(i=1,2,…,m；j=1,2,…，n)的值，使它满足约束条j

ci1xi1 ci2xi2 cin,m;j,m;j1, ,

xij0(i1,mm并且使目标函数sci1xi1mA1，A2，…，AmnB1，B2，…Bn。1-单 品……………… 求一组变量xj(j=1,2,…,n)的值，使它满足约束条件c

,a(i,j

ij (生产各种产品所需原料Ai,x 0(j,xn n并且使目标函数sbjxj的值最大（总利润最多j1-8所示。问在这个生产周期，怎样安排各机床的生产任务，才能既完成加1-加 每 1-加 每 …………… 设xij为机床Ai在一生产周期加工零件Bj的个（i=1,2,…mj=1,2,…，nxij(i=1,2,…，m；j=1,2,…,n),cijxijai(i,j (机床Ai加工各零件总机时过Ai能工作机时,xijbj(j, (各机床加工零件Bj的总数不能少于Bj需要数,,m;j1, ,xij0整数(i1 并且使目标函数sdijxij的值最小（加工总成本最少j1（五）1-9所示。问应怎样安排下料方式，使得既能满足需1-…………… 设用Bj种方式下料的原材料数xj，则这一问题的数学模型为,cijxjai(i,j约束条件 (所下的Ai零件总数不能少于ai,x 0整数j,xn n并且使目标函数sxj的值最小（所用原材料量少j（六）设用n种原料B1，B2，…Bn制成具有m种成分A1，A2，…Am的产品，其a1a2,…am。各种原料的单价、各种原料所含1-10所示。问应如何配料，才使产品成本最低。1-一单位 量 …………解（j=1,2,…,nxj(j=1,2,…,n)的值，使它满足c

,a(i,j

ij ,x 0(j,x nn

sbjxjj1

的值最小（产品成本最低x1,x2,xn x

xax

bb11ax

12 1nxa

bbb21

22

2n 约束条件ax x xb或bbm1

m2

mn

(j1,2,,并使目标函数sc1x1c2x2cnxn达到最小（或最大。如果约束条件中第k

ak1x1ak2x2aknxnbk，则人为xnk0，使之成为ak1x1ak2x2aknxnxnkbk如果约束条件中第r

ar1x1ar2x2arnxnbrxnr0，使之成为ar1x1ar2x2arnxnxnrbr通过这种方法，使所有的约束条件都变成等式。xnk,xnr为松弛变量如果问题是使目标函数sc1x1c2x2cnxn标函数ssc1x1c2x2cn

xjxj

minsc1x1c2x2cna11x1a12x2a1nxnaa

a22

a2n

a am1

am2

(j1,2,,

a1n

x1

a1ja

b

x

a记A

2n

，b2

x2

，P

2j

b

x a

mn

m

n

minsAxx

Pj(1jnAjxj（1，其次如果x0x0 x0满足约束条件即有Ax0b,x00则称

如果可行解（向量）x00，或x0的非量对应的系数列向量线性关，则称x0为基础可行解有两个煤厂A、B，每月分别进煤60吨、100吨。它们担负供应三个居民区用煤任45吨、75吨、40吨。A10A1，A2，A3B1B25070个；各机床必须加元/个）如表1-11所示。问如何分配这三台机床加工这两种零件的任务，才使总的加工费 A1，A2，A3，把这种原料经过加工，制成成品，再运往销地。假设用4吨原料可制成1吨成品。A1年产307万吨。产地A2年产原料26万吨，同时需要成品13万吨A3年产24万吨，不需成品。A1与A2150公里，A1A3100公里，A2A3200公里。又知原料运费为0.3万元/万吨公里，成品运费为0.25万元/万吨公里。且知在A1开设加工费为0.55万元/A20.4万元/A30.3万元/A2设厂规模过年产成品5万吨，A1和A3可以不限制。问应在何地设厂，生产多少成品，才能使生产费用（包括原料运费、成品运费、加工费等）1-12610元。木器厂在现有木料（单位：立方米木料（单位：立方米1-13所示。问应如何组织生产，使总产量最大。 3020203025102015棵树浇水。问应怎样安排才能使植树（包括挖坑、栽树、浇水）某钢厂两个炼钢炉同时各用法炼钢。第一种炼法每炉用a小时；第二种用b小时（包括清炉时间。假定这两种炼法每炉出钢都是k公斤，而炼1公斤钢的平均费第一法为m元，第二法为n元。若要求在c小时内炼钢公斤数不少于d，问应怎样分配两种炼法的任务，才使费用最少。50098789810000根，7820000根。问怎样截法，才使所用的原材料最17—1250062001-月（元/件（元/件设有n种饲料，各含m种营养成分。每只鸡每天需要各营养成分的数量、各种饲成分数 饲………………nn种作物。每块土地只种一种作物且每种作物只在一块土地上1-16所示。问应如何制订种植计划，才使总产值最多。各种作物的产 土……………第二章单纯形方法（1 在理论研究部分，为讨论方便，不妨设BAm列组成，即令xx,x,,x

x , ,,x

cc,c,,c

,

,,

xxBcc，c

xNxxBxB的mxNxN的nm个B,NxBx x NAxbBxBNxN

BNxB1bB1NBNBB BB

1

NB将sNB

与cB1Axc

两边相加，并应用（4） scB1b(cB1A

cB1N

xB

由（3）

N xNxNBNB1NcNBNxB

xB B

x

xN

xN 满足条件约束Axb。称（6）为对应B的基础解，但它不一定是可行B（xB1bB

程是不断调整基B，使解（6）成为最优解。称使解（6）为最优解的基B为最（5）B解（6）对应的目标函数值为scB

当cB1Ac0时，适当取x0可使(cB1Ac)x0, scB1b(cB1Ac)xc （6）B当cB1Ac0x0B scB1b(cB1Ac)xc B若解（6）xB1b0BB鉴于cB1Ac在最优解判别中的重要作用，称之为检验数或判别数。B (4)式看出，cB1Nc。 xB1b cB1Acscx

s(cB1Ac)x

BAx

B1AxB

B1Acs cB

B1

B1bs看成是一个变量，则（8）式是一个关于n1个变量sx1x2,xn（2，实质上是求线性方程组（8）s取最小值的解。方程组（8）

B1A

c

(m1)s的系数始终为1，其余方程中s的系数始终为0。因此，在解方程组的过程

b0nc cB1A

bT(B)

1n

B1

(m1)

bmn由方程组（8）知，单纯形表（10）sb01x1b01x1b0nxnb 11b

b12

b1n

b21x1b22x2b2nxn bm1x1bm2x2bmnxn

xj0(j1,2,,B1AB1B,NB1B,B1NE,B1N（10例 设有线性规划问minsx12x22x1x2x3

x 0(i1,2,3x解minsx12x2x32x1

x2

x3

x4

0x4x x本例中，A 1 1,b4,c

2,

0,xx,x,x,

0 6

BB表(10)可知，构造单纯形表实际上是要计算cBB

cB1A

B1bB1A确定基BP,P 1（当然也可以选取BP,P

2或2101 101

BPP 1A的m220 20 的列向量组成BB为非奇异矩阵即可。并由此得到B1

1xx,x，

x,

，

c

c

2,0

计算目标值

s

B1b1

14

b,

,,bcB1A

12

0,5,0,

B1b

146

26

1

1

0100 2 100

11

2-1s-0-0-61200-0-1-B，使之最终满足B由一个可行基开始求解线性规划问B为可行BPkNPjxj1,xjb0j成（sxj,把b1jb2jbmj中的某一个bkj变成1,其余m0（从其余m1xjBxB1b0B例 2-2s9(b020(b0324(b106(b120(b13-2(b159(b203(b220(b233(b251(b264(b300(b31-4(b321(b330(b341(b354(b36x1 解由表2-2

BPPP

x90

4

x2，x5x6x6x2x5x2择检验数为正数的任一非基变量为入基变量。x1x3x42-2为x1

2x5x62 2

3x5x6

2 2

x5x6x3仅存在于(12)x3为出基变量，只能在第x3x2x3x5x6成为非基变量。由于该方程中“入x2的系数b3240x210，x3为出基变量。x2的系数b12,b22,b32均非正数，则无法进行换基xxxxx1

1

3x1x 3 3 再将第一个方程乘以16 x1

43

1x2

3924303 63x为出基变量。xb1024b2096b3 6b3 使以第一个方程为基础消去第二个方程中的x2时，右端的常数变为负数2-3。计算过程是以表2-2中的元素 为基础，先将b所在的行乘以1，使

1，再将b22所在的行乘以-9s6x1所4x3所在的行。这就把b221，x2中的其他元素变成了0x4x2（重新标注基变量，便完成2-3。b22x2x4x16，x23，x316，x4x5x6目标函数的最优值为s342-3s-34(b000(b020(b03-3(b04-6(b05-3(b066(b100(b120(b13-2(b14-8(b15-3(b163(b201(b220(b231(b 1(b251(b26316(b300(b310(b321(b334(b3435(b35(b363①在换基迭代中，必须选择检验数b0j0xj为入基变量。如果②如果第kxj的系数bkj0，第kx

0bk

bi

bk0是相应的两列元素的比值

bi0(b0xb b③选b 项，以b所在的行分别乘以

加到b所在的行，将bb b

bb0；将b

1，使b1

④如果各检验数b0j⑤如果检验数b0jj1,2,n)中有正数b0lb0l所在列的其他元素b1jb2jbmj中亦有正数，则重复步骤①～④，⑥如果检验数b0jj1,2,n)中有正数b0lb0l所在列的其他元素b1jb2j,bmj产生第一个可行基的方M)mina11x1a12x2a1nxnaxaxax21

22

2n ax x xm1

m2

mn 并假定bj0j12m，如果某个bk0乘以-1即可。现引进辅助问)min c2

cn x

xax 11

12

1n

a21x1a22x2a2nxn ymam1x1am2x2amnxnxj0(1jn);yi0(1iy1y2,ym是为了寻找第一个可行基人为添加的，称为人工变量。对

cn

0 a

b

1n

1A

bb2c

amn

A的前m1Em1BBE，则s,y1,y2,,ym0b

1 cB,

bb,

A

cB

bcBbb2 cB1AccA

cn

1n

am

a2n amn

0,0,,0

mm

ai1

mm

ai2,

mm

aina于是得到初始单纯形表T(B)

cB1A

B1

0

ai

ain

0 0 1 0

am

cn a1n a2n amn

(y1,y2,,ym)(b1,b2,,bm注意到bj0j12m，即基础解(s

,x,,

)(0000) B为辅助问题的可行基，称由于y10y20,ym0，从而minzy1y2ym0，即目标函若minzy1y2ym0y1y2ym0时不能满足若minzy1y2ym0，即y1y2ym0，且y1y2,ymy1y2，,ym已无任何作用，辅助若minzy1y2ym0y1y2ym0，但仍有某yjyjx1x2,,xn(系数全为零)，yjARA)m引起的；yjxkyj0xkxkyj对换，进行换基迭y1y2，ym全部成为非基变量，变成情况(2),第三章对偶线性规划问题mna11

a12

c2

a1nxnaa

a22

a2n

a am1

am2

j

n,()20,,Ⅱmaxa11y1a21y2am1ym yay 12

22

m2 ay y 1n 2n

mn yi0(i1,2,,yy1,y2,,ymmnAxxmaxyAy

定理1如果线性规划问题(Ⅰ)的第k个约束条件是等式，那么它的对偶规划(Ⅱ)中的第kyk第l个约束条件是等式，那么它的对偶规划(Ⅰ)中的第lxl证 略如果线性规划问题(Ⅰ)的第kak1x1ak2x2aknxn

ak1x1ak2x2aknxn如果线性规划问题(Ⅰ)的第kak1x1ak2x2aknxn则其对偶规划(Ⅱ)中的第kyk由于minsmaxs，maxgmin(g)例 求线性规mins2x13x22x14x2x33x7x5x

9x

解”约束，得到mins2x13x22x14x2x3 3x7x5x 5x6x

maxg5y18y272y13y25y3 7y6y

y1y29y3y,y30；y2”约束，得到max(s)2x13x22x14x2x33x7x5x

9x3ming5y18y272y13y25y34747

6

y1y29y3y,y30；y2或

5y18y272y13y25y3 7y6y

y1y29y3 y,y30；y2对比(16)式与(17)y1y3y2的系数均相差一个符号。表面看来(16)与(17)y2无非负限制故其本质是一样的只是在两者的最优解中，y2的取值互为相反数定理2x,y

sg证 由规划问题(14)知Axb，由规划问题(15)知cyA，于是scxyA)xyAx)ybg，即sg定理 若x*,y*分别为互为对偶线性规划问题(Ⅰ)和(Ⅱ)的可行解,并cx*y*bx*,y*证明由定理2x，则cxy*bcx*x*为问y*为问题(Ⅱ)的最优解。定理4 证 用反证法。设(Ⅰ)有可行解为x0,但无最优解，即cx0无下界y02cx0y0b，这与cx0无下界矛定理5若互为对偶的线性规划问题(Ⅰ)和(Ⅱ)都有可行解,则其都有最证明用反证法。设(Ⅰ)和(Ⅱ)都有可行解。如果(Ⅰ)（或(Ⅱ)）没有最优解,则由定理4必得(Ⅱ)（或(Ⅰ)）无可行解,与假设所以若(Ⅰ)(Ⅱ)定理6若互为对偶的线性规划问题(Ⅰ)和(Ⅱ)中任意一个有最优解,则证明我们称对偶问题的最优解为原问题约束条件的价格。具体说来，如y*y*,y*,y*y*为原问题(Ⅰ)的第k 束条件的价格如果对偶问题(Ⅰ)的最优解为x*(x*,x*,x*)则称x*原问题(Ⅱ)的第l个约束条件的价格

6,b1 s*cx*g*y*b(y*,y*,y*)b2y*by*by* m 1 2 m bm当原问题(Ⅰ)的第一个约束条件右端常数b1增加一个单位，即b1变成b11原问题的最优解（也是对偶问题的最优解）b1

m 2 bm

即最优解增加了y*个单位。其他y*也有类似的含意 y*（1km）表示原问题(Ⅰ)的第k个约束条件右端常数b 附录 销地（居民区）5648销量

x11x12x13

x11x21 x13x23

xx

(i

jmins10x115x12本题看似一个生产组织问题，实际应化为问题处理。1,2；jx11x12xx

x31x32

x12x22x32

xijx

(i

jmins0.4x110.3x120.3x210.5x220.2x31这是一个布局问题。影响生产费用的关键因素是各地点Ai原料到Aj的数量xij为Ai运原料到Aj的数量（万吨）（i j11,2， j11,32,Aj的原料总数（Aj自产）AjAi（Ai自留）AiAj的产品总数（Aj自产）Aj的y11y21y31yy

y23y33z2xij0,x

0,zj

(imins0.3(150x120.55z17256立方；各种产品的数量不能为复数等两个方面。设x1x2，则约束条件为：0.18x10.09x20.08x10.28x2x0,x maxs6x1AixijBjAi的时间（单位：日（i j1,2,3，考虑一天中的生产安排，则有约束条x x13x2330x15x18x

x

(i jmaxs30x1115x12 maxs20x2140x22x11x12x13x21x22x11x12x13xx

xij0且为整数（i或maxs30x1220x22

maxs20x11maxs25x13x21x22分别为第二钢炉使用第一、二种方法炼钢的时间（小时c小时和总炼钢量不小于d公斤两个方面。约束条件为x11x12xx

x22k(

x)k( x)

xij

(i,j规划目标是使费用最低，minsmk( x)nk(x x 698厘米毛A154321078厘米毛A2012356Bjxj5x14x23x32x4

x 3 2x3xx 3

x (jx66minsxx1x2公斤谷类饲料混合一天的饲料。约束条件为x1x24xx x x77

x10,x2这是一个库存管理问题。设x7～x12分别表示7～12月份的进货量y7～y12分别7～12500。例如：7月初的进6500，即有200x7500；77月的售货8500，即200x7y7x8500x7(xiyi)xi1

(kxi,yi0(i规划目标是使销售利润（总销售额减总进货额）6200件产品的进货价为a元∕件。目标函数为maxs29y724y826y928y1022y1125(200a28x724x825x927x1023x1123x12maxs29y724y826y928y1022y1125(28x724x825x927x1023x1123x12n种饲料各投入多少单位进行xjBj饲料进行配合