第一章 线性规划模型
1 第一章 线性规划模型
线性规划（Linear Programming）是数学规划的一个重要组成部分，是最优化与运筹学理论中的一个重要分支和常用的方法，是最优化理论的基础性内容。
第一节 线性规划问题及其数学模型
一、问题的提出
在生产管理和经营活动中经常提出一类问题，即如何利用有限的人力、物力、财力等资源，以便得到最好的经济效果。
例1 生产计划问题
某工厂在计划期内要安排生产Ⅰ、Ⅱ的两种产品，已知生产单位产品所需的设备台时，A、B两种原材料的消耗以及每件产品可获得的利润如下表所示。问应如何安排生产计划使该工厂获利最多？
Ⅰ Ⅱ 资源限量
设备 1 2 8(台时)
原材料A 4 0 16(kg)
原材料B 0 4 12(kg)
单位产品利润（元） 2 3
解：设12,xx分别表示在计划期内生产产品Ⅰ、Ⅱ的产量。由于资源的限制，所以有：
机器设备的限制条件: 1228xx
原材料A的限制条件： 1416x（称为资源约束条件）
原材料B的限制条件： 2412x
同时，产品Ⅰ、Ⅱ的产量不能是负数，所以有120,0xx（称为变量的非负约束）。
显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有许许多多。而工厂的目标是在不超过所有资源限量的条件下，如何确定产量12,xx以得到最大的利润，即使目标函数1223zxx的值达到最大。
综上所述，该生产计划安排问题可用以下数学模型表示：
例2 运输问题
某公司经销某种产品，三个产地和四个销地的产量、销量、单位运价如下表所示。问在保证产销平衡的条件下，如何调运可使总运费最少？
销地
单位运价
产地 B1 B2 B3 B4 产量
A1 5 6 10 3 60
A2 4 1 9 7 40
A3 4 2 3 8 60
销量 30 50 40 40 第一章 线性规划模型
2 解:（1）决策变量：设(1,2,3;1,2,3,4)ijxij为从产地i运到销地j的运量
第一章 线性规划
习题1.1 （生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？
表1—1
产 品
单耗
资 源 甲 乙 资源限制
A
B
C 1
2
0 1
1
1 300kg
400kg
250kg
单位产品利润（元/件） 50 100
解：设x1、x2分别代表甲、乙两种产品的生产数量（件），z表示公司总利润。依题意，问题可转换成求变量x1、x2的值，使总利润最大，即
max z=50x1+100x2
且称z=50x1+100x2为目标函数。
同时满足甲、乙两种产品所消耗的A、B、C三种资源的数量不能超过它们的限量，即可分别表示为
x1 + x2≤300
2x1 + x2≤400
x2≤250
且称上述三式为约束条件。此外，一般实际问题都要满足非负条件，即x1≥0、x2≥0。
这样有
max z=50x1+100x2
x1 + x2≤300
2x1 + x2≤400
x2≤250
x1、x2≥0
习题1.2 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为200万m3的支流。两化工厂每天排放某种有害物质的工业污水分别为2万m3和1.4万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的总费用最小。
解：设x1、x2分别代表工厂1和工厂2处理污水的数量(万m3)。则问题的目标可描述为
min z=1000x1+800x2
约束条件有
第一段河流（工厂1——工厂2之间）环保要求
(2－x1)/500 ≤0.2%
______________________________________________________________________________________________________________
精品资料 第一章 线性规划
1、
由图可得：最优解为
2、用图解法求解线性规划：
Min z=2x1+x2
01058244212121xxxxxx
解：
由图可得：最优解x=1.6,y=6.4 ______________________________________________________________________________________________________________
精品资料 3用图解法求解线性规划：
Max z=5x1+6x2
0,23222212121xxxxxx
解：
由图可得：最优解Max z=5x1+6x2, Max z= +______________________________________________________________________________________________________________
精品资料 4用图解法求解线性规划：
Maxz = 2x1 +x2
0,5242261552121211xxxxxxx
由图可得：最大值35121xxx ， 所以2321xx
max Z = 8.
______________________________________________________________________________________________________________
1 第1章 线性规划
Chapter 1 Linear Programming
本章内容提要
线性规划是运筹学的重要内容。本章介绍线性规划数学模型、线性规划的基本概念以及求解线性规划数学模型的基本算法——单纯形法。
学习本章要求掌握以下内容：
线性规划模型的结构
线性规划的标准形式，非标准形式转化为标准形式
线性规划的图解以及相应的概念。包括：约束直线，可行半空间，可行解，可行域，凸集，极点，目标函数等值线，最优解
线性规划的基本概念。包括：基，基础解，基础可行解，基变量，非基变量，进基变量，离基变量，基变换
单纯形法原理。包括：基变量和目标函数用非基变量表出，检验数，选择进基变量的原则，确定离基变量的方法，主元，旋转运算
单纯形表。包括初始单纯形表的构成，单纯形表运算方法
初始基础可行解，两阶段法
退化的基础可行解
§1.1 运筹学和线性规划
1.1.1 运筹学
运筹学（Operations Research）是二十世纪三十年代二次大战期间由于战争的需要发展起来的一门学科。当时，英国组织了一批自然科学和工程科学的学者，和军队指挥员一起，研究大规模战争提出的一些问题。如轰炸战术的评价和改进、反潜艇作战研究等，研究结果在战争实践中取得了明显得效果。这些研究当时在英国称为Operational Research，直译为作战研究。战争结束以后，这些研究方法不断发展完善，并逐步形成学科理论体系，其中一些主要的理论和方法包括：线性规划，网第一章 线性规划
2 络流，整数规划，动态规划，非线性规划，排队论，决策分析，对策论，计算机模拟等。这些理论和方法在经济管理领域也得到了广泛应用，Operations Research也转义成为“作业研究”。我国将Operations Research译成“运筹学”，非常贴切地将Operations Research这一英文术语所包含的作战研究和作业研究两方面的涵义都体现了出来。
