数学实验第三版（主编：李继成赵小艳）课后练习答案（九）（1）（2）

实验九：线性函数极值求解

练习一

1.求解线性规划问题：

（1）max z=3+,s.t.

clc;clear;
%采用软件解法
c=[-3,-1];
a=[-1,1;1,-2;3,2];
b=[2;2;14];
[x,min]=linprog(c,a,b)

找到最优解。

x =

min =

-13

题上要求的是最大值，则当x=4,1，时，有最大值13；

(2)min

clc;clear;
%采用软件解法
c=[3,1,-1];
a=[-1,-1,2;-1,2,-1];
b=[-2,-2];
aeq=[3,2,-1];
beq=[14];
l=[0;0;0];
u=[];
[x,min]=linprog(c,a,b,aeq,beq,l,u)

找到最优解。

x =

min =

2.某车间有甲、乙、丙三台车床可用于加工三种零件,这三台车床可用于工作的最多时间分别为700h,800h和900h,需要加工的三种零件的数量分别为300,400和500.不同车床加工不同的零件所用时间和费用如表9.2所示,在完成任务的前提下,如何分配加工任务,才能使加工费最少?

表9.2 工时数分配表

车床名称	加工单位零件所需时数			加工单位零件所需费用			可用于工作的时数
车床名称	零件1	零件2	零件3	零件1	零件2	零件3	可用于工作的时数
甲	0.6	0.5	0.5	7	8	8	700
乙	0.4	0.7	0.5	8	7	8	800
丙	0.8	0.6	0.6	7	9	8	900

clc;clear;
%采用软件解法
c=[7,8,8,8,7,8,7,9,8];
a=[0.6,0.5,0.5,zeros(1,6);
    zeros(1,3),0.4,0.7,0.5,zeros(1,3);
    zeros(1,6),0.8,0.6,0.6];
b=[700;800;900];
aeq=[1,0,0,1,0,0,1,0,0;
   0,1,0,0,1,0,0,1,0;
   0,0,1,0,0,1,0,0,1];
beq=[300;400;500];
l=[0;0;0;0;0;0;0;0;0];
u=[];
[x,min]=linprog(c,a,b,aeq,beq,l,u)

找到最优解。

x =

400

500

300

min =

8900

所以，让乙生产400件零件2和500件零件3，让丙生产300件零件1，这样分配加工费最少。

3.某工厂利用甲、乙两种原料生产A1, A2，A3三种产品,每月可供应的原料数量(单位:t)、每万件产品所需各种原料的数量及每万件产品的价格如表9.3所示:

表9.3 原料价格表

原料	每万件产品所需原料/t			每月原料可供应量/t
原料	A1	A2	A3	每月原料可供应量/t
甲	4	3	1	180
乙	2	6	3	200
价格/(万元·)	12	5	4

应如何制订每月的最优生产计划,使得总收益最大?

我们设甲造, ，为x1，x2,x3,乙造为x4,x5,x6;

clc;clear;
%采用软件解法
c=-[12,5,4,12,5,4];
a=[4,3,1,zeros(1,3);
    zeros(1,3),2,6,3];
b=[180;200];
aeq=[];
beq=[];
l=[zeros(1,6)];
u=[];
[x,min]=linprog(c,a,b,aeq,beq,l,u)

找到最优解。

x =

180

100

min =

-1920

则甲生产180万件，乙生产100万件时收益最大，收益为1920万元。

4.某棉纺厂的原棉需从仓库运送到各车间,各车间原棉需求量、单位产品从各仓库运往各车间运输费以及各仓库的库存容量如表9.4所列,问如何安排运输任务使得总运费最小?

表9.4 需求量、运输费和库存容量情况表

运输费		车间			仓库容量
运输费		1	2	3	仓库容量
仓库	1	2	1	3	50
	2	2	2	4	30
	3	3	4	2	10
需求量		40	15	35

我们设1仓库往1车间运x1,往二车间运x2,以此类推……

