物流运筹学 课件 刘蓉 第1-11章 物流与运筹学-物流对策论

导论软科学中“硬度”较大的一门科学，兼有逻辑的数学和数学的逻辑的性质。系统工程学和现代管理学中一种基础理论和不可缺少的方法。运筹学与现实1、2015,迪顿通过引入经济规划研究中的对偶理论，着重讨论了这一理论在福利经济学和计量分析中的应用，获诺贝尔经济学奖。2、2012，罗思和沙普利因“稳定匹配理论和市场设计实践”获诺贝尔经济学奖，其理论源于博弈论的思想，运筹学的分支。从1994年诺贝尔经济学奖授予3位博弈论专家（Nash）开始，共有5届诺贝尔经济学奖与博弈论的研究有关。3、作为一种管理层决策的工具，所有管理类专业、管理科学与工程、机械设计、建筑设计、土建等等专业都需要运筹学，涉及军事、建筑、纺织、钢铁、煤炭、石油、电力、农业等领域。4、大到国防战争，小到生活琐事，上至宏观战略、下至微观行动，处处涉及运筹学。

运筹学的由来与发展运筹学的性质与特点

运筹学的主要内容运筹学的学科地位运

筹

学

概

况名称的由来

OperationResearch

运筹帷幄“史记”运作研究发展历程

运筹学的由来与发展二战以前萌芽二战期间产生五六十年代发展七八十年代成熟一、运筹学的产生与发展早期运筹学思想及例子齐王赛马丁渭修皇宫哥尼斯堡七桥问题丁谓修宫宋真宗大中祥符年间，大内失火，一夜之间，大片宫室楼台、殿阁亭榭变成了废墟。为了修复这些宫殿，宋真宗挑选了善于思考的晋国公丁谓负责。当时，要完成这项重大建筑工程，需要解决一系列相关难题：一是取土困难，因为要到郊区去取土，路途太远；二是与此相关的物资运输问题难于解决，这不光是运土问题，还要运输大量其它材料；三是大片废墟垃圾的处理问题。丁谓运筹规划，制定了高明的施工方案。首先下令“凿通衢取土”，从施工现场向外挖了若干条大深沟，挖出的土作为施工用土。这样一来，取土问题就舍远求近地就地解决了。第二步，再把宫外的汴水引入新挖的大沟中，“引诸道竹木筏排及船运杂材，尽自堑中入至宫门”。这样，又解决了大批木材、石料的运输问题。待建筑运输任务完成之后，再排除堑水，把工地所有垃圾倒入沟内，重新填为平地。简单归纳起来，就是这样一个过程：挖沟（取土）－

引水入沟（运输）－

填沟（处理垃圾）。此方案不仅取得了“一举而三役济”的效果，而且“省费以亿万计”，还大大缩短了工期。丁谓所设计的方案，其思想与如今运筹学中的统筹方法是一致的。

运筹学思想及例子。。。。。运筹学名词使用是在1938年(英国解决雷达站同整个作战系统的协调配合问题)。二战中美，英，加拿大等国用于战争。1948年美国麻省理工学院率先开设了运筹学课程，运筹学成为一门学科。战后扩展到工业政府等部门。自60年代以来，由于计算机的应用运筹学得到了迅速的发展并开始普及。我国50年代中期由钱学森、许国志等学者引入我国，1958年建立了运筹学研究室。1962年管梅谷提出“中国邮路问题”。1970年华罗庚教授领导下在全国推广统筹法和优选法，取得显著成绩，在很多分支领域达到了当时的国际水平。1980年4月中国运筹学学会成立，基本形成了自己的理论体系，并在各领域中得到广泛应用。运筹学的产生和发展

数学对运筹学的作用——是有关理论和方法的研究基础，是建立运筹学模型的工具。计算机的发展，促进运筹学的进一步发展——高速、可靠的计算是运筹学解决问题的基本保障。

运筹学定义运筹学是运用科学的方法（如分析、试验、量化等）来决定如何最佳地运营和设计各种系统的一门学科。运筹学对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。

引入数学方法解决实际问题

--定性与定量方法结合系统与整体性

--从全局考察问题应用性

--源于实践、为了实践、服务于实践交叉学科

--涉及经济、管理、数学、工程和系统等多学科开放性

--不断产生新的问题和学科分支多分支

--问题的复杂和多样性运筹学的性质与特点线性规划数学规划非线性规划整数规划动态规划学科内容多目标规划双层规划组合优化最优计数问题网络优化排序问题统筹图随机优化对策论排队论库存论决策分析可靠性分析运筹学的主要内容

