第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 x10， x2 0 目标(object) ： 限制条件 (subject to )：