工程数学习题加答案

一、论述用单纯形方法解LPLP

zcTxAxbx0Bcxmn-mA[B,N]，ccB,cT[cT,cT]c cNxxB,xT[xT,xTx NAxb[B,N]xBbBxNxx xN xB1b zcTx[cT,cT]xBcT

x N xN

B NcT(B1bB1Nx)cT N， ,0,cTB1NcT]xBx x

N 令T[0, ,0,cTB1NcT]， BzcTB1bTxB且 。BcTB1[B,N]BBcTB1ABLP

zcTB1bTB B

xB1bB1Nxx0 x0xB1b x0

BzcTxcTB1bBBBx0 x00B B1b0时称x为非的基本可行解LPBB1b0定理LP问题有可行解，则必有基本可行解；若有最优解，则一定存在一个基 定理若0，x 证x

Tx

zcTB1bTxcTB1b定理若的第k个分量0，且AB1A0，则该LP问题。这里Ak Ak证取

1（这是一个n维的列向量，第k个分量为1，其余分量为0）Akexx+0(x0 A

B1A k

kA=k0 k

AxA(x)AxAAxx BBB1Ak k＋TekB BBk

定理若k个分量0A

且cTxˆcTx证令xˆx+（见前面定理中的定义，这里0A B1Ak k =B,N k k0

AxˆA(xAxAAxb B1A +( k+e)0，只0

B1A 0+

k0，B1bB1Ak0k b1 a1kb B1b

2,

2k

由b

0

b

mk取mina

0,i1 m BBB1Ak k＋TekB BB

这里k0，但因为三、从集合{1,2,3,…,m}n个排成一个圆，如果经旋转能够重合的两个圆看长度为n的圆排列按周期分类，设周期为d的圆共有M(d)个，则要求的数字为T(n)M(d)dT(n)M(dddM(d)mnd|n

nM(n)(d d1M(d) (d1d例从1,2,3,44m4n

T(4)M(d)M(1)M(2)Md 2 M(2)

(d)4d [(1)42(2)41]21

M(4)

(d)4d [(1)44(2)42(4)41]4 T(4)46607020001100A1700吨、1100吨、C200吨、D1001所示，运费与运量成正比，建 费产ABCD甲7乙解：设甲、乙运往A、B、C、Dx11x12x13x14x21x22x23x24吨，则由题

f21x1125x127x1315x14+51x2151x2237x23 xxx x21x22x23x24 x x x13x23 x

x11x12x13x142000 需原料kg （kg日230024325(千元354x1x2x3时可以得到最大利润3x15x24x3，则由题意， z3x15x2 2x 2x24x3 3x2x5x xj0,j1,2,

zx1 x2x xx (0,-

zx1 x2x xx x1x20x1x1-(0,-xx4x2x8的交叉点坐标为(164约 x15x20x1x24x5x0x2x8的交叉点坐标为(388 x15x21z

F4x2x22x2 3x12x2x3 x1,x2,x3因为3x12x2x39x1x2x33x1z2x2yx303x102x20x3 maxF4x2(x2)2x f(z)max{4x 03x1 f(y)max{x2f(y2x 02x2 f(9)max{2x212f(9x 0x3 z2zf1(z)4

(y2xf2(y)

02x2

4 9x2max x2

16yx

02x2

492 max{492 02x2y 49f(9)max{2x212f(9x max{2x2124(9x max{22x2

120x39 }max{22(x18)2}0x39

A＝｛a1，a2，…，an｝sBs(aAA使得s(aB 012j…1TTF2TT?TTiTnT012j…1TTF2TT?TTiTnT012342TFTFF3TFTTF1TTTTT2TTt(i,j)

i1,ji1,js(aii1,t(i1,j)i1,t(i1,js(ai))TT(i1,j01true。因为③所以T(i1,js(ai11true身就能满足要求。因为④所以第i行中与第is(aitrueT(i1t(i1,jT：2行之后的单元格，它上方的单元格值为Ttrue。因为对于第i个元素，如果在它出现前的i1个元素就能满足要求，那算上第i个T(i1,t(i1,js(aiT：排除第i个元素，前i1个元素恰好可以满足要求与第i个元间的缺口时，值为true。BNy 如果要求只能向正东和正北方向（沿水平和垂直的格子线）AB有多AB86xyAB8x6y。反之，8x6yAB的最短路，ABS（多重集）的重复排列数，即向(8+6)个假想位置8xy：C C

nC(nk为从n元素中取出k个的方法数。S1C(n,1C(n,3C(nm)，m是不超过n的最大奇数S2C(n0C(n,1C(n,p，p是不超过n (xy)nC0xny0C1xn1y1C2xn2y2...Cn x1y1n2 [1(1)]2C0C1C2...(1)n

2S1S1S2个数为nx个。如果能确定标号树枝的个数为nn1，那么根据标号树枝个数nxnn1xnn2。下面证明标号树枝的个数为nn1nn个无枝森林，现k(uv)的选择为n(k1uv必须是连接不含un种取法，而vk1n(ni)n(n1)*n(n2)*...*n(1)nn1(n因为每个标号树枝含有n1条边，有(n1种顺序，也就是说每个标号树枝被构造了(n1次，所以标号树枝的个数为nn1。nr个来做组合，共可以做C(nr1r个不同假设选出的r个数分别为c1c2c3,...cr1≢c1≢c2≢c3 ≢cn≢1≢c1c21c32...cr(r1)≢nrr个数互不相同，相当于从1~nr1中选出r Step179iStep2：比i178jStep3：将第i1jStep4：将第i位及其之后的所有位置逆序，得n个元素依次给以标号123n，n个元素的全排列中，求每个元素Aiiii12n。i|AiAj|(n

i,j|A1A2...AnnN|Ai||n i n!(111... G(x)aa1xa2x2...akxk k为序列a0a1a2n个数12nDnD0

Dn[Dn1(n1)Dn2

(n2)Dn3 (1)n1(DD D0D1DD

1)n G(xDD1xD2x2Dkxk kG(x)DD1xD2x2...Dkxk xG(x) DxD1x2D2x3...Dkxk1 D

n n1 n1 (n 可得(1x)Ge(x)1x2!n!e1 1x ... 1 (1x ...

...)(1x

D(1111)n! 十二记1,2,...,n中与n互素的数的个数为(n)称为函数比如1,2,...,互质，又称互素。若N1N互质，又称互素。若N1Nn分解为素数的乘积，设npa1pa2pak (n)

1

1)...(11 证明：因数xnpixAi1npii12k|A1A2...Ak| kn|A||AA| k

|...(1)k|A

...A

jihn

n

n

kki1kk

pip

jihjpipj

1

1)...(11 a1a2···amkl1≤kl≤makak+1···almkkSkai，Skrkmodm0≤rk≤m-1，k12,·,m.lSl≡0modm命题成立．否则，1≤rk≤m-1k12,·,m．由鸽巢原理，故存在rk=rh,Sk≡Sh，不妨设h＞kSh－Sk=ak+1+ak+2+…+ah≡0modmkk证Skai，k=12,77S77=(a1a7)+(a8a77S77≤11×12=132S1S2S77S1+21,S77+21共154项．其中最大项S77+21≤132+21=153，由鸽巢原理，必有两项相等．而且必是前段中某项与后段中某项相等．设Sk=Sh+21，k＞h,Sk－Sh 即ah+1+ah+2+…+ak=21633AF，将其不认识的人放入集合S。由鸽巢原理，F、S3FBCDBCDBCDBCABC三人相互认识，得证；若中S中至少有三人，……。AAFSB 十六对K9的边进行红蓝，则必有红K4或蓝色三角形AB AB ABABEDBABACEGDHFBACEBACEGF十七、多项式(abcd)100因此，多项式(abcd)100xyzw100的不同的非xynx0变化到nn1种不同的取值xy只能取固定值nxxyn一共有n1组不同的非负整数解。1xyn的非负整数解的个数为n1。xyznx(yz)nx0nn+1x的每一种取值，(y+z)只能取固定1，y+z=n-xn-x+1组不同的非负整数解.因此，x+y+z=n的不同的非负整数解的个数为，（n+10）+（n+1-1）+（n+1-2）+n+1n+1nn-1)++n+1)(n+2)/22，xyzn(n+1)(n+2)/2。x+y+z+w=100,x+(y+z+w)=x0101101x的每一种取值，(y+z+w)只能2，y+z+w=100-x，一共有(101-x)(102-x)/2组不同的非