第二章 线性规划的图解法

第二章线性规划的图解法第1页，课件共33页，创作于2023年2月

学习重点及难点

1、线性规划问题的建模及图解法

(熟练掌握)2、图解法的求解过程及解的各种情况

（重点)3、图解法的灵敏度分析(熟练掌握)第二章线性规划的图解法第2页，课件共33页，创作于2023年2月第二章线性规划的图解法线性规划（LinearProgramming，简记为LP）是运筹学的一个重要分支，是运筹学中研究较早、发展较快、理论上较为成熟和应用上极为广泛的一个分支。特别是1947年G.B.Dantying提出了一般线性规划问题求解的方法——单纯形法之后，线性规划的理论与应用都得到了极大的发展。单纯形法的有效性使它不仅是线性规划的最基本的算法之一，而且已成为整数规划和非线性规划某些算法的基础。第3页，课件共33页，创作于2023年2月§1线性规划问题及其数学模型一、线性规划问题的提出

要利用线性规划的方法解决实际问题，首先要建立其数学模型.数学模型是描述实际问题共性的抽象的数学形式，因此可以利用纯数学的方法进行研究，从而得到实际问题的性质及其解决的办法。从实际问题中建立数学模型，主要有以下三个步骤：

(1)根据影响所要达到目的的因素确定决策变量；

(2)由决策变量和所要达到目的之间的函数关系确定目标函数.(3)由决策变量所受的限制条件确定决策变量所要满足的约束条件；第4页，课件共33页，创作于2023年2月例1.资源的合理利用问题

某厂生产甲、乙两种产品，要消耗A、B、C三种资源，已知每生产单位产品甲需要A、B、C资源分别是3、2、0，生产单位产品乙需要A、B、C资源分别是2、1、3，资源A、B、C的现有数量分别是65、40、75，甲、乙两种产品的单位利润分别是1500、2500，问如何安排生产计划，使得既能充分利用现有资源又使总利润最大？第5页，课件共33页，创作于2023年2月产品甲产品乙资源的限制资源A3265资源B2140资源C0375单位利润15002500第6页，课件共33页，创作于2023年2月解：将一个实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：设x1表示生产甲产品的数量；x2表示生产乙产品的数量2．确定目标函数：工厂的目标是总利润最大

maxz=1500x1+2500x23．确定约束条件：

3x1+2x265（A资源的限制）

2x1+x240（B资源的限制）

3x275（C资源的限制）4．变量取值限制：一般情况，决策变量只取大于等于0的值（非负值）

x1

0,x2

0第7页，课件共33页，创作于2023年2月用max表示最大值，s.t.（subjectto的简写）表示约束条件，

得到该问题的数学模型为：

maxZ=1500x1+2500x23x1+2x2

65s.t.2x1+x2

40

3x275x1,x2

0线性规划数学模型三要素：

决策变量、目标函数、约束条件第8页，课件共33页，创作于2023年2月例2配料问题某化工厂根据一项合同要为用户生产一种用甲、乙两种原料混合配制而成的特殊产品.甲、乙两种原料都含有A、B、C三种化学成分，其含量（%）和单位成本以及按合同规定产品中三种化学成分的最低含量（%）限制如表所示.问厂方应如何配制该产品，使得总成本达到最小？第9页，课件共33页，创作于2023年2月原料化学成分甲乙产品成分最低含量A1234B232C3155单位成本32第10页，课件共33页，创作于2023年2月解：(1)确定决策变量：设每单位该产品用x1单位甲原料和x2单位乙原料配制而成.

(2)明确目标函数：成本最小，即求

z=3x1+2x2的最小值

(3)所满足的约束条件对化学成分A的要求：12x1+3x2≥4

对化学成分B的要求：2x1+3x2≥2

对化学成分C的要求：3x1+15x2≥5

配料平衡条件：x1+x2=1(4)变量基本要求：

x1，x2≥0第11页，课件共33页，创作于2023年2月则问题的数学模型为：记为minz=3x1+2x212x1+3x2≥42x1+3x2≥2S.t.3x1+15x2≥5

x1+x2=1

x1，x2≥0第12页，课件共33页，创作于2023年2月例3运输问题设某种物资有两个产地A1，A2，其产量分别为2000吨、1100吨，另有四个销地B1、B2、B3、B4需要该种物资，其需求量分别为1700吨、1100吨、200吨、100吨.已知每吨运费如表所示，问如何调运，才能使总运费最省？销地产地B1B2B3B4A12125715A251513715第13页，课件共33页，创作于2023年2月解：设xij表示由产地Ai运往销地Bj（i=1,2；j=1,2,3,4）的运量.

目标函数为总运费最小:minZ=21x11+25x12+7x13+15x14+51x21

+51x22+37x23+15x24

由于总产量与总需求量相等（产销平衡）,所以有约束条件：对产地产量的约束:

