《运筹学-绪论、线性规划引论(名校讲义)》由会员分享，可在线阅读，更多相关《运筹学-绪论、线性规划引论(名校讲义)（14页珍藏版）》请在金锄头文库上搜索。
1、第一讲第一讲 绪论、线性规划引论绪论、线性规划引论1 绪论o运筹学简述 o运筹学的主要内容 o本课程教材和参考书o本课程特点和要求o本课程授课方式与考核 2 线性规划引论o线性规划概述 o从实际问题中提炼数学模型举例1.1 1.1 运筹学简述（运筹学简述（1 1） o运筹学（Operations Research）是系统工程的最重要的理论 基础之一，在美国有人把运筹学称之为管理科学 (Management Science)。运筹学所研究的问题，可简单地归 结为一句话：“依照给定条件和目标，从众多方案中选择最 佳方案”，故有人称之为最优化技术。 o1938年英国最早出现了军事运筹学，命名为“Op
2、erational Research”,1942年，美国从事这方面工作的科学家命其名为 “Operations Research”这个名字一直延用至今。o美国运筹学的早期著名工作之一是研究深水炸弹起爆深度问 题。当飞机发现潜艇后，飞机何时投掷炸弹及炸弹的引爆引 度是多少？运筹学工作者对大量统计数字进行认真分析后， 提出如下决策：1.仅当潜艇浮出水面或刚下沉时，方投掷深 水炸弹。2炸弹的起爆深度为离水面25英尺（这是当时深水 炸弹所容许的最浅起爆点）。空军采用上述决策后，所击沉 潜艇成倍增加，从而为运筹学增添了荣誉。1.1 1.1 运筹学简述运筹学简述 （2 2）o也许有人怀疑，运筹学是研究从众
3、多方案（甚至无限多个方 案）中选佳的优化技术，那么在当代计算机技术迅速发展的 今天，这种优化技术是否会丧失其重要性？事实正相反，新 型计算机的出现，恰为运筹学的应用开辟了新天地。 o假设有70艘油轮向70个港口运货，已知每艘油轮驶向每个港 口的费用，油轮公司需制订出最优运输方案。采用全枚举法 （穷举法）需计算方案数为70!(大于10100 ）；IBM公司当 时生产的大计算机1秒种大约可算出109（即10亿）个方案。 若要逐个算出全部方案，则需调用占有空间为1050个地球一 样大的IBM公司生产的众多大计算机同时计算几百亿年以上 。而在这种大机器上用线性规划的单纯形法计算只需几秒钟 （这是整数规
4、划问题）。 o可见，将运筹学与计算机科学及其它科学结合应用，将会产 生更好的效果。 1.2 1.2 运筹学的主要内容运筹学的主要内容 o运筹学发展到今天，内容已相当丰富，分支也很 多。对其内容的分类方法不尽相同，主要是根据 解决的问题特点以及技术本身特点来分类。根据 解决问题的主要特征可分两大类：确定型和概率 型。其中确定型包含：线性规划，整数规划，动 态规划，非线性规划，多目标决策及确定性存贮 等；概率型中包含：回归分析，决策论，对策论 ，排队论，马尔可夫链，图论与网络，概率存贮 及搜索技术等。o本书将阐述运筹学中最基本的部分规划论（ 即线性规划，整数规划，动态规划及非线性规划 ）及网络（即
5、图论与网络）。 1.3 1.3 本课程教材和参考书本课程教材和参考书 o先修课：高等数学，线性代数o教材：运筹学规划论及网络，王永县 编著o参考书：教材后面的参考文献（共16本）1.4 1.4 本课程特点及要求本课程特点及要求 o目的：不仅掌握优化理论方法的专业知识 ，更重要的是提高分析问题和解决问题的 能力。o方法：强调思路、观点及弄清物理概念， 掌握一定的理论推导能力，但不搞纯数学 公式。 o避免2种倾向：只罗列方法，不讲本质； 或只追求数学推导，掩盖物理概念。 o内容为2部分：基本技术和开阔思路。2.1 2.1 线性规划概述（线性规划概述（1 1）o线性规划的广泛应用是计算机时代的产物。
6、o1902年，Julius Farkas 发表论文，阐述有关线性 规划问题。o1938年，英国人康德进行较详细研究。o1947年，美国学者George Dantzig（丹茨格）发明 了求解线性规划的单纯形法（1951年发表），从 而为线性规划的推广奠定了基础。有人认为，求 解线性规划的单纯形算法可与求解线性方程组的 高斯消元法相媲美。2.1 2.1 线性规划概述（线性规划概述（2 2）o线性规划的数学模型有三要素，从实际问题提炼 成数学模型时，首先寻找需求解的未知量xj (j=1,n)，然后列举三要素： 1.列写与自变量（未知量）有关的若干个线性 约束条件（等式或不等式）。2.列写自变量xj取
7、值限制（xj0，xj0或不限） 。3.列写关于自变量的线性目标函数值（极大值或 极小值）。o其中，前两条称为可行条件，最后一条称为优化 条件。符合这三个条件的数学模型通常称为线性 规划的一般型（general）。 2.2 2.2 从实际问题中提炼数学模从实际问题中提炼数学模 型举例型举例 （1 1）例1-1饮食问题o每人每天食用的食品中含有各种必需的营养素， 家庭主妇面临着一种抉择：如何采购食品，才能 在保证必需营养素最低需求量前提下花钱最少？o这是典型的线性规划问题。 设有n种食品供选择，m种营养素应保证一定量。令 ： xj每天食用的j种食品数量 cj单位j种食品的价格 aij单位j种食品含
8、有 i种营养素数量 bi每天对营养i的最低需求量2.2 2.2 从实际问题中提炼数学模从实际问题中提炼数学模 型举例型举例（2 2） 针对问题特点，可列写线性规划数学模型如下：（最低营养需求约束）（自变量约束，食品量不会为负）（目标函数，使购食品费用取最小值） （i=1,2,m; j=1,2,n） 2.2 2.2 从实际问题中提炼数学模从实际问题中提炼数学模 型举例型举例 （3 3）例1-2 Chebyslev近似 给出一组方程 o其中，mn，希求一组近似解x1，x2, xn使误差 尽量小。即求出一组解，使之代入方程组中，造 成不满足约束的方程的最大误差量尽量小。这是 长期以来被认为必存在的这
9、样一个解而又很难找 到解的问题，然而用线性规划求解却比较方便。 下面就讨论如何建立该问题的线性规划数学模型 。 设：2.2 2.2 从实际问题中提炼数学模从实际问题中提炼数学模 型举例型举例 （4 4）o则问题变为求出一组xj(j=1,2,n)使尽量小，于 是变为：即：且令min为统一标志，令 x0，则上述问题变为下述线 形规划问题 ：2.2 2.2 从实际问题中提炼数学模从实际问题中提炼数学模 型举例型举例（5 5） 自变量约束：x00，xj不限（j=1,2,n） 目标函数：x0min2.2 2.2 从实际问题中提炼数学模从实际问题中提炼数学模 型举例型举例 （6 6）o从上面例子中看出，列写线性规划数学模型的关 键步聚为：根据问题性质，找出需求解的变量，即自变量。根据问题的限制因素或条件，列出自变量的取值 限制及与自变量有关的线性约束条件（等式约束 或不等式约束）。根据问题的目标要求，列出自变量有关的线性目 标函数（极大值或极小值）。
