当前位置: 首页 > >

最新文档-第2章线性规划-PPT精品文档

发布时间:

第2章 线性规划 2.1 2.2 2.3 2.4 问题的提出 线性规划的数学模型 图解法 单纯形法 2.1 问题的提出 【例1-1】、 【例1-2】 【例2-1】某商场决定:营业员每周连续工作5天后连续休息2天, 轮流休息。根据统计,商场每天需要的营业员如表1-2所示。 表1-2 营业员需要量统计表 星期 一 二 三 四 需要人数 300 300 350 星期 五 六 日 需要人数 480 600 550 400 商场人力资源部应如何安排每天的*嗳耸股坛∽艿挠翟 最少。 【解】 设xj(j=1,2,…,7)为休息2天后星期一到星期日开始* 的营业员,则这个问题的线性规划模型为 min Z ? x 1 ? x 2 ? x 3 ? x 4 ? x 5 ? x 6 ? x 7 ? x1 ?x ? 1 ? x1 ? ? x1 ? ? x1 ?x2 ? ?x3 ?x ? j ? x 4 ? x 5 ? x 6 ? x 7 ? 300 ? x 2 ? x 5 ? x 6 ? x 7 ? 300 ? x 2 ? x 3 ? x 6 ? x 7 ? 350 ? x 2 ? x 3 ? x 4 ? x 7 ? 400 ? x 2 ? x 3 ? x 4 ? x 5 ? 480 ? x 3 ? x 4 ? x 5 ? x 6 ? 600 ? x 4 ? x 5 ? x 6 ? x 7 ? 550 ? 0 , j ? 1, 2 , ? ,7 星 期 一 二 三 四 需要 人数 300 300 350 400 星 期 五 六 日 需要 人数 480 600 550 最优解: 1 x1 2 x2 3 x3 0 c1 67 c2 146 c3 404 >= 301 >= 350 >= 300 300 350 104 1 0 4 x4 5 x5 6 x6 170 c4 97 c5 120 c6 400 >= 480 >= 600 >= 400 480 600 0 0 0 7 x7 17 c7 550 >= 550 0 Z=617(人) 2.2 线性规划的数学模型 一般地,假设线性规划数学模型中,有m个约束,有n个决策变量 xj, j=1,2…,n,目标函数的变量系数用cj表示, cj称为价值系数。约 束条件的变量系数用 aij 表示, aij 称为工艺系数。约束条件右端的 常数用bi表示,bi称为资源限量。则线性规划数学模型的一般表达 式可写成 max(min) Z ? c1 x1 ? c2 x2 ? ? cn xn ? a11 x 1 ? a12 x2 ? ? a1n xn ? (或 ? , ? )b1 ? a x ? a x ? ? a x ? (或 ? , ? )b 2n n 2 ? 21 1 22 2 ? ? ? a x ? a x ? ? a x ? (或 ? , ? ) b mn n m ? m1 1 m 2 2 ? ? x j ? 0, j ? 1, 2, , n 为了书写方便,上式也可写成: max(min) Z ? ? c j x j j ?1 n ? n ?? aij x j ? (或 ?, ?)bi ? j ?1 ? x ? 0, j ? 1, 2, , n ? j i ? 1, 2, ,m 在实际中一般xj≥0,但有时xj≤0或xj无符号限制。 线性规划的数学模型由 决策变量 Decision variables 目标函数Objective function 及约束条件Constraints 构成。称为三个要素。 怎样辨别一个模型是线性规划模型? ?其特征是: ?1.解决问题的目标函数是多个决策变量的 线性函数,通常是求最大值或 最小值; ?2.解决问题的约束条件是一组多个决策变量 的线性不等式或等式。 2.3 线性规划的图解法 对于只有两个决策变量的线性规划问题,可以在*面直角坐标 系上作图表示线性规划问题的有关概念,并求解。 图解法的步骤: 1.求可行解集合。分别求出满足每个约束包括变量非负要求的 区域,其交集就是可行解集合,或称为可行域; 2.绘制目标函数图形。先过原点作一条矢量指向点(c1,c2),矢 量的方向就是目标函数增加的方向,称为梯度方向,再作一条 与矢量垂直的直线,这条直线就是目标函数图形; 3.求最优解。依据目标函数求最大或最小移动目标函数直线, 直线与可行域顶点相交的对应坐标就是最优解。 一般地,将目标函数直线放在可行域中,求最大值时直线 沿着矢量方向移动,求最小值时沿着矢量的反方向移动。 x2 40 a x Z ? 3 0 0 x ? 4 0 0 x 例2-2 m 1 2 2 x1 ? x 2 ? 40 2 x x 40 1? 2? x1 ? 1 . 5 x 2 ? 30 x1 ? 0 , x 2 ? 0 最优解X=(15,10) 最优值Z=8500 30 x 1 . 5 x 30 1? 2? (15,10) 20 10 (300,400) O 10 20 30 40 x1 x2 例2-3 6 ? 3 x1 ? x 2 ? 6 ?x ? x ? 4 ? 1 2 ? ? x1 ? 3 x 2 ? 6 ? ? x1 ? 0、 x 2 ? 0 最优解X=(3,1) 最优值Z=5 min Z=x1+2x2 4 2 (1,2) (3,1) 2 4 6 x1 x2 例2-4 6 ? 3 x1 ? x 2 ? 6 ?x ? x ? 4 ? 1 2 ? ? x1 ? 3 x 2 ? 6 ? ? x1 ? 0、 x 2 ? 0 有无穷多个最优解 即具有多重解,通解为 min Z=5x1+5x2 4 X(1)=(1,3) ( 1 ) ( 2 ) 0≤α≤1 X ? ? X ? ( 1 ? ? ) X , 2 (5,5) X(2)=(



友情链接: