1-1 线性规划-问题、模型与图解法

1、11-1 1-1 线性规划线性规划- -问题、模型及图解法问题、模型及图解法2线性规划的发展线性规划的发展n20世纪世纪30年代年代 前苏联数学家康特洛维奇前苏联数学家康特洛维奇 提出提出解乘数法解乘数法(1975年诺贝尔经济学奖年诺贝尔经济学奖)n1947 美国空军数学顾问美国空军数学顾问 丹捷格丹捷格 线性规划线性规划 单单纯形法纯形法n冯冯. 诺依曼诺依曼 对偶理论对偶理论 库恩库恩 塔克塔克 盖尔盖尔 严格证明严格证明3概要概要n1 问题描述问题描述n2 建模建模n 2.1 建模三要素建模三要素 n 2.2 一般形式一般形式 2.3 标准形式标准形式n3 模型求解模型求解n 3.1图解

2、法图解法n 3.1.1 方法步骤方法步骤n 3.1.2 解的几种情况解的几种情况n 3.2 基本概念与理论基本概念与理论n 3.3 单纯形法单纯形法 n 3.3.1 单纯形法的一般思路单纯形法的一般思路+例子例子n 3.3.2 单纯形表结构单纯形表结构+例子例子n 3.3.3 单纯形法的计算步骤单纯形法的计算步骤n 4n 3.4 大大M法法n 3.5 两阶段法两阶段法n4 几种特殊情况几种特殊情况n 4.1 无可行解无可行解n 4.2 无界解无界解n 4.3 多重最优解多重最优解n 4.4 进基变量的相持进基变量的相持n 4.5 出基变量的相持出基变量的相持51 1 问题描述问题描述-线性规划

3、经典问题线性规划经典问题 生产计划问题生产计划问题某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：每件产品占用的机时数（小时/件）产品甲产品乙产品丙产品丁设备能力（小时）设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.05000利润（元/件）5.247.308.344.1862 2 建模建模 2.1 2.1 建模三要素建模三要素变量变量 目标函数目标函数 约束条件约束条件（1）理解要解决的问题，了解解题的目标和条件；）理解要解决

4、的问题，了解解题的目标和条件；（2）定义决策变量（）定义决策变量（ x1 ，x2 ， ，xn ），每一组），每一组值表示一个方案；值表示一个方案；（3）用决策变量的线性函数形式写出目标函数，确）用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；定最大化或最小化目标；（4）用一组决策变量的等式或不等式表示解决问题）用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件过程中必须遵循的约束条件712341234123412341234max5.247.38.344.181.51.02.41.020001.05.01.03.58000. .1.03.03.51.05000,0z

5、xxxxxxxxxxxxstxxxxx x x xSchool of BusinessECUSTn习题：营养配餐问题习题：营养配餐问题q假定一个成年人每天至少需要从食物中摄取假定一个成年人每天至少需要从食物中摄取3000大大卡的热量、卡的热量、55克蛋白质和克蛋白质和800毫克的钙。市场上只有毫克的钙。市场上只有猪肉、鸡蛋、大米和白菜四种食品可供选择，它们每猪肉、鸡蛋、大米和白菜四种食品可供选择，它们每公斤所含的热量和营养成分以及市场价格见下表。请公斤所含的热量和营养成分以及市场价格见下表。请问如何选择才能在满足营养的前提下，使购买食品的问如何选择才能在满足营养的前提下，使购买食品的费用最小？

6、费用最小？School of BusinessECUST每公斤食物营养表序号食品名称热量(大卡)蛋白质(克)钙(毫克)价格(元)1猪肉100050400142鸡蛋8006020063大米9002030034白菜200105002300055800School of BusinessECUST营养配餐问题建模营养配餐问题建模n决策变量：决策变量：qxj 每天购入第每天购入第j种食品的公斤数种食品的公斤数n目标函数：每天的食品采购成本最小目标函数：每天的食品采购成本最小n约束条件：满足每天的营养要求约束条件：满足每天的营养要求q(1) 满足每天至少满足每天至少3000大卡的热量要求大卡的热量要求1

7、234m i n14632zxxxx123410008009002003000 xxxxSchool of BusinessECUSTq(2) 满足每天至少摄入55克蛋白质的营养要求q(3) 满足每天至少摄入800毫克钙的营养要求q非负约束：采购量不能为负值12345060201055xxxx1234400200300500800 xxxx1234, , ,0 x x x xSchool of BusinessECUST营养配餐问题的数学模型12341234123412341234m i n14632100080090020030005060201055.400200300500800, ,

8、,0zxxxxxxxxxxxxstxxxxx x x xSchool of BusinessECUST2.2 线性规划的一般线性规划的一般形式形式n线性规划问题是求一个线性函数(目标函数)在满足一组线性等式或不等式条件下极值的数学问题的统称。n线性规划问题的一般特征：q(1) 有一组有待决策的变量(决策变量)，一般表示为x1, x2, ., xn，变量组的每一组取值对应于某一种决策方案，根据实际问题，通常要求变量取非负值，即0,1,2,ixinSchool of BusinessECUSTq(2) 每个问题中存在若干个约束条件，约束条件可用决策变量的线性等式或线性不等式来表达。q(3) 每个问

