附录四习题参考答案
（1）最优解x1=4，x2=3；z=55 （2）最优解x1=2，x2=1；z=13 5.5
最优解x1=x2=1，x3=x4=x5=0；z=5 5.6
最优解(1, 0, 1)和(0, 1, 1)。Z=5. 5.7
最优解为x13=x22=x34=x41=1，最优值为48 5.8
虚拟一人戊，完成各项工作时间取甲乙丙丁中最小者，构造下表 人 任务 A B C D E 甲 25 29 31 42 37 乙 39 38 26 20 33 丙 34 27 28 40 32 丁 24 42 36 23 45 戊 24 27 26 20 32
最优分配方案：甲-B，乙-D和C，丙-E，丁-A；总计需要131小时
5.9 此问题是一个非平衡的纸牌问题，通过虚设一泳姿，而设运动员的游泳成绩为零，化为平衡指派问题。
5.10
解：设xij＝ 1，商贩从i直接去j
0， 否则 整数规划模型为：
min z =
??i?1nndijxij
j?1 s.t
?i?1nxij = 1 (j=1,2, …,n)
?j?1n xij = 1 (i=1,2, …,n)
ui – uj+n xij≤n-1
ui 为连续变量(i=1,2, …,n)，也可取整数值 i，j=1，2， …，n，i≠j 5.11
４２０
附录四习题参考答案
解：设xij表示第i种产品在j机床上开始加工的时刻，模型为 min z ＝ max ﹛x13＋t13，x23＋t23，x33＋t33﹜
s.t xij＋tij≤ti，j＋1 （i＝1，2，3；j＝1，2）加工顺序约束 xij＋tij－xi＋1，j≤M σi
xi+1，j＋ti＋1，j－xij≤M（1－σi） 互斥性约束 i=1,2; j=1,2,3; σi =0或1
xij ≥0
第六章 非线性规划
6.1
▽f（X）＝（2x1?x2x1?2x2,）’ 2222x1?x1x2?x2x1?x1x2?x22?x12?4x1x2?x2） 22x1?2x1x2?2x22?2x12?2x1x2?x21H（X）＝2（222(x1?x1x2?x2)?x12?4x1x2?x26.2
在（0，3，1），（0，1，－1），（2，1，1），（2，3，－1）各点二次型不定，只有在（1，2，0）点二次型正定，故该点为极小点。
6.3
为凸规划 6.4.
f（x）为严格凹函数。因σ＝0.08，Fn＝1/σ＝12.5，查表得n＝6，则
t1＝b0 +F5( a0- b0)=25+(8/13)×(0-25)=9.6154 6 t1’＝a0 +F5( b0- a0)=0+(8/13)×(25-0)=15.3846 6 f（t1）=-68.6715> f（t1’）=-376.7504 故取a1＝0，b1＝15.3846，t2’＝9.6154 t2＝b1 +(F4/F5) ( a1- b1)=5.7692 因f（t2）=25.7624> f（t2’），故取a2＝0，b2＝9.6154，t3’＝5.7692 t3＝b2 +(F3/F4) ( a2- b2)=3.8462 因f（t3）=39.698> f（t3’），故取a3＝0，b3＝5.7692，t4’＝3.8462 t4＝b3 +(F2/F3) ( a3- b3)=1.9231
４２１
FF附录四习题参考答案
因f（t4）=31.444< f（t4’），故取a4＝1.9231，b4＝5.7692，t5＝1.9231，并令ε＝0.01
t5’＝a4+(1/2+ε)( b4- a4)=3.850
因f（t5’）=39.6924> f（t5），故取a5＝3.85，b5＝5.7692，因f（t5’）< f（t3），故t3＝3.8462为近似最优点。
6.5.
（）（）
若取初始点X0＝（1，1）’，则可算出：λ0＝13/34，X1＝（8/34，
（）
-5/34）’，β0＝1/（33×34），λ1＝34/13，从而得到极小点X2＝（0，0）’
6.7
原题可改写为
min f（x）＝－（x－4）2 g1(x) = x-1 ≥ 0 g2(x) = 6-x ≥ 0 K-T条件为：
－2（x*－4）－γ*1＋γ*2＝0 γ*1（x*－1）＝0 γ*2（6－x*）＝0
γ*1，γ*2≥ 0
解得x*＝1为最优，f（x*）＝9
6.8
（1）Kuhn-Tucker条件：
2x1－4x2－10＋γ1＋4γ2－γ3＝0 －4x1＋8x2－ 4＋γ1＋ γ2－γ4＝0 γ1（ 6－ x1－ x2）＝0 γ2（18－4x1－ x2）＝0 γ3 x1 ＝0 γ4 x2 ＝0
γ1，γ2，γ3，γ4 ≥0
求解得x1 ＝4，x2 ＝2，γ1 ＝2，γ2 ＝2，γ3 ＝0，γ4 ＝0 （2）等价的线性规划问题为：
min φ（z）＝z1＋z2
2x1－4x2－y1＋y3＋4y4+ z1＝10 4x1－8x2－y2＋y3＋ y4+ z2＝4 x1＋ x2＋ x3 ＝6 4x1＋ x2 ＋ x4 ＝18
x1，x2，x3，x4，y1，y2，y3，y4，z1，z2 ≥0 求解得（x1，x2，x3，x4）＝（4，2，0，0）；（y1，y2，y3，y4）＝（0，
４２２
附录四习题参考答案
0，2，2）；（z1，z2）＝（0，0）
6.9
第一次迭代用梯度法，第二次迭代借助于线性规划求可行下降方向。
（）（）
前两次的迭代结果是：X0＝（0，0）’，P0＝（1，1）’，λ0＝4/3
（）（）X1＝（4/3，4/3）’，P1＝（1.0，-0.7）’，λ1＝0.314 （）（）X2＝（1.467，1.239）’，f（X2）＝0.863 该问题的最优解是 X*＝（1. 6，1.2）’，f（X*）＝0.8 6.10
构造罚函数
P（x，M）＝（x1－2）4＋（x1－2 x2）2＋M〔min（0，－（x12－x2））〕 （1）（1）
取X＝（2，1）’为初始点，有f（X）＝0，经5次迭代，趋于问题的极小解Xmin＝（1，1），迭代计算的有关数据见下表：
（）（）
K Mk Xk+1 f（Xk+1） 1 0.1 （1.4539，0.7608） 0.0935 2 1.0 （1.1687，0.7407） 0.5753 3 10.0 （0.9906，0.8425） 1.5203 4 100.0 （0.9507，0.8875） 1.8917 5 1000.0 （0.94611，0.89344） 1.9405
第七章 动态规划
7.1
最短路线：A- B2- C1- D 1-E，其长度为8 7.2
（1）最优解为：x1＝2，x2＝1，x3＝3；zmax=108
（2）最优解为：x1＝1.82，x2＝1.574，x3＝3.147；zmin=29.751 7.3
提示：先将该不等式转化为与它等价的数学规划问题 max （x1x2…xn）
x1＋x2＋…＋xn＝a （a>0） xi ≥0，i＝1，2，…，n
然后利用动态规划来求解，令最优值函数为
maxf k（y）＝（x1x2…xk）
x1???xk?yxi >0，i＝1，2，…，k
其中y>0。因而，证明该不等式只需证明f n（a）＝（a/n）n,再用归纳法证明之。
４２３
附录四习题参考答案
7.4
用xki表示从产地i分配给销地k，k+1，…，n的物资的总数，则采用逆推法时，动态规划的基本方程为
minmf k（x1，…，xm）＝﹛?hik(xik)＋f k＋1（xk1－x1k，…，xkm－xiki?1k
k
xmk）﹜
式中 0≤xik≤xki
?xi?1mik＝bk，（ k＝1，2，…，n）
f n+1 =0
并且有 x1i＝ai，（i＝1，2，…，m） 7.5
最优方案是每年均投资于A，三年后的最大利润为440万元。 7.7
最佳产量为：x1＝110，x2＝110.5，x3＝109.5；总最低费用36321元。
7.8
最优解有三个：（1）x1＝1，x2＝3，x3＝1，x4＝0 （2）x1＝2，x2＝1，x3＝2，x4＝0 （3）x1＝0，x2＝5，x3＝0，x4＝0 最大价值为20千元。 7.9
把往4个仓库派巡逻队划分成4个阶段，状态变量sk为k阶段初拥有的未派出的巡逻队，决策变量uk为k阶段派出的巡逻队数，状态转移方程为sk+1＝sk－uk。用逆推法写出的动态规划基本方程为
f 4（s4）＝min﹛p k（uk）﹜
uk?Dk(sk)minf k（sk）＝﹛p k（uk）＋f k＋1（sk＋1）﹜
uk?Dk(sk)式中p k（uk）为k阶段派出uk个巡逻队时预期发生的事故数。 7.10（生产计划问题） （1）线性规划模型：
４２４
附录四习题参考答案
设第j季度工厂生产产品xj吨，第j季度初存贮的产品为yj吨，（显然y1＝0）
min f＝15.6x1＋0.2y2＋14x2＋0.2y3＋15.3x3＋0.2y4＋14.8x4 s.t. x1－y2＝20 y2＋x2－y3＝25 y3＋x3－y4＝30
y4＋x4＝15
0≤x1≤30 0≤x2≤40 0≤x3≤25 0≤x4≤10 yj≥0 j＝2，3，4 （2）动态规划模型：
若将每个季度看作一个阶段，则此问题为一个四阶段的决策问题。令 sk——第k季度初的库存量；xk——第k季度的产量；wk（sk，xk）——第k季度初的生产成本与存贮费之和；fk（sk，xk）——当k季度初的库存量为sk时，从第k季度到年末厂方为完成合同所需支付的最少的生产费用。由题意应有：
wk（sk，xk）＝0.2 sk＋dk xk
状态转移方程 sk＋1＝sk＋xk－bk
min递归方程 fk（sk）＝﹛wk（sk，xk）＋fk＋1（sk＋1）﹜
xk?Dk(sk) f5（s5）＝0
由题意不难知 s1＝0，s5＝0，sk≥0 （k＝2，3，4）
又考虑到当sk≥bk时xk可以为0；当sk 而且当Dk（sk＋1）＝?时xk不能取sk＋1－sk＋bk。 由于sk和xk都是连续变量，集合Dk（sk）为一个区间，故还需根据问题所要求的精度，把sk和xk离散化，然后求解。 ４２５ 附录四习题参考答案 附录四：习题参考答案 第一章 线性规划及单纯形法 1.1 （1）解： 第一，求可行解集合。令两个约束条件为等式，得到两条直线，在第一象限划出满足两个不等式的区域，其交集就是可行集或称为可行域，如图1-1所示，交集为（1/2, 0）。 第二，绘制目标函数图形。将目标函数的系数组成一个坐标点（6，4），过原点O作一条矢量指向点（6，4），矢量的长度不限，矢量的斜率保持4比6，再作一条与矢量垂直的直线，这条直线就是目标函数图形，目标函数图形的位置任意，如果通过原点则目标函数值Z=0，如图1-2所示。 第三，求最优解。图1-2的矢量方向是目标函数增加的方向或称梯度方向，在求最小值时将目标函数图形沿梯度方向的反方向平行移动，（在求最大值时将目标函数图形沿梯度方向平行移动）直到可行域的边界，停止移动，其交点对应的坐标就是最优解，如图1-3所示。最优解x=（1/2, 0）,目标函数的最小值Z=3。 X2 2x1+x2≥1 3x1+4x2≤1.5 O 1/2 X1 图1.1-1 X2 2x1+x2≥1 3x1+4x2≤1.5 (6,4) O 1/2 X1 图1.1-2 ４００ 附录四习题参考答案 X2 2x1+x2≥1 3x1+4x2≤1.5 (6,4) O 1/2 X1 图1.1-3 （2）无可行解；[求解方法与（1）类似] （3）无界解； （4）无可行解； （5）无穷多最优解 z*=66 （6）唯一最优解 z*=92/3,x1=20/3,x2=3/8 1.2 （1）解：由题目可知，其系数矩阵为 ?1 0 1 0 0??1 0?（P1，P2，P3，P4，P5）即?0 2 0 ? ??3 2 0 0 1???x1?x3?4?1 0 1 ??0 2 0 ?线性独立，故有?2x?12?x因 （P，P，P）??24123???3x?2x?18?x?25?3 2 0 ???1?x1?x3?4?令非基变量x4,x5?0得?2x2?12→ ?3x?2x?182?1得到一个基可行解x(1)?x1?4??x2?6 ?x?2?3T?（2，6，2，0，0），Z1?36。 ４０１ 附录四习题参考答案 ?x1?x3?4?1 1 0 ??0 0 1 ?线性独立，故有?x?12?2x （P，P，P）??42134???3x?18?2x?x?25?3 0 0???1?x1?x3?4?令非基变量x2,x5?0得?x4?12→ ?3x?18?1?x1?6??x4?12 ?x??2?3T得到一个基本解，但非可行解x(2)?，Z2?18。 （6,0,?2,12,0）同理可以求出 ? 1 0 0??，得基本可行解(3)T 0 1 0。 （P3，P4，P5）??x?（0,0,4,12,18）???? 0 0 1???1 0 0??，得基本可行解(4)T0 1 0。 （P??x?（4,0,0,12,6）1，P4，P5）????3 0 1???1 0 0??0 2 1?，得基本可行解(5)T。 （P，P，P）?x?（4,3,0,6,0）124????3 2 0??? 0 1 0??，得基本可行解(6)T 2 0 0。 （P2，P3，P5）??x?（0,6,4,0,6）???? 2 0 1???1 0 0??，得基本非可行解(7)T0 2 0。 （P??x?（4,6,0,0,?6）1，P2，P5）????3 2 1???0 1 0??，得基本非可行解(8)T2 0 1 。 （P2，P3，P4）??x?（0,9,4,?6,0）????2 0 0 ??（1）、（2）答案如下表所示，其中打三角符号的是基本可行解，打星 号的为最优解： ４０２ 附录四习题参考答案 x1 x2 x3 x4 x5 z x1 x2 x3 x4 x5 △ 0 0 4 12 18 0 0 0 0 -3 -5 △ 4 0 0 12 6 12 3 0 0 0 -5 6 0 -2 12 0 18 0 0 1 0 -3 △ 4 3 0 6 0 27 -9/2 0 5/2 0 0 △ 0 6 4 0 6 30 0 5/2 0 -3 0 *△ 2 6 2 0 0 36 0 3/2 1 0 0 △* 4 6 0 0 -6 42 3 5/2 0 0 0 △ 0 9 4 -6 0 45 0 0 5/2 9/2 0 △ 1.3 (1)解：单纯形法 首先，将问题化为标准型。加松弛变量x3，x4，得 maxz?10x1?5x2?3x1?4x2?x3?9 ?st?5x1?2x2?x4?8?x?0?j其次，列出初始单纯形表，计算最优值。 CB 0 0 σj 0 10 σj 5 10 σj XB X3 X4 X3 X1 X2 X1 10 X1 3 5 10 0 1 0 1 0 0 5 X2 4 2 5 14/5 2/5 1 1 0 0 （表一） T*0 X3 1 0 0 1 0 0 5/14 -1/7 -5/14 0 X4 0 1 0 -3/5 1/5 -2 -3/14 2/7 -25/14 B 9 8 21/5 8/5 3/2 1 由单纯形表一得最优解为x?(1,3/2),z?35/2. 图解法： ４０３ 附录四习题参考答案 X2 4 5X1 +2X2≤8 第一步：相当于原点（0,0） 3X1+4X2≤9 9/4 (1, 3/2) O 8/5 3 x1 图1.3-1 X2 4 5X1 +2X2≤8 第二步：相当于点（8/5,0） 3X1+4X2≤9 9/4 (1, 3/2) O 8/5 3 x1 图1.3-2 ４０４ 附录四习题参考答案 X2 4 5X1 +2X2≤8 第三步：相当于点（1,3/2） 3X1+4X2≤9 9/4 (1, 3/2) O 8/5 3 x1 图1.3-3 （2）略 1.4 (1) 解：大M法 首先将数学模型化为标准形式 maxz?4x1?5x2?x3?3x1?2x2?x3?x4?18?2x?x?x?4 ?125st??x1?x2?x3?5?xj?0,(j?1,?,5)?式中x4，x5为松弛变量，x5可作为一个基变量，第一、三约束分别加入人工变量x6 x7，目标函数中加入-Mx6-Mx7一项，得到大M单纯形法数学模型 maxz?4x1?5x2?x3?3x1?2x2?x3?x4?x6?18?2x?x?x?4 ?125st??x1?x2?x3?x7?5?xj?0,(j?1,?,7)?由单纯形表计算： ４０５ 附录四习题参考答案 CB -M 0 -M σ-M 5 -M σj 1 0 -M σj j XB X6 X5 X7 X6 X2 X7 X3 X2 X7 4 X1 3 2 1 -1 2 -1 4-2M -1 2 -2 5-2M 5 X2 2 1 1 0 1 0 0 0 1 0 0 1 X3 1 0 -1 1 1 0 -1 1 1 0 0 0 0 X4 -1 0 0 -M -1 0 0 -M -1 0 -1 1-M 0 X5 0 1 0 0 -2 1 0 -2M -2 1 -2 2-2M -M X6 1 0 0 0 1 0 0 0 -M X7 0 0 1 0 0 0 1 0 0 0 1 0 B 18 4 5 10 4 1 10 4 11 4+4M 5+3M 表1.4-1.1 在迭代过程中，人工变量一旦出基后不会在进基，所以当人工变量X6 出基后，对应第六列的系数可以不再计算，以减少计算量。 当用大M单纯形法计算得到最优解并且存在人工变量大于零时，则表明原线性规划无可行解。 两阶段单纯形法 首先，化标准形同大M法，第一、三约束分别加入人工变量x6 x7后，构造第一阶段问题 minw?x6?x7?3x1?2x2?x3?x4?x6?18?2x?x?x?4 ?125st??x1?x2?x3?x7?5?xj?0,(j?1,?,7)?用单纯形法求解，得到第一阶段问题的计算表1.4-1.2， CB 1 0 1 σj XB X6 X5 X7 0 X1 3 2 1 -4 0 X2 2 1 1 -3 0 X3 1 0 -1 0 0 X4 -1 0 0 1 0 X5 0 1 0 0 1 X6 1 0 0 0 1 X7 0 0 1 0 B 18 4 5 ４０６ 附录四习题参考答案 1 0 1 σj 1 0 1 σj X6 X1 X7 X6 X2 X7 0 1 0 0 -1 2 -1 2 1/2 1/2 1/2 -1 0 1 0 0 1 0 -1 0 1 0 -1 0 -1 0 0 1 -1 0 0 1 -3/2 1/2 -1/2 2 -2 2 -1 3 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 12 2 3 10 4 1 表1.4-1.2 在第一阶段的最优解中人工变量不为零，则原问题无可行解。 注：在第二阶段计算时，初始表中的检验数不能引用第一阶段最优表的检验数，必须换成原问题的检验数。 (2) 无穷多最优解，如X1＝（4，0，0）；X2＝（0，0，8） (3) 无界解 (4) 唯一最优解 X*＝（5/2，5/2，5/2，0） (5) 唯一最优解 X*＝（24，33） (6) 唯一最优解 X*＝（14，0，－4） 1.5 （1） X*仍为最优解，max z＝λCX； （2） 除C为常数向量外，一般X*不再是该问题的最优解； （3） 最优解变为λX*，目标函数值不变。 1.6 （1） d≥0,c1＜0, c2＜0 （2） d≥0,c1≤0, c2≤0,但c1，c2中至少一个为零 （3） d＝0或d＞0，而c1＞0且d/4=3/a2 （4） c1＞0,d/4＞3/a2 （5） c2＞0,a1≤0 （6） x5为人工变量，且c1≤0, c2≤0 1.7 解：设xj表示第j年生产出来分配用于作战的战斗机数；yj为第j年已培训出来的驾驶员；（aj－xj）为第j年用于培训驾驶员的战斗机数；zj为第j年用于培训驾驶员的战斗机总数。则模型为 max z = nx1+(n-1)x2+…+2xn-1+xn s.t. zj=zj-1+(aj-xj) yj=yj-1+k(aj-xj) x1+x2+…+xj≤yj xj,yj,zj≥0 (j=1,2, …,n) 1.8 ４０７ 附录四习题参考答案 提示：设出每个管道上的实际流量，则发点发出的流量等于收点收到的流量，中间点则流入等于流出，再考虑容量限制条件即可。目标函数为发出流量最大。 设xij＝从点i到点j的流量 max z＝x12＋x13 st. x12＝x23＋x24＋x25 x13＋x23＝x34＋x35 x24＋x34＋x54＝x46 x25＋x35＝x54＋x56 以上为流量平衡条件 x12＋x13＝x46＋x56 始点＝收点 x12≤10，x13≤6，x23≤4，x24≤5，x25≤3，x34≤5，x35≤8，x46≤11，x54≤3，x56≤7 xij≥0，对所有i，j 1.9 提示：设每个区段上班的人数分别为x1，x2，…，x6即可 1.10 解：设男生中挖坑、栽树、浇水的人数分别为x11 、x12 、x13，女生中挖坑、栽树、浇水的人数分别为x21 、x22 、x23 ,S为植树棵树。由题意，模型为： max S＝20 x11+10 x21 s.t. x11 +x12 +x13 =30 x21 +x22 +x23 =20 20 x11+10 x21 =30 x12+20 x22=25 x13+15 x23 Xij≥0 i=1,2；j=1,2,3 1.11 解：设各生产x1,x2,x3 max z = 1.2 x1+1.175x2+0.7x3 s.t. 0.6x1+0.15x2 ≤2000 0.2x1+0.25x2+0.5x3≤2500 0.2x1+ 0.6x2+0.5x3≤1200 x1,x2,x3≥0 1.12 解：设7－12月各月初进货数量为xi件，而各月售货数量为yi件，i＝1，2，…，6，S为总收入，则问题的模型为： max S＝29y1＋24y2＋26y3＋28y4＋22y5＋25y6－（28x1＋24x2＋25x3＋27x4＋23x5＋23x6） st. y1≤200＋x1≤500 y2≤200＋x1－y1＋x2≤500 y3≤200＋x1－y1＋x2－y2＋x3≤500 y4≤200＋x1－y1＋x2－y2＋x3－y3＋x4≤500 y5≤200＋x1－y1＋x2－y2＋x3－y3＋x4－y4＋x5≤500 y2≤200＋x1－y1＋x2－y2＋x3－y3＋x4－y4＋x5－y5＋x6≤500 ４０８ 附录四习题参考答案 xi≥0，yi≥0 i＝1，2，…，6 整数 1.13 解：用x1，x2，x3分别代表大豆、玉米、麦子的种植面积（hm2，公顷）；x4，x5分别代表奶牛和鸡的饲养数；x6，x7分别代表秋冬和春夏季多余的劳动力（人日），则有 maxz?175x1?300x2?120x3?400x4?2x5?1.8x6?2.1x7 ?100(土地限制）?x1?x2?x3?1.5x4 ? 400x4?3x5 ?15000(资金限制）? ?20x?35x?10x?100x?0.6x?x ?3500?123456?（劳动力限制）??50x?175x?40x?50x?0.3x?x?4000st.?123457??x?32（牛栏限制）?4?x5?3000(鸡舍限制）??，7）??xj?0(j?1， 第二章 对偶理论和灵敏度分析 2.1 对偶问题为 mins?10y1?20y2?y1?4y2?10?(1) ?y1?y2?1st??2y1?y2?2??y1,y2?0mins?5y1?4y2?y3?y1?2y2?y3?2?y1?y2?1 (2)? ?st?y1?3y2?y3?3?y?y?13?1??y1?0,y2?0,y3无约束maxs?15y1?20y2?5y3mins?3y1?5y2?2y3?y1?2y3?3??y1?5y2?y3??5??2y?y?3y?2?5y?6y?y??6123(3) ?(4) ?1?23st?st?3y1?3y2?7y3??3?3y1?10y2?y3??7?y?y?y?123??1?y1?0,y2?0,y3无约束?y?0,y?0,y无约束23?1 ４０９ 附录四习题参考答案 2.2 （1）因为对偶变量Y=CBB-1,第k个约束条件乘上λ（λ≠0），即B-1的k列将为变化前的1/λ，由此对偶问题变化后的解（y’1, y’2, …, y’k,…y’m）=（y1, y2, …, (1/λ)yk,…ym） （2）与前类似，y’r= bryr ，y’i= yi（i≠r） br??bk （3）y’i=λyi（i=1,2, …,m） （4）yi（i=1,2, …,m）不变 2.3 (1) 对偶问题为 maxs?3y1?6y2?2y3?2y4?y1?3y2?y4?8??2y1?y2?6?st?y2?y3?y4?3?y?y?y?623?1??y1,y2,y4?0,y3无约束 (2) 由互补松弛性——ysX*?0（ys,X*分别为松弛变量和最优 解）可得y5?y6?y7?0，从而可知， y1?3y2?y4?82y1?y2?6y2?y3?y4?3又由对偶性质的最优性——CX?Yb可得 ** 3y1?6y2?2y3?2y4?20 四方程联立即可求得对偶问题的最优解： Y*＝（2，2，1，0） 2.4 解： 其对偶问题为 min w=8y1+12y2 ４１０ 附录四习题参考答案 2y1+2y2 ≥2 (1) 2y2 ≥1 (2) y1+y2 ≥5 (3) y1+2y2 ≥6 (4) y1, y2 ≥0 将y1*,y2* 代入约束条件，得（1）与（2）为严格不等式，由互补松弛性YsX*=0得x1*=x2*=0；又因为y1, y2≥0，由互补松弛性 Y*Xs=0，得Xs1=Xs2=0，即 原问题约束条件应取等号，故 x3+x4=8 解之得 x3=4 x3+2x4=12 x4=4 所以原问题最优解为X*=(0, 0, 4, 4)T，目标函数最优值为 Z*=44。 2.5 （1） 略 （2） 原问题的解 互补的对偶问题的解 第一步（0，0，0，60，40，80） （0，0，0，－2，－4，－3） 第二步（0，15，0，0，25，35） （1，0，0，1，0，－1） 第三步（0，20/3，50/3，0，0，80/3） （5/6，2/3，0，11/6，0，0） （3） 对偶问题的解 对偶问题互补的对偶问题的解 第一步（0，0，0，－2，－4，－3） （0，0，0，60，40，80） 第二步（1，0，0，1，0，－1） （0，15，0，0，25，35） 第三步（（5/6，2/3，0，11/6，0，0） （0，20/3，50/3，0，0，80/3） （4） 比较（2）和（3）计算结果发现，对偶单纯形法实质上是将单纯形法应用于对偶问题的求解，又对偶问题的对偶即原问题，因此两者计算结果完全相同。 2.6 （1）15/4≤c1≤50,4/5≤c2≤40/3 （2）24/5≤b1≤16，9/2≤b2≤15 （3）X*=（8/5，0，21/5，0） （4）X*=（11/3，0，0，2/3） 2.8 （1）a=40,b=50,c=x2,d=x1,e=-22.5,f=-80,g=s-440 （2）最大值 （3）2?a+?b>= -90, ?a+2?b>= -80 2.9 （1）x1,x2,x3代表原稿纸、日记本和练习本月产量，建模求解最终单纯形表如下： x1 x2 x3 x4 x5 x2 2000 0 1 7/3 1/10 -10 ４１１ 附录四习题参考答案 x1 1000 1 0 -4/3 -1/10 40 cj-zj 0 0 -10/3 -1/10 -50 （2）临时工影子价格高于市场价格，故应招收。招200人最合适。 2.10 (1) s=13x1-(2x1*1.0+3x1*2.0)+16x2-(4x2*1.0+2x2*2.0） =5x1+8x2 max z=5x1+8x2 s.t. 2x1+4x2≤160 3x1+2x2≤180 x1,x2≥0 X*= (50,15) max z=370元 （2）影子价格： A ：7/4 B：1/2 （3）CBB-1p-（-c3+11）≥0 CB=73/4=18.25 （4）b’ = (160+a,180), B-1 b =((3/8)a +15,50-a/4) ≥0 得到-40≤a ≤200 a=200 增加利润350元 X2 X1 s 15+(3/8)a 50- a/4 -370- 7a/4 X1 0 1 0 X2 1 0 0 X3 3/8 -1/4 -7/4 X4 -1/4 1/2 -1/2 第三章 运输问题 3.1 解： 表3.1-1 A1 A2 A3 需要量 B1 (10) (16) (5) 5 B2 （6） （10） （4） 3 B3 （7） （5） （10） 4 B4 （12） （9） （10） 6 供应量 4 9 5 18 西北角法是优先从运价表的西北角的变量赋值，当行或列分配完毕后，再在表中余下部分的西北角赋值，以此类推，直到右下角元素分配完毕。 表3.1-1西北角元素是x11, x11=min｛a1, b1｝= min｛4, 5｝= 4，将4填 在C11的左侧，表示A1供应4单位给B2。同时将第一行划去，表示A1的产量全部运出，得表3.1-2。在表3.1-2中，西北角元素是x21，x21= min｛9, 5-4｝=1，同时降第一列划去，表示B1已满足需要，得到表3.1-3。依次向 ４１２ 附录四习题参考答案 右下角安排运量，结果如表3.1-4所示。 表3.1-2 A1 A2 A3 需要量 A1 A2 A3 需要量 A1 A2 A3 需要量 B1 4 (10) (16) (5) 5 B1 4 (10) 1 (16) (5) 5 B1 4 (10) 1 (16) (5) 5 B2 （6） （10） （4） 3 B2 （6） （10） （4） 3 B2 （6） 3（10） （4） 3 B3 （7） （5） （10） 4 表3.1-3 B3 （7） （5） （10） 4 表3.1-4 B3 （7） 4（5） （10） 4 B4 （12） 1（9） 5（10） 6 供应量 4 9 5 18 B4 （12） （9） （10） 6 供应量 4 9 5 18 B4 （12） （9） （10） 6 供应量 4 9 5 18 最小元素法的思想是就近优先运送，即最小运价cij对应的变量xij优先赋值xij=min｛ai, bj｝，然后在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后得到一个初始基本可行解。 表3.1-1中最小元素是C32，令x32=min｛a3, b2｝= min｛5, 3｝= 3，同时将第二列划去，得到表3.1-5。在表3.1-5中，最小元素为C23，C31，任意选取其一，这里选C31，令x31= min｛5-3, 5｝=2，同时将第三行划去，得表3.1-6。依次进行下去，其结果见表3.1-7。 表3.1-5 A1 A2 A3 需要量 A1 A2 B1 (10) (16) (5) 5 B1 (10) (16) B2 （6） （10） 3（4） 3 B2 （6） （10） B3 （7） （5） （10） 4 表3.1-6 B3 （7） （5） B4 （12） （9） （10） 6 B4 （12） （9） 供应量 4 9 5 18 供应量 4 9 ４１３ 附录四习题参考答案 A3 需要量 A1 A2 A3 需要量 (5) 5 B1 3 (10) (16) 2 (5) 5 3（4） 3 B2 （6） （10） 3（4） 3 （10） 4 表3.1-7 B3 （7） 4（5） （10） 4 （10） 6 B4 1（12） 5（9） （10） 6 5 18 供应量 4 9 5 18 伏格尔法是最小元素法的改进，考虑到产地到销地的最小运价和此小运价之间的差额，如果差额很大，就选最小运价处险调运，否则会增加总运费。 在表3.1-1中求行差额?i(i?1,2,3)和列差额?j(j?1,?4)。计算公式为 ?i?i行次小运价?i行最小运价， ?j?j列次小运价?j列最小运价 max??i,?j??max?1,4,1,5,2,2,1??5,即?1最大，第一列的最小运价使c31,所以先调运x31?min?a3,b1??min?5,5??5，这时A3和B1同时满足约束，若同时将第三行与第一列划去，最后即变量个数比小于3+4-1=6个，因而应再x32，x33,x34和x11,x12中任意选一个变量作为即变量，运量为零，这里选x11，如表3.1-8所示。 求第二个基变量仍然是求差额，因为第三行和第一列已满足，所以只求u1,u2和v2，v3，v4即可，结果见表3.1-9。此时，有两个最大差额u2，v2，任选一个即可，这里选v2.第二列最小运价为c12，故x12=min｛4,3｝=3.同 时将第二列划去。这样依次下去，其结果见表3.1-10。 表3.1-8 A1 A2 A3 需要量 vj B1 0 (10) (16) 5 (5) 5 【5】 B1 B2 （6） （10） （4） 3 2 B2 B3 （7） （5） （10） 4 2 表3.1-9 B3 B4 供应量 ui B4 （12） （9） （10） 6 1 供应量 4 9 5 18 ui 1 4 1 ４１４ 附录四习题参考答案 A1 A2 A3 需要量 vj A1 A2 A3 需要量 3.4 (1) A1 A2 A3 需要量 （2） A1 A2 A3 需要量 3.5 0 (10) (16) 5 (5) 5 — B1 0 (10) (16) 5 (5) 5 （6） （10） （4） 3 【4】 B2 3（6） （10） （4） 3 （7） （5） （10） 4 2 表3.1-10 B3 （12） （9） （10） 6 3 B4 （12） 6（9） （10） 6 4 9 5 18 1 4 — 供应量 4 9 5 18 1（7） 3（5） （10） 4 B1 8（6） （4） （2） 8 B1 8（6） （4） （2） 8 B2 （7） （5） 6（9） 6 B2 （7） （5） 6（9） 6 B3 0（5） 4（10） 1（7） 5 B3 2（5） 4（10） 1（7） 5+2 B4 （8） 5（8） （3） 5 B4 （8） 5（8） （3） 5 供应量 8 9 7 24 供应量 8+2 9 7 24 甲 乙 丙 丁 可供量 A 500 500 1000 B 1500 500 2000 C 500 1500 2000 销售量 1500 1500 1500 500 3.6 存贮能力大，即产大于销，虚拟一个销地，所需存取时间为0，文件数为100，最优解为：x11=200, x21=100, x31=0 ,x32=100, x33=100, x34=100 最优值为：(200×5＋100×2)×8＋100×8×4＋100×6×2＝14000 3.7 ４１５ 附录四习题参考答案 解：用伏格尔法初始解：28.5+29.6+34.7+35.4=128.2 仰 泳 蛙 泳 蝶 泳 自由泳 泳 仰 泳 蛙 泳 蝶 泳 自由泳 泳 仰 泳 蛙 泳 蝶 泳 自由泳 泳 仰 泳 蛙 泳 蝶 泳 自由泳 赵 37.7 43.4 33.3(0) 29.2(0) 0(1) 赵 37.7 43.4 33.3(0) 29.2(1) 0(0) 赵 37.7 43.4 33.3 [29.2] 钱 32.9 33.1 28.5(1) 26.4 0 钱 32.9 33.1 28.5(1) 26.4 0 钱 32.9 33.1 [28.5] 26.4 张 [33.8] 42.2 38.9 29.6 王 37.0 [34.7] 30.4 28.5 周 35.4 41.8 33.6 31.1 张 33.8(1) 42.2 38.9 29.6(0) 0 王 37.0 34.7(1) 30.4 28.5 0 周 35.4(0) 41.8 33.6 31.1 0(1) 张 33.8（2） 42.2 38.9 29.6(1) 0 王 37.0 34.7(1) 30.4 28.5 0 周 35.4(1) 41.8 33.6 31.1 0(0) 赵 37.7 43.4 33.3(0) 29.2(0) 0(1) 钱 32.9 33.1 28.5(1) 26.4 0 张 33.8 42.2 38.9 29.6(1) 0 王 37.0 34.7(1) 30.4 28.5 0 周 35.4(1) 41.8 33.6 31.1 0(0) 最优解：29.2+28.5+33.8+34.7=126.2 3.8 （1）a=5,b=5,c=5,d=6,e=15 最优解略 （2）c31≥8 3.9 数学模型为： min z = ??ci?1j?1mnijijx ４１６ 附录四习题参考答案 s.t ?xj?1mnij≤ai (i=1,2,…,m) ?xi?1ij≥bj (j=1,2,…,n) xij≥0 上面第一个约束条件可以改写为－ ?xj?1nij≥－ai，则对偶问题为： max z’ = ?bvjj?1nj－?auii?1mi s.t vj ≤ui +cij (i=1,2,…,m j=1,2,…,n) ui, vj≥0 对偶变量ui的经济意义为在i产地单位物资的价格，vj的经济意义为在j销地单位物资的价格。对偶问题的经济意义为：如该公司欲自己将该种物资运至各地销售，其差价不能超过两地之间的运价（否则买主将在i地购买自己运至j地），在此条件下，希望获利为最大。 3.10 用xj表示每期（半年一期）的新购数，yij表示第i期更换下来送去修理用于第j期的发动机数。显然当j>i＋1时，应一律送慢修，cij为相应的修理费。每期的需要数bj为已知，而每期的供应量分别由新购与大修送回来的满足。如第1期拆卸下来的发动机送去快修的可用于第2期需要，送去慢修的可用于第3期及以后各期的需要。因此每期更换下来的发动机数也相当于供应量，由此列出这个问题用运输问题求解时的产销平衡表与单位运价表为： 1 2 3 4 5 6 库存 供应量 新 购 10 10 10 10 10 10 0 660 第1期送修的 M 2 1 1 1 1 0 100 第2期送修的 M M 2 1 1 1 0 70 第3期送修的 M M M 2 1 1 0 80 第4期送修的 M M M M 2 1 0 120 第5期送修的 M M M M M 2 0 150 需 求 量 100 70 80 120 150 140 520 3.11. ４１７ 附录四习题参考答案 解：转运问题，最优解如下表 甲 乙 A B C 产 量 甲 1000 500 1500 乙 900 300 300 1500 A 1000 1000 B 1000 1000 C 100 900 1000 销 量 1000 1000 1300 1300 1400 第四章 目标规划 4.1分别用图解法和单纯形法求解下述目标规划问题 （1）满意解为X1＝（50/3，0）’，X2＝（88/9，62/9）’间线段 （2）满意解为X＝（4，6）’ 4.2. －－－－ （1）满意解X＝（0，35）’，d1＝20，d3＝115，d4＝95，其余di＋ ＝di＝0 －－－ （2）满意解X＝（0，220/3）’，d1＝20，d2＝5/3，d4＝400/3，其－＋ 余di＝di＝0 －－－－ （3）满意解X＝（0，35）’，d1＝20，d3＝115，d4＝95，d5＝27，－＋ 其余di＝di＝0 （4）满意解不变 4.3 设安排商业节目x1小时，新闻x2小时，音乐x3小时，模型为： －－－min z = p1(d1+ d2+d+3) + p2d4 －s.t x1 + x2 + x3 + d1 = 12 － x1 + d2= 2.4 x2 - d+3 = 1 － 250x1 - 40x2 – 17.5x3 + d4 - d+4= 600 －－－ x1, x2, x3, d1 ,d2 ,d+3 ,d4 , d+4 ≥0 4.4 略 4.5 设A、B型机的产量分别为x1，x2台，模型为： ４１８ 附录四习题参考答案 ???minz?P1d1??P2(d2?d3?)?P3(d4?d4?d5?)?300x1?450x2?d1??d1??104????x1?d2?d2?10?x?d??d??15?233st????4x1?6x2?d4?d4?150?3x?2x?d??d??70255?1????x1,x2?0,di,di?0,(i?1,?,5) 第五章 整数规划 5.1 解：令y＝ 1，当x2＝x3＝1时 0，否则 故有x2x3＝y，又x12，x33分别与x1，x3等价，因此原模型可转换为 max z ＝ x1＋ y－ x3 st. －2x1＋3x2＋ x3 ≤ 3 y ≤ x2 y ≤ x3 x2＋ x3 ≤ y＋1 xj ＝ 0或1（j＝1,2,3）；y＝ 0或1 5.2 min z = 10?cxjj?110j s.t ?xj?1j= 5 x1 + x8 = 1 x3 + x5 ≤ 1 x7 + x8 = 1 x4 + x5 ≤ 1 x5 + x6 + x7 + x8 ≤ 2 xj＝ 1，选择钻探sj井位 0，否则 5.3 （1）最优解x1=2，x2=2或x1=3，x2=1；z=4 （2）最优解x1=4，x2=2；z=14 5.4 ４１９ 附录四习题参考答案 设第j季度工厂生产产品xj吨，第j季度初存贮的产品为yj吨，（显然y1＝0） min f＝15.6x1＋0.2y2＋14x2＋0.2y3＋15.3x3＋0.2y4＋14.8x4 s.t. x1－y2＝20 y2＋x2－y3＝25 y3＋x3－y4＝30 y4＋x4＝15 0≤x1≤30 0≤x2≤40 0≤x3≤25 0≤x4≤10 yj≥0 j＝2，3，4 （2）动态规划模型： 若将每个季度看作一个阶段，则此问题为一个四阶段的决策问题。令 sk——第k季度初的库存量；xk——第k季度的产量；wk（sk，xk）——第k季度初的生产成本与存贮费之和；fk（sk，xk）——当k季度初的库存量为sk时，从第k季度到年末厂方为完成合同所需支付的最少的生产费用。由题意应有： wk（sk，xk）＝0.2 sk＋dk xk 状态转移方程 sk＋1＝sk＋xk－bk min递归方程 fk（sk）＝﹛wk（sk，xk）＋fk＋1（sk＋1）﹜ xk?Dk(sk) f5（s5）＝0 由题意不难知 s1＝0，s5＝0，sk≥0 （k＝2，3，4） 又考虑到当sk≥bk时xk可以为0；当sk 而且当Dk（sk＋1）＝?时xk不能取sk＋1－sk＋bk。 由于sk和xk都是连续变量，集合Dk（sk）为一个区间，故还需根据问题所要求的精度，把sk和xk离散化，然后求解。 ４２５ 百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库运筹学规划习题答案在线全文阅读。
相关推荐：
