数学建模-整数规划课件.ppt

1、2022-12-25数学建模*2022-12-25第三部分 整数规划应用实例分析整数规划问题的几种求解方法分枝界定法隐枚举法匈牙利法蒙特卡洛法实验准备*例例1 整数规划问整数规划问题题 某厂拟购进甲、乙两类机床生产新产品。已知甲、乙机床某厂拟购进甲、乙两类机床生产新产品。已知甲、乙机床进价分别为进价分别为2万元和万元和3万元；安装占地面积分别为万元；安装占地面积分别为4m2和和2m2；投后的收益分别为投后的收益分别为300元元/日和日和200元元/日。厂方目前仅有资金日。厂方目前仅有资金14万元，安装面积万元，安装面积18m2。为使收益最大，厂方应购进甲、乙机床各多少台？为使收益最大，厂方应购

2、进甲、乙机床各多少台？实例一 整数规划问题甲型乙型现有量进价（万元）2315占地面积（m2）4218利润（百元）32*设设应购进甲、乙机床台数分别为x1和x2，工厂的收益为z。2123xxzMax143221xx182421xx0,21xx整数整数规划规划(IP)1.模型建立为整数,21xxs.t.实例一 整数规划问题*format short c=-3;-2;a=2,3;4,2;b=14;18;lb=0;0;x,Fval=linprog(c,a,b,lb)先不考虑解的整数限制，问题B的最优解：x1=3.25，x2=2.5，最优值：z=14.75。2.模型求解设整数规划问题为A，与它相应的线性

3、规划为问题B，先来求解问题B。1）舍去小数：取x1=3，x2=2，算出目标函数值z=13。2）试探：如取x1=4，x2=1时，z=14，如取x1=3，x2=3时，不满足约束条件，通过比较得到模型的最优整数解。解法一：实例一 整数规划问题*1）不考虑解的整数限制，问题B的最优解：x1=3.25，x2=2.5，最优值：z=14.752.模型求解解法二：设整数规划问题为A，与它相应的线性规划为问题B实例一 整数规划问题*2.模型求解 因为2与3之间无整数，故这两个子集的整数解必与原可行集合整数解一致，这一步骤称为分枝。对问题A分枝构成两个子问题称为B1和B2。问题B1数学模型：2123xxzMax1

