运筹学之线性规划引论

第一章线性规划引论1.1线性规划问题及其数学模型1.2线性规划问题的图解法1.3线性规划问题的建模与应用举例1/15/202311.1线性规划问题及其数学模型(1)线性规划问题例1、生产组织与计划问题A,B各生产多少,可获最大利润?可用资源煤劳动力仓库AB123202单位利润40503060241/15/20232解:设产品A,B产量分别为变量x1，x2根据题意，两种产品的生产要受到可用资源的限制，具体讲：对于煤，两种产品生产消耗量不能超过30，即：

x1

+2x2

30对于劳动力，两种产品生产的占用量不能超过60，即：3x1+2x2

60对于仓库，两种产品生产的占用量不能超过24，即：2x2

24另外，产品数不能为负，即：

x1，x2

01/15/20233同时，我们有一个追求的目标---最大利润，即：

MaxZ=40x1+50x2综合上述讨论，在生产资源的消耗以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的数学模型：Max

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目标函数约束条件1/15/20234例2合理配料问题求：最低成本的原料混合方案原料ABＣ每单位成本14102261253171642538每单位添加剂中维生12148素最低含量1/15/20235解：设每单位添加剂中原料i的用量为xj(j=1,2,3,4)根据题意：混合配料后，每单位添加剂中A的含量不得低于12，即4x1

+6x2+x3+2x412每单位添加剂中B的含量不得低于14，即x1

+x2+7x3+5x414每单位添加剂中C的含量不得低于8，即2x2

+x3+3x4

8另外，原料使用量不能为负，即：

x1，x2，

x3，x4，

01/15/20236同时，我们有一个追求的目标---成本最低，即：MinZ=2x1

+5x2+6x3+8x4综合上述讨论，在添加剂中各维生素的含量以及成本与原料消耗量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的数学模型：目标函数约束条件MinZ=2x1

+5x2+6x3+8x44x1

+6x2+x3+2x412x1

+x2+7x3+5x4142x2

+x3+3x4

8

xj

0(j=1,…,4)s.t1/15/202372.9m钢筋架子100个，每个需用2.1m各1，原料长7.4m1.5m求：如何下料，使得残余料头最少。解：首先列出各种可能的下料方案；计算出每个方案可得到的不同长度钢筋的数量及残余料头长度；确定决策变量；根据下料目标确定目标函数；根据不同长度钢筋的需要量确定约束方程。例3、合理下料问题1/15/20238设按第i种方案下料的原材料为xi根组合方案123456782.9m211100002.1m021032101.5m10130234合计7.3m7.1m6.5m7.4m6.3m7.2m6.6m6.0m料长7.4m7.4m7.4m7.4m7.4m7.4m7.4m7.4m料头0.1m0.3m0.9m0.0m1.1m0.2m0.8m1.4m1/15/20239例4、运输问题工厂123库存仓121350222430库334210需求401535运输单价求：运输费用最小的运输方案。1/15/202310解：设xij为i仓库运到j工厂的原棉数量其中：i

＝1，2，3j＝1，2，3MinZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33x11+x12+x13

50x21+x22+x23

30x31+x32+x33

10x11+x21+x31=40x12+x22+x32=15x13+x23+x33=35xij

0s.t1/15/202311(2)线性规划问题的特点决策变量：(x1…xn)T

代表某一方案，

决策者要考虑和控制的因素非负；目标函数：Z=ƒ(x1

…xn)为线性函数，求Z极大或极小;约束条件：可用线性等式或不等式表示.具备以上三个要素的问题就称为线性规划问题。1/15/202312目标函数约束条件(3)线性规划模型一般形式1/15/202313隐含的假设比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij,bi,cj为确定值1/15/2023141.2线性规划问题的图解法定义1：满足约束(2)的X=(X1…Xn)T称为线性规划问题的可行解，全部可行解的集合称为可行域。定义2：满足(1)的可行解称为线性规划问题的最优解。1/15/202315例1-1

MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t1/15/202316解：(1)、确定可行域

X1+2X230

