赵 彤 zhaotong@gucas.ac.cn 运筹学模型与软件实践 Models and Software Practice of the Operations Research 赵 彤 zhaotong@gucas.ac.cn

第一章 线性规划 线性规划模型 线性规划的图解 单纯形方法介绍 Lindo\Lingo求解方法 线性规划模型在实际问题中的应用 第一章　线性规划 线性规划模型 线性规划的图解 单纯形方法介绍 Lindo\Lingo求解方法 线性规划模型在实际问题中的应用 WinQSB求解线性规划问题 Excel求解线性规划问题 Matlab求解线性规划问题

基本特点 研究对象 运筹学中应用最广泛的方法之一 运筹学中最基本的方法之一，网络分析、整数规划、目标规划以及多目标规划都是以线性规划方法为基础的 解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大 研究对象 有一定的人力、财力、资源条件下，如何合理安排使用，效率最高 某项任务确定后，如何安排人、财、物，使之最省

经典应用 合理利用线材问题：如何下料使用材最省 配料问题：在原料供应量的限制下如何获取最大利润。 投资问题：从投资项目中选取方案，使投资回报最大 产品生产计划：合理利用人力、物力和财力等，使获利最大 劳动力安排：用最少的劳动力来满足工作的需要 运输问题：如何制定调运方案，使运费最小 ．．．．．

为什么要使用线性规划？ 线性规划很容易而有效率的被求解 如果存在最优解，则肯定能够找到 功能强大的灵敏度分析 许多实际问题本质上是线性的

1.1 线性规划模型 线性规划问题及其一般数学模型 例1、多产品生产问题（Max, ） 设x1, x2 分别代表甲、乙两种电缆的生产量，

例2、配料问题（min, ) 设 x1, x2分别代表每粒胶丸中甲、乙两种原料的用量 从前面几个例子里有没有什么规律？

特点 要解决的问题的目标可以用数值指标反映 对于要实现的目标有多种方案可选择 有影响决策的若干约束条件 有没有潜台词？

线性规划数学模型的一般表示方式

隐含的假设 比例性：决策变量变化引起目标的改变量与决策变量改变量成正比 可加性：每个决策变量对目标和约束的影响独立于其它变量 连续性：每个决策变量取连续值 确定性：线性规划中的参数aij , bi , ci为确定值

综合后的写法： １：和式

综合后的写法： ２：向量

综合后的写法： ２：矩阵式

标准化变换的方法 1:目标函数的转化 目标函数为max型，价值系数一律反号。令 f(x) = -f(x) = -CX, 有 max f(x) = - min [- f(x)] = - min f (x) 2:约束条件的转化 　　如果某一约束条件是线性不等式 则可等价地转化为： 其中新引进的变量xn+i称为松弛变量

线性规划的基本概念

线性规划的基本概念 线性规划的基矩阵、基变量、非基变量 目标函数 约束条件 = 右边常数 行列式≠0 基矩阵 =

　　设系数矩阵A的秩为m，由m<n，故有无穷多解，假设前m个变量的系数线性无关，则： 使用向量形式： 方程组的基是B．设xB是对应于这个基的基变量 ，若令非基变量 ，并用高斯 消去法，可以求出一个解此解的非零分量的数目不大于方程个数m.

1.2 线性规划的图解法 f(x)=36

注释 可能出现的情况： 可行域是空集 可行域无界无最优解 最优解存在且唯一，则一定在顶点上达到 最优解存在且不唯一，一定存在顶点是最优解

基本假设

极点 凸集 凸集 不是凸集

线性规划问题的几个特点： 线性规划问题的可性解的集合是凸集 线性规划问题的基础可行解一般都对应于凸集的极点 凸集的极点的个数是有限的 最优解只可能在凸集的极点上，而不可能发生在凸集的内部

