二、线性规划与目标规划 第2章线性规划与单纯形法 第3章对偶理论与灵敏度分析 ■第4章运输问题 第5章目标规划
二、线性规划与目标规划 ◼第2章 线性规划与单纯形法 ◼第3章 对偶理论与灵敏度分析 ◼第4章 运输问题 ◼第5章 目标规划
第2章线性规划与单纯形法 第1节线性规划问题及其数学模型 ■第2节线性规划问题的几何意义 第3节单纯形法 ■第4节单纯形法的计算步骤 ■第5节利用 MATLAB求解线性规划问题
第2章 线性规划与单纯形法 ◼第1节 线性规划问题及其数学模型 ◼第2节 线性规划问题的几何意义 ◼第3节 单纯形法 ◼第4节 单纯形法的计算步骤 ◼第5节 利用MATLAB求解线性规划问题
第1节线性规划问题及其数学模型 1.1问题的提出 12图解法 13线性规划问题的标准形式 令1.4线性规划问题的解的概念
第1节 线性规划问题及其数学模型 ❖ 1.1 问题的提出 ❖ 1.2 图解法 ❖ 1.3 线性规划问题的标准形式 ❖ 1.4 线性规划问题的解的概念
第1节线性规划问题及其数学模型 线性规划是运筹学的一个重要分支。线性规划在理论上 比较成熟,在实用中的应用日益广泛与深入。特别是在电 子计算机能处理成干上万个约束条件和决策变量的线性规 划问题之后,线性规划的适用领域更为广泛了。从解决技 术问题的最优化设计到工业、农业、商业、交通运输业 军事、经济计划和管理决策等领域都可以发挥作用。它已 是现代科学管理的重要手段之一。解线性规划问题的方法 有多种,以下仅介绍单纯形法
第1节 线性规划问题及其数学模型 线性规划是运筹学的一个重要分支。线性规划在理论上 比较成熟，在实用中的应用日益广泛与深入。特别是在电 子计算机能处理成千上万个约束条件和决策变量的线性规 划问题之后，线性规划的适用领域更为广泛了。从解决技 术问题的最优化设计到工业、农业、商业、交通运输业、 军事、经济计划和管理决策等领域都可以发挥作用。它已 是现代科学管理的重要手段之一。解线性规划问题的方法 有多种，以下仅介绍单纯形法
1.1问题的提出 11问题的提出 例1某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品,已知 生产单位产品所需的设备台时及A、B两种原材料的消耗, 如表1-1所示。 资源产品 拥有量 设备 1 2 8台时 原材料A 4 0 16 kg 原材料B 0 4 12 kg 每生产一件产品工可获利2元,每生产一件产品工可获利 3元,问应如何安排计划使该工厂获利最多?
1.1 问题的提出 1.1 问题的提出 例 1 某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知 生产单位产品所需的设备台时及A、B两种原材料的消耗， 如表1-1所示。 资源 产 品 Ⅰ Ⅱ 拥有量 设 备 1 2 8台时 原材料 A 4 0 16 kg 原材料 B 0 4 12 kg 每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利 3元，问应如何安排计划使该工厂获利最多?
1.1问题的提出 用数学关系式描述这个问题 ●设x1,x2分别表示计划生产L,Ⅱ产品的数量, 称它们为决策变量。 ·生产x1,x2的数量多少,受资源拥有量的限制, 这是约束条件。即x1+2x2≤84x1≤164x2≤12 生产的产品不能是负值即x,x2≥0 ●如何安排生产,使利润最大,这是目标
1.1 问题的提出 称它们为决策变量。 •设 x1 , x2 分别表示计划生产I,II产品的数量， 1 2 2 8 4 1 16 4 2 12 1 2 + • x x ; x ; x x ,x , 这是约束条件。即 生产 的数量多少，受资源拥有量的限制 •生产的产品不能是负值,即x1 ,x2 0 •如何安排生产，使利润最大,这是目标。 用数学关系式描述这个问题
11问题的提出 得到本问题的数学模型为 目标函数maxz=2x1+3x2 x1+2x2≤8 约束条件:4x16 4x,≤1 2 x2≥0 这就是一个最简单的线性规划模型
1.1 问题的提出 + = + 0 4 12 4 16 2 8 2 3 1 2 2 1 1 2 1 2 x ,x x x x x : max z x x 约束条件 目标函数 得到本问题的数学模型为: 这就是一个最简单的线性规划模型
1.1问题的提出 例2靠近某河流有两个化 o工厂1 工厂(见图1-1),流经第一化工 0工厂2 厂的河流流量为每天500万立方 500万立方米 200万立方米 米,在两个工厂之间有一条流 量为每天200万立方米的支流。 图1-1 化工厂1每天排放含有某种有害物质的工业污水2万立方米, 化工厂2每天排放的工业污水为1.4万立方米。从化工厂1排出 的污水流到化工厂2前,有20%可自然净化。根据环保要求, 河流中工业污水的含量应不大于0.2%。因此两个工厂都需处 理一部分工业污水。化工厂1处理污水的成本是1000元/万立 方米,化工厂2处理污水的成本是800元/万立方米。问: 在满足环保要求的条件下,每厂各应处理多少工业污水, 使两个工厂处理工业污水的总费用最小
1.1 问题的提出 例 2 靠近某河流有两个化 工厂(见图1-1)，流经第一化工 厂的河流流量为每天500万立方 米，在两个工厂之间有一条流 量为每天200万立方米的支流。 图1-1 化工厂1每天排放含有某种有害物质的工业污水2万立方米， 化工厂2每天排放的工业污水为1.4万立方米。从化工厂1排出 的污水流到化工厂2前，有20%可自然净化。根据环保要求， 河流中工业污水的含量应不大于0.2%。因此两个工厂都需处 理一部分工业污水。化工厂1处理污水的成本是1000元/万立 方米,化工厂2处理污水的成本是800元/万立方米。问: 在满足环保要求的条件下，每厂各应处理多少工业污水， 使两个工厂处理工业污水的总费用最小
11问题的提出 建模型之前的分析和计算 设 化工厂1每天处理的污水量为x1万立方米 化工厂2每天处理的污水量为x,万立方米 经第2工厂前的水质要求 (2-x1)2 5001000 经第2工厂后的水质要求: 0.8(2-x1)+(14-x22 700 1000
1.1 问题的提出 设： 化工厂1每天处理的污水量为x1万立方米； 化工厂2每天处理的污水量为x2万立方米 1000 2 700 0 8 2 1 4 2 1000 2 500 2 2 1 2 1 − + − − [ . ( x ) ( . x )] ( x ) 经第 工厂后的水质要求： 经第 工厂前的水质要求： 建模型之前的分析和计算
1.1问题的提出 得到本问题的数学模型为: 目标函数mnx=1000x+800x2 约束条件 x 1 0.8x1+x,≥1.6 x1 2 x2≤1.4 x1,x2≥0
1.1 问题的提出 , 0 1.4 2 0.8 1.6 1 min 1000 800 1 2 2 1 1 2 1 1 2 + = + x x x x x x x z x x 约束条件 目标函数 得到本问题的数学模型为：