《简单的规划模型(运筹学教材上的例子)》由会员分享，可在线阅读，更多相关《简单的规划模型(运筹学教材上的例子)（34页珍藏版）》请在金锄头文库上搜索。
1、数学模型 Mathematical Model,刘志兵Department of Mathematics Huanggang Normal University Hubei 438000, C,Welcome you to my class!,,例1：某工厂在计划期间内安排生产I、II 两种产品，已知生产单位产品 所需的设备台时（单位：台时/千克）及A、B两种原材料的消耗（单位：千克 /千克），如下表所示。该工厂每生产一千克产品I可获利2千元，每生产一千 克产品II可获利3千元，问应如何安排计划使该工厂获利最多？,第一章 线性规划,一、线性规划问题及其数学模型,,4x2 12,4x1 16,x
2、1，x2 0,x1+2x2 8,解：设x1、x2分别表示在计划期内产品I、II的产量（单位:千克），则建 立如下数学模型：,max z=2x1+3x2,,例2：靠近某河流有两个化工厂（见图1-1），流经第一化工厂的河流流量为每天500万M3，在两个工厂之间有一条流量为每天200万M3支流，第一化工厂每天排放含有某种有害物质的工业污水2万M3，第二化工厂每天排放这种工业污水1.4万M3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可自然净化，根据环保要求，河流中工业污水的含量应不大于0.2%。这两个工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是1000元/万M3，第二化
3、工厂处理工业污水的成本是800元万/M3，现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。,解：设x1、x2分别表示化工厂I、II的处理工业污水数量产量（单位: M3 ）， 则建立如下数学模型：,x1 2,0.8x1 +x2 1.6,x1，x2 0,x1 1,min z=1000x1+800x2,x2 1.4,,从以上两例可以看出，它们都是属于一类优化问题，它们的共同特征：,1、每一个问题都用一组决策变量（x1,x2,xn）表示某一方案；这组决 策变量的值就代表一个具体方案，一般这些变量取值是非负的。,2、存在一定的约束条件，这些约束条件可以用一
4、组线性等式或线性不 等式来表示。,3、都有一个要求达到的目标，它可用决策变量的线性函数（称为目标 函数）来表示，按问题的不同，要求目标函数实现最大化或最小化。,满足以上三个条件的数学模型称为线性规划的数学模型，其一般形式为：,目标函数 max(min) z=c1x1+ c2x2 cnxn (1.1)满足约束条件 a11x1+a12x2+a1nxn(、=)b1a21x1+a22x2+a2nxn(、=)b2am1x1+am2x2+amnxn(、=)bm (1.2)x1、x2xn0 (1.3)在线性规划的数学模型中，方程（1.1）称为目标函数；（1.2）、（1.3） 称为约束条件；（1.3）也称为变
5、量的非负条件。,二、线性规划问题的基本概念,线性规划问题的一般形式为：,可行解 ：满足约束条件、的解X,最优解 ：使目标函数达到最大值的可行解X,,现以Mathematica为例求解如下：,输出结果：,执行命令：,ConstrainedMax2 x1+3 x2,x1+2 x2=8,4 x1=16,4 x2 4, x2 - 2,线性规划的计算,线性规划问题的求解，如今可用Mathematica、Matlab、 Lingo等软件直接求解（算法为单纯形法），也可用Basic、C、 VB、VC等语言编制程序求解。,三、应用举例,实际问题中只要满足线性规划问题定义，就可建立线性规划模 型，一般步骤是先设
6、决策变量，再列约束条件和目标函数。,例3 合理利用线材问题：现要做100套钢架，每套钢架需用长 为2.9米、2.1米、1.5米的元钢各一根制成。已知原料长7.4米，问应 如何下料，使用的原材料最省。,解：原料裁成所需长度的钢管的裁剪方式有如下几种,2,0,1,7.3,0.1,1,2,0,7.1,0.3,可设每种裁剪方式裁剪根数分别为x1,x2,x3,x4,x5,x6,x7,x8，则可建 立模型：,x1+x3 +3x4+2x6+3x7+4x8 100,2x2+x3+3x5 +2x6+x7 100,x1,x2 ,x3 ,x4,x5 ,x6,x7 ,x80,2x1+x2+ x3 +x4 100,mi
7、n z = 0.1x1+0.3x2+0.9x3+0x4+1.1x5+0.2x6+0.8x7+1.4x8+ (2x1+x2+ x3 +x4 100)*2.9+(2x2+x3+3x5 +2x6+x7- 100)*2.1+(x1+x3 +3x4+2x6+3x7+4x8-100)*1.5,，并取整数,例4 配料问题：某工厂要用三种原材料C、P、H混合调配出三 种不同规格的产品A、B、D。已知产品的规格要求，产品单价，每 天供应的原材料数量及原材料单价，分别见下表。该厂应如何安排 生产，使利润收入为最大？,解：设每天生产的产品A中含C的量为AC，依次类推，则有：,原材料每天供应量限制：,产品规格要求限制
8、：,AP 25%(AC+AP+AH),AC 50%(AC+AP+AH),BC 25%(BC+BP+BH),BP 50%(BC+BP+BH),AC+BC+DC 100,AP+BP+DP 100,AH+BH+DH60,目标函数为：,max z =50(AC+AP+AH) +35(BC+BP+BH)+25(DC+DP+DH)-65(AC+BC+DC )-25(AP+BP+DP)-35(AH+BH+DH),综合可知：,,第二章 运输问题,一 、运输问题的数学模型,已知有 m 个产地 Ai，n 个销地 Bj，从 Ai 到 Bj 的单位运价为 cij,见表,若用 xij 表示从 Ai 到 Bj 的运量，则
9、在产销平衡的条件下，要求 得总运费最小的调运方案，可建立模型 如下：,,其中 X=(x11,x12,x1n,x21,x22,x2n,xm1,xm2,xmn)T， A=(Pij)(m+n) (mn)，Pij=ei+em+j，b=(a1,a2,am,b1,b2,bm)T， C=(c11,c12,c1n,c21,c22,c2n,cm1,cm2,cmn).,max z =CXAX=bX0,二、产销不平衡的运输问题及其求解方法,当ai bj时，,假想一个销地记为 Bn+1= ai - bj ，,销量记为bn+1= ai - bj ，,从产地 Ai 到销地 Bn+1的单位运价全部为 0 ，即ci,n+1
10、= 0，i=1,2,m.,例5 求解下述运输问题：,解：由于ai =20+50=70 bj =15+25+18=58，因此假想一销地B4，变为：,B4,12,0,0,当ai bj 时类似处理,例6 已知条件如下表所示，试求出总的运费最节省的化肥调拨方案。,解：对该问题做如下处理：,30,20,70,30,10,50,16,14,19,17,15,M,M,ai=160 bj=70,30,0,0,0,0,例8 已知条件如下表所示，又知每条船每次装卸货时间各需天，则 该航运公司至少应配备多少条船，才能满足所有航线的运货要求 。,解：该公司所需配备船只分为两部分：,(1) 载货航程需要的周转船只数：,
11、如第一条航线从 E 到 D，,航行过程中需配备船只数为 ：(17+2)3=57.,同理可得其它三条航线 这部分所需船只数分别为：,从B到C：(3+2)2=10，,从A到F：(7+2)1=9，,从D到B：(13+2)1=15，,共需57+10+9+15=91条.,,(2) 各港口间调度所需船只数：,统计各港口需求情况如下：,每天到达,每天需求,余缺数,3,2,1,1,0,0,3,2,1,1,0,0,-1,-1,2,2,-3,1,问题变为从C,D,F三港口运输空船到A,B,E三港口，要使其效率最 高，建立如下运输模型（表格表示）：,产地,销地,C,D,F,A,B,E,ai,2,2,1,bj,1,1
12、,3,2,3,5,14,13,17,7,8,3,再用表 上作业 法求解,该部分最少所需周转船只数为：40条；,故总共至少需要船只数为：91+40=131条.,,例9 某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表，问两种货物各托运多少箱，可使获得利润为最大？,一、整数规划问题的提出,第三章 线性整数规划,,解：设x1、x2分别为甲、乙两种货物的托运箱数，则建 立如下数学模型：,x1，x2 取整数,,二、基本概念,线性整数规划：变量取整数的线性规划。,线性纯整数规划：所有的变量都限制为(非负)整数的 线性整数规划。,线性混合整数规划：部分变量限制为(非负)整数
13、的线 性整数规划。,,引入 0-1 变量的实际问题,0 - 1 型整数规划是整数规划中的特殊情形，它的变量 仅取值 0 或 1 。此时该变量称为 0-1 变量，或称二进制变量。,1、投资场所的选定相互排斥的计划,三、 0-1型整数规划,,例10 某公司拟在市东、西、南三区建立门市部，拟议 中有7个位置（点）Ai (i=1,7)可供选择。规定：在东区，由A1,A2,A3三个点中至多选两个；在西区，由A4,A5两个点中至少选一个；在南区，由A6,A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估 计为ci元，但投资总额不能超过B元。问应选择哪几个点可 使年利润为最大？,解：设,,,2、相互排斥的约束条件,对这种二选一的问题，可以通过引入0-1变量把它们 统一在一个问题中。,,其中 M 为充分大的正数,
