优化问题与规划模型-read.pdfVIP

优化问题与规划模型 优化问题分类：（非）线性规划、整数规划、0-1 规划、（多）目标规划、（与时间有关 的）动态规划、（系数是随机变量的）随机规划。 6.0 多变量优化 一个城郊的社区计划更新消防站。原来的消防站在旧城中心。规划要将新的消防站设置 得更科学合理。在前一个季度收集了消防队对火警反应时间的资料：平均要用3.2分钟派遣 消防队员；消防队员到达火灾现场的时间（行车时间）依赖于火灾现场的距离。行车时间的 资料列于表1 Distance （miles ）：距离（英里） Drive Time （minutes ）：行车时间（分） 表1 关于设备位置问题的反应时间资料 从消防官员处得到的从城区的不同区域打来的求救电话频率的数据列于图1。其中每一格代 表一平方英里，格内的数字为每年从此区域打来的紧急求救电话的数量。 1）求反应时间。 消防队对离救火站 r 英里处打来的一个求救电话需要的反应时间估计为 d 分钟。 2 ）求平均反应时间。 设城区位区域[0,6]´[0,6] 内，(x,y)是新的消防站的位置。根据求救电话频率，确定消防队对 求救电话的平均反应时间 z=f(x,y) 3 ）求新的消防站的最佳位置。 即确定函数 f(x,y)的极小值点。首先， 用随机有哪些信誉好的足球投注网站算法：在可行域[0,6]´[0,6]内简单地选取n 个随机的的点，计算目标函数在这些点的值，选择其中最小的点即可。然后，可采用 Matlab 求最值点程序求出精确的最小值点: 求函数 fun 在 x0 点附近的最小值点 [x ，f] = fminsearch(fun, x0) 6.1 线性规划 1939年苏联数学家康托洛维奇发表《生产组织与计划中的数学问题》 1947年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论. 1. 问题 例 1 作物种植安排 一个农场有 50 亩土地, 20 个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每 亩地分别需要劳动力 1/2 1/3 1/4, 预计每亩产值分别为 110 元, 75 元, 60 元. 如何规划 经营使经济效益最大. 分析：以取得最高的产值的方式达到收益最大的目标. 1. 求什么？分别安排多少亩地种蔬菜、棉花、水稻？ x 亩、 x 亩、 x 亩 1 2 3 2. 优化什么？ 产值最大 max f=10x +75x +60x 1 2 3 3. 限制条件？ 田地总量 x +x +x  50 劳力总数 1/2x +1/3x +1/4x  20 1 2 3 1 2 3 模型 I : 设决策变量：种植蔬菜 x 1 亩, 棉花 x2 亩, 水稻 x3 亩， 求目标函数 f=110x +75x +60x 1 2 3 在约束条件x +x +x  50 1/2x +1/3x +1/4x 20 下的最大值 1 2 3 1 2 3 规划问题：求目标函数在约束条件下的最值, 规划问题包含 3 个组成要素: 决策变量、目标函数、约束条件。 当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题, 否则称为非线性 规划问题。 2. 线性规划问题求解方法 称满足约束条件的向量为可行解,称可行解的集合为可行域, 称使目标函数达最值的可行解为最优解. 命题 1 线性规划问题的可行解集是凸集. 因为可行解集由线性不等式组的解构成。两个变量的线性规划问题的可行解集是平面上的凸 多边形。 命题 2 线性规划问题的最优解一定在可行解集的某个极点上达到. 图解法： 解两个变量的线性规划问题，在平面上画出可行域，计算目标函数在各极点处的 值，经比较后，取最值点为最优解。 命题 3 当两个变量的线性规划问题的目标函数取不同的目标值时，构成一