clc;clear;
%采用软件解法
c=[2,1,3,2,2,4,3,4,2];
a=[];
b=[];m=zeros(1,3);
aeq=[1,0,0,1,0,0,1,0,0;
     0,1,0,0,1,0,0,1,0;
      0,0,1,0,0,1,0,0,1;
      1,1,1,m,m;
      m,1,1,1,m;
      m,m,1,1,1];
beq=[40,15,35,50,30,10];
l=[zeros(1,9)];
u=[];
[x,min]=linprog(c,a,b,aeq,beq,l,u)

找到最优解。

x =

min =

190

当x取以上值时，运费最少，为190。

练习二

1.某单位有300万元可用于投资,共有6个项目可供选择,其投资额(单位:万元)分别为40,6080,50,90,70,预计三年后可获利润(单位:万元)分别为10,12,15,11,16,13,试确定一种投资方案可使得三年后获得的利润最大.

clc;clear;
%采用软件解法，0-1规划问题
c=-[10,12,15,11,16,13];
a=[];
b=[];
aeq=[40,60,80,50,90,70];
beq=[300];
l=[zeros(1,6)];
u=[ones(1,6)];
z=1:6;
[x,min]=intlinprog(c,z,a,b,aeq,beq,l,u);
x,z=-min

x =

选择投资一、二、三、四、六这几个项目三年后获得的利润最大，可获得61万元。

2.某校学生在大学三年级第一学期必须要选修的课程(必修课)只有一门(2个学分);可供限定选修的课程有8门,任意选修课程有10门.由于一些课程之间互有联系,所以可能在选修某门课程时必须同时选修其他课程,这18门课程的学分数和要求同时选修课程的相应信息如表9.8所示。

表9,8 课程信息表

限定选修课	课号	1	2	3	4	5	6	7	8
	学分	5	5	4	4	3	3	3	2
	选课要求					1		2
任意选修课	课号	9	10	11	12	13	14	15	16	17	18
	学分	3	3	3	2	2	2	1	1	1	1
	选课要求	8	6	4	5	7	6

按学校规定,每个学生每学期选修的总学分不能少于21学分,因此,学生必须在上述18门课程中至少选修19学分,学校同时还规定学生每学期选修任意选修课的学分不能少于3学分,也不能超过6学分,为了达到学校的要求,试为该学生确定一种选课方案.

clc;clear;
c=[5,5,4,4,8,3,8,2,5,6,7,5,5,5,1,1,1,1];
a=[-c;zeros(1,8),5,6,7,5,5,5,1,1,1,1;zeros(1,8),-5,-6,-7,-5,-5,-5,-1,-1,-1,-1];
b=[-19;6;-3];
aeq=[];beq=[];
u=[ones(18,1)];
l=[zeros(18,1)];
z=1:18;
[x,min]=intlinprog(c,z,a,b,aeq,beq,l,u)

LP: Optimal objective value is 19.000000.

Heuristics: Found 1 solution using ZI round.

Upper bound is 21.000000.

Relative gap is 9.09%.

Cut Generation: Applied 1 cover cut.

Lower bound is 19.000000.

Relative gap is 9.09%.

Heuristics: Found 1 solution using total rounding.

Upper bound is 19.000000.

Relative gap is 0.00%.

找到最优解。

Intlinprog 在根节点处停止，因为目标值在最优值的间隙容差范围内，options.AbsoluteGapTolerance = 0。intcon 变量是

容差范围内的整数，options.IntegerTolerance = 1e-05。

x =

min =

由此我们可以得知，选择1,2,3,8,15,16,18课程即可，而且此时刚好达到要求19学分。

3.比较示例8中的两种方法,为什么会产生两种不同的结果?你对此两种算法有何认识?考虑怎样改进贪婪算法,既能提高运算速度,又保证一定能够找到最优解?

两种算法结果不一样的原因很简单：第一种是正确答案，第二种是利用价值密度去求最大值

而在实际情形中，物品是不能装一半或三分之一之类的，只能整个装下或不装，这样我们用第二种方法求得的结果只是在最佳答案附近，并不能保证一定是最佳答案。