实际问题举例

对策问题（囚徒困境）

Resource-allocation资源分配Portfolioselection投资组合

Supplychainnetworkdesign供应链网络设计实际问题对策问题：囚徒困境

囚B囚A

坦白

抵赖

坦白-8，-80，-10

抵赖-10，0-1，-1实际问题资源分配实际问题

潘得罗索工业公司生产胶合板，根据厚度和所用木材的质量而有所不同。因为产品在一个竞争的环境中进行销售，产品的价格由市场决定。所以每个月管理层面临的一个关键问题是选择产品组合以获取尽可能多的利润。需要考虑当前生产产品必须的各种资源的可得数量。六项最重要的资源为（1）四种类型的原木（根据原木的质量区分）和（2）生产胶合板的两项关键作业的生产能力（模压作业和刨光作业）。

Portfolioselection投资组合实际问题比尔是Nesbit投资公司的财务主管，他必须组合长期市场有价证券的业务量的每月支付计划。证券业务量的金额高达$50,000,000。组合此业务量的有价证券必须很快确定下来，在风险控制限度内，以使得一定时限内的收益最大。Supplychainnetworkdesign供应链网络设计实际问题上海国美电器商场有限公司在上海的商场为什么圆形布点？围绕上海市外环线内部圆形均匀分布着9家商场，为什么只有一个配送中心，为什么要建在外环线的外面？你对这个问题如何分析！模型要素

变量—可控因素目标—优化的动力和依据约束—内部条件和外部约束研究内容

建模概念最优性条件算法灵敏度分析最优化模型

实例问题线性规划模型建模分析线性规划模型模型线性规划模型运筹学在管理中的应用生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等库存管理：多种物资库存量的管理，库存方式、库存量等运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等财务和会计：预测、贷款、成本分析、定价、证券管理、现金管理等***设备维修、更新，项目选择、评价，工程优化设计与管理等运筹学在物流中的运用规划论：线性规划可解决物资调运、配送和人员分派等问题；整数规划可以求解完成工作所需的人数、机器设备台数和厂、库的选址等；动态规划可用来解决诸如最优路径、资源分配、生产调度、库存控制、设备更新等问题。存储论：物资库存策略（量、时间、结构）网络（图）论：路线选择决策论：对策论是一种定量分析方法，可以帮助我们寻找最佳的竞争策略，以便战胜对手或者减少损失。例如在一个城市内有两个配送中心经营相同的业务，为了争夺市场份额，双方都有多个策略可供选择，可以运用对策论进行分析，寻找最佳策略。又如，某一地区，汽车运输公司要与铁路系统争夺客源，有多种策略可供选择，这也可用对策论研究竞争方案，等等排队论：排队论在物流过程中具有广泛地应用，例如机场跑道设计和机场设施数量问题，如何才能既保证飞机起降的使用要求，又不浪费机场资源；又如码头的泊位设计和装卸设备的购置问题，如何达到既能满足船舶到港的装卸要求，而又不浪费港口资源；再如仓库保管员的聘用数量问题、物流机械维修人员的聘用数量问题，如何达到既能保证仓储保管业务和物流机械的正常运转，又不造成人力浪费，等等，这些问题都可以运用排队论方法加以解决。运筹学解决问题的过程1）提出问题：认清问题2）寻求可行方案：建模、求解3）确定评估目标及方案的标准或方法、途径4）评估各个方案：解的检验、灵敏性分析等5）选择最优方案：决策6）方案实施：回到实践中7）后评估：考察问题是否得到完满解决1）2）3）：形成问题；4）5）分析问题：定性分析与定量分析。构成决策。教学计划

数学规划以线性规划和整数规划为教授重点，组合优化部分主要讲网络优化，而随机优化讲授对策论，其它部分作为选讲内容。教学方法

以授课为主，案例分析与上机实习相结合。而讲课中主要培养用最优化方法解决实际问题的能力。教学计划与方法考核内容

理论方法—笔试70%

应用能力—实验10%学习态度--平时20%考试与要求韩伯棠，管理运筹学，

高等教育出版社，北京，2000年徐光辉等，运筹学手册，

科学出版社，北京，1999年参考资料线性规划LinearProgramming

线性规划（LinearProgramming，简称LP）运筹学的一个重要分支，是运筹学中研究较早、发展较快、理论上较成熟和应用上极为广泛的一个分支。

1947年G.B.Dantying提出了一般线性规划问题求解的方法——单纯形法之后，线性规划的理论与应用都得到了极大的发展。

