第1章：线性规划

第一章：线性规划1.1线性规划(LinearPrograming---L.P.)概述一、L.P.概念：

L.P.是目前应用最广泛的一种系统优化方法。其理论已十分成熟，广泛应用于工农业生产和经济管理等领域。以数学为工具，在一定资源条件下，如何合理安排，取得最大经济效果。二、发展史：

30年代末(苏)康特罗维奇书“生产组织与计划中的数学方法”，为L.P.建立数学模型和求解奠定了基础。

1、(美)库普曼(T.C.Koopmans)建立了L.P.数学模型，获诺贝经济奖。

2、(美)丹泽(G.B.Dantzig)在1947年提出求解L.P.数模的通用方法---单纯形法。

1946年，世界上第一台计算机问世，使单纯形法处理大规模L.P.数模成为可能。三、L.P.问题的求解过程

1、将实际问题转化为数学模型(数学公式)：建模。

2、求解数学模型：

图解法：适合于2个变量的L.P.数学模型。

单纯形法：适合于任意个变量的L.P.数学模型。

3、利用数学模型的最优解获得原问题的最优决策方案。11.2线性规划及其数学模型一、L.P.问题

例：某厂生产甲、乙两种产品，均需在A、B、C三种不同的设备上加工，产品加工所需工时、销售后能获得的利润及设备有效工时数如下表。问：如何安排生产计划，才能使该厂获得总利润最大？

解:①设甲、乙产品产量分别为x1、x2公斤———决策变量，简称变量

②设总利润为Z，则

MaxZ=70x1＋30x2———目标函数

③设备可用工时数限制———约束条件

s.t.3x1+9x2≤540A设备可用工时约束

5x1+5x2≤450B设备可用工时约束

9x1+3x2≤720C设备可用工时约束

x1,x2

≥0非负约束

设备产品

ABC利润(元/公斤)

甲乙3955937030限制工时

540450720单耗2二、L.P.数学模型的经济含义

1、数学模型的三要素:

①.有一组待确定的决策变量。如(x1,x2)为一个具体行动方案。

②.有一个明确的目标要求(Max或Min)。如要求利润最大。

③.存在一组约束条件。如设备A、B、C三种资源的约束。

2、数学模型中系数的含义:

①.目标函数中决策变量的系数70,30------叫价值系数，表单位产品提供的利润(元/件)；

②.约束条件左边决策变量的系数------叫约束条件系数或单耗(台时、kg、kg/件)；

③.约束条件右边常数540,450,720------叫限制常数，表现有的资源限量。

三、线性规划数学模型的解

1、可行解：满足约束条件②、③、④、⑤的所有解。

2、可行解域：所有可行解的集合，上图阴影部分。

3、最优解：满足目标函数①的可行解。

4、基本解：所有约束条件直线的交点对应的解，即上图所有的实心点和空心点对应的解。

5、基本可行解：既是基本解又是可行解，即上图所有的实心点对应的解。它满足两个条件：其一是约束条件直线的交点对应的解；其二是可行解，即满足所有的约束条件，在可行解域内。

oX1X2

②③④⑤⑤ahbkMaxZ=70x1＋30x2…①s.t.3x1+9x2≤540…②5x1+5x2≤450…③9x1+3x2≤720…④x1,x2

≥0…⑤3

1、线性规划模型：如果以上数学模型中的方程均是线性方程，则该数模称为线性规划数模。

2、非线性规划模型：如果以上数学模型中的方程至少有一个方程是非线性方程，则该数模称为非线性规划数模。

四、L.P.的一般形式

Max(Min)Z=c1

x1+c2

x2+---+cn

xn

a11

x1+a12

x2+---+a1n

xn

≤(≥,=)b1

a21

x1+a22

x2+---+a2n

xn≤(≥,=)b2s.t.-----------------------------------------------------

am1

x1+am2

x2+---+amn

xn≤(≥,=)bm

xj≥0,j=1---n

41.3线性规划问题的建模确定决策变量；确定目标函数；列出约束条件。一、运输问题建模:编制最优运输计划,使总运费最少例：某地有三个有色金属矿A1、A2、A3，生产同一种金属矿石，A1矿的年产量为100万吨，