x11+x12+x13+x14=2000

x21+x22+x23+x24=1100

对销地需求量的约束:x11+x21=1700

x12+x13=1100

x13+x23=200

x14+x24=100

另外xij是运输量，应满足xij≥0（i=1,2；j=1,2,3,4）第14页，课件共33页，创作于2023年2月所以产销平衡运输问题的模型可记为minz=21x11+25x12+7x13+15x14

+51x21+51x22+37x23+15x24s.t.x11+x12+x13+x14=2000

x21+x22+x23+x24=1100

x11+x21=1700

x12+x22=1100

x13+x23=200

x14+x24=100

xij

≥0（i=1,2；j=1,2,3,4）.第15页，课件共33页，创作于2023年2月二、线性规划问题的数学模型具体分析例1、例2、例3，虽然它们的背景意义各不相同，但从数学模型角度，却具有以下一些共同要点：第一，求一组决策变量xi，并往往要求它们为非负；第二，确定决策变量可能受到的约束，称为约束条件，它们可以用决策变量的线性等式或线性不等式来表示；第三，在满足约束条件的前提下，使某个函数值达到最大（如利润等）或最小（如成本、运费等）.该函数称为目标函数，它是决策变量的线性函数.具备以上三个要素的问题称为线性规划问题.简单地说，线性规划问题就是求一个线性目标函数在一组线性约束条件下的极值问题.第16页，课件共33页，创作于2023年2月二、线性规划问题的数学模型一般表示形式：………………………........................................……第17页，课件共33页，创作于2023年2月

1、和式其他常用表示形式：………第18页，课件共33页，创作于2023年2月

2、矩阵式…………………………...……………第19页，课件共33页，创作于2023年2月

3、向量式……………第20页，课件共33页，创作于2023年2月302010当z值不断增加时，该直线x2=

-（3/5）x1+Z/2500沿着其法线方向向右上方移动。

§2线性规划的图解法

maxZ=1500x1+2500x2s.t.3x1+2x2

65①2x1+x2

40②

3x275③

x1,x2

0④

由图示可知最优点为B（5，25），最优值为70000可行域、可行解、最优解、最优1可行域③②①50等值线B唯一最优解第21页，课件共33页，创作于2023年2月**如将例1的目标函数设为z=1500x1+1000x2

，那么，最优情况下，目标函数的等值线与直线1重合这时，最优解有无穷多个，是线段BC上的所有点，最优值为32500②①50BC无穷多最优解第22页，课件共33页，创作于2023年2月无界解如将例1的约束条件变为:3x1+2x2≥652x1+x2≥403x2≥75

x1，x2≥0那么，可行域成为一个上无界的区域，最优值z→∞，这时，问题无有限最优解，即解无界1③②①50B第23页，课件共33页，创作于2023年2月无可行解（无解）.如下述线性规划问题

maxz=2x1+x2s.t.x1+x2≤22x1+3x2≥8

x1,x2≥0用图解法求解时看出不存在满足所有约束的公共区域（可行域）,即无可行解，当然也无最优解。这时，也简称为无解.第24页，课件共33页，创作于2023年2月线性规划问题解的特点和几种可能情况：线性规划问题的可行解的集合是凸集凸集的极点（顶点）的个数是有限的最优解如果存在只可能在凸集的极点上取得，而不可能发生在凸集的内部线性规划问题的解可能是：唯一解、无穷多最优解、无界解和无可行解(无解)第25页，课件共33页，创作于2023年2月教科书:P221、2课后作业第26页，课件共33页，创作于2023年2月谢谢！本章结束第27页，课件共33页，创作于2023年2月§3线性规划图解法的灵敏度分析灵敏度分析：在建立数学模型和求得最优解之后，研究线性规划的一些系数的变化对最优解产生什么影响？重要的原因：1、模型中的系数一般都是估计值和预测值，不一定非常准确；2、即使这些系数在某一时刻是精确值，它们也会随着市场条件的变化而变化，不会一成不变；3、有了灵敏度分析就不必为了应付这些变化而不停的建立新的模型和求新的最优解。第28页，课件共33页，创作于2023年2月3020一、目标函数中的系数的灵敏度分析

maxZ=1500x1+2500x2s.t.3x1+2x2

65①2x1+x2

40②

3x275③

x1,x2

01③②①50B由图示可知最优解为B(5，25),最优值为70000x2

=-3x1/2+65②-3/2x2=25③0Z=c1x1+c2x2x2=-c1x1/c2+z/c2-c1/c2-3/2<-c1/c2<0第29页，课件共33页，创作于2023年2月一、目标函数中的系数的灵敏度分析

-3/2≤-c1/c2≤0当c2=2500不变时，0≤c1≤3750，最优解不变当c1=1500不变时，1000≤

c2，最优解不变第30页，课件共33页，创作于2023年2月3020

maxZ=1500x1+2500x2s.t.3