运筹学线性规划试题及答案

第一章 线性规划(Linear Programming )1 2 3 4 5 线性规划问题及数学模型 单纯形法的原理 单纯型法的步骤 LP问题的进一步讨论 应用举例1

第一节

线性规划问题及数学模型

Linear Programming , LP

1939年 1941年 1947年 1979年 1984年

苏 康托洛维奇 美 Hichook 丹捷格(G. B. Dantzig) 苏 哈奇安算法 Karmarkar算法

单纯形法

LP是数学规划的一个重要分支，数学规划着重解决资源 的优化配置，一般可以表达成以下两个问题中的一个： (1)当资源给定时，要求完成的任务最多； (2)当任务给定时，要求为完成任务所消耗的资源最 少。 若上述问题的目标﹑约束都能表达成变量的线性关系， 则这类优化问题称LP问题。 LP是一种解决在线性约束条件下追求最大或最小的线性 目标函数的方法。

一、实例例1 生产计划问题 (书P8,典型示例)产品 设 备 原料A 原料B 利润 I 1 4 0 2 II 2 0 4 3 资源限量 8台时 16公斤 12公斤

Step 1:明确问题，设定决策变量 设I、II两种产品的产量分别为x1, x2 Step 2: 确定约束条件

。

工时约束：

投资组合某人有一笔50万元的资金可用于长期 投资,可供选择的投资机会包括购买国库券 、公司债券、投资房地产、购买股票或银 行保值储蓄等。不同的投资方式的具体参 数如下表。投资者希望投资组合的平均年 限不超过5年，平均的期望收益率不低于 13%,风险系数不超过4,收益的增长潜 力不低于10%。问在满足上述要求的前提 下投资者该如何选择投资组合使平均年收 益率最高？

序 投资方式 投 资 期 年收益 风 险 增长潜 号 限(年)率% 系数 力% 1 国库券 3 10 6 2 1 5 0 11 15 25 20 10 12 3 1 3 8 6 1 2 0 0 15 30 20 5 10 0

2 公司债券 3 房地产 4 股票 5 短期存款 6 长期储蓄 7 现金存款

解：设xi为第I种投资方式在总投资额中的比例， 则模型如下： Max S= 11x1+15x2 +25x3 +20x4+10x5 +12x6+3x7 s.t. 3x1+10x2 + 6x3+ 2x4+ x5+ 5x6 5 11x1+15x2+25x3+20x4+10x5+12x6+3x7 13 x1+ 3x2 + 8x3 + 6x4+ x5+ 2x6 4 15x2 +30x3 +

运筹学

第1章 线性规划 章

实用运筹学 运用Excel Excel建模和求解 -运用Excel建模和求解 第1章 线性规划 Linear ProgrammingRUC, Information School, Ye Xiang

运筹学

第1章 线性规划 章

本章内容要点线性规划问题及其数学模型； 线性规划问题及其数学模型； 线性规划问题的电子表格建模； 线性规划问题的电子表格建模； 线性规划问题的多解分析。 线性规划问题的多解分析。

RUC, Information School, Ye Xiang

运筹学

本章内容1.1 线性规划问题及其数学模型 1.2 线性规划问题的图解法

第1章 线性规划 章

1.3 用Excel 规划求解”工具求解线性规划问 Excel“规划求解 规划求解” 题 1.4 线性规划问题求解的几种可能结果

RUC, Information School, Ye Xiang

运筹学

第1章 线性规划 章

线性规划是运筹学中研究较早， 线性规划是运筹学中研究较早，理论和 算法比较成熟的重要分支之一。 算法比较成熟的重要分支之一。 它主要研究在线性等式(或不等式)的 它主要研究在线性等式(或不等式) 限制条件下， 限制条件下，使某一线性目标函数取得 最

运筹学

第1章 线性规划 章

实用运筹学 运用Excel Excel建模和求解 -运用Excel建模和求解 第1章 线性规划 Linear ProgrammingRUC, Information School, Ye Xiang

运筹学

第1章 线性规划 章