A2矿为80万吨，A3矿为50万吨。矿石全部供应四个冶炼厂，B1厂的全部需求量为50万吨，

B2厂70为万吨，B3厂为80万吨，B4厂为30万吨。产量恰好等于总需求量，矿石由各矿山运到冶炼厂的单位运价已知，如下表。问如何安排运输，使各矿山的矿石运到冶炼厂，满足各厂的需要，且运输费用最小，试建立该问题的数学模型？

.确定决策变量:设

xij

为从第i个矿山到第

j

个冶炼厂的矿石运输量(万t)..确定目标函数:设总运费为Z,则

MinZ=1.5x11+2x12+0.3x13+3x14+7x21+0.8x22+1.4x23+2x24+1.2x31+0.3x32+2x33+2.5x34

.确定约束条件:

x11+x12+x13+x14=100s.t.x21+x22+x23+x24=80x31+x32+x33+x34=50x11+x21+x31=50x12+x22+x32=70x13+x23+x33=80x14+x24+x34=30

xij

≥0,i=1~3;j=1~4.5二、合理下料问题建模:寻求最佳下料方式,使余料最少.

例有一批长度为180公分的钢管,需截成70、52和35公分三种管料。它们的需求量应分别不少于

100、150和100个。问应如何下料才能使钢管的余料为最少?

解:

.确定决策变量:

设xj

为第j种下料方式所用的钢管根数..确定目标函数:设总余料为Z,则

MinZ=5x1+6x2+23x3+5x4+24x5+6x6+23x7+5x8(公分).确定约束条件:

2x1+x2+x3+x4≥100s.t.2x2+x3+3x5+2x6+x7≥150x1+x3+3x4+2x6+3x7+5x8≥100

xj≥0,且为整数.

6三、人员分派问题建模:合理分派人员,使总效率最大.例：设有四件工作分派给四个人来做，每项工作只能由一人来做，每个人只能做一项工作。希望适当安排人选，发挥各人特长又能使总的效率最大(或完成最快,或费用最少)。表1.5表示各人对各项工作所具有的工作效率。

.确定决策变量:设xij

为分派第i个人从事第

j

项工作,xij=1,0(分派与否).确定目标函数:设总效率为Z,则

MaxZ=0.6x11+0.2x12+0.3x13+0.1x14+0.7x21+0.4x22+0.3x23+0.2x24

+0.8x31+1.0x32+0.7x33+0.3x34+0.7x41+0.7x42+0.5x43+0.4x44

.确定约束条件:

x11+x12+x13+x14=1s.t.x21+x22+x23+x24=1x31+x32+x33+x34=1x41+x42+x43+x44=1x11+x21+x31+x41=1x12+x22+x32+x42=1x13+x23+x33+x43=1x14+x24+x34+x44=1

xij=1,0,i=1~4;j=1~4.7四、投资方案选择问题建模:合理选择方案,使总收益最大.例：某炼油公司为提高炼油能力和增加企业经济效益,经研究有五种技术改造的投资方案可供选择，它们所需的投资费用年收益如下表所示。其中:方案1和方案2只能选择其中一种，不能兼而实现，并且，如选择方案2，则方案3必须同时选择，或者都不选择。

现该公司可供支配的资金总额为：第一年有650万元，第二年仅有460万元。技术改造的结果要求至少应增加出油能力500桶/天，但又不得超过1100桶/天，试确定该公司总经济效益最大的投资方案。8

.确定决策变量:设xj

为第j方案的取舍，

xj=1,0(取舍).确定目标函数:设总经济效率为Z,则

MaxZ=100x1+200x2+50x3+30x4+20x5(万元).确定约束条件:

200x1+300x2+150x3+100x4+50x5≤650s.t.200x1+150x2+50x3+70x4+40x5≤460500x1+1000x2+100x3+50x4+20x5≥500500x1+1000x2+100x3+50x4+20x5≤1100x1+x2≤1-x2+x3=0

