1
运筹学
2 第一章 绪论
第二章 线性规划
如何建立线性规划的数学模型；
线性规划的标准形有哪些要求？如何把一般的线性规划化为标准形式？
如何用图解法求解两个变量的线性规划问题？线性规划问题的解有哪些性质？
如何用单纯形方法、两阶段算法 求解线性规划问题？
如何写出一个线性规划问题的对偶问题？如果已知原问题的最优解如何求解对偶问题的最优解？（对偶的性质，互补松紧条件）
对偶单纯形方法适合解决什么样的问题？如何求解？
对于已经求解的一个线性规划问题如果改变价值向量和右端向量原最优解/基是否仍是最优解/基？如果不是，如何进一步求解？
3 1、建立线性规划的数学模型：
特点：
（1）每个行动方案可用一组变量（x1，…，xn）的值表示，这些变量一般取非负值；
（2）变量的变化要受某些限制，这些限制条件用一些线性等式或不等式表示；
（3）有一个需要优化的目标，它也是变量的线性函数。
2、线性规划的标准形有哪些限制？如何把一般的线性规划化为标准形式？
目标求极小；约束为等式；变量为非负。
min
b 0TzCXAXX
例：把下列线性规划化为标准形式：
121212112max 2328 1 20,0zxxxxxxxxx
3、如何用图解法求解两个变量的线性规划问题？由图解法总结出线性规划问题的解有哪些性质？
例：参看ppt（唯一最优解、无穷多最优解、无界解、无解）
线性规划解的性质：（基、基本解、基本可行解、凸集、顶点）
定理1 线性规划的可行域是凸集。 4 定理2 X是线性规划基可行解的充分必要条件是X是可行域的顶点。
定理3 线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。
4、如何用单纯形方法求解线性规划问题？（单纯形表）
第 1 页 共 29 页 《运筹学》复习参考资料
资料加工、整理人——杨峰（函授总站高级讲师）
要求掌握的各部分知识点
第一部分 线性规划问题的求解（相当于教材的第一章）
——重要算法：单纯形迭代、大M法单纯形迭代、表上作业法、匈牙利法
第二部分 动态规划问题的求解（相当于教材的第三章）
——重要算法：图上标号法
第三部分 网络分析问题的求解（相当于教材的第四章）
——重要算法：破圈法、TP标号法、寻求网络最大流的标号法
第四部分 存储论简介（相当于教材的第七章）
※杨老师关于学习方法的提示：《运筹学》属于应用数学的范畴，本门课程在管理类本科生层次开设时，又称“管理运筹学”，是现代数学理论和计算机技术应用于管理科学的新兴学科。非应用数学系（专业）学生学习本门课程之前务必先具备“高数Ⅱ”（线性代数、概率论与数理统计）的知识基础。学员同志们通过学习，必须领会数学建模的思想、系统工程的思想。
非全日制学生学习时，只要求知道若干典型数学模型及其算法的操作，即只须明白“怎样做”，而不必去过问“为什么”要这样做。 第 2 页 共 29 页 第一部分 线性规划问题的求解
一、两个变量的线性规划问题的图解法：
㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。
定义：达到目标的可行解为最优解。
㈡图解法：
图解法采用直角坐标求解：x1——横轴；x2——竖轴。1、将约束条件（取等号）用直线绘出；
2、确定可行解域；
3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；
注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。
4、确定最优解及目标函数值。
㈢参考例题：（只要求下面这些有唯一最优解的类型）
例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：
案例. 石华建设监理公司监理工程师配置问题
1问题重述
石华建设监理公司 ( 国家甲级 ) 侧重于国家大中型项目的监理，仅在河北省石家庄市就曾同时监理七项工程，总投资均在 5 000 万元以上．由于工程开工的时间不同，各工程工期之间相互搭接，具有较长的连续性， 1998 年监理的工程量与 1999 年监理的工程量大致相同．每项工程安排多少监理工程师进驻工地，一般是根据工程的投资、建筑规模、使用功能、施工的形象进度、施工阶段来决定的．监理工程师的配置数量随之变化．由于监理工程师从事的专业不同，他们每人承担的工作量也是不等的．有的专业一个工地就需要三人以上，而有的专业一人则可以兼管三个以上的工地．因为从事监理业的专业多达几十个，仅以高层民用建筑为例就涉及到建筑学专业、工民建 ( 结构 ) 专业、给水排水专业、采暖通风专业、强电专业、弱电专业、自动控制专业、技术经济专业、总图专业、合同和信息管理专业等，这就需要我们合理配置这些人力资源．为了方便计算，我们把所涉及的专业技术人员按总平均人数来计算，工程的施工形象进度按标准施工期和高峰施工期来划分．通常标准施工期需求的人数较容易确定．但高峰施工期就比较难确定了，原因有两点： (1) 高峰施工期各工地不是同时来到，是可以事先预测的，在同一个城市里相距不远的工地，就存在着各工地的监理工程师如何交错使用的运筹问题． (2) 各工地总监在高峰施工期到来的时候要向公司要人，如果每个工地都按高峰施工期配置监理工程师的数量，将造成极大的人力资源浪费，这一点应该说主要是人为因素所造成的．因此，为了达到高峰施工期监理工程师配置数量最优，人员合理地交错使用，扼制人为因素，根据历年来的经验对高峰施工期的监理工程师数量在合理交错发挥作用的前提下限定了范围．另经统计测算得知，全年平均标准施工期占 7 个月，人均年成本 4 万元；高峰施工期占 5 个月，人均年成本 7 万元．标准施工期所需监理工程师如下表所示．
应用风险型决策方法必须具备以下条件:
（1）具有决策者期望达到的明确目标
（2）存在决策者可以选择的两个以上可行备选方案
（3）存在着决策者无法控制的两种以上的自然状态
（4）不同行动方案在不同自然状态下的收益值或损失值可以计算出来
（5）决策者能估计出不同的自然状态发生的概率
网络计划技术的应用准备工作
1确定计划目标2项目任务活动的分解3确定各工序的衔接顺序4确定各个工序时间
网络计划图的绘制规则:
（1）网络图只能有一个总开始事项，一个总结束事项
（2）网络图是有向图，不允许有回路
（3）事项i,j之间不允许有两个或两个以上的工序
（4）必须正确表示工序之间的先行后继关系
（5）虚工序的运用
后验分析的具体工作步骤包括:
补充新信息，计算修正概率，后验决策，计算补充新信息的价值，重新决策
线性规划模型的标准型:
目标函数最大化，约束条件为等式，变量符号为非负
运筹学的工作程序
步骤一 明确问题
步骤二 问题归类与概念化
步骤三 建立数学模型
步骤四 求解模型
步骤五 结果分析与模型检验
步骤六 实施解决
分析动态规划的基本方程时，必须做到以下几点:
（1）把实际问题恰当地划分为若干个阶段
（2）正确地选择状态变量，使它既能描述过程的演变特性，又要满足无后效性
（3）确定决策变量及每阶段的允许决策集合
（4）正确写出状态转移方程
（5）正态写出阶段指标函数和过程指标函数
评价排队系统优劣的六项数量指标是:
队长，列队长，逗留时间，等待时间，系统负荷水平，系统状态概率
