第1章 线性规划基本性质

第一章 线性规划的内容

运筹学第1 运筹学第1章

线性规划基本性质

第一章 线性规划的内容

本章知识内容线性规划的一般模型 线性规划的图解法 线性规划的标准形式 线性规划的解及其性质 线性规划的应用模型

第一章 线性规划的内容

第一章 线性规划基本性质线性规划( Programming,简称LP LP) 线性规划(Linear Programming,简称LP)是数学规划与 运筹学中的一个重要的分支， 运筹学中的一个重要的分支，是运筹学中最重要的一种数量 方法。 方法。 线性规划的发展历史 1939年 前苏联数学家康托洛维奇发表了《 1)1939年，前苏联数学家康托洛维奇发表了《生产组织与 计划中的数学方法》学术报告，首次提出了线性规划问题， 计划中的数学方法》学术报告，首次提出了线性规划问题， 但是他没有找到一个统一的求解这类问题的方法。 但是他没有找到一个统一的求解这类问题的方法。 美国学者希奇柯克(Hitchcock,1941) 2)美国学者希奇柯克(Hitchcock,1941)独立的提出了运 输问题这样一类特殊的线性规划问题。 输问题这样一类特殊的线性规划问题。 1947年 美国学者丹捷格( 3)1947年，美国学者丹捷格( Dantzig )提出求解线性规 划的单纯形法和许多相关的理论， 划的单纯形法和许多相关的理论，为线性规划奠定了理论基 推动了线性规划的发展。 础，推动了线性规划的发展。

第一章 线性规划的内容

LP研究的主要问题(优化思想) LP研究的主要问题(优化思想) 研究的主要问题一类是有限资源的最佳分配问题， 一类是有限资源的最佳分配问题，即在已有资源 人力、财力、物质、时间等)一定的前提下， (人力、财力、物质、时间等)一定的前提下， 研究如何对有限的资源做出最佳方式的调配和最 有利的使用， 有利的使用，以便最充分的发挥资源的效能去获 取最大的经济效益； 取最大的经济效益； 另一类是当一项任务确定以后， 另一类是当一项任务确定以后，研究如何统筹安 做到完成任务后所耗费的资源量(人力、 排，做到完成任务后所耗费的资源量(人力、财 物质、时间等)为最少； 力、物质、时间等)为最少； ——实际上 实际上， ——实际上，上述两类问题是一个问题的两个不 同的角度，即效益最大或耗费最省。 同的角度，即效益最大或耗费最省。 max / min

第一章 线性规划的内容

第一节 线性规划的一般模型一、引例 某厂拟生产甲、乙两种产品， 例1 某厂拟生产甲、乙两种产品，每件产品的利润 分别为3 百元。 乙产品的部件各自在A 分别为3、5百元。甲、乙产品的部件各自在A、B 两个车间分别生产，且每件产品需要在A 两个车间分别生产，且每件产品需要在A、B车间的 生产时间为1、2工时；最后都要在C车间进行装 生产时间为1 工

时；最后都要在C 装配每件甲、乙产品分别需要3 工时。 配，装配每件甲、乙产品分别需要3、4工时。A、 B、C三车间每天可用于生产这两种产品的工时为 12、36。问如何安排生产才能获得最大的利润？ 8、12、36。问如何安排生产才能获得最大的利润？

第一章 线性规划的内容

甲 A B C 利润 百元/ (百元/件) 1 0 3 3

乙 0 2 4 5

每天最 大工时 8 12 36

第一章 线性规划的内容

该问题的LP模型为： 该问题的LP模型为： LP模型为max z = 3 x1 + 5 x2 (0) ≤8 x1 2 x2 ≤ 12 s.t. 3 x1 + 4 x2 ≤ 36 x1、x2 ≥ 0 (1) (2) (3) (4)

第一章 线性规划的内容

某厂生产三种药物A 例2 某厂生产三种药物A、B、C,这些 药物可以从四种不同的原料甲、 药物可以从四种不同的原料甲、乙、丙、 丁中提取， 丁中提取，下表给出了单位原料可提取 的药物量， 的药物量，且四种原料的单位成本分别 百元。 为5、6、7、8百元。 要求：生产A种药物至少160单位； 160单位 要求：生产A种药物至少160单位；B 种药物恰好200单位， 种药物不超过180 200单位 种药物恰好200单位，C种药物不超过180 单位，且使原料总成本最小。 单位，且使原料总成本最小。

