补充线性规划问题练习题解答

补充线性规划问题习题及解答

1．某铜厂轧制的薄铜板每卷宽度为100cm，现在要在宽度上进行切割以完成下列订货任务：24cm宽的75卷，40cm宽的50卷和32cm宽的110卷，长度是一样的，试将这个要解决的切割方案问题列成线性规划模型，使切余的边料最少。 答：有下面八种切法

设x1，x2，x3，x4，x5，x6 ，x7，x8分别表示八种下料方案切割的铜卷数，求解x1，x2，x3，x4，x5，x6，x7，x8使满足条件：

x4 x5 2x6 2x7 75 4x1

2x x4 x6x8 50 2 3x x 2x x x 11034578 x1，x2，x3，x4，x5，x6, x7, x8 0取整数

并使余料总数：

Z= 4x1+20x2+4x3+4x4+12x5+12x6 +20x7 +28x8 取得最小值。 近似最优解x1=25/4,x3=20,x4=50 其他为0，最优值z*=305。（不是整数解）

2．某养鸡场养鸡10000只，用大豆和谷物饲料混合喂养，每天每只平均吃混合饲料0.5kg，其中应至少含有0.1kg蛋白质和0.002kg钙。已知大豆中含50%蛋白质和0.5%的钙，价格是1.00元/kg，谷物中含有10%的蛋白质和0.4%的钙，价格是0.30元/kg，粮食部门每周只保证供应谷物饲料25000kg，大豆供应量不限，问应如何搭配两种饲料，才能使喂养成本最低，建立该问题的数学模型。

解：设每周用大豆x1公斤，谷物x2公斤,数学模型为

≥0.1×7×10000=7000 蛋白质

50%x1 +10%x2

0.5%x1+0.4%x2≥0.002×7×10000=140 钙 x1 +x2≤0.5×7×10000=35000 总量 x2≤25000 谷物限量 x1≥0,x2≥0 min z=x1+0.3x2

图解最优解x1=9333.33 , x2=23333.33,最小值z*=16333.33。 3．一家昼夜服务的饭店，24小时内需要服务员的人数如下

每个服务员每天连续工作8小时，且在表中时段开始上班，试求要求满足以上要求的最少上班人数，建立该问题的数学模型。

解：设在j钟点上班的人数为xj(j=1,2,…,6)，上班之后连续工作8小时，下班离开，每班中间不允许交接班离开。故有

据题意有

2~6时 x1 +x6 ≥4 6~10时 x1+x2+ ≥8 10~14时 x2+x3 ≥10 14~18时 x3+x4 ≥7 18~22时 x4+x5 ≥12 22~2时 x5+x6 ≥4 min z=x1+x2+x3+x4+x5+x6

最优解x1=4 , x2=10 , x4=8 , x5=4 , 其他xj=0, 最优值min z=26（人） 4．设有四个投资机会：

甲：在三年内，投资人应在每年年初投资，每年每元可获利息0.2元，每年取息后可重新将本息投入生息。

乙：在三年内，投资人应在第一年年初投资，每两年每元可获得利息0.5元，两年后取息，可重新将本息投入生息。

丙：在三年内，投资人应在第二年年初投资，两年后每元可获得利息0.6元，这种投资最多不得超过15000元。

丁：投资人应在第三年年初投资，一年内每元投资可获利息0.4元，这种投资不得超过10000元。

假定在这三年为期的投资中，开始时有30000元可供投资，投资人应怎样决定投资，才能在第三年底获得最高的收益，试建立其数学模型。 解：设xij为第i年初投放到j项目的资金数，其数学模型为：

max z=1.2x31+1.6x23+1.4x34 x11+x12≤30000 x21+x23≤1.2x11 x31+x34≤1.2x21+1.5x12 x23≤15000 x34≤10000

xij≥

0 ,(i=1,2,3 ,j=1,2,3,4)

最优解x11=12500, x12=17500, x23=15000, x31=16250, x34=10000,其他为0；最优值z*=57500

5．某一求目标函数最大值的线性规划问题，用单纯形法求解时得到的某一步的单纯形表如下：