60年来，随着计算机的发展，线性规划已广泛应用于工业、农业、商业、交通运输、经济管理和国防等各个领域，成为现代化管理的有力工具之一。§1线性规划问题及其数学模型e.g.1

资源的合理利用问题问：如何安排生产计划，使得既能充分利用现有资源又使总利润最大？

表1

产品资源 甲乙库存量

A 1 3 60 B 1 1 40

单件利润

15 25

某工厂在下一个生产周期内生产甲、乙两种产品，要消耗A、B两种资源，已知每件产品对这两种资源的消耗，这两种资源的现有数量和每件产品可获得的利润如表1。第一章线性规划及单纯形法maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

解：

设x1，x2

为下一个生产周期产品甲和乙的产量；

约束条件：Subjecttox1+3x2≤60x1

+x2≤40x1，x2≥0目标函数：z=15x1+25x2

表1

产品资源 甲乙库存量

A 1 3 60 B 1 1 40

单件利润

15 25

决策变量§1线性规划问题及其数学模型e.g.2

营养问题

假定在市场上可买到B1,B2,…Bnn

种食品，第

i

种食品的单价是ci,另外有m

种营养A1,A2,…Am。设

Bj内含有

Ai

种营养数量为aij

(i=1~m,j=1~n)，又知人们每天对Ai

营养的最少需要量为bi。见表2：

表2

食品最少营养 B1B2…Bn

需要量

A1 a11 a12…a1n b1A2 a21 a22…a2n b2………………Amam1am2…amn

bm

单价

c1c2…cn

试在满足营养要求的前提下，确定食品的购买量，使食品的总价格最低。第一章线性规划及单纯形法

表2

食品最少营养 B1B2…Bn

需要量

A1 a11 a12…a1n b1A2 a21 a22…a2n b2………………Amam1am2…amn

bm

单价

c1c2…cn

解：

设xj

为购买食品

Bj

的数量(j=1,2,…,n)（i=1,2,…,m）xj≥0（j=1,2,…,n）§1线性规划问题及其数学模型三个基本要素：Note：1、善于抓住关键因素，忽略对系统影响不大的因素；2、可以把一个大系统合理地分解成n

个子系统处理。1、决策变量xj≥0

2、约束条件——一组决策变量的线性等式或不等式3、目标函数——决策变量的线性函数第一章线性规划及单纯形法max（min）z=c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn≤（或=，≥）b1

a21x1+a22x2+…+a2nxn≤（或=，≥）b2

……am1x1+am2x2+…+amnxn

≤（或=，≥）bm

xj

≥0（j=1,2,…,n） 其中aij、bi、cj（i=1,2,…,m；j=1,2,…,n）为已知常数线性规划问题的一般形式：§1线性规划问题及其数学模型线性规划问题的标准形式：maxz=c1x1+c2x2+…+cnxn

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

a21x1+a22x2+…+a2nxn=b2

……am1x1+am2x2+…+amnxn

=bm

xj

≥0（j=1,2,…,n）

bi≥0（i=1,2,…,m） 特点：1、目标函数为极大化；2、除决策变量的非负约束外，所有的约束条件都是等式，且右端常数均为非负；3、所有决策变量均非负。第一章线性规划及单纯形法如何转化为标准形式？1、目标函数为求极小值，即为：。

因为求minz等价于求max(-z)，令z’=-z，即化为：

2、约束条件为不等式，xn+1≥0松弛变量如何处理？§1线性规划问题及其数学模型

３、右端项bi<0时，只需将等式两端同乘（-1）则右端项必大于零

4、决策变量无非负约束

设xj

没有非负约束，若xj≤0，可令xj=-xj’

，则xj’≥0；

又若xj

为自由变量，即xj

可为任意实数，可令xj

=xj’-xj’’，且xj’,xj’’≥0第一章线性规划及单纯形法e.g.3试将LP

问题minz=-x1+2x2-3x3

s.t.x1+x2+x3

≤7x1-x2+x3≥2-3x1+x2+2x3=-5x1,x2≥0

化为标准形式。解：令x3=x4-x5

其中x4、x5

≥0；对第一个约束条件加上松弛变量x6

；对第二个约束条件减去松弛变量x7

；对第三个约束条件两边乘以“-1”；令z’=-z

把求minz

改为求maxz’maxz’=x1-2x2+3x4-3x5

s.t.x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=23x1-x2-2x4+2x5=5x1,x2,x4,x5,x6,x7≥0

§1线性规划问题及其数学模型LP的几种表示形式：§2线性规划问题的图解法定义1在LP问题中，凡满足约束条件(2)、(3)的解x=(x1,x2,…,xn)T

称为LP问题的可行解，所有可行解的集合称为可行解集（或可行域）。记作D={x|Ax=b,x≥0}。定义2

设LP问题的可行域为D，若存在x*∈D，使得对任意的x∈D

都有cx*≥cx，则称x*为LP问题的最优解，相应的目标函数值称为最优值，记作z*=cx*。§2线性规划问题的图解法maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

(40,0)(0,0)BC(30,10)O(0,20)AL1L2Z=250目标函数变形：x2=-3/5

x1+z/25x2x1最优解：

x1=30x2=10最优值：zmax=700B点是使z达到最大的唯一可行点第一章线性规划及单纯形法LP问题图解法的基本步骤：1、在平面上建立直角坐标系；2、图示约束条件，确定可行域和顶点坐标；3、图示目标函数（等值线）和移动方向；4、寻找最优解。§2线性规划问题的图解法maxz=3x1+5.7x2

s.t.x1+1.9x2≥3.8

x1-1.9x2≤3.8x1+1.9x2≤11.4

x1-1.9x2≥-3.8

x1，x2≥0x1x2ox1-1.9x2=3.8x1+1.9x2=3.8x1+1.9x2=11.4（7.6,2）D0=3x1

+5.7x2

maxZ

minZ（3.8,4）34.2=3x1

+5.7x2

可行域x1-1.9x2=-3.8(0,2)(3.8,0)

绿色线段上的所有点都是最优解,即有无穷多最优解。Zman=34.2第一章线性规划及单纯形法maxz=2x1+2x2s.t.2x1–x2≥2-x1+4x2≤4

x1，x2≥0OA(１,0)x1x2Note:可行域为无界区域，目标函数值可无限增大，即解无界。称为无最优解。可行域为无界区域一定无最优解吗？无可行解

指找不到一组变量能满足线性规划的所有约束条件的情况，也就是线性规划问题不存在可行解，或者说可行域是空集。例如线性规划问题：§2线性规划问题的图解法由以上两例分析可得如下重要结论：1、LP问题从解的角度可分为：⑴有可行解⑵无可行解有唯一最优解b.有无穷多最优解C.无最优解2、LP问题若有最优解，必在可行域的某个顶点上取到；若有两个顶点上同时取到，则这两点的连线上任一点都是最优解。§2线性规划问题的图解法图解法优点：直观、易掌握。有助于了解解的结构。图解法缺点：只能解决低维问题，对高维无能为力。例某工厂经市场调研，决定生产甲、乙两种产品，其单台利润分别为60元和30元，两种产品共用一种钢材、一台设备，其资源及获利情况如下：甲乙现有资源钢材消耗定额（公斤/台）24600公斤台时消耗定额（小时/台）31400小时配件（件/台）20250件利润（元）6030求利润最大的产品结构决策。作业练习②确定目标函数及约束条件——建立数学模型目标函数：③将不等式变为等式并在x1－x2坐标图中作出直线④最优点在凸边形的顶点，代入（1）式可得maxP解：①设变量：设甲生产x1台，乙生产x2台，可得最大利润约束条件：05050100100150150200250300350200250300350400x1x2A(0,150)B(100,100)C(125,25)D(125,0)(4)基、基向量、基变量⊙设r(A)=m,并且B是A的m阶非奇异的子矩阵（det(B)

0),则称矩阵B为线性规划问题的一个基。⊙矩阵B=（P1，P2….Pm)，其列向量Pj称为对应基B的基向量。⊙与基向量Pj

相对应的变量xj就称为基变量，其余的就称为非基变量。MaxS=CX（3-6）

s.t.AX=b（3-7）

X

0（3-8）基解.基可行解.可行基⊙对于某一特定的基B，非基变量取0值的解，称为基解。⊙满足非负约束条件的基础解，称为基可行解。⊙与基可行解对应的基，称为可行基。为了理解基解.基可行解.最优解的概念，用下列例子说明：例：maxS=2x1+3x2s.t.-2x1+3x2

63x1-2x2

6x1+x2

4x1,x2

0x243211234x1O-1-1-2-2-3-3-2x1+3x2=63x1-2

x2=6x1+x2=4AQ1Q2Q3Q4BmaxS=2x1+3x2s.t.-2x1+3x2

63x1-2x2

6x1+x2

4x1,x2

0x243211234x1O-1-1-2-2-3-3ABx243211234x1O-1-1-2-2-3-3-2x1+3x2

63x1-2

x2

6x1+x2

4AQ1Q2Q3Q4BmaxS=2x1+3x2s.t.-2x1+3x2

