第32讲运筹学基础.ppt

运筹学基础 一、运筹学模型 运筹学模型的分类： 1.数学规划模型， 2.图与网络模型， 3.对策论模型， 4.排队论模型， 5.决策论模型， 6.存贮论模型， 7.排序与统筹方法。 运筹学分析的主要步骤 发现和定义待研究的问题， 构造数学模型， 寻找经过模型优化的结果， 通过应用这些结果对系统进行分折和改善系统的运行。 二、线性规划 生产计划问题 设生产桌子x个，生产椅子y个（决策变量为2个）. 要达到销售收入最大： Max z=50x＋30 y （目标函数）。 工时要求：4x＋3y ? 120, 2 x＋y ? 50. （约束条件） 变量取值要求：x?0, y?0. （约束条件）。 线性规划模型为： max z = 50 x＋30 y s.t. 4 x＋3 y ? 120 2 x＋y ? 50 x ? 0, y ? 0. 目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 ≤ 300 (A) 2 x1 + x2 ≤ 400 (B) x2 ≤ 250 (C) x1 ≥ 0 (D) x2 ≥ 0 (E) 得到最优解： x1 = 50， x2 = 250 最优目标值 z = 27500 图解法的步骤 1.画出直角坐标系。 2.画出可行域，即满足约束条件的全部（x,y）点。 3.对目标函数z给任意两个常数，画出两条目标函数等值线，确定目标出函数的方向。沿这一方向，平移目标函数等值线到可行域的边界，确定最优解。 4.求解过最优解点的两个约束等式组成的线性方程组，求出最优解的数值。 5.代最优解数值到目标出函数中，得出最优值。 3.1 不确定型决策方法 某决策问题的方案和状态的收益表如下： 1. 悲观准则（ max—min 准则） 从每个方案中最差结果出发，从中选择最有利的方案 u（Ai）=min a i,j i =1,2,…,m j 最优方案是 u（A i※）=max u（A i） i 本例中是最优方案是A1 2. 乐观准则（ max—max 准则） 从每个方案中最好的结果出发，从中选择最有利的结果 u (Ai) = max ai,j j 最优方案是 Ai* ， u (Ai*) = max u(Ai) i 本例中最优方案是 A 2 。 3. 折衷准则 悲观准则和乐观准则的折衷.乐观系数为 ?，悲观系数为1－ ?. （0 ≤ ? ≤1） j j i 本例中：? = 0.8 最优方案A2 . 5. 遗憾准则（ min－max准则，后悔值准则） 若某种状态下未被考虑，将出现遗憾或后悔。对可能导至后悔最小的方案进行选择。 先列出后悔值矩阵： 后悔值的评价标准 r(Ai)= max b i, j i = 1,2,…,m. j r(A i *)= min r (A i ) i 最优方案为 A 1 ， A 4 。 用各准则进行决策后，可再进行分析和比较。 3.2 风险型决策方法 在不确定型决策中，将外部环境分成若干状态：s1,s2,…,sm，但各种状态的信息不知道。 在风险型决策中，同样将环境分成若干状态：s1,s2,…,sm ，但每一种状态出现的概率可以直接预测或间接预测出来，即对每一状态si，知道出现的概率 p ( s i ) ( i = 1,2,…,m ), 再进行决策。 1. 概率最大原则 根据所给出