下载文档原格式
运筹学复习重点第1章线性规划与单纯形法（1）化线形规划标准形的手法（2）线性规划解的概念、解的情形、解的判定（3）单纯形法的计算过程、迭代逻辑。
（4）熟练运用单纯形表求解问题；若给出单纯形表，要会解读，会基于单纯形法基本原理反推出表中一些参数。
（5）两阶段法、大M法第2章对偶理论和灵敏度分析（1）会写对偶问题，掌握对偶性质，原问题与对偶问题之间的关系。
（2）互补松弛定理的应用：知道一个问题的最优解，求另一个问题的最优解。
（3）对偶单纯形法（4）当目标函数系数和右端项变化时灵敏度分析的简便方法第4章整数规划（1）分支定界法：如何构造分支子问题，如何更新目标函数最优值上下界，何时终止。
（2）割平面法：如何写对源约束方程；如何拆分、组装割平面方程；如何利用对偶单纯形法继续求解。
第5章无约束优化（1）凸函数与凸规划的定义与判别（2）一维搜索的0.618法基本原理和迭代过程（3）无约束优化的最速下降法的基本原理、迭代过程第6章约束极值优化（1）可行下降方向的含义、满足什么代数条件、几何意义（2）正确写出Kuhn-Tucker条件，理解K-T条件与最优解的关系（3）利用Kuhn-Tucker条件，求出K-T点和最优解。
（4）外点法和内点法的基本原理、无约束优化目标函数的一般构造手法第7章动态规划（1）动态规划的基本原理和基本方程（2）动态规划的逆推解法（3）动态规划求静态规划问题的套路第8章图与网络优化（1）图的基本概念、树的基本性质、最小支撑树的求法（2）求最短路的Dijkstra算法（3）增广链的概念、用途，求网络最大流的标号法第10章排队论（1）排队系统基本性能指标的含义、关系（2）泊松流与负指数分布的关系，排队系统中基本参数λ和μ含义的多维解读。
（3）系统状态概率Pn的含义、它在推导系统基本性能指标中的基础地位，推导它自身所依据的状态转移图。
（4）M/M/1模型、M/M/c模型的状态转移图，概率平衡方程，以及了解系统状态概率、基本性能指标的计算过程。
运筹学必考知识点总结在运筹学中，有一些必考的知识点是非常重要的。
这些知识点涵盖了运筹学的基本概念、方法和模型，对于考生来说，掌握这些知识点是至关重要的。
本文将对运筹学的一些必考知识点进行总结，帮助考生更好地备考。
1. 线性规划线性规划是运筹学中的重要方法之一，它通过建立数学模型来解决各种决策问题。
在线性规划中，目标是最大化或最小化一个线性函数，同时满足一系列线性约束条件。
考生需要掌握线性规划的基本理论，包括线性规划模型的建立、单纯形法和对偶理论等内容。
2. 整数规划整数规划是线性规划的扩展，它要求决策变量取整数值。
整数规划在实际应用中有着广泛的用途，因此对于考生来说，掌握整数规划的基本理论和解题方法是必不可少的。
3. 动态规划动态规划是一种用于求解多阶段决策问题的优化方法。
在动态规划中，问题被分解为多个子问题，并且这些子问题之间存在重叠。
考生需要了解动态规划的基本原理、状态转移方程的建立以及动态规划算法的实现。
4. 网络流问题网络流问题是运筹学中的一个重要领域，它涉及到图论和优化算法等多个方面的知识。
在网络流问题中，主要考察最大流、最小割、最短路等问题的求解方法。
5. 效用理论效用理论是运筹学中的一个重要分支，它研究人们在做出决策时的偏好和选择。
效用函数、期望效用、风险偏好等概念是考试中的热点内容。
6. 排队论排队论是研究排队系统的运作规律和性能指标的数学理论。
在排队论中，考生需要了解排队系统的稳定性条件、平衡方程、性能指标的计算方法等。
7. 多目标决策多目标决策是指在考虑多个目标时的决策问题。
在多目标决策中，往往需要考虑到多个目标之间的矛盾和权衡，因此考生需要掌握多目标规划的基本原理和解题方法。
8. 随机规划随机规划是考虑到不确定因素的决策问题。
在随机规划中，目标函数、约束条件等参数都是随机变量，因此需要考虑到风险和概率的因素。
以上是一些运筹学中的必考知识点，考生在备考过程中需要重点关注这些知识点。
《运筹学基础》复习要点一、基本概念与理论1．任意多个凸集的交集还是凸集。
2．任意多个凸集的并集不一定是凸集3．给定1R b ∈及非零向量n R a ∈，称集合}|{b x a R x H Tn=∈=是nR 的一个超平面。
4．由超平面}|{b x a R x H Tn=∈=的两个半平面}|{b x a R x H T n ≥∈=+和}|{1b x a R x H T n ≤∈=都是凸集。
5．设S 是凸集，S x ∈。
若对任何z y S z S y ≠∈∈,,，以及任何10<<λ，都有z y x )1(λλ-+≠，则称x 为S 的顶点。
6．如果一个LP 问题无界，则它的对偶问题必无可行解。
7．设w x ,分别为原始LP 问题、对偶问题的可行解，若b w x c T T =，则原始LP 问题、对偶问题的最优解分别为w x ,。
8.可行解x 是基本可行解的充分必要条件是x 的正分量，所对应的A 中列向量线性无关。
9.写出LP 问题的对偶问题0..min ≥≥⎪⎩⎪⎨⎧x b Ax x c t s T的对偶问题是： 0..min ≥≤⎪⎩⎪⎨⎧w c w A w b t s TT10．设一个标准形式的LP 问题的基为B ，右端向量为b ，则对应的基本解是⎪⎪⎭⎫⎝⎛=-01b B x 。
11．线性规划问题的可行域是凸集。
12．设线性规划问题LP 为0..min ≥=⎪⎩⎪⎨⎧x b Ax t s x c T B 为一个基，对应的典式为0..min 111≥=+⎪⎩⎪⎨⎧-=---x b B Nx B x t s x b B c z N B T TB ζ 其中),0(1T N TB Tc N B c -=-ζ。
13.线性规划问题的规范形式为0..min ≥≥⎪⎩⎪⎨⎧x b Ax x c t s T14. 线性规划问题的标准形式为0..min ≥=⎪⎩⎪⎨⎧x b Ax t s xc T15.线性规划问题的一般形式为⎪⎪⎪⎩⎪⎪⎪⎨⎧+==≥+=≥==n q j x qj x m p i b x a p i b x a t s x c j ji Ti i Ti T ,,1,,2,10,,1,,2,1..min 为自由变量16.对线性规划问题，关于它的解分三种情况：问题无解、问题无界和问题有最优解。
运筹学复习要点1．线性规划部分（1）会求一般线性规划问题的标准形式。
要求见38页表格。
（2）了解线性规划的可行解、基解、基可行解、最优解、基变量、非基变量等概念。
（3）知道单纯形法的几个基本定理。
（4）掌握大M法与两阶段法求解线性规划问题的方法步骤。
（5）知道线性规划问题唯一最优解，有无界解，无穷多最优解，无可行解的判别方法。
（6）了解单纯形法的矩阵表示方法，会找出B-1 。
2．对偶理论（1）会求原规划问题的对偶问题。
（2）了解对偶原理。
（3）知道对偶单纯形法的迭代步骤。
（4）灵敏度分析部分：会对增加变量与增加约束条件情况进行分析。
3．运输问题（1）知道运输问题的数学模型。
（2）掌握运输问题的表上作业法（初始方案的确定，最优性检验，调运方案的调整）。
（3）会处理产大于销的运输问题。
4．指派问题（1）知道匈牙利法解决分配问题的理论依据，掌握匈牙利法求解指派问题的方法。
（2）知道人多任务少时的处理方法及人比任务少时的处理方法。
5．整数规划（1）会用割平面法求解整数规划问题6．目标规划（1）会建立目标规划数学模型，会解释目标约束的意义。
（2）会用图解法求解目标规划。
7．图论部分（1）了解图的基本概念：简单图、完全图、偶图、子图、部分图等，次（度）、链、路、圈、回路等。
（2）知道树的概念和基本性质。
知道求图的最小部分树的理论依据和方法。
（3）会求最短路。
（4）会求网络的最大流与最小割。
（5）会求最小费用流。
8.动态规划（1）了解动态规划的基本概念及最优化原理.（2）知道动态规划的基本方程与求解方法.9．决策分析（1）掌握不确定型决策分析条件收益矩阵与机会损失矩阵建立方法及相关决策准则。
（2）会运用决策树方法解决简单的序贯决策问题。
（3）掌握AHP法的分析问题步骤，会用和法求判断矩阵的特征向量。
运筹学复习题一、填空题1．在线性规划标准形式中，要求约束条件右侧常数),,2,1(m i b i =为_____ 数。
《运筹学》课程复习资料一、判断题：1.图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。
[ ]2.线性规划问题的每一个基本解对应可行解域的一个顶点。
[ ]3.任何线性规划问题存在并具有惟一的对偶问题。
[ ]4.已知y i*为线性规划的对偶问题的最优解，若y i*＞0，说明在最优生产计划中第i种资源已完全耗尽。
[ ] 5.运输问题是一种特殊的线性规划问题，因而其求解结果也可能出现下列四种情况之一：有惟一最优解，有无穷多最优解，无界解，无可行解。
[ ]6.动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已做出的决策。
[ ]7.如果线性规划问题存在最优解，则最优解一定可以在可行解域的顶点上获得。
[ ]8.用单纯形法求解Max型的线性规划问题时，检验数Rj＞0对应的变量都可以被选作入基变量。
[ ]9.对于原问题是求Min，若第i个约束是“＝”，则第i个对偶变量yi≤0。
[ ]10.用大M法或两阶段法单纯形迭代中若人工变量不能出基(人工变量的值不为0)，则问题无可行解。
[ ]11.如图中某点vi 有若干个相邻点,与其距离最远的相邻点为vj,则边[vi,vj]必不包含在最小支撑树内。
[ ]12.在允许缺货发生短缺的存贮模型中，订货批量的确定应使由于存贮量的减少带来的节约能抵消缺货时造成的损失。
[ ] 13.根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解。
[ ] 14.在线性规划的最优解中，若某一变量xj为非基变量，则在原来问题中，改变其价值系数cj，反映到最终单纯形表中，除xj的检验数有变化外，对其它各数字无影响。
[ ]15.单纯形迭代中添加人工变量的目的是为了得到问题的一个基本可行解。
[ ]16.订购费为每订一次货所发生的费用，它同每次订货的数量无关。
[ ]17.一个动态规划问题若能用网络表达时，节点代表各阶段的状态值，各条弧代表了可行方案的选择。
《运筹学》复习资料整理总结1. 建立线性规划模型的步骤。
确定决策变量 确定目标函数 确定约束条件方程2. 线性规划问题的特征。
都有一个追求的目标，这个目标可表示为一组变量的线性函数，按照问题的不同，追求的目标可以为最大，也可以为最小。
问题中有若干个约束条件，用来表示问题中的限制或要求，这些约束条件可以用线性等式或线性不等式表示。
问题中用一组决策变量来表示一种方案。
3. 线性规划问题标准型的特征。
4. 化标准型的方法。
123123123123min z 2+223-8340,0,x x x x x x x x x x x x =+-+=⎧⎪-+-≤⎨⎪≤≥⎩为自由变量123123123123min z 2+223-634,0,x x x x x x x x x x x x =+-+=⎧⎪-+-≥⎨⎪≥⎩为自由变量5. 基本解：令其余的变量取值为0，则得到Ax=b 的一个解y,称此解为线性规划问题的基本解。
6. 基本可行解：若基本解y 满足y ≥0,则称这个解为基本可行解。
7. 可行解：满足约束条件的解x=（x1、x2、……xn ）T 称为线性规划问题的可行解。
8. 最优解：函数达到最优的可行解叫做最优解。
9.图解法适合于变量个数为2个的线性规划问题。
10.单纯形法解线性规划问题如何确定初始基本可行解。
（1）约束条件为≤，先加入松弛变量x1、x2……xm后变为等式，取松弛变量为基本变量（2）约束条件为=，先加入人工变量xm+1、xm+2……xm+n，人工变量价值系数为m（3）约束条件为≥，先加入多于变量xn+1、xn+2……xm+n后变为等式，在添加人工变量xn+m+111.单纯形法最优解的检验准则。
（1）若基本可行解x’对应的典式的目标函数中非基变量的系数全部满足cN-cBB-1Pj≤0,则基本可行解x’为原问题的最优解。
（2）若基本可行解x’对应的典式的目标函数中所有非基变量的系数满足cN-cBB-1Pj≤0,且有一非基变量的系数满足Ck-Zk=0,则原问题有无穷多组最优解12.对目标函数为极小（min）型的线性规划问题，用单纯形法解的三种处理方法。
运筹学知识点总结一、线性规划线性规划是运筹学中最基础、最重要的一个分支。
它的基本形式可以表示为：Max cxs.t. Ax ≤ bx ≥ 0其中，c是一个n维的列向量，x是一个n维的列向量，A是一个m×n的矩阵，b是一个m维的列向量。
线性规划的目标是找到满足约束条件的x，使得目标函数cx取得最大值。
而当目标是最小化cx时，则是最小化问题。
线性规划问题有着很好的性质，它的最优解一定存在且一定在可行域边界上。
而且，很多非线性规划问题也可以通过线性化转化成线性规划问题，因此线性规划具有广泛的适用范围。
二、整数规划整数规划是线性规划的一个扩展，它在线性规划的基础上增加了对决策变量的整数取值限制。
这样的问题往往更加接近实际情况。
整数规划问题的一般形式可以表示为：Max cxs.t. Ax ≤ bx ∈ Zn整数规划问题的求解难度要比线性规划问题高很多。
因为整数规划问题是NP-hard问题，也就是说它没有多项式时间的算法可以解决。
但是对于特定结构的整数规划问题，可以设计专门的算法来求解。
比如分枝定界法、动态规划等。
整数规划问题在许多领域都有着广泛的应用，比如生产调度、设备配置、网络设计等。
三、动态规划动态规划是一种用来求解具有重叠子问题结构的最优化问题的方法。
它的核心思想是将原问题分解成一系列相互重叠的子问题，然后利用子问题的最优解来构造原问题的最优解。
动态规划问题的一般形式可以表示为：F(n) = max{F(n-1), F(n-2)+cn}其中，F(n)是问题的最优解，cn是问题的参数，n是问题的规模。
动态规划问题的求解是一个自底向上的过程，它依赖于子问题的最优解，然后通过递推关系来求解原问题的最优解。
动态规划在资源分配、路径优化、排程问题等方面有着广泛的应用。
四、决策分析决策分析是一种用来帮助人们做出最佳决策的方法。
它可以应用在各种风险决策、投资决策、生产决策等方面。
决策分析的一般形式可以表示为：Max E(u(x))其中，E(u(x))是对决策结果的期望效用，u(x)是决策结果的效用函数，x是决策变量。
运筹学复习提纲第一章线性规划1、线性规划的三个要素目标函数、决策变量、约束条件一般形式，标准形式（转化）2、求解线性规划的图解法3、线性规划解的可能性唯一最优解、无穷多最优解、无界解、无可行解(原因)4、单纯形法（必考点）基，基变量，基本解，基本可行解，可行解，最优解，最优基单纯形法解题思路、步骤，最优解的判定定理，单纯形法的管理启示大M法的可能结果图解法。
大M法。
线性规划数学模型的建立？（建模）第二章线性规划讨论1、线性规划灵敏度分析价值系数、资源向量第三章 对偶规划 1、对偶模型 2、对偶性质对称性定理，弱对偶定理，强对偶定理，互补松驰定理 3、影子价值对偶问题的最优解，影子价值的经济含义 （课后习题69页，5）1、 求该问题产值最大的最优解和最优值2、 求出该问题的对偶问题和最优值3、 给出两种资源的影子价格，说明其经济含义：第一只能够资源限量由2 变为4 ，最优解是否改变？4、 代加工产品丁，每单位产品需要消耗第一种资源两单位，消耗第二种资源3单位，应该如何定价？ 解：1、先转化成标准型：利用单纯形法求解：123123123123max 42832..68,,0Z x x x x x x s t x x x x x x =++++≤⎧⎪++≤⎨⎪≥⎩1234512341235max 4200832..680;1,2,,5jZ x x x x x x x x x s t x x x x x j =++++⎧+++=⎪+++=⎨⎪≥=⎩该问题有唯一最优解： 2、利用对偶问题的性质求解对偶问题的最优解和最优值：第一种资源影子价格为2，表明第一种资源增加1个单位，产值(或利润)增加2个单位，即第一种资源为紧缺资源(x 4 = 0)； 第二种资源影子价格为0，表明第二种资源增加1个单位，产值(或利润)增加0个单位，第二种资源有剩余(x 5 = 6) 。
3、对偶问题数学模型：其对偶模型为：*(0,0,2,0,6)TX =*4Z =*(2,0,12,5,0)Y =*4Z =123123123123max 42832..68,,0Z x x x x x x s t x x x x x x =++++≤⎧⎪++≤⎨⎪≥⎩121212min 2886431W y y y y y y =++≥⎧⎪+≥⎪，根据题意：(4)设产品丁的产量为x6第四章整数规划1、整数规划的含义2、整数规划的类型及求解方法3、整数规划问题建模 0-1规划建模4、分枝定界法第五章目标规划1、目标规划问题建模2、目标规划图解法（满意解）问：在材料不能超用的条件下，企业如何安排生产计划？要求尽可能满足下列目标：(1)力求使利润指标不低于80元；(2)考虑到市场需求, 两种产品的产量需保持1:1的比例；(3)设备A既要求充分利用，又尽可能不加班；(4)设备B必要时可以加班，但加班时间尽可能少。
1. 简答题（1） 运筹学的工作步骤提出和形成问题：即要弄清问题的目标，可能的约束，问题的可控变量以及相关的参数，搜集相关资料；建立模型：即把问题中可控变量，参数，目标与约束之间的关系用模型表示出来；求解：用各种手段将模型求解，解可以是最优解，次优解，满意解。
复杂模型的求解需用计算机，解得精度要求可有决策者提出；解的检验：首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题；解的控制：通过控制解的变化过程决定对解是否做一定的改变； 解的实施：是指将解用到实际中必须考虑的实际问题，如向实际部门讲清解的用法，在实施中可能产生的问题和修改。
（2）退化产生原因及解决办法单纯形法计算中用θ规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。
勃兰特规则：1.选取cj-zj ＞0中下标最小的非基变量xk 为换入变量，即k=min(j ｜cj-zj ＞0)2. 当按θ规则计算存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量。
（3）对偶问题的经济解释• 这说明yi 是右端项bi 每增加一个单位对目标函数Z 的贡献。
• 对偶变量 yi 在经济上表示原问题第i 种资源的边际价值。
• 对偶变量的值 yi*所表示的第i 种资源的边际价值，称为影子价值。
∑∑=====nj mi i i j j y b x c Z 11ωiiy b Z =∂∂若原问题的价值系数Cj 表示单位产值，则yi 称为影子价格； 若原问题的价值系数Cj 表示单位利润，则yi 称为影子利润。
影子价格不是资源的实际价格，而是资源配置结构的反映，是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化。
（4）分枝定界法步骤a) 先求出整数规划相应的LP(即不考虑整数限制)的最优解， b) 若求得的最优解符合整数要求，则是原IP 的最优解； c) 若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束，在原可行域中剔除部分非整数解。
1. 简答题（1） 运筹学的工作步骤提出和形成问题：即要弄清问题的目标，可能的约束，问题的可控变量以及相关的参数，搜集相关资料；建立模型：即把问题中可控变量，参数，目标与约束之间的关系用模型表示出来；求解：用各种手段将模型求解，解可以是最优解，次优解，满意解。
复杂模型的求解需用计算机，解得精度要求可有决策者提出；解的检验：首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题；解的控制：通过控制解的变化过程决定对解是否做一定的改变； 解的实施：是指将解用到实际中必须考虑的实际问题，如向实际部门讲清解的用法，在实施中可能产生的问题和修改。
（2）退化产生原因及解决办法单纯形法计算中用θ规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。
勃兰特规则：1.选取cj-zj ＞0中下标最小的非基变量xk 为换入变量，即k=min(j ｜cj-zj ＞0)2. 当按θ规则计算存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量。
（3）对偶问题的经济解释• 这说明yi 是右端项bi 每增加一个单位对目标函数Z 的贡献。
• 对偶变量 yi 在经济上表示原问题第i 种资源的边际价值。
• 对偶变量的值 yi*所表示的第i 种资源的边际价值，称为影子价值。
∑∑=====n j mi i i j j y b x c Z 11ωiiy b Z=∂∂若原问题的价值系数Cj 表示单位产值，则yi 称为影子价格； 若原问题的价值系数Cj 表示单位利润，则yi 称为影子利润。
影子价格不是资源的实际价格，而是资源配置结构的反映，是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化。
（4）分枝定界法步骤a) 先求出整数规划相应的LP(即不考虑整数限制)的最优解， b) 若求得的最优解符合整数要求，则是原IP 的最优解； c) 若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束，在原可行域中剔除部分非整数解。
1. 简答题（1） 运筹学的工作步骤提出和形成问题：即要弄清问题的目标，可能的约束，问题的可控变量以及相关的参数，搜集相关资料；建立模型：即把问题中可控变量，参数，目标与约束之间的关系用模型表示出来；求解：用各种手段将模型求解，解可以是最优解，次优解，满意解。
复杂模型的求解需用计算机，解得精度要求可有决策者提出；解的检验：首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题；解的控制：通过控制解的变化过程决定对解是否做一定的改变； 解的实施：是指将解用到实际中必须考虑的实际问题，如向实际部门讲清解的用法，在实施中可能产生的问题和修改。
（2）退化产生原因及解决办法单纯形法计算中用θ规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。
勃兰特规则：1.选取cj-zj ＞0中下标最小的非基变量xk 为换入变量，即k=min(j ｜cj-zj ＞0)2. 当按θ规则计算存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量。
（3）对偶问题的经济解释• 这说明yi 是右端项bi 每增加一个单位对目标函数Z 的贡献。
• 对偶变量 yi 在经济上表示原问题第i 种资源的边际价值。
• 对偶变量的值 yi*所表示的第i 种资源的边际价值，称为影子价值。
∑∑=====n j mi i i j j y b x c Z 11ωiiy b Z=∂∂若原问题的价值系数Cj 表示单位产值，则yi 称为影子价格； 若原问题的价值系数Cj 表示单位利润，则yi 称为影子利润。
影子价格不是资源的实际价格，而是资源配置结构的反映，是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化。
（4）分枝定界法步骤a) 先求出整数规划相应的LP(即不考虑整数限制)的最优解， b) 若求得的最优解符合整数要求，则是原IP 的最优解； c) 若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束，在原可行域中剔除部分非整数解。
d) 然后，再在缩小的可行域中求解新构造的线性规划的最优解，这样通过求解一系列线性规划问题，最终得到原整数规划的最优解。
（5）树的性质一个无圈的连通图称为树。
1 树至少有两个悬挂点。
2 一个图为树的充要条件是：不含圈，边数比点数少1.3 一个图为树的充要条件是：连通，边数比点数少1.4 一个图为树的充要条件是：任两点之间恰有一条链。
2. 建模题（1）线性规划建模：).(x ,,x ,x b ),(x a x a x a ).(b ),(x a x a x a b ),(x a x a x a ).(x c x c x c z max(min)n mn m m m n n n n n n 310211121221122222121112121112211≥≥=≤+++≥=≤+++≥=≤++++++=ΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛ约束条件目标函数（2）目标规划建模：最好等于：min d - -d + 最好不大于：min d + 最好不小于：min d -目标的重要程度不同，用优先等级因子P k 来表示第k 等级目标。
优先等级因子P k 是正的常数，P k >> P k+1 。
同一优先等级下的目标的相对重要性，赋以不同的加权系数w（3） 整数规划模型Max (min) Z = Σcjxj s.t. Σaijxj ≤ bi(i=1,2,…m) xj ≥ 0 且部分或全部是整数nj d d x Kk E d d x cmi b x ad w d wP Z k k j knj k k j kj inj j ijl kl L l l kl K k k k,...,2,10,,,...,2,1,...,2,1),()(min *1111=≥==-+==≥≤+=+-=+-=++=--=∑∑∑∑非负性约束目标约束绝对约束3. 证明题（1）证明可行域为凸集为了证明满足线性规划问题的约束条件的所有点(可行解)组成的集合是凸集，只要证明D 中任意两点连线上的点必然在D 内即可。
设是D 内的任意两点；X(1)≠X(2)。
（2）证明无界解的判定构造一个新的解 X (1)，它的分量为因 σm+k ＞0，所以对任意的λ＞0都是可行解，把x(1)代入目标函数内得∑==≥=nj j jj nj x b xP 1,,2,1,0,Λ()()()()()()()()()()TnTnx x x X x x x X222212112111,,,,,,ΛΛ==则有()()()()∑∑===≥==≥=nj j j j n j j j j nj x b x P n j x b x P 122111,,2,1,0,,,2,1,0,ΛΛ 令X=(x 1，x 2，…，x n )T 为x (1),x (2)连线上的任意一点，即X=αX (1)+(1-α)X (2)(0≤α≤1) X 的每一个分量是()()21)1(j j j x x x αα-+=，将它代入约束条件， 得到 ()()()[]()()()b b b b x P x P x P x x P x P n j nj j j j j n j j j n j n j j j j j j =-+=-+=--=∑∑∑∑∑=====αααααα11221111211又因()()01,0,0,21>->≥ααj j x x ，所以x j ≥0，j=1,2,…,n 。
由此可见X ∈D ，D 是凸集。
证毕。
()()()()km j n m j x x a b x j k m km i ii+≠+===>-=++并且,,,1;0011','1Λλλλz=z0+λσm+k ；因σm+k ＞0，故当λ→+∞，则z →+∞，故该问题目标函数无界。
（3）证明弱对偶性4. 计算题（1） 标准型，单纯行法计算∑∑∑==++=+++++------------→-mi ini n mi m i i m mi ii mmn m m m m m n m n m n m m BB in m m j a c c a c c b c z a a b x c a a b x c a a b x c x x x x b X C c c c c c 111,111,221,2222111,1111111100100001ΛΛΛΛMM M M M M MM ΛΛΛΛΛΛΛθθθθ..,0;;min :,证毕于是得到得到右乘上式将所以满足是对偶问题的可行解，因原问题的对偶问题是左乘上式，得到将是对偶问题的可行解，若即以满足约束条件是原问题的可行解，所因设原问题是bY X A Y X C C X A Y X C A Y Y Y C YA Yb bY X A Y Y Y bX A X 0X b;AX CX;z max ≤≤≥≥≥≥=≤≤≥≤=ω（2） 对偶型计算原问题（LP ）对偶问题,,,max 2112121112112211≥⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛⎪⎪⎪⎭⎫⎝⎛+++=nm n mn m m n nn x x x b b x x x a a a a a a x c x c x c z ΛM M ΛM O M M ΛΛ()()0,,,,,,,,,min 2121211121121m 2211≥≥⎪⎪⎪⎭⎫⎝⎛+++=n n mn m m n m m y y y c c c a a aa a a y y yb y b y b y ΛΛΛM OM M ΛΛΛω（3）运输问题1.初始解确定最小元素法：–从单位运价表中逐次挑选最小元素，安排运量min{a i,b j}。
–然后，划去该元素所在行或列：•当产大于销，划去该元素所在列；•当产小于销，划去该元素所在行。
伏格尔法：第一步：求出每行次小运价与最小运价之差，记为ui，i=1,2,…,m ；同时求出每列次小运价与最小运价之差，记为vj，j=1，2，…，n ；第二步：找出所有行、列差额的最大值，即L=max{ui，vi}，差额L对应行或列的最小运价处优先调运；第三步：这时必有一列或一行调运完毕，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运完毕，就得到一个初始调运方案。
2.判定最优解闭合回路法：从每一空格出发找一条闭回路。
它是以某空格为起点，用水平或垂直线向前划，当碰到一数字格时可以转90°后，继续前进，直到回到起始空格为止。
当检验数还存在负数时，说明原方案不是最优解。
位势法：变量的检验数σij=cij –ui –vj=0， 即cij =ui +vj ，且令u1 =0，计算位势量ui 和vj 计算非基变量的检验数σij = c ij –u i – v j 3. 改进方法确定进基变量a) 检查非基变量xij 的检验数σij ，按 min{σij| σij <0}= σlk 确定xlk 进基。
确定离基变量b) 非基变量xlk 进基之后，能让它的运量增加多少呢？就要求它所在行和列的运量保持产销平衡。
保持产销平衡的方法是闭回路法。
c) 闭回路法：以进基变量xlk 所在格为始点和终点，其余顶点均为基变量的封闭回路。
d) 闭回路的画法：从进基变量xlk 所在格开始，用水平或垂直线向前划，每碰到一个基变量格转90º，继续前进，直到返回始点。
e) 奇偶点： 始点是偶点，依次奇偶相间标注；偶点标“+” ，表示运量增加量；奇点标“-” ，表示运量减少量。
f) 调整量：最小可减少的运量，即奇点运量的最小值。
奇点运量的最小值所在格的基变量离基。
4. 产销不平衡产大于销：只要增加一个假想的销地j=n+1(实际上是储存)，该销地总需要量为 而在单位运价表中从各产地到假想销地的单位运价为 销大于产：可以在产销平衡表中增加一个假想的产地i=m+1，该地产量为 在单位运价表上令从该假想产地到各销地的运价为（4） 指派问题1. 各行各列出现零元素a. 每行元素减去该行最小元素b. 每列元素减去该行最小元素 2. 进行试指派，寻求最优解a.给只有一个0元素的行（列）的0加圈，然后划去0元素所在行的其他0元素，记作φb. 加圈0元素数目等于矩阵的阶数，则指派问题达到最优解3. 做最少的直线覆盖所有0元素，已确定该系数矩阵中能找到最多的独立元素数a. 对没有圈的行打√号b. 对已打√的行所有含φ元素的列打√c. 在对打有√的列中含圈的元素打√d. 对没有打√的行及打√的列画一纵线，这就是覆盖所有0元素的最少直线e.∑∑==-nj j m i i b a 110;1,=+n i c ∑∑==-n j m i j j a b 110;,1=+j m c（5） 最小支撑树破圈法：任取一圈，去掉权重最大的边，重复进行直到无圈可破。
