211线性规划标准形式与基本定理 LP标准形: min Cx+c2x2+…+cnxn s t a1X+…+ax 12 b,i=1, LP向量形式: min cx s t Ax=b x≥0 其中A∈Rm",c,x∈R",b∈R" 约定:x,为决策变量,c,为费用(价格)系数,c′x为 目标函数,a为技术系数,b为右端项 ◎2007 Fang Weiguo School of economics and management
© 2007 Fang Weiguo School of Economics and Management
211线性规划标准形式与基本定理 各种形式的线性规划都可以化为标准形: (1) max cx→min(c)x i)a1x+a2x2+…+anxn≤b→>(引入松弛变量) a1x+a12x2+…+amxn+x}=b,x}≥0 i)anx1+a2x2+…+anxn≥b-→(引入剩余变量) 1x1+a12x2+…+anxn-x’=b,x}≥0 i)x,无非负限制,令x=yy",y≥0,y"≥0 (v)x1≥b(h,≠0),令y=x-h,y1≥0(平移变换) ◎2007 Fang Weiguo School of economics and management
© 2007 Fang Weiguo School of Economics and Management
211线性规划标准形式与基本定理 例 max+x min st.2x1+3x2≤6,+ ≥0 7x,≥4 4 4 ≥0 2 3 ≥0 令x2=y2-y2",y2≥0,y2"≥0 标准形:min-x1-y2+y2 st.2x1+3y2-3y2"+x3=6, x1+7y2-7 x1≥0,y2≥0,y2"≥20,x3≥0,x4≥0 ◎2007 Fang Weiguo School of economics and management
© 2007 Fang Weiguo School of Economics and Management
211线性规划标准形式与基本定理 图解法 例max2x1+5 st.x1+2x,≤8 x1≤4 2S3 4 x1≥0,x2≥0 唯一最优解(2,3) C 2007 Fang Weiguo School of economics and management
© 2007 Fang Weiguo School of Economics and Management
211线性规划标准形式与基本定理 max x+2x, St.x1+2x,≤8 x1≤4 x,≤3 x1≥0,x200 有无穷个最优解 C 2007 Fang Weiguo School of economics and management
© 2007 Fang Weiguo School of Economics and Management