(一)线性规划建模与求解
B.样题：活力公司准备在5小时内生产甲、乙两种产品。甲、乙两种产品每生产1
单位分别消耗2小时、1小时。又根据市场需求信息，乙产品的产量应该至少是甲产品产量的3倍。已知甲、乙两种产品每销售1单位的利润分别为3百元和1百元。请问：在5小时内，甲、乙两种产品各生产多少单位，才能够使得总销售利润最大？
要求：1、建立该问题的线性规划模型。
2、用图解法求出最优解和最大销售利润值，并写出解的判断依据。如果不存在最优解，也请说明理由。
解：1、(1)设定决策变量： 设甲、乙两种产品分别生产x 1、x 2单位 。
(2)目标函数： max z=2 x 1+x 2
(3)约束条件如下：1221
12
25..3,0+≤??≥??≥?x x s t x x x x
2、该问题中约束条件、目标函数、可行域和顶点见图1所示，其中可行域用阴影部分标记，不等式约束条件及变量约束要标出成立的方向，目标函数只须画出其中一条等值线，
结论：本题解的情形是： 无穷多最优解 ，理由： 目标函数等值线z=2 x 1+x 2与
约束条件2 x 1+x 2≤5的边界平行 。甲、乙两种产品的最优产量分别为 (5,0)或(1,3)单位；最大销售利润值等于 5 百元。
（二）图论问题的建模与求解样题
A.正考样题（最短路问题的建模与求解，清华运筹学教材编写组第三版267-268页例
13）某企业使用一台设备，每年年初，企业都要做出决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。但是变卖旧设备可以获得残值收入，连续使用1年、2年、3年、4年以上卖掉的设备残值分别为8万元、6万元、3万元和0万元。试制定一个5年的更新计划，使总支出最少。已知设备在各年的购买费与维修费如表2所示。要求：（1）建立某种图论模型；（2）求出最少总支出金额。
解：（1）建立图论——最短路问题模型。
①设点V i 表示第i 年年初，虚设一个点V 6，表示第五年年底；
②弧(V i , V j )表示第i 年初购进一台设备一直使用到第j 年初(即第i-1年年底)再卖掉并获得残值收入；
③弧(V i , V j )上的权数表示第i 年初购进一台设备，一直使用到第j 年初所需支付的购买、维修及抵扣残值收入以后的全部费用（单位：万元）。例如：弧(V 1, V 4)上的费用权数30=11+(5+6+8)-3=27(万元)。
模型如图2所示：
（2）用Dijkstra 法求解从V 1到V 6的最短路。 给起点V 1标号（0,v 1）；
1.I={v 1} ; J={v 2,v 3,v 4,v 5,v 6} 弧集合{[v 1,v 2]、[v 1,v 3] 、[v 1,v 4] 、[v 1,v 5] 、[v 1,v 6]} s 12=l 1+b 12=0+8=8;s 13=l 1+b 13=0+16=16;s 14=l 1+b 14=0+27=27; s 15=l 1+b 15=0+41=41;s 16=l 1+b 16=0+59=59
∵min{s 12,s 13,s 14,s 15,s 16}=min{8,16,27,41,59}=8= s 12=l 2 ∴给v 2标号（8,v 1） 2.I={v 1,v 2} J={ v 3,v 4,v 5,v 6}
弧集合{[v 1,v 3] 、[v 1,v 4] 、[v 1,v 5] 、[v 1,v 6] 、[ v 2,v 3]、[v 2,v 4]、[v 2,v 5]、[v 2,v 6]} s 23=l 2+b 23=8+8=16;s 24=l 2+b 24=8+16=24;s 25=l 2+b 25=8+27=35;s 26=l 2+b 26=8+41=49
∵min{s 13,s 14,s 15,s 16,s 23,s 24,s 25,s 26}=min{16,27,41,59,16,24,35,49}=16= s 13或s 23=l 3 ， ∴任选一个s 13，选择给v 3标号（16, v 1）。
3.I={v 1,v 2,v 3} J={v 4,v 5,v 6} 弧集合{[v 1,v 4]、[v 1,v 5] 、[v 1,v 6] 、[v 2,v 4]、[v 2,v 5] 、[v 2,v 6]、 [v 3,v 4]、[v 3,v 5] 、[v 3,v 6] }
s 34=l 3+b 34=16+9=25; s 35=l 3+b 35=16+27=35;s 26=l 2+b 26=8+41=49
∵min{s 14,s 15,s 16,s 24,s 25,s 26,s 34,s 35,s 36}=min{27,41,59,24,35,49,25,35,49}=24=s 24=l 4 ∴给v 4标号（24,v 2）
4.I={v 1,v 2,v 3,v 4} J={v 5,v 6} 弧集合{ [v 1,v 5] 、[v 1,v 6] 、[v 2,v 5] 、[v 2,v 6]、 [v 3,v 5] 、[v 3,v 6]、[v 4,v 5] 、[v 4,v 6 }
s 45=l 4+b 45=24+9=33; s 46=l 4+b 46=24+17=41
∵min{s 15,s 16,s 25,s 26,s 35,s 36,s 45,s 46}=min{41,59,35,49,35,49,33,41}=33=s 45=l 5 ∴给v 5标号（33,v 4）
5.I={v 1,v 2,v 3,v 4,v 5} J={v 6} 弧集合{ [v 1,v 6]、[v 2,v 6]、[v 3,v 6]、[v 4,v 6]、[v 5,v 6] }
s 56=l 5+b 56=33+10=43 ∵min{s 16,s 26,s 36,s 46,s 56}=min{59,49,49,41,43}=41=s 46=l 6 ∴给v 6标号（41,v 4）
表2
17
17
41 28 27 41 v 6 v 5 27
v 4 v 2 v 3 16
16 9
8 8 v 1 10 9
59
图2
6.I={Φ} J={Φ} 计算终止。
由终点v 6标号反向追踪，可得到v 1到v 6的最短路：v 1→v 2→v 4→v 6,长度为l 6=41,即5年内该设备的最小总支出金额为41万元。 B.考题复习知识点：
1.最短路问题求解的基本思想？请查阅课本或其他参考书籍，自行简答总结。
2.掌握用上述“Dijkstra 标号法”求解的步骤和处理方法，考试时书写格式请参照本样题。
3.掌握最短路确定的反向追踪方法和最短距离。考试题比此题计算量小。
4.掌握图论问题建模的程序，会说明图论模型各组分（弧或边、节点、权数）的实际涵义。
（三）动态规划——“复合系统工作可靠性问题”建模和求解）
A ．正考样题及其解答：某厂设计一种电子设备，由三种元件D 1、D 2、D 3组成。已
知这三种元件的单位价格、单位重量和可靠性如表4，要求在设计中所使用元件的费用不超过105元，重量不超过21克。问应如何设计使设备的可靠性达到最大。 解：（1）建立动态规划模型
①按元件的种类数划分阶段，k ＝1,2,3。每阶段阶段第k 种元件并联几个。
②状态变量x k 表示第k 阶段初尚未使用的费用；状态变量y k 表示第k 阶段初剩余的可增加重量。显然x 1=105,y 1=21,x k >0,y k >0 。
③决策变量u k 表示第k 阶段元件D k 并联的个数。允许决策集合：
c k 表示第k 种元件的单位费用；w k 表示第k 种元件的单位重量； ④状态转移方程：x k+1＝ x k -c k ·u k ； y k+1＝y k -w k ·u k 。
⑤阶段指标函数d k (u k )表示元件D k 正常工作的概率 ；最优指标函数f k (x k ,y k )
表示从元件D k 到元件D 3 正常运行的最大概率。 ⑥逆序解法的基本方程如下： （2）用逆序解法求解 ①第3阶段，k=3
②第2阶段，k=2 ③第1阶段，k=1
④由于x 1=105,y 1=21,故问题为求出f 1(105,21)即可。而
3
3
3
3
3
3
3
]]
??
??????
??
????????
∑∑k
k
k
k
j=k+1j=k+1
k
k
k
k
k
k
k
x -c y -w 1≤u ≤min([ ],[,k =1,2c w D (x , y )=u x y
1≤u ≤min([ ],[c w k u k k k d (u )=1-(1-p )[]111(,)444f (,)max ()(,) k=3,2,1(,)1
+++∈?=???=??k k k k k k k k k k k k u D x y x y d u f x y f x y []33333f (,)=max ()?? ??
?=x y d u 3333u x
y 1≤u ≤=min [ ],[]2051-(1-0.5)22223222222205f (,)max [](,)--??=?--??x y f x c u y w u 2
22u x y 1≤u ≤min([ ],[])
154
1-(1-0.8)11121111201554
f (,)max [](30,3)----??=?--??x y f x u y u 1111u x y 1≤u ≤min([ ],[])
303
1-(1-0.9)
∴
状态转移图如下：
结论：
求得u*1=1, u*2=2,u*3=2为最优方案，即D1、D2、D3三种元件分别并联1个、2 个和2个。总费用为100元，总重量为21克，可靠性为0.648。
B.正考复习知识点：
1.会按照样题解答那样分六步建立动态规划模型。文字说明方面：准确说明各种变量的实际涵义；数学表达方面：能正确、规范地写出逆序解法的基本方程，阶段变量必须逆着写取值，明确边界条件；在建模时对取值明确的状态变量应该说明其具体值；会以规范的集合语言写出允许决策集合的具体形式；具体写出状态转移方程函数形式；写出阶段指标函数的数学表达式。考试题目比此题的计算量要小，而且未必会考两个状态的情形。
2.比照样题中的解答步骤来书写答题过程，会绘制“状态转移图”并以此得出结论，会得出全过程最优指标函数值并给出依据。
3.清华大学教材编写组编写《运筹学》第三版237-238页例8计算过程可以参考（但f k(s k)中x k的范围有错，请按照课件第四章50-53张例
4.6.1来改正，答题格式也须参照后者。
（四）线性目标规划或运输问题的建模和求解
A.正考样题——非标准运输问题的建模与“表上作业法求解”
有三个发电站产地B1，B2，B3需要从两个煤矿A1，A2购买煤炭，各自的产量、需求量以及每万吨煤炭的运价（千元）如表5所示。问如何调运煤炭，使得总运输费用最小？
[]
1211
10520152154
22
2
f(105,21)max[](10530,213)
=max0.9(75,18),0.99(45,15)
----
??
=?--
??
f u u
f f
1
1
1
u
1≤u≤min([ ],[])
303
1≤u≤
1-(1-0.9)
[]
2322
7520185
333
f(75,18)max[](7515,184)
=max0.8(60,14),0.96(45,10),0.992(30,6)
--
??
=?--
??
f u u
f f f
2
2
2
u
1≤u≤min([ ],[])
154
1≤u≤3
1-(1-0.8)
[]
2322
4520155
33
1
36014
f(45,15)max[](4515,154)
=max0.8(30,11)0.8(30,11)
(60,14)max[]max(0.5,0.75)0.
--
=
??
=?--
??
=
===
f u u
f f
f
2
2
2
3
3
3
u
1≤u≤min([ ],[])
154
u
u
1≤u≤2
1≤u≤min([ ],[])
205
1-(1-0.8)
1-(1-0.5)75
34510
3306
33011
451005075075
3060505
301105
===
===
==
f
f
f
(,)max[]max(.,.).
(,)max[]max(.).
(,)max[]max(.)
3
3
3
3
3
3
3
3
3
u
1≤u≤2
1≤u≤min([ ],[])
205
u
u=1
1≤u≤min([ ],[])
205
u
u=1
1≤u≤min([ ],[])
205
1-(1-0.5)
1-(1-0.5)
1-(1-0.5)05
=.
23
f(45,15)0.8(30,11)0.80.50.4
==?=
f
[]
2
f(75,18)=max0.80.75,0.960.75,0.9920.50.72
???=
[]
1
f(105,21)=max0.90.72,0.990.40.648
??=
表5 产销平衡表和单位运价表
要求：（1）请建立该问题的线性规划模型，如果有必要再化为标准问题。（2）用表上作业法求解：用最小元素法确定初始方案；用闭回路法或者位势法验证初始方案是否最优？如果非最优，请用闭回路法调整，直至求出最优方案。 解：（1）设产地A i （i=1,2）调运到销地B j （j=1,2,3）的煤炭为x ij 万吨，可建立以下模型：
2
3
111213212223
1
111121321
2223112112221323min 2362231577216
2
3..150(1,2;1,2,3)
ij ij i j ij z c x x x x x x x x x x x x x x x s t x x x x x i j ===?=+++++++=??++=??+≤??
+≤??+≤?≥==??∑∑
（2）因为总产量8万吨（=6+2）小于总需求量9万吨（=3+1+5），所以本问题不是标准运输问题。增加一个虚拟产地A 3，它的单位运价c 31=c 32=c 33=0，产量为9-8=1（万吨）。
（3）第一步：用最小元素法确定初始方案（方案可能有以下三种，随着添加0位置不同而不同）。
(0)(1)(5)(2)(1)2362236(1)(0)1577212(0) 0 0 01(0) 3 1 5 (2) (0) (0) (0)
?????????? 01521??????????或15201??????????或15201??????????
方法二：伏格尔法（本题用此法求出的初始基可行解就是最优解）
(1)(0)(5)(2)(1)2362236[0](5)(0)
1577212[6](0) 0 0 01[0](0) 3 1 5 [15] [77] [21] [ 8] (0) [ 2] (1) [ -] [ -] ( 0)
(0)
?????????? 10521??
????????
第二步：求非基变量检验数，验证初始方案(最小元素法求得的第一种初始方案)是否最优。
法一：用位势法求检验数。
求解见表6 因为min(σ22,σ233233ij 32整，x 32为进基变量。
法二：用闭回路法求检验数
(0)(1)(5)(2)(1)236223157721 0 0
0??
??
?????
?
σ22=77-15+23-62=23;σ23=21-15+23-23=6;σ33=0-0+23-23=0； σ32=0-0+23-62=-39（注：图中画出了非基变量x 32的闭回路）；
因为min(σ22,σ23,σ32,σ33|σij <0)＝σ32=-39<0，，所以初始方案并非最优方案，需进一步调整，x 32为进基变量。
第三步：求θ值，调整初始方案。 过程如下：
0 1 521θθθθ
+--????????+?
?
以X 32作为进基变量。调整量θ＝min(1,1)=1，按照左图所示进行调
整，选择x 31作为出基变量。
方案调整后为方案二（注：另一个基可行解），如下：
10521??????????
22233133
决策结论：产地A 1向销地B 1调运煤炭1万吨，向销地B 3调运煤炭5万吨；产地A 2向销地B 1调运煤炭2万吨；销地B 2的需求量由虚拟产地A 3来满足，实际上它的需求量1万吨完全未得到满足。最小总运费=23×1+0×62+23×5+15×2+0×1=168（千元）。
B.正考复习知识点：
（1）本题是“销大于产”的非标准问题，但考试时也有可能考“产大于销”的非标准化问题。那么后一种情况该如何建模、标准化处理呢？请参看课件第一章“运输问题”的相应内容：96-98张。
（2）掌握运输问题求解的“表上作业法”（非标准问题标准化后才能求解）。确定初始方案请熟练掌握“最小元素法”即可，对“伏格尔法”不需要掌握；求方案的检验数请务必掌握“位势法”；对方案的优化改进，能找出进基变量的闭回路、确定θ值，并对方案加以优化调整。掌握变量检验数的经济含义（第三版84页最后两段）
（3）最优方案是唯一的，还是有多个呢？能给出判断依据，并且得出最优方案、最优目标函数值。
实验二线性规划的求解 学号：４1０1１ 姓名:何科 班级：201５级10班 一、实验目的 1.熟悉并掌握MATLAB的线性规划求解函数ｌinprｏg()及其用法； 2.熟悉并掌握LINGＯ软件求解线性规划的方法； 3.能运用LＩNGO软件对线性规划问题进行灵敏度分析。 二、实验任务 1.对例1和例2,在MAＴLAB进行求解。 2.对例３、４、5，在LIＮGO软件进行求解，并作灵敏度分析. 3.对“3．3 投资的收益与风险"的模型I，在MAＴLＡB中进行求解。 4.对“习题5,６，7,8”进行建模与求解。 三、实验过程与结果(对重要实验结果,截取全屏图，保存为JＰＧ／PＮＧ图 片） 1.例1: 代码： f=[13 9 10 11 12 8］; A=［0。４ 11 1 0 ００； 0 0 0 0.5 1。2 １。3]; b＝［800；９00］； Aeｑ＝［1 ００１０ 0; ０ 1 0 0 1 0; 0 ０１ 0 0 1]; bｅq=[４00；600;500］； vlb=ｚeｒos(６，1)； vub＝[］； [ｘ,fval］=ｌｉｎprog（f，Ａ,ｂ，Aｅq,ｂeq,vlｂ,vｕｂ） 结果： ｘ = ０.000０ 600.00０0 0。0000 400．０0０0 0．0000 5０0.0000 ｆｖal =1.３800e+０4 例2: 代码： c=［4０ 3６］； Ａ=[-5 —3］；
b=［-45]; Ａｅq＝[]; beｑ=［］; ｖlb=zeros(２，１）； vub＝［9;15]; ［ｘ，ｆｖａl]=ｌiｎprog（ｃ,A，b,Aeq，beq,ｖlb，vub) ?结果: ?x ＝ 9．00０0 0.0０００ fval = ３6０ 例３: ?代码： maｘ＝72*x1＋64＊ｘ2； x1+ｘ2＜＝５０; 1２＊x1+8＊ｘ2〈=48０; 3*ｘ１<＝100； ?结果： ?? Globａl oｐtimal solutｉｏn founｄ. Objective value：336０。000 Iｎｆｅaｓｉｂilｉties：０．0000０0 Ｔotal solver itｅｒａtions: 2 Ｖariａｂle Ｖaｌuｅ Rｅduｃeｄ Cost X1 2０。０00０0 0．00０0０0 Ｘ2 30.00０00 ０.0０00０0 ＲｏｗＳlack or Surplus DuaｌＰr ｉｃe 1 3360.00０ 1．00000０ 2 0.00０00０４8。00000 3 0。000０0０ 2。000０00 ４ 40.0０000 0.０0０000 ?灵敏度分析: ?
线性规划模型及其举例 摘要：在日常生活中，我们常常对一个问题有诸多解决办法，如何寻找最优方案，成为关键，本文提出了线性规划数学模型及其举例，在一定约束条件下寻求最优解的过程，目的是想说明线性规划模型在生产中的巨大应用。 关键词：资源规划；约束条件；优化模型；最优解 在工农业生产与经营过程中，人们总想用有限的资源投入，获得尽可能多的使用价值或经济利益。如：当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多，利润最大）。 一.背景介绍 如果产出量与投入量存在（或近似存在）比例关系，则可以写出投入产品的线性函数式： 1()n i ij j j f x a x ==∑，1,2,,,1i m m =+ (1) 若将（1）式中第（1m +）个线性方程作为待求的目标函数，其余m 个线性方程作为资源投入的限制条件（或约束条件），则（1）式变为： OPT. 1()n j j j f x c x ==∑ ST. 1 n ij j j a x =∑> ( =, < )i b , 1,2,,i m = (2) 0,j x ≥ 1,2,,j n =… （2）式特点是有n 个待求的变量j x （1,2,,j n =…）；有1个待求的线性目标函数()f x ，有m 个线性约束等式或不等式，其中i b （1,2,,i m =…）为有限的资源投入常量。将客观实际问题经过系统分析后，构建线性规划模型，有决策变量，目标函数和约束条件等构成。 1．决策变量（Decision Variable,DV ）在约束条件范围内变化且能影响（或限定）目标函数大小的变量。决策变量表示一种活动，变量的一组数据代表一个解决方案，通常这些变量取非负值。 2．约束条件（Subject To,ST ）在资源有限与竞争激烈的环境中进行有目的性的一切活动，都
线性规划建模及单纯形法 思考题 主要概念及内容： 线性规划模型结构（决策变量，约束不等式、等式，目标函数）；线性规划标准形式； 可行解、可行集（可行域、约束集），最优解；基、基变量、非基变量、基向量、非基 向量；基本解、基本可行解、可行基、最优基。 复习思考题： 1、线性规划问题的一般形式有何特征？ 2、建立一个实际问题的数学模型一般要几步？ 3、两个变量的线性规划问题的图解法的一般步骤是什么？ 4、求解线性规划问题时可能出现几种结果，哪种结果反映建模时有错误？ 5、什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 6、试述线性规划问题的可行解、基本解、基本可行解、最优解、最优基本解的概念及它 们之间的相互关系。 7、试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个 最优解、无界解或无可行解。 8、在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 9、大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什 么？最大化问题呢？ 10、什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情 况下，继续第二阶段？ 作业习题 1、将下列线性规划问题化为标准型 （1）???????≥=--+-≥-+-≤+-++-+=0,,953413223183622453max 4214321432143214321x x x x x x x x x x x x x x x x x x x z （2）???????≤≥=+-+-≥-+--≤--++++=0 ,0,15 2342722351232243min 4214321432143214 321x x x x x x x x x x x x x x x x x x x f 2、（1）求出下列不等式组所定义的多面体的所有基本解和基本可行解（极点）： ?????≥≤++-≤++0,,1243263323 21321321x x x x x x x x x （2）对下述线性规划问题找出所有基本解,指出哪些是基本可行解,并确定最优解. ??? ????≥=-=+-+=+++++=)6,,1(00 31024893631223max 61532143213 21K K j x x x x x x x x x x x x x x z j 3、用图解法求解下列线性规划问题
-1- 第一章线性规划 §1 线性规划 在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济 效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947 年G. B. Dantzig 提出 求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性 规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。 1.1 线性规划的实例与定义 例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000 元与3000 元。 生产甲机床需用A、B机器加工，加工时间分别为每台2 小时和1 小时；生产乙机床 需用A、B、C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时 数分别为A 机器10 小时、B 机器8 小时和C 机器7 小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？ 上述问题的数学模型：设该厂生产1 x 台甲机床和2 x 乙机床时总利润最大，则1 2 x , x 应满足 （目标函数）1 2 max z = 4x + 3x (1) s.t.（约束条件） ?? ? ?? ? ? ≥ ≤ + ≤ + ≤ , 0 7 8 2 10 1 2 2 1 2 1 2 x x x x x x x （2） 这里变量1 2 x , x 称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式是问题的约束条件，记为s.t.(即subject to)。由于上面的目标函数及约束条件均为线性
数学建模 第一章 线性规划 §1 线性规划 在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947年G. B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。 1.1 线性规划的实例与定义 例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用B A 、机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用C B A 、、三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A 机器10小时、B 机器8小时和C 机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？ 上述问题的数学模型：设该厂生产1x 台甲机床和2x 乙机床时总利润最大，则21,x x 应满足 （目标函数） 2134m ax x x z += (1) s.t. （ 约 束 条 件 ） ?????? ?≥≤≤+≤+0 ,781022122 121x x x x x x x （2） 这里变量21,x x 称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式是问题的约束条件，记为s.t.(即subject to)。
上述即为一规划问题数学模型的三个要素。由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。 总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。 在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往也是困难的一步，模型建立得是否恰当，直接影响到求解。而选取适当的决策变量，是我们建立有效模型的关键之一。 1.2 线性规划的Matlab 标准形式 线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便，Matlab 中规定线性规划的标准形式为 b Ax x c x T ≤ that such min 其中c 和x 为n 维列向量，b 为m 维列向量，A 为n m ?矩阵。 例如线性规划 b Ax x c x T ≥ that such max 的Matlab 标准型为 b Ax x c x T -≤-- that such min 1.3 线性规划问题的解的概念 一般线性规划问题的标准型为 ∑==n j j j x c z 1min (3) ∑==≤n j i j ij m i b x a 1,,2,1 s.t.Λ (4) 可行解 满足约束条件（4）的解),,,(21n x x x x Λ=，称为线性规划问题的可行解，而使目标函数（3）达到最小值的可行解叫最优解。
线性规划模型在实际生活中的应用 【摘要】线性规划在实际生活中扮演着很重要的角色，研究对象是计划管理工作中有关安排和估值的问题,其广泛应用于经济等领域，是实际生活中进行管理决策的最有效的方法之一。解决的主要问题是在给定条件下,按某一衡量指标来寻找安排的最优方案。本文通过对例题利用线性规划分析，如何合理的分配利用，最终找到最优解使企业利润最大，说明了线性规划在实际生活中的应用，而且对线性规划问题模型的建立，模型的解进行了分析，运用图解法和单纯形法解决问题。 【关键词】线性规划、建模、实际生活、图解法、单纯形法 前言：线性规划（Linear programming,简称LP）是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。 在实际生活中，经常会遇到一定的人力、物力、财力等资源条件下，如何精打细算巧安排，用最少的资源取得最大的效益的问题，而这正是线性规划研究的基本容，它在实际生活中有着非常广泛的应用．任何一个组织的管理者都必须对如何向不同的活动分配资源的问题做出决策，即如何有效地利用人力、物力完成更多的任务，或在预定的任务目标下如何耗用最少的人力、物力去实现目标。在许多情况下，大量不同的资源必须同时进行分配，需要这些资源的活动可以是不同的生产活动，营销活动，金融活动或者其他一些活动。随着计算技术的不断发展，使成千上万个约束条件和决策变量的线性规划问题能迅速地求解，更为线性规划在经济等各领域的广泛应用创造了极其有利的条件。线性规划已经成为现代化管理的一种重要的手段。本文运用常用的图解法和单纯形法解决利润最大化决策问题，贴近生活，很好的吧线性规划应用到生活实践中。 1、简单线性问题步骤简单介绍 建模是解决线性规划问题极为重要的环节，一个正确的数学模型的建立要求建模者熟悉线性规划的具体实际容，要明确目标函数和约束条件，通过表格的形式把问题中的已知
线性规划问题建模与求解 一．实验目的 1． 掌握线性规划问题建模基本方法。 2． 熟练应用Excel “规划求解”功能对线性规划问题进行建模与求解。 3．掌握线性规划问题的对偶理论和灵敏度分析。 二．实验设备 硬件：PC 机。 软件：Microsoft Excel 。 三．实验内容 1．建立线性规划问题的数学模型。 2．利用Excel “规划求解”功能对线性规划问题进行建模与求解。 3．根据实验优化结果，进行灵敏度及经济分析。 四．实验步骤 一．某厂准备生产A,B,C 三种产品，它们都消耗劳动力和材料，有关数据见表3。 表3 某厂生产利润与消耗资源表 A B C 拥有量 （单位） 劳动力 6 3 5 47 材料 3 4 5 30 单位产品利润（元） 3 1 4 问： ①如何确定产品的生产计划使该厂获利最大？ ②产品A 的利润在什么范围内变动时，上述最优计划不变？ ③如劳动力数量不变，材料不足时可从市场购买，每单位0.4元，问该厂要不要购进原材料扩大生产，购多少为宜？ ④生产产品B 的方案之一是降低成本，问产品B 的成本降低多少时，生产该产品才有利？ 要求：（1）建立该问题的数学模型 （2）利用EXCEL “规划求解”软件进行模型的求解，并产生分析报告。 （3）进行灵敏度与经济分析。 二 ：建立生产计划优化问题模型 解：设三种产品的生产量分别是X 1，X 2，X 3 产 品 资源
MaxZ=3X1+X2+4X3 6X1+X2+4X3≤47 3X1+4X2+5X3≤30 X1，X2，X3≥0 3．利用Excel “规划求解”功能建模与求解 （1）Excel “规划求解”的安装 1）启动Excel，打开“工具”菜单。如果没有“规划求解”，单击“加载宏”。 2）复选框中选中“规划求解”，单击“确定”后返回Excel。则在“工具”菜单中出现“规划求解”。 （2）线性规划模型的求解 1）启动Excel，输入线性规划模型的约束条件系数，右边常数项系数和目标变量系数。并定义线性规划的变量单元格、约束条件左边单元格和目标函数单元格 2)输入公式 E3 =SUMPRODUCT(B3:D3,B6:D6) E4=SUMPRODUCT(B4:D4,B6:D6) B7=SUMPRODUCT(B5:D5,B6:D6) 3）将光标停留在“总利润”单元格B7上，打开“工具”菜单中的“规划求解”，弹出下面
非线性规划模型 在上一次作业中，我们对线性规划模型进行了相应的介绍及优缺点，然而在 实际问题中并不是所有的问题都可以利用线性规划模型求解。实际问题中许多都 可以归结为一个非线性规划问题，即如果目标函数和约束条件中包含有非线性函数，则这样的问题称为非线性规划问题。一般来说，解决非线性的问题要比线性的问题难得多，不像线性规划有适用于一般情况的单纯形法。对于线性规划来说，其可行域一般是一个凸集，只要存在最优解，则其最优解一定在可行域的边界上达到；对于非线性规划，即使是存在最优解，却是可以在可行域的任一点达到，因此，对于非线性规划模型，迄今为止还没有一种适用于一般情况的求解方法，我们在本文中也只是介绍了几个比较常用的几个求解方法。 一、非线性规划的分类1无约束的非线性规划当问题没有约束条件时，即求多元函数 的极值问题，一般模型为 I r m i n f(X) X 一0 此类问题即为无约束的非线性规划问题 1.1无约束非线性规划的解法 1.1.1 一般迭代法 即为可行方向法。对于问题J mnf(X) [X X O 给出f (X)的极小点的初始值X(O),按某种规律计算出一系列的X(k)(k =1,2,…)， 希望点阵｛X (k)｝的极限X "就是f (X)的一个极小点。 由一个解向量X(k)求出另一个新的解向量X(kI) 向量是由方向和长度确定的，所以XZ I)=X k「k P k(k =12…) 即求解A和P k,选择'k和P k的原则是使目标函数在点阵上的值逐步减小，即 f (X0) 一f (X1) 一- f (X k) 一. 检验｛X(k)｝是否收敛与最优解，及对于给定的精度；7,是否IIlf(X k JlF ； 1.1.2 一维搜索法 当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有： (1)试探法(“成功一失败”，斐波那契法，0.618法等)； (2)插值法(抛物线插值法，三次插值法等)； (3)微积分中的求根法(切线法，二分法等)。考虑一维极小化问题 a?f(t) 若f (t)是[a,b]区间上的下单峰函数，我们介绍通过不断地缩短[a,b]的长度，来
第一章 线性规划 §1 线性规划 在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947年G. B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。 1.1 线性规划的实例与定义 例1某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用B A 、机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用C B A 、、三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A 机器10小时、B 机器8小时和C 机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？ 上述问题的数学模型：设该厂生产1x 台甲机床和2x 乙机床时总利润最大，则2 1,x x 应满足 （目标函数）2134m ax x x z += (1) s.t.（约束条件）???????≥≤≤+≤+0 ,781022122 121x x x x x x x （2） 这里变量21,x x 称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式 是问题的约束条件，记为s.t.(即subject to)。由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。 总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。 在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往也是困难的一步，模型建立得是否恰当，直接影响到求解。而选适当的决策变量，是我们建立有效模型的关键之一。 1.2 线性规划的Matlab 标准形式 线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便，Matlab 中规定线性规划的标准形式为 b Ax x c x T ≤ that such min beq x Aeq =? ub x lb ≤≤ 其中c 和x 为n 维列向量，A 、Aeq 为适当维数的矩阵，b 、beq 为适当维数的列向 量。 例如线性规划 b Ax x c x T ≥ that such max
(一)线性规划建模与求解 B.样题：活力公司准备在5小时内生产甲、乙两种产品。甲、乙两种产品每生产1 单位分别消耗2小时、1小时。又根据市场需求信息，乙产品的产量应该至少是甲产品产量的3倍。已知甲、乙两种产品每销售1单位的利润分别为3百元和1百元。请问：在5小时内，甲、乙两种产品各生产多少单位，才能够使得总销售利润最大？ 要求：1、建立该问题的线性规划模型。 2、用图解法求出最优解和最大销售利润值，并写出解的判断依据。如果不存在最优解，也请说明理由。 解：1、(1)设定决策变量： 设甲、乙两种产品分别生产x 1、x 2单位 。 (2)目标函数： max z=2 x 1+x 2 (3)约束条件如下：1221 12 25..3,0+≤??≥??≥?x x s t x x x x 2、该问题中约束条件、目标函数、可行域和顶点见图1所示，其中可行域用阴影部分标记，不等式约束条件及变量约束要标出成立的方向，目标函数只须画出其中一条等值线， 结论：本题解的情形是： 无穷多最优解 ，理由： 目标函数等值线z=2 x 1+x 2与 约束条件2 x 1+x 2≤5的边界平行 。甲、乙两种产品的最优产量分别为 (5,0)或(1,3)单位；最大销售利润值等于 5 百元。 （二）图论问题的建模与求解样题 A.正考样题（最短路问题的建模与求解，清华运筹学教材编写组第三版267-268页例 13）某企业使用一台设备，每年年初，企业都要做出决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。但是变卖旧设备可以获得残值收入，连续使用1年、2年、3年、4年以上卖掉的设备残值分别为8万元、6万元、3万元和0万元。试制定一个5年的更新计划，使总支出最少。已知设备在各年的购买费与维修费如表2所示。要求：（1）建立某种图论模型；（2）求出最少总支出金额。
线性规划建模求解 第一题某食品厂在第一车间用1单位原料N可加工3单位产品A及2单位产品B，产品A可以按单位售价8元出售，也可以在第二车间继续加工，单位生产费用要增加6元，加工后单位售价增加9元。产品B可以按单位售价7元出售，也可以在第三车间继续加工，单位生产费用要增加4元，加工后单位费用可增加6元。原料N的单位购入价为2元，上述生产费用不包括工资在内。3个车间每月最多有20万工时，每工时工资0.5元，每加工1单位N需1.5个工时，如A 继续加工,每单位需3工时，如B继续加工，每单位需2个工时。原料N每月最多能得到10万单位。问如何安排生产，使工厂获利最大。 第二题某公司计划在三年的计划期内，有四个建设项目可以投资：项目Ⅰ从第一年到第三年年初都可以投资。预计每年年初投资，年末可收回本利120% ，每年又可以重新将所获本利纳入投资计划；项目Ⅱ需要在第一年初投资，经过两年可收回本利150% ，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目Ⅲ需要在第二年年初投资，经过两年可收回本利160% ，但用于该项目的最大投资额不得超过15万元；项目Ⅳ需要在第三年年初投资，年末可收回本利140% ，但用于该项目的最大投资额不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？ 第三题某工厂生产Ⅰ、Ⅱ、Ⅲ、Ⅳ四种产品，产品Ⅰ需依次经过A、B两种机器加工，产品Ⅱ需依次经过A、C两种机器加工，产品Ⅲ需依次经过B、C两种机器加工，产品Ⅳ需依次经过A、B机器加工。有关数据如表所示，请为该厂制定一个最优生产计划。 第四题某石油公司有两个冶炼厂。甲厂每天可生产高级、中级和低级的石油分别为200，300和200桶，乙厂每天可生产高级、中级和低级的石油分别为100，200和100桶。公司需要这三种油的数量分别为14000，24000和14000桶。甲厂每天的运行费是5000元，乙厂是4000元。问：1）公司应安排这两个厂各生产多少天最经济？2）如甲厂的运行费是2000元，乙厂是5000元。公司应如何安排两个厂的生产。 第 五题某旅馆每日至少需要下列数量的服务员，有关数据如表所示。每班服务员从开始上班到下班连续工作八小时，为满足每班所需要的最少服务员数，这个旅馆至少需要多少服务员。
线性规划建模实验题 一、李四企业的生产经营规划问题 李四经营着一个小企业，这个企业最近出现了一些问题，资金周转出现困难。该企业一共生产经营着三种产品，当前有两种产品赔钱，一种产品赚钱。其中，第一种产品是每生产一件赔100元，第二种产品每生产一件赚300元，第三种产品每生产一件赔400元。 三种产品分别消耗（或附带产出）三种原料，其中第一种产品每生产一件附带产生100千克原料A，需要消耗100千克原料B和200千克原料C；第二种产品每生产一件需要消耗100千克原料A和100千克原料C，附带产生100千克原料B；第三种产品每生产一件需要消耗原料A、B、C各100千克。由于生产第一种产品的设备已经损坏，且企业也无能力筹集资金修复之，所以该企业现已无法组织生产第一种产品。 现在仓库里还存有A原料40000千克，后续货源供应难以得到保证；库存B原料20000千克，如果需要，后续容易从市场采购得到；库存C原料30000千克，如果需要，后续容易从市场采购得到。 李四想转行经营其他业务，但苦于仓库里还积压着90000千克原料，如果直接出售原料，则比生产后出售成品赔得更多。没有办法，李四只好向运筹学专家咨询，看看如何组织生产才能将损失降到最低。 请对李四企业的生产经营情况进行考查和分析，建立该问题的线性规划模型，并使用Excel软件和LINDO软件求解该问题（要求附带结果分析报告）。
二、王五管理的科研课题的经费使用规划问题 王五管理着一个科研课题，根据课题进展情况看，不久就要结题了。由于课题的管理采用经费与任务包干制，所以可以通过节约开支来预留课题完成后的产业推广经费。现王五需要制订出这样的一个方案：既按期完成科研任务，又要尽可能多地节省费用，人员的收入还不能减少。同时他还想知道这笔可节省的费用究竟是多少？ 课题组的费用构成有两个部分：一是人员经费开支，二是试验消耗与器材采购费用开支。其中，由于出台了增收节支激励政策，所以人员经费开支与原计划相比每月可节省1万元，试验消耗与器材采购费用开支每月可节省4万元。 该课题由两个子课题构成。其中第一个子课题的开支情况为：每月人员经费为1万元，每月试验与器材经费的开支为10万元；第二个子课题的开支情况为：人员经费计划为1万元，实际上该子课题每月可通过边研制边推广应用的方式获得净收入1万元，这样就可以保证每月正常的人员经费开支，所节余的1万元可向课题组上缴，同时该子课题的试验与器材经费开支需求是每月8万元。 第一个子课题的总经费还剩20万元，但如果申请，还可以增加；第二个子课题的经费还有40万元，但即使申请也不可能再增加。 课题组研究后一致决定采用如下原则进行决策： （1）所节余的人员经费用于奖励，不计入节省费用的总额当中。 （2）在保证圆满完成课题任务的前提下，最大限度地积累课题应用性推广经费。 请建立该问题的线性规划模型，帮助王五制订最合理的科研结题周期以及可节省的费用（要求使用Excel软件和LINDO软件求解该问题，并附带结果分析报告）。
1.（建模） Metalco 公司生产一种新的合金，新合金的成分为40%的锡、35%的锌和25%的 请建立数学模型确定各种合金的比例，以使新产品的生产成本最低。（财经社，数据模型与决策4.18，p137） 2.用单纯形法求解下列线性规划问题。（清华编写组，运筹学第三版，1.4，p45） （1）?????≥≤+≤++=0 ,24 261553.2max 2121212 1x x x x x x t s x x z （2） ???????≥≤+≤≤+=0 ,18231224 .52max 2121212 1x x x x x x t s x x z 3.（同上，2.9，p76）现有线性规划问题 ??? ??≥≤++≤++-++-=0,,) 2(9010412)1(20 3..1355max 3 21321321321x x x x x x x x x t s x x x z 先用单纯形法求出最优解，然后分析在下列条件下，最优解分别有什么变化？ （1） 约束条件（1）的右端常数由20变为30； （2） 约束条件（2）的右端常数由90变为70； （3） 目标函数中x3的系数由13变为8； （4） x1的系数列向量由???? ??-121变为??? ? ??50； （5） 增加一个约束条件（3）10010510321≤++x x x 4.（蓝伯雄，管理数学（下），2.11，p90）某厂生产甲、乙两种产品，需要A 、B 两种原料， （1） 请构造数学模型使该厂利润最大，病求解该问题。 （2） 原料A 、B 的影子价格为多少？ （3） 现有新产品丙，每件需消耗3千克原料A 和4千克原料B ，问该产品的销售价格至 少为多少时才值得生产？ （4） 工厂可在市场上买到原料A 。工厂是否应该购买该原料以扩大生产？在保持原问题
如何在Excel中建立并求解线性规划模型 刘桂莲 摘要：数学中线性规划问题的求解一直是很繁琐的，功能强大的Excel软件为我们提供了一种很好的求解方法，但这种方法却很少被人了解。本文就如何在Excel中建立并求解线性规划模型作了较详尽的论述。 关键词：线性规划数学模型电子表格模型规划求解Excel 线性规划是运筹学的一个分支，它的应用已愈来愈深入到社会生产和经济活动的各个领域。描述线性规划问题的抽象的数学式子是线性规划问题的数学模型。建立数学模型后，求解满足约束条件的目标函数的最优解是解决线性规划问题的关键。数学中常用的方法是图解法和单纯形法，而图解法只适用于两个变量的目标函数，单纯形法则计算量相当大，步骤烦琐，容易出错。在Excel中建立 电子表格模型，并利用它提供的“规划求解”工具，能轻松快捷地求解模型的解。 例如，某玻璃制品公司有三个工厂，公司目前决定停止不赢利产品的生产并撤出生产能力来生产两种新开发的产品：玻璃门和双把窗。估计三个工厂每周可用来生产新产品的时间分别为4小时、12小时、18小时，而每扇门需工厂1生产时间1个小时和工厂3生产时间3个小时，每扇窗需工厂2和工厂3生产时间各为2个小时，预测门的单位利润是300元，窗的单位利润是500元，问每周两种新产品数量的哪种组合能使总利润最大？ 问题的决策变量有两个：每周门的生产数量和窗的生产数量，目标是总利润最大，需满足的条件是：⑴三个工厂每周用于生产新产品的时间w每周可得时间 ⑵每周门、窗的生产数量均》0。设每周门的生产数量为X，窗的生产数量为y，则该问题的数学模型即为：最大化利润P =300x+500y,约束条件：xw4, 2y< 12，3x+2yw 18，x>0和y》0。 将上表的有关数据输入到Excel中，建立如图1所示的电子表格模型。被输入已知数据的单元格是数据单元格，如单元格C5：D8，G5：G7。决策变量(即两种产品每周的生产量)放在单元格C9和D9，正好定位在这些产品所在列的 数据单元格下面，这种含有需要做出决策的单元格是可变单元格。单元格E5： E7是用来计算各个工厂每周的总生产时间，如单元格E5就是用C5：D5和C9: D9的对应数值各自相乘再总加得到。Excel中有一个叫SUMPRODUCT的函数 能对相等行数和相等列数的两个变化范围的单元格中的值乘积后进行加和。被加 和的每个值是对第一个变化范围的一些值和对应位置的第二个变化范围的一些值的积。女口 E5=SUMPRODUCT(C5 : D5，C9：D9)是把C5：D5变化范围的每个值与C9 : D9变化范围中对应的每个值相乘，然后各个积相加。同样 E6=SUMPRODUCT(C6 : D6, C9：D9)，E7=SUMPRODUCT(C7 : D7, C9：D9)， E5、E6、E7这些单元格的数值是依赖于可变单元格的，它们是输出单元格。单元格F5、 F6、F7中的“W”符号表示它们左边的总值不允许超过列G中的对应
第二章 线性规划的对偶理论与灵敏度分析习题 1. 写出下列线性规划问题的对偶问题。 (1)????? ? ?≥=++≤++≥++++=无约束 3213213213213 21,0,5343 32243422min x x x x x x x x x x x x x x x z (2) ????? ? ?≤≥≤++≥-+-=++++=0 ,0,8374355 22365max 3213213213213 21x x x x x x x x x x x x x x x z 无约束 (3)?? ??? ??? ???==≥=====∑∑∑∑====) ,,1;,,1(0) ,,1(),,1(min 1 111n j m i x n j b x m i a x x c z ij m i j ij n j i ij m i ij n j ij (4)???????????=≥++==<=<=∑∑∑===),,,,1(0),,2,1() ,,1(min 1 211111n n j x m m m i b x a m m i b x a x c z j n j i j ij n j i j ij n j j j 无约束 2. 判断下列说法是否正确，为什么? (1)如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； (2)如果线性规划的对偶问题无可行解，则原问题也一定无可行解； ( 3)在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值； (4)任何线性规划问题具有唯一的对偶问题。 3. 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。
机械工程学院工业工程专业学号： 姓名：
线性规划问题建模与求解 一．实验目的 1．掌握线性规划问题建模基本方法。 2．熟练应用Excel“规划求解”功能对线性规划问题进行建模与求解。 3．掌握线性规划问题的对偶理论和灵敏度分析。 二．实验设备 硬件：PC机。 软件：Microsoft Excel。 三．实验内容 1．建立线性规划问题的数学模型。 2．利用Excel“规划求解”功能对线性规划问题进行建模与求解。 3．根据实验优化结果，进行灵敏度及经济分析。 四．实验步骤 某出版单位有4500个空闲的印刷机时和4000个空闲的装订工时，拟用于下列4种图书的印刷和装订。已知各种书每册所需的印刷和装订工时如表2所示。 表2 印刷和装订工时数据表 问： ①该出版单位为了实现利润最大化，如何安排4种图书的生产？ ②该单位是否愿意出50元的加班费，让工人加班1小时？ ③由于管理工作的进步，使得第1种产品成本每件下降0.2元，此时得最优生产方案是否有变化，总利润是多少？ ④出版第2种书的方案之一是降低成本，若第2种书的印刷加装订成本合计每册6元，则第2种书的成本为多少时，出版该书才有利？ 要求：（1）建立该问题的数学模型 （2）利用EXCEL“规划求解”软件进行模型的求解，并产生分析报告。 （3）进行灵敏度与经济分析。
2．建立生产计划优化问题模型 解：设四种图书馆的日产量分别为1x ，2x ，3x ，4x 。依题意，列出下面的线性规划模型 MaxZ=1 x +2 x +43x +34 x 0.11 x +0.32 x +0.83x +0.44 x <= 4500 0.21 x +0.12 x +0.13x +0.34 x <=6700 1x >=0 2 x >=0 3x >=0 4x >=0 定义“资源使用量”（即约束条件左边）的计算公式。 如定义印刷使用（即约束条件1左边）单元格F3，则输入公式为=SUMPRODUCT(B3:E3,B6:E6) 依此类推，定义装订F4和定义总利润SUMPRODUCT(B5:E5,B6:E6) ，
线性规划建模问题 1、招聘问题 新机电器始创于1989年，是高低压电器元件、成套装置附件、高压电控电器配套件的专业生产制造商，是国家的高、低压电器开关行业协会理事单位，在业内享有很高声誉。新机电器已发展成为拥有八家子公司，在永嘉、温州、厦门、青田、陕西均有设厂。 工种：普车车工、数控车工、装配工、检验员、计算机绘图员各1名。 要求：具有良好的工作心态，吃苦耐劳，虚心好学，积极进取，有团队协作精神以及良好的沟通能力。 面试须知： 岗位安排方案完成后，新机为前往厂内实习的人员，提供了往返车费，总共是46元。获悉该厂又分新、旧两个厂区，要求每区至少去一名同学，且去旧厂区面试的同学比新厂区至少多一名。 已知前往新厂区每位同学的往返车费是4元，该厂区为每人提供的考虑岗位数为5个；旧厂区每位同学的往返车费是6元，而为每人可供考虑的岗位数为3个。 建模分析： 分析：以两组为基本单位，共同出谋划策，怎样合理地安排分别前往新、旧两区的人数，并能使面试时可选择的空缺岗位数达到最多，这样每人实习录用的机会就增多。请问岗位最多是多少？ 假设： 问题解答： 解：设前往新、旧厂区的 人数分别为y x,，设岗位数 为z，则根据题意得， y x z3 5+ =，且 1,1 1 4646 x y y x x y ≥≥ ? ? ≥+ ? ?+≤ ? y=1
在坐标系中将各不等式区域表示如下： 我们发现当5 ,4= =y x时，不等式所夹的区域最大，因此，前往新、旧厂区的人数分别为4、5时，可供选择的岗位数最大，为35个。 2、已知高翔工业区内的新机厂区并不是真正的加工厂，实际上只完成装配工作，所需配件由青田与陕西两个厂区供应，而这两个厂生产出的零部件毛利价格不同。 拿“JN15-12-31.5型户内高压接地开关”为例，扭簧为其中的配件之一，而青田与陕西产的扭簧可获利润不同，毛利价格现列表如下： 要求：每日由青田与陕西厂区供应的货品总和需保持在500—1000件之间，而且青田厂区的产品数至少要比陕西的多100件，下面请你给出一项合理的方案，将货源如何进行调配，才能使我厂每日的毛利最多？最多为多少？方案的好坏，以及策划的速度快慢都直接影响到你在实习期间以及今后工作岗位的调动及职务与薪酬。 问题解决： 解：设每日青田与陕西厂区所提供的货品数分别为y x,，设每日扭簧的毛利为z元，则根 据题意得：y x z20 15+ =，且 0,0 5001000 100 x y x y x y ≥≥ ? ? ≤+≤ ? ?≥+ ? ，在坐标系中将各不等式的区域表示如
数学建模 （第 1 次作业）题目：线性规划
工厂生产 摘要： 某工厂用三种原材料，，c,p,h混合调配出三种不同规格的产品A,B,D。已知产品的规格要求，产品单价，每天能提供的原材料数量及原材料单价，分别见表1和表2.该厂应该如何安排，使得利润收入最大？ Table: 1.产品规格要求与单价表 假设一：每天没有原材料损耗 假设二:生产的产品都能卖出去 假设三：市场价格恒定（利润恒定） 假设四：工厂能有效完成工程任务量 正文：设产品A,B,D的每日产量分别为X1,X2,X3。其中A产品需要原材料为X11,X12，X13。产品B为X21,X22,X23。产品D为X31,X32,X33。厂家利润为Z元。 由上图所给表格1与表格2，给出利润表达式 Zmax=50X1+35X2+25X3-(X11+X21+X31)*65-(X12+X22+X32)*25-(X13+X2 3+X33)*35 由A,B,D,原材料生产要求给出限制条件 X11≥50%X1
X12≤25%X1 X21≥25%X2 X22≤50%X2 X11+X21+X31≤100 X12+X22+X32≤100 X13+X23+X33≤60 X1=X11+X12+X13 X2=X21+X22+X23 X3=X31+X32+X33 X1,X2,X3,X11,X12,X13,X21,X22,X23,X31,X32,X33≥0 由上述限制推出： -X11+1/2*X1≤0 X12-1/4*X1≤0 -X21+1/4*X2≤0 X22-1/2*X2≤0 X11+X21+X31≤100 X12+X22+X32≤100 X13+X23+X33≤60 X1-(X11+X12+X13)=0 X2-(X21+X22+X23)=0 X3-(X31+X32+X33)=O X1,X2,X3,X11,X12,X13,X21,X22,X23,X31,X32,X33≥0
实验课题： （一）线性规划问题 1.用lingo求解下列线性规划问题： 2. 某班男同学30人、女同学20人，植树。工作效率（个/人、天）如下表。如何安排，植树最多？ 3.某牧场饲养一批动物，平均每头动物至少需要 700g 蛋白质、30g 矿物质和100g 维生素。现有A、B、C、D、E五种饲料可供选用，每千克饲料的营养成分(单位：g)与价格(单位：元/kg)如下表所示： 试求能满足动物生长营养需求又最经济的选用饲料方案。 4.在以色列，为分享农业技术服务和协调农业生产，常常由几个农庄
组成一个公共农业社区。在本课题中的这个公共农业社区由三个农庄组成，我们称之为南方农庄联盟。 南方农庄联盟的全部种植计划都由技术协调办公室制订。当前，该办公室正在制订来年的农业生产计划。 南方农庄联盟的农业收成受到两种资源的制约。一是可灌溉土地的面积，二是灌溉用水量。这些数据由下表给出。 注：英亩-英尺是水容积单位，1英亩-英尺就是面积为1英亩，深度为1英尺的体积；1英亩-英尺≈1233.48立方米。 南方农庄联盟种植的作物是甜菜、棉花和高粱，这三种作物的纯利润及耗水量不同。农业管理部门根据本地区资源的具体情况，对本联盟农田种植规划制定的最高限额数据由下表给出。 三家农庄达成协议：各家农庄的播种面积与其可灌溉耕地面积之比相等；各家农庄种植何种作物并无限制。所以，技术协调办公室面对的任务是： 根据现有的条件，制定适当的种植计划帮助南方农庄联盟获得最大的
总利润，现请你替技术协调办公室完成这一决策。 对于技术协调办公室的上述安排，你觉得有何缺陷，请提出建议并制定新的种植计划。 5．有一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如下表所示： 前舱中舱后舱 最大允许载重量（t）2000 3000 1000 容积（m3）4000 5400 1000 现有三种货物待运，已知有关数据如下表所示： 商品数量（件）每件体积（m3/件）每件重量（t/件）运价（元/件） A 600 10 8 1000 B 1000 5 6 700 C 800 7 5 600 又为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系。具体要求前、后舱分别与中舱之间载重理比例上偏差不超过15%，前、后舱之间不超过10%。 问该货轮应装载A, B, C各多少件，其运费收入为最大？ 6.某战略轰炸机群奉命摧毁敌人军事目标。已知该目标有四个要害部位，只要摧毁其中之一即可达到目的。为完成此项任务的汽油消耗量限制为48000 升、重型炸弹48 枚、轻型炸弹32 枚。飞机携带重型炸弹时每升汽油可飞行2 千米，带轻型炸弹时每升汽油可飞行3 千米。又知每架飞机每次只能装载一枚炸弹，每出发轰炸一次除来回路程汽油消耗（空载时每升汽油可飞行4 千米）外，起飞和降落每次