63x1-2x2

6x1+x2

4x1,x2

0满足约束条件

-2x1+3x2

63x1-2

x2

6x1+x2

4

与坐标系

x1,x2=0的交点（O，A，B，Q1，Q2，Q3，Q4）都是代表基解。注意：点（4，0）（0，4）不满足约束条件满足约束条件

-2x1+3x2

63x1-2

x2

6x1+x2

4

且满足

x1,x2

0的交点（O，Q1，Q2，Q3，Q4）都是代表基可行解。注意：点A，B不满足x1,x2

0点（O，Q1，Q2，Q3，Q4）刚好是可行域的顶点。x243211234x1O-1-1-2-2-3-3-2x1+3x2

63x1-2

x2

6x1+x2

4AQ1Q2Q3Q4B可行域x243211234x1O-1-1-2-2-3-3-2x1+3x2

63x1-2

x2

6x1+x2

4AQ1Q2Q3Q4B可行域本问题解的情况：基解：点（O，A，B，Q1，Q2，Q3，Q4）可行解：由点（O，Q1，Q2，Q3，Q4）围成的区域。基可行解：点（O，Q1，Q2，Q3，Q4）最优解：

Q3解的集合：非可行解可行解解的集合：基解解的集合：可行解基解基可行解解的集合：可行解基解基最优解基可行解线性规划（2）-单纯形方法单纯形方法基本思路：从可行域中某个基可行解（一个顶点）开始（称为初始基可行解）。如可能，从可行域中求出具有更优目标函数值的另一个基可行解（另一个顶点），以改进初始解。继续寻找更优的基可行解，进一步改进目标函数值。当某一个基础可行解不能再改善时，该解就是最优解。

由于军事上的需要，担任美国空军审计官的数学顾问旦茨基博士，根据在第二次世界大战中实际规划的经历，从1946年起就开始寻找一种方法，想用它较快地计算出包括进度、训练及后勤供应在内的规划问题。研究先从建立数学模型着手。在研究中，得到了投入—产出模型的启发，并在其他数学家的支持下，提出了解决线性规划问题极其有效的单纯形方法。单纯形法的由来

旦茨基教授在一次演说中，形象而风趣地说明了单纯形解法的奇效：设给70个人分配70项任务，每人一项。如果每人完成各项任务所需要付出的代价（时间、工资）都知道，要寻求代价最小的方案。所有的可行方案共有70！种。70！比还要大。如果用穷举法，逐个来比较的话，基本是不可能的。而用单纯形法软件，几秒钟就可以给出答案。

不仅如此，还能预测当方案中某因素发生变化，对决策目标的影响。神奇的单纯形法返回目录

线性规划问题的可行解有无穷多个，与某一凸集上的无穷多个点一一对应。要从无穷多个可行解中寻找最优解，几乎不可能。可以证明，最优解必定能取在凸集的顶点（极点、基本可行解）上，而极点的个数是有限的。当然，这个“有限”，数字往往相当可观，如前面的70！，要逐个比较的话，也不现实。而单纯形解法，用跨跃的方式，高速地优化基本可行解，迅速达到最优。单纯形法—跨跃式地寻求最优解优maxSS=ooABCDE凸集概念：

设D是n维线性空间Rn的一个点集，若D中的任意两点x(1),x(2)的连线上的一切点x仍在D中，则称D为凸集。凸集（非凸集）

开始，用单纯形表进行换基迭代。后来的改进单纯形法，大大减少了计算量。为利用计算机创造了条件。最初使用手摇和电动台式计算器，不能完成特大量的计算。由于线性规划应用广泛，大到整个国民经济计划，小到一个车间的生产安排，因此受到重视。解线性规划的能力迅速提高。1951年只能解约束条件为十几个方程的问题。现在，能解上万个方程的问题。且解题速度大大加快。专家们已经用单纯形解法开发出了计算效率极高应用软件。运用这个软件，输入数据，立即就可以打印出结果。

单纯形解法应用的发展过程例：一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？解：数学模型

maxS=6x1+4x2s.t.2x1+3x2

1004x1+2x2

120x1,x2

0引进松弛变量x3,x4

0数学模型标准形式：

maxS=6x1+4x2s.t.2x1+3x2+x3=1004x1+2x2+x4=120x1,x2,

x3,x4

0

A=（P1，P2，P3，P4）

=23104201