4、43221xx182421xx0,21xx）分枝约束(31xs.t.问题B2数学模型：2123xxzMax143221xx182421xx0,21xx）分枝约束(41xs.t.实例一 整数规划问题*2.模型求解B2最优解：x1=4，x2=1，z2=14B1最优解：x1=3，x2=8/3，z1=43/3图解法（单纯形法）求得的最优解分别为：实例一 整数规划问题*4）对问题B1在进行分枝，得问题B11和B122.模型求解问题B11数学模型：2123xxzMax143221xx182421xx0,21xx31xs.t.问题B12数学模型：2123xxzMax143221xx182421xx0,21x

5、xs.t.）分枝约束(22x31x）分枝约束(32x实例一 整数规划问题*求解问题B11和B12 得到：2.模型求解5）此时由于所有子问题的目标值均小于或等于z2，故问题A的目标函数最优值z*=z2=14，最优解为x1=4，x2=1。B11最优解：x1=3，x2=2，z11=13B12最优解：x1=2.5，x2=3，z12=13.5实例一 整数规划问题*2022-12-25整数规划整数规划（Integer Programming）数学规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。整数规划分类：（1）变量全限制为整数时，称纯（完全）

6、整数规划。（2）变量部分限制为整数的，称混合整数规划。*2022-12-25整数规划整数规划特点（i）原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。整数规划无可行解。有可行解（当然就存在最优解），但最优解值变差。（ii）整数规划最优解不能按照实数最优解简单取整而获得。*2022-12-25整数规划整数规划求解方法分类（1）分枝定界法可求纯或混合整数线性规划。（2）割平面法可求纯或混合整数线性规划。（3）隐枚举法求解“0-1”整数规划：过滤隐枚举法；分枝隐枚举法。（4）匈牙利法解决指派问题（特殊“0-1”规划）

7、。（5）蒙特卡洛法求解各种类型规划。*2022-12-25分枝定界法（1）分枝：通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；（2）定界：并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。（3）剪枝：在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题。分枝定界法*2022-12-25分枝定界法步骤（1）求解整数规划问题A对应的线性规划问题B（松弛问题）；（2）分枝，在松弛问题B的最优解中任选一个不符合整数条件的变量xj，其值为bj，以bj表

8、示小于bj的最大整数，构造两个约束条件 将这两个约束条件，分别加入问题B，求两个后继规划问题B1和B2。1和jjjjbxbx分枝定界法*2022-12-25分枝定界法*为整数对2121212121,0,05.1645.1432.2030maxxxxxxxxxtsxxz0,05.1645.1432.2030max)(212121210 xxxxxxtsxxzL：松弛问题5.2,5.321xx松弛问题的最优解：1 2 3 4 5 6 7 松弛问题的可行域增加x13增加x14L1L2分枝定界法例例2*0,05.1645.1432.2030max)(212121210 xxxxxxtsxxzL：松弛问

9、题x13x140,035.1645.1432.2030max)(2112121211xxxxxxxt sxxzL0,045.1645.1432.2030max)(2112121212xxxxxxxt sxxzL父问题子问题结论 1：（IP）的最优解一定在某个子问题中父问题的最优值为整数）对（2121212121,0,05.1645.1432.2030maxxxxxxxxxt sxxzIP5.2,5.321xx最优解：3：子问题中的整数解都是（IP）的可行解子问题的最优解2：子问题的可行域父问题的可行域*为整数2121212121,0,05.1645.1432.2030maxxxxxxxxxts

10、xxz0,05.1645.1432.2030max212121210 xxxxxxtsxxzL：松弛问题:0L155,5.25.3021zxx，x13x14:1L3440,6173121zxx，2321xx：1303z关闭341121xx，22854z3z27221xx，1305z无可行解剪枝21421xx，1302z剪枝,5.25.321xx，最优解：:2Lx22x233L4Lx12x135L剪枝6L130*23)(21ZxxIP最优值：，的最优解：1 2 3 4 5 6 7 4x1+x2=16.52x1+3x2=14.5z=30 x1+20 x2*某公司拟在市东、西、南三区建立门市部，拟议

11、中有7个位置Ai(i=1,2,7)可供选择。规定在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪些点可使年利润最大？0-1变量变量例例3 投资场所的选定投资场所的选定 0-1变量变量*,71,2,i点没被选用A，当0点被选用A，当1x令变量10引入iii71iiixcz Max71iiiBxb2xxx3211xx541xx761或0 xis.t.1.模型建立目标函数：约束条件：v在东区，由A1，A2，A3三个点中至多选两个

12、；v在西区，由A4，A5两个点中至少选一个；v在南区，由A6，A7两个点中至少选一个。0-1变量变量*2022-12-250-1 型整数规划0-1 型整数规划决策变量只能取0或1的整数规划，叫做0-1整数规划。决策变量称为0-1变量(二进制变量、逻辑变量)。0-1变量作为逻辑变量，常被用来表示系统是否处于某个特定状态，或者决策时是否取某个特定方案。在实际问题中引入0-1变量，可以把各种情况需要分别讨论的数学规划问题统一在一个问题中讨论了。时)P即取P(当决策不取方案 0时P当决策取方案 1x*某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表格所示。问两种货物各托运

13、多少箱，可使获得利润为最大?货物甲乙托运限制体积每箱（米3）5424重量每箱（百公斤）2513利润每箱（百元）20100-1 型整数规划例例4互相排斥的计划互相排斥的计划*2022-12-250-1 型整数规划 1.模型建立变量10为为整数x,x0,135245372445st.1020z Max212121212121yxxxxxxxxxx+(1-y)M+yM 假设现在有车运和船运两种运输方式，但只能选择一种运输方式，如用车运时关于体积的限制条件为5x1+4x224(车)。如用船运时关于体积的限制条件为7x1+3x245(船)。（这两条件互相排斥）。设甲、乙两种货物的托运箱数分别为x1，x2

14、，可获得的利润为z。设变量设变量y表示运货的方式，当表示运货的方式，当y为为1时，用车运，时，用车运，y为为0时，时，用船运。用船运。M是充分大的数是充分大的数*2022-12-250-1 型整数规划 模型分析用船运 1用车运 0yMyxxyMxx)1(4537244521210 用车运时y2121372445xxxx1 用船运时y4537452121xxxx失效MyxxyMxx)1(453724452121失效有多个相互排斥的约束条件*相互排斥的约束条件 如果有m个互相排斥的约束条件（0）若不生产第j种产品（即xj=0）j=1，2，3则问题的模型为500842321xxx300432321x

15、xx10032321xxx321 ,jyMxjjj3,2,1 且为整数0jxj321 1或0,jyjs.t.如果生产第如果生产第j j种产品，则其产量种产品，则其产量x xj j0 0，由，由x xj jM Mj jy yj j知，知，y yj j1 1。因此，相。因此，相应的固定费用在目标函数中将被考虑。应的固定费用在目标函数中将被考虑。同理，如果不生产第同理，如果不生产第j j种产品，则种产品，则其产量其产量x xj j=0=0，只有，只有y yj j为为0 0才有意义，因才有意义，因此，相应的固定费用不应在目标函数此，相应的固定费用不应在目标函数中被考虑。中被考虑。0-1 型整数规划 0

16、 1jy*2022-12-250-1 型整数规划解法只检查变量取值的组合的一部分的方法。：求解下列问题隐枚举法1 或 0,64 3 4422.523 3213232321321321xxxxxxxxxxxxxtsxxxzMax(a)(b)(c)(d)例6*2022-12-250-1 型整数规划解法解法一：隐枚举法(x1,x2,x3)z值abcd过滤条件过滤条件(0,0,0)0Z0(0,0,1)5Z5(0,1,0)-2(0,1,1)3(1,0,0)3Z8(1,0,1)(1,1,0)81(1,1,1)61 或 0,64 3 4422.523 3213232321321321xxxxxxxxxxxx

17、xtsxxxzMax所以，最优解所以，最优解(x x1 1，x x2 2，x x3 3)T T=(1=(1，0 0，1)1)T T，max max z z=8=8。*2022-12-250-1 型整数规划解法为了使最优解尽可能早出现，可先将目标函数中各变量的顺序按其系数大小重新排列，这样可进一步减少计算量。隐枚举法按目标函数中各变量系数的大小重新排列各变量按目标函数中各变量系数的大小重新排列各变量最大化问题：由小到大最大化问题：由小到大最小化问题：由大到小最小化问题：由大到小*解法二（优化）：重新排列xj的顺序(系数递减)321,106434422235max2321213213213，或 i

18、xxxxxxxxxxxstxxxzi321,106434422523max3221321321321，或 ixxxxxxxxxxxstxxxzi0-1 型整数规划解法*0-1型整数规划计算表目标函数z 3x12x25x3 5x33x12x2 最大值的上限是8，第二大的值是55x33x12x28 点(x3,x1,x2)约束条件满足条件?是否z值(1,1,0)8 8隐枚举法：共计算5次(均满足约束条件)。（最优解为1，0，1，最优值8）可根据计算逐渐改变过滤条件(该例因最大值的点满足其他四个约束，即找到最大化问题的最好的整数解。就不需验证计算第二大值的点是否满足约束条件)0-1 型整数规划解法过滤

19、隐枚举法*5432157428maxxxxxxz4323354321xxxxx423554321xxxxx)5,4,3,2,1(10jxj或步骤步骤1 1：将问题转化为如下标准形式：将问题转化为如下标准形式：njjjxcz1min),2,1(1mibxaijnjij),2,1(10njxj 或其中其中c cj j00，且，且c c1 1c c2 2c cn n。例7求解0-1整数规划（选学-分枝隐枚举法）0-1 型整数规划解法*如约束条件为，两边同乘(-1)；如约束条件为等式，可令变量 ，代入目标函数和其它约束条件中，将xn消掉。jnjijinxabx11 按目标函数中系数由小到大的顺序重新排

20、列变量，并将约束条件中的排列顺序做相应改变。zzzminnxnnxx1 如目标函数为max z，令 ，可化为 。如某个变量 的系数为负，令 ，使系数变正。0-1 型整数规划解法步骤步骤1 1：将问题转化为标准形式：将问题转化为标准形式：*调整后的0-1规划问题变为：1087542min14532xxxxxz2323314532xxxxx452314532xxxxx2,110 x3,4,5);(j1,0jjxj，或或(a)(b)步骤步骤2 2：令所有变量取令所有变量取0 0，求出目标函数值，并代入约束条，求出目标函数值，并代入约束条件中检查是否可行，如果可行即为问题的最优解；否则转下一件中检查是

21、否可行，如果可行即为问题的最优解；否则转下一步。步。014532xxxxxz 令 ，得-10，但不满足两个约束条件。0-1 型整数规划解法*步骤步骤3 3：分支和定界。依次令各变量分别取分支和定界。依次令各变量分别取0 0或或1 1，将问题划，将问题划分为两个子问题，分别检查解是否可行，如不可行继续对边界分为两个子问题，分别检查解是否可行，如不可行继续对边界值较小的子问题分支，直到找出一个可行解为止，这时得到值较小的子问题分支，直到找出一个可行解为止，这时得到 值的一个上界。值的一个上界。z分支过程见下图所示：12 x02 x13x03x0-1 型整数规划解法*步骤步骤4 4：考察所有子问题，

22、有以下四种情况：考察所有子问题，有以下四种情况：zzz 若某个子问题的边界值对应原问题的可行解，则将它的若某个子问题的边界值对应原问题的可行解，则将它的边界值与保留的边界值与保留的 值作比较，并取较优的一个作为新的值作比较，并取较优的一个作为新的 值。值。如所有子问题都已考察完毕，则保留下来的如所有子问题都已考察完毕，则保留下来的 值及其对应的解值及其对应的解即为即为0-10-1整数规划问题的最优解。整数规划问题的最优解。若某个子问题的边界值大于保留下来的若某个子问题的边界值大于保留下来的 值，不管其是值，不管其是否可行，则将这一分支剪掉。否可行，则将这一分支剪掉。z 若某个子问题不可行（若某

23、个子问题不可行（在该分支中的上级变量的值已经确定的情况下，其余变量不管取什么值都无法满足所有约束时，该枝的分枝已无可行解），则将这一分支剪掉。），则将这一分支剪掉。若某个子问题可行且边界值优于若某个子问题可行且边界值优于 值，但该边界值对应值，但该边界值对应的解不是可行解，则该问题待考察。如有多个问题待考察，优的解不是可行解，则该问题待考察。如有多个问题待考察，优先对其中最优值最大的一个子问题进行考察，转步骤先对其中最优值最大的一个子问题进行考察，转步骤3 3。z0-1 型整数规划解法*13x03x15x05x15x05x 分支边界值分支边界值 =-6=-6-4-4，但相应的解不可行，需继续分

24、支。，但相应的解不可行，需继续分支。过程如上图所示。过程如上图所示。*z0-1 型整数规划解法*上述求解过程也可用表格表示：上述求解过程也可用表格表示：(0(0，1 1，0 0，1 1，0)0)(0(0，1 1，1 1，0 0，0)0)(0(0，0 0，1 1，0 0，0)0)(1(1，0 0，1 1，0 0，0)0)(1(1，1 1，0 0，0 0，0)0)(0(0，1 1，0 0，0 0，0)0)(1(1，0 0，0 0，0 0，0)0)(0(0，0 0，0 0，0 0，0)0)-4，剪枝1 -4，剪枝-1不可行，剪枝-5 -4，剪枝-3可行 -4-4-6-8-10ba备注约束条件z 值序

25、号),(14532xxxxxzzzz0-1 型整数规划解法*所以，最优解：所以，最优解：即原问题的最优解为：即原问题的最优解为：4min,)00011(),(T14532zxxxxxT，4max,)00101(),(T54321zxxxxxT，分枝隐枚举法0-1 型整数规划解法*指派问题（0-1型）一、指派问题一、指派问题拟派n人去做n项工作，由于每人的专长不同，各人完成不同任务效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高的问题，这类问题称为指派问题(分派问题、分配问题)B1B2BnA1c11c12c1nA2c21c22c2nAncn1cn2cnn人人任务任务ci

26、j表示第表示第i个人个人完成第完成第j项任务项任务的效率。的效率。*二、指派问题的数学模型二、指派问题的数学模型 10),2,1(1),2,1(1.1111或ijnjijniijninjijijxnixnjxstxcMinZnnnnnnccccccccc212222111211=(Cij)指派问指派问题系数题系数矩阵矩阵B1B2BnA1c11c12c1nA2c21c22c2nAncn1cn2cnn人人任务任务解：设解：设项任务去完成第个人不分配第项任务去完成第个人分配第jijixij ,0 ,1指派问题（0-1型）*某单位现在、四某单位现在、四项工作需完成，现在甲、乙、项工作需完成，现在甲、乙

27、、丙、丁四个人均可完成这四项丙、丁四个人均可完成这四项任务。每人完成各项任务所用任务。每人完成各项任务所用的时间如右表所示，问应指派的时间如右表所示，问应指派何人去完成何项任务，使所需何人去完成何项任务，使所需时间最少？时间最少？甲甲215134乙乙1041415丙丙9141613丁丁78119ABCD任务任务人员人员9118713161491514410413152满足所有约束条件的可行解满足所有约束条件的可行解xij也可也可写成表格或矩阵形式，称为写成表格或矩阵形式，称为解矩阵解矩阵1000000101000010(xij)=本例的一个可行解矩阵(cij)=例例8 指派问指派问题题指派问题

28、（0-1型）*指派问题数学模型的性质：指派问题数学模型的性质：若从指派问题的系数的系数矩阵（cij）的一行（列）各元素中分别减去该行（列）的最小元素，得到新矩阵（bij），那么以（bij）为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。独立的独立的0元素：元素：位于不同行不同列的位于不同行不同列的0元素称为独立的元素称为独立的0元素。元素。结论：若能在系数矩阵(bij)中找出n个独立的0元素；则令解矩阵(xij)中对应这n个独立的0元素取值为1，其它元素取值为0。将其代入目标函数中得到zk=0，它一定是最小。这就是以(bij)为系数矩阵的指派问题的最优解，也就得到了问题的最优解。指派问题

29、（0-1型）*三、指派问题的解法（匈牙利法）三、指派问题的解法（匈牙利法）第一步第一步:使指派问题的系数矩阵经变换，在各行各列都出现元素。使指派问题的系数矩阵经变换，在各行各列都出现元素。（）从系数矩阵的每行元素减去该行的最小元素；（）再从所得系数矩阵的每列元素中减去该列的最小元素。9118713161491514410413152241047501110062111302497min0010235096060713024min指派问题（0-1型）*经第一步变换后，系数矩阵中每行每列都已有了0元素；只需找出n个独立的0元素，若能找出，就以这些独立的0元素对应解矩阵中的元素为1，其它作为0，这就

30、得到最优解。找独立0元素的步骤如下：第二步：进行第二步：进行试指派试指派，以寻求最优解。，以寻求最优解。0（1）从只有一个从只有一个0元素的行开始，给这个元素的行开始，给这个0元素加圈，记作元素加圈，记作.然后再划去然后再划去所在列的其它所在列的其它0元素，记作元素，记作 。00102350960607130（2）给只有一个给只有一个0元素的列的元素的列的0元素加圈，元素加圈，记作记作；然后划去；然后划去所在行的所在行的0元素，记元素，记作作 。0指派问题（0-1型）*00102350960607130（3）反复反复(1),(2)两步，直到所有两步，直到所有0元素都元素都被圈出和划掉为止。被圈

31、出和划掉为止。（4）若各行各列均有多于若各行各列均有多于2个的个的0元素未被元素未被圈出或划掉，任选其中任意一个圈出或划掉，任选其中任意一个0元素加圈。元素加圈。（5）若若元素的数目元素的数目m等于矩阵的阶数等于矩阵的阶数n，那么指派问题的最优解已得到，若那么指派问题的最优解已得到，若m4）,x23）（组条件起作用第，组条件不起作用第，定义1,2ii 0i 1yi又又M为任意大为任意大正数，则问题正数，则问题可表达为：可表达为：134142122211211yyMyxMyxMyxMyx指派问题（0-1型）*4、用以表示固定费用的函数、用以表示固定费用的函数0)(00)()(jjjjjjjxxx

32、cKxC生产费用函数：生产费用函数：100)(1或ijjnjjjjjyMyxyKxcMinZ引入变量引入变量yj种产品不生产第种产品生产第iiyj,0,1指派问题（0-1型）*例10 东方大学计算机实验室聘用4名大学生（代号1、2、3、4）和2名研究生（代号5、6）值班答疑。已知每人从周一至周五每天最多可安排的值班时间及每人每h值班的报酬如下表学生代号报酬（元/h)每天最多可安排的值班时间周一 周二 周三 周四 周五12345610109.99.810.811.3 0 6 0 70 6 0 6 0 8 3 0 5 5 6 0 4 0 4 8 00 6 0 6 3应用举例*该实验室开放时间是上午

33、8点至晚上10点，开放时间内须有且仅需一名学生值班，规定大学生每周值班不少于8h，研究生每周不少于7h，每名学生每周值班不超过3次，每次值班不少于2h，每天安排值班的学生不超过3人且其中必须有一名研究生，试为该实验室安排一张人员的值班表，使总支付的报酬最少解：设xij为学生i在周j的值班时间，10ijy安排学生i在周j值班否则用aij代表学生i在周j最多可安排的值班时间，ci为学生i的每h的报酬，则其数学模型为应用举例*6511515161516156min2(1,6;1,5)8(1,4)7(5,6)14(1,5).3(1,6)3(1,5)1(1,5)0,0/1(1,6;1,5)iijijij

34、ijijijijjijjijiijjijijjijijZc xyxa yijxixixjs tyiyjyyjxyij不超过可安排时间大学生每周值班不少于8h研究生每周值班不少于7h实验室每天开放14h每名学生一周值班不超过3次每天值班不超过3人每天有一名研究生值班应用举例*学生代号一 二 三 四 五123456 6 7 6 7 4 6 4 6 8 5 8 5 6 6 2 2 2 2 2 6 3 2 6 3 最优结果为总支付报酬每周727.5元值班方案为：应用举例*2022-12-25蒙特卡洛法整数规划蒙特卡洛法(Monte Carlo method)也称为随机取样法，进行大统计量（N）的统计实

35、验方法或计算机随机模拟方法。当所求解问题是某种随机事件出现的概率，或者是某个随机变量的期望值时，通过某种“实验”的方法，以这种事件出现的频率估计这一随机事件的概率，或者得到这个随机变量的某些数字特征，并将其作为问题的解。大数定理：均匀分布的算术平均收敛于真值中心极限定理：置信水平下的统计误差*Monte Carlo方法的基本思想很早以前就被人们所发现和利用。早在17世纪，人们就知道用事件发生的“频率”来决定事件的“概率”。19世纪人们用投针试验的方法来决定圆周率。本世纪40年代计算机的出现、特别是近年来高速计算机的出现，使得用数学方法在计算机上大量、快速地模拟这样的试验成为可能。使用蒙特卡罗方

36、法估算值.放置30000个随机点后,的估算值与真实值相差0.07%.蒙特卡洛法整数规划*2022-12-25蒙特卡洛法整数规划求解问题可以分为两类:确定性问题和随机性问题。解题步骤：1.根据提出的问题构造一个简单、适用的概率模型或随机模型，使问题的解对应于该模型中随机变量的某些特征（如概率、均值和方差等），所构造的模型在主要特征参量方面要与实际问题或系统相一致 2.根据模型中各个随机变量的分布，在计算机上产生随机数，实现一次模拟过程所需的足够数量的随机数。通常先产生均匀分布的随机数，然后生成服从某一分布的随机数，方可进行随机模拟试验。*2022-12-25蒙特卡洛法整数规划 解题步骤：3.根据

37、概率模型的特点和随机变量的分布特性，设计和选取合适的抽样方法，并对每个随机变量进行抽样（包括直接抽样、分层抽样、相关抽样、重要抽样等）。4.按照所建立的模型进行仿真试验、计算，求出问题的随机解。5.统计分析模拟试验结果，给出问题的概率解以及解的精度估计。*2022-12-25蒙特卡洛法整数规划例：随机变量x=0，1，2表示每分钟到达超市收款台的人数，有分布列模拟十分钟内顾客到达收款台的状况。xk012pk 0.40.30.3r=rand(1,10);for i=1:10;if r(i)0.4 n(i)=0;else if 0.4=r(i)&r(i)0.7 n(i)=1;else n(i)=2;

38、end endendr,n*如下图，正方形的面积A=1；1/4圆的面积B=/4。我们想象有一个容器在正方形中夹有一个极薄的圆弧隔板。下小雨时搬至屋外，经一定时间后，称1/4圆的容器内的水重C，与作为一个整体的正方形中的水重D。C与D之比应该等于B与A之比，即可得例例10 求求的近似值蒙特卡洛法整数规划*让计算机来模拟雨点落下：产生伪随机数 x 和 y，让 x 的值的范围在 01 之间；让 y 的值的范围也在 01 之间，模拟雨点落在正方形中，当然会有的雨点落在1/4圆中。数以百万计雨点可以累计得到 C 和 D，从而上述公式算出的近似值。关键点：落入扇形区的判据蒙特卡洛法整数规划*2022-12

39、-25蒙特卡洛法整数规划%随机模拟方法%c=0;x=0;y=0;pai;for i=1:20000 x=rand(1,1);%雨点在x方向的位置y=rand(1,1);%雨点在y方向的位置if(x*x+y*y=1.0)c=(c+1);endendpai=(4*c/20000)模型求解*2022-12-25实验准备问题 习题2.3 生产计划安排（P18）准备工作：1、matlab软件的熟悉2、矩阵的表示 和基本操作3、随机数产生函数的用法 实验要求 独立完成实验报告写出完整的模型假设、模型建立、模型求解（源代码）、模型结果、模型分析（结果说明什么问题？达到建模目的？适用范围？模型是否合理？）*2022-12-25*