1.3 单纯形方法介绍 G.R.Dantzig(丹捷格)提出的单纯形法得到了广泛的应用，现行的线性规划求解软件大多数都基于单纯形方法的理论． 基于线性规划问题有最优解，则必可在某一基本可行解处达到． 单纯形方法的主要思路：先找一个基可行解，判别它是否存在最优解．若不是，就找一个更好的基可行解，再进行检验，如此迭代进行，直到找到最优解． 这里涉及到两个问题：一是寻找初始可行解，二是如何判别和迭代．

线性规划的计算机求解 本节将介绍如何使用计算机软件包Lindo求解线性规划(LP)问题 Lindo求解一个LP问题会得到如下几种结果：不可行(No Feasible Solution)、可行(Feasible)；可行时又分为:有最优解(Optimal Solution)和无界解(Unbounded Solution)

求解一个线性规划问题 例1 采用Lindo求解如下LP问题 在Lindo中已经假定所有变量都是非负的，所以非负约束不必再输入到计算机中

Lindo的界面及输入内容

Lindo的输出内容 有关松弛变量和剩余变量(Slack or Surplus)、对偶价值系数(Dual Price)等将在第三章作详细讨论

一个管理中的具体例子

采用Lindo计算

星期一 星期二 星期三 星期四 星期五 星期六 星期日 2 4 3 8

将Lindo程序转化成为Lingo程序

上例采用Lingo编制对应的程序

考虑进一步的问题

线性规划模型在实际问题中的应用 通过线性规划问题的Lindo、Lingo软件学习与应用，使同学掌握使用计算机软件去求解线性规划问题的方法。 下面将研究线性规划在工商管理中的应用，解决管理中的实际问题，进一步掌握对管理中的实际问题如何建立数学模型，并进行求解。

资源分配的问题（同前例题）

下料问题

Lindo求解过程

求解过程及分析

进一步的思考

配料问题

问题分析

LINDO求解结果

计算结果说明

WinQSB软件简介 WinQSB软件中的QSB表示Quantitative System for Business的缩写。早期的版本在DOS操作系统下运行，WinQSB在Windows操作系统下运行。 WinQSB是一种教学软件，对于非大型的问题一般都能计算，较小的问题还能演示中间的计算过程，特别适合多媒体课堂教学。 该软件可应用于管理科学、决策科学、运筹学及生产运作管理的求解问题。

用WinQSB软件求解线性规划模型

启动线性规划(LP)和整数规划(ILP)程序。 建立新问题或打开磁盘中已有的文件或创建新问题 点击开始 程序 WinQSB Linear and Integer Programming

输入数据 修改变量类型 按照固定的电子表格形式输入变量系数矩阵(如果上一步选择了Normal Model Form则按自由格式输入)

修改变量名和约束名 求解 系统默认的变量名为X1，X2,…,Xn,约束名为C1,C2, …,Cm。可以Edit菜单下修改变量和约束的名称 如果选择菜单的Solve and Analyze可以(1)直接求解Solve the problem;(2)求解并显示单纯形法的迭代步骤(Solve and Display Steps)以及图解法(Graphic Method,限两个变量)。 选择（1）时：

选择（2）时：

Excel求解线性规划问题 Excel是分析和求解线性规划问题的一个很好工具 作为Office家族一员，Excel的普及性和易学性也会让大家感到利用计算机软件包求线性规划问题非常容易

从例题开始

Excel表格作出的设置 SUMPRODUCT函数的功能为：E5=C5*C9+D5*D9 该函数可以将2至30个大小形状相同的单元格区域(每个单元格区域用逗号隔开)中的对应数值相乘后再相加

加载求解线性规划问题的宏 注意：需要使用OFFICE的安装光盘

调用求解规划问题的宏

求解规划问题的对话框1 设置目标单元格 等于 可变单元格 推测 指定目标函数所在单元格的引用位置，经求解后获得一特定值、最大值或最小值 指定是否需要对目标单元格求解最大、最小值或某一指定数值。如果需要让目标函数为某一指定数值（解方程？），则要在右侧编辑框中输入 指决策变量所在的各个单元格、不含公式可以有多个区域或单元格。（目标单元格必须直接或间接与目标单元格相联系） 自动定位“设置目标单元格”中的可变单元格