xj=0,1,j=1~5.9五、选点决策问题:合理选点,使总利率最大.例：某公司拟在A、B、C、D、E五个城市中建立若干产品经销联营点，各处设点都需资金、人力、设备等，需求量以及能提供的利润各处不同，有些点可能亏本，但却能获得贷款和人力等。假设数据已知，见下表，为使总利润最大，问厂方应作何种最优选点决策？

.确定决策变量：要求从五个城市中选择最优产品经销联营点，设决策变量xj(j=1,2,…,5)表示第j个城市的取舍，所以决策变量xj的取值仅有1和0两种值。.确定目标函数：要求公司总利润Z最大，则

MaxZ＝4.5x1＋3.8x2＋9.5x3－2x4－1.5x5

.确定约束条件:4x1＋6x2＋12x3－8x4＋x5≤20s.t.5x1＋4x2＋12x3＋3x4－8x5≤15x1＋x2＋x3≤2

xj＝0、1，j=1,…,5

资源城市应投资(百万元)应投人力（人）应投设备（套）利润(万元)A45145B64138C1212195D-830-2E1-80-1.5资源限量20152101.4线性规划图解法一、适用范围：

二个变量的数学模型。二、求解步骤：

MaxZ=70x1＋30x2…①s.t.3x1+9x2≤540…②5x1+5x2≤450…③9x1+3x2≤720…④x1,x2

≥0…⑤

oX1X2

②③④⑤⑤ahbk7030(75,15)最优解为：X*=(75，15)TZ*=5700

第二步：确定可行解域，即所有约束方程图形的公共部分；

第三步：绘出目标函数直线，根据目标函数的要求以及与决策变量的关系，找出直线移动方向。

第五步：确定最优解及最优目标函数值。

第一步：将所有约束方程用图形绘出；

第四步：目标函数直线向着可行解域的右上方平行移动，直至与可行解域相切为止，这个切点就是最优点，对应的解就是最优解。

所以，产品甲、乙分别安排产量75Kg、15Kg，可使工厂获利最大为5700元。11三、LP几何意义

oX1X2

②③④⑤⑤ahbk

1、闭合的可行解域是凸多边形(凸集)。

2、可行解域有若干个顶点：O、a、h、k、b。对应的解叫基本可行解。

3、最优解若唯一存在，则必是顶点中的某一个。12四、特殊的数学模型

1、有无穷多个最优解：若有两个最优解，则必有无穷多个最优解。如下例数学模型：MaxZ=x1＋2x2s.t.x1+x2≤6x1+2x2≤8x2≤3x1,x2

≥0

OX1X2Q1Q2Q3Q4此线性规划问题的最优解在Q2Q3线段上，如上图所示，即线段Q2Q3上任意一点都使Z取得相同的最大值，这个线性规划问题有无穷多最优解。因此，若有两个最优解，则必有无穷多个最优解。

13四、特殊的数学模型

2、解无界：可行解域无界，目标值无限增大。如下例数学模型：

MaxZ=x1＋x2s.t.-2x1+x2≤4x1-5x2≤2x1,x2

≥0

OX1X2用图解法求解结果见上图所示，从图中可以看到，该问题可行解域无界，目标函数值可以增大到无究大，称这种情况为无界解或无最优解。

14四、特殊的数学模型

3、无可行解域：约束条件相互矛盾。如下例数学模型MaxZ=3x1＋4x2s.t.x1+x2

≥6x1≤2x2≤3x1,x2

≥02OX1X2636该问题可行解域为空集，如上图所示，即无可行解域，当然也无最优解。151.5线性规划单纯形法

一、适用范围

任意个变量的数学模型。二、原理从一初始顶点(初始基本可行解)出发，沿可行解域的边缘逐个验算遇到的顶点(基本可行解)，直至找最优点(最优解)为止。MaxZ=70x1＋30x2…①s.t.3x1+9x2≤540…②5x1+5x2≤450…③9x1+3x2≤720…④x1,x2

≥0…⑤

oX1X2

②③④⑤⑤ahbk最优解为：X*=(75，15)TZ*=5700

16三、LP数模的标准型条件一:具有等式约束方程组；条件二:右边常数非负；条件三:变量非负；条件四:目标函数为Max型。MaxZ=70x1＋30x2…①s.t.3x1+9x2≤540…②5x1+5x2≤450…③9x1+3x2≤720…④x1,x2

≥0…⑤对设备A：3x1+9x2

≤540，引入非负松弛变量x3，加到不等式的左边得

3x1+9x2+x3

=540

实际使用的

空闲工时(≥0)限制工时

工时数

(起松弛作用,叫松弛变量)

MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720

xj

≥0，j=1,～,5则原数模的标准型为：对设备B：5x1+5x2

≤450，引入非负松弛变量x4，加到不等式的左边得

5x1+5x2+x4

=450

实际使用的

空闲工时(≥0)限制工时

工时数

(起松弛作用,叫松弛变量)

对设备C：9x1+3x2

≤720，引入非负松弛变量x4，加到不等式的左边得

9x1+3x2+x5

=720

实际使用的

空闲工时(≥0)限制工时

工时数

(起松弛作用,叫松弛变量)

17四、LP数模的规范型条件一:具有标准型；条件二:约束方程组系数矩阵中含有至少一个单位子矩阵(对应的变量叫基变量)；条件三:目标函数中不含基变量。MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720

xj

≥0，j=1,～,5；x3,x4,

x5为基变量则原数模的规范型为：MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720

xj

≥0，j=1,～,5

x3x4x539100100A=55010中有B=010=（

3、

4、

5）=E93001001一组基

1

2

3

4

5

x1x2x3x4x5

非基变量基变量基的作用是:可以得到初始基本可行解(即初始顶点--通常是原点O),是单纯行迭代的基础。18五、最优解寻求步骤第一步、确定初始基本可行解：利用规范型数模，令非基变量x1、x2=0，求出基变量x3、x4、x5。

得初始基本可行解为：

X(1)=（

x1,x2,

x3,x4,x5）T=(0,0,

540,450,720

)T

甲乙设备A设备B设备C→空闲工时

Z(1)=0，利润为0未生产，资源全部闲置(对应原点O)(x1、

x2

为非基变量，x3、x4、x5为基变量)

第二步、判断X(1)是否最优：检查用非基变量表达的目标函数中非基变量前的系数(叫检验数)。

MaxZ=70x1+30x2

因为检验数70、30>0，所以当x1

和x2从0增大时，Z也会增大。故当前解非最优。当前解须改进，寻求更好的解。

oX1X2

②③④⑤⑤ahbkMaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720

xj

≥0，j=1,～,5；x3,x4,

x5为基变量19第三步、确定改进的非基变量及其上界:

选择使目标Z值改变得最快的

非基变量优先改进。

(1)、确定非基变量

x1优先改进：因为从目标函数MaxZ=70x1+30x2可以看出

x1增加1，可使目标Z增加70；x2增加1，目标Z能增加30。

(2)、x1增加的上界是80：因为从约束方程组可以得出(从资源最优利用考虑，令x3、x4、x5

=0)x1=180-3x2-(1/3)x3=180---目前可用的设备A台时数最多可生产甲产品180Kg。

x1=90-x2-(1/5)x4=90---目前可用的设备B台时数最多可生产甲产品90Kg。

x1=80-(1/3)x2-(1/9)x5=80---目前可用的设备C台时数最多可生产甲产品80Kg。

取最小值即非基变量x1增加的上界是80-----最小比值规则。此时x2=0。第四步、确定新解：将x1=80，

x2=0代入约束方程组中求出x3、x4、x5的值。得新基本可行解为：

X(2)=（x1,x2,

x3,x4,x5）T=（80,0,300,50,0）T

甲乙设备A设备B设备C→空闲工时(对应点a)

Z(2)=5600，利润为5600(x2、

x5

为非基变量，x1、x3、x4为基变量)MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720

xj

≥0，j=1,～,5；x3,x4,

x5为基变量

oX1X2

②③④⑤⑤ahbk20第五步、判断X(2)是否最优：检查用非基变量表达的目标函数中非基变量前的系数(叫检验数)。

MaxZ=70x1+30x2=70[80-(1/3)x2-(1/9)x5]

