值时，得
BXB b
由于B是满秩矩阵，故 B 是1 惟一存在的，于是
XB B1b
这样由XB和零组成的解称为基本解；满足约束条件的 解称为可行解；满足约束条件的基本解称为基本可行 解；对应基本可行解的基称为可行基；使目标函数达 到最优值的可行解称为最优可行解，如果这样的可行 解又是基本的，则称为最优基本可行解。
10.1 线性规划问题
例5 某线性规划问题的约束方程为

2
x1 x1

x3 4x

2
1
1
讨论线性规划问题的基本概念。
解：不难验证A与 A 的秩是相等的，都等于2， 而且A的全部二阶方阵为3个，即
B 1 1 20 4 ， B 2 1 21 0 ， B 3 0 41 0
于是问题就成为求出未知量，使它们满足前面 的方程组，且使函数S取最小值。
10.1 线性规划问题
共同的特点：就是问题的条件都可以用一 组线性等式或线性不等式来表达，并且取最大 (小)值的目标函数也是线性函数．具有这样特点 的问题便是线性规划问题，线性规划问题数学
模型的一般形式为：
max(min)S c1x1 c2 x2 cn xn
(3) 两个变量的线性规划问题的图解法,及图上作业法 解平衡型的运输问题；
第十章 线性规划
(4)性规划问题单纯形表的结构,单纯形法及改进的单 纯形法求解线性规划问题；
(5)线性规划问题无可行解、有可行解而无最优解、有 惟一最优解、有无穷多最优解等情况在单纯形方法 中的反映；
(6)线性规划在生产实践、车辆调度等问题上的应用；
例1 设某食品厂生产甲乙两种产品，生产1t 甲产品需要3个工日和10t小麦，可得盈利8千元； 生产1t乙产品需要4个工日和8t小麦，可得盈利 9千元。该食品厂一个月只能出300个工日，小 麦一月只能进700t，那么该厂应如何安排生产， 才能在现有的条件下获得最大的盈利？
10.1 线性规划问题
解：设甲、乙两种产品各生产x1，x2t，由于该 厂一个月只能出300个工日，所以
三个方阵全是满秩的，故都是线性规划的基。
10.1 线性规划问题
(1)对应于基B1，方程组的等价形式为
1 2
04xx1210x311；
D10，XBxx12，x1，x2是基变量，XDx3， x3
是非基变量，若令非基变量取0值，则有
(7) 表上作业法解平衡型运输问题的方法。
2．教学重点与难点 （1）重点
第十章 线性规划
熟练掌握用单纯形法解线性规划问题； “图解法”求解含两个变量的线性规划问题。
（2）Байду номын сангаас点
线性规划问题的概念、数学模型的建立； 图上作业法(和表上作业法)求解运输型问题。
第十章 线性规划
10.1 线性规划问题
10.1.1 数学模型

X 0
的解、可行解、基本解、基本可行解、最优
可行解、最优基本可行解系统表示如下：
10.1 线性规划问题
解 （满足AX b）
基本解（X B B1b, X D 0） (若X B的分量有零值时， 称为退化基本解)
基本可行解 （X B 0）
非基本可行解 （XB有负值）
最优基本可行解 （满足基本可行解条件） 且使CX取最大值
第十章 线性规划
10.1 线性规划问题 10.2 图解法与运输问题 10.3 单纯形法 10.4 应用与实践 10.5 拓展与提高
第十章 线性规划
一 知识结构框图
第十章 线性规划
二 教学基本要求和重点、难点
1．教学基本要求
(1) 线性规划问题的数学模型的建立及将数学模型化 为标准形式的方法；
(2) 线性规划问题的基、基变量、非基变量、可行 解、基本可行解、最优解的概念；
并且使S取得最大值，即
mS a x 8x19x2
10.1 线性规划问题
例2 在设计制造某一种产品时，需要用 300cm长的圆钢，截成长度分别为90cm和70cm 的两种坯料，要求截出长90cm的坯料1000根， 70cm的坯料2000根，那么应该如何截取，才能 使所用的圆钢最少？
10.1 线性规划问题
定理10.1 对于标准化模型问题
max S CX
AX b (b 0)