认识：第一种算法虽然笨拙但有效，如果不考虑时间问题，我们保证一定可以寻到最优解，而且适用于任何问题。第二种算法针对本题是“弄巧成拙”，其适用范围仅仅在可割裂的物品上，如：水，小米，沙子，水泥等等。

改进：至于如何改进贪婪算法，不同的题目我们会有不同的解决办法。就针对本题而言，我们其实可以加上一些欠缺的考虑，如：找出能够最大限度的利用空间的选择组合，与贪婪算法的结果进行比较然后综合得出最佳答案。（我感觉贪婪算法的改进其实就是加上了一部分枚举法，然后让答案相对比较完善。当你全部选择了枚举法之后，这个算法就优化到了%100，但是时间的消耗就变大了，所以改进其实就是在两者之间做出一个平衡的选择，仅个人见解）

4.某医院每日至少需要护士值班人数如表9.9所示,

表9.9 值班护士的人数

班次	时间段	人数	班次	时间段	人数
1	6:00-10:00	60	4	18:00-22:00	50
2	10：00-14:00	70	5	22:00-2:00	20
3	14:00-18:00	60	6	2:00-6:00	30

每班的护士在值班开始时向病房报到,连续工作8h,医院至少需要多少护士才能满足值班要求?

clc;clear;
c=[ones(1,6)];
a=-[1,0,0,0,0,1
    1,1,0,0,0,0
    0,1,1,0,0,0
    0,0,1,1,0,0
    0,0,0,1,1,0
    0,0,0,0,1,1];
b=-[60,70,60,50,20,30];
aeq=[];beq=[];
u=[];
l=[zeros(6,1)];
z=1:6;
[x,min]=intlinprog(c,z,a,b,aeq,beq,l,u)

x =

min =

150

医院至少需要150名护士才能满足值班需求。

5.某厂要求每日8小时的产量不低于1800件,为了便于进行质量控制,计划聘请两种不同水平的检验员,一级检验员的标准为25件/h,正确率98%,计时工资40元/h;二级检验员的标准为15件h,正确率95%,计时工资30元/h;检验员每检错一次,工厂要损失20元.为使总检验费用最省,该工厂应聘一级、二级检验员各几名?

clc;clear;
c=[400,360];
a=-[200,120];
b=[-1800];
aeq=[];beq=[];
u=[9;15];
l=[zeros(2,1)];
z=1:2;
[x,min]=intlinprog(c,z,a,b,aeq,beq,l,u)

则需聘请九名一级检验人员。

6.某校篮球队拟从以下6名预备队员中选拔3名作为正式队员,并使队员平均身高尽可能高,这6名预备队员情况如表9.10所示

表9.10 预备队员情况

号码	预备队员	身高/cm	位置
1	小张	193	中锋
2	小李	191	中锋
3	小王	187	前锋
4	小赵	186	前锋
5	小田	180	后卫
6	小周	185	后卫

队员的挑选要满足:(1)至少补充一名后卫队员;(2)小李或小田中间只能入选一名;(3)最多补充一名中锋;(4)如果小李或小赵入选,小周就不能人选,问应如何挑选队员?

clc;clear;
c=-1/3*[193,191,187,186,180,185];
a=[1,1,0,0,0,0
    0,0,0,0,-1,-1
    0,1,0,0,1,0
    0,1,0,1,0,1];
b=[1;-1;1;2];
aeq=[ones(1,6)];
beq=[3];
u=[ones(6,1)];
l=[zeros(6,1)];
z=1:6;
[x,min]=intlinprog(c,z,a,b,aeq,beq,l,u)

x =

min =

-188.3333

选择小张、小王、小周即可。

推荐下一篇文章：

数学实验第三版（主编：李继成赵小艳）课后练习答案（九）（3）https://blog.csdn.net/2301_80199493/article/details/136113244?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22136113244%22%2C%22source%22%3A%222301_80199493%22%7D