解： 表2 设x,为购买食 食品 最少 品B,的数量(j=1,2, 营养 Bi B2 Bn 需要量 A all a12 aln bi A2 a21 d22 a2n b2 Am aml am2 amn bm 单价 C1 min C2 Cn s.t. 24x,2b (i=1,2,…,m 0<x;<lj x20J=1,2.,n)
表 2 食品 最少 营养 B1 B2 … Bn 需要量 A1 a11 a12 … a1n b1 A2 a21 a22 … a2n b2 … … … … … … Am am1 am2 … amn bm 单 价 c1 c2 … cn 解 ： 设 xj 为购买食 品 Bj 的数量 ( j=1,2, …,n ) （i = 1,2,…,m） xj ≥0 （j = 1,2,…,n） 0≤ xj ≤l j 1 min n j j j z c x = = 1 . . n ij j i j s t a x b =
Note: 1、善于抓住关键因素 ,忽略对系统影响不大的因素； 2、可以把一个大系统合理地分解成个子系统处理。 三个基本要素： 1、决策变量 x≥0 2、约束条件 组决策变量的线性等式或不等式 3、目标函数一一决策变量的线性函数
三个基本要素： Note： 1、善于抓住关键因素，忽略对系统影响不大的因素； 2、可以把一个大系统合理地分解成 n 个子系统处理。 1、决策变量 xj≥0 2、约束条件 —— 一组决策变量的线性等式或不等式 3、目标函数 —— 决策变量的线性函数
2.1标准形式与图解法 线性规划问题的一般形式： min(ax）z=c+Cx2+… S.t. a1x1+a1zX3++a1mxn(或，≥）b, a2x1+a22x3+.十a2n≤（或-入2）b2 amX1+amX3+…十Amn≤（或-，≥）bm x,≥0=1,2，.，n》 其中a,b,、C(i=1,2,,m;j=1,2,,n）为已知 常数
min（max）z = c1 x1 + c2 x2 + … + cn xn s.t. a11x1+ a12x2+ … + a1n xn≤（或=，≥）b1 a21x1+ a22x2+ … + a2n xn ≤（或=，≥）b2 … … am1 x1 + am2 x2+ … + amnxn ≤（或=，≥）bm xj ≥ 0 （j = 1,2,…,n） 其中aij、bi、cj（i = 1,2,…,m；j = 1,2,…,n）为已知 常数 线性规划问题的一般形式： 2.1 标准形式与图解法
§2.1.1标准形式 特点： 线性规划问题的标准形式： 1、目标函数为极 min 9=Cx1+CX2t…+CXm 小化： 2、除决策变量的 S.t. aux1+a1xx2+ainn _bi 非负约束外，所有 a2x1+a2zx2+.十a2mYn =b2 的约束条件都是等 式，且右端常数均 amX1+am2X3+…十Amn=bm 为非负； x≥0=1,2，.，n) 3、所有决策变量 均非负。 b,≥0(1=1,2，，m）
线性规划问题的标准形式： min z = c1 x1 + c2 x2 + … + cn xn s.t. a11x1+ a12x2+ … + a1n xn = b1 a21x1+ a22x2+ … + a2n xn = b2 … … am1 x1+ am2 x2+ … + amnxn = bm xj ≥ 0 （j = 1,2,…,n） bi ≥ 0 （i = 1,2,…,m） 特点： 1、目标函数为极 小化； 2、除决策变量的 非负约束外，所有 的约束条件都是等 式，且右端常数均 为非负； 3、所有决策变量 均非负。 §2.1.1 标准形式
如何转化为标准形式？ 1、目标函数为求极大值，即为 maxz= cx, j=l 因为求maxz等价于求min(-z),令z=-z, 即化为： min=x xn+1≥0 松弛变量 2 约束条件为不等式 n ax,≤b Xn+l j=1 aux,≥b, 如何处理？
如何转化为标准形式？ 1、目标函数为求极大值，即为： max 1 。 n j j j z c x = = ' 1 min n j j j z c x = = − 因为求 max z 等价于求 min (-z)，令 z’ = - z， 即化为： 2、约束条件为不等式， = + + = n j ij j n bi a x x 1 1 = n j aij x j bi 1 = n j aij x j bi 1 xn+1 ≥ 0 松弛变量 如何处理？