运筹学 一般线性规划问题的数学模型

运筹帷幄之中决胜千里之外线性规划LinearProgramming第一章线性规划及单纯形法一般线性规划问题的数学模型图解法单纯形法原理单纯形法的计算步骤单纯形法的进一步讨论应用举例第一节一般线性规划问题的数学模型线性规划问题的数学模型线性规划问题的标准型及其标准化线性规划问题解的含义一、线性规划的发展1939年，前苏联数学家康托洛维奇用线性模型研究提高组织和生产效率问题1947年，Dantzig提出求解线性规划的单纯形法1950-1956年，主要研究线性规划的对偶理论1958年，发表整数规划的割平面法1960年，Dantzig和Wolfe研究成功分解算法，奠定了大规模线性规划问题理论和算法的基础。1979年，Khachiyan，1984年，Karmarkaa研究成功线性规划的多项式算法。另外，很多现代算法研究如进化、神经网络等。解：一般方法是在铁皮的四个角上剪去四个边长各为x的正方形，折叠做成一个容器，则容积为V=(a-2x)2·x。要让容积最大即确定x(0≤x≤a)的值，使V达到最大。

ax图1-1二、问题的提出例1.1用一块长为a的正方形铁皮做一个容器，应如何剪裁，使做成的容器的容积为最大（见图1-1）例1.2Maxz=2x1+3x22x1+2x2≤12

x1+2x2≤84x1≤164x2≤12

x1，x2≥0例1.3

某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表。问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？Maxz=50x1+100x2

x1+x2≤3002x1+x2≤400x2≤250

x1

，x2≥0例1.4套裁下料问题

某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根，已知原料每根长7.4m。应如何下料，可使所用原料最省？解：共可设计下列5种下料方案设x1,x2,x3,x4,x5

分别为上面5种方案下料的原料根数。建立数学模型如下目标函数：Minz=0.1x2+0.2x3+0.3x4+0.8x5

约束条件：s.t.x1+2x2+x4=1002x3+2x4+x5=1003x1+x2+2x3+3x5=100

x1,x2,x3,x4,x5≥0总结提出问题类似的例子可以举出很多。归结起来有两种情况：一是给定资源，如何充分利用二是给定计划，研究如何统筹安排，用最少的人力物力去完成都是求极值的问题，有些问题可以用微积分解决，但例中除了要求变量非负外带了很多附加条件，解决这类问题就是运筹学中规划论研究的内容。◆线性规划的三个要素决策变量：（x1，x2），一组值代表一个方案目标函数：max或min约束条件：不等式或等式◆线性规划：目标函数、约束条件均为线性函数三、线性规划的数学模型1.一般形式决策变量：X=(x1,x2,…..,xn)T目标函数：max(minz)=c1x1+c2x2+…+cnxn约束条件：

a11x1+a12x2+……..+a1nxn≤(=≥)b1

a21x1+a22x2+……..+a2nxn≤(=≥)b2

…………am1x1+am2x2+……..+amnxn≤(=≥)bmx1,x2,……xn≥0

其中，“max(minz)”是“maximize(minimize)的缩写，含义为“最大化(最小化)”2.一般形式的其它写法①求和形式②向量形式目标函数：

Max（Min）z=CX约束条件：s.t.X≥0其中C=(c1,c2,…,cn)③矩阵形式决策变量常数项系数矩阵价值系数四、线性规划数学模型的建立1.建模条件(1)优化条件：问题所要达到的目标能用线型函数描述，且能够用极值（max或min）来表示；(2)限定条件：达到目标受到一定的限制，且这些限制能够用决策变量的线性等式或线性不等式表示；(3)选择条件：有多种可选择的方案供决策者选择，以便找出最优方案。2.建模步骤(1)确定决策变量：即需要我们作出决策或选择的量。一般情况下，题目问什么就设什么为决策变量。(2)找出所有限定条件：即决策变量受到的所有的约束；(3)写出目标函数：即问题所要达到的目标，并明确是max还是min。例1.5混合配料问题某糖果厂用原料1、2、3加工三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中原料1、2、3的含量、原料每月限用量、三种牌号糖果的加工费及售价，如下表所示。该厂每月如何生产才能获利最大？解:用i=1，2，3代表原料1、2、3，j=1，2，3代表糖果甲、乙、丙。xij表示第j种产品中原料i的含量，则对于原料1：x11，x12

，x13

；对于原料2：x21，x22，x23

；对于原料3：x31

，x32

，x33

；对于甲：x11

，x21

，x31

；对于乙：x12，x22，x32

；对于丙：x13

，x23

，x33

