线性规划模型与标准化_图文.ppt

4
最优解
可行域
-8 0
目标函数等值线
数 据 模 型 与 决 策——江 苏 大 学 MBA 课 程 江
6
x1
主讲： 主讲：赵观兵
8
进一步讨论
例3 某公司由于生产需要，共需要A、B两种原料至少350 吨（A，B两种材料有一定替代性），其中A原料至少购进125 吨。但由于A，B两种原料的规格不同，各自所需的加工时间 也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需 要1小时，而公司总共有600个加工小时。又知道每吨A原料的 价格为2万元，每吨B原料的价格为3万元，试问在满足生产需 要的前提下，在公司加工能力的范围内，如何购买A、B两种 原料，使得购进成本最低？
xj = xj’- xj” 其中
xj’≥0，xj”≥0
即用两个非负变量之差来表示一个无符号限制的变量， 当然xj的符号取决于xj’和xj”的大小。
数 据 模 型 与 决 策——江 苏 大 学 MBA 课 程 江 主讲： 主讲：赵观兵
15
2、目标函数为极小化的问题： 目标函数为极小化的问题： 设目标函数为： Min Z = c1x1 + c2x2 + … + cnxn (可以)令 Z’ ＝ -Z ， 则该极小化问题与下面的极大化问题有相同的最优解， 即： Max Z’ = - c1x1 - c2x2 - … - cnxn 但必须注意，尽管以上两个问题的最优解相同，但它们 最优解的目标函数值却相差一个符号，即： Min Z ＝ - Max Z’ 3、右端常数项为负数的问题： 右端常数项为负数的问题： 在标准形式中，要求约束条件右端常数项必须全部是非负 的。当某个右端常数项为负时，如 bi<0，则把该约束条件两 端同时乘以(-1)，得到：-ai1 x1-ai2 x2- … -ain xn = -bi

21
三、二维线性规划的图解法
3、几个概念 （3）可行解
由约束条件和变量取值限制围成的公共 区域中的每一个点都称为线性规划问题的可 行解。
（4）可行域
所有可行解的集合，构成线性规划问题 的可行域。
22
三、二维线性规划的图解法
4、解的状态
（1）唯一解 （2）无穷多个最优解 (目标函数直线与可行域某直线重合)
二、线性规划模型及标准化
1、线性规划模型的一般形式
例二：配料问题 某工厂要用四种合金T1，T2，T3和T4为 原料，经熔炼成为一种新的不锈钢G。这四 种原料含元素铬（Cr），锰（Mn）和镍（Ni） 的含量（%），这四种原料的单价以及新的 不锈钢材料G所要求的Cr，Mn和Ni的最低含 量（%）如下表所示：
25
三、二维线性规划的图解法
线性规划的几何意义
（1）凸集
集合C∈En，从C中任取两点X、Y，当 0<λ<1时，仍有λX+（1-λ）Y∈C，则称C为 凸集。 凸集：
26
三、二维线性规划的图解法
线性规划的几何意义 （1）凸集 不是凸集：
27
ห้องสมุดไป่ตู้
2、线性规划模型的标准化方法： （1）把最小化目标函数转化为求最大化问 题。令 z' z （2）把约束方程中的不等式转化为等式。 具体做法是：对于小于等于情况，引进松弛变 量，对于大于等于情况，引进剩余变量。 x j x 'j x"j （3）变量取值可能无约束。令 x 'j x j （4）变量小于等于零，令 （5）右端项 b j 小于零，等式两端同乘-1
2
一、情况介绍
线性规划研究的问题可以归结为两大类 别： 1、在现有的资源条件下，如何充分利 用资源，使任务或目标完成得最好（求约束 极大化问题）。 2、在给定目标下，如何以最少的资源 消耗，实现这个目标（求约束极小化问题）。

题的求解过程。
混合整数线性规划问题求解
要点一
混合整数线性规划问题的复杂性
混合整数线性规划问题是指包含整数变量的线性规划问题 。由于整数变量的存在，混合整数线性规划问题的求解变 得更加困难，需要采用特殊的算法和技术来处理。
要点二
混合整数线性规划模型的求解方 法
为了解决混合整数线性规划问题，可以采用一些特殊的算 法和技术，如分支定界法、割平面法等。这些方法能够将 问题分解为多个子问题，并逐步逼近最优解，从而提高求 解效率。
目标函数的类型
常见的目标函数类型包括最小化、最大化等。
确定约束条件
约束条件
01
约束条件是限制决策变量取值的条件，通常表示为数学不等式
或等式。
确定约束条件的原则
02
根据问题的实际情况，选择能够反映问题约束条件的条件作为
约束条件。
约束条件的类型
03
常见的约束条件类型包括等式约束、不等式约束等。
线性规划模型的建立
也可以表示为
maximize (c^T x) subject to (A x geq b) and (x leq 0)。
线性规划的应用场景
生产计划
物流优化
在制造业中，线性规划可以用于优化生产 计划，确定最佳的生产组合和数量，以满 足市场需求并降低成本。
在物流和运输行业中，线性规划可以用于 优化运输路线、车辆调度和仓储管理，降 低运输成本和提高效率。
初始基本可行解
在线性规划问题中，一个解被称为基 本可行解，如果它满足所有的约束条 件。
在寻找初始基本可行解时，可以采用 一些启发式算法或随机搜索方法，以 快速找到一个可行的解作为起点。
初始基本可行解是线性规划问题的一 个起始点，通过迭代和优化，可以逐 渐逼近最优解。

线性规划模型
y
一、线性规划模型
（一）建立线性规划模型有三个基本步骤：
1、找出待定的未知变量（又称为决策变量— —决策者自己可以控制的变量），并且用符号表 示；2、找出问题中所有的限制或约束，写出未知变 量的线性方程组或线性不等式组；
3、找出模型的目标函数：是以函数形式表示的 决策者追求的目标写出未知变量的线性方程或线 性不等式
的解。 2、可行域：所有可行解组成的集合。
3、最优解：使得目标函数达到最优值的可行 解。
4、最优值：对应于最优解的目标函数值。
5、基：约束方程组 AX的系b数矩阵为
阶的m 矩阵n 则称A的任m 意一n个 阶的非奇
异子m 矩阵m B为线性规划的一个基。
6、基向量：组成基B的列向量
Pjk(k1,2 ,m)
33xx11
x2 x2
2x3 2x3
0.5x4 24 4x4 30
xi 0
(i 1,2,3,4)
s.t. Subject to 受约束于
（二）线性规划模型的结构具有如下特性
（1）目标函数是决策变量 的线性函数；
x（ i i1， 2， 3， 4）
（2）约束条件是决策变量 的线性等式或不等式；
x（ i i1， 2， 3， 4）
（1）、确定初始基可行解并且计算相应的目标 函数值
为了确定初始基可行解，需要先找出初始可
称为 基向量。
7、基变量：基向量 Pjk(k1,对2应的,m 变)量 称为基变量x ，j k 基变量以外的变量称为非基变量。
8、基本解：在 AX中，b令非基变量全部为0
，求出
的A一X个解b X，称为基本解。
9、基可行解：满足非负条件 解。X 0的基本10、可行基：基可行解对应的基。