求解规划问题的对话框2 约束 指定约束条件所在单元格的引用位置，通过“添加”按钮添加

求解规划问题的“选项”1 最长运算时间 迭代次数 精度 允许误差 设定求解过程的时间，允许的最大值为32767秒 设定求解过程的迭代运算次数，允许的最大值为32767次 以确定约束条件单元格中的数值是否满足目标值或上下界 在此输入满足整数约束条件的目标单元格求解结果与最佳结果间的允许百分偏差。这个选项只应用于具有整数约束条件的问题。设置的允许误差越大，求解过程就越快。

求解规划问题的“选项”2 收敛度 采用线性模型 显示迭代结果 当最近五次迭代时，目标单元格中数值的变化小于“收敛度”编辑框中设置的数值时，“规划求解”停止运行。收敛度只应用于非线性规划问题，并且必须由一个在0和1之间的小数表示。设置越小，收敛度越高（所需计算时间越长）。 当模型中的所有关系都是线性的，并且希望解决线性优化问题时，选中此框可加速求解进程。 每次迭代后都将中断“规划求解”，并显示当前的迭代结果

求解规划问题的“选项”3 自动按比例缩放 假定非负 估计 导数 搜索 当输入和输出值数量差别很大时，可以使用此功能，例如，对一项百万元投资的盈利百分数进行放大。 假定可变单元格的下限为0。 指定在每个一维搜索中用来得到基本变量初始估值的逼近方案 指定用于估计目标函数和约束函数偏导数的差分方程 指定每次的迭代算法，以确定搜索方向

求解规划问题的结果1

求解规划问题的结果2（对话框给出的信息） 满足所有约束条件 求解达到最长运输时间停止 求解达到最大迭代次数停止 目标单元格中数值不收敛 “规划求解”未找到合适结果 “规划求解”应用户要求终止 无法满足设定的“采用线性模型”条件 “规划求解”在目标或约束条件单元格中发现错误值 内存不足。Microsoft Excel无法获得规划求解所需内存

求解规划问题的结果3（报告） 运算结果报告

求解规划问题的结果3（报告） 灵敏度分析（敏感度分析） 极限报告 在“规划求解参数”对话框的“目标单元格”编辑框所指定的公式的微小变化，以及约束条件的微小变化对求解结果都会有一定影响。此报告提供关于求解结果对这些微小变化的灵敏度分析信息。含有整数约束的模型不能生成本报告。对于非线性模型，此报告提供缩减梯度和拉格朗日乘数；对于线性模型，此报告提供缩减成本、影子价格（机会成本）、目标函数（允许有小量增减量）以及右侧约束区域。 列出目标单元格和可变单元格以及他们的数值、上下界和目标值。含有整数约束的模型不能生成此报告。下限是在满足约束条件和保持其它可变单元格值不变的情况下，某个可变单元格可以取得的最小值。

MATLAB优化应用 线性规划问题求最优解函数

MATLAB优化应用 线性规划问题求最优解函数 x=linprog(f,A,b) x=linprog(f,A,b,Aeq,beq) x=linprog(f,A,b,Aeq,beq,lb,ub) x=linprog(f,A,b,Aeq,beq,lb,ub,x0) x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options) [x,fval]=linprog(…) [x, fval, exitflag]=linprog(…) [x, fval, exitflag, output]=linprog(…) [x, fval, exitflag, output, lambda]=linprog(…)

说明： x=linprog(f,A,b)返回值x为最优解向量。 x=linprog(f,A,b,Aeq,beq) 作有等式约束的问题。若没有不等式约束，则令A=[ ]、b=[ ] 。 x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options) 中lb ,ub为变量x的下界和上界，x0为初值点，options为指定优化参数进行最小化。