线性规划模型上.pptVIP

线性规划模型的基本结构 1.决策变量 ——未知数。它是通过模型计算来确定的决策因素。又分为实际变量——求解的变量和计算变量，计算变量又分松弛变量（上限）和人工变量（下限）。 2.目标函数——经济目标的数学表达式。目标函数是求变量的线性函数的极大值和极小值这样一个极值问题。 3.约束条件——实现经济目标的制约因素。它包括：生产资源的限制（客观约束条件）、生产数量、质量要求的限制（主观约束条件）、特定技术要求和非负限制。 线性规划模型的基本假设 1.线性 目标函数和约束条件 2.可分性 活动对资源的可分性 3.可加性 活动所耗资源的可加性，资源总需要量为多种活动所需资源数量的总和。 4.明确性 目标的明确性 5.单一性 期望值的单一性 6.独立性 变量是独立的表示各种作业对资源都是互竟关系，没有互助关系 7.非负性 例7 有 n 个物品，编号为 1, 2, …, n，第 i 件物品 例8 有n 项任务，由 n 个人来完成，每个人只能 技术经济研究中运用线性规划方法的特点及局限性 特点： 1.可以使研究对象具体化、数量化。可以对所研究的技术经济问题做出明确的结论； 2.线性 3.允许出现生产要素的剩余量 4.有一套完整的运算程序 重 ai 千克，价值为 ci 元，现有一个载重量不超过 大，应如何装载这些物品？ a 千克的背包，为了使装入背包的物品总价值最 用变量 xi 表示物品 i 是否装包，i =1, 2, …, n， 并令： 解 可得到背包问题的规划模型为： 做一件， 第 i 个人完成第 j 项任务要 cij 小时，如 何合理安排时间才能使总用时最小？ 引入状态变量 xij ，并令： 解 则总用时表达式为： 可得到指派问题的规划模型为： 上面介绍的指派问题称为指派问题的标准形 式，还有许多其它的诸如人数与任务数不等、及 但一般可以通过一些转化，将其变为标准形式. 某人可以完成多个任务，某人不可以完成任务， 某任务必须由某人完成等特殊要求的指派问题. 对于标准形式的指派问题，我们可以利用匈 牙利算法实现求解. 它将指派问题中的系数构成 一个矩阵，利用矩阵上简单的行和列变换，结合 解的判定条件，实现求解. 局限性： 1. 线性规划它是以价格不变和技术不变为前提条件的，不能处理涉及到时间因素的问题。因此，线性规划只能以短期计划为基础。 2.在生产活动中，投入产出的关系不完全是线性关系，由于在一定的技术条件下，报酬递减规律起作用，所以要满足线性假定是不可能的。在线性规划解题中，常常把投入产出的非线性关系转化为线性关系来处理，以满足线性的假定性，客观上产生误差。 3.线性规划本身只是一组方程式，并不提供经济概念，它不能代替人们对现实经济问题的判断。 技术经济研究中运用线性规划方法的特点及局限性 * * 第3章 线性规划模型(上) 在工程技术、经济管理、科学研究和日常生活等诸多领域中，人们经常遇到这样一类决策问题：在一系列客观或主观限制条件下，寻求所关注的某个或多个指标达到最大(或最小)的决策。 例如，生产计划要按照产品工艺流程和顾客需求，制定原料、零件、部件等订购、投产的日程和数量，尽量降低成本使利润最高；运输方案要在满足物资需求和装载条件下安排从各供应点到各需求点的运量和路线，使运输总费用最低。 这一类问题的特点就是：在若干可能的方案中寻求某种意义下的最优方案。数学上称为最优化问题，而研究处理这种问题的方法叫最优化的方法。优化模型是一种特殊的数学模型，优化建模方法是一种特殊的数学建模方法。 常见的线性规划问题：①运输问题；②合理下料问题；③生产的组织与计划问题； ④配料问题；⑤分派问题；⑥布局问题。 优化模型一般有下面三个要素： 1．决策变量，它通常是该问题要求解的那些未知量； 2．目标函数，通常是该问题要优化(最大或最小)的那个目标的数学表达式，它是决策变量的函数。 3．约束条件，由该问题对决策变量的限制条件给出。 优化模型从数学上可表示成如下一般形式： 其中“s. t.”表示“subject to” ，意思是“受约束于”，如果f(x), h(x), g(x)均为线性函数，则上述模型称为线性规划(Linear Programming，简记为LP)，否则称为非线性规划(NLP) 3.1 线性规划(目标函数和约束条件都是线性函数) 一、几个相关概念 一个线性规划问题有解：指能找出一组 满足约束条件，并称这组xj为问题的可行解。 可行域：指全部可行解组成的集合。 最优解：指可行域中使目标函数值达到最优的可行解。 线性规