第二章线性规划答案

第3章 线性规划

授课时间： 授课地点：

一、线性规划的数学模型 讲解P29情景案例 涉及知识点： ? 数学模型的建立 ? 模型的计算机软件求解 ? 线性规划的一般模型

二、线性规划的应用（一）

1、某公司有60万元资金，计划投资甲、乙两个项目，按要求对项目甲的投资不小于对项目乙投资的

2倍，且对每个项目的投资不能低于5万元，对项目甲每投资1万元可获得0.43万元的利润，对项目乙每投资1万元可获得0.6万元的利润，该公司正确提财投资后，在两个项目上共可获得的最大利润为 B

A.36万元 B.31.2万元 C.30.4万元 D.24万元

2、某企业生产甲、乙两种产品。已知生产每吨甲产品要用A原料3吨、B原料2吨；生产每吨乙产品要用A原料1吨、B原料3吨。销售每吨甲产品可获得利润5万元、每吨乙产品可获得利润3万元。该企业在一个生产周期内消耗A原料不超过13吨，B原料不超过18吨，那么该企业可获得最大利润是

A 12万 B 20万 C 25万 D 27万

3、某加工厂用某原料由车间加工出A产品，由乙车间

运筹学Operations Research

Chapter 2 线性规划Linear Programming2.1 LP的数学模型 2.2 图解法 2.3 标准型 2.4 基本概念 2.5 单纯形法 Mathematical Model of LP

Graphical MethodStandard form of LP

Basic Concepts Simplex Method

2.1 数学模型Mathematical Model

2.1 线性规划的数学模型 Mathematical Model of LP

Chapter 2 线性规划 Linear Programming

案例分析 某企业在计划期内计划生产甲、乙、丙三种产品。 这些产品分别需要在设备 A、B上加工，需要消耗材料 C、D,按工艺资料规定，单件产品在不同设备上加工 及所需要的资源如表2.1所示。已知在计划期内设备的 加工能力各为200台时，可供材料分别为360、300公斤； 每生产一件甲、乙、丙三种产品，企业可获得利润分 别为 40 、 30 、 50 元，假定市场需求无限制。企业决策 者应如何安排生产计划，使企业在计划期内总的利润 收入最大？

2.1 线性规划的数学模型 Mathemati

第二章 线性表

一、选择题

1．线性表是具有n个__C___的有限序列（n>0）。

A．表元素 B．字符 C．数据元素 D．数据项 2．一个顺序表所占用的存储空间大小与___B___无关。 A．表的长度 C．元素的类型

B．元素的存放顺序

D．元素中各字段的类型

3．线性表的顺序存储结构是一种__A___。 A．随机存取的存储方式 C．索引存取的存储方式

B．顺序存取的存储方式 D．Hash存取的存储方式

4. 若线性表采用顺序存储结构，每个元素占用 4 个存储单元，第一个元素的存储地址为 100,则第 12 个元素的存储地址是__B____。 A．112 B.144 C.148 D.412 5. 线性表是__A____。

A．一个有限序列，可以为空 B．一个有限序列，不能为空 C．一个无限序列，可以为空 D．一个无限序列，不能为空

6．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为__C____。 A．O（n）O（n） B．O（n）O（1） C．O（1）O（n） D．O（1）O(1) 7．若长度为n的非空线性表采用顺序存储结构

第二章 线性表 一、选择题

1. 下面关于线性表的叙述错误的是（ ）。

A.线性表采用顺序存储必须占用一片连续的存储空间 B. 线性表采用链式存储不必占用一片连续的存储空间 C. 线性表采用链式存储便于插入和删除操作的实现 D. 线性表采用顺序存储便于插入和删除操作的实现 2. 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ ）。

A.q=p->next；p->data=q->data；p->next=q->next；free(q)； B. q=p->next；q->data=p->data；p->next=q->next；free(q)； C. q=p->next；p->next=q->next；free(q)； D. q=p->next；p->data=q->data；free(q)；

3. 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ ）。

A. O(n) B. O(nlog2n) C. O(1) D. O(n2)

4．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ ）。

第二章 线性表

一、选择题

1．线性表是具有n个__C___的有限序列（n>0）。

A．表元素 B．字符 C．数据元素 D．数据项 2．一个顺序表所占用的存储空间大小与___B___无关。 A．表的长度 C．元素的类型

B．元素的存放顺序

D．元素中各字段的类型

3．线性表的顺序存储结构是一种__A___。 A．随机存取的存储方式 C．索引存取的存储方式

B．顺序存取的存储方式 D．Hash存取的存储方式

4. 若线性表采用顺序存储结构，每个元素占用 4 个存储单元，第一个元素的存储地址为 100,则第 12 个元素的存储地址是__B____。 A．112 B.144 C.148 D.412 5. 线性表是__A____。

A．一个有限序列，可以为空 B．一个有限序列，不能为空 C．一个无限序列，可以为空 D．一个无限序列，不能为空

6．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为__C____。 A．O（n）O（n） B．O（n）O（1） C．O（1）O（n） D．O（1）O(1) 7．若长度为n的非空线性表采用顺序存储结构

（一）线性规划

案例分析1

例1.10 飞乐公司经营一个回收中心，专门从事用三种废弃原材料C、P、H混合调出三种不同规格的产品ABD。根据混合时候各种材料的比例，可将该产品分为不同的等级（参照表1.12）。尽管在混合各种等级产品时允许一定的机动性，但每一等级产品中各种材料的最大值和最小值必须符合下面质量标准的规定（最大值和最小值是根据该材料的重量在该等级产品总重量中的比例来确定的）。在两种较高等级的产品中，有一种特定材料的比例是固定的。已知产品的规格要求，产品单价，每天能供应的原材料数量及原材料单价，分别见表1.12和表1.13，问该厂应如何安排生产，使利润收入为最大？ 表1.12

