24系统工程与运筹-复习.pptxVIP

2017/6/26;初始基本可行解;初始基本可行解;单纯形法的表格形式;单纯形法的表格形式;单纯形法的表格形式;单纯形法的表格形式;单纯形法的表格形式;单纯形法的表格形式;单纯形法的表格形式;单纯形法的表格形式;单纯形法的表格形式;单纯形法的表格形式;单纯形法的表格形式;单纯形法的表格形式;单纯形法的表格形式;;单纯形法的表格形式;单纯形法的表格形式;单纯形法的表格形式;求目标函数值最小的线性规划问题;原 始 对 偶 表;min z= 2x1+4x2-x3 s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15;写对偶问题的练习（2）;表明第j项任务只能有1人或1台设备完成;为效率矩阵或系数矩阵，其 元素大于零，表示分配第i人去完成第j 项任务时的效率（或时间、成本等）,i,j=1,2,…,n。;;?匈牙利算法基本思想： 对同一工作i来说，所有机床的效率都提高或降低同一常数，不会影响最优分配；同样，对同一机床j来说,做所有工作的效率都提高或降低同一常数，也不会影响最优分配。 匈牙利算法：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。;例 求下表所示效率矩阵的指派问题的最优解;[解];进行试指派——通过行检验、列检验;;在没有被直线覆盖的部分中找出最小元素，然后在打?行各元素都减去这最小元素，而在打?列中各元素都加上这最小元素，以保证原来0元素不变，这样得到新的系数矩阵（它的最优解和原问题相同）。若得到n个独立的0元素，则已经得到最优解。否则回到第三步重复进行。;返回第二步：行检验、列检验;最优方案1：指定甲-B，乙-D，丙-E，丁-C，戊-A,所需要的时间最少为32小时。;练习 有一份中文说明书，需翻译成英、日、德、俄四种文字，分别记作E、J、G、R，现有甲、乙、丙、丁四人，他们将中文说明书翻译成英、日、德、俄四种文字所需时间如下：;[解]：;指定甲译俄文，乙译日文，丙译英文，丁译德文，所需要的时间最少。m表示 的个数，n表示矩阵的阶。;若H(x)为正定，该驻点X*是严格局部极小值点； 若H(x)为负定，该驻点X*是严格局部极大值点； 若H(x)为半正定（半负定），则进一步观察它在该点某邻域内的情况，可能是可能不是； 如果H(x) 不定的，该驻点X*就不是f(X)极值点。;二、极值点的必要条件和充分条件 最优性条件的研究是非线性规划理论研究的一个中心问题。 为什么要研究最优性条件？ 本质上把可行解集合的范围缩小。 它是许多算法设计的基础。;无约束问题的最优性条件 （P1） Min f(X) X ? En 定理3（一阶必要条件） 设f(X)在X*点可微，则X*为（P1） 的一个局部极值点，一定有 ?f(X*)=grad f(X*)=0（ X*称为驻点）;无约束问题的最优性条件 （P1） Min f(X) X ? En 定理4（二阶必要条件） 设f(X)在X*点二阶可微，如果X*为 （P1） 的一个局部极小点，则有 ?f(X*) =0 和 H（ X* ）为半正定。;无约束问题的最优性条件 （P1） Min f(X) X ? En 定理5（二阶充分条件） 设f(X)在X*点二阶可微，如果?f(X*) =0 和 H(X*)为正定，则X*为(P1) 的一个局部极小点。; ; ;例 Min f(X)= 2x12+5x22+x32+ 2x2x3 + 2x1x3 - 6x2+3 X ? E3 解：?f(X) = （4x1+ 2x3, 10x2+ 2x3 – 6, 2x1+ 2x2 + 2x3 ）=0 驻点x*=(1,1,-2) H(X) =?2f(X)=;H(X) =?2f(X)=;H(X)正定， X*=(1,1,-2)为最优解。 f(X*)=0;例 利用极值条件解无约束非线性规划问题 解 因为