线性规划与目标规划 第1章 线性规划与单纯形法.doc

线性规划与目标规划第1章线性规划与单纯形法
二、线性规划与目标规划
第1章线性规划与单纯形法
第2章对偶理论与灵敏度分析
第3章运输问题
第4章目标规划
清华大学出版社
第1章线性规划与单纯形法
第1节线性规划问题及其数学模型
第2节线性规划问题的几何意义
第3节单纯形法
第4节单纯形法的计算步骤
第5节单纯形法的进一步讨论
第9>6节应用举例
清华大学出版社
第1节线性规划问题及其数学模型
11>.1 问题的提出
图解法
线性规划问题的标准形式
线性规划问题的解的概念
清华大学出版社
第1节线性规划问题及其数学模型
线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟,在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后,线性规划的适用领域更为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。解线性规划问题的方法有多种,以下仅介绍单纯形法。
清华大学出版社
问题的提出
问题的提出
例 1 某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品,已知生产单位产品所需的设备台时及A、B两种原材料的消耗,如表1-1所示。
资源产品
Ⅰ
Ⅱ
拥有量
设备
1
2
8台时
原材料 A
4
0
16 kg
原材料 B
0
4
12 kg
每生产一件产品Ⅰ可获利2元,每生产一件产品Ⅱ可获利3元,问应如何安排计划使该工厂获利最多?
清华大学出版社
问题的提出
用数学关系式描述这个问题
清华大学出版社
问题的提出
得到本问题的数学模型为:
这就是一个最简单的线性规划模型。
清华大学出版社
问题的提出
例 2 靠近某河流有两个化工厂(见图1-1),流经第一化工厂的河流流量为每天500万立方米,在两个工厂之间有一条流量为每天200万立方米的支流。
图1-1
化工厂1每天排放含有某种有害物质的工业污水2万立方米,。从化工厂1排出的污水流到化工厂2前,有20%可自然净化。根据环保要求,%。因此两个工厂都需处理一部分工业污水。化工厂1处理污水的成本是1000元/万立方米,化工厂2处理污水的成本是800元/万立方米。问:
在满足环保要求的条件下,每厂各应处理多少工业污水,
使两个工厂处理工业污水的总费用最小。
清华大学出版社
问题的提出
设:
化工厂1每天处理的污水量为x1万立方米;
化工厂2每天处理的污水量为x2万立方米
建模型之前的分析和计算
清华大学出版社
问题的提出
得到本问题的数学模型为:
清华大学出版社
问题的提出
每一个线性规划问题都用一组决策变量
表示某一方案,这组决策变量的值代表一个具体方案。一般这些变量的取值是非负且连续的;
都有关于各种资源和资源使用情况的技术数据,创造新价值的数据;
存在可以量化的约束条件,这些约束条件可以用一组线性等式或线性不等式来表示;
都有一个达到某一目标的要求,可用决策变量的线性函数(称为目标函数)来表示。按问题的要求不同,要求目标函数实现最大化或最小化。
上述两个问题具有的共同特征:
清华大学出版社
问题的提出
决策变量及各类系数之间的对应关系
清华大学出版社
问题的提出
线性规划模型的一般形式
清华大学出版社
图解法
图解法
例1是一个二维线性规划问题,因而可用作图法直观地进行求解。
清华大学出版社
图解法
目标值在(4,2)点,达到最大值14
清华大学出版社
图解法
(1)无穷多最优解(多重最优解),见图1-4。
(2)无界解,见图1-5-1。
(3)无可行解,见图1-5-2。
通过图解法,可观察到线性规划的解可能出现的几种情况:
清华大学出版社
图解法
目标函数 max z=2x1+4x2
图1-4 无穷多最优解(多重最优解)
清华大学出版社
图解法
图1-5-1 无界解
清华大学出版社
图解法
当存在相互矛盾的约束条件时,线性规划问题的可行域为空集。例如,如果在例1的数学模型中增加一个约束条件:
则该问题的可行域即为空集,即无可行解,
无可行解的情形
清华大学出版社
图解法
增加的约束条件
图1-5-2 不存在可行域
清华大学出版社
线性规划问题的标准型式
线性规