本章内容要点线性规划问题及其数学模型； 线性规划问题及其数学模型； 线性规划问题的电子表格建模； 线性规划问题的电子表格建模； 线性规划问题的多解分析。 线性规划问题的多解分析。

RUC, Information School, Ye Xiang

运筹学

本章内容1.1 线性规划问题及其数学模型 1.2 线性规划问题的图解法

第1章 线性规划 章

1.3 用Excel 规划求解”工具求解线性规划问 Excel“规划求解 规划求解” 题 1.4 线性规划问题求解的几种可能结果

RUC, Information School, Ye Xiang

运筹学

第1章 线性规划 章

线性规划是运筹学中研究较早， 线性规划是运筹学中研究较早，理论和 算法比较成熟的重要分支之一。 算法比较成熟的重要分支之一。 它主要研究在线性等式(或不等式)的 它主要研究在线性等式(或不等式) 限制条件下， 限制条件下，使某一线性目标函数取得 最

《管理运筹学》实验报告

实验日期： 2016年 04月 21日 —— 2016 年 05 月 18 日 班级 2014级04班 姓名 杨艺玲 学号 实验 管理运筹学问题的计算机求解 名称 实验目的： 2014190456 通过实验学生应该熟练掌握“管理运筹学3.0”软件的使用，并能利用“管理运筹学3.0”对具体问题进行问题处理，且能对软件处理结果进行解释和说明。 实验所用软件及版本： 管理运筹学3.0 实验过程：（含基本步骤及异常情况记录等) 一、实验步骤（以P31页 习题1 为例） 1.打开软件“管理运筹学3.0” 2.在主菜单中选择线性规划模型，屏幕中会出现线性规划页面

3.在点击“新建”按钮以后，按软件的要求输入目标函数个数和约束条件个数，输入目标函数级约束条件的歌变量的系数和b值，并选择好“≤” 、“≥”或“＝”，如图二所示，最后点击解决

1

4.注意事项： （1） 输入的系数可以是整数、小数，但不能是分数，要把分数化为小数再输入。 （2） 输入前要合并同类项。 当约束条件输入完毕后，请点击“解决”按钮，屏幕上讲显现线性规划问题的结果，如图所示

2

5.输出结果如下

5.课后习题： 一、P31习题1

第一章

线性规划及单纯形法

绪论

本章主要内容

?线性规划概述

?一般线性规划问题的数学模型?线性规划问题的图解法

?线性规划的基本定理?单纯形法

?用计算机软件求解线性规划问题?线性规划的应用举例

2

线性规划

【开篇案例】

时间

所需导游人数

一、人力资源分配的问题

某旅行社为了迎接旅游黄金周的到来，对一日游导游人员的需求经过统计分析如表所示。为了保证导游充分休息，导游每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排导游人员的作息，既满足工作需要，又使配备的导游人数最少？

星期日星期一星期二星期三星期四星期五星期六

40343235284642

3

线性规划

【开篇案例】

二、生产计划的问题

明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如右表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？

甲563352323乙1042561218丙7824--3216资源限制80001200010000铸造工时(小时/件)机加工工时(小时/件)装配工时(小时/件)自产铸件成本(元/件)外协铸件成本

实验二 应用LINGO、MATLAB软件求解非线性规划

一.实验目的

1. 对实际问题进行数学建模，并学会用数学软件Matlab或运筹软件Lindo/Lingo对问题进行求解；

2. 学会建立M文件，并学会用Matlab的软件包内部函数求解非线性规划问题。

二.实验内容

1.写出下属问题的数学模型（LINGO）

将机床用来加工产品A，6小时可加工100箱。若用机床加工产品B，5小时可加工100箱。设产品A和产品B每箱占用生产场地分别是10和20个体积单位，而生产场地（包括仓库）允许15000个体积单位的存储量。机床每周加工时数不超过60小时。产品A生产x1（百箱）的收益为（60-5x1）x1元，产品B生产x2（百箱）的收益为（80-4x2）x2元，又由于收购部门的限制，产品A的生产量每周不能超过800箱，试制定周生产计划，使机床生产获最大收益。

2.用数学软件求解下列问题:(MATLAB) （1） minf??x1?2x2?x12?x22

