运筹学作业题

1．已知某线性规划问题的初始单纯形表和用单纯形表法迭代后得到的表1，试求括号中未知数a-l的数值。 项目 x4 6 x5 1 cj-zj x1 (f) x5 4 cj-zj x1 x2 x3 x4 x5 (b) (c) (d) 1 0 -1 3 (e) 0 1 (a) -1 2 0 0 (g) 2 -1 1/2 0 (h) (i) 1 1/2 1 0 -7 (j) (k) (l) 解：

（1）X5是基变量，检验数l=0 （2）x1是基变量，则，g=1，h=0 （3）x4行乘以1/2得到迭代后的x1行 所以，f=6*1/2=3, b=2，c=4，d=-2

（4）x4行乘以1/2加到x5行上，得到迭代后的x5行 所以，c*1/2+3=i，i=5，d*1/2+e=1, e=2

（5）迭代前为初始单纯形表，价值系数为初始表检验数

所以，x2价值系数为-1， x3价值系数为2，x4价值系数为0 则，-7=-1-（2a-0*i），所以a=3

j=2-（-a）=5；k=0-（1/2*a+1/2*0）=-3/2

即，a=3，b=2，c=4，d=-2，e=2, f=3, g=1, h=0, i=5, j=5, k= -3/2, l=0

2.已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯

形表如下表2所示。求表中括号中未知数的值 cj→ CB 0 0 0 基 x4 x5 x6 cj- zj … 0 3 2 x4 x1 x2 cj- zj 5/4 25/4 5/2 0 1 0 0 0 0 1 （k） (d) (e) (f) （g） b （b） 15 20 3 x1 1 （a） 2 3 2 x2 1 1 （c） 2 2 x3 1 2 1 2 0 x4 1 0 0 0 … （l） 0 0 0 -1/4 3/4 （h） -5/4 -1/4 （i） 1/2 （j） 0 x5 0 1 0 0 0 x6 0 0 1 0 解：初始单纯形表中的单位矩阵，在最终单纯形表中变化为B-1

(1) B?1?l?1?l?1?1??1??b??5/4?44?44??????25/4? '?1??03i? b?Bb??03i??15????44????11?20??5/2?0h0h???2?2????????在最终表中，x4是基变量，所以l=1 所以，b=10，i=-1/4，h=-1/2

?1?1?1??1??0?44??'???1? 则a=2 ?13?1??a(2) p1?Bp1??044??????1??2?0?0?1??????22???1?1?1??1??0?44??'???0? 则c=3 ?13?1??1（3）p2?Bp2??044??????1?c??1?0?1?22???????以此类推其它未知数取值。

即，a=2 b=10 c=3 d=1/4 e=5/4 f=-1/2 g=-3/4 h= -1/2 i= -1/4 j= -1/4 k=0 l=1

3.给出线性规划问题

maxz?2x1?4x2?x3?x4?x1?2x1 ??st.??x?1???3x2?x2x2??x3??x4x4?8?6?6?9

x2?x3xj?0(j?1,..4.),要求：（1）写出其对偶问题；（2）已知原问题最优解为X*=(2,2,4,0)，试根据对偶理论，直

接写出对偶问题的最优解。 解：（1）其对偶问题为

minw?8y1?6y2?6y3?9y4?y1?3y1??st.??y?1???2y2?y2?y3y3???y4y4y4?2?4?1?1

?y3yj?0(j?1,...,4)（2）根据对偶理论知，x1?2,x2?2,x3?4 均绝对大于零，所以其变量对应的对偶问题的约束条件取严格等式。原问题与对偶问题同时取得最优解，且目标函数值相等。则可得：

minw?8y1?6y2?6y3?9y4?y1?3y??1st.???8y1???2y2?y2?6y2?y3y3?6y3?y4?y4?y4?9y4?y1?45?2?y?35?2?4解得，?

y?1?1?3??2x1?4x2?x3?x4?y4?04.某厂生产A/B/C三种产品，其所需劳动力、材料等相关数据见下表。要求：

（1）确定获利最大的产品生产计划；（2）产品A的利润在什么范围内变动时，上述最优计划不变；（3）如果设计一种新产品D，单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该产品是否值得生产？（4）如果劳动力数量不增，材料不足时可从市场购买，没单位0.4元。问该厂要不要购进原材料扩大生产，以购进多少为宜。 消耗定额 资源 劳动力 材料 产品 A B C 可用量（单位） 6 3 3 4 1 5 5 4 45 30 产品利润（元/件） 3 解：

（1）设A/B/C三种产品的产量分别为x1，x2，x3，写出最优生产计划数学模型。

maxz?3x1?x2?4x3?6x1?3x2?5x3?45 ?st.?6x1?3x2?5x3?45?x?0,j?1,2,3?j标准化后，列单纯形表计算。 cj→ CB 0 0 0 4 3 4 基 x4 x5 cj- zj x4 x3 cj- zj x1 x3 cj- zj 5 3 15 6 b 45 30 3 x1 6 3 3 (3) 3/5 3/5 1 0 0 1 x2 3 4 1 -1 4/5 -11/5 -1/3 1 -2 4 x3 5 （5） 4 0 1 0 0 1 0 0 x4 1 0 0 1 0 0 1/3 -1/5 -1/5 0 x5 0 1 0 -1 1/5 -4/5 -1/3 2/5 -3/5 所有检验数均小于等于零，所以当前解为最优解。

?x1?5??x2?0 ?x?3?3（2）假设产品A的利润变动量为λ时，上述最优计划不变。 则体现在最终单纯形表上为： cj→ CB 3+λ 4 基 x1 x3 cj- zj b 5 3 3+λ x1 1 0 0 1 x2 -1/3 1 λ/3-2 4 x3 0 1 0 0 x4 1/3 -1/5 -λ/3-1/5 0 x5 -1/3 2/5 λ/3-3/5 抱持最优计划不变，则需要当前解仍为最优解。即检验数行均小于等于零。 ???3?2?0?39??1解得 ???????0?55?35???3?0??351224所以 ???3?55即在上述范围内最优计划不变。

（3）设计新产品，相当于增加一列p，则有

?1?3'?1p6?Bp6??1???51????8??2?3?????4? 2??2?5??????5??2?1?6?c6??34???4??

?5??5?因为检验数大于零，所以此产品值得生产。

（4）劳动力数量不增，材料不足可购买，相当于资源拥有量b发生了变化，设变化情况为

1????1??5??5???0?3???0???3? ?b???，则b'?b?B?1?b?????3????2?123????????????3????55??5?因为决策为扩大生产，即保持生产品种（基变量）不变，所以得到：

??5??0?3得到0???15 ?2?3???0?5因为利润z?3x1?x2?4x?3??3，可知z值随着λ增长而增长。当λ取最大值15时，5z值同时取的最大值。因此以购进15单位为宜。

5、 1.2.3三个城市每年需分别供应电力320，250，350个单位，由A、B两个电站提供，它们的最大可供电量分别为400，450个单位，单位费用如表所示。由于需求大于供给，决定城市1的供应量可减少0~30个单位，城市2的供应量不变，城市3的供应量不能少于270单位。试求总费用最低的分配方案。（将可供电量用完。）

1 城市 电站 A B 15 21 2 18 25 3 22 16

解：建立产销平衡的运输表，需要增设虚拟产地C，如表所示。 城市 电站 A B 虚拟电站C 需求量 1 11 15 21 M 290 12 15 21 0 30 18 25 M 250 2 31 22 16 M 270 3 32 22 16 0 80 400 450 70 产量 解题过程略。总运费14605.