卫生管理运筹学课件

*第一节

基本概念*第二节线性规划问题的图解法*第三节线性规划模型的解及性质*第四节单纯形法

第五节对偶规划第六节运输问题及表上作业法

线性规划

一、单纯形法的解题过程二、线性规划模型的变换三、单纯形法的计算方法四、一般情况的处理--人工变量法

（2）检验、确定进基变量如果任何一个非基变量的值增加都不能使目标函数值增加，即所有检验数非正，则当前的基本可行解就是最优解，计算结束。若存在检验数大于0，那么绝对值最大者对应的非基变量xj称为“进基变量”，转（3）。单纯形法的基本步骤:

这个基变量xr称为出基变量。转（4）。如果进基变量的值增加时，所有基变量的值都不减少，即所有aij非正，则表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加，此时，不存在有限最优解，计算结束。(3)确定出基变量满足单纯形法的基本步骤:

（4）迭代运算将进基变量作为新的基变量，出基变量作为新的非基变量，确定新的基、新的基本可行解和新的目标函数值。在新的基变量、非基变量的基础上重复（1）。单纯形法的基本步骤:

注意：单纯形法中

1.每一步运算只能用矩阵初等行变换；

2.表中第3列(b列)的数总应保持非负（≥0）

3.当所有检验数均非正（≤0）时，得到最优单纯形表。

4.可能出现的特殊情况

单纯形法求解中的特殊情况

1．最终产生最优值的单纯形表中，某一非基本变量的检验数＝0，意味着作任何增大，目标函数的最优值不变．此时线性规划问题的最优解并不唯一，有多重最优解．（见下面例题）例用单纯形法求解下列规划问题解:令于是原线性规划问题变为标准形式：单纯形表迭代10-1/81/41-3x1

00-10Cj-Zj013/81/43-1x200-10Cj-Zj1[4]0-1/214-1x4-11½02-1x2

-2

2

00Cj-Zj631016-1x42-2[2]104-1x3x1x2x3x4-3-1

-1-1b最优解为：最优值为：2．当枢列（进基变量所在列）中的每一项系数不是0就是负值时，说明所有约束条件对进基变量的增加都无约束作用，因此目标函数可以无限地增加．这种情况我们称为无有限最优解（或称有无界解或无最优解）．但在现实中，不可能有此情况，往往是模型建立错误，遗漏了一些约束条件所致．

单纯形法求解中的特殊情况

单纯形法求解中的特殊情况

3．在选取进基变量时，有2个及2个以上变量的检验数具有相同的最大正值（极小化问题为相同的最小负值），这时可任选其中一个变量进基．选择进基变量的不同，可能在达到最优解前迭代的次数也不同，但事先无法预测．

4．出现相同的最小比值，此时可从具有相同最小比值所对应的基本变量中，选择下标最大的那个基本变量为出基变量．这时有可能出现退化的基本可行解，即至少有一个基本变量为零（见规划教材例2-8中的表2-6和表2-7）．出现退化的基本可行解对运算带来麻烦，理论上可能出现单纯形法陷入循环或闭环，在每次迭代中值保持不变，不能使解趋向最优解．但幸运的是，在实际应用中从未遇到或发生过这种情况．尽管如此，人们还是对如何防止出现循环作了大量研究。提出了各种避免循环的方法。

单纯形法求解中的特殊情况

在选择进基变量和出基变量时作以下规定：

①在选择进基变量时，在所有

j>0的非基变量中选取下标最小的进基；

②当有多个变量同时可作为出基变量时，选择下标最小的那个变量出基。这样就可以避免出现循环,当然，这样可能使收敛速度降低。#避免循环的方法：五、一般情况的处理--人工变量法

一般情况的处理：主要是讨论初始基本可行解不明显时，常用的方法。例如

P533(4)规范化规范化标准化考虑一般问题：

bi>0

，i=1,…,mMaxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2

...am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn

≥0引入人工变量

xn+i

≥0，i=1

,…,m；

a11x1+a12x2+…+a1nxn+xn+1

=b1

a21x1+a22x2+…+a2nxn+xn+2

=b2

...am1x1+am2x2+…+amnxn+xn+m

=bm

x1,x2...

xn,xn+1,…,xn+m

≥01．两阶段法：两阶段法是把一般问题的求解过程分为两步：第一步：求解原问题的一个基本解：建立一个辅助问题。对于前面的约束方程组，构造一个标函数为：Minz＝

xn+1＋

xn+2＋

…＋

xn+m这样，从目标最优角度迫使人工变量取零值，以达到原问题一个基本可行解的目的。这个阶段的辅助问题有下列明显的事实：设

X*