9、题中有一个目标函数，这个目标函数可表示为决策变量的线性函数。要求这个目标函数在满足约束条件下实现最大化或最小化n将约束条件及目标函数都是决策变量线性函数的数学规划问题称为线性规划(LP, linear programming)School of BusinessECUST121121212212m ax m i n, ,. . . , ,. . . , ,. . . ,. . ., ,. . . ,nnnmnmzf x xxgx xxbgx xxbstgx xxb 一般的数学规划模型112211112211211222221122. . .( , )( , ).( , )0,(1,2,m ax

10、 m i n, )nnnnnnmmm nnmjzcxc xc xa xa xa xba xa xa xbsta xaxaxbxjn 线性规划模型线性规划模型的一般形式12,nx xx12,nc cc1112,mnaaa通常称 为决策变量， 为价值系数， 为技术系数, 为资源限制系数。12,mb bbSchool of BusinessECUST112211112211211222221122. . .( , )( , ).( , )0,(1,2,m ax m)i n, nnnnnnmmm nnmjzc xc xc xa xa xa xba xa xa xbstaxaxaxbxjn1m ax(m

11、 i n)njjjzc x11 201 2( , )(, ,. . . , ).(, ,. . . , )nijjijja xbimstxjn 可简写为：School of BusinessECUST向量式112211112211211222221122. . .( , )( , ).( , )0,(1,2,m ax m)i n nnnnnnmmm nnmjzc xc xc xa xa xa xba xa xa xbstaxaxaxbxjn1212, ,. . . ,:，nnxxCc ccXxm ax m i nzC X1P2PnPb1 122( , ).0 nnP xP xP xbstXSc

12、hool of BusinessECUST矩阵式11121212221212. . ., ,. . ,:. .nnnmmm naaaaaaAP PPaaa1P2PnPm ax(m i n)zC X0( , ).A XbstX 系数矩阵右端常数School of BusinessECUST2.3 线性规划模型的标准形式线性规划模型的标准形式LP模型的标准型为：1 122m ax. . .nnzcxc xc x11 11221121 1222221 12201 2. . . . . . . . . . . .,(, ,. . . , )nnnnmmm nnmja xa xa xba xa xa x

13、bsta xaxaxbxjn其中右端常数项 , 0ib), 2 , 1(mi(1) 目标函数为求最大值目标函数为求最大值(2) 约束条件均为等式，约束条件均为等式，且右端为非负常数且右端为非负常数(3) 决策变量均为非负决策变量均为非负值值School of BusinessECUSTm axzC X10.njjjP xbstX用向量表示时，标准型可写为：用矩阵形式，可表示为：m axzC X0.A XbstXSchool of BusinessECUST非标准形式标准形式n(1) 目标函数：min maxn(2) 右端常数：bi0n(3) 约束：不等式约束 等式约束q =q =n(4)变量：

14、不满足非负条件 满足非负条件q0 0q无符号限制(自由变量) 0School of BusinessECUSTn(1) 目标函数：min max若目标函数为nnxcxcxcZ2211min引进新的目标函数,ZZ则Z的最小值即为ZZZ maxmin从而目标函数变换为：nnxcxcxcZ2211max的最大值，即：School of BusinessECUSTn(2) 右端常数：bi0q若约束条件中某线性方程式的常数项 bi 为负数，则将该线性方程式两端乘以-1即可，但需注意不等式变号。School of BusinessECUSTn(3) 约束：不等式约束 等式约束q = ：在不等式左边加上一个

15、非负变量(松弛变 量)，将不等式变为等式。q = ：在不等式左边减去一个非负变量(剩余变 量)，将不等式变为等式。School of BusinessECUSTn简例：将LP模型12max33Zxx12122102601 2.(, )ixxstxxxi化为标准型。解：对10221 xx引入变量(松弛变量), 03x 使得式变为：102321xxx对式1226xx引入变量(剩余变量), 04x 使得式变为：12426xxxSchool of BusinessECUST于是将原LP模型化为标准形式：12max33Zxx1231242102601 2 3 4., , ,ixxxstxxxxiScho

16、ol of BusinessECUSTn(4)变量：不满足非负条件 满足非负条件q0 0：x 0 ,令x= -x, 则x 0,用变量x 替换xq无符号限制(自由变量) 0：nx无符号限制,令x=xx,其中x,x0。用变量x和x替换xSchool of BusinessECUSTn例将下列LP模型：123min23 Zxxx123123123123723250.,xxxxxxstxxxx xx化为标准型。无符号限制School of BusinessECUSTSchool of BusinessECUST12333312121433533334521272323250.m a,x, ,zxxxx

17、xxxxxxxxxxxx xxxxstxxx x 313 3 模型求解模型求解 3.13.1图解法图解法( (线性规划问题的几何特征线性规划问题的几何特征) ) School of BusinessECUSTn3.1.1 两个决策变量线性规划模型图解法的基本步骤两个决策变量线性规划模型图解法的基本步骤：q(1) 建立以x1, x2为坐标轴的直角坐标系，画出线性规划问题的可行域；q(2) 任取z = z0, 画出对应的目标函数直线, 将该直线在可行区域内平行移动，构成目标函数的等值线簇；q(3) 目标函数值最优的等值线与可行域的交点(若存在)即为问题的最优解。可行域：满足所有约束条件的解的集合，

18、即所有约束条件共同围成的区域。School of BusinessECUSTn例 用图解法求下列线性规划问题的最优解Max Z= 3x1 +5 x2 s.t. 2 x1 16 2x2 10 3x1 +4 x2 32 x1 0, x2 02x1=162x2=103x1+4x2=32x1x248103590ABCDSchool of BusinessECUST2x1 =162x2 =10 x1x248103583x1 +4 x2 =320ABCD目标函数目标函数 Z= 3x1 +5 x2 代表以代表以 Z 为参数的一族平行线。为参数的一族平行线。Z=30Z=37Z=15最优解：4,5X35(1) 惟一最优解惟一最优解max z= x1+3x2 s.t. x1+x26 -x1+2x28 x1,x20123456xz=0z=3z=6z=9z=12z=15.3013456约 束 条 件 （ 1）约 束 条 件 （ 2）C-1-8-2-3-4-5-6-7x213.1.2 线性规划问题解的几种情况线性规划问题