+30x2=5600+(20/3)x2-(70/9)x5

因为检验数20/3>0，所以当x2

从0增大时，Z也会增大。故当前解非最优。当前解须改进，寻求更好的解。第六步、确定改进的非基变量及其上界:选择使目标Z值改变得最快的非基变量优先改进。

(1)、确定非基变量

x2改进：因为目标函数中只有一个正检验数。

(2)、x2增加的上界是15：因为从约束方程组可以得出(从资源最优利用考虑，令x3、x4、x5

=0)x2=60-(1/3)x1-(1/9)x3=60-(1/3)x1→x2=37.5

x2=90-x1-x4=90-x1→x2=15

x2=240-3x1-(1/3)x5=240-3x1→

x1=80-(1/3)x2代入上面二式

取前二式的最小值即非基变量x2增加的上界是15-----最小比值规则。此时x1=75。MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720

xj

≥0，j=1,～,5；x3,x4,

x5为基变量

oX1X2

②③④⑤⑤ahbk21第七步、确定新解：将x1=75，

x2=15代入约束方程组中求出x3、x4、x5的值。得新基本可行解为：

X(3)=（

x1,x2,

x3,x4,x5）T=（75,15,

180,0,0）T

甲乙设备A设备B设备C→空闲工时

Z(3)=5700，利润为5700(x4、

x5

为非基变量，x1、x2、x3为基变量)(对应点h)第八步、判断X(3)是否最优：检查用非基变量表达的目标函数中非基变量前的系数(叫检验数)。

MaxZ=70x1+30x2=

5700-2x4-(20/3)x5

由5x1+5x2+x4

=4509x1+3x2+x5

=720

解得x1=75+(1/10)x4-(1/6)x5，x2=15-(3/10)x4+(1/6)x5，代入目标函数中得

MaxZ=70x1+30x2=70[75+(1/10)x4-(1/6)x5]

+30[15-(3/10)x4+(1/6)x5]=

5700-2x4-(20/3)x5

因为检验数-2、-20/3<0，所以当前解最优。最优解为：

X*=（75,15,

180,0,0）T，Z*=5700

所以，产品甲、乙分别安排产量75Kg、15Kg，可使工厂获利最大为5700元。MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720

xj

≥0，j=1,～,5；x3,x4,

x5为基变量

oX1X2

②③④⑤⑤ahbk22将数模写成如下形式：

3x1+9x2+x3

=540

5x1+5x2+x4

=450

9x1+3x2+x5

=720-Z+70x1＋30x2=0

列出以下单纯形表进行旋转运算

：六、单纯形法表格化-----单纯形表MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720

xj

≥0，j=1,～,5；x3,x4,

x5为基变量

oX1X2

②③④⑤⑤ahbk23基x1x2x3x4x5b

x339100540x455010450x593001720-Z70300000

70300000001809080x3x4x1-Z11/3001/9800810-1/3300010/301-5/950020/300-70/9-560037.515240x3x2x1-Z0103/10-1/615001-12/51180100-1/101/675000-2-20/3-5700基本可行解X(1)=(0，0，540，450，720)TZ(1)=0对应原点OX(2)=(80，0，300，50，0)TZ(2)=5600对应顶点aX(3)=(75，15，180，0，0)TZ(3)=5700对应顶点h最优解为：X*=X(3)=(75，15，180，0，0)TZ*=Z(3)=

5700

007003070将入基列变成单位向量列将入基列变成单位向量列24问题一：若最大检验数有两个或两个以上并且相等，应如何确定入基变量(可任选)。问题二：若最小比值有两个或两个以上并且相等，应如何确定出基变量(可任选)。问题三：原问题无解的判断：入基列元素全部非正。基x1x2x3x4x5b

1

2x33910054018060x4550104509090x59300172080240-Z70700000基x1x2x3x4x5b

x33-9100540x450010450x59-3001720-Z70300000基x1x2x3x4x5b

x339100540180x45501045080x59300172080-Z70300000MaxZ=70x1＋30x2s.t.3x1-9x2≤5405x1≤4509x1-3x2≤720x1,x2

