线性规划通常研究资源的最优利用、设备最佳运行等问题。 例如，当任务或目标确定后，如何统筹兼顾，合理安排， 用最少的资源 （如资金、设备、原标材料、人工、时间等） 去完成确定的任务或目标；企业在一定的资源条件限制下， 如何组织安排生产获得最好的经济效益（如产品量最多 、 利润最大）。
应用模型举例
【例1.1】最优生产计划问题。某企业在计划 期内计划生产甲、乙、丙三种产品。这些 产品分别需要要在设备A、B上加工，需要 消耗材料C、D，按工艺资料规定，单件产 品在不同设备上加工及所需要的资源如表 1.1所示。已知在计划期内设备的加工能力 各为200台时，可供材料分别为360、300公 斤；每生产一件甲、乙、丙三种产品，企 业可获得利润分别为40、30、50元，假定 市场需求无限制。企业决策者应如何安排 生产计划，使企业在计划期内总的利润收 入最大？
怎样辨别一个模型是线性规划模型？其特征是： 1．解决问题的目标函数是多个决策变量的线性函 数，通常是求最大值或 最小值； 2．解决问题的约束条件是一组多个决策变量 的线 性不等式或等式。
书本还例举了诸如合理用料问题;配料问题;投资问题;均衡配 套生产问题等.
• 线性规划的一般模型
max(min)Z c1x1 c2 x2 L cn xn
人 工作 甲 乙 丙 丁
译英文 2 10 译日文 15 4 译德文 13 14 译俄文 4 15
97 14 8 16 11 13 9
1.1 数学模型 Mathematical Model
线性规划（Linear Programming,缩写为LP）是运筹学的重 要分支之一，在实际中应用得较广泛，其方法也较成熟， 借助计算机，使得计算更方便，应用领域更广泛和深入。
•
一般地，假设线性规划数学模 型中，有m个约束，有n个决策 变量xj, j=1,2…,n，目标函数的
a11x 1 a12 x2 L a1n xn (或 , )b1
La21Lx1
L
a22 x2 L LLLL
a2n xn LLL
L
(或 , )b2 LLLL
变量系数用cj表示, cj称为价值 系数。约束条件的变量系数用 aij表示，aij称为工艺系数。约
同时，我们有一个追求目标，即获
取最大利润。于是可写出目标函数z
为相应的生产计划可以获得的总利
润：z=40x1+30x2 +50x3
【解】设x1、x2、x3 分别为甲、乙、丙三种产品 的产量数学模型为：
mZ a 4 x x 1 0 3x 2 0 5x 3 0
3 x1 x 2 2 x3 200
x3 ≤ 200；
对设备B，三种产品生产所占用的机
时数不能超过200，于是我们可以得到不 等式： 2x1+2x2+4x3 ≤ 200；
对材料C，三种产品生产所消耗的材 料数不能超过360公斤，于是我们可 以得到不等式： 4x1+5x2+x3 ≤ 360； 对材料D ，三种产品生产所消耗的 材料数不能超过300，于是我们可以 得到不等式： 2x1+3x2+5x3 ≤ 300；
. . am1x1 + am2x2 + … + amnxn = bm
x1 ，x2 ，… ，xn ≥ 0
注：本教材默认目标函数是 max
可以看出，线性规划的标准形式 有如下四个特点：目标最大化、
约束为等式、决策变量xj均非负、 右端常数bi项非负。
对于各种非标准形式的线性 规划问题，我们总可以通过以下 变换，将其转化为标准形式
2 4
x1 x1
2 x2 5x2
4 x3 200 x3 360
2
x1
3x2
5
x3
300
x1 0， x 2 0， x 3 0
产品 甲 乙
资源 设备A
31
设备B
22
材料C
45
最优解X=(50,30,10);Z=3400 材料D
23
利润（元/件） 40 30
丙 现有资 源
2 200 4 200 1 360 5 300 50
am1
x1
am2 x2
L
amn x n (或 , )bm
x j 0, j 1, 2,L , n
束条件右端的常数用bi表示，
n
bi称为资源限量。则线性规划 max(min)Z c j x j
数学模型的一般表达式可写成
j 1
在实际中一般xj≥0,但有时xj≤0或xj 无符号限制。
n
aij x j
(或 , )bi
j1
i 1, 2,L , n
x j 0, j 1, 2,L , n
1.2 线性规划的标准型 Standard form of LP
Max（或Min）z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … + a1nxn = b1 a21x1 + a22x2 + … + a2nxn = b2
表1.1 产品资源消耗
产品
资源
甲
乙
丙 现有资源
设备A
3
1
2
200
设备B2ຫໍສະໝຸດ 24200
材料C
4
5
1
360
材料D
2
3
5
300
利润（元/件） 40
30
50
分析：设变量xi为第i种（甲、乙、丙） 产品的生产件数（i＝1，2，3）。根据
题意，我们知道三种产品的生产受到设
备能力（机时数）的限制。对设备A，三
种产品生产所占用的机时数不能超过200， 于是我们可以得到不等式： 3x1+ x2+ 2
这是一个典型的利润最大化的生产计划问题。其标 中，“Max”是英文单词“Maximize”的缩写，含义 为“最大化”；例题中x1、x2、x3 称为决策变量; 不等式组称为约束条件,( 有时在它前面加“s.t.” 表示“subject to”的意思，意思是“满足 于……”);函数Z称为目标函数,随讨论问题的不 同,Z也可以求最小值. • 线性规划的数学模型由 决策变量 Decision variables ;目标函数Objective function及约束 条件Constraints构成。称为三个要素。
线性规划 例题5 分配问题及匈牙利算法
一、问题的提出和数学模型
例：有一份说明书，要分别译 成英、日、德、俄四种文字， 交与甲、乙、丙、丁四个人去 完成，因各人专长不同，他们 完成翻译不同文字所需要的时 间（小时）如表所示。规定每 项工作只能交与其中的一个人 完成，每个人只能完成其中的 一项工作。
问：如何分配，能使所需的 总时间最少？