2.2 将下列线性规划模型化为标准形式并列出初始单纯形表。

（1）123123123123123min 243221943414..524260,0,z x x x x x x x x x s t x x x x x x =++-++≤⎧⎪-++≥⎪⎨--=-⎪⎪≤≥⎩无约束 解：（1）令11333','",'x x x x x z z =-=-=-，则得到标准型为（其中M 为一个任意大的正数）12334567123341233561233712334567max '2'24'4''003'22'2''194'34'4''14..5'24'4''26',,','',,,,0z x x x x x x Mx Mx x x x x x x x x x x x s t x x x x x x x x x x x x x =-++-++--++-+=⎧⎪++--+=⎪⎨++-+=⎪⎪≥⎩初始单纯形表如表2-1所示：2.3 用单纯形法求解下列线性规划问题。

（1）123123123123123max 2360210..220,,0z x x x x x x x x x s t x x x x x x =-+++≤⎧⎪-+≤⎪⎨+-≤⎪⎪≥⎩ （2） 1234123412341234min 52322347..2223,,,0z x x x x x x x x s t x x x x x x x x =-+++++≤⎧⎪+++≤⎨⎪≥⎩解：（1）最优解为**(15,5,0),25T x z ==。

（2）最优解为**(0,1.5,0,0),3T x z ==-。

2.4 分别用大M 法和两阶段法求解下列线性规划问题。

（1） 123123123123max 2357..2510,,0z x x x x x x s t x x x x x x =+-++=⎧⎪-+≥⎨⎪≥⎩ （2） 12121231241234min 433436..24,,,0z x x x x x x x s t x x x x x x x =++=⎧⎪+-=⎪⎨++=⎪⎪≥⎩ 解：（1）最优解为**(6.429,0.571,0),14.571T x z ==。

（2）最优解为**(0.4,1.8,1,0), 3.4T x z ==。

2.6 已知线性规划问题123451234512345min 23523234..2330,1,2,,5jZ x x x x x x x x x x s t x x x x x x j =++++⎧++++≥⎪-+++≥⎨⎪≥=⎩其对偶问题最优解为***124/5,3/5;5y y Z ===。

试用对偶理论找出原问题最优解。

解：先写出它的对偶问题12121212121212max 43223235..233,0w y y y y y y y y s t y y y y y y =++≤⎧⎪-≤⎪⎪+≤⎪⎨+≤⎪⎪+≤⎪≥⎪⎩将**124/5,3/5y y ==代入约束条件可知，第2、3、4个约束为严格不等式，因此，由互补松弛性得***2340x x x ===。

又因为**12,0y y >，所以原问题的两个约束条件应取等式，因此有**15**153423x x x x ⎧+=⎪⎨+=⎪⎩ ⇒ *1*511x x ⎧=⎪⎨=⎪⎩ 故原问题最优解为**(1,0,0,0,1),5T X z ==。

2.12 现有线性规划问题123123123123max 5513320..1241090,,0z x x x x x x s t x x x x x x =-++-++≤⎧⎪++≤⎨⎪≥⎩先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？（1）约束条件①的右端项系数由20变为30；（2）约束条件②的右端项系数由90变为70； （3）目标函数中3x 的系数由13变为8； （4）1x 的系数列向量由(1,12)T-变为(0,5)T； （5）将原约束条件②改变为12310510100x x x ++≤； （6）增加一个约束条件12323550x x x ++≤。

解：在上述LP 问题的第①、②个约束条件中分别加入松弛变量x 4,x 5得123451234123512345max 551300320..1241090,,,,0z x x x x x x x x x s t x x x x x x x x x =-++++-+++=⎧⎪+++=⎨⎪≥⎩① ②列出此问题的初始单纯形表并进行迭代运算，过程如表2-11所示。

由表2-11中的计算结果可知，LP 问题的最优解X *=(0,20,0,0,10)T ，z *=5*20=100。

（1）约束条件①的右端项系数由20变为30，则有1103030419030B b -⎡⎤⎡⎤⎡⎤==⎢⎥⎢⎥⎢⎥--⎣⎦⎣⎦⎣⎦ 列出单纯形表，并利用对偶单纯形法求解，过程如表2-12所示。

由表2-12中计算结果可知，LP 问题的最优解变为**(0,0,9,3,0),139117T X z ==⨯=。

（2）约束条件②的右端常数由90变为70，则有1102020417010B b -⎛⎫⎛⎫⎛⎫== ⎪⎪ ⎪--⎝⎭⎝⎭⎝⎭列出单纯形表，并利用对偶单纯形法求解，结果如表2-13所示。

由表2-13结果知，LP 问题的最优解变为**(0,5,5,0,0),5513590T X z ==⨯+⨯=。

（3）目标函数中x 3的系数由13变为8，由于x 3是非基变量，其检验数变为38530(2)70σ=-⨯-⨯-=-< 所以LP 问题的最优解不变。

