运筹学-绪论、线性规划引论-名校讲义课件.pptVIP

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