X=（x1,x2,x3,x4)B=(P3，P4

）=1001P3，P4线性无关，x3和x4是基变量，x1、x2是非基变量。

用非基变量表示的方程：

x3=100-2x1-3x2x4=120-4x1-2x2(I)S=6x1+4x2令非基变量（x1,

x2）t=（0，0）t

得基础可行解：

x(1)=(0,0,100,120)t

S1=0

经济含义：不生产产品甲乙，利润为零。分析：S=

6x1+

4x2（分别增加单位产品甲、乙，目标函数分别增加6、4，即利润分别增加6百元、4百元。）

增加单位产品对目标函数的贡献，这就是检验数的概念。

增加单位产品甲（x1）比乙对目标函数的贡献大（检验数最大），把非基变量x1换成基变量，称x1为进基变量，而把基变量x4换成非基变量，称x4为出基变量。确定了进基变量x1

，出基变量x4

以后，得到新的系统：

x3=40-2x2+（1/2）x4x1=30-（1/2）x2-（1/4）x4(II)S=180+x2-（3/2）x4令新的非基变量（

x2，x4）=（0，0）t得到新的基础可行解：x(2)=(30,0,40,0)t

S2=180经济含义：生产甲产品30个，获得利润18000元。

这个方案比前方案，但是否是最优？分析：S=180+x2-（3/2）x4非基变量x2系数仍为正数，确定x2为进基变量。在保证常数项非负的情况下，确定x3为出基变量。得到新的系统：

x1=20+（1/4）x3-（3/8）x4x2=20-（1/2）x3+（1/4）x4(III)S=200-（1/2）x3-（5/4）x4

令新的非基变量（x3,x4）t=（0,0）t得到新的基础可行解：x(3)=(20,20,0,0)t

S3=200经济含义：分别生产甲乙产品20个，可获得利润20000元。分析：S=200-（1/2）x3-（5/4）x4目标函数中的非基变量的系数无正数，S3=200是最优值，x(3)=(20,20,0,0)t是最优解。该企业分别生产甲乙产品20个，可获得最大利润20000元。X(3)=(20,20,0,0)t相当于Q2(20,20)X(1)=(0,0,100,120)t相当于O(0,0)X(1)=(0,0,100,120)t相当于O(0,0)X(2)=(30,0,40,0)t相当于Q1(30,0)X(2)=(30,0,40,0)t相当于Q1(30,0)X(3)=(20,20,0,0)t相当于Q2(20,20)举例:求解下列线性规划问题maxz＝1.5x1+2.4x2+0x3+0x4+0x5S.t.x1+x2+x3=1003x1+2x2+x4=1902x1+3x2+x5=240xj≥0(j=1,2,3…5)解：约束方程的系数矩阵为：1

1

100

A=(P1，P2，P3

，P4

，P5

）＝3

2

010

23

001初始可行基为：100B＝（P3，P4

，P5

）＝010001用非基变量表达基变量：

x3=100

－x1－1x2

x4=190

－3x1－2x2

x5=240

－2x1－3x2

将上式代入目标函数得：

z=0+１.５x1+2.4x2令非基变量为零，即令x1＝0，x2＝0得一个基可行解：x（0）＝（0,0,100,190,240)此时得z＝0非基变量的系数都是正数，因此将非基变量变换成基变量，目标函数的值就可能变大。取x2为入基变量（一般选择正价值系数最大的非基变量为入基变量，而2.4>1.5）于是还要确定基变量x3，x4，x5中的一个换出来成为非基变量。下面来确定换出变量：当x1=0时（先固定x1是两个非基变量中的一个）,x3=100

－1x2≥0x4=190

－2x2≥0x5=240

－3x2≥0要让x3，x4，x5非负，且有一个为0，只有选择x2≤80时，才能使x3,x4x5同时非负。(此时x3≥20>0，x4≥30>0，x5≥0)因此只有当x2=min(100/1,190/2,240/3)=80时,才能使x3,x4x5非负的同时，有一个原来的基变量x5取值为0，从而可以换出来成为非基变量。其中x3=20

>0，

x4=30

>0，

X5=0，取X5为出基变量（所谓的最小比值规则）x2≤100x2≤

95x2≤80x2≤80用非基变量表达基变量：

x3+x2=100-x1x3=20

-1/3x1+1/3x5

x4+2x2=190-3x1x4=30-5/3x1+2/3x5

3x2=240-2x1-

x5x2=80

-2／3x1-1/3x5

将上式代入目标函数得：z=192-0.1x1-0.8x5令非基变量为零，即x1＝0，x5＝0得一个基本可行解：x（1）＝（0,80,20,30,0),z=192由于非基变量的价值系数都是负数，而x1≥0，x5≥0，因此当x1＝0，x5＝0时，z取得最大值192。所以最优解

X*=x（1）＝（0,80,20,30,0),目标函数值z*=192

c

c1c2cmcm+1cm+2cncBxBx1x2xmxm+1xm+2xnbc1c2cmx1x2xm

100a’1m+1a’1m+2a’1n

010a’2m+1a’2m+2a’2n

001a’mm+1a’mm+2a’mnb’1b’2b’m检验数

0

00-z(0)用单纯形表求解问题例、用单纯形表求解LP问题解：化标准型表1：列初始单纯形表（单位矩阵对应的变量为基变量）

21000

01505100

0

24620100511001

21000

—24/65/1正检验数中最大者对应的列为主列主元化为1主列单位向量换出换入最小的值对应的行为主行表2：换基（初等行变换，主列化为单位向量，主元为1）

21000

01505100

2

412/601/600104/60-1/61

01/30-1/30

15/524/26/4

0*52*2/6+0*4/61-2/3=主元检验数>0确定主列

最小确定主列表3：换基

（初等行变换，主列化为单位向量，主元为1）

21000

015/20015/4-15/2

2

7/21001/4-1/213/2010-1/43/2000-1/4-1/2

最优解为X=(7/2,3/2,15/2,0,0)目标函数值Z=8.5

2*7/21*3/2+0*15/28.5检验数<=0例2、试利用单纯形表求例1中的最优解解：

得初始的单纯形表：初始基本可行解，Z=-1，122108x4-1-130400341017x51x1x2x3x4x5bXBCBΘ523-11C

换入变量，换出变量，２为主元进行旋转变换基本可行解，Z=15，1/2

1

1

1/2

04x33151-40-205/230-1/213x51

x1

x2

x3

x4

x5bXBCBΘ523-11C122108x4-1-130400341017x51x1x2x3x4x5bXBCBΘ523-11C8/27/1

最优解

最优值

换入变量，换出变量，５/２为主元进行旋转变换4/1/21/2

1

1

1/2

04x33151-40-203/5/25/230-1/213x51

x1

x2

x3

x4

x5bXBCBΘ523-11C02/513/5-1/517/5x3381/5

0-26/50-9/5-2/516/50-1/52/56/5x15x1x2x3x4x5bXBCBΘ

523-11Cmaxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

maxz=15x1+25x2+0x3+0x4s.t.x1+3x2+x3=60

x1

+x2++x4=40x1，x2

，x3

，x4≥0

00

ccBxB00x3x4检验数152500x1

x2

x3

x413101101152500b6040001θx(0)=(0,0,60,40)Tz0=0x21/3-500x(1)=(0,20,0,20)Tz1=500x10700x(2)=(30,10,0,0)Tz2=7001/2检验数都小于等于零x(2)为最优解

zmax

=70060/340/12531/312000-1/312020/3-25/3020/1/320/2/3152/32/310-1/23/2300-1/2100-5-10唯一最优解与无穷多个最优解若最终单纯形表的非基变量的检验数都小于零,则线性规划问题有唯一的最优解若最终单纯形表中存在某个非基变量,其检验数等于零,则该线性规划问题有无穷多个最优解.例3、用单纯形方法求解线性规划问题解：本题的目标函数是求极小化的线性函数，可以令则这两个线性规划问题具有相同的可行域和最优解，只是目标函数相差一个符号而已。

010103x220012-12x30-010103x224/1101004x303/1010103x40_101004x308

0000-1100-212x116

100-202/1100-212x500

120008/2120018x50

x1x2x3x4x5bXBCBΘ12000C最优解最优值2/23/1-利用单纯形法求解下列线性规划问题首先将线性规划标准化很明显可以以x4、x5作为初始基变量，得到初始单纯形如下：-22100CBXBx1x2x3x4x5b00x4x532-2-1-21100114-22100此时，x2的检验数大于0，还没有得到最优解。但是我们以x2作为换入变量，但是x2所在列所有系数都小于0，此时该线性规划存在无界解。单纯形法计算过程构造初始单纯形表对标准化后的线性规划问题，首先找出初始基变量，构造初始单纯形表，其中检验数由（2.18）计算。相应地可以得到初始基可行解，基可行解的目标函数值。最优性检验若得到单纯形表中所有的检验数都小于或等于零，则该单纯形表给出的基可行解就是最优解，终止计算。否则进行下一步。确定换入变量选择最大的正检验数对应的非基变量为换入变量。确定换出变量若换入变量（更一般地，若某个正检验数对应的变量）所作列的系数均小于或等于零，则线性规划问题为无界解，终止计算。否则用换入变量所作列的系数去除b列的对应数，在除得的商中选择最小者对应的基变量为换出变量。旋转运算确定换入和换出变量后得到新的基变量，然后以换入变量所在列、换出变量所在行交叉处的元素为主元，通过矩阵的初等行变换（一般不使用交换两行的运算）将约束方程组增广矩阵中主元变换为1，主元列的其它元素变换为零。从而得到一个新的单纯形表。然后回到第2步。第3章线性规划对偶理论及其应用例1

