设:
(2)基向量:
称B中每个列向量Pj(j=12……m)为基向量。
与基向量Pj对应的变量xj为基变量(basicvariable)。
除基变量以外的变量为非基变量。
(3)非基向量:
4.基解、基可行解、可行基
(1)基解:
某一确定的基,令非基变量等于零,由约束条件方程②解出基变量,称这组解为基解。
在基解中变量取非0值的个数不大于方程数m,基解的总数不超过
(2)基可行解:
满足变量非负约束条件的基本解,简称基可行解。
(3)可行基:
对应于基可行解的基称为可行基。
5.单纯形迭代的基本思路
从可行域中某一个顶点开始,判断此顶点是否是最优解,如不是,则再找另一个使得其目标函数值更优的顶点,称之为迭代,再判断此点是否是最优解。
直到找到一个顶点为其最优解,就是使得其目标函数值最优的解,或者能判断出线性规划问题无最优解为止
6.单纯形求解线性规划(标准型——规范型,计算题)
7.人工变量法(大M法)——怎样判断LP问题无可行解
8.单纯形变法解的判断(5种)
解的判别:
1)唯一最优解判别:
最优表中所有非基变量的检验数非零,则线性规划具有唯一最优解。
2)多重最优解判别:
最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解(或无穷多最优解)。
3)无界解判别:
某个σk>0且aik≤0(i=1,2,…,m)则线性规划具有无界解。
4)无可行解的判别:
当用大M单纯形法计算得到最优解并且人工变量依然为基变量时,则表明原线性规划无可行解。
5)退化解的判别:
存在某个基变量为零的基本可行解。
第六章:
单纯形变法的灵敏度与对偶
1.怎样把LP问题转化为对偶问题
(1)目标函数由MAX变为MIN
(2)原问题有多少约束行,对偶问题的目标函数就有多少变量
(3)原问题目标函数有多少变量,对偶问题就有多少约束行
(4)原问题的价值系数C变为对偶问题右端常数项B
(5)原问题的右端常数B变为对偶问题目标函数的价值系数C
(6)原问题的系数矩阵A转置后变为对偶问题的系数矩阵
操作表格如下:
原问题(或对偶题)
对偶问题(或原问题)
约束条件右端项
目标函数变量的系数
目标函数变量的系数
约束条件右端项
目标函数max
目标函数min
约
束
条
件
m个
m个
变
量
≤
≥0
≥
≤0
=
无约束
变
量
n个
n个
约
束
条
件
≥0
≥
≤0
≤
无约束
=
第七章:
运输问题(有一道计算题)
1.何为产销平衡?
产大于销?
销大于产?
2.运输规划问题建模3.表上作业法
步骤
描述
方法
第一步
求初始基行可行解(初始调运方案)
西北角法
最小元素法
第二步
求检验数并判断是否得到最优解:
当非基变量的检验数σij全都非负时得到最优解,若存在检验数σij<0,说明还没有达到最优,转第三步。
闭回路法
位势法
第三步
调整运量,即换基,选一个变量出基,对原运量进行调整得到新的基可行解,转入第二步
4.初始可行解(最小元素法、基变量的个数)
(1)最小元素法
在表上找到单位运价最小的x21,并使x21取尽可能大的值,即x21=min(4,3)=3,把A2的产量改为1,B1的销量改为0,并把B1列划去。
在剩下的3×3矩阵中再找最小运价,同理可得其他的基本可行解。
一般来说用最小元素法求得的初始基本可行解比西北角法求得的总运价要少。
这样从用最小元素法求得的初始基本可行解出发求最优解的迭代次数可能少一些。
(2)基变量的个数(略)
5.非基变量的检验数(闭回路、位势法)
(1)闭回路法
对于代表非基变量的空格(其调运量为零),把它的调运量调整为1,由于产销平衡的要求,我们必须对这个空格的闭回路的顶点的调运量加上或减少1。
最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。
如果所有代表非基变量的空格的检验数都大于等于零,则已求得最优解,否则继续迭代找出最优解。
(2)位势法(略)
6.进基、出基(闭回路调整法)
(1)选取所有负检验数中最小值对应的非基变量xij作为入基变量,以求尽快实现最优。
(2)在以xij为出发点的闭回路中,找出所有偶数的顶点的调运量,以其中的最小的变量为出基变量
(3)将该闭回路上所有的奇数顶点的调运量增加这一数值,所有的偶数顶点的调运量减少这一数值。
7.多个最优解?
退化解?
(1)如何寻找多个最优方案?
识别是否有多个最优解的方法和单纯形表法一样,只需看最优方案中是否存在非基变量的检验数为零。
如在本题中给出的最优运输方案中x11的检验数为0,可知此运输问题有多个最优解。
只要把x11作为入基变量,调整运输方案,就可得到另一个最优方案
第八章:
整数规划
1.整数规划?
纯整数规划?
0-1规划?
(1)一部分或全部决策变量取整数值的规划问题称为整数规划。
不考虑整数条件,由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。
若该松弛问题是一个线性规划,则称该整数规划为整数线性规划。
(2)纯整数线性规划:
指全部决策变量都必须取整数值的整数线性规划。
(3)0-1型整数线性规划:
决策变量只能取值0或1的整数线性规划。
2.整数规划的解VS对应的LP问题的解
3.整数规划问题的建模
第十章:
动态规划
1.多阶段决策、最优性定理
(1)在实际生产经营活动中,常常可以将一个较复杂的决策过程划分为若干个相互联系的阶段,而每个阶段都需要做出决策,并且某个阶段的决策确定之后,将影响其后的下一个阶段的决策。
(2)最优化原理:
作为整个过程的最优策略具有如下性质:
不管在此最优策略上的某个状态以前的状态和决策如何,对该状态来说,以后的所有决策必定构成最优子策略。
也就是说,最优策略的任意子策略都是最优的。
对最短路问题来说,从“最短路”上的任一点到终点的那部分道路(最短路上的子路),也一定是从该点到终点的最短路(最短子路)。
2.阶段、状态、决策、状态转移、阶段指标、策略、过程指标
(1)阶段k:
首先将问题的全过程适当地分成若干个互相联系的阶段,一般是根据时间与空间的自然特征去划分阶段;k是表示决策顺序的离散的量
(2)状态
:
是指每个阶段开始时所处的自然状况或客观条件。
状态可以是数量,也可以是字符,数量状态可以是连续的,也可以是离散的
(3)状态转移:
状态转移方程
:
第
阶段的状态,是由第
阶段的状态、和第
阶段的决策所决定的,用方程的形式表示这种关系为
,称之为状态转移方程;其中函数关系
因问题的不同而不同。
(4)决策
:
决策是某一阶段内的抉择,第k阶段的决策与第k个阶段的状态
有关,通常用
表示第k阶段处于
状态时的决策变量,而这个决策又决定了第
阶段的状态
(5)策略
:
由所有各阶段的决策组成的决策函数序列称为“全过程策略”,记为
,从第k阶段开始到最后第n阶段的决策函数序列,称“k子策略”,记为
(6)阶段指标函数
:
从状态
出发,选择决策
所产生的第
阶段决策效用指标
(7)过程指标函数
动态规划要求过程指标具有可分离性
指标具有可加性:
指标具有可乘性:
3.解最短路问题
4.解资源分配问题
第十一章:
图与网络模型(有一道计算题)
1.图论中的图VS几何中的图
图论:
图是由点和边构成,可以反映一些对象之间的关系。
图G区别于几何学中的图。
这里只关心图中有多少个点、以及哪些点之间有连线。
图论:
图是由点和边构成,可以反映一些对象之间的关系。
一般情况下图中点的相对位置如何、点与点之间联线的长短曲直,对于反映对象之间的关系并不是重要的。
2.图、有向图、边、弧、连通图、赋权图、网络、树
(1)图:
图是由点和边构成,可以反映一些对象之间的关系。
(2)树:
无圈的连通图即为树
(3)
3.求解最短路的双标号法
双标号法的步骤
(1)给出点Vs以标号(0,s)
(2)找出已标号的点的集合I,没标号的点的集合J,以及弧的集合
(3)如果B是空集,则计算结束。
①如果Vt已标号(Lt,Kt),则Vs到Vt的距离为Lt,而从Vs到Vt的最短路径,则可以从Vt反向追踪到起点Vs(根据Kt的记录)而得到。
②如果Vt未标号,则可以断言不存在从Vs到Vt的路。
如果上述的弧(B)的集合不是空集,则转下一步。
(4)对B中的每一条弧,计算Sij=Li+Cij。
在所有的Sij中,找到其值为最小的弧。
不妨设此弧为(Vc,Vd),则给此弧的终点以双标号(Scd,c),返回步骤2。
4.图的最小生成树(破圈法、最小生成树的权重)
性质1:
任何树中必存在次为1的点。
性质2:
n个顶点的树必有n-1条边。
性质3:
树中任意两个顶点之间,恰有且仅有一条链。
性质4:
树连通,但去掉任一条边,必变为不连通。
性质5:
树无回圈,但不相邻的两个点之间加一条边,恰得到一个圈。
(2)最小生成树问题:
在一个赋权的、连通的、无向图G中找出一个生成树,并使得这个生成树的所有边的权数之和为最小
(3)求解最小生成树的破圈算法
a.在给定的赋权的连通图上任找一个圈
b.在所找的圈中去掉一个权数最大的边(如果有两条或两条以上的边都是权数最大的边,则任意去掉其中一条)。
c.如果所余下的图已不包含圈,则计算结束,所余下的图即为最小生成树,否则返回第1步。
(4)最大流问题的网络图论解法基本算法步骤:
(1)找出一条从发点到收点的路,在这条路上的每一条弧顺流方向的容量都大于零。
如果不存在这样的路,则已经求得最大流。
(2)找出这条路上各条弧的最小的顺流的容量pf,从而通过这条路增加网络的流量pf。
(3)在这条路上,减少每一条弧的顺流容量pf,同时增加这些弧的逆流容量pf,返回步骤
(1)。
****为了使算法更快捷有效,我们一般在步骤
(1)中尽量选择包含弧数最少的路。
第十三章:
存储论(有一道计算题)
1.经济定购批量模型
一年的总费用
TC(Q)求极值,得使总费用最小的订购批量为
一年的存贮费用=
一年的订货费用=
一年的总费用=
两次订货间隔时间
2.经济生产批量模型
设每次生产量为Q,生产率是p,则每次的生产时间t为Q/p,于是最高库存量为(p-d)Q/p。
到T时刻存贮量为0,则0到T时间内的平均存贮量为
(p-d)Q/2p。
故单位时间的存贮费为:
另一方面,设D为产品在考察期内的总需求量,则考察期内的生产准备费为c3D/Q,进而,考察期内的总费用TC为:
使TC达最小值的最佳生产量
一年的最低总费用
生产量为Q*时的最大存贮量为
每个周期所需时间为
显然,
时,经济生产批量模型趋于经济订购批量模型。
3.年总费用、存储费、订货费、年订货次数、订货时间间隔、在订货点
4.允许缺货的经济订购、生产模型(概念)
(1)概念:
所谓允许缺货是指企业在存贮量降至0时,不急于补充、等一段时间,然后订货。
顾客遇到缺货也不受损失或损失很小,并假设顾客会耐心等待,直到新的补充到来。
当新的补充一到,企业立即将所缺的货物交付给这些顾客,即缺货部分不进入库存。
(2)模型:
设每次订货量为Q,由于最大缺货量为S,则最高库存量为Q-S,故不缺货时期内的平均存贮量为(Q-S)/2,于是,周期T内的平均存贮量=(Q-S)t1/2T。
由于t1=(Q-S)/d,T=Q/d,则周期T内的平均存贮量=(Q-S)2/2Q。
又周期T内的平均缺货量=(St2)/2T。
由于t2=S/d,T=Q/d,故周期T内的平均缺货量=S2/2Q。
故单位时间的总费用TC为:
使TC达最小值的最佳订购量
订购量为Q*时的最大缺货量
一年的最低总费用
订购量为Q*时的最大存贮量为
每个周期T所需时间
显然,
时,允许缺货订购模型趋于经济订购批量模型。
5.经济订购批量折扣模型
6.需求为随机变量的单一周期存储模型
7.(Q,R)策略,(T,S)策略
(Q,R)策略
下面我们给出求(Q,R)策略最优解的近似方法,而精确的数学公式太复杂,这里不作介绍。
具体求解步骤如下:
1.设全年的需求量近似为D,利用经济订货批量存贮模型求出(每次的)最优订货量Q*。
2.根据具体情况制定出服务水平,即制定在m天里出现缺货的概率,也即不出现缺货的概率为1。
利用下式求出r
P(m天里需求量r)=1,
其中r为再订货点,即当库存量下降到r时订货,m天后到货
第十四章:
排队论
1.排队系统要素
2.排队系统符号表示
一个排队系统的特征可以用五个参数表示,形式为:
A/B/C/D/E
其中:
a––顾客到达的概率分布,可取M、D、G等;
b––服务时间的概率分布,可取M、D、G等;
c––服务台个数,取正整数;
d––排队系统的最大容量,可取正整数或;
e––顾客源的最大容量,可取正整数或。
例如M/M/1//
表示顾客到达过程服从泊松分布,服务时间服从负指数分布,一个服务台,排队的长度无限制和顾客的来源无限制。
单位时间顾客平均到达数,单位时间平均服务顾客数(<)
数量指标公式:
a、系统中无顾客的概率P0=1/
b、平均排队的顾客数Lq=2/()
c、系统中的平均顾客数Ls=Lq+/
d、顾客花在排队上的平均等待时间Wq=Lq/
e、顾客在系统中的平均逗留时间Ws=Wq+1/
f、顾客得不到及时服务必须排队等待的概率Pw=/
g、系统中恰好有n个顾客的概率Pn=(/)nP0
3.泊松到达、负指数时间、服务强度
4.M/M/1效率指标、M/M/2与M/M/1
5.排队系统的经济分析
第十五章:
对策论
1.对策模型三要素
2.矩阵对策
3.如何判断最优纯策略?
怎样求解矩阵对策小的值?
4.如何判断矩阵对策论存在最优