线性规划求最优解

1期中考试：4月18日8:00-9:30410624月23日(周六)调课春假后5月6日(周五)8:00–9:30第二节经典分配(指派)问题与匈牙利法3n个员工分配作n项工作，已知第i个员工做第j项工作的成本为cij，i=1,…,n;j=1,…,n。规定：每人完成其中一项，每项只交给一个人完成。求最佳分配方案。两个基本类型若完成任务的成本表现为资源的消耗,则考虑的是如何分配任务,使目标极小化;若完成任务的成本表现为生产效率的高低,则要考虑如何分配,使目标极大化。分配问题的数学模型设决策变量为：401否则项工作员工分配做第第jixijn1in1jijijc=zmax)min(orxn,1,2,=i1xn1jijn,1,2,=j1xn1iijn,1,=jn;,1,2,=i1,0xij或s.t.5nnnnnnnnccccccccccccccccC321333323122322211131211•分配问题(基)可行解的结构:在n2个分量中只有n个分量为1,其余的全部为0;并且这些为1的分量的位置应位于成本矩阵的不同行不同列上.即分配问题的解应对应于成本矩阵的不同行与不同列(为什么?)分配问题成本（效率）矩阵例：已知分配A1、A2、A3、A4、A5五人分别完成五项任务,他们分别完成各任务的时间如下6人工作B1B2B3B4B5A14871512A279171410A3691287A46714610A56912106cij问应如何分配,使这五人分别完成这五项任务的总时间最小?匈牙利算法基本思想•匈牙利算法适用于极小化且成本矩阵的所有元素都非负的分配问题•如果成本矩阵的所有元素都非负,并且存在一组位于不同行不同列的0元素,则只要令对应于这些0元素位置的xij=1,其余的xij=0,即为所求的最优解.因为此时必有z=0就是问题的最优值•匈牙利算法的关键:如何产生并寻找一组位于不同行不同列的0元素7分配问题的性质—匈牙利算法的依据8定理1：对于分配问题，成本矩阵的任一行(或列)减去(或加上)一个相同的数得到的新指派问题与原问题同解作用:如何在效率矩阵中产生零元素9s)(s)(xcxcxs)(xcxcs)x(cxc=zn1jkjkjnki1in1jijijn1jkjn1jkjkjnki1in1jijijn1jkjkjnki1in1jijijz证明：指派问题的性质(续)•定理2:若成本矩阵C的元素可分成0与非0两部分,则覆盖0元素的最少直线数等于不同行不同列的0元素的最大个数.•作用:如何寻找位于不同行不同列的零元素.10分配问题的求解-匈牙利方法步骤11第一步：成本矩阵的每一行及每一列减去该行或列的最小数，使每行每列至少有一个0；第二步：画直线覆盖全部0元素。覆盖原则如果直线条数=n（此时矩阵每行都有一个打（）的0，并且所有打（）的0必在不同行不同列）,只要令对应打（）0元素的xij=1即为最优解，算法结束。如果直线条数n（此时打（）的0个数n），转下一步；第三步：进行成本矩阵变换。变换原则得到一个新的成本矩阵，转第二步。直到矩阵的每一行都有一个打（）的0元素为止覆盖原则•1、从第一行开始，若该行只有一个0元素，就对这个0打上（），对打（）的0元素所在列画一条直线；若该行没有或有两个以上0（已划去的不计在内），则转下一行，依次进行到最后一行；•2、从第一列开始，与行做法类似，依次进行到最后一列；•3、重复以上两个步骤。若还有未被划去的0,且未被划去的0之间存在闭回路。这时可沿着闭回路的走向，对每个间隔的0打（），然后对打（）的0，或所在的行，或所在的列，画一条直线。12变换原则1、从矩阵未被直线覆盖的数字中找出一个最小的数k；2、对矩阵的每行，当该行有直线覆盖时，令ui=0，无直线覆盖的令ui=k；3、对矩阵有直线覆盖的列，令vj=-k，对无直线覆盖的令vj=0；4、从原矩阵的每个元素cij中分别减去ui和vj，得到一个新矩阵。13例题求解146101296106147678129610141797121578466674310463040810126303710208113400432040500123203771081103004320405001232037710811030()()()()150321050501112103660091103104320405001232037710811030()()()()01101-1000-1()()()()()因为直线数=5=n,所以算法停止.最优分配方案:31BA22BA13BA44BA55BA最小的总时间:)(2866697h一般指派问题16最大化分配问题人数和工作数不等的分配问题一个人可做几项工作的分配问题某项工作一定不能由某人做的分配问题最大化分配问题转化为最小化：maxZ=ΣΣcijxijminZ’=ΣΣ(-cij)xijminZ’’=ΣΣ(M-cij)xij=ΣΣbijxijM是足够大的常数，新问题的最优解就是原问题的最优解17最大化分配问题18610129610617711781296101429121215784最大化分配问题最大值617101712179176171017617171771711177178171217917617101714172179171217121715177178174171175811711010610958117315855210913最小化分配问题人数和工作数不等的分配问题191012966177118129614291215784101296617711812961429121578400000一个人可做几项工作的分配问题2078329824763195232154321BBBBBAAA31952319527832982476319525432111321BBBBBAAAAAA1可同时做三项工作某项工作一定不能由某人做的分配问题21452782946178298247639525432154321BBBBBAAAAA452782946178298247639525432154321MMAAAAABBBBBA1不能做B4;A3不能做B322复习232425目标规划(Goalprogramming)目标规划的数学模型目标规划的图解法目标规划的单纯形法目标规划概述目标规划是在线性规划的基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个分支。2、线性规划求最优解；目标规划是找到一个满意解。1、线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。一、目标规划概述（一）、目标规划与线性规划的比较4、线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要（或更能满足需要）。3、线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急和主次之分，即有优先权。目前，已经在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到了广泛的应用。（二）、目标规划的基本概念例题4—1线性规划模型为：maxZ=8x1+10x22x1+x2≤11①x1+2x2≤10②x1,x2≥0X*=(4,3)TZ*=62目标函数的地位突出，约束条件是必须严格满足的等式或不等式，是绝对化的“硬约束”，此种问题若要求太多时，很容易相互矛盾，得不到可行解。如根据市场情况再加以下要求：(1)产品Ⅰ产量不大于产品Ⅱ。(2)超过计划供应原材料时，需高价采购，这使成本增加。(3)应尽可能充分利用设备工时，但不希望加班。(4)利润不少于56元。用式子表示：x1-x2≤02x1+x2≤11x1+2x2=108x1+10x2≥56左边：决策值（表示实际执行效果）右边：目标值（表示理想目标）实际效果与理想目标之间可能有偏差值（不足或者超过），若引入偏差变量，就可变成等式。例题4—2：解：确定优先因子后得数学模型：minZ=P1d1++P2(d2-+d2+)+P3d3-2x1+x2≤11（在绝对约束基础上进行目标规划）x1-x2+d1--d1+=0(要求：d1+尽可能小，最好是0才能满足≤)x1+2x2+d2--d2+=10（要求：d2-和d2+都尽可能小，最好等于0）8x1+10x2+d3--d3+=56（要求：d3-尽可能小，最好是0才能满足≥）x1,x2,di-,di+≥0