运筹学 课件第二章线性规划模型与图解法

运筹学课件第二章线性规划模型与图解法第一页，共二十四页，2022年，8月28日第２章线性规划2.1线性规划的模型与图解法2.2单纯形法2.3对偶问题与灵敏度分析2.4运输问题第二页，共二十四页，2022年，8月28日2.1线性规划的模型与图解法2.1.1问题的引入（１）生产安排问题如何合理使用有限的人力、物力和资金，使得收到最好的经济效益。第三页，共二十四页，2022年，8月28日

例1：某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：

试拟订使总收入最大的生产方案。资源单耗产品

资源甲乙资源限量煤电油9445310360200300单位产品价格712第四页，共二十四页，2022年，8月28日

甲乙

资源限量

煤(t)94360

电（kw·h)45200

油（t）310300

单价（万元）712解：设甲乙产品产量分别为x1和x2kg，——决策变量总收入为z万元。则maxz=7x1+12x2——目标函数9x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1，x2≥0s.t.——约束条件第五页，共二十四页，2022年，8月28日（２）配料问题如何合理地搭配（混合）材料，以最经济的方式，达到配比要求。例2：（营养配餐问题）假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？第六页，共二十四页，2022年，8月28日各种食物的营养成分表第七页，共二十四页，2022年，8月28日解：设xj(j=1,2,3,4)为第j种食品每天的购入量，z为每天购买食品的总费用，则配餐问题的线性规划模型为：

minz=14x1+6x2+3x3+2x41000x1+800x2+900x3+200x4300050x1+60x2+20x3+10x455400x1+200x2+300x3+500x4800x1,x2,x3,x40第八页，共二十四页，2022年，8月28日（3）下料问题如何截取原材料，在达到截取要求的情况下，使废料最少。例3：料长7.4米，截成2.9、2.1、1.5米各200根,方案如下表。如何截取余料最少？

方案料型1

2

3

4

52.9米

2.1米

1.5米120100022131203

合计残料7.47.37.27.16.600.10.20.30.8第九页，共二十四页，2022年，8月28日解：设xj(j=1,2,3,4,5)为采用第j种方案截取的原料根数，z为截取后的余料总米数，则下料问题的线性规划模型为：

minz=0x1+0.1x2+0.2x3+0.3x4+0.8x5x1+2x2+x4

2002x3+2x4+x52003x1+x2+2x3+3x5

200xj0(j=1,2,3,4,5)第十页，共二十四页，2022年，8月28日2.1.2线性规划的模型一、LP模型的三要素规划问题的数学模型包含三个组成要素：（1）决策变量：指决策者为实现规划目标采取的方案措施，是问题中要确定的未知量。（2）目标函数：指问题要达到的目的要求，表示为决策变量的函数。（3）约束条件：指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。第十一页，共二十四页，2022年，8月28日二、LP模型的一般式

一般地，线性规划模型：1、决策变量：x1,…,xn2、目标函数：3、约束条件：第十二页，共二十四页，2022年，8月28日

简记为：第十三页，共二十四页，2022年，8月28日三、LP模型的矩阵式

表示为：第十四页，共二十四页，2022年，8月28日例如：第十五页，共二十四页，2022年，8月28日练习1：某畜牧厂每日要为牲畜购买饲料以使其获取A、B、C、D四种养分。市场上可选择的饲料有M、N两种。有关数据如下：试决定买M与N二种饲料各多少公斤而使支出的总费用为最少？410售价

0.40.62.01.7牲畜每日需要量00.10.20.1N0.100.10.2M每公斤含营养成分

ABCD饲料第十六页，共二十四页，2022年，8月28日2.1.3线性规划模型的图解法（适用于2个变量的一般型）一、线性规划问题的解的概念设线性规划问题的一般型为（1）可行解：满足全部约束条件的决策变量X为可行解；

全部可行解的集合R称为可行解域。（2）最优解：使目标函数为最大（或最小）的可行解X*。第十七页，共二十四页，2022年，8月28日二、线性规划的图解法图解法步骤：1、根据约束条件画出可行解域；（1）先作非负约束（2）再作资源限制约束（3）各约束的公共部分即该LP的约束的图形（可行域）2、画出目标函数的等值线；（1）任给z两个不同的值，作相应两条直线（2）将目标直线向增大的方向移，直至可行域的边界，

交点X*即最优解。3、求出最优解。由交点二直线联立求解出最优解X*的值。第十八页，共二十四页，2022年，8月28日x1x209040405030100Dl1l2l3例1用图解法求解下列线性规划问题。可行域目标函数等值线X*有唯一最优解（顶点D）解直线l2,l3组成的线性方程组得：X*=(20,24)T——最优生产方案Z*=7×20+12×24=428——最大收入第十九页，共二十四页，2022年，8月28日（2）在模型（1）中，目标函数改为

maxz=3x1+10x2，其它不变。

09040405030100Dl1l2l3AX1易知，目标函数等值线与直线l3平行。X2故线段AD上的点均为最优解。有无穷多最优解第二十页，共二十四页，2022年，8月28日x1x204可行域无界，在可行域上没有使目标函数值为有限的最优解。无有限最优解（无界解）第二十一页，共二十四页，2022年，8月28日1x2012x1