≥0b

935131/3025七、单纯形的经济信息

MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720

xj

≥0，j=1,～,5；x3,x4,

x5为基变量

1、决策变量的解：x1=75公斤,x2=15公斤，提供最优决策方案。

2、松弛变量的解：最优决策条件下，提供资源的剩余量。

x3=180,设备A的闲置台时。

x4=0,设备B的闲置台时。

x5=0,设备C的闲置台时。

3、产品相关价值系数：改化或约化的价值系数(新解下的价值系数---单位产品提供的利润)。

o:X(1)=(0,0,540,450,720)T；MaxZ=0+70x1+30x2+0x3+0

x4+0

x5a:X(2)=(80,0,300,50,0)T；MaxZ=5600+0x1+

(20/3)x2+0x3+0x4-(90/7)x5h:X(3)=(75,15,180,0,0)T；MaxZ=5700+0x1+0x2-0x3-2x4-(20/3)x5

反映各产品有相互制约作用，起了考虑市场信息和规划方案改变对利润的综合影响。

oX1X2

②③④⑤⑤ahbk最优解为：X*=(75，15)TZ*=5700

26

4、资源影子(潜在)价格

⑴影子价格的概念:最优规划条件下，单位资源能够带来的目标增量。是反映资源最优利用的一种虚拟价格，也叫资源边际利润。

⑵影子价格的计算:最优表中松弛变量检验数的相反数或最优目标函数中松弛变量系数的相反数。基x1x2x3x4x5bx3001-12/51180x20103/10-1/615x1100-1/101/675-Z000-2-20/3-5700检验数：0-2-20/3影子价格：0220/3MaxZ=5700+0x1+0x2-0x3-2x4-(20/3)x5当设备A增加1个台时，此时x3=-1，则利润Z增加0元，为5700+0元；当设备B增加1个台时，此时x4=-1，则利润Z增加2元，为5700+2元；当设备C增加1个台时，此时x5=-1，则利润Z增加20/3元，为5700+20/3元。结论：设备A的影子价格为0(元/台时)，

设备B的影子价格为2(元/台时)，

设备C的影子价格为20/3(元/台时)。

27⑶影子价格的应用①在企业内部：指出挖潜方向。原理：影子价格高的资源潜力大，影子价格低的资源潜力小。设备A的影子价格为0元/台时：已有180台时剩余，缺少180台时不会造成任何损失，增加数量

也不会增加利润，为非关键资源，不应对此花费代价。设备B的影子价格为2元/台时：缺少

1台时将造成

2元的损失，增加1

台时将增加

2元的利润。

为关键资源，应重点挖潜(比如增加数量)，其重要程度次之。设备C的影子价格为20/3元/台时：缺少

1台时将造成

20/3元的损失，增加1

台时将增加

20/3

元的利润。为关键资源，应重点挖潜(比如增加数量)，其重要程度最高。②在企业外部：制定外单位来料加工时的收费用标准：合计收费0+900+4800=5700元。设备A的收费用标准为0元/台时，现有540台时，共收费0×540=0元(不考虑收费)；

设备B的收费用标准为2元/台时，现有450台时，共收费2×450=900元；

设备C的收费用标准为20/3元/台时，现有720台时，共收费20/3×720=4800元；

衡量资源的使用是否合理：同一种资源在不同的地方和不同的时期，其影子价格不相同。影子价格高的说明使用合理，否则说明使用不合理。应建立动态影子价格体系，物尽其用。

281.6人造基下的单纯形法---大M法

一、什么时候会出现人造基

例：求解下列数模

MinZ=x1－2x2s.t.x1+x2≥2-x1+x2≥1x2≤3x1,x2

≥0当数模的约束条件出现”＝”或”≥”时，要将数模化为规范型，一般情况下就需要引入人工变量形成人造基。

标准化：引入非负松弛变量x3、x4、x5

令Z=-D,化成标准型如下

MaxD=-x1+

2x2s.t.x1+x2-x3

=2-x1+x2-x4

=

1x2+x5=3

xj≥0，j=1~5规范化：引入非负人工变量x6、x7

化成规范型如下