产品名称 Ａ B D

规格要求 原材料C不少于５０％ 原材料Ｐ不多于２５％ 原材料C不少于２５％ 原材料P不多于５０％

不限

单价（元／kg）

50 35 25

回收中心可以从一些渠道定期收集到所需的固体废弃物，因此，可以获得维持稳定作业的处理量。表1.13给出了中心每天可以收集到每种材料的数量和原材料单价。

表1.13

原材料名称

C P H

每天最多供应量（kg）

100 100 60

单价（元／kg）

65 25 35

飞乐公司是绿地组织的全资公司，绿地组织

第二章 线性规划的对偶理论与灵敏度分析

例一美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设 备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、 各售出一件时的获利情况如下表所示。问该公司应制造Ⅰ、Ⅱ两种家电备多少 件.使获取的利润为最大。

设：

x1—— A产品的生产量 max z= 2 x1 + x2 5x2 ≤ 15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1,x2 ≥ 0

x2—— B产品的生产量

利润 约束 条件 st .

一、标准化 利润 max z= 2 x1 + x2 + 0x3 + 0x4 + 0x5 5x2 + x3 = 15 约束 6x1 + 2x2 + x4 = 24 st . 条件 x1 + x 2 + x5 = 5 x1,x2 ,x3 ,x4 ,x5 ≥ 0 二、写出初始单纯形表(必定存在有单位矩阵)C CCB 0 0 0 2 0 1 XB b b

22

11

00xx4 3 11 00 00 00

00xx5 4 0 5/4 1 1/4 0 -1/4

00x5 0 -15/2 0-1/2 1 3/2 θ

xx1 x2x2 x3 1 00 61 10 20 50 20 11 10

15

数学建模

第七章7.2

数学规划模型

7.1 奶制品的生产与销售自来水输送与货机装运

7.37.4 7.5

汽车生产与原油采购接力队选拔和选课策略 饮料厂的生产与检修

7.6 钢管和易拉罐下料y

数学建模

数学规划模型实际问题中 的优化模型 x~决策变量

Min(或Max) z f ( x), x ( x1 , x n ) s.t. g i ( x) 0, i 1,2, mf(x)~目标函数

T

gi(x) 0~约束条件 数 学 规 划 线性规划 非线性规划 整数规划

决策变量个数n和 多元函数 约束条件个数m较大 条件极值 最优解在可行域 的边界上取得

重点在模型的建立和结果的分析

数学建模

4.1 奶制品的生产与销售企业生产计划 空间层次

工厂级：根据外部需求和内部设备、人力、原料等 条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费 用参数等，以最小成本为目标制订生产批量计划。 时间层次 若短时间内外部需求和内部资源等不随时间变化，可 制订单阶段生产计划，否则应制订多阶段生产计划。 本节课题

数学建模

例1 加工奶制品的生产计划1桶 牛奶 或 12小时 8小时 3公斤A1 获利24元/公斤

4公斤A2

获利16元/公斤

每天：

管理运筹学 西北大学 经济管理学院 茹老师课件

运 筹 学西北大学经济管理学院 茹少峰 rsf00@http://www.77cn.com.cn

管理运筹学 西北大学 经济管理学院 茹老师课件

第8章整数线性规划

本章要求理解整数规划的含义；掌握两个变量的纯整数线性规划模型的图解法；掌握分枝定界 法的思想和方法；了解割平面法的原理；能够正 确引入0—1变量建立0-1线性规划模型；掌握指派 问题的求解算法；正确使用计算机软件求解整数 规划问题。

管理运筹学 西北大学 经济管理学院 茹老师课件

8.1 整数线性规划问题的提出在前面讨论的线性规划问题中，最优解可能是分数或小数，但对于某些 具体问题常要求最优解是整数。我们称这样的线性规划问题为整数线性规划 问题(Integer Linear Programming 简记为 ILP) 。 在整数规划中如果所有的变量都限制为整数，就称为纯整数规划(Pure ILP),如果仅一部分变量限制为整数，就称为混合整数规划(Mixed ILP), 整数规划的一个特例就是 0—1 规划，它的变量仅取 0 或 1。 例 8-1 投资决策问题 某部门在今后五年中可用于投资的资金总额为

数学建模

第七章7.2

数学规划模型

7.1 奶制品的生产与销售自来水输送与货机装运

7.37.4 7.5

汽车生产与原油采购接力队选拔和选课策略 饮料厂的生产与检修

7.6 钢管和易拉罐下料y

数学建模

数学规划模型实际问题中 的优化模型 x~决策变量

Min(或Max) z f ( x), x ( x1 , x n ) s.t. g i ( x) 0, i 1,2, mf(x)~目标函数

T

gi(x) 0~约束条件 数 学 规 划 线性规划 非线性规划 整数规划

决策变量个数n和 多元函数 约束条件个数m较大 条件极值 最优解在可行域 的边界上取得

重点在模型的建立和结果的分析

数学建模

4.1 奶制品的生产与销售企业生产计划 空间层次

工厂级：根据外部需求和内部设备、人力、原料等 条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费 用参数等，以最小成本为目标制订生产批量计划。 时间层次 若短时间内外部需求和内部资源等不随时间变化，可 制订单阶段生产计划，否则应制订多阶段生产计划。 本节课题

数学建模

例1 加工奶制品的生产计划1桶 牛奶 或 12小时 8小时 3公斤A1 获利24元/公斤

4公斤A2

获利16元/公斤

每天：