本章要求
理解线性规划模型的可行解、基本解、基本可行解、基本最优解、最优解等概念和这些概念之间的关系；
熟悉单纯形法的原理和求解线性规划模型的基本思路；
掌握单纯形法的求解线性规划模型的步骤；能够用单纯形表法求出线性规划模型的基本最优解；
会使用计算机软件求解线性规划模型
第3章线性规划模型的单纯形法
单纯形法(SimplexMethod)是目前求解一般线形规划模型最常用的一种方法，本章主要介绍单纯形表方法的原理和求解一般线性规划问题的步骤。
1.线性规划模型的一般形式为：
max(或min)z=C?x?+…+Cnxn
e+ax,20ksn(或=,2)b,=12.,m
其中，a;,b;,c;是已知数，x;(j=1,2…,n)是待决策的变量C?x?+…+Cnxn称为目标函数(Objectivefunction),c;称为价值系数(CostCoefficient),向量C=(c?,C?,…,Cn)称为价值向量
(3.1)
列向量b=(b?,…,bm)称为右端向量RHS(Right-hand-sidevector),
a?x?+ai?X?+…+ainxn≤(或=,≥)b和x;,x;?,…x;≥0称为约束条件(Subjectto)。x;,≥0(l=1,2,…,k)称为变量的非负约束条件。
称为约束矩阵(Constraintsmatrix),
由系数a组成的矩阵
3.1线性规划数学模型的结构及特征
其余的变量可取正值、负值、或零值，称这样的变量为符号
无限制变量或自由变量。线性规划模型的特征是：一组决策变量
x;(j=1,2…,n)。一组约束条件和一个目标函数，目标函数和约束条件都是线性的。
3.1线性规划数学模型的结构及特征
在线性规划的一般模型(3.1)中，目标函数有最大化和最小化；约束条件有大于等于、小于等于、等于形式；决策变量有非负约束和无非负约束。
这就导致了线性规划模型的多样性，多样性给讨论线性规划模型求解带来了不便，因此定义一个标准形式的线性规划模型，
将其它形式的线性规划模型都转换成标准形式，这样只讨论标准
形式的线性规划模型的求解方法。
(3.2)
标准形式模型特征为：约束条件为线性等式；所有变量全部
大于等于0;右端常数项大于等于0;目标函数求最大值。
1.标准形式定义为
maxz=C?x?+…+Cnxn
3.2线性规划问题的标准形式
标准形式几种等价的形式
简写形式
(3.3)
3.2线性规划问题的标准形式
矩阵形式
maxz=CX
(3.4)
列向量形式
maxz=CX
(3.5)
3.2线性规划问题的标准形式
其中
其中
A,b,C的定义如3.1中。
2.一般形式的线性规划模型变换为标准形式
(1)目标函数的转换。
如果原问题是求最小值minz=CX,则等价地转换为
maxz1=-CX。
(2)约束条件的转换。
对于,引进非负变量x,用
∑a,x,+x,.;=b;,x;≥0代替这个不等式约束，其中变量x
j=1
为松弛变量(Slack)。
对于,引进非负变量xn+i,用
,xn+i≥0代替这个不等式约束，其中变量xn+为剩余变量(Surplus)。
(3)变量的非负约束的转换。若x,无约束的变量，则令xk=x-x且xk,x≥0。
3.2线性规划问题的标准形式
例3-1将一般线性规划模型转化为标准型
minz=-x?+2x2-3x?
(3.5)(3.6)
3.2线性规划问题的标准形式
解令x?=x?一x?,且x?,x?≥0,约束不等式(3.5)加入松弛
变量x?,约束不等式(3.6)加入剩余变量x?,这时标准形式为maxz=x?-2x?+3x?-3x?+0x?+0x?
3.2线性规划问题的标准形式
例3-2将一般线性规划模型转化为标准型minz=x?+2x?+3x?
3.2线性规划问题的标准形式
解令x1=-x?,X?=x3-x3,x?=x?-2,其中
x,x2,x3,x3≥0,2≤x?≤6等价于x?≥0,且x?≤6-2=4,
将x?≤4作为一个约束条件加入到约束方程组中，并引入松弛变量x?,x?和剩余变量x?,就得到了标准形式
maxz=x′-2x2-4-3x3+3x