问a1，a2，a3，c，d各为何值及变量xj属于那一类性质的变量时： （1）现有解为唯一最优解。

（2）现有解为最优，但最优解有无穷多个。 （3）存在可行解，但目标函数无界。 （4）此问题无可行解。 答：

1.c＜0, d≥0, x3, x4 ,x5都不是人工变量；

2.c=0, d≥0 , a1，a2至少一个大于零，x3,x4,x5都不是人工变量； 3.c＞0 , d ≥0 , a1≤0，a2≤0，x3,x4,x5都不是人工变量； 4.c≤0 , d＞0 且x3,x4,x5 至少一个是人工变量。

6. 某线性规划问题的初始单纯形表及迭代后的表格如下：

求a，b， ，k，l各个值。

答：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

7. 写出下列线性规划问题的对偶问题：

min

Z 3x1 2x2 3x3 4x4 x1 2x2 3x3 3x4 3

x2 3x3 4x4 5

2x1 3x2 7x3 4x4 2 x1 0,x2,x3无约束，x4 0

maxw 3y1 5y2 2y3 2y3 3 y1

2y1 y2 3y3 2

3y1 3y2 7y3 3 3y 4y 4y 4

23

1 y1 0,y2 0,y3无约束

（1）

s.t.

答:

min

Z cijxij

i 1j 1n

mn

（2）

s.t.

i 1xij ai i 1,2, ,m j 1 答: ui vj cijm

xij bj j 1,2, ,n

i 1 ui,vj不限制

xij 0 i 1,2, ,m;j 1,2, ,n (i 1，2，...，m；j

maxw aiui bjvj

j 1

mn

1，2，...，n)

8．用对偶单纯形法求解下列线性规划问题:

min

Z x1 x2 2x1 x2 4

x 7x 7 12 x,x 0 12

（1）

s.t.

解:化成标准形式，列对偶单纯形表

采用对偶单纯形迭代规则得最优表： 最优解X=(21/13,10/13,0,0) ,最优值minZ= 31/13(maxZ’=-31/13) 。

min

Z 4x1 12x2 18x3 x1 3x3 3

2x2 2x3 5 x,x,x 0 123

（2）

s.t.

解: 化成标准形式，列对偶单纯形表

最优解X=(0,3/2,1,0,0) ,

最优值minZ=36(maxZ’=0-(3/2)×12-1×18=-36) 。 9．设 min Z 3x 5x x 2x 4x

12345

s.t.

x1 x2 x3 3x4 x5 6

x1 x2 2x3 x4 x5 3 x,x,x,x,x 0 12345

（1）写出其对偶问题。 （2）求解对偶问题。

（3）从对偶解中求出原问题的解。 答：（1）对偶模型

maxw 6y1 3y2

y1 y2 3 y y 5

12

y1 2y2 1

s.t.

3y1 y2 2

y1 y2 4

y1 0,y2 0

*

（2）求解对偶问题，图解法。得Y=(-3,1) ,w=-15 。

（3）利用互补松弛性求原问题解，由y1,y2异于0，知原约束均为等式；又由对偶约束1，2，4式为严格不等式，故可得x1,x2,x4等于0。代入原约束方程组，解得x3=3，x5=3, 即X=(0,0,3,0,3),最优值z=-1×3-4×3=-15=w。

10．从下面最优单纯形表中（最大化问题，约束条件均为“ ”连接）

（1）写出原问题与对偶问题的最优解。 （2）求

Z Z， b1 x6

-5

*

*

*

T

，并解释这两个数值的含义。

5

2

（3）如果以代价增添第一种资源一个单位，是否值得？ （4）若有人原向你购买第三种资源，应要价多少才合算？

（5）是否有其它最优解，如果没有，说明为什么？如果有，则求出另

一个最优解。

解：(1)原问题最优解X*=(2,0,3/2,0,1,0)T ,对偶问题最优解Y*=(4,0,9,0,0,0)。

(2)在最优表上可以得到最优基的逆B,

-1

-1

201 1

B 104

116

根据最优表上Pj’=BPj ,可解得Pj=BPj’,从而得A,

A 100

010 …… 此处隐藏：8229字，全部文档内容请下载后查看。喜欢就下载吧 ……