穗羊公司的例子3.1线性规划的对偶问题生产计划问题（LP1）III每周可使用量A（千克）125B（吨）214C（百工时）439单位产品利润（万元）32III每周可使用量A（千克）125B（吨）214C（百工时）439单位产品利润（万元）32穗羊公司如果要出让其拥有的资源:单价y1,y2,y3y1y2y3生产每件产品的资源出让后获得的收益应该不低于该件产品的收益.产品I:产品II:接手其所有资源的厂家期望出价越低越好:资源定价问题（LP2）比较原问题（生产计划）对偶问题（资源定价）3.1.2规范形式的线性规划问题原问题（LP）对偶问题（DLP）

规范形式最大化问题:约束条件全为型决策变量全部非负最小化问题:约束条件全为型决策变量全部非负规范形式的对偶关系原问题对偶问题目标函数:maxCX目标函数:minb´Ym个约束条件:AXbm个决策变量:Y0n个决策变量:X0n个约束条件:A´YC´原问题对偶问题非规范形式的对偶关系对非规范形式的对偶关系，只需对上述表进行相应修改即可：例如对于一个最小化问题，若某个决策变量yi

0,则其对偶的约束条件为型的;若其某个约束条件是型,则其对应的对偶变量是非正的.3.1.3非规范形式线性规划的对偶问题1变量取值范围不符合非负要求的情况3.1.3非规范形式线性规划的对偶问题2约束方程不是“≤”的情况

3.1.4总结约束条件对变量，变量对约束条件；正常对正常，不正常对不正常；变量正常是非负，约束条件正常看目标(max≤，min≥)。

例2.5求解下面线性规划的对偶规划LPDLP3.2对偶规划的基本性质3.2.1对称性定理：线性规划的对偶问题的对偶问题是原问题。证明：

对偶定义令w’=-w；约束方程左右同乘“-1”对偶定义令z=-z’；约束方程左右同乘“-1”3.2对偶规划的基本性质3.2.2弱对偶性定理：如果X、Y分别是原问题和对偶问题的一个可行解，则其对应的原问题的目标函数值不大于对偶问题的目标函数值，也即证明：因为X、Y分别是原问题（3.1）与对偶问题（3.2）的可行解，故：

所以推论一：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。推论二：如果原问题存在无界解，则对偶问题一定无可行解；反之，如果对偶问题存在无界解，原问题也一定不存在可行解。3.2.3最优性定理也就是说若原问题与对偶问题各存在一个可行解,且它们对应的目标函数值相等,则它们分别是原问题与对偶问题最优解.如果原问题存在最优解X*，则其对偶问题一定具有最优解Y*，且初始单纯形表的矩阵表示CBCN0CSxBxNxS0BNISbCBCN00最优单纯形表的矩阵表示CBCN0CBxBxNxSCBIB－1NB-1B-1b0CN-CBB－1N-CBB－1CBB－1b令则Y*>=0,且故Y*即为对偶问题的最优解。又因为3.2.4强对偶性定理（对偶定理）B-1B-1B-1B-1在初始单纯形表中单位矩阵经过迭代后变为基矩阵B的逆在初始单纯形表给出的解中基变量Xs=b,而在迭代后的表给出的解中基变量

XB=B-1b系数矩阵的变化:[A,I]B-1[A,I]在初始单纯形表中变量xj的系数为Pj经过迭代后变为Pj′,并且Pj′=B-1Pj若迭代后的单纯形表为最终表则该表也同时给出对偶问题的最优解

32000

CBXBx1x2x3x4x5b0x3

0015/2-3/23/23x1

1003/2-1/23/22x2010-211

000-1/2-1/213/2

32000

CBXBx1x2x3x4x5b0x3

1210050x4

2101040x5430019

320000例3.1的初始表与最终表B?B-1例3.1的原问题与对偶问题最终单纯形表的比较

32000

CBXBx1x2x3x4x5b0x3

0015/2-3/23/23x1

1003/2-1/23/22x2010-211

000-1/2-1/213/2

54900

y1y2y3y4y5

4y2-5/210-3