第二章 线性规划

第二章 线性规划线 性 规 划 内 容 框 架 () 1 LP数学模型 ( 2)LP各种解的概念： 可行解(重点) 基本概念 基本解(难点) 基本可行解(重点) 最优解 基本最优解 解的基本性质：四个主要定理 图解法 ?条件 实际问题 LP模型 大M 法 基本方法 单纯形法(原始单纯形法、人工变量法 两阶段法) 对偶单纯形法 (求解) 前提？步骤？ 修正单纯形法 对偶理论 进一步讨论 灵敏度分析 参数规划 算法复杂性问题 哈奇扬算法、karmarkar算法 整数LP 运输问题 特殊LP 多目标LP

第二章 线性规划的数学模型 线性规划 Linear Programming LP 规划论中的静态规划 在有限资源的条件下，合理分配和利用 资源，以期取得最佳效益的优化方法。 求解方法： – 图解法 – 单纯形解法2

第二章 线性规划第一部分 线性规划的数学模型第一节 线性规划一般模型 第二节 线性规划的图解法

第三节 线性规划的标准型第四节 线性规划解的概念

第二部分 线性规划的单纯形法Homework3

现有三个仓库(A,B,C)的产品运往四个纺 织厂。运费情况如下：仓库 A 仓库 B 仓库 C 需求量 工厂 1 2 2 1 40 工厂 2 1 2 4 50 工厂 3 3 4 3 25 工厂 4 5 1 2 35 库存 50 30 70

问应当怎样调运使运费最省？

第一节 线性规划一般模型一、线性规划问题的三要素 决策变量 – 决策问题待定的量值称为决策变量。 – 决策变量的取值要求非负。 约束条件 – 任何问题都是限定在一定的条件下求解，把各种限 制条件表示为一组等式或不等式，称之为约束条件。 – 约束条件是决策方案可行的保障。 – LP的约束条件，都是决策变量的线性函数。 目标函数 – 衡量决策方案优劣的准则，如时间最省、利润最大、 成本最低。 – 有的目标要实现极大，有的则要求极小。 – 目标函数是决策变量的线性函数。5

第一节 线性规划一般模型二、线性规划的定义 对于求取一组变量xj (j=1,2,......,n),使之既满足 线性约束条件，又使具有线性表达式的目标函 数取得极值(极大值或极小值)的一类最优化 问题称为线性规划问题，简称线性规划。

第一节 线性规划一般模型二、线性规划模型的构建 例1. 运输问题某饮料公司在国内有三个生产厂，分布在城市 A1 、 A2 、 A3, 其一级承销商有 4 个，分布在城市 B1 、 B2 、 B3 、 B4 , 已知各厂的产量、各承销商的销售量及从 Ai 到 Bj 的每 吨饮料

运费为 Cij,为发挥集团优势，公司要统一筹划 运销问题，求运费最小的调运方案。销地 产地 A1 A2 A3 销量 B1 6 7 3 2 B2 3 5 2 3 B3 2 8 9 1 B4 5 4 7 4 产量 5 2 37

第一节 线性规划一般模型(1)决策变量。决策的是调运量，因此决策变量为：从Ai到Bj的运输量为xij,

(2)目标函数。运费最小的目标函数为minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34

(3)约束条件。产量之和等于销量之和,故要满足： 供应平衡条件 销售平衡条件x11+x12+x13+x14=5 x21+x22+x23+x24=2 x31+x32+x33+x34 =3 x11+x21+x31=2 x12+x22+x32=3 x13+x23+x33=1 x14+x24+x34=4xij≥0 (i=1,2,3;j=1,2,3,4)8

非负性约束

第一节 线性规划一般模型 综上所述，该问题的数学模型表示为minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34

s.t.subject to

x11+x12+x13+x14=5 x21+x22+x23+x24=2 x31+x32+x33+x34 =3 x11+x21+x31=2 x12+x22+x32=3 x13+x23+x33=1 x14+x24+x34=4xij≥0 (i=1,2,3;j=1,2,3,4)9

第一节 线性规划一般模型例2. 生产计划问题 某厂生产两种产品，需要三种资源，已知各产 品的利润、各资源的限量和各产品的资源消耗 系数如下表：

劳动力 设 备 原材料 利润元/kg

产品A 9 4 3 70

产品B 4 5 10 120

资源限量 360 200 30010

第一节 线性规划一般模型 问题：如何安排生产计划，使得获利最多？ 步骤： 1、确定决策变量：设生产A产品x1 kg;B产品x2 kg 2、确定目标函数：maxZ=70X1+120X2 3、确定约束条件：劳动力约束 9X1+4X2≤360 设备约束 4X1+5X2 ≤200 原材料约束3X1+10X2 ≤300 非负性约束X1≥0 X2≥0

补例. 教材P1711

第一节 线性规划一般模型四、线性规划的一般模型 用一组非负决策变量表示一个决策问题， 存在一定的等式或不等式的线性约束条件， 有一个希望达到的目标，可表示成决策变量的线 性函数。可能是最大化，也可能是最小化。 线性规划一般模型的代数式 为：max(min)Z=c1x1+c2x2+…+cnxn a11x1+a12x2+…+a1nxn ≤(≥,=)b1 a21x1+a22x2+…+a2nxn ≤(≥,=)b2 …………… am1x1+am2x2+…+amnxn≤(≥,=)bm x1,x2,…,xn ≥(≤)0

第二节 LP问题的图解法一、图解法的基本步骤

用图示的方法来求解线性规划问题。 一个二维的线性规划问题，可以在平面图上 求解，三维的线性规划则要在立体图上求解， 而维数再高以后就不能图示了。

(1) 可行域的确定 可行解 (2) 最优解13

第二节 LP问题的图解法1. 可行域的确定 满足所有约束条件的解的集合，称之为可行域。即所有约束 x2 条件共同围城的区域。

例3的数学模型为 maxZ= 3x1 +5 x2 x1 ≤8 2x2 ≤12 S.t. 3x1 +4 x2 ≤36 x1 ≥0, x2 ≥0

96 3

D

C(4,6)

x1 =8

2x2 =12B

0

A4 8 12

x1

3x1 +4 x2 =36

五边形OABCD内(含边界)的

任意一点 (x1,x2) 都是满足所有 约束条件的一个解，称之可行解 。14

第二节 LP问题的图 …… 此处隐藏：1023字，全部文档内容请下载后查看。喜欢就下载吧 ……