3X1+2X2602X224X10X202030100102030X2DABC2X224X1+2X2303X1+2X260X10X20可行域1/15/202317(2)、求最优解最优解：X*=(15,7.5)Zmax=975Z=40X1+50X20=40X1+50X2(0,0)，(10,-8)C点：X1+2X2=30

3X1+2X2=600203010102030X1X2DABC最优解Z=975可行解Z=0等值线1/15/202318解：(1)、确定可行域与上例完全相同。(2)、求最优解0203010102030DABC最优解Z=1200最优解：BC线段1/15/202319最优解：BC线段B点：X(1)=(6,12)C点：X(2)=(15,7.5)X=X(1)+(1-)X(2)(01)MaxZ=1200

X1615

X2127.5X==+(1-)X1=6+(1-)·15X2=12+(1-)·7.5X1=15-9X2=7.5+4.5(01)1/15/202320例1-3、MaxZ=2X1+4X22X1+X28-2X1+X22X1,X20s.tZ=08246X240X1-2X1+X222X1+X28X10X20可行域无界无有限最优解无有限最优解可行域无上界1/15/202321例1-4、MaxZ=3X1+2X2-X1-X21X1,X20无可行域无可行解-1X2-1X10s.tX20X10-X1-X211/15/202322012345678123456⑴⑵⑶⑷∴有唯一最优解：x1=4x2=2最优值Z=14x2

x1(42)1/15/202323012345678123456⑴⑵⑶⑷x2

x11/15/202324⑴⑵无界解x1x2

⑴⑵x1x2

无可行解1/15/202325直观结论若线性规划问题有解，则可行域是一个凸多边形（或凸多面体）；若线性规划问题有最优解，则唯一最优解对应于可行域的一个顶点；无穷多个最优解对应于可行域的一条边；若线性规划问题有可行解，但无有限最优解，则可行域必然是无界的；若线性规划问题无可行解，则可行域必为空集。1/15/2023261.3线性规划问题的建模与应用举例数学规划的建模原则容易理解。建立的模型不但要求建模者理解，还应当让有关人员理解。这样便于考察实际问题与模型的关系，使得到的结论能够更好地应用于解决实际问题。容易查找模型中的错误。这个原则的目的显然与(1)相关。常出现的错误有：书写错误、公式错误。容易求解。对线性规划来说，容易求解问题主要是控制问题的规模，包括决策变量的个数和约束条件的个数。这条原则的实现往往会与(1)发生矛盾，在实现时需要对两条原则进行统筹考虑。1/15/202327建立线性规划模型的四个步骤设立决策变量；明确约束条件并用决策变量的线性等式或不等式表示；用决策变量的线性函数表示目标，并确定是求极大（Max）还是极小（Min）；根据决策变量的物理性质研究变量是否有非负性。1/15/202328例某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：人力资源分配的问题设司机和乘务人员分别在各时间段一开始时上班，并连续工作8h，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?1/15/202329解：设xi表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：Minz=x1+x2+x3+x4+x5+x6

约束条件：s.t.

x1+x6≥60

x1+x2≥70

x2+x3≥60

x3+x4≥50

x4+x5≥20

x5+x6≥30

x1,x2,x3,x4,x5,x6≥0，整数1/15/202330例某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？套裁下料问题解:考虑下列各种下料方案（按一种逻辑顺序给出）把各种下料方案按剩余料头从小到大顺序列出1/15/202331假设x1,x2,x3,x4,x5分别为上面前5种方案下料的原材料根数。我们建立如下的数学模型。目标函数：Minz=x1+x2+x3+x4+x5

约束条件：

s.t.

x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥01/15/202332假设x1,x2,x3,x4,x5,x6,x7,x8分别为上面前8种方案下料的原材料根数。我们建立如下的数学模型。目标函数：

Minz=0.1x1+0.3x2+0.9x3+1.1x5+0.2x6+0.8x7+1.4x8约束条件：

s.t.2x1+x2+x3+x4≥1002x2+x3+3x5+2x6+x7≥100

