工程最优化第七章.ppt

1、第七章定义了整数修订计划(IP )、7.1概要、变量的一部分或全部取整数的数学修订计划，IP在工程设施修订、经济修订计划、生产管理和科研领域具有实用价值。 在许多实际问题中，许多变量，例如人数、机械台数、产品个数、工程项目数等，只能取整数或离散值(后者能够通过适当的转换转换为整数值)。 (1)目标函数和约束条件是否为线性： LIP (线性IP )、NLIP (非线性IP )； 关于IP的求解，因为不能使用相关变量的连续、容易导出等分析概念，难易度高，理论上连续订划不成熟。 迄今为止没有十分有效的通用解法。 只能解决中小型LIP和某种特殊类型的NLIP。 (2)按变量类型：全部IP； 混合IP；

2、 01 .解IP的两种方法： (1)解除整数限制，求出作为连续修正图像的解，然后向可执行区域方向进行舍入，得到IP的近似最佳解。 (1)连续修正图像最佳解为x(0)18/7、19/7t、(2)舍入误差最小为x(1)3、3t、不可点、(3)取向可执行区域，该方法的缺点：(1)无法以舍入误差最小的原则严格地调整连续最佳解。 不这样做时得到的解可能不可能，(2)即使可能进行整数化得到的近似最佳整数解，但对于其近似精度大多不好的(3)大的问题，舍入方法的校正计算量相当大。 有按变量舍弃、放入两种可能性。 例如，由于有100个变量，因此可以得到2100 1.26765061030次实验的解。 并且，不能

3、保证得到真正的最佳整数解。 但是，由于该方法的简易性，工程应用程序中仍在使用，存在对精度要求不太高的IP问题。 请注意，舍入误差对精度的影响仅在变量值大时(例如大于20时)才小。 求解IP的两种方法： (1)消除整数约束，获得连续校正图像最佳解作为连续校正图像解，其后在可执行区域的方向上进行舍入，从而获得IP的近似最佳解。 (2)使用专门解IP的方法，求出更正确的最佳整数解。 一般的方法是完全枚举法、隐藏枚举法、分支边界法、割平面法、蒙特卡罗法等7.2完全枚举法(贫穷法)，理论上，IP的可执行解的数量有限，可以“简单”地列举所有可执行解，优点： (1)IP有多少(2)程序设计简单，不需要了解很

4、多数学理论和程序设计技术；(3)寻求全局最大优点。 缺点：补正量太大，(例如，将20个任务分别分配给20个人完成，不同的分配方案一共20=2.43290201018种，使用每秒千亿次的计算机也要近一个月。 因此，仅适用于小规模问题的解决，例如，n10-15，解：完全枚举程序：整数x，yp max=0. do1I=1，51 x=I1do1j=1，51 y=j1if (3* x 12 * y.gt.) 3 I 10 )停止结束在经过2601个周期后变为x*=16、y *=0、z *=768，如果在从3x 12y 50可知x 50/3=16.67、y50/12=的3x 12y 50解y (503x)

5、/12，则在x从0变为16时只是改变为12，循环次数进一步减少到22次，7.3随机列举法在可执行解的数目多、采样次数足够多(例如106 )时，可得到“满意解”。解：这个问题的可执行解为10051010个，目前15105个抽样，程序必须是P217 :P218第一行PMAX2147483647 (机器的最小整数)第二行是do1I 1，1500000第四行的UNI(0)萨为什么？ 从概率统一修正样本分布的观点来说，将一次样本落入S1的概率设为f，全部进行n次实验，其中一次落入S1的概率为P1(1f )N，最佳解为x*，反复点落入S1时被认为是“满意解”， 由于n一般较大，因此N106为P=10.991000000=0.999 (43个9 )，如果还不满足，则设f=0. 00001 n 106p=10.9999100