哈尔滨工程大学：《运筹学基础》课程教学资源（PPT课件讲稿）第一章 线性规划

第1章线性规划- 第一章线性规判 Linear Programming 2021年2月21日 经济管理学院

2021年2月21日 经济管理学院 ---第 1 章 线性规划--- -2- 第 一 章 线性规划 Linear Programming

第1章线性规划- 1.1线性规划概述(1) 线性规划的广泛应用是计算机时代的产物 1902年, Julius farkas发表论文,阐述有关线性规划问题。 1938年,英国人康德进行较详细研究。 1947年,美国学者 George Darηtzg(丹茨格)发明了求解线性规划 的单纯形法(1951年发表),从而为线性规划的推广奠定了基础 有人认为,求解线性规划的单纯形算法可与求解线性方程组的高 斯消元法相媲美。 2021年2月21日 经济管理学院

2021年2月21日 经济管理学院 ---第 1 章 线性规划--- -3- 1.1 线性规划概述（1） • 线性规划的广泛应用是计算机时代的产物。 • 1902年，Julius Farkas 发表论文，阐述有关线性规划问题。 • 1938年，英国人康德进行较详细研究。 • 1947年，美国学者George Dantzig（丹茨格）发明了求解线性规划 的单纯形法（1951年发表），从而为线性规划的推广奠定了基础。 有人认为，求解线性规划的单纯形算法可与求解线性方程组的高 斯消元法相媲美

第1章线性规划- §1.1线性规划概述(2) 线性规划的数学模型有三要素,从实际问题提炼成数学模 型时,首先寻找需求解的未知量x(=1,n),然后列举三 要素 1.列写与自变量(未知量)有关的若干个线性约束条件(等 式或不等式) 2.列写自变量x,取值限制(x,≥0,x,≤0或不限) 3.列写关于自变量的线性目标函数值(极大值或极小值) 其中,前两条称为可行条件,最后一条称为优化条件。符 合这三个条件的数学模型通常称为线性规划的一般型 general) 2021年2月21日 经济管理学院

2021年2月21日 经济管理学院 ---第 1 章 线性规划--- -4- §1.1 线性规划概述（2） • 线性规划的数学模型有三要素，从实际问题提炼成数学模 型时，首先寻找需求解的未知量xj (j=1,…,n)，然后列举三 要素： 1. 列写与自变量（未知量）有关的若干个线性约束条件（等 式或不等式）。 2. 列写自变量xj取值限制（xj≥0，xj≤0或不限）。 3. 列写关于自变量的线性目标函数值（极大值或极小值）。 • 其中，前两条称为可行条件，最后一条称为优化条件。符 合这三个条件的数学模型通常称为线性规划的一般型 （general）

第1章线性规划- 1.1一般线性规划问题及数学模型(3) 1.1问题的提出 例:某企业计划生产甲、乙两种产品,该两种产品均需经A、B、C、D四 种不同设备上加工,按工艺资料规定,在各种不同设备上的加工时间及设 备加工能力、单位产品利润如表中所示。问如何安排产品的生产计划,才能 使企业获利最大? 设备 单位利润 甲产品 乙产品 A222 B128 C40 D042 3 加工能力1 16 2021年2月21日 经济管理学院

2021年2月21日 经济管理学院 ---第 1 章 线性规划--- -5- 设 备 产品 A B C D 单位利润 甲产品 乙产品 2 2 1 2 4 0 0 4 2 3 加工能力 12 8 16 12 1.1.1 问题的提出 例：某企业计划生产甲、乙两种产品，该两种产品均需经A、B、C、D四 种不同设备上加工，按工艺资料规定，在各种不同设备上的加工时间及设 备加工能力、单位产品利润如表中所示。问:如何安排产品的生产计划,才能 使企业获利最大? 1.1 一般线性规划问题及数学模型（3）

第1章线性规划- 建立模型: 设产品的产量甲x1件,乙—x2件,则 目标( object):Maxz=2x1+3x2 限制条件 (Subject to ):(2x,+2x<1 2x,≤8 4x1 4x2<12 ≥0,X,≥0 2021年2月21日 经济管理学院 -6-

2021年2月21日 经济管理学院 ---第 1 章 线性规划--- -6- 建立模型： 设 产品的产量 甲⎯⎯x1件 ，乙⎯⎯ x2件，则 Max z=2 x1+3 x2 2 x1+2 x2  12 x1+2 x2  8 4 x1  16 4 x2  12 x10， x2 0 目标(object) ： 限制条件 (subject to )：

第1章线性规划- 1.1,2线性规划问题的一般数学模型 1.相关概念 (1)决策变量:指模型中要求解的未知量,简称变 量式 (2)目标函数:指模型中要达到的目标的数学表达 (3)约束条件:指模型中的变量取值所需要满足的 切限制条件。 此三项内容称为模型结构的三要素 2021年2月21日 经济管理学院

2021年2月21日 经济管理学院 ---第 1 章 线性规划--- -7- 1.1.2 线性规划问题的一般数学模型 1.相关概念 （1）决策变量：指模型中要求解的未知量，简称变 量。 （2）目标函数：指模型中要达到的目标的数学表达 式。 （3）约束条件：指模型中的变量取值所需要满足的 一切限制条件。 此三项内容称为模型结构的三要素

第1章线性规划- 2.线性规划模型的一般要求 (1)变量:取值为连续的、可控的量; (2)目标函数:线性表达式; (3)约束条件:线性的等式或者不等式 2021年2月21日 经济管理学院 8-

2021年2月21日 经济管理学院 ---第 1 章 线性规划--- -8- 2.线性规划模型的一般要求 （1）变量：取值为连续的、可控的量； （2）目标函数：线性表达式； （3）约束条件：线性的等式或者不等式

第1章线性规划- 线性规划问题的一般表示方法 (1)一般式 maxz=C1X1+CnX2+………+c S t.a 11 ta 12 X2+……+a1nXn≤b a21X1+a22X2+…+a2nXn≤b an1x1+am2x2+…+ amnOn≤bm X12x2, ≥0 S t ---subject to 2021年2月21日 经济管理学院

2021年2月21日 经济管理学院 ---第 1 章 线性规划--- -9- 3 . 线性规划问题的一般表示方法 （1）一般式： max z=c1x1+c2x2+………+cnxn s.t. a11x1+a12x2+………+a1nxn≤b1 a21x1+a22x2+………+a2nxn≤b2 ………… ………………… am1x1+am2x2+………+amnxn≤bm x1 ,x2 , ………,xn≥0 s.t.---subject to

第1章线性规划- (2)和式:maxz n st(Σaxb(i=12,m) J- 0(j=1,2,,n) 其中 表示目标函数系数 ai 表示约束条件系数 表示约束右端项 2021年2月21日 经济管理学院 10-

2021年2月21日 经济管理学院 ---第 1 章 线性规划--- -10- n (2) 和式： max z= cjxj j=1 n s.t.  aijxj ≤bi （i=1,2,……,m) j=1 xj ≥ 0 （j=1,2,……,n) 其中：cj ---------表示目标函数系数 aij---------表示约束条件系数 bi ---------表示约束右端项

第1章线性规划- (3)矩阵:maxz=CX st.AX≤b X≥0 (4)向量:maxz>cy tΣPX≤ m X:≥0 2021年2月21日 经济管理学院

2021年2月21日 经济管理学院 ---第 1 章 线性规划--- -11- n （4） 向量: max z=cjxj n j=1 s.t  pjxj≤b （i=1,2,……,m） j=1 xj≥0 （j=1,2,……,n) （3） 矩阵: max z=CX s.t. AX≤b X≥0