MATLAB使用蒙特卡洛算法求解线性整数规划和01规划

　　蒙特卡洛方法是一种利用计算机的随机数理论模拟实际的情况的一种方法。今天主要是以实例讲解蒙特卡洛方法的MATLAB编程实现求解线性整数规划和01规划。
　　实例1
　　首先使用intlinprog线性整数规划求解函数对该线性规划进行求解，该函数的语法如下：xintlinprog（f，intcon，A，b）xintlinprog（f，intcon，A，b，Aeq，beq）xintlinprog（f，intcon，A，b，Aeq，beq，lb，ub）xintlinprog（f，intcon，A，b，Aeq，beq，lb，ub，x0）xintlinprog（f，intcon，A，b，Aeq，beq，lb，ub，x0，options）xintlinprog（problem）〔x，fval，exitflag，output〕intlinprog（）intlinprog函数标准型xintlinprog（f，intcon，A，b，Aeq，beq，lb，ub）f系数阵intcon变量个数A，b：不等式限制条件Axb中的A和bAeq，beq：等式限制条件中的Aeqxbeq中的Aeq和beqlb，ub：自变量的最小值和最大值用x，Fval代替上述各命令行中左边的x，则可得到在最优解x处的函数值Fval〔x，fval〕intlinprog（f，intcon，A，b，Aeq，beq，lb，ub）
　　程序clc；clearall；f〔58〕；A〔11；59〕；b〔645〕；lbzeros（2，1）；intcon〔12〕；〔x，fval〕intlinprog（f，intcon，A，b，〔〕，〔〕，lb，〔〕）；fprintf（maxf（x）在x1fx2f处取得最大值：f，x（1），x（2），fval）；
　　运行结果LP：Optimalobjectivevalueis41。250000。Heuristics：Found1solutionusingZIround。Upperboundis39。000000。Relativegapis2。50。CutGeneration：Applied1Gomorycut。Lowerboundis40。000000。Relativegapis0。00。Optimalsolutionfound。Intlinprogstoppedattherootnodebecausetheobjectivevalueiswithinagaptoleranceoftheoptimalvalue，options。AbsoluteGapTolerance0（thedefaultvalue）。Theintconvariablesareintegerwithintolerance，options。IntegerTolerance1e05（thedefaultvalue）。maxf（x）在x10。000000x25。000000处取得最大值：40。000000
　　蒙特卡洛求解线性整数规划程序
　　主程序（使用floor向下取整函数）
　　floor函数floor朝负无穷大四舍五入此MATLAB函数将X的每个元素四舍五入到小于或等于该元素的最接近整数。Yfloor（X）Yfloor（t）Yfloor（t，unit）clc；clearall；rand（state，sum（clock））；初始化随机数发生器f0inf；x0〔〕；num1e7；tic计时开始fori1：numx06rand（2，1）；随机产生初始解x1floor（x）；向下取整函数〔f，g〕mengte3（x1）；调用自定义函数计算ifsum（g0）2iff0f求最大值如果当前值更优，则更新值x0x1；f0f；endendendtoc计时结束fprintf（maxf（x）在x1fx2f处取得最大值：f，x0（1），x0（2），f0）；
　　自定义函数mengte3。mfunction〔f，g〕mengte3（x）f是目标函数g（x）0f5x（1）8x（2）；x1x（1）；x2x（2）；g〔x1x26；5x19x245〕；end
　　运行结果历时10。114315秒。maxf（x）在x10。000000x25。000000处取得最大值：40。000000
　　使用ceil向上取整函数求解ceil朝正无穷大四舍五入此MATLAB函数将X的每个元素四舍五入到大于或等于该元素的最接近整数。Yceil（X）Yceil（t）Yceil（t，unit）
　　主程序clc；clearall；rand（state，sum（clock））；初始化随机数发生器f0inf；x0〔〕；num1e7；tic计时开始fori1：numx06rand（2，1）；随机产生初始解x1ceil（x）；〔f，g〕mengte3（x1）；调用自定义函数计算ifsum（g0）2iff0f求最大值如果当前值更优，则更新值x0x1；f0f；endendendtoc计时结束fprintf（maxf（x）在x1fx2f处取得最大值：f，x0（1），x0（2），f0）；
　　运行结果历时11。714213秒。maxf（x）在x13。000000x23。000000处取得最大值：39。000000
　　实例2
　　首先使用intlinprog线性整数规划求解函数对该线性规划进行求解：
　　程序clc；clearall；f〔6235〕；A〔3516；2111；1245〕；b〔4310〕；intcon〔1234〕；lbzeros（4，1）；ubones（4，1）；〔x，fval〕intlinprog（f，intcon，A，b，〔〕，〔〕，lb，ub）；fprintf（maxf（x）在x1fx2fx3fx4f处取得最大值：f，x（1），x（2），x（3），x（4），fval）；
　　运行结果LP：Optimalobjectivevalueis14。500000。Heuristics：Found1solutionusingZIround。Upperboundis13。000000。Relativegapis0。00。Optimalsolutionfound。Intlinprogstoppedattherootnodebecausetheobjectivevalueiswithinagaptoleranceoftheoptimalvalue，options。AbsoluteGapTolerance0（thedefaultvalue）。Theintconvariablesareintegerwithintolerance，options。IntegerTolerance1e05（thedefaultvalue）。maxf（x）在x11。000000x20。000000x31。000000x41。000000处取得最大值：14。000000
　　蒙特卡洛求解01规划程序
　　主程序（四舍五入round函数）clc；clearall；rand（state，sum（clock））；初始化随机数发生器f0inf；x0〔〕；num1e7；tic计时开始fori1：numx01rand（4，1）；随机产生初始解x1round（x）；利用四舍五入round函数01变量〔f，g〕mengte4（x1）；调用自定义函数计算ifsum（g0）3iff0f求最大值如果当前值更优，则更新值x0x1；f0f；endendendtoc计时结束fprintf（maxf（x）在x1fx2fx3fx4f处取得最大值：f，x0（1），x0（2），x0（3），x0（4），f0）；
　　自定义函数mengte4。mfunction〔f，g〕mengte4（x）f是目标函数g（x）0f6x（1）2x（2）3x（3）5x（4）；x1x（1）；x2x（2）；x3x（3）；x4x（4）；g〔3x15x2x36x44；2x1x2x3x43；x12x24x35x410〕；end
　　运行结果历时11。086100秒。maxf（x）在x11。000000x20。000000x31。000000x41。000000处取得最大值：14。0
　　本文内容来源于网络，仅供参考学习，如内容、图片有任何版权问题，请联系处理，24小时内删除。
　　作者郭志龙
　　编辑郭志龙
　　校对郭志龙