；目标函数：利润最大，利润=收入-原料成本-加工费约束条件：原料用量限制，含量限制maxz=(3.4-0.5)(x11+x21+x31)+(2.85-0.4)(x11+x22+x32)+(2.25-0.3)(x13+x23+x33)-2(x11+x12+x13)-1.5(x21+x22+x23)-1(x31+x32+x33)x11+x12+x13≤2000(供应量限制）

x21+x22+x23≤2500

x31+x32+x33≤1200x11≥0.6(x11+x21+x31)(含量限制）

x31≤0.2(x11+x21+x31)

x12≥0.3(x12+x22+x32)x32≤0.5(x11+x22+x32)x33≤0.6(x13+x23+x33)

xij≥0,i=1,2,3;j=1,2,3五、线性规划的数学模型的标准形式目标函数：maxz=c1x1+c2x2+…+cnxn约束条件：

a11x1+a12x2+……..+a1nxn=b1

a21x1+a22x2+……..+a2nxn=b2

………………am1x1+am2x2+……..+amnxn=bmx1,x2,……xn≥0,b1,b2,……bm≥0◆非标准形式如何化为标准形式目标函数极小化Minz=c1x1+c2x2+…+cnxn令z′=-z，则

Maxz′=（-c1x1）

+（-c2x2）

+…+（-cnxn）两个问题最优解相同，最优值相差一个符号，即

Minz=-Maxz′约束条件为不等式ai1x1+ai2x2+…+ainxn≤bi引进一个新的变量s，

s=bi–(ai1x1+ai2x2+…+ainxn)显然，s≥0这时新的约束条件成为

ai1x1+ai2x2+…+ainxn+s=biS——松弛变量，在实际问题中表示未被充分利用的资源数，未被转化为价值和利润，在目标函数中系数为零.ai1x1+ai2x2+…+ainxn≥bi引进一个新的变量t，

t=(ai1x1+ai2x2+…+ainxn)–bi显然，t≥0这时新的约束条件成为

ai1x1+ai2x2+…+ainxn-t=bit——剩余变量，在实际问题中表示超用资源数，未被转化为价值和利润，在目标函数中系数为零如约束条件为

2x1+2x2≤12可令x3=12-2x1-2x2则新的约束条件为

2x1+2x2+

x3=12x3为松弛变量，x3≥0如约束条件为

2x1+2x2≥

12可令x4=2x1+2x2-12则新的约束条件为

2x1+2x2-

x4=12x4为剩余变量，x4≥0右端项有负值如bi<0则把该等式约束两端同时乘以-1，得到：

-ai1x1-ai2x2-…-ainxn=-bi

变量取负值如xi≤0，令xi'=-xi

，则xi'≥0变量无约束如x无约束，令x＝x´-x´´,其中x´≥

0，x´´≥0例1.6

将以下线性规划问题化为标准形式

minZ=x1+2x2+3x3s.t.-2x1+x2+x3≤9-3x1+x2+2x3

≥43x1-2x2-3x3=-6x1≤0

,x2≥0

，x3取值无约束。解：首先令z´=-z，x3=x´3-x´´3，其中x´3≥

0,x´´3≥0，

x´1=－x1，其中x´1≥

0，考虑约束，引进松弛变量x4≥0

、剩余变量x5≥0再次等式约束其右端项为负数，所以两边同乘以-1，得到-3x´1

+2x2+3x´3-3x´´3

=6问题转化为：

maxZ´=x´1

-2x2-3x´3+3x´´3

+0x4+0x5s.t.2x´1

+x2+x´3-x´´3

+x4=93x´1

+x2+2x´3-2x´´3

-x5=43x´1

+2x2+3x´3-3x´´3

=6x´1,x2,x´3,x´´3,x4,x5≥0

练习1.6（a）解：首先令z´=-z，x2=x´2-x´´2，其中x´2≥

0,x´´2≥0，

x´3=－x3，其中x´3≥

0，考虑约束，引进松弛变量x4≥0

、剩余变量x5≥0问题转化为：

六、线性规划问题的解对于线性规划问题maxCTX（1.1a）

(LP)s.t.AX≤b（1.1b）

X≥0（1.1c）其中,C,XRn,bRm,Amn矩阵有以下几个概念（单纯形法中详细介绍）：1.可行解(feasiblesolution)

满足(1.1b)(1.1c)X=(x1,x2,…..,xn)T称为线性规划问题(LP)的可行解。全部可行解的集合称为可行域。2.最优解(optimalsolution)

使目标函数(1.1a)达到最大值的可行解成为最优解。3.基设n>m,A的秩为m。B是矩阵A中的一个mm阶的满秩矩阵，称B是线性规划问题的一个基。不失一般性，设

=(P1,···,Pm),B中的每一个列向量Pj(j=1,···m)称为基向量，与基向量Pj对应的变量xj称为基变量。线性规划除基变量以外的其他变量称为非基变量。4.基解在约束方程组(1.1b)中，令所有非基变量xm+1=xm+2=··