x1+x3+3x4+2x6+3x7+4x8≥100x1,x2,x3,x4,x5,x6,x7,x8≥0，整数1/15/202333设按第i种方案下料的原材料为xi根组合方案123456782.9m211100002.1m021032101.5m10130234合计7.3m7.1m6.5m7.4m6.3m7.2m6.6m6.0m料长7.4m7.4m7.4m7.4m7.4m7.4m7.4m7.4m料头0.1m0.3m0.9m0.0m1.1m0.2m0.8m1.4m1/15/202334例:明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？生产计划的问题1/15/202335解：设x1，x2，x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4，x5分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。求xi

的利润:利润=售价-各成本之和可得到xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。这样我们建立如下数学模型：

目标函数:Maxz=15x1+10x2+7x3+13x4+9x5

约束条件：s.t.5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥01/15/202336例:某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问：该厂应如何安排生产，使利润收入为最大？配料问题1/15/202337解：设xij表示第i种（甲、乙、丙）产品中原料j的含量。这样我们建立数学模型时，要考虑：对于甲：x11，x12，x13；对于乙：x21，x22，x23；对于丙：x31，x32，x33；对于原料1：x11，x21，x31；对于原料2：x12，x22，x32；对于原料3：x13，x23，x33；1/15/202338目标函数：利润最大，利润=收入-原料支出

约束条件：规格要求4个；供应量限制3个。Max

z=-15x11+25x12+15x13-30x21+10x22-40x31-10x33

s.t.0.5x11-0.5x12-0.5x13≥0（原材料1不少于50%）-0.25x11+0.75x12-0.25x13≤0（原材料2不超过25%）0.75x21-0.25x22-0.25x23≥0（原材料1不少于25%）-0.5x21+0.5x22-0.5x23≤0（原材料2不超过50%）

x11+x21+x31≤100(供应量限制）

x12+x22+x32≤100(供应量限制）

x13+x23+x33≤60(供应量限制）xij≥0,i=1,2,3;j=1,2,31/15/202339例：某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。据测定每万元每次投资的风险指数如下表：投资问题1/15/202340a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？

b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？问：解：1）确定决策变量：连续投资问题设xij(i=1-5，j=1、2、3、4)表示第i年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下决策变量：A

x11x21x31x41x51

B

x12x22x32x42

C

x33

D

x241/15/2023412）约束条件：第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是：x11+x12=200第二年：B次年末才可收回投资故第二年年初的资金为1.1x11，于是：x21+x22+x24=1.1x11第三年：年初的资金为1.1x21+1.25x12，于是：x31+x32+x33=1.1x21+1.25x12第四年：年初的资金为1.1x31+1.25x22，于是：x41+x42=1.1x31+1.25x22第五年：年初的资金为1.1x41+1.25x32，于是：x51=1.1x41+1.25x32

B、C、D的投资限制：

xi2≤30(i=1，2，3，4)，

x33≤80，x24≤1001/15/202342a)

Max

z=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200

x21+x22+x24=1.1x11

x31+x32+x33=1.1x21+1.25x12

x41+x42=1.1x31+1.25x22

x51=1.1x41+1.25x32

xi2≤30(i=1、2、3、4)，

x33≤80，x24≤100xij≥0(i=1,2,3,4,5；j=1,2,3,4）3）目标函数及模型：1/15/202343b)

Min

f=（x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24s.t.

x11+x12≤200

x21+x22+x24≤1.1x11

x31+x32+x33≤1.1x21+1.25x12

x41+x42≤1.1x31+1.25x22

x51≤1.1x41+1.25x32

xi2≤30(i=1、2、3、4)，

x33≤80，x24≤1001.1x51+1.25x42+1.4x33+1.55x24≥330xij≥0(i=1,2,3,4,5；j=1,2,3,4）1/15/202344第一章作业6、7、8、9、10、12中任选三题1/15/202345补充例题(20050415-1)某厂生产一种产品，该产品在未来5个月的需求量、每个月最大生产能力和单位生产成本如下表所示：另外，每件产品每月的存储