§10.1.2数学模型 计算方法 傅孝胡 在实际问题中，线性规划模型是建立在以下假设基础之上的： (1)比例性，指每个决策变量：在约束条件中和在目标函数中数 第十华量优化 方法 值变化时，按x对应的系数a防与价值系数c严格的成比例 1地工线性规同题 变化： 的过性到R 八行数式 (2) 可加性，指目标函数的总值是各项组成部分值cx,之和；第i 地上单纯法 个约束关系式中各组成部分值之和就是第项资源需求总量， 地（丰线丝代此到面 的一城业装 决策变量是相互独立的，不发生关联，且不允许有交叉： 地上无有非址性我 (3)可分性，即模型中的变量可以取小数、分数或某一实数 (4)确定性，即模型中的参数均为确定的常数 然而，有些实际问题不符合上述条件，例如每件产品售价3元，但批 量采购的话，可以打七折.对于这类不符合线性的条件，在一些合理 的假设下，有时可看作近似满足线性条件，也可用线性规划来建模 傅孝明 计算方法
计算方法 傅孝明 第十章最优化 方法 §10.1 线性规划问题 §10.2 线性规划问题的 几何意义 §10.3 单纯形法 §10.4 非线性优化问题 §10.5 一维搜索 §10.6 无约束非线性优 化 . . . . . . §10.1.2 数学模型 在实际问题中, 线性规划模型是建立在以下假设基础之上的: (1) 比例性, 指每个决策变量 xj 在约束条件中和在目标函数中数 值变化时, 按 xj 对应的系数 aij 与价值系数 cj 严格的成比例 变化; (2) 可加性, 指目标函数的总值是各项组成部分值 cixi 之和; 第 i 个约束关系式中各组成部分值之和就是第 i 项资源需求总量. 决策变量是相互独立的, 不发生关联, 且不允许有交叉; (3) 可分性, 即模型中的变量可以取小数、分数或某一实数; (4) 确定性, 即模型中的参数均为确定的常数. 然而, 有些实际问题不符合上述条件, 例如每件产品售价 3 元, 但批 量采购的话, 可以打七折. 对于这类不符合线性的条件, 在一些合理 的假设下, 有时可看作近似满足线性条件, 也可用线性规划来建模. 傅孝明 计算方法
§10.2.1图解法 计算方法 博季胡 第十华量优化 方注 定义10.1 的L城生套面 称线性规划问题有解，是指能找到一组值 地位装性城划问整的 几有型义 (x1,x2,·,x)∈R”以满足所有约束条件；否则，称该问题无 地上排性多 地里耳性比业想 解.任意一个满足约束条件的解(x1,2,·,xn)都称为该线 一性字生 性规划问题的一个可行解.全部可行解构成的集合称为可行 域.在可行域中使目标函数值达到最优的可行解称为最优解 4口，5,1三，升2900 傅孝明 计算方法
计算方法 傅孝明 第十章最优化 方法 §10.1 线性规划问题 §10.2 线性规划问题的 几何意义 §10.3 单纯形法 §10.4 非线性优化问题 §10.5 一维搜索 §10.6 无约束非线性优 化 . . . . . . §10.2.1 图解法 . 定义 10.1 . . 称线性规划问题有解, 是指能找到一组值 (x1, x2, · · · , xn) ∈ R n 以满足所有约束条件; 否则, 称该问题无 解. 任意一个满足约束条件的解 (x1, x2, · · · , xn) 都称为该线 性规划问题的一个可行解. 全部可行解构成的集合称为可行 域. 在可行域中使目标函数值达到最优的可行解称为最优解. 傅孝明 计算方法
§10.2.1图解法 计算方法 傅孝胡 第十华量优化 方法 当线性规划模型中只含2个变量时，问题具有明显的几何意 的1址姓到问面 1的之线性规则同整图 义，可通过在平面上作图的方法求解，称为图解法 几同盘义 进单件法 地丰性丝代此到面 图解法的基本步骤如下：在平面上建立直角坐标系：图示约束 地一城堂 地士无有表非过性我 条件，判别是否存在可行域，如果存在，则找出可行域：图示目 标函数，寻找最优解 4口4①424是2)00 傅孝明 计算方法
计算方法 傅孝明 第十章最优化 方法 §10.1 线性规划问题 §10.2 线性规划问题的 几何意义 §10.3 单纯形法 §10.4 非线性优化问题 §10.5 一维搜索 §10.6 无约束非线性优 化 . . . . . . §10.2.1 图解法 当线性规划模型中只含 2 个变量时, 问题具有明显的几何意 义, 可通过在平面上作图的方法求解, 称为图解法. 图解法的基本步骤如下: 在平面上建立直角坐标系; 图示约束 条件, 判别是否存在可行域, 如果存在, 则找出可行域; 图示目 标函数, 寻找最优解. 傅孝明 计算方法
§10.2.1图解法 计算方法 博孝明 第十华量优化 下面通过例10.1来作具体说明.先将其数学模型重写如下： 方注 的L城生套代面 maxz= 地位装性城划问整的 2x1+5x2, 几有型义 地上非性这 4x1+2x2≤18， (1a) 地里耳性比业则 一线字生 4x1+2≤16， (1b) 山无表业年 S.t. x1+3x2≤12 (1c) x1,2≥0 (1d) 1口，0121型克月00 傅孝明 计算方法
计算方法 傅孝明 第十章最优化 方法 §10.1 线性规划问题 §10.2 线性规划问题的 几何意义 §10.3 单纯形法 §10.4 非线性优化问题 §10.5 一维搜索 §10.6 无约束非线性优 化 . . . . . . §10.2.1 图解法 下面通过例10.1来作具体说明. 先将其数学模型重写如下: max z = 2x1 + 5x2, s. t. 4x1 + 2x2 6 18, (1a) 4x1 + x2 6 16, (1b) x1 + 3x2 6 12, (1c) x1, x2 > 0. (1d) 傅孝明 计算方法
§10.2.1图解法 计算方法 (1)以1为横坐标轴，2为纵坐标轴，适当选取坐标长度的单位， 博孝明 建立平面直角坐标系.由变量的非负约束条件(1d)知，满足该 第十华量优化 条件的解均在第！象限内. 方法 (2) 依据约束条件，找出可行域.约束条件(1a)表示含直线 运1址性到的问面 1的之线性规则同整图 4x1+2x2=18上的点及其左下方的半平面，约束条件(1b) 几月丝义 的进甲件 (1c)的含义类似.同时满足(1a-(1d)的点构成该线性规划问题 地（丰线丝代此到面 的可行域，如图1所示，即凸多边形OP1P2P3P4 地一地堂 (3)图示目标函数.随着：的变化，方程：=2x1+52表示斜率为 地上无有非址性秋 -2/5的一族平行直线，见图1. (4)确定最优解.因为最优解是可行域中使目标函数值：达到最大 值的点，从图1中可看出，当代表目标函数的那条直线由原点开 始向右上方移动时，z的值逐渐增大，一直移动目标函数的直 线，直到与约束条件确定的凸多边形相切时停止，切点所在的 位置即为最优解， 000 傅孝明 计算方法
计算方法 傅孝明 第十章最优化 方法 §10.1 线性规划问题 §10.2 线性规划问题的 几何意义 §10.3 单纯形法 §10.4 非线性优化问题 §10.5 一维搜索 §10.6 无约束非线性优 化 . . . . . . §10.2.1 图解法 (1) 以 x1 为横坐标轴, x2 为纵坐标轴, 适当选取坐标长度的单位, 建立平面直角坐标系. 由变量的非负约束条件(1d)知, 满足该 条件的解均在第 I 象限内. (2) 依据约束条件, 找出可行域. 约束条件(1a)表示含直线 4x1 + 2x2 = 18 上的点及其左下方的半平面, 约束条件(1b)、 (1c)的含义类似. 同时满足(1a)-(1d)的点构成该线性规划问题 的可行域, 如图1所示, 即凸多边形 OP1P2P3P4. (3) 图示目标函数. 随着 z 的变化, 方程 z = 2x1 + 5x2 表示斜率为 −2/5 的一族平行直线, 见图1. (4) 确定最优解. 因为最优解是可行域中使目标函数值 z 达到最大 值的点, 从图1中可看出, 当代表目标函数的那条直线由原点开 始向右上方移动时, z 的值逐渐增大, 一直移动目标函数的直 线, 直到与约束条件确定的凸多边形相切时停止, 切点所在的 位置即为最优解. 傅孝明 计算方法