第二章线性规划的基本概念1.docx

第二章 线性规划的基本概念2.1 线性规划问题及其数学模型2.1.1 问题提出例 2.1.1：某制药厂生产甲、乙两种药品，生产这两种药品要消耗某 种维生素生产每吨药品所需要的维生素量及所占设备时间见表 2.1 该厂每周所能得到的维生素量为160kg，每周设备最多能开15个台 班且根据市场需求，甲种产品每周产量不应超过4t已知该厂生产 每吨甲、乙两种产品的利润分别为5万元和2万元问该厂应如何安 排两种产品的产量才能使每周获得的利润最大？每吨产品的消耗每周资源总量甲乙维生素/kg3020160设备治班5115例2.1.2某加工厂要制作100套钢架，每套要用长为2.9m, 2.1m, 1.5m的圆钢各一根已知原料长为7.4m，问应如何下料，可使所用材料最省？这一类问题的共同特征：1. 每一个问题都有一组决策变量(x , x ,…,x )表示某一方案；这组决1 2 n策变量的值就代表一个 具体的方案一般这些变量取值是非负 的2. 存在一定的约束条件，这些约束条件可以用一组约束等式或约束 不等式来表示3. 都有一个要达到的目标，它可以用决策变量的线性函数(目标函数) 来表示按问题的不同，要求目标函数实现最大值或最小值线性规划(LP)：将约束条件及目标函数都是决策变量的线性函数的规 划问题称为线性规划.max(min)Z线性规划数学模型的一般形式：+ •…+ c xnna x + a x H b a x = b11 1 12 2 1n n 1a x + a x H b a x = b21 1 22 2 2 n n 2a x + a x H b a x = bm1 1 m 2 2 mn n mx , x ,…,x > 01 2 n2.2 两个变量问题的图解法例 2.1.1max Z = 5 x + 2 x1230x + 20x < 160125 x + x < 15s.t 1 2x <41x > 0, x > 012概念：可行域：满足约束条件和非负条件的区域 可行解：满足约束条件和非负条件的解线性规划问题可能出现的几种结果：（画图说明）1． 有唯一解：2. 有无穷多最有解：p44例：目标函数的梯度=某个约束条件的梯度3. 无最优解：注意：无界的可行域不一定无最优解 例：可行域一端是开放的4. 无可行解：可行域为空。

例:约束条件构成的交集为空2.3 线性规划数学模型的标准形式及解的概念2.3.1 标准形式1. 目标函数最大化2. 约束条件（非负约束条件除外）一律化为等式3. 决策变量非负 标准形式的数学表达式：（1） 一般形式（2）工记号简写形式（ 3 ） 矩阵形式（ 4） 向量形式2.3.2 将非标准形式转化为标准形式转换方法：（1）if min Zthen n max Z'=>最优解不变，最优值Z * =—Q）by Z' = 一 Z（2）if 约束条件是小于等于型， then 在该约束条件不等式左边 添加一个新变量 松弛变量不等式改成等式3）if 约束条件是大于等于型， then 在该约束条件不等式左边 减去一个新变量 剩余变量不等式改成等式4）约束方程右端项b < 0,则在约束方程两端乘以（-1）,不等号改变i方向，再按方法（2）或（3）处理（5）决策变量x没有非负的要求，则取两个新变量：x' > 0,x" > 0k k k令x = x'- x"，替换原数学模型中所有的x，并在非负约束中 k k k k增加 x' > 0,x" > 0kk例2.3.3有关解的概念可行解：满足约束条件及非负条件的解最优解：满足目标函数的可行解基矩阵:线性规划约束方程中组的系数矩阵的秩为m则A中任意 m阶可逆矩阵B称为线性规划问题的一个基矩阵。

基向=JHl以向量形式表示矩阵B，则称为基B的一个基向量其对应的决策变量称为基变量非基向量:A中其余的n-m个列向量称为非基向量其对应的决策变 量称为非基变量基本解：基变量满足约束条件，非基变量都为0的一个解称为关于基B的一个基本解基本解的个数Cmn基本可行解：满足非负条件的基本解例：x + 2 x < 812x < 22求其所有的基本解、基本可行解2.4 线性规划的基本理论2.4.1 凸集与凸集合凸集：设集合S u Rn，右对Vx , x e S, V九e E),l]，都有Xx + (1 -九)x e S， 1 2 1 2则称集合 S 为凸集凸组合：设X ,X ,…X e Rn .若存在实数X , X，…九，X e b,1](i二1,2,…k )2九二1，1 2 k 1 2 k i i旦使：工X X = X，则称X为X ,X ,…X e Rn的一个凸组合i i 1 2 kj=1严格凸组合：设 X ,X ,…X e Rn .若存在实数 X , X，…X , X e(0,1)C = 1,2，…k )2 X = 1，1 2 k 1 2 k i ij=1使工X X = X，则称X为x ,X，…X e Rn的一个严格凸组合。

i i 1 2 kj=1极点： 如何凸集中一点S,不能表示称为该凸集中任意两个不同点的严格凸 组合，则该点为该凸集中的一个极点2.4.2 线性规划的基本定理定理2・4・1线性规划的可行域是一个凸集（证明见前例）引理2.4.2线性规划问题的可行解x =（x ,x , ,x \是基本可行解 1 2 nOX的正分量所对应的列向量线性无关定理2・4・3线性规划问题的每一个基本可行解对应于可行域S的一 个极点定理2・4・4有界凸集S上任一点X都可表示为S的极点的凸组合 定理2・4・5对线性规划问题，若可行域有界，且存在最优解，则目 标函数必可在其可行域的某个顶点达到最优值结论：•线性规划问题的可行域是一个有界或无界的凸多边形，其顶点个 数有限（定理2.4.1）• 若线性规划问题有最优解，则其最优解必可在某顶点上达到（定 理2.4.5）• 线性规划的每个基本可行解对应于可行域的一个极点（顶点）.两者 一一对应 （定理2.4.3）寻找最优解的方法:基本可行解一＞最优解定理2・4・6对于线性规划，若存在可行解，则必存在基本可行解。