线性规划与二次规划

第五讲:线性规划与二次规划---水鹏朗数学建模理论与实验5.1线性规划举例例1某工厂每日8小时产量不低于1800件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员：速度15件/小时，正确率95%，计时工资3元/小时。检验员每错检一次，工厂要损失2元。问题：为使总检验费用最省，应聘用一级、二级检验员各几名？决策变量：设需要一级和二级检验员的人数分别为x1，x2人工资花费：121284833224xxxx错检损失：1212825(10.98)815(10.95)2812xxxx总花费：124036zxx约束条件：128258151800xx125345xx120;0xx5.1线性规划举例12121212min{4036[40,36][,]}..,534500Tzxxxxstxxxx线性规划：目标函数是线性函数，约束条件是线性不等式或等式。满足约束条件的所有点构成的集合称作可行解集合。1x2x125345xx可行解集合1212max{}..,0;0xxstxx凸多边形区域subjectto=s.t.5.1线性规划举例配餐问题有m种不同类型的食物,，这些食物提供了有益于健康的n种营养成分。是人体每天对营养成分的最小需求量。是食物的单价.是每单位质量的食物包含营养成分的量。问题：如何配餐的花费代价最小？12,,,mFFF12,,,nNNNjcjNibiFjiaiFjN决策变量：设每天食物的量分别是iFix花费代价：1miiiCbx营养约束：1,1,2,,0,1,2,,mjiijiiaxcjNxim5.1线性规划举例线性规划11min..,,1,2,,0,1,2,,miiimjiijiiCbxstaxcjnximmin..,0TstbxAxcx111111212222122212,,,mmmmnnnnmxbcaaaxbcaaaxbcaaaxbcA5.1线性规划举例运输问题有I个生产基P1，P2，…,PI存储着某种货物，这些货物必须运至J个港口M1,M2,…,MJ装船出口。生产基地Pi存储货物的总量是si(i=1,2,…,I),港口Mj对货物运输能力是rj.设从基地Pi到港口Mj单位质量货品的运输价格是bij.在基地库存充足情况下，设计一个运输调度方案，满足：1).基地所有存货被运抵港口；2).每个港口的运输能力被充分利用；3).运输调度方案的总运费最小。(注：库存充足意味着s1+s2+…+sIr1+r2+…+rJ.)决策变量：设从基地Pi运输到港口Mj的货物量为yij总运费：11IJijijijCby存货全部运出约束：1Jijijys运输能力充分利用约束：1Iijjiyr非负约束：0ijy5.1线性规划举例线性规划1111min..,,1,2,,,1,2,,0,1,2,,;1,2,,IJijijijIijjiJijijijCbystyrjJysiIyiIjJ标准化111212121111212121[,,,,,,,,,,],[,,,,,,,,,,]TJJIIJTJJIIJbbbbbbbyyyyyyyby11112222(IJ)12I(IJ);,JJJJJeqeqIrrrsss，eeeeeeAceee100010Ac0011J1jJj10e是元素全是的维行向量是维行向量是第个元素为，其它元素是0的J维行向量min..,TeqeqstbyAycAycy05.1线性规划举例数据拟合问题-Min_Max问题设测定了一组数据,用次的多项式拟合变量x和y之间的关系,问题:找一个m次多项式使得所有数据点的最大偏差是最小的。{(,):1,2,,}nnxynN(1)mmn问题描述设多项式函数为0101()[1,,,][,,,]mimmiiTmmyPxaxxxaaaaa在每个数据点的偏差()[1,,,]mkmkkkkkPxyxxya5.1线性规划举例问题描述(续)1,2,,minmax{}where[1,,,]kkNmkkkkxxyaa绝对值约束转化为线性约束[1,,,][1,,,]mkkkkmkkkkxxyxxyaa关于a的线性等式约束引进辅助变量控制所有样本点的偏差max{}k[1,,,][1,,,]mkkkmkkkxxyxxyaa[1,,,][1,,,]mkkkmkkkxxyxxyaa转下页5.1线性规划举例线性规划1[,]min..,mstaAca111222111222111111,111111mmmnnnmmmnnnyxxyxxyxxyxxyxxyxxAc5.1线性规划举例线性分式规划问题-LinearFractionalProgramming找出n维向量,使得线性分式函数12[,,,]nnxxxx在非空、有界集合neqeqRAxbxAxb基本假定：线性分式函数的分母在集合上是严格正的.()TTfcxxdx上的最大值。max()..,nTTeqeqfstxcxxdxAxbAxb带线性约束的优化问题,可以直接求解，很难说明得到的解是全局最优的。问题：如何转化为线性规划求解？5.1线性规划举例线性分式规划问题-LinearFractionalProgramming注意到目标函数是齐次的(分子-分母都是线性的),因此，对分子分母同乘以正数，目标函数的值是不变的。所以，可以引入辅助变量t，使得分母优化变量：()1TTtttdxdx固定，然后最大化分子max()..,nTTeqeqfstxcxxdxAxbAxb0t()TTtttcxcx,[,]nttzxz目标函数：,Ttzc5.1线性规划举例线性分式规划问题-LinearFractionalProgramming约束条件的转化：[,][,]1[,]10eqeqeqeqeqeqTTttttttttttzAxbAxb0Ab0zAxbAxb0Ab0zdxd5.1线性规划举例线性分式规划问题-LinearFractionalProgrammingmax()..,nTTeqeqfstxcxxdxAxbAxb1[,]max[,]..,[,][,],,1[,]10nTteqeqeqeqTTtsttttttzzczAbx0zAb0Abz0dzd5.2线性规划的标准形式1122max..,nTnncxcxcxstxeqeqcxAxbAxb求最大值的线性规划求最小值的线性规划1122min..,nTnncxcxcxstxeqeqcxAxbAxb121212mm,mmmmnneqeqAAbb是的矩阵是的矩阵是和维的列向量个不等式，个等式约束max..,nTstxeqeqeqeqcxAbAxbAbmin..,nTstxeqeqeqeqcxAbAxbAb5.3线性规划的性质max..,nTstxeqeqeqeqcxAbAxbAb满足所有约束条件的向量构成的集合是线性规划的可行域，最优解是否存在取决于可行域的性质●线性规划的可行域是凸集；●线性规划可能有解、无解或无界；●线性规划的最优解在凸多面体的顶点上；凸集凸集非凸集顶点D是凸集对D内任意两点x、y的连线上所有点都在集合内，即对任意的实数0≤a≤1，点ax＋(1－a)y在D中。可行域有界线性规划有解可行域空集线性规划无解可行域无界线性规划有解或无界5.3线性规划的对偶问题max..,,nTstxcxAxbx0min..,mTTTstyybyAcy0对偶优化问题A是一个mn的约束矩阵在nm的情况下，可以把低维空间中带有很多约束的线性规划转换为高维空间中具有很少约束的线性规划。通过这种转化可以使一些线性规划的求解和分析更容易。Axybc资源给定情况下最大化收益收益固定情况下花费资源最小化5.3线性规划的对偶问题max..,,nTstxcxAxbx0min..,mTTTstxybyAcy0对偶优化问题线性规划的有界可行是指目标函数在可行域上存在最大值(或最小值).可行域有界则线性规划必然有界可行；但线性规划有界可行不一定可行域一定有界。例如：2121212min2..,25210xxstxxxxx1x2x1225xx12210xx可行域无界，但最大值是10，最小值是5(I)(II)对偶定理：如果线性规划(I)是有界可行的，那么它的对偶规划(II)也是有界可行的，并且(I)的最大值与(II)的最小值相等。注：如果仅仅关心线性规划的最优函数值，求解线性规划和它的对偶中较简单的一个就可以，但最优点之间的对应关系不是简单直接的。平衡定理(EquilibriumTheorem):设和是(I)和(II)的可行解，它们是(I)和(II)的最优解如果对所有i,则；如果对所有j,则*x*y5.4线性规划求解软件[x,fval]=Linprog(f,A,b)min..,TfstxAxb[x,fval]=Linprog(f,A,b,Aeq,beq)eqmin..,TeqfstxAxbAxb[x,fval]=Linprog(f,A,b,Aeq,beq,LB,UB)eqmin..,TeqfstxAxbAxbLBxUB5.4线性规划求解软件[x,fval,exitflag]=Linprog(f,A,b,Aeq,beq,LB,UB)returnsanexitflagthatdescribestheexitconditionofLinprog.Possiblevaluesofexitflagandthecorrespondingexitconditionsare1LinprogconvergedtoasolutionX.成功，得到了全局最优解！0Maximumnumberofiterationsreached.迭代次数达到了上限！-2Nofeasiblepointfound.没有可行点(可行区域可能是空集）！-3Problemisunbounded.目标函数在可行域上无下界！-4NaNvalueencounteredduringexecutionofalgorithm.算法运行中溢出！-5Bothprimalanddualproblemsareinfeasible.原规划与对偶规划都不可行！-7Magnitudeofsearchdirectionbecametoosmall;nofurtherprogresscanbemade.Theproblemisill-posedorbadlyconditioned.搜索方向的幅度太小，算法无法继续运行（问题可能是病态的！)5.5二次