运筹学课件1-1线性规划问题及其数学模型

运筹学 课件

第一章 线形规划本章学习重点线性规划是运筹学中比较成熟的一个分支 它具有成熟而有效的求解方法， ,它具有成熟而有效的求解方法，可以借助于 计算机进行求解，在军事、 计算机进行求解，在军事、经济等领域中具有 广泛的应用。学习本章， 广泛的应用。学习本章，要掌握线性规划的数 学模型(建模以及把不同形式的线性规划问题 化为标准形式的方法)、 化为标准形式的方法)、求解方法。上页 下页 返回

运筹学 课件

第一节

线性规划问题 及其数学模型

线性规划问题的提出 线性规划的基本概念 线性规划的数学模型 线性规划问题的标准形式

继续

返回

运筹学 课件

问题的提出 引例: 生产计划问题 引例:I 1 4 0 2 II 2 0 4 3 资源限量 8 台时 16kg 12kg

设备 原材料 A 原材料 B 利润

上页

下页

返回

运筹学 课件

如何安排生产 使利润最大

?产品 2

产品 I

上页

下页

返回

运筹学 课件

什么是线性规划？ 什么是线性规划？在工业、农业、国防、建筑、交通运输、科研、商业 在工业、农业、国防、建筑、交通运输、科研、 等各种活动中，常常要求对资源进行统一分配、 等各种活动中，常常要求对资源进行统一分配、全面规划 和合理调度， 和合理调度，以便从各种可能安排方案中找出最优的计划 或设计，用以指导生产。在这类问题中， 或设计，用以指导生产。在这类问题中，一方面有期望达 到最优要求的目标(例如希望产值最高或消耗最少), ),另 到最优要求的目标(例如希望产值最高或消耗最少),另 一方面又要受到一定条件的限制(例如人力、物力、 一方面又要受到一定条件的限制(例如人力、物力、财力 的限制),如何安排才能使成效最高， ),如何安排才能使成效最高 的限制),如何安排才能使成效最高，消耗既定资源取得 的收益最大，或达到既定收益所消耗的资源最少。 的收益最大，或达到既定收益所消耗的资源最少。这可以 借助线性规划 线性规划( Programming,LP)来解决。 借助线性规划(Linear Programming,LP)来解决。上页 下页 返回

运筹学 课件

线性规划研究的内容 在现有的资源条件下 ， 如何充分利用资 在现有的资源条件下， 使任务或目标完成得最好( 源 ， 使任务或目标完成得最好 ( 求极大 化问题) 化问题)。 在给定目标下 ， 如何以最少的资源消耗 在给定目标下， 实现这个目标(求极小化问题) ,实现这个目标(求极小化问题)。

上页

下页

返回

运筹学 课件

第1步 -确定决策变量 设 ——I x1——I的产量 ——II x2 ——II的产量是问题中要确定的未知量， 是问题中要确定的未知量， 表明规划中的用数量表示的 方案、措施，可由决策

者决 方案、措施， 定和控制。 定和控制。

x1

x2

上页

下页

返回

运筹学 课件

第2步 --定义目标函数利润

Max Z =

x1 +

x2

上页

下页

返回

运筹学 课件

第2步 --定义目标函数

Max Z = 2 x1 + 3 x2

上页

下页

返回

运筹学 课件

对我们有 何限制?

上页

下页

返回

运筹学 课件

第3步 --表示约束条件x1 + 2 x2 ≤ 8 4 x1 ≤ 16 4 x2 ≤ 12 x1、 x2 ≥ 0设备 原材料A 原材料 原材料B 原材料 利润 I 1 4 0 2 II 2 0 4 3 资源限量 8 台时 16kg 12kg

上页

下页

返回

运筹学 课件

该计划的数学模型目标函数 Max Z = 2x1 + 3x2 2x 3x 2x 约束条件 x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12 x 1、 x 2 ≥ 0

x1

x2上页 下页 返回

运筹学 课件

基本概念

决策变量(Decision variables) 决策变量( 目标函数(Objective function) 目标函数( 它是决策变量的函数 约束条件(Constraint conditions) 约束条件( 指决策变量取值时受到 可行域(Feasible region) 可行域( 的各种资源条件的限制 最优解(Optimal solution) 最优解( ,通常表达为含决策变量的等式或不等式。 量的等式或不等式。 可行域中使目标 函数达到最优的 决策变量的值 满足约束条件的决 策变量的取值范围上页 下页 返回

问题中要确定的未知量，表 问题中要确定的未知量， 明规划中的用数量表示的方 案、措施，可由决策者决定 措施， 和控制。 和控制。

运筹学 课件

线性规划问题的共同特征 一组决策变量X表示一个方案,一般X大 一组决策变量X表示一个方案,一般X 于等于零。 于等于零。 约束条件是线性等式或不等式。 约束条件是线性等式或不等式。 目标函数是线性的。 求目标函数最大 目标函数是线性的。 化或最小化

上页

下页

返回

运筹学 课件

例2(书) 2(书某厂生产甲乙两种产品，已知制成一吨产品 某厂生产甲乙两种产品， 甲需用资源A 3吨 资源B 甲需用资源A 3吨，资源B 4m3;制成一吨产品乙 需用资源A 2吨 资源B 需用资源A 2吨，资源B 6m3,资源c 7个单位。 资源c 7个单位。 个单位 若一吨产品甲和乙的经济价值分别为7万元和5 若一吨产品甲和乙的经济价值分别为7万元和5万 元，三种资源的限制量分别为90吨、200m3和210 90吨 三种资源的限制量分别为90 个单位，试决定应生产这两种产品各多少吨才能 个单位， 使创造的总经济价值最高? 使创造的总经济价值最高?上页 下页 返回

运筹学 课件

建模步骤： 建模步骤： 第一步：确定决策变量 第一步： x1:生产产品甲的数量(吨) 生产产品甲的数量( 生产产品乙的数量( x2:生产产品乙的数量(吨) 上述变量为由决策者决定的未知量，称 上述变量为由决策者决定的未知量， 决策变量。 为决策变量。上页 下页 返回