1.1线性规划问题

课 程 简 介
第三章：运输问题（4学时） 第四章：整数规划（4学时） 第五章：动态规划（3学时） 第六章：动态规划应用举例（7学时） 第七章：图与网络分析（7学时） 第八章：排队论（8学时）
第 一 章 单 纯 形 法 划 与 规 性 线
第一章 线性规划与单纯形法
线性规划是运筹学最重要的分支。自 1947年美国人丹捷格提出求解线性规划的 单纯形法以来，它在理论上已趋向成熟， 实际上的应用日益广泛与深入，现在几乎 各行各业都可以建立线性规划模型。比如 制定企业最佳经营计划、确定产品最优配 料比、寻找材料的最优下料方案、研究各 种资源的最优分配方案等等。由于线性规 划模型具有应用的广泛性，更主要由于它 的算法易于在计算机上实现，实际上， EXCEL的“规划求解”即可以用来求解一 般的线性规划问题。所以，线性规划已成 为现代管理科学的重要基础和手段之一。
图 解 法
2 2
图1-1
X2 60
图 1 1-1 1-1 1
4x1+2x2=120
Q3 Q2
50 40
30
20 10
2x1+3x2=100
Q1 10 20 30 40 50
O
x1
图 解 法
决策变量的一组取值称为线性规划问题 的一个解。满足约束条件的解称为可行解。 所有可行解的集合即称为可行域。使目标函 数达到最优的解称为最优解。 例1的可行域包含无穷多个可行解，为了 在无穷多个可行解中找到最优解，我们在坐 标系中画出目标函数表示的一族平行线。观 察这族平行线移动时对应的Z值变化,可以看 出，这族平行线愈向右上方移动，对应Z值愈 大。由于平行线族在Q2点脱离可行域，所以， 例1在Q2点取得最优解。 Q2是直线 2x1+3x2=100和4x1+2x2=120的交点，解此方程 组可得 :x1=20,x2=20.因为例1的解是：生产 Ⅰ型Ⅱ型计算机分别为20台，能得到最大利 润为200单位。
线 性 规 划 数 学 模 型
线性规划数学模型的一般形式如下： 目标函数：max(min)Z=c1x1+c2x2+‥‥+cnxn 约束条件:
a11x1+a12x2+‥‥+a1nxn≤（≥，＝）b1 a21x1+a22x2+‥‥+a2nxn≤（≥，＝）b2 …………………………………… am1x1+am2x2+‥‥+amnxn≤（≥，＝）bm x1,x2,‥‥,xn≥0
设司乘人员在各时间段一 开始时上班，并连续工作8小 时，问该公司线路至少应配备多少司乘人 员。列出该问题数学模型。 设x1,x2 ,…, x6为各班新上班人数，考虑到 在每个时间段工作的人数既包括该时间段 新上班的人又包括上一个时间段上班的人 员，按所需人员最少的要求可列出本例的 数学模型：
线 性 规 划 数 学 模 型
段内所需司机和乘务人员数如下： 班次 1 2 3 4 5 6 时间 6：00—10：00 10 00—14 00 10：00—14：00 14：00—18：00 18：00—22：00 22：00— 2：00 2：00— 6：00 所需人数 60 70 60 20 20 30
线 性 规 划 数 学 模 型
信息与计算科学专业
运筹与优化理论
讲授教师：向宇
课 程 简 介
运筹学是高等学校经济管理 类专业本科生所必修的一门专业 基础课；是分析和解决经营管理 领域最优化问题的一门方法论学 科；是每个有志于从事现代经营 管理工作的同志所应该掌握的重 要数量分析工具。
课 程 简 介
何谓“运筹学”？它的英文名称 是Operations Research,直译为“作业研 究”，就是研究在经营管理活动中如 何行动，如何以尽可能小的代价，获 取尽可能好的结果，即所谓“最优化” 问题。汉语是世界上最丰富的语言， 中国学者把这门学科意译为“运筹 学”，就是取自古语“运筹于帷幄之 中，决胜于千里之外”，其意为运算 筹划，出谋献策，以最佳策略取胜。 这就极为恰当地概括了这门学科的精 髓。
课 程 简 介
在人类历史的长河中，运筹谋划的 思想俯拾皆是，精典的运筹谋划案例也 不鲜见。像“孙子兵法”就是我国古代 战争谋略之集大成者；像诸葛亮更是家 喻户晓的一代军事运筹大师。然而，把 “运筹学”真正当成一门科学来研究， 则还只是近几十年来的事。第二次世界 大战中，英美等国抽调各方面的专家参 与各种战略战术的优化研究工作，获得 了显著的成功，大大推进了胜利的进程。 战后，从事这些活动的许多专家转到了 民用部门，使运筹学很快推广到了工业 企业和政府工作的各个方面，从而促进 了运筹学有关理论和方法的研究和实践， 使得运筹学迅速发展并逐步成熟起来。
1.2 图解法
如何求解线性规划模型是本章讨论的中 心问题。首先介绍只有两个决策变量的线性 规划的图解法，该方法能够对线性规划的解 法从几何直观上给我们以启迪。 对于两个决策变量的每一组取值，都可 以看作平面直角坐标系中一个点的坐标，因 此，我们可以把满足约束条件的点在平面直 角坐标系中表示出来。以例1的模型为例，约 束条件2x1+3x2≤100，4x1+2x2≤120都代表由一 条直线划定的半个平面，考虑到x1,x2≥0，所 以，满足所有约束条件的点应为坐落在第一 象限的区域OQ1Q2Q3（如图），该区域称为可 行域。
课 程 简 介
运筹学发展到现在，虽然只 有五十多年的历史，但其内容已 相当丰富，所涉及的领域也十分 广泛。以《运筹学国际文摘》收 集的各国运筹学论文的内容为例， 按技术分类就有50多种。现在这 门新兴学科的应用已深入到国民 经济的各个领域，成为促进国民 经济多快好省，健康协调发展的 有效方法。
课 程 简 介
线 性 规 划 数 学 模 型
建立该问题的数学模型
设x1,x2分别表示计划期内产品Ⅰ，Ⅱ 的产量。因为计划期内生产用的原料和工 时都是有限的，所以在确定产品Ⅰ，Ⅱ的 产量时要满足下面约束条件： 2x1+3x2≤100 4x1+2x2≤120 x1,x2≥0 一般满足上述约束方程组的解不是唯 一的，根据题意我们需要的是既满足约束 条件，又使得所获利润最大的方案。
1 1 线 性 规 划 问 题
§1 线性规划问题
1.1 线性规划问题的数学模型
线性规划是研究在一组线性不等式或等式 约束下使得某一线性目标函数取最大（或最 小）的极值问题。下面我们通过几个例子来 介绍线性规划问题的数学模型。
例1.某工厂生产Ⅰ，Ⅱ两种型号计算机，为了生产 一台Ⅰ型和Ⅱ型计算机，所需要原料分别为2和3个单 位，需要的工时分别为4和2个单位。在计划期内可以 使用的原料为100个单位，工时为120个单位。已知生 产每台Ⅰ，Ⅱ型计算机可获得利润分别为6和4个单位， 试确定获利最大的生产方案。
我们讲授这门课程的目的就是要使同 学们系统地了解运筹学的基本概念、基本 原理、研究方法及其应用，掌握运筹学整 体优化的思想和定量分析的优化技术，并 能正确应用各类模型分析和解决实际问题。 这门课程共讲授48学时，根据这些学 时，我们安排了如下一些内容： 第一章：线性规划与单纯形法 （8学时） 第二章：线性规划的对偶理论与灵敏 度分析 （7学时）
线 性 规 划 数 学 模 型
若以Z表示总利润，我们的目标是 maxZ=6x1+4x2 综合上述，该问题可用数学模型 表示为： 目标函数： maxZ=6x1+4x2 约束条件： 2x1+3x2≤100 4x1+2x2≤120 x1,x2≥0
线 性 规 划 数 学 模 型
例2 某昼夜服务的公交线路每天各时间区
目标函数： 约束条件： minZ=x1+x2+x3+x4+x5+x6 x1+x6≥60 x1+x2≥70 x2+x3≥60 x3+x4≥20 x4+x5≥20 x5+x6≥30 x1,x2,…,x6≥0
线 性 规 划 数 学 模 型
上面两例优化模型，都具有下述特征： (1)每个问题都用一组未知变量 x1,…,xn表示所求方案，通常这些变量都 是非负的，称为决策变量。 (2)存在一组约束条件，这些约束条 件都可以用一组线性等式或不等式表示。 (3)都有一个要求的目标，并且这个 目标可表示为一组决策变量的线性函数， 称为目标函数。目标函数可以是求最大， 也可以是求最小。 具有上述特征的数学模型就称为线性 规划模型。
2 ）具有两个变量的线性规划问题的可行 域是凸多边形。 （2）若线性规划存在最优解，它一定在可 行域的某个顶点得到。 虽然图解法只能求解包含2个变量的问 题，作为算法，没有太大价值，但是上述 结论却非常有意义。它将搜索最优解的范 围从可行域的无穷多个点缩小到有限几个 顶点。这就开启了人们的思路。而后面我 们要介绍的求解多维线性规划的单纯形法 就是在此结论的基础上推广得到的。