第二章线性规划模型

第二章 线性规划模型线性规划是数学规划中研究较早 , 发展较快 , 应用广泛的的一个重要分支 , 也是数学模型中的一项重要内容 . 它在生产安排、物质运输、投资决策、交通运输等现代工农业和经济安排、物质运输、投资决策、交通运输等现代工农业和经济管理等方面都有着广泛的应用 . 我们知道 , 在经济活动中提高经济效益一般可通过两个途径 : 第一是加强技术方面的改造以降低生产过程中对资源的消耗从而降低制造成本 ; 第二是提高企业的管理 , 即合理安排人力及物力，以降低企业的管理成本 .线性规划最早由前苏联数学家康托罗维奇首先提出 , 1947年美国数学家丹齐克提出了解决线性规划的普遍算法 单纯形方法； 1947年美国数学家冯 . 诺依曼提出了对偶理论并开创了线性规划的许多新领域 ; 线性规划的研究成果推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究 .一 、线性规划模型一、模型的建立我们从下面几个例子引出线性规划的模型 .问题一某车间为其它部门生产 200套钢管三脚架 , 每套由长度为2.9、 2.1、 1.5米的钢管各一根组成 . 已知原料钢管的长度为7.4米 , 如何确定钢管的切割方案 , 能使钢管的利用率最高. 分析 首先对长度为 7.4米的钢管要确定合适的切割方案 , 并使得每次切割后丢弃的原料尽可能少 . 为此建立所有可能的切割方案 :1.440080.831070.222061.10305030140.911130.302120.11021余料1.52.12.9编号以 表示在第 种方案下所使用的原料数 , 则一个合适的切割方案表现为而衡量方案好坏的评价指标为在该方案下所丢弃的余料数 , 即反映为余料函数由此得到该问题的数学表达式 :问题二 投资决策问题某基金公司为扩展业务需要招聘部分基金经理 . 在业务考试中 , 考官提出了这样一个问题 .为公司制定一个五年期的投资计划 . 项目可供选择：现已知有四个投资项目 A: 于每年的年初可进行投资 , 并于次年末完成 , 投资收益为 6% ；项目 B: 于第三年的年初进行投资 , 并于第五年的年末完成投资 , 投资收益为 16.5%, 投资额不超过 35万；项目 C: 于第二年的年初进行投资 , 并于第五年的年末完成成投资 , 投资收益为 21.5%, 投资额不超过 40万； 项目 D: 于每年的年初可进行投资 , 并于当年末完成 , 投资收益为 2.35%.该公司现有资金 120万 , 试为该公司制定投资计划 . 模型建立以 代表年份 , 分别表示 4个项目 , 表示在第 年对项目 的投资额 . 显然 , 每年的资金必须全部用于某些项目的投资 . 由条件所设知每年可行的投资计划为第一年第二年第三年第四年第五年投资收益函数为由此得到该问题的数学模型问题三 运输问题产地的产量分别为 对该类物资 , 有 个需并设求点 , 分别记为 需求量为又从产地 到需求点 的单位运输成本为 求相应的运输方案 .设有一种物资 , 它有 个产地 , 记为模型建立设 表示从产地 到需求点 的运输量 , 则合适的运输方案表现为对产量的要求对需求量的要求而相应的目标函数为由此得到相应的数学模型为思考一般情况下 , 产销是不平衡的 , 此时相应的模型将如何?在上面例中 , 目标函数及约束条件均为线性表达式 , 故把这样的模型称为 线性规划模型 .定义 如下的一组数学关系式即称为一个 线性规划 或 线性规划模型求解线性规划的传统解法是单纯形法 . 但单纯形方法针 对的是线性规划的标准型 , 为此引入标准型（典式）的概念 .定义 具有如下形式的线性规划为线性规划的 标准型 :对于非标准形式的线性规划都可以经过适当的转换而化化为相应的标准型 .二、线性规划的解法1.解的概念设线性规划定义 设 是 维实向量 , 若 满足 ,则称 是线性规划的一个 解 ; 若解 满足 , 则称其为规划的 可行解 ; 可行解的全体称为 可