运筹学(第四版)清华大学出版社《运筹学》教材编写组-第2章

《运筹学(第四版)清华大学出版社《运筹学》教材编写组-第2章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、清华大学出版社1二、线性规划与目标规划第2章线性规划与单纯形法第3章对偶理论与灵敏度分析第4章运输问题第5章线性目标规划清华大学出版社2第2章线性规划与单纯形法第1节线性规划问题及其数学模型第2节线性规划问题的几何意义第3节单纯形法第4节单纯形法的计算步骤第5节单纯形法的进一步讨论第6节应用举例清华大学出版社3第1节线性规划问题及其数学模型2.1.1问题的提出2.1.2图解法2.1.3线性规划问题的标准形式2.1.4线性规划问题的解的概念清华大学出版社4第1节线性规划问题及其数学模型线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟，在实用中的应用日益广泛与深

2、入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。解线性规划问题的方法有多种，以下仅介绍单纯形法。清华大学出版社52.1.1问题的提出2.1.1问题的提出例1某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。资源产品ⅠⅡ拥有量设备128台时原材料A4016kg原材料B0412kg每生产一件产品Ⅰ可获利2元，每生产

3、一件产品Ⅱ可获利3元，问应如何安排计划使该工厂获利最多?清华大学出版社62.1.1问题的提出用数学关系式描述这个问题清华大学出版社72.1.1问题的提出得到本问题的数学模型为:这就是一个最简单的线性规划模型。清华大学出版社82.1.1问题的提出例2靠近某河流有两个化工厂(见图1-1)，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。图1-1化工厂1每天排放含有某种有害物质的工业污水2万立方米，化工厂2每天排放的工业污水为1.4万立方米。从化工厂1排出的污水流到化工厂2前，有20%可自然净化。根据环保要求，河流中工业污

4、水的含量应不大于0.2%。因此两个工厂都需处理一部分工业污水。化工厂1处理污水的成本是1000元/万立方米,化工厂2处理污水的成本是800元/万立方米。问:在满足环保要求的条件下，每厂各应处理多少工业污水，使两个工厂处理工业污水的总费用最小。清华大学出版社92.1.1问题的提出设：化工厂1每天处理的污水量为x1万立方米；化工厂2每天处理的污水量为x2万立方米建模型之前的分析和计算清华大学出版社102.1.1问题的提出得到本问题的数学模型为：清华大学出版社112.1.1问题的提出每一个线性规划问题都用一组决策变量表示某一方案，这组决策变量的值代表一个具体方案。一般这些

5、变量的取值是非负且连续的；都有关于各种资源和资源使用情况的技术数据，创造新价值的数据；存在可以量化的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示;都有一个达到某一目标的要求，可用决策变量的线性函数(称为目标函数)来表示。按问题的要求不同，要求目标函数实现最大化或最小化。上述两个问题具有的共同特征：清华大学出版社122.1.1问题的提出决策变量及各类系数之间的对应关系清华大学出版社132.1.1问题的提出线性规划模型的一般形式清华大学出版社142.1.2图解法1.2图解法例1是一个二维线性规划问题，因而可用作图法直观地进行求解。清华大学出版社152.1.

6、2图解法目标值在（4，2）点，达到最大值14清华大学出版社162.1.2图解法（1）无穷多最优解(多重最优解)，见图1-4。（2）无界解，见图1-5-1。（3）无可行解，见图1-5-2。通过图解法，可观察到线性规划的解可能出现的几种情况：清华大学出版社172.1.2图解法目标函数maxz=2x1+4x2图1-4无穷多最优解（多重最优解）清华大学出版社182.1.2图解法图1-5-1无界解清华大学出版社19当存在相互矛盾的约束条件时，线性规划问题的可行域为空集。例如，如果在例1的数学模型中增加一个约束条件:则该问题的可行域即为空集，即无可行解，无可行解的情形2.1.2

7、图解法清华大学出版社20增加的约束条件图1-5-2不存在可行域2.1.2图解法清华大学出版社212.1.3线性规划问题的标准型式2.1.3线性规划问题的标准型式清华大学出版社222.1.3线性规划问题的标准型式用向量形式表示的标准形式线性规划线性规划问题的几种表示形式清华大学出版社232.1.3线性规划问题的标准型式用矩阵形式表示的标准形式线性规划清华大学出版社242.1.3线性规划问题的标准型式(1)若要求目标函数实现最小化，即minz=CX，则只需将目标函数最小化变换求目标函数最大化，即令z′=−z，于是得到maxz′=−CX。(2)约束条件为不等式。分两种