不符合标准型的几个方面
：
⑴目标函数为 min z=c1x1+c2x2++cnxn 令z=-z ,变为 max z= -c1x1- c2x2- -cnxn ⑵约束条件为 a11x1+a12x2++a1nxn≤b1 加入非负变量xn+1，称为松弛变量，有 a11x1+a12x2++a1nxn+xn+1=b1 ⑶约束条件为 a11x1+a12x2++a1nxn≥b1 减去非负变量xn+1，称为剩余变量，有 a11x1+a12x2++a1nxn - xn+1=b1 ⑷变量xj无约束。 令xj= xj - xj，对模型中的进行变量代换。
图解法
max z 2 x1 3x2 x2 x1 2 x2 8 4 x1 16 4 x2 12
x2
x1 , x2 0
x1
x1 无穷多最优解
唯一最优解
线性规划问题如果有 最优解,则最优解一定在可 行域的边界上取得,特别地, 一定可在可行域的顶点上 取得.
无可行解
解无界
线性规划问题的标准型
b
• 把其系数列成数据表即单纯形表: amm+1„ amn bm xm 0 0 „ 0 σ j 0 0 „ 0 σ m+1„ σ n -z0
单纯形法(二)
按照单纯形法的思路求解线性规划问题, 要解决 三个技术问题:⑴给出第一个基本可行解; ⑵检验一个 基本可行解是否是最优解; ⑶转换到另一个基本可行 解. ⑴把线性规划问题变成标准型后, 观察是否每个 约束方程中都有独有的、系数为1的变量. 如果是,则 取这些变量作为基变量,便得到一个基本可行解; 否则, 就给没有这种变量的约束条件添加一个人工变量,同 时修改目标函数. (见例题)
研究对象
• 有一定的人力、财力、资源条件下，如 何合理安排使用，效益最高
• 某项任务确定后，如何安排人、财、物， 使之最省
线性规划问题及其数学模型
问题的提出(一)
例 某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品， 已知生产单位产品所需的设备台时和原料A、B的消 Ⅰ Ⅱ 耗量如下表。 该工厂每生产一件 产品Ⅰ可获利2元，每生产一件产 设 备 1 2 8 台时 品Ⅱ可获利3元，问应如何安排生 原料 A 4 0 16kg 原料 B 0 4 12kg 产计划能使该厂获利最多？
消去法把中心元素化成1, 同列的其他元素化
成0, 得到一个பைடு நூலகம்的单纯形表,也就得到一个新
的基本可行解.
单纯形法(三)
用单纯形法求解线性规划问题的具体步骤如下： ①找出初始可行基，确定初始基本可行解，建 立初始单纯形表；转②。 ②检验对应于非基变量的检验数σj。若σj≤0（xj 为非基变量）都成立，则当前单纯形表对应 的基本解就是最优解，停止计算；否则转③。 ③在所有σj>0中，若有一个σk对应的xk的系数 a'ik≤0 (i=1,2,…,m)，则此问题为无界解（无 解），停止计算；否则转④。
• 1947 •
DANTZIG 人员轮训 任务分配 美国科学院院士 “单纯形法”
• 1960 “最佳资源利用的经济计算” 康托洛维奇和库伯曼斯(Koopmans)因 对资源最优分配理论的贡献而获1975年 诺贝尔经济学奖。 • 60-70年代 计算机 50约束 100变 30000约束 3000000变量
线性规划
• 运筹学中应用最广泛的方法之一。
• 运筹学的最基本的方法之一，网络规划， 整数规划，目标规划和多目标规划都是 以线性规划为基础的。 • 解决稀缺资源最优分配的有效方法，使 付出的费用最小或获得的收益最大。
引 言
• 历史悠久
• 理论成熟 • 应用广泛
1939
KOHTOPOBUZ “生产组织与计 划中的 数学方法” “解乘数法”
• 冯•诺伊曼(Von Neuman)和摩根斯坦 (Morgenstern)1944年发表的 《对策论 与经济行为》涉及与线性规划等价的对 策问题及线性规划对偶理论 • 从1964年诺贝尔奖设经济学奖后，到 1992年28年间的32名获奖者中有13人 (40%)从事过与线性规划有关的研究工 作，其中比较著名的还有Simon， Samullson，Leontief，Arrow，Miller 等
⑵如果单纯形表最后一行中的σj都满足 σj≤0, 则 对应的基本可行解是最优解; 否则就不是最优解. σj称 为检验数.
⑶第一,确定换入变量. 在大于0的检验数中找最
大的为σk, 对应变量xk为换入变量. 第二,确定换出变量. 取 θ=min{bi/a‘ik|a’ik>0}=bl/a’lk, 对应的第l行的基 变量为换出变量. 第三, 旋转运算. 换入变量所在的行与换出变量 所在的列交叉点的元素称为中心元素,用高斯
•
为了便于单纯形法的实施，我们用单纯形表来描 述线性规划问题的一个基本可行解的情况。
不妨设x1,x2,…,xm组成一组基变量，且对应一个基本可行解。 用高斯消去法把等式约束和目标函数变形为
• x1 • •
+a'1m+1xm+1+…+a'1nxn=b'1 x2 +a'2m+1xm+1+…+a'2nxn=b'2 … ………………………
④根据 max（σj>0）=σk 确定xk为换入变 量；根据θ规则 θ＝min{b'i/a'ik｜1≤i≤m, a'ik>0}＝b'l/a'lk • 确定相应的换出变量，并得到中心元素 a'lk。转⑤。 • ⑤以a‘lk为枢轴元素进行转轴运算，得 到新的单纯形表。转②
• 用单纯行法求解线性规划问题后，应回答下 面几个问题： • ⑴是否解无界？上面的步骤已作出回答。 • ⑵是否无可行解？求解后，若人工变量 都已取0，则有可行解；否则，无可行解。 • ⑶唯一最优解还是无穷多最优解？在最 后的单纯形表中，若所有非基变量的检验数 都严格小于0，则为唯一最优解；若存在某个 非基变量的检验数等于0，则有无穷多最优解。
用Matlab实现线性规划问题
• 1.函数介绍： -> lp 线性规划函数 x=lp(f,A,b) 解如下形式线性规划问题。 Min f x x Subject to: Ax≤b
->x=lp(f,A,b,vlb,vub) 参数vlb、vub给出设计变量的上下边界 约束，即vlb ≤x ≤vub ->x=lp(f,A,b,vlb,vub,x0),初值为x0。 -> x=lp(f,A,b,vlb,vub,x0,N),指出由A,b定义 的约束中前N个为等式约束。 -> x=lp(f,A,b,vlb,vub,x0,N，DISPLAY),控 制警告信息显示，当DISPLAY=-1时， 不显示警告信息。
解：经过次变换化为标准型： -〉Matlab程序如下： c=[-6,-4]; A=[2,3;4,2]; B=[100,120]; Vlb=[0,0]; Vub=[]; [x,lam]=lp(c,a,b,vlb,vub)
• 例2：某车间生产A和B两种产品。为了生 产A和B，所需的原料分别为2个和3个单 位，而所需的工时分别为4个和2个单位， 现在可以应用的原料为100个单位， 工时为120个单位，每生产一台A和B分别 可获得利润6元和4元，应当安排生产A和 B各多少台，才能获得最大的利润？ [分析]此问题的数学表达式为，设该车间 应安排生产的A,B的数量分别为x1台和x2 台，那么问题是求解最大值函数 z=6x1+4x2.
原材料方面：2x1+3x2≤100 工时方面： 4x1+2x2 ≤120 非负条件： x1,x2≥0 解：即
Max z=6x1+4x2 Sub.to 2x1+3x2 ≤100 4x1+2x2 ≤120 x1,x2 ≥0 Min z=-6x1-4x2 Sub.to 2x1+3x2 ≤100 4x1+2x2 ≤120 x1,x2 ≥0
• 线性规划问题的标准型 • max z=c1x1+c2x2++cnxn • a11x1+a12x2++a1nxn=b1 • a21x1+a22x2++a2nxn=b2 • • am1x1+am2x2++amnxn=bm • x1, x2, , xn≥0 • 其中，bi≥0 (i=1,2,,m)
设工厂1和工厂2 每天分别处理污水x1 和x2万m3，则有： Min z=1000x1+800x2 (2-x1)/500 ≤0.002 [0.8(2-x1)+1.4-x2]/700 ≤0.002 x1≤2, x2≤1.4
x1, x2≥0
问题的提出(三)
以上两例都有一些共同的 特征： ⑴用一组变量表示某个方 案，一般这些变量取值 是非负的。 ⑵存在一定的约束条件， 可以用线性等式或线性 不等式来表示。 ⑶都有一个要达到的目标， 可以用决策变量的线性 函数来表示。
满足以上条件的数学 模型称为线性规划模型。 线性规划模型的一般形式 如下：
max(min) z c1 x1 c2 x2 cn xn a11x1 a12 x2 a1n xn (, )b1 a21x1 a22 x2 a2 n xn (, )b2 am1 x1 am 2 x2 amn xn (, )bm x1 , x2 , xn 0
xB x1 x2 „ xm xm+1 „ xn
•
-z
• x1 x +a' 0 x a1m+1„ a1n b1 =b' 1 0 „ m mm+1 m+1+…+a'mnxn m x2 0 1 „ 0 a2m+1„ a2n b2 +σ „„„„„„„„„„ ┇ m+1xm+1+…+σnxn= -z0 ┇