第一章 线性规划的内容

A 甲 乙 丙 丁 1 2 1 1

B 2 0 4 2

C 3 1 1 2

单位成本 5 6 7 8

第一章 线性规划的内容

该问题的LP模型为： 该问题的LP模型为： LP模型为min ω = 5 x1 + 6 x2 + 7 x3 + 8 x4 x1 + 2 x2 + x3 + x4 ≥ 160 2 x + 4 x3 + 2 x4 = 200 1 s.t. 3 x1 + x2 + x3 + 2 x4 ≤ 180 x1、x2、x3、x4 ≥ 0

第一章 线性规划的内容

某河流边有两个工厂， 例3 某河流边有两个工厂，流经第一化工厂的 河流流量为每天500万立方米， 500万立方米 河流流量为每天500万立方米，在两个工厂之间 有一条流量为每天200万立方米的支流。 200万立方米的支流 有一条流量为每天200万立方米的支流。第一化 工厂每天排放含有某种有害物质的工业污水2 工厂每天排放含有某种有害物质的工业污水2万 立方米，第二化工厂每天排放这种工业污水1.4 立方米，第二化工厂每天排放这种工业污水1.4 万立方米。 万立方米。从第一化工厂排出的工业污水流到第 二化工厂以前有20%可以自然净化。 20%可以自然净化 二化工厂以前有20%可以自然净化。根据环保要 河流中工业污水的含量应不大于0.2% 0.2%, 求，河流中工业污水的含量应不大于0.2%,这两 个工厂都需要各自处理一部分工业污水。 个工厂都需要各自处理一部分工业污水。两个工 厂的处理工业污水的成本分别是1000 1000元 厂的处理工业污水的成本分别是1000元/万立方 800元 万立方米。 米、800元/万立方米。现在要问在满足环保要求 的条件下，每厂应各自处理多少污水， 的条件下，每厂应各自处理多少污水，使这两个 工厂总的处理工业污水的费用最小？ 工厂总的处理工业污水的

费用最小？

第一章 线性规划的内容

min ω = 1000 x 1 + 800 x 2 ≥1 x1 4 x + 5 x ≥ 8 2 1 ≤ 2 s .t . x 1 x 2 ≤ 1 .4 x 1、 x 2 ≥ 0

第一章 线性规划的内容

1)目标函数 2)决策变量函数约束、 3)约束条件——函数约束、非负性约束 约束条件

4)max / min t.——subject 5)s. t. subject 6)LP模型的三要素—— LP模型的三要素 模型的三要素 目标函数、决策变量、 目标函数、决策变量、约束条件 to

第一章 线性规划的内容

二、线性规划的通式LP模型的共同点： LP模型的共同点： 模型的共同点 可以用一组变量来表示这类问题的待定方案， 1)可以用一组变量来表示这类问题的待定方案， 这些变量的一组定值就代表一个具体的方案。 这些变量的一组定值就代表一个具体的方案。 存在一定的约束关系， 2)存在一定的约束关系，这些约束关系都能用关 于决策变量的线性关系式来表示。 于决策变量的线性关系式来表示。 有一个期望达到的目标， 3)有一个期望达到的目标，这个目标能以某种确 定的数量指标刻画出来， 定的数量指标刻画出来，并也可以表示成关于决策 变量的线性函数。按所考虑问题的不同， 变量的线性函数。按所考虑问题的不同，要求该函 数值最大或者最小。 数值最大或者最小。

第一章 线性规划的内容

LP模型的通式 LP模型的通式max z / min ω = c1 x1 + c2 x2 + Lcn xn a11 x1 + a12 x2 + L + a1n xn ≤ (≥) b1 a x + a x + L + a x ≤ (≥)b 22 2 2n n 2 21 1 s.t. L L L a x + a x + L + a x ≤ (≥)b m2 2 mn n m m …… 此处隐藏：2002字，全部文档内容请下载后查看。喜欢就下载吧 ……