变量xij与教师 i 以及课程 j 的关系如下：
i j 语文 数学 物理 化学
张 王
李 赵
x11 x21
x31 x41
x12 x22
x32 x42
x13 x23
x33 x43
x14 x24
x34 x44
max z= 92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24 +83x31+90x32+74x33+65x34+93x41+61x42+83x43+75x44 s.t. x11+x12+x13+x14=1 （1） x21+x22+x23+x24=1 （2） x31+x32+x33+x34=1 （3） x41+x42+x43+x44=1 （4） x11+x21+x31+x41=1 （5） x12+x22+x32+x42=1 （6） x13+x23+x33+x43=1 （7） x14+x24+x34+x44=1 （8） xij=0, 1 这个问题的变量只能取值0或1，这样的线性规划问题成为0－1规划。
min( z ) 2 x1 3 x2
x1 2 x2 8 4 x 16 1 s .t . 4 x2 12 x1 0, x2 0

MATLAB求解线性规划问题的命令
命令函数 linprog()
命令格式
⑴X=linprog(f,A,b)
求解LP问题
min f X
eq
⑵[X,fval]=linprog(f,A,b,Aeq,Beq,LB,UB)
求解LP问题
min f X
一般的指派问题线性规划模型如下： 设：
0 第i个人不从事第 j项任务 x ij 1 第i个人被指派完成第 j项任务
得到以下的线性规划模型：
min(max) z
n
c x
i 1 j 1 ij
n
n
ij ij
s.t.
x x
j1 i 1 n
1
j 1,2,, n
ij
1 i 1,2,, n

函数说明
(6)线性规划问题没有可行解时,系统提示 Warning: The constraints are overly stringent;there is no feasible solution.
如果优化成功,系统将会提示: Optimization terminated successfully

函数说明
(4)返回值output有3个分量，iterations表示优化过程 的叠代次数，cgiterations表示PCG叠代次数， algorithm表示优化采用的运算规则。 (5)返回值lambda有4个分量，ineqlin是线性不等式约 束条件， eqlin是线性等式约束条件，upper是变量 的上界约束条件， lower是变量的下界约会条件。 它们的返回值分别表示相应的约束条件在优化过程 中是否有效，本例中可以看到，三个不等式约束中 的后两个是有效的。
可行解（feasible solution）
使得约束条件成立的决策变量的一组值
可行域（feasible region）
全体可行解组成的集合（经常记为S）
最优解（optimal solution）
可行域中使目标函数达到所需最大或最小的可行解
3、用MATLAB软件求解线性规划问题

线性规划问题的求解方法包括图解法、单纯 形法、矩阵法等. 但在决策变量个数较多，求解过程都比较复 杂时，用MATLAB软件求解线性规划问题则 比较简单.
案例二（生产计划的问题）某工厂在计划期内要安 排生产Ⅰ、Ⅱ的两种产品，已知生产单位产品所需 的设备台时，A、B两种原材料的消耗以及每件产品 可获的利润如下表所示。问应如何安排计划使该工 厂获利最多？
Ⅰ
设备 原材料A 原材料B 单位产品利润 （万元） 1 4 0 2
Ⅱ
2 0 4 3
资源限量
8(台时) 16(kg) 12(kg)
x ij 0,1
由以上3个例子，我们可以归纳出线性规划问题的一般形式：
max(min) z c1x1 c 2 x 2 c jx j c n x n s.t. a11x1 a12 x 2 a1 jx j a1n x n (, )b1 a 21x1 a 22 x 2 a 2 jx j a 2n x n (, )b 2 a m1x1 a m 2 x 2 a mjx j a mn x n (, )b m x1 x2 xj xn 0
设备能 每件产品占用的 力 机时数（小时/ 产品甲 产品乙 产品丙 产品丁 （小时 件） ） 设备A 设备B 设备C 1.5 1.0 1.5 1.0 5.0 3.0 2.4 1.0 3.5 1.0 3.5 1.0 2000 8000 5000
利润（元/件）
5.24
7.30
8.34
4.18
设变量xi为第i种产品的生产件数（i＝1，2，3，4）， 目标函数z为相应的生产计划可以获得的总利润。在加工 时间以及利润与产品产量成线性关系的假设下，可以建立 如下的线性规划模型：
线性规划的不等式约束条件 线性规划的等式约束条件
A X b
Aeq X Beq