=(x*1,x*2,…,x*n,x*n＋1,…,x*n＋m）为这个问题的最优解，那么，若

x*n+1

＝x*n＋2＝…＝x*n＋m＝0，则(x*1,x*2,…,x*n

）为原问题的一个基本可行解，这时目标函数值为零；否则，即x*n＋1,…,x*n＋m不全为零时，说明原问题无可行解。即引入人工变量

xn+i

≥0，i=1,…,m；

构造:Min

Ｚ＝xn+1

＋xn+2

＋…

＋xn+m

MaxＺ

=-xn+1

-xn+2

-…-xn+m

a11x1+a12x2+…+a1nxn+xn+1

=b1a21x1+a22x2+…+a2nxn+xn+2

=b2

.

.

.am1x1+am2x2+…+amnxn+xn+m

=bmx1，

x2，...

，xn，

xn+1，…，xn+m

≥0

显然，xj=0，j=1,…,n;

xn+i=bi，

i=1,…,m

是基本解,它对应的基是单位矩阵。

结论：若得到的最优解满足xn+i=0

i

=1,…,m

，则是原问题的基本可行解;否则，原问题无可行解。得到原问题的基本可行解后，第二阶段求解原问题。第二步：求解原问题：以第一步得到的基本可行解为初始基本可行解，用单纯形法求解原问题。在表格计算过程中，这一步的初始单纯形表可这样产生（1）由第一步的最优单纯形表删去xn＋1

，xn＋2

，…，xn+m

列；（2）把第一行的目标函数系数行换为原问题目标函数的系数；（3）检验数行直接用前文介绍的方法在表格上计算得到，即用xj的价值系数cj减去cB列的各元素与xj列各对应元素的乘积，把计算结果填入xj列的最后一行，得到检验数σj

。例1：Max

Z=5x1+2x2+3x3-x4

x1+2x2+3x3=152x1+x2+5x3=20

x1+2x2+4x3+x4=26

x1,x2,x3,x4≥0第一步

求解原问题的一个基本解：

Max

Z=-x5-x6

x1+2x2+3x3+x5=152x1+x2+5x3+x6=20

x1+2x2+4x3+x4=26

x1,x2,x3,x4,x5,x6≥0

第一阶段得到原问题的基本可行解:(0，15/7，25/7，52/7)T第二步，求解原问题：

把基本可行解填入表中

得到原问题的最优解:(25/3，10/3，0，11)T最优目标值：112/3

引入人工变量xn+i

≥0（i=1,…,m）及充分大正数M

。得到：

MaxZ=c1x1+c2x2+cnxn+M

xn+1

+Mxn+m

a11

x1+a12

x2+…+a1n

xn+xn+1

=b1

a21

x1+a22

x2+…+a2n

xn+xn+2

=b2...

am1

x1+am2

x2+…+amn

xn+xn+m

=bm

x1,x2，…

，xn

，xn+1，…

，xn+m

≥02．大M法Max

Z=5x1+2x2+3x3-x4-M

x5-M

x6

x1+2x2+3x3+x5

=152x1+x2+5x3+x6=20

x1+2x2+4x3+x4=26

x1,x2,x3,x4,x5,x6

≥0例1：Max

Z=5x1+2x2+3x3-x4

x1+2x2+3x3=152x1+x2+5x3=20

x1+2x2+4x3+x4=26

x1,x2,x3,x4≥0第一节存贮问题及其基本概念

一、存贮问题

问题1医院血库的存血问题一方面，为抢救病人，血库必须储备一定数量的血液，血库存量越多，不仅抢救病人方便，应急能力越强，而且输血越多，血库经济效益也越好；另—方面，血库存血要用恒温箱等医疗设备，血存的越多，设备数量及为此支付的费用就越多，如果存放时间太长，血液还可能变质，造成更大损失。可见，血存得多，整体效益未必好。一、存贮问题

问题2中成药的存放问题药库存放中成药的品种数量越多，医生看病开药方选择药物的余地就越大，病人取药也越方便。但是存贮量大，所占空间也就大，支付的各种费用也多，特别是中成药受温度，湿度及虫害影响极易变质，可能造成更大经济损失。显然，存贮量大，综合效益也未必好。一、存贮问题

一方面说明了存贮问题的重要性和普遍性，另方面又说明了存贮问题的复杂性和多样性。近年来，随计算机的普及与推广，存贮论的应用也越来越广泛，已渗透到社会生活的各个领域。在卫生系统，诸如血库管理、药品存贮等都有所应用。

二、存贮模型中的基本概念

1．需求

根据需求的时间特征．可将需求分为连续性需求和间断性需求。在连续性需求中，随着时间的变化，需求连续地发生，因而存贮也连续地减少，在间断性需求中，需求发生的时间极短，可以看作瞬时发生，因而存贮的变化是跳跃式地减少。根据需求的数量特征，可将需求分为确定性需求和随机性需求。在确定性需求中，需求发生的时间和数量是确定的。在随机性需求中，需求发生的时间或数量是不确定的。对于随机性需求，要了解需求发生时间和数量的统计规律性。二、存贮模型中的基本概念

2．补充

(a)

开始订货到开始补充(开始生产或货物到达)为止的时间。这部分时间如从订货后何时开始补充的角度看，称为拖后时间，如从为了按时补充需要何时订货的角度看，称为提前时间。在同一存贮问题中，拖后时间和提前时间是一致的，只是观察的角度不同而已。在实际存贮问题中，拖后时间可能很短，以致可以忽略．此时可以认为补充能立即开始，拖后时间为零。如拖后时间较长，则它可能是确定性的，也可能是随机性的。二、存贮模型中的基本概念

2．补充

(b)开始补充到补充完毕为止的时间(即入库或生产时间)。这部分时间和拖后时间一样，可能很短(因此可以忽略)，也可能很长，可能是确定的，也可能是随机的。对存贮问题进行研究的目的是给出一个存贮策略，用以回答在什么情况下需要对存贮进行补充。什么时间补充，补充多少。一个存贮策略必须满足可行性要求，即它所给出的补充方案是可以实行的，并且能满足需求的必要条件。二、存贮模型中的基本概念

3．费用在存贮论研究中，常以费用标准来评价和优选存贮策略。为了正确地评价和优选存贮策略，不同存贮策略的费用计算必须符合可比性要求。最重要的可比性要求是时间可比和计算口径可比。

时间可比是指各存贮策略的费用发生时间范围必须一致。实际计算时，常用—个存贮周期内的总费用或单位时间平均总费用来衡量；

计算口径可比是指存贮策略的费用统计项目必须一致。经常考虑的费用项目有存贮费、订货费、生产费、缺货费等。在实际计算存贮策略的费用时，对于不同存贮策略都是相同的费用可以省略。二、存贮模型中的基本概念

3．费用

(1)存贮费：存贮物资资金利息、保险以及使用仓库、保管物资、物资损坏变质等支出的费用，一般和物资存贮数量及时间成比例。

(2)订货费：向外采购物资的费用。其构成有两类：一类是订购费用，如手续费、差旅费等，它与订货次数有关，而和订货数量无关；另—类是物资进货成本，如贷款、运费等，它与订货数量有关。二、存贮模型中的基本概念

3．费用

(3)生产费：自行生产需存贮物资的费用。其构成有两类：一类是装配费用(准备结束费用)，如组织或调整生产线的有关费用，它同组织生产的次数有关，而和每次生产的数量无关；另一类是与生产的数量有关的费用，如原材料和零配件成本、直接加工费等。

(4)缺货费：存贮不能满足需求而造成的损失。如失去销售机会的损失，停工待料的损失，延期交货的额外支出，对需方的损失赔偿等。当不允许缺货时，可将缺货费作无穷大处理。二、存贮模型中的基本概念

4.存贮策略

所谓一个存贮策略，是指决定什么情况下对存贮进行补充，以及补充数量的多少。下面是一些比较常见的存贮策略。

(1)t-循环策略：不论实际的存贮状态如何，总是每隔一个固定的时间t，补充一个固定的存贮量Q。

(2)(t，S)策略：每隔一个固定的时间t补充一次，补充数量以补足一个固定的最大存贮量S为准。因此，每次补充的数量是不固定的，要视实际存贮量而定。当存贮(余额)为I时，补充数量为Q=S-I。二、存贮模型中的基本概念

4.存贮策略

(3)(s，S)策略：当存贮(余额)为I，若I>s，则不对存贮进行补充；若I≤s，则对存贮进行补充，补充数量Q=S-I。补充后存贮量达到最大存贮量S。s称为订货点(或保险存贮量、安全存贮量、警戒点等)。在很多情况下，实际存贮量需要通过盘点才能得知。若每隔一个固定的时间t盘点一次，得知当时存贮I，然后根据I是否超过订货点s，决定是否订货、订货多少，这样的策略称为(t，s，S)策略。二、存贮模型中的基本概念

5.存贮模型

所谓存贮模型，指为控制物资的合理存贮数量和选择最佳订货时间或订货点而建立的数学模型。按变量的类型不同，存贮模型可分为两类：一类为确定型存贮模型，适用于需求方式为确定性的存贮问题；另一类为随机性存贮模型，适用于需求方式为随机性的存贮问题。第二节确定型存贮模型

一、模型一：不允许缺货，补充时间极短为了便于描述和分析，对模型作如下假设：(1)需求是连续均匀的，即需求速度(单位时间的需求量)R是常数；(2)补充可以瞬时实现，即补充时间(拖后时间和生产时间)近似为零；(3)单位存贮费(单位时间内单位存贮物的存贮费用)为C1。由于不允许缺货，故单位缺货费(单位时间内每缺少一单位存贮物的损失)C2为无穷大。订货费(每订购一次的固定费用)为C3。货物(存贮物)单价为K．采用t-循环策略。设补充间隔时间为t，补充时存贮已用尽，每次补充量(订货量)为Q，则存贮状态图见图6-1。模型一：不允许缺货，补充时间极短一次补充量Q必须满足t时间内的需求，故Q=Rt。因此，订货费为C3+KRt，而t时间内的平均订货费为C3/t+KR。由于需求是连续均图6-1匀的，故t时间内的平均存贮量为模型一：不允许缺货，补充时间极短t时间内的平均存贮费为1/2C1Rt。由于不允许缺货，故不需考虑缺货费用。所以t时间内的平均总费用C(t)随t的变化而变化，其图像见图6-2。当t=t*时，C(t*)＝C*是C(t)的最小值。为了求得t*，可解模型一：不允许缺货，补充时间极短由于存贮物单价K和补充量Q无关，它是一常数，因此，存贮物总价KQ和存贮策略的选择无关。所以，为了分析和计算的方便，在求费用函数C(t)时，常将这一项费用略去。略去这一项费用后，模型一：不允许缺货，补充时间极短

例1某医院每月需要某重要药品400件，每件定价2000元，不可缺货。设每件每月保管费为0.1%，每次定购费为100元，假设该药品的进货可以随时实现。问应怎样组织进货，才能最经济。

解：K=2000元/件，R=400件/月，Cl=2000·0.1％=2元/件·月，C3=100元/次。模型一：不允许缺货，补充时间极短所以，应该每隔15天进货一次，每次进货该药品200件，能使总费用(存贮费和订购费之和)为最少400元/月，平均每天约26.67元。若按年计划，则每年大约进货12/0.5=24(次)，每次进货200件。模型一：不允许缺货，补充时间极短

例2

某大医院每月消耗青霉素针剂160000盒，每盒每月保管费0.2元，不允许缺货，试比较每次订货费为1000元或100元两种情况下的经济订货批量。

解：Cl=0.2元/盒·月，R=160000盒/月。（1）（（（模型一：不允许缺货，补充时间极短（2）模型一：不允许缺货，补充时间极短本例由于订货费不同，我们采用不同策略，当订货费低时，我们采用多次小批量，可使费用达最优；当订货费高时，我们采用少次大批量，可使费用达最优。模型二：允许缺货，补充时间较长

模型假设条件：(1)需求是连续均匀的，即需求速度R为常数；(2)补充需要一定时间。不考虑拖后时间，只考虑生产时间。即一旦需要，生产可立刻开始，但生产需一定周期。设生产是连续均匀的，即生产速度P为常数。同时，设P>R；(3)单位存贮费为C1，单位缺货费为C2，订购费为C3。不考虑货物价值。模型二：允许缺货，补充时间较长存贮状态图见图6-3。[0，t]为一个存贮周期，t1时刻开始生产，t3时刻结束生产；[0，t2]时间内存贮为零，t1时达到最大缺货量B；[t1，t2]时间内产量一方面以速度R满足需求，另方面以速度(P-R)弥补[0，t1]时间内的缺货。至t2时刻缺货补足；模型二：允许缺货，补充时间较长[t2，t3]时间内产量一方面以速度R满足需求，另方面以速度(P-R)增加存贮。至t3时刻达到最大存贮量A，并停止生产；[t3，t]时间内以存贮满足需求，存贮以速度R减少。至t时刻存贮降为零，进入下一个存贮周期。下面，根据模型假设条件和存贮状态图，首先导出[0，t]时间内的平均总费用(即费用函数)，然后确定最优存贮策略。

模型二：允许缺货，补充时间较长从[0，t1]看，最大缺货量B=Rt1；从[t1，t2]看，最大缺货量B＝(P-R)(t2-t1)。故有Rt1=(P-R)(t2-t1)，从中解得：

（6-6）从[t2,t3]看，最大存贮量A＝(P-R)(t3-t2)：从[t3，t]看，最大存贮量A＝R(t-t3)。故有(P-R)(t3-t2)＝R(t-t3)，从中解得：（6-7）在[0，t]时间内，存贮费为：缺货费为：模型二：允许缺货，补充时间较长故[0，t]时间内平均总费用为：将(6-6)和(6-7)代入，整理后得：模型二：允许缺货，补充时间较长解方程组容易证明，此时的费用C(t*，t2*)是费用函数C(t，t2)的最小值。模型二：允许缺货，补充时间较长因此，模型二的最优存贮策略各参数值为：最优存贮周期

(6-9)经济生产批量

(6-10)

缺货补足时间(6-11)模型二：允许缺货，补充时间较长开始生产时间(6-12)结束生产时间(6-13)最大存贮量(6-14)最大缺货量(6-15)平均总费用(6-16)模型二：允许缺货，补充时间较长例3某药厂生产某种药品，正常生产条件下每天可生产100件。根据供货合同，需每天80件供货。存贮费每件每天2元，缺货费每件每天5元，每次生产准备费用(装配费)为800元，求最优存贮策略。解依题意，符合模型二的条件且P=100件/d，R=80件/d，Cl=2元/d·件，C2=5元/d·件，C3=800元/次。模型二：允许缺货，补充时间较长利用公式(6-9)～(6-16)，可得最优存贮周期

经济生产批量缺货补足时间模型二：允许缺货，补充时间较长开始生产时间结束生产时间最大存贮量最大缺货量平均总费用模型二：允许缺货，补充时间较长可以把模型一看作模型二的特殊情况。在模型二中，取消允许缺货和补充需要一定时间的条件，即C2→，P→，则模型二就是模型一。事实上，如将C2→和P→代入模型二的最优存贮策略各参数公式，就可得到模型一的最优存贮策略。只是必须注意，按照模型一的假设条件，应有：t1*＝t2*=t3*=0A*＝Q*B*=0模型三：不允许缺货，补充时间较长

在模型二的假设条件中，取消允许缺货条件(即设C2→，t2=0)，就成为模型三。因此，模型三的存贮状态图和最优存贮策略可以从模型二直接导出。模型三的存贮状态图见图6-4。最优存贮周期经济生产批量结束生产时间最大存贮量平均总费用模型三：不允许缺货，补充时间较长

例4某医院2001年每月需用某种针剂10000支，每月购进25000支(在边补充边消耗期间，订购后需6天才开始到货)，单位存贮费为0.05元/支·月，单位订购费1000元，试求最优存贮策略。解：本例特点是补充除需要入库时间，还需考虑拖后时间。因此，订购时间应在存贮降为零之前的第6天。除此之外，本例和模型三的假设条件完全一致。本例的存贮状态图见图6-5。模型三：不允许缺货，补充时间较长

从图6-5可见，拖后时间为[0，t0]，存贮量L应恰好满足这段时间的需求，故L=Rt0由题意知P=25000支/月R=10000支/月Cl=0.05元/支·月C3=1000元/次t0=6天，L=100006/30=2000支。代入式(6-17)~(6-21)可算得：最优存贮周期模型三：不允许缺货，补充时间较长

模型三：不允许缺货，补充时间较长

经济生产批量结束生产时间最大存贮量平均总费用模型四：允许缺货，补充时间极短

在模型二的假设条件中，取消补充需要一定时间的条件(即设P→)，就成为模型四。因此，和模型三一样，模型四的存贮状态图和最优存贮策略也可以从模型二中直接导出。模型四的存贮状态图见图6-6。最优存贮策略各参数：最优存贮周期

经济生产批量生产时间最大存贮量最大缺货量平均总费用模型四：允许缺货，补充时间极短

例5假设某医院每年均匀地耗用A种卫生材料24000单位(允许缺货，瞬时补充)。已知每单位A材料每月存贮费0.1元，每采购一次该材料需采购费350元，单位缺货费为0.2元/单位·月，试求最优存贮策略。解：由题意知：R=24000/12=2000单位Cl=0.1元/单位·月C2=0.2元/单位·月C3=350元/次,可算得：最优存贮周期

经济生产批量

模型四：允许缺货，补充时间极短

生产时间最大存贮量最大缺货量平均总费用模型四：允许缺货，补充时间极短

对于确定型存贮问题，上述四个模型是最基本的模型。其中，模型一、三，四又可看作模型二的特殊情况。在每个模型的最优存贮策略的各个参数中，最优存贮周期t*是最基本的参数，其它各个参数和它的关系在各个模型中都是相同的。根据模型假设条件的不同，各个模型的最优存贮周期t*之间也有明显的规律性。因子对应了是否允许缺货的假设条件，因子对应了补充是否需要时间的假设条件。

模型四：允许缺货，补充时间极短

一个存贮问题是否允许缺货或补充是否需要时间，完全取决于对实际问题的处理角度，不存在绝对意义上的不允许缺货或绝对意义上的补充不需要时间。如果缺货引起的后果或损失十分严重，则从管理的角度应当提出不允许缺货的建模要求；否则，可视为允许缺货的情况。至于缺货损失的估计，应当力求全面和精确。如果补充需要的时间相对于存贮周期是微不足道的，则可考虑补充不需要时间的假设条件；否则，需要考虑补充时间。在考虑补充时间时，必须分清拖后时间和生产时间，两者在概念上是不同的。为了鼓励大批量订货，供方常对需方实行价格优惠。订货批量越大，货物价格就越便宜。模型五除含有这样的价格刺激机制外，其它假设条件和模型一相同。一般地，设订货批量为Q，对应的货物单价为K(Q)。当Qi-1≤Q<Qi，时，K(Q)＝Ki(i=1，2,…，n)。其中，Qi为价格折扣的某个分界点，且0≤Q0<Ql<Q2<…<Qn，K1>K2>…>Kn。由式(6-1)，在一个存贮周期内模型五的平均总费用(费用函数)为：其中，Q=Rt。当Qi-1≤Q=Rt<Qi时，K(Q)=Kii=1,2,…,nC(t)为关于t的分段函数。为了了解它的性质，以n＝3为例，画出其图象，见图6-7。模型五：价格与订货批量有关的存贮模型

模型五：价格与订货批量有关的存贮模型

(1)计算。若，则平均总费用：(2)计算(3)若，则C*对应的批量为最小费用订购批量Q*。相应地，和最小费用C*对应的订购周期t*=Q*/R。模型五：价格与订货批量有关的存贮模型

例6医院每周需打印纸45箱，存贮费每箱每周5元，每次订购费50元，不允许缺货。打印纸进货时若(1)订货量1箱～9箱时，每箱120元；(2)订货量10箱～49箱时，每箱100元；(3)订货量50箱～99箱时，每箱95元；(4)订货量99箱以上时，每箱90元。求最优存贮策略。解R=45箱/周，C1=5元/周，C3=50元/次Q0=0，Ql=1，Q2=10，Q3=50，Q4=100K1=120，K2=100，K3=95，K4=90模型五：价格与订货批量有关的存贮模型

标准的线性规划模型不含有明显的单位基

——人工变量法引入人工变量xn+i

≥0，i=1

,…,m；x1,x2...

xn,xn+1,…,xn+m

≥

0a11x1+a12x2+…+a1nxn+xn+1

=b1

a21x1+a22x2+…+a2nxn+xn+2

=b2

am1x1+am2x2+…+amnxn+xn+m

=bm

......

1．两阶段法：第一步：求解原问题的一个基本解建立一个辅助问题。构造一个目标函数为：MinZ＝

xn+1＋

xn+2＋

…＋

xn+m第二步：求解原问题：以第一步得到的基本可行解为初始基本可行解，用单纯形法求解原问题。2．大M法：引入充分大正数

M

，改造目标函数MaxZ=c1x1+c2x2+cnxn-

Mxn+1-…-

Mxn+m

一、对偶问题的提出

二、对偶规划的形式

1.对称形式的对偶问题

2.非对称形式的对偶问题

3.一般形式对偶问题三、对偶规划的基本性质四、对偶单纯形法五、灵敏度分析小结一、对偶问题的提出

线性规划是研究资源最优利用的理论，所谓最优利用包括两方面的含意，即者包含相同的1.在一定的资源条件下完成最多的任务；2.完成给定的任务，使用的资源最小。因此，线性规划就有一个有趣的特征：

任何一个求极大值的规划问题，必存在一个与其匹配的求极小值的规划问题

它们的解之间还存在着密切的关系。线性规划的这个特征称为对偶性。如果称前一个问题为原问题，则后一个问题便叫做原问题的对偶问题；反之，若称后一个问题为原问题，则前一个问题便是对偶问题，即对偶问题是相对而言的。

例1

某医院营养科用糖、蛋白质和脂肪生产四种食品A、B、C、D,一个人每月各种营养成分的最低需求量、不同食品的营养成分含量及其单价如表1-8所示。问某人每月怎样购买这些食品，才能既满足营养要求，又可以花钱最少？

表1-8食品营养成分含量及单价ABCD最低需求量（单位）

含量（单位/公斤）糖蛋白质脂肪533221412245604035单价（元/公斤）1.50.70.91.2解：设某人每月购买食品A、B、C、D各为x1、

x2、x3、x4公斤，共花费Z元，于是它的数学模型为：

例2

假设营养科不安排生产食品A、B、C、D，而出售单一营养成分的糖、蛋白质和脂肪。仍用例1中的数据，问该营养科如何确定糖、蛋白质和脂肪的单价，才能在市场竟争中立于不败之地，并可获得利润最多？现在从另一个角度来讨论该问题。

同理，由单一营养成分食品合成的食品B、C和D的单价分别不得超过0.7、0.9和1.2元/公斤，故有：

2y1+2y2+y3≤0.74y1+y2+2y3≤0.92y1+4y2+5y3≤1.2解：设糖、蛋白质和脂肪的单价分别为y1元/单位、y2元/单位和y3元/单位，某人每月购买单一营养成分食品共花费W

元。欲使该厂获利最多，应该让

W=60y1+40y2+35y3达到最大值。

如要该营养科在市场竟争中稳操胜券，以单一营养成分食品合成食品A单价不得超过1.5元/公斤，即

5y1+3y2+3y3≤1.5例1是例2的对偶问题

这里，y1，y2和y3称为单一营养成分食品的影子价格，影子价格并不是单一营养成分食品的实际成本或价格，而是从生产活动的反面来分析问题，即从出售合成食品的收益来估计所利用的单一营养成分食品的价值。例1与例2互为对偶线性规划

我们应用单纯形法求解例1和例2，将会发现原规划的最后单纯形表不仅给出了原规划的最优解，而且它的对应的检验行Cj-Zj也给出了对应的对偶规划的最优解（符号相反）。

所以两个规划问题，互相对偶时，只要解一个就够了。对偶规划的解，就是原规划中的影子价格，也就是资源的拥有者宁愿停止生产活动而将资源转让出去的最低价格。返回二、对偶规划的形式

以上从一个食品生产问题引出了对资源的估价问题，得到了对偶规划。实际上，对于一般的线性规划模型可以直接给出其对偶规划模型，并不需要像上面那样经过一番讨论。为此，我们需要分析原规划与对偶规划之间的关系。对偶规划的形式分为对称形式和非对称形式。返回1.对称形式的对偶问题称具有下面形式的一对规划是对称形式的对偶规划：它的对偶规划y1,y2,…,ym称为对偶变量

例1和例2中的一对规划就是对称形式的系数矩阵互为转置

一对对称形式的对偶问题的对应关系：Max，≤，变量皆非负

Min，≥，变量皆非负变量约束条件价值系数右端常数系数矩阵为AA转置矩阵AT（1）若一个模型目标函数是求“极大”，约束条件为“小于等于”的不等式，则对偶模型的目标函数是求“极小”，约束是“大于等于”的不等式；即“Max，≤”⇔“Min，≥”（2）若一个模型有n个变量，m个约束条件,则对偶模型有n个约束条件；m个变量；（3）一个模型目标函数中价值系数等于对偶模型中相应约束条件的右端常数；一个模型约束条件中的右端常数等于对偶模型目标函数中相应的价值系数；（4）若一个模型约束条件中的系数矩阵为A，则对偶模型约束条件中的系数矩阵为A转置矩阵AT；（5）两个规划模型中的变量皆非负。一对对称形式的对偶规划之间具有下面的对应关系：

原变量xj对偶变量y¡

产品类别

资源类别

≤b1

≤b2

≤bm

资源价格

产品价值\∨\∨\∨

МinWМaxZ表1-10线性规划原问题与对偶问题间变换关系例3

求下列线性规划的对偶规划（书中例15）对偶变量y1y2y3y1y2y3解：这两个模型都是对称形式的规划模型，它们的对偶规划分别为：对偶变量x1x2x3x1x2返回2.非对称形式的对偶问题

对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。

（1）将模型统一为“max，≤”或“min，≥”的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；

（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；

一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。含有等式约束和变量无符号限制

（3）若原规划某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。例如：设原规划中第一个约束为等式

a11

x1

+…+a1n

xn

=b1那么，这个等式与下面两个不等式等价统一成≤

这样，原规划模型可以写成对偶变量

于是y1

没有非负限制，即

此时已转化为对称形式，直接写出对偶规划这里，把y1

看作是a11

x1

+…+a1n

xn

=b1

非对称形式的对偶规划的对应关系

非对称形式含有等式约束和变量无符号限制变量无符号限制等式约束2.非对称形式的对偶问题

例4

写出下面线性规划的对偶规划模型解先将约束条件变形为“≤”形式对偶变量y1y2y3y4y5

再根据非对称形式的对应关系，直接写出对偶规划对偶变量x1x2x3x4例5

设有线性规划问题（书中例16）试写出它的对偶问题。解：对偶规划为：对偶变量y1y2例6

设有线性规划问题（书中例17）试写出它的对偶问题。解：所求的对偶问题是：对偶变量y1y2返回3.一般形式的对偶关系见下表所示

对于一般形式的对偶问题,也可以不考虑对称形式的转化,而直接遵循如下对偶关系进行转化。返回小结

对称形式的对偶问题Max，≤，变量皆非负

Min，≥，变量皆非负变量约束条件价值系数右端常数系数矩阵为AA转置矩阵AT二、对偶规划的形式

对称形式的对偶问题Max，≤，变量皆非负

Min，≥，变量皆非负变量约束条件价值系数右端常数系数矩阵为AA转置矩阵AT

一般形式的对偶关系

非对称形式的对偶规划的对应关系

非对称形式含有等式约束和变量无符号限制变量无符号限制等式约束见下表所示

二、对偶规划的形式返回

设有原线性规划问题，它的矩阵表示如下：三、对偶规划的基本性质式中其对偶规划的矩阵表示是这里，A，B，C

与上面的原规划相同。

下面我们用矩阵表示法说明对偶问题的基本性质：三、对偶规划的基本性质三、对偶规划的基本性质

性质1

线性规划对偶问题的对偶是原问题。

性质2

若分别为互为对偶线性规划问题的可行解，则有

性质3

若分别为互为对偶线性规划问题的可行解，则当时，是最优解。

性质4

若互为对偶的两个线性规划问题中，有一个有最优解，那么另一个也一定有最优解，且最优的目标函数值相等。

性质5

原问题的判别数对应着对偶问题的一个解。有了性质5，在求解线性规划问题时，原规划问题单纯形表中的判别数，就是对偶问题的一个解，但符号相反。返回四、对偶单纯形法

我们前面介绍的一般单纯形法，是从“可行”(右端项非负）开始，逐步地迭代运算，直到得出最优解。而应用对偶规划的性质，可以找到一种求解线性规划的新方法——对偶单纯形法。对偶单纯形法则是从“不可行”(右端项含负）开始，在保持最优性之下逐步迭代，直到不可行变为可行，即得到可行最优解为止。当对偶问题的约束条件的数目较原问题为少时，应用对偶单纯形法求解较为方便。单纯形法思路（保持可行性）对偶单纯形法思路（保持最优性）可行(右端项非负）非最优（检验数非负）可行最优解可行非最优（检验数非负）不可行(右端项含负）最优（检验数非正）可行最优解不可行最优（检验数非正）

对偶单纯形法的基本思想

对偶单纯形法的基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。例7

利用对偶单纯形法求解解：

将原问题化成再化成标准形列表用对偶单纯形法求解：

0

S50S6[-1]-21-11021-4-101-3←2

Zj

Cj-Zj000000-1-40-3000

-1x10S612-11-100-3[-2]-3213

-8←

Zj

Cj-Zj-1-21-1100-2-1-2-10-3

-1x10x317/205/2-2-1/203/213/2-1-1/274

Zj

Cj-Zj-1-7/20-5/221/20-1/20-1/2-2-1/2-7

Cj

－1－40－300

x1x2

x3

x4

s5s6

b

1

23

2/31/22/3对偶单纯形法的步骤可以归纳如下：(1)

将原问题化成标准形式：

建立初始对偶单纯形表,若b列全为非负，判别数行Cj-Zj≤0,则已得最优解，计算停止；若b列中至少有一个负分量，且判别数Cj-Zj≤0，则进行下一步；(2)

以对应的基变量作为换出变量;（3）检查所在行的系数若所有的则无可行解，计算停止。若存在则计算确定为换入变量；（4）以为主元素，进行迭代运算，得新表。重复步骤（1）—（4）对偶单纯形法的步骤可以归纳如下：1．确定换出变量：选择最负的基本变量为换出变量。

2．确定换入变量：用换出变量那一行具有负值的系数分别去除同列的检验数，取最小商数所对应的变量为换入变量；如果换出变量那一行无负值的系数，则原问题无可行解。

3．初等行运算，使枢元位置变为1,其他枢列位置变为0。

4．最优解检查。如果所得的基本解都是非负的，则此解即为最优解。如果基本解中还有负的数值，则重复第一步继续迭代，直到所有基本变量为非负的数值为止。对偶单纯形法迭代的要点1．初始解可以是非可行解，当检验数都是小于等于零时，就可以进行基变换，这样就避免了增加人工变量，使运算简化。

2．对变量较少，而约束条件很多的线性规化问题，可先将其变为对偶问题，再用对偶单纯形法求解，简化计算。

3．用于灵敏度分析。对偶单纯形法的优点及用途

①

单纯形表检验数行全部非正（对偶可行）

②

变量取值可有负数（非可行解）

对偶单纯形法在什么情况下使用：注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。应用前提：有一个基，其对应的基满足:

适合于解如下形式的线性规划问题对偶单纯形法的适用范围

在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法，可以简化计算。#返回它主要考虑两种情况：一是这些系数在什么范围内变化时，已得到的最优解保持不变，或者最优解的基本变量保持不变（但数值有所改变）；二是如果某些系数的变化引起最优解的变化，如何用最简便的方法求出新的最优解。五、灵敏度分析系数变化的灵敏度分析

基矩阵B——原始系数矩阵中对应于基本变量的列所组成的矩阵。

基矩阵的逆阵B-1——在任一单纯形表中相应于初始基本变量的那些列给出了相应于该表格的基矩阵的逆阵B-1。在单纯形表每次迭代后,每个变量的系数列向量是B的逆阵B-1乘以该变量的原始列向量而得到的，右端常数的列向量是B的逆阵B-1乘以右端常数的原始列向量而得到的。P

=B-1Pb

=B-1b

检验数是Cj-Zj=Cj-CBB-1P

（一）价值系数c发生变化：

m

考虑检验数

j=cj-∑cri

arij（

j=1,2,…,n）

i=1

1.若ck是非基变量的系数：

设ck变化为

ck+

ck

k’=ck+

ck-∑cri

arik=

k+

ck对于极大化问题，只要

k’≤0,即

ck≤-

k，则最优解不变；否则，将最优单纯形表中的检验数

k

用

k’取代，继续单纯形法的表格计算。

MinY’=-2x1-3x2-x3+0x4+0x5

1/3x1+1/3x2+1/3x3+x4=1

1/3

x1+4/3x2+7/3x3+x5=3

x1,x2,x3,x4,x5≥0例8

MaxY=2x1+3x2+x3

1/3x1+1/3x2+1/3x3≤

1

1/3

x1+4/3x2+7/3x3≤3

x1,x2,x3≥0

最优单纯形表从表中看到σ3=c3+Δc3-(c1×a13+c2×a23)

可得到Δc3

≥

－3

时，原最优解不变。当3+Δc3

≥0最优解不变

2．若cs

是基变量的系数：

设cs

变化为cs+

cs，那么

j’=cj-∑cri

arij-(

cs+

cs)asj=

j-

csas，

i≠s

观察所有非基变量：对于极小化问题，只要对所有非基变量

j’≥0，即

j’≥

csasj，则最优解不变；否则，将最优单纯形表中的检验数

j

用

j’取代，继续单纯形法的表格计算。

Max{

j/asj

asj>0}≤

cs≤Min{

j/asj

asj<0}下表为最优单纯形表（考虑基变量系数c1发生变化）3+Δc1

≥05-4Δc1≥01+Δc1≥0最优解不变可得到-1≤ΔC2≤5/4时，原最优解不变。最优值将会出现相应的变化。MaxZ=2x1+3x2+0x3+0x4+0x5x1+2x2+x3=84x1+x4=164x2+x5=

12

x1,x2,x3,x4,x5

≥

0例9下表为最优单纯形表（考虑基变量系数c2发生变化）从表中看到σj=cj-(c1×a1j+c5×

a5j+(c2+Δc2)×a2j)

j=3,4可得到-3≤Δc2≤1时，原最优解不变。

3.若基变量的系数和非基变量的系数都变化：

只要计算非基变量的检验数即可。

设分量br变化为br+

br，根据前面的讨论，最优解的基变量xB=B-1b，那么只要保持B-1(b+

b)≥0，则最优基不变，即基变量保持，只有值的变化；否则，需要利用对偶单纯形法继续计算。对于问题

Max

Z=cT

x

Ax≤b

x≥0（二）右端项b

发生变化最优单纯形表中含有B-1=(aij

）i=1,…,m;j=n+1,…,n+m

那么，新的xi=(B-1b)I+

brairi=1,…,m

由此可得，最优基不变的条件是Max{-bi

/air

air>0

}≤

br≤Min{-bi

/air

air<0}

例9的最优单纯形表如下例9MaxZ=2x1+3x2+0x3+0x4+0x5x1+2x2+x3

=84x1+

x4

=164x2+x5=

12

x1,x2,x3,x4,x5

≥

0若Δb3=-8，则4+（-8）=-4<0，改变了最优性，只要再继续迭代即可。见下表比如第三个式子中，由4+Δb3≥0，解得Δb3≥-4

时最优性不变。#小结1.对偶单纯形法迭代的要点2.对偶单纯形法的优点及用途3.对偶单纯形法的适用范围五、灵敏度分析（一）价值系数c