《第一章、线性规划及单纯形方法》由会员分享，可在线阅读，更多相关《第一章、线性规划及单纯形方法（140页珍藏版）》请在金锄头文库上搜索。
1、Linear Programming,第一章 线性规划及单纯形法,线性规划问题 线性规划模型 线性规划的图解法 可行域的性质 线性规划的基本概念 基础解、基础可行解 单纯形表,1.1线性规划问题及其数学模型,生产计划问题 配料问题 背包问题 运输问题 指派问题 下料问题,1. 生产计划问题（Production Planning）,某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,求使得总利润最大的生产计划。,设四种产品的产量分别为x1，x2，x3，x4，总利润为z，线性规划模型为：
2、,max z=5.24x1+7.30 x2+8.34x3+4.18x4 s.t. 1.5x1+1.0 x2+2.4x3+1.0 x42000 1.0 x1+5.0 x2+1.0 x3+3.5x48000 1.5x1+3.0 x2+3.5x3+1.0 x45000 x1, x2, x3, x40,目标函数,约束条件,变量非负约束,这个问题的最优解为：x1=294.12件，x2=1500件，x3=0，x4=58.82件 最大利润为：z=12737.06元。,2. 配料问题（Material Blending）,某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成为新的不锈钢G。这四种原料含铬（
3、Cr）、锰（Mn）和镍（Ni）的含量（），这四种原料的单价以及新的不锈钢G所要求的Cr、Mn、Ni的最低含量（）如下表：,要求配100公斤不锈钢G，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。,min z=115x1+97x2+82x3+76x4 s.t. 3.21x1+4.53x2+2.19x3+1.76x4320 Cr的含量下限约束 2.04x1+1.12x2+3.57x3+4.33x4210 Mn的含量下限约束 5.82x1+3.06x2+4.27x3+2.73x4430 Ni的含量下限约束 x1+x2+x3+x4=100 物料平衡约束 x1, x2, x3, x40,设四种
4、原料分别选取x1，x2，x3，x4公斤，总成本为z。,这个问题的最优解为：x1=26.58, x2=31.57, x3=41.84，x4=0（公斤）, 最低成本为z=9549.87元。,3. 背包问题（Knapsack Problem）,一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：,求背包中装入每种物品各多少件，使背包中物品总价值最高。,设三种物品的件数各为x1，x2，x3件，总价值为z。 max z=17x1+72x2+35x3 s.t. 10 x1+41x2+20 x350 x1，x2，x30 x1，x2，x3为整数 这是一个整数规划问题
5、（Integer Programming）。最优解为： x1=1，x2=0，x3=2件，最高价值z=87元。,4. 指派问题（Assignment Problem）,有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由第i个人完成第j项任务的成本（或效益）为cij。求使总成本最小（或总效益最大）的分配方案。 设：,张、王、李、赵四位老师被分配教语文、数学、物理、化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教这四门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门课的平均总成绩最高。,例题,设：,max z=92x11+68x12
6、+85x13+76x14+82x21+91x22+77x23+63x24+ 83x31+90 x32+74x33+65x34+93x41+61x42+83x43+75x44 s.t. x11+x12+x13+x14=1 (1) x21+x22+x23+x24=1 (2) x31+x32+x33+x34=1 (3) x41+x42+x43+x44=1 (4) x11+x21+x31+x41=1 (5) x12+x22+x32+x42=1 (6) x13+x23+x33+x43=1 (7) x14+x24+x34+x44=1 (8) xij=0,1,最优解为：x14=1，x23=1，x32=1，x
7、41=1，max z=336 即张老师教化学，王老师教语文，李老师教数学，赵老师教语文。,四门课的总分可以达到336分。,每一个问题都有一组变量称为决策变量，一般记为,上述例子的共同点：, 每个问题中都有决策变量需满足的一组约束条件线性 的等式或不等式。,线性规划问题的数学模型,通常要求决策变量取值非负，即, 都有一个关于决策变量的线性函数称为目标函数。要 求这个目标函数在满足约束条件下实现最大化或最小化。,将约束条件及目标函数都是决策变量的线性函数的规划问题称为线性规划。有时也将线性规划问题简记为LP（linear programming),一般地，假设线性规划数学模型中，有m个约束，有n个
8、决策变量xj, j=1,2,n，目标函数的变量系数用cj表示, cj称为价值系数。约束条件的变量系数用aij表示，aij称为工艺系数。约束条件右端的常数用bi表示，bi称为资源限量。则线性规划数学模型的一般表达式可写成,线性规划问题的数学模型,线性规划模型,线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：,线性规划的标准形式,maxz=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0 目
9、标函数为极大化，约束条件全部为等号约束，右端常数项bj均为非负，所有变量全部是非负的，这样的线性规划模型称为标准形式,线性规划模型用矩阵和向量表示,max z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0,记,矩阵形式：,向量形式：,其中,线性规划模型总结,线性规划模型的结构 目标函数 ：max，min 约束条件：,=, 变量符号：0, 0, Free 线性规划的标准形式 目标函数：max 约束条件：= 右端常数项： 0 变量符号：0,MaxZ
10、=CX s.t. AX=b X0,线性规划问题的标准化,极小化目标函数转化为极大化 小于等于约束条件转化为等号约束 大于等于约束条件转化为等号约束 右端常数项小于等于0的标准化 变量小于等于0的标准化 变量没有符号限制（Free）的标准化,min z=2x1-3x2+x3 令 z=-z，z=-2x1+3x2-x3 新的目标函数 max z=-2x1+3x2-x3 取得极大化的最优解时，这个最优解同时使原目标函数值取得最小化的最优解。但两个问题最优解的目标函数值相差一个负号。,一、极小化目标函数问题转化为极大化目标函数,例如，对于以下两个线性规划问题,min z=2x1+3x2 s.t. x1+
11、x23 x21 (A) x1, x20,max z=-2x1-3x2 s.t. x1+x23 x21 (B) x1, x20,它们的最优解都是x1=2, x2=1，但(A)的最小化的目标函数值为min z=7，(B)的最大化的目标函数值为max z=-7,2x1+3x2-4x35 引进松弛变量(Slack variable) 2x1+3x2-4x3+x4=5 如果有一个以上小于等于约束，要对于每一个约束引进不同的松弛变量。例如： 2x1+3x2-4x35 3x1-2x2+5x38 在两个约束中分别引进松弛变量x4，x50 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 +x5=8,
12、二、小于等于约束条件转化为等号约束,例如： 2x1+3x2-4x35 3x1-2x2+5x38 在两个约束的左边分别减去剩余变量x4，x50 2x1+3x2-4x3-x4 =5 3x1-2x2+5x3 -x5=8,三、大于等于约束条件转化为等号约束,四、右端常数项小于等于0的标准化,当右端常数项为小于等于0时，如： 2x1-3x2+4x3-4 只需不等式两边同乘以-1，再加上松弛变量即可 -2x1+3x2-4x34,五、变量小于等于0的的标准化,六、变量没有符号限制(Free)的标准化,例如： min z=x1+2x2-3x3 s.t. 2x1+3x2-4x35 3x1-2x2+5x38 x1
13、0, x2:free, x30 先将目标函数转化为极大化，并在约束中引进松弛变量和剩余变量，把不等式约束变为等式 Max z=-x1-2x2+3x3 s.t. 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 -x5=8 x10, x2:free, x3, x4, x50,Max z=-x1-2x2+3x3 s.t. 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3-x5=8 x10, x2:free, x3, x4, x50 然后，令x2=x2-x2”，其中x2,x 2”0 ,代入模型: Max z=-x1-2(x2-x”2)+3x3 s.t. 2x1+3(x2-x”2)
14、-4x3+x4 =5 3x1-2(x2-x”2)+5x3 -x5=8 x1, x2, x”2, x3, x4,x50 整理，得到标准形式： Max z=-x1-2x2+x”2+3x3 s.t. 2x1+3x2-3x”2-4x3+x4 =5 3x1-2x2+2x”2+5x3 -x5=8 x1, x2, x”2, x3, x4,x50,练习： min z=2x1-x2+4x3 s.t. x1+x2-x33 3x1-x2+2x36 x1-3x2-4x3-4 x10, x30,对于模型中只有两个变量的线性规划问题，可以通过在平面上作图的方法求解。 一个线性规划问题有解，是指能找出一组xj(j=1,2,
15、n)，满足约束条件，称这组xj为问题的可行解。 通常线性规划问题总是含有多个可行解，称全部可行解的集合为可行域，可行域中使目标函数为最优的可行解为最优解。,1.2 图解法,线性规划的图解,max z=x1+3x2 s.t. x1+ x26 -x1+2x28 x1 0, x20,可行域,目标函数等值线,最优解,z=6,z=3,z=9,z=12,问题：1、线性规划的最优解是否可能位于可行域的内部？又是否可能位于可行域的边界上？,线性规划的图解,max z=x1+3x2 s.t. x1+ x26 -x1+2x28 x1 0, x20,可行域,目标函数等值线,最优解,z=6,z=3,z=9,z=12,
16、问题：2、若目标函数改为max z=x1+x2，可行域不变，那么 线性规划的最优解在哪里取得？,线性规划可行域和最优解的几种情况,1、可行域封闭 唯一最优解,2、可行域封闭 多个最优解,3、可行域开放 唯一最优解,4、可行域开放 多个最优解,5、可行域开放 目标函数无界,6、无可行解,图解法得到的启示,（1）解的情况：唯一最优解；无穷多最优解； 无界解；无可行解 （2）若可行域存在，则可行域是一个凸集 （3）若最优解存在，则一定在可行域（凸集）的 某个顶点处取得 （4）解题思路：找出凸集的任意顶点，该点的目标函数值与相邻顶点的比较，若该点函数值大，则该点为最优解；否则转到目标函数值更大的顶点，如