函数说明
(2)运用linprog()命令时，系统默认为它的各种 linprog(f,A,b, Aeq, Beq,LB,UB,X0,options)都存 在，且按固定顺序排列。本例中，在存在约束LB的 情况下，它后面的参数没给出，可以不声明，但是 LB前面的参数即使没给出（例如等式约束条件）也 要用空矩阵“[ ]”的方式给出声明，不能省略。 (3)返回值exitflag有3种情况： 表示优化结果已经超过函数的估计值 或者已声明的最大叠代次数； exitflag=1 表示优化过程中变量收敛于解X。 exitflag= －1 表示优化结果不收敛。 exitflag=0

函数说明(1) f 目标函数的系数组成的向量 X 目标函数取得极值的决策变量组成的列向量 A 矩阵 线性规划的不等式约束条件 A X b b 向量

Aeq 矩阵 线性规划的等式约束条件 Aeq X Beq Beq 向量
LB
UB
变量的下界约束
变量的上界约束
变量的初始值 X0 Options 控制规划过程的参数系列
四位教师每人只能教一门课，每一门课只能 由一个教师来教。要确定哪一位教师上哪一门课， 使四门课的平均成绩之和为最高。 设xij（i=1, 2, 3, 4；j=1, 2, 3, 4）为第i个教师是 否教第j门课，xij只能取值0或1，其意义如下：
0 第i个教师不教第 j门课 x ij 1 第i个教师教第 j门课
背包问题
例1.2 一只背包最大装载重量为50公斤。现有三种物品， 每种物品数量无限。每种物品每件的重量、价值如下表 所示： 物品1 重量（公斤/ 件） 价值（元/件） 物品2 物品3
10
17
41
72
20
35
要在背包中装入这三种物品各多少件，使背包中的物品价值最高 。
设装入物品1，物品2和物品3各为x1，x2，x3 件，由于物品的件数必须是整数，因此背包问题 的线性规划模型是一个整数规划问题：
fval 优化结束后得到的目标函数值
目标函数取得极值的决策变量组成的列向量 优化结束后得到的目标函数值 控制规划过程的参数系列
[X,fval,exitflag,output,lambda]
=linprog(f,A,b,Aeq,Beq,LB,UB,X0,options)
目标函数的系数组成的向量 矩阵 向量 变量的初始值 变量的上界约束 矩阵 向量 变量的下界约束
max s.t. z= 5.24x1 +7.30x2 +8.34x3 +4.18x4 1.5x1 +1.0x2 +2.4x3 +1.0x4 ≤2000 1.0x1 +5.0x2 +1.0x3 +3.5x4 ≤8000 1.5x1 +3.0x2 +3.5x3 +1.0x4 ≤5000 x1, x2, x3, x4
线性规划
线性规划简介
线性规划问题最早是前苏联学者康德洛维奇（L.V. Kantorovich）于1939年提 出的，但他的工作当时并未广为人知。 第二次世界大战中，美国空军的一个研究小组SCOOP（Scientific Computation of Optimum Programs）在研究战时稀缺资源的最优化分配这 一问题时，提出了线性规划问题。并且由丹泽（G.B.Dantzig）于1947年提 出了求解线性规划问题的单纯形法。 50年代初，电子计算机研制成功，较大规模的线性规划问题的计算已经成为 可能。因此，线性规划和单纯形法受到数学家、经济学家和计算机工作者的 重视，得到迅速发展，很快发展成一门完整的学科并得到广泛的应用。 1952年，美国国家标准局（NBS）在当时的SEAC电子计算机上首次实现单 纯形算法。 1976年IBM研制成功功能十分强大、计算效率极高的线性规划软件MPS，后 来又发展成为更为完善的MPSX。这些软件的研制成功，为线性规划的实际 应用提供了强有力的工具。 随着计算机硬件和软件技术的发展，目前用微型计算机就可以求解变量个数 达106，约束个数达104的巨大规模的问题，并且计算时间也不太长。
X
T