MaxD=-x1+

2x2s.t.x1+x2-x3

+x6=2-x1+x2-x4

+x7=

1x2+x5=3

xj≥0，j=1~7，x5,x6,x7为基变量规范型解基的形成只要三种可能：①由决策变量自然形成的解基：由具体的物理变量组成，可含在最优解里，②由添加松弛变量形成的解基：每步迭代后的解均是可行解。③由引入人工变量形成的解基(人造基)：由虚拟人工变量组成，改变了原s.t.。29

二、大M法例：求解下列数模

MinZ=x1－2x2

…①s.t.x1+x2≥2

…②-x1+x2≥1

…③x2≤3

…④x1,x2

≥0

…⑤

-1o123x1-2-1123x2②③④

abch

规范化：引入非负松弛变量x3、x4、x5

和非负人工变量x6、x7

化成规范型如下

s.t.x1+x2-x3

+x6=2-x1+x2-x4

+x7=

1x2+x5=3

xj≥0，j=1~7，x5,x6,x7为基变量将目标函数变形为：MinZ=x1-2x2+M(x6+x7)，其中M为很大很大的正常数。

MinZ=x1-2x2+M(3-2x2+x3+x4)=

3M+x1-(2M+2)x2+Mx3+Mx4

令Z=-D，将目标函数规范化得：

MaxD=-3M-x1+(2M+2)x2-Mx3-Mx4

单纯形表计算如下：30不可行解

X(1)

=(0，0，0，0，3，2，1)TD(1)=-3M(对应O点)X(2)

=(0，1，0，0，2，1，0)TD(2)=2-M(对应a点)初始基本可行解X(3)

=(1/2,3/2,0,0,3/2,0,0)TD(3)=5/2(对应b点)X(4)

=(0，2，0，1，1)TD(4)=4(对应C点)X(5)

=(0，3，1，2，0)TD(5)=6(对应h点)X*

=(0，3，1，2，0)TZ*=-D(5)=-6311.7线性规划数学模型计算机求解

一、求解软件QSB介绍

QSB是专门用来求解运筹学模型的软件。数学模型不需要标准化和规范化，直接将原始数学模型输入计算机即可求解。

二、求解举例

MaxZ=70x1＋30x2…①s.t.3x1+9x2≤540…②5x1+5x2≤450…③9x1+3x2≤720…④x1,x2

≥0…⑤32

一、灵敏度分析的概念

1、可用资源的数量发生变化，会使得右边限制常数bi发生变化。2、由于市场条件发生变化，会使得价值系数Cj

发生变化。3、由于生产工艺的改进，会使得单耗(约束条件系数或叫技术系数)aij发生变化。4、为使资源得到充分利用，增加生产项目，会增加变量个数。5、为提高产品质量，增加资源种类或生产工艺，会增加约束条件个数。各类因素发生变化：对原规划问题最优解(原最优决策方案)的影响分析；这些因素在什么范围内变化时，原规划问题最优解或最优基不变。各类因素发生变化分为以下两种情况：第一种情况：多种因素同时发生变化，原最优解可能发生变化，一般从头开始迭代计算，求出新最优解。第二种情况：单种因素单方面发生变化，原最优解可能发生变化，此时不必从头开始迭代计算，只要在原最优表中进行分析计算，即可求出新最优解。

以下只讨论第二种情况。第二章：灵敏度分析33二、单纯形表的逆矩阵及各表之间的运算关系

基x1x2x3x4x5bx339100540x455010450x593001720-Z70300000x30810-1/3300x4010/301-5/950x111/3001/980-Z020/300-70/9-5600x3001-12/51180x20103/10-1/615x1100-1/101/675-Z000-2-20/3-5700非基区

基区

表的逆矩阵(基区的系数构成的矩阵)34三、单纯形表的逆矩阵及各表之间的运算关系

39100540550104509300172070300000最优表

初始表001-12/511800103/10-1/615100-1/101/675000-2-20/3-57001-12/51003/10-1/600-1/101/600-2-20/31=

×

最优表逆矩阵B-1-1/63/1001-12/511/6-1/100001=

×

539，