X 0
其中A为m行n列矩阵，矩阵的秩为。
(1)若存在一个可行解，则必存在一个基本可行解；
(2)若存在一个最优解，则必存在一个最优基本可行解。
10.1 线性规划问题
例4 将例1给出的线性规划问题数学模型 化为标准形式。
130xx1148xx22

300 700
xi 0, (i 1, 2)
解：引入松弛变量x30,x4 0，则标准形式
数学模型 max S 8 x1 9 x 2
130xx11

xi 0 , (i 1, 2 , 3 n )
10.1 线性规划问题
对于非标准化的模型都可以进行某种变换 使之标准化。具体方法如下： (1)引入松弛变量
如果约束条件不标准，例如第j个方程为：
a j1 x 1 a j2 x 2 a jn x n b j 时，则引进变量 xnj 0 ，使
如果A的全部m阶满秩方阵的集合记为{B}， 对任一B，约束方程可写为
B ,D X b 或 B X B D X D b
称B是该线性规划问题的一个基，对应于B 的 XB的每一分量称为基变量； XD的每一分量称 为非基变量。
10.1 线性规划问题
为了简化，令XD=0，即XD的每一分量令其取零
10.1 线性规划问题
10.1.2 线性规划问题的标准形式
m ax S c1x1 c2 x2 cn xn
a11 x1 a12 x2

a 21 x1

a22 x2


a1n x n b1 a2n xn b2

a
m
1
x1

am2
x2

amn xn bm
x2
x3)T(1 2
0
1)T 2
10.1 线性规划问题
(3)同理对应于基
0 B3 4
1 0
的基本解为
X(x1
x2
x3)T(0
1 4
1 )T
而且是基本可行解。
10.1 线性规划问题
为了便于理解线性规划问题的基本概念，
现将线性规划问题
max S CX
AX b (b 0)
3x14x2300
又由于小麦一个月只能进700t，所以
10x18x2 700
如果设总的盈利为S，则
S8x19x2
10.1 线性规划问题
本题目的就是求出一组变量x1，x2的值， 使它们满足不等式组
130xx1148xx22

300 700
xi 0, (i 1, 2)
3x3

4x4

2000
xi 0, (i 1, 2,3, 4)
并且使S取得最小值，即
mS ix n 1 x 2 x 3 x 4
10.1 线性规划问题
例3 一批工业物资，由三个仓库调运到 三个工厂，其存需数量如表10-2所示，单位 运价如表10-3所示，问应怎样调运才能使总 的运价最省？
a12
a1n
x1 b1
a22
a2n，X
x2,bb2



am2
amn
xn bm
C()
10.1 线性规划问题
假定在方程组有无穷多个解(m<n)时，最终 目的是从这无穷多个解中选出使
S CX
最大的解，称为最优解。
10.1 线性规划问题
4x2 8x2

x3 x4

300 700
， ．
xi 0(i 1,2,3,4)
10.1 线性规划问题
10.1.3 线性规划问题的基本概念
线性规划问题的数学模型用矩阵形式可表示为
max S CX
a11 Aa21
am1
AX b (b 0)

X 0
a11x1 a12 x2

a21x1 a22 x2

a1n xn b1( b1, b1) a2n xn b2 ( b2 , b2 )
am1x1 am2 x2 amn xn bm ( bm , bm )

xi 0, (i 1, 2,3 n)
10.1 线性规划问题
解：调运矩阵为
B1 B2 B3
A1 x11 x12 x13
A2

x
21
x 22
x
23

A3 x 31 x 32 x 33
其中xij表示从仓库Ai到工厂Bj调运物资的数量， 单位t，
10.1 线性规划问题
x11 x21 x31 2 0
10.1 线性规划问题
(3)目标函数的标准化 如果一模型的目标函数求值不标准，即求最
小值 m in S c 1 x 1 c 2 x 2 c n x n ，则令
S'S
那么问题转化成求
m a x S ' c 1 x 1 c 2 x 2 c n x n
(4)如果约束条件中，某个方程的常数项为 负值时，则对其等号两端同乘以(-1)，使常数项 化为正数，从而使之标准化。
一般基本可行解 （只满足X B 0条件）
非基本解 （不是由 X B B 1b, X D 0构成）
可行解 （满足AX b,