文档介绍：数学规划模型韩会磊四川大学数学学院 E-mail:******@scu.; huileihan@ I 引言一个复杂系统往往要受诸多因素的影响,而这些因素又要受到一定的限制。最优化就是研究在一定约束下,如何选取这些因素的值,使某项(或某些)指标达到最优的一门学科。数学规划是最优化中的重要部分。它包括线性规划、整数规划、目标规划、动态规划、非线性规划等。数学规划方法在经济、军事、科技等领域内都有广泛的应用。内容提要一、一般的数学规划模型二、数学规划常见模型: 1. 运输问题(例 1,2) 2. 网络(规划)问题(例 3,4) 3. 分派问题(例 5) 4. 生产活动问题(例 6,7,8,9) 5. 选址问题(例 10 , 11 , 12 , 13 , 14 ) (例 15 ) 7. 线性目标规划问题(例 15 ) 一、一般的数学规划模型数学规划模型的一般形式: )( min Xfz?)( nRSX?? TnxxxX),,,( 21??) 或)( max (Xfz?例如: )0( 2??kkxy z max0,0 , 222????yx dyx .}0,,|), {( 222????yxdyxyxS TyxX),(?若能写出描述 S的数学式子,则可直接写出。这里)( nRSX?? TnxxxX),,,( 21??)( min Xfz?) 或)( max (Xfz?目标函数可行域可行解决策变量描述 S 的数学式子约束条件 S????问题可行问题不可行?X 最优解?z 最优目标值几个概念: 特别: nnxcxcxcz????? 2211 min (或 max) 或??? nj jjxcz 1 min mibxats i nj j ij,,2,1,),(.. 1??????? 11212 1 11..bxaxaxats nn????? 22222 121bxaxaxa nn????? mn mn mmbxaxaxa????? 2211??) , (或 1b??) , (或 2b??) , (或 mb??njx j,,2,1,0???njx j,,2,1,0???线性规划模型( LP ) 或 CX z? min b AX ts?..OX?等约束的 LP 模型的矩阵形式 LP 模型的向量形式注:M? CX z? min b AX ts?..OX? M是常数与 CX z? min b AX ts?..OX?有相同的最优解 . CX z? min b AX ts?..OX? CX z?? 0 max b AX ts?..OX?与有相同的最优解另外: 1. 取整数,称模型为整数规划模型 jx jx 2. 中部分取整数,称模型为混合整数规划模型 jx 3. 只取 0或1两个值,称为 0 — 1 规划模型 , 称为非线性规划模型 ,称为单目标规划模型; 若目标函数不只一个,称为多目标规划模型。 nBBB? 21mA A A? 2 1ma a a? 2 1nbbb? 21 mn mm n c??????? 21 222 21 112 11 产地销地运价例1求使总运费最少的调运方案。试建模。产量需求量 42 一、运输问题????? mj j mi iba 11 假设解的运量。到销地为产地设 ji ijBAx 则????? mi nj ij ijxcz 11 min ???? nj i ijmiaxts 1,,2,1,..????? mi j ijnjbx 1,,2,1,?njmix ij,,2,1;,,2,1,0?????产销平衡注:若产大于销,则??? nj i ijmiax 1,,2,1,??若产小于销,则??? mi j ijnjbx 1,,2,1,??线性规划模型