minf??x1?2x2?s..t2x12?3x2?61212x1?x2221212（2）

x1?4x2?5x1,x2?0x1?3,x2?6

三. 模型建立

1、设生产A产品为x1百箱，生产B产品为x2

实验二 应用LINGO、MATLAB软件求解非线性规划

一.实验目的

1. 对实际问题进行数学建模，并学会用数学软件Matlab或运筹软件Lindo/Lingo对问题进行求解；

2. 学会建立M文件，并学会用Matlab的软件包内部函数求解非线性规划问题。

二.实验内容

1.写出下属问题的数学模型（LINGO）

将机床用来加工产品A，6小时可加工100箱。若用机床加工产品B，5小时可加工100箱。设产品A和产品B每箱占用生产场地分别是10和20个体积单位，而生产场地（包括仓库）允许15000个体积单位的存储量。机床每周加工时数不超过60小时。产品A生产x1（百箱）的收益为（60-5x1）x1元，产品B生产x2（百箱）的收益为（80-4x2）x2元，又由于收购部门的限制，产品A的生产量每周不能超过800箱，试制定周生产计划，使机床生产获最大收益。

2.用数学软件求解下列问题:(MATLAB) （1） minf??x1?2x2?x12?x22

minf??x1?2x2?s..t2x12?3x2?61212x1?x2221212（2）

x1?4x2?5x1,x2?0x1?3,x2?6

三. 模型建立

1、设生产A产品为x1百箱，生产B产品为x2

第三章 特殊的线性规划问题

第一节 运 输 问 题

人员、物资的流动在社会生产实践中是极其频繁且普遍的. 我们经常需要把某些货物从一些地方运送到另一些地方，在制定运输方案时，考虑最多的是运输费用是否最低？例如：要从甲、乙两地向A、B运送100t药材，每吨运费（单位：百元）及供需情况见表3-1：

表3-1 药材供应、需求量和单位运价表

单 位 运 供 应 费 点 需 求 点 A城 B城 供应量（t） 甲地 乙地 需求量(t) 1 5 30 2 10 70 40 60 通常人们总是将单位运费最低的优先安排，其次考虑运费次低的线路. 这样从甲地运30t到A城，运10t到B城；从乙地运60t到B城，该方案的总费用为: 30×1+10×2+60×10=650（百元）.

值得注意的是，我们虽然每次都优先考虑运费最小的线路，但最终方案的总费用未必最少. 如上面问题可安排从甲地运40t给A城，乙地分别运30t给A、B两城，从而总费用为: 40×2+30×5+30×10=530（百元）．

出现这种现象主要是因为局部最优不等于全局最优，或者说局部最优的简单相加不等于全局最优，所以我们有必要研究运输问题. 事实上它属于线性规划问题的范畴，但由于

运筹学 线性规划 单纯形法

第一章 线性规划问题及单纯形法线性规划问题及其数学模型 图解法 单纯形法原理 单纯形法计算步骤 单纯形法的进一步讨论

运筹学 线性规划 单纯形法

第五节

单纯形法的进一步讨论

本节重点: 本节重点:● 大 M法 ●两阶段法 ●解的存在情况判别

运筹学 线性规划 单纯形法

一, 人工变量的引入及其解法当约束条件为" 1. 当约束条件为"≥"型,引入剩余变量和人工变 量 由于所添加的剩余变量的技术系数为 由于所添加的剩余变量的技术系数为1,不能作 为初始可行基变量,为此引入一个人为的变量(注意, 为初始可行基变量,为此引入一个人为的变量(注意, 此时约束条件已为" ),以便取得初始基变量 以便取得初始基变量, 此时约束条件已为"="型),以便取得初始基变量, 故称为人工变量. 故称为人工变量. 人工变量 由于人工变量在原问题的解中是不能存在的, 由于人工变量在原问题的解中是不能存在的,应 尽快被迭代出去, 尽快被迭代出去,因此人工变量在目标函数中对应的 价值系数应具有惩罚性,称为罚系数 罚系数. 价值系数应具有惩罚性,称为罚系数.罚系数的取值 视解法而定 两种方法: 两种方法:大M法和二阶段法.