化为标准型: minF(X)=-40x1-80x2 X∈D C PS s t +x2=9 x2+x4=7 2x1+3x2+xx=24 12 ≥0 6
6 , ,..., 0 2 3 24 7 9 min ( ) 40 80 1 2 5 1 2 5 2 4 1 3 5 1 2 + + = + = + = = − − x x x x x x x x x x X D R F X x x s.t. 化为标准型:
)线性规划的基本概念 1.线性规划的图解 max F(X)=40x,+80x (1.5,7)F*=620 X∈DcR St.x1≤9 2x1+3x,<24 x1,x2≥0 0
7 三）线性规划的基本概念 , 0 2 3 24 7 9 max ( ) 40 80 1 2 1 2 2 1 2 1 2 + = + x x x x x x X D R F X x x s.t. 1.线性规划的图解 x2 x1 0 F=0 (1.5,7) F*=620
2.线性规划的基本概念 1)可行解 1.5,7)F*=620 满足约束条件及非负条件的解。P x,=0 (D内及其边界上的解) x2=0 2)基本解 使n-m个变量等于0,解约束方程 组(共有m个约束方程)所得的解。=9 基本解对应于约束边界的交点.0 x=0 F=0 3)基本可行解 mIn F(X)=-40x1-80x2 可行域中的基本解(即D的顶点)。x=D=R 4)基本变量与非基本变量 S.t. 1+x3=9 预先取为零值的nm个变量为非x2+x=7 基本变量,其余m个为基本变量。 2x1+3x,+x=24 8
8 2. 线性规划的基本概念 1）可行解 —满足约束条件及非负条件的解。 （D内及其边界上的解） 2）基本解 —使n-m个变量等于0，解约束方程 组(共有m个约束方程)所得的解。 基本解对应于约束边界的交点. 3）基本可行解 —可行域中的基本解（即D的顶点）。 4）基本变量与非基本变量 预先取为零值的n-m个变量为非 基本变量，其余m个为基本变量。 x3 = 0 x2 x1 0 F=0 (1.5,7) F*=-620 x4 = 0 x5 = 0 x1 = 0 x2 = 0 , ,..., 0 2 3 24 7 9 min ( ) 40 80 1 2 5 1 2 5 2 4 1 3 5 1 2 + + = + = + = = − − x x x x x x x x x x X D R F X x x s.t
四)线性规划的基本性质 1)可行域D为凸集,每个基本可行解对应于D上的 一个顶点; 2)只要可行域存在且封闭,则起码有一个基本可 行解为最优点; *i)若最优点所在的边界线与等值线平行,则该 边界线上的点均为最优点; i)若可行域不封闭,则可能有无界解。 3)最优点可在D的顶点中寻找
9 四）线性规划的基本性质 1）可行域D为凸集，每个基本可行解对应于D上的 一个顶点； 2）只要可行域存在且封闭，则起码有一个基本可 行解为最优点； *ⅰ）若最优点所在的边界线与等值线平行，则该 边界线上的点均为最优点； ⅱ）若可行域不封闭，则可能有无界解。 3)最优点可在D的顶点中寻找
二、求解线性规划的单纯形法 一)基本思路 先取D的一个顶点作为初始点,由此出发朝 可使目标函数降低最快的方向依次经过一系 列的基本可行解,直至达到最优解 *1)需获得一个初始基本可行解; 2)每次只更换一个非基本变量 3)保证下降性和可行性
10 二. 求解线性规划的单纯形法 一)基本思路 先取D的一个顶点作为初始点,由此出发朝 可使目标函数降低最快的方向依次经过一系 列的基本可行解,直至达到最优解. *1)需获得一个初始基本可行解; 2)每次只更换一个非基本变量; 3)保证下降性和可行性