第一章-线性规划和单纯形法.pptVIP

建立线性规划数学模型的步骤 1、选择适当的决策变量 设决策变量的原则 2、用决策变量表达目标函数 收入或利润极大化 成本或支出极小化 3、用决策变量表达所有的约束条件 4、注意变量的符号约束返回 线性规划数学模型 的特点 1、一组决策变量(x1,x2,…,xn) 决策者可选择 2、一个目标函数 极大化或极小化 是决策变量的线性函数 Max(或min) z=c1x1+c2x2+…+cnxn 3、一组约束条件 决策变量的线性等式或不等式组 4、通常变量有符号约束 xj≥０ 线性规划数学模型 的特点 1、一组决策变量(x1,x2,…,xn) 决策者可选择 2、一个目标函数 极大化或极小化 是决策变量的线性函数 Max(或min) z=c1x1+c2x2+…+cnxn 3、一组约束条件 决策变量的线性等式或不等式组 4、通常变量有符号约束 xj≥０ 线性规划模型的一般形式 例某工厂生产A、B两种产品，有关资料如下表所示： 设总成本为z，A、B产品销量为x1、x2， 产品C的销售量为x3，报废量为x4，则： max z = 4 x1 + 10 x2 + 3 x3 － 2 x4 2 x1 + 3x2 ≤ 12 3x1 + 4x2 ≤ 24 －2x2 +x3 + x4 = 0 x3 ≤ 5 x1、x2 、x3 、x4≥0 船只种类 船只数 拖 轮 30 A型驳船 34 B型驳船 52 航线号 合同货运量 1 200 2 400 航线号 船队 类型 编队形式 货运成本 （千元／队） 货运量 （千吨） 拖轮 A型 驳船 B型 驳船 1 1 1 2 — 36 25 2 1 — 4 36 20 2 3 2 2 4 72 40 4 1 — 4 27 20 问：应如何编队，才能既完成合同任务，又使总货运成本为最小？ 例 某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运成本如下表所示： 解： 设：xj为第 j 号类型船队的队数（j = 1，2，3，4），z 为总货运成本 则： min z = 36x1 + 36x2 + 72x3 + 27x4 x1 + x2 + 2x3 + x4 ≤ 30 2x1 + 2x3 ≤34 4x2 + 4x3 + 4x4 ≤52 25x1 + 20x2 ＝200 40x3 + 20x4 ＝400 xj ≥ 0 j = 1,2,3,4 例 合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是1.5，1，0.7（m），这些轴需要用同一种圆钢来做，圆钢长度为4 m。现在要制造1000辆汽车，最少要用多少圆钢来生产这些轴？ 解：这是个条材下料问题 ，设切口宽度为零。 设一根圆钢切割成甲、乙、丙三种轴的根数分别为y1，y2，y3,则切割方式可用不等式1.5y1+y2+0.7y3≤4表示，求这个不等式关于y1，y2，y3的非负整数解。象这样的非负整数解共有10组，也就是有10种下料方式，如下表所示。 方案 规格 1 2 3 4 5 6 7 8 9 10 需求量 y1(根) 2 2 1 1 1 0 0 0 0 0 1000 y2 1 0 2 1 0 4 3 2 1 0 1000 y3 0 1 0 2 3 0 1 2 4 5 1000 余料（m） 0 0.3 0.5 0.1 0.4 0 0.3 0.6 0.2 0.5 设xj ( j = 1,2…,10)为第j种下料方案所用圆钢的根数。则用料最少数学模型为: 方案 规格 1 2 3 4 5 6 7 8 9 10 需求量 y1(根) 2 2 1 1 1 0 0 0 0 0 1000 y2 1 0 2 1 0 4 3 2 1 0 1000 y3 0 1 0 2 3 0 1 2 4 5 1000 余料（m） 0 0.3 0.5 0.1 0.4 0 0.3 0.6 0.2 0.5 求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长的，最后切割最短的，不能遗漏了方案 。 例 配料问题。某钢铁公司生产一种合金，要求的成分规格是：锡不少于28%，锌不多于15%，铅恰好10%，镍要界于35%~5