第1章绪论线性规划数学模型.ppt

第一节 线性规划问题及数学模型 剩余量：线性规划中，一个大于等于约束条件中超过资源或能力最底限的部分称之为剩余量。2 xl + x2≥400，假如最优解为（150,110）那么剩余量就为10。 两个概念 松弛量：线性规划中，小于等于约束条件中未被使用的资源或能力的值成为松弛量。 xl+ x2≤300，假如最优解为 （150,140）那么本约束的松弛量就为10。 例1：将以下线性规划问题转化为标准形式? minf = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 ≤15.7 4.1 x1 + 3.3 x3 ≥8.9 x1 + x2 + x3 = 38 x1 , x2 , x3 ≥ 0? 第一节 线性规划问题及数学模型 解：首先,将目标函数转换成极大化： 令 z= -f = -3.6x1+5.2x2-1.8x3 第一节 线性规划问题及数学模型 其次考虑约束，有2个不等式约束，引进松弛变量x4和剩余变量x5，我们可以得到以下标准形式的线性规划问题： max z = - 3.6 x1 + 5.2 x2 - 1.8 x3 s.t. 2.3x1+5.2x2-6.1x3+x4= 15.7 4.1x1+3.3x3-x5= 8.9 x1+x2+x3= 38 x1 ,x2 ,x3 ,x4 ,x5 ≥ 0 第一节 线性规划问题及数学模型 （3）右端项有负值的问题： 在标准形式中，要求右端项必须每一个分量非负。 当某一个右端项系数为负时，如 bi0，则把该等式约束两端同时乘以-1，得到： -ai1 x1-ai2 x2- … -ain xn = -bi （4） 变量无符号限制的问题： 在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj = xj’- xj” (xj’≥0，xj”≥0) 或 xj =-xj’ (xj’≥0) 第一节 线性规划问题及数学模型 第一节 线性规划问题及数学模型 例2：将以下线性规划问题转化为标准形式 minf= -3 x1 + 5 x2 + 8 x3 - 7 x4 s.t. 2 x1 - 3 x2 + 5 x3 + 6 x4 ≤ 28 4 x1 + 2 x2 + 3 x3 - 9 x4 ≥ 39 6 x2 + 2 x3 + 3 x4 ≤ - 58 x1 , x3 , x4 ≥ 0 第一节 线性规划问题及数学模型 解：首先，将目标函数转换成极大化 令 z = -f = 3x1–5x2–8x3+7x4 ； 其次考虑约束，有3个不等式约束，引进松弛变量x5 ,x7和剩余变量x6 ； 由于x2无非负限制，可令x2=x2’-x2”,其中 x2’≥0，x2”≥0 ； 由于第3个约束右端项系数为-58，于是把该式两端乘以-1 。 于是，我们可以得到以下标准形式的线性规划问题： 第一节 线性规划问题及数学模型 max z = 3x1–5x2’+5x2”–8x3 +7x4 s.t. 2x1–3x2’+3x2”+5x3+6x4+x5= 28 4x1+2x2’-2x2”+3x3-9x4-x6= 39 -6x2’+6x2”-2x3-3x4-x7 = 58 x1 ,x2’,x2”,x3 ,x4 ,x5 ,x6 ,x7 ≥ 0 ? 第一节 线性规划问题及数学模型 总结：把一般的LP化成标准型的过程： 1 目标标准化 min Z 等价于 max ( - Z ) max Z’=-∑cjxj 2 化约束为等式 加松弛变量、减剩余变量 3 右端非负 4 变量非负化 做变换 或 1、 P43：1.2（1）；P45：1.13；选作1.15、1.17； 2、复习线性代数相关知识 本次作业 第一节 线性规划问题及数学模型 * * * * * * * * 北京联合大学 自动化学院 耿钰 课程基本介绍 夫运筹帷幄之中，决胜千里之外。 ——《史记·高祖本纪》 由来：西汉初年，天下已定，汉高祖刘邦在洛阳南宫举行盛大的宴会，喝了几轮酒后，他向群臣提出一个问题：“我为什么会取得胜利？项羽为什么会失败？”高起、王陵认为高祖派有才能的人攻占城池与战略要地，给立大功的人加官奉爵，所以能成大事业。而项羽恰恰相