（4）x 1的系数列向量由(-1,12)T 变为(0,5) T ，则x 1在最终单纯形表中的系数列向量变为1'110004155B P -⎡⎤⎡⎤⎡⎤==⎢⎥⎢⎥⎢⎥-⎣⎦⎣⎦⎣⎦ 从而x 1在最终单纯形表中的检验数变为'1'11105(5,0)505B cC B P σ-⎡⎤=-=--=-<⎢⎥⎣⎦所以LP 问题的最优解保持不变。

（5）将原约束条件②改变为10x 1+5x 2+10x 3≤100，则x 1在最终单纯形表中系数列向量变为'111(1,14)T P B P -==-，检验数'11115(5,0)(1,14)0TB cC B P σ-=-=---=x 2在最终单纯形表中系数列向量变为'122(1,1)T P B P -==，检验数'12225(5,0)(1,1)0T B c C B P σ-=-=-=。

又因11020204110020B b -⎡⎤⎡⎤⎡⎤==⎢⎥⎢⎥⎢⎥-⎣⎦⎣⎦⎣⎦的各分量均大于0，故LP 问题的最优解不变。

（6）增加一个约束条件2x 1+3x 2+5x 3≤50，则在此约束条件中加入松弛变量x 6，并将此约束加入到最终单纯形表中，继续迭代，过程如表2-14所示。

由表2-14中计算结果可知，LP 问题的最优解变为*(0,25/2,5/2,0,15,0)T X =，*525/2135/295z =⨯+⨯=。

3.1 分别用分支定界法和割平面法求解下列整数规划模型。

（1）12min 43z x x =-- （2）12max z x x =+121212410..238,0,x x s t x x x x +≤⎧⎪+≤⎨⎪≥⎩且为整数 12121226..4520,0,x x s t x x x x +≤⎧⎪+≤⎨⎪≥⎩且为整数 解：（1）求解得到最优解***122,1,11x x z ===-。

（计算步骤略） （2）仅写出利用割平面法求解的过程。

在原IP 问题约束条件中加入松弛变量x 3,x 4，化为标准型，可得12341231241234max 0026..4520,,,0z x x x x x x x s t x x x x x x x =+++++=⎧⎪+++=⎨⎪≥⎩且为整数不考虑整数条件，用单纯形法求解原问题的松弛问题，计算结果如表3-1所示。

表因此，松弛问题的最优解为x 1=5/3,x 2=8/3,x 3=0,x 4=0;z =13/3。

由于x 2不为整数，因此在最终单纯形表中根据x 2所在的行作割平面342/31/3()0x x -+≤ 即342x x --≤-将它作为约束条件，引入松弛变量后加到最终单纯形表中，并采用对偶单纯形法继续迭代，计算过程如表3-2所示。

由于12,x x 的值均为整数，所以得到原问题的最优解为**(2,2),4T x z ==3.4 某厂新购4台不同类型机器，可以把它们安装在4个不同的地点。

由于对特定的机器而言，某些地方可能安装起来特别方便且合适，所以不同的机器安装在不同的地点费用是不同的。

估计的费用见表3-3，试制定使得总安装费用最小的安装方案。

解：设 1,0,ij i jx =⎧⎨⎩如果机器安装在地点否则c ij —机器i 安装在地点j 所需的费用。

建立该问题的数学模型如下：目标函数：4411min ij iji j z c x ===∑∑约束条件：(1)每一部机器只分配在一个地点，即4111,2,3,4ijj x i ===∑(2)每一个地点只能有一台机器，即 4111,2,3,4iji xj ===∑(3) 01ij x =或工作指派问题可以看成是一类特殊的运输问题，每个供应点的供应量为1，每个需求点的需求量也为1。

因此，本题可以采用表上作业法进行计算，也可以利用匈牙利法进行计算。

计算得到的最佳安装方案为：机器1安装在地点4、机器2安装在地点1、机器3安装在地点3、机器4安装在地点2，最小总安装费为14元。

3.9 设有三个化肥厂供应四个地区的农用化肥。

假定等量的化肥在这些地区使用的效果相同。

各化肥厂年产量、各地区年需求量及从各化肥厂到各地区运送单位化肥的运价如表3-17所示。

试确定使总运费最少的化肥调拨方案。

解：这是一个产销不平衡的运输问题，总产量为160万t ，四个地区的最低需求为110万t ，最高需求为无限。

根据现有产量，第IV 个地区每年最多能分配到60万t ，这样最高需求就为210万t ，大于产量。

为了求得平衡，在产销平衡表中增加一个假想的化肥厂D ，其年产量为50万t 。

由于各地区的需求量包含两部分，如地区I ，其中30万t 是最低需求，故不能由假想化肥厂D 供给，令相应的单位运价为M （任意大的正数）；而另一部分20万t 满足或不满足均可以，因此可以由假想化肥厂D 供给，按前述，可令相应的单位运价为0。