动态规划解线性规划

运筹学EXCEL操作介绍

使用Excel解线性规 划问题2010年10月15日

参考书目：

《Excel数据建模与应用》,第4章，清华大学出版社 《数据、模型与决策》第二章附录，机械工业出版社

运筹学EXCEL操作介绍

一个简单的例子某工厂计划生产两种产品，利润分别为2和3,已知生产单 位产品所需的设备台时和A、B两种原材料的消耗，如表

设备 原材料A 原材料B

产品1 1 4 0

产品2 2 0 4

8台时 16KG 12KG

目标是不超过资源限制的情况下，确定两产品产量，得 到最大利润。

运筹学EXCEL操作介绍

建立数学公式(步骤一)在工作表的顶部输入数据 确定每个决策变量所对应 的单元格位置 选择单元格输入公式，找 到目标函数的值 确定约束单元格输入公式， 计算每个约束条件左边的 值 确定约束单元格输入公式， 可采用 ‘复制粘贴’ 或 ‘直 计算每个约束条件右边的 接输入’ 的方式导入数据。 值

运筹学EXCEL操作介绍

建立数学公式(步骤二)在工作表的顶部输入数据 确定每个决策变量所对应 的单元格位置 选择单元格输入公式，找 到目标函数的值 选择一个单元格输入公式， 计算每个约束条件左边的 值 选择一个单元格输入公式， 计算每个约束条件右边的 值

图中，规定B1

（一）线性规划

案例分析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

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

第35卷第1期2005年1月

数学的实践与认识

Vol.35　No.1　

Jan.,2005　

确定线性规划全部最优解的方法

薛声家,　左小德

(暨南大学管理学院,广东广州　510632)

摘要:　使用凸多面体的表示定理,导出了标准型线性规划最优解的一般表达式,并基于单纯形法,给出最

优解唯一性条件以及当唯一性条件不满足时求出全部最优解的计算步骤,同时附有数值例子.

关键词:　线性规划;凸多面体;最优解;单纯形法

一般说来,实际上的经济管理问题所形成的线性规划的最优解给出了该实际问题的最佳实施方案.当线性规划有不止一个最优解时,便存在无穷多个最优解,求出线性规划的多个最优解是件很有意义的工作,因为它可以提供更多的最优方案供决策者选择.目前虽有不少文献对线性规划无穷多个最优解的情况进行了讨论,但有些存在错误和缺陷[1,2],另一些则讨论得不够完整、深入,缺乏详细有效的求解方法.本文使用凸多面体的表示(分解)定理,导出了标准型线性规划最优解的一般表达式,给出确定全部最优解的计算步骤,并附有数值例子.

1　线性规划最优解的一般表达式

考虑标准型线性规划问题:

Maxz=cTx

(SLP)s.t.Ax=b

xE0

　　其中,A为m×n阶矩阵,c和x为n维列向量,b为m维列

第四章 线性规划的对偶理论

一、填空题

1．线性规划问题具有对偶性，即对于任何一个求最大值的线性规划问题，都有一个求最小值/极小值的

线性规划问题与之对应，反之亦然。

2．在一对对偶问题中，原问题的约束条件的右端常数是对偶问题的目标函数系数。 3．如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为等式_。 4．对偶问题的对偶问题是原问题_。

5．若原问题可行，但目标函数无界，则对偶问题不可行。

6．若某种资源的影子价格等于k。在其他条件不变的情况下(假设原问题的最佳基不变)，当该种资源增加3个单位时。相应的目标函数值将增加3k 。

﹡－

7．线性规划问题的最优基为B，基变量的目标系数为CB，则其对偶问题的最优解Y= CBB1。

﹡﹡﹡﹡

8．若X和Y分别是线性规划的原问题和对偶问题的最优解，则有CX= Yb。 9．若X、Y分别是线性规划的原问题和对偶问题的可行解，则有CX≤Yb。

﹡﹡﹡

10．若X和Y分别是线性规划的原问题和对偶问题的最优解，则有CX=Y*b。

11．设线性规划的原问题为maxZ=CX，Ax≤b，X≥0，则其对偶问题为min=Yb YA≥c Y≥0_。 12．影子价格实际上是与原问题各约束条

2016高三数学 不等式与线性规划 姓名：________ 2015.11.10

．．．．．．．．

x≥2，??139

1.实数x，y满足?x－2y＋4≥0，若z＝kx＋y的最大值为13，则实数k＝( ) A.2 B. C. D.5

24

??2x－y－4≤0，y≥－1，??

2.变量x，y满足?x－y≥2，

??3x＋y≤14，

若使z＝ax＋y取得最大值的最优解有无穷多个，则a的取值集合是____.

14

3.下列命题正确的是( ) A．若x≠kπ，k∈Z，则sin2x＋2≥4 B．若a＜0，则a＋≥－4

sinxa

ba

C．若a＞0，b＞0，则lg a＋lg b≥2lg a·lg b D．若a＜0，b＜0，则＋≥2

ab

4.函数f(x)＝(x－2)(ax＋b)为偶函数，且在(0，＋∞)单调递增，则f(2－x)＞0的解集为_____． x＋y≥0，??

5.在平面直角坐标系xOy中，记不等式组?x－y≤0，

??y≤2

??u＝x＋y，

所表示的平面区域为D.在映射T：?

?v＝x－y?

的作用下，区域D内的点(x，y)对应的象为点(u，v)，则由点(u，v)所形成的平面区域的面积为_____．

6.设对任意实数x>0，y>0，

第四章 线性规划的对偶理论

一、填空题

1．线性规划问题具有对偶性，即对于任何一个求最大值的线性规划问题，都有一个求最小值/极小值的

线性规划问题与之对应，反之亦然。

2．在一对对偶问题中，原问题的约束条件的右端常数是对偶问题的目标函数系数。 3．如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为等式_。 4．对偶问题的对偶问题是原问题_。

5．若原问题可行，但目标函数无界，则对偶问题不可行。

6．若某种资源的影子价格等于k。在其他条件不变的情况下(假设原问题的最佳基不变)，当该种资源增加3个单位时。相应的目标函数值将增加3k 。

﹡－

7．线性规划问题的最优基为B，基变量的目标系数为CB，则其对偶问题的最优解Y= CBB1。

﹡﹡﹡﹡

8．若X和Y分别是线性规划的原问题和对偶问题的最优解，则有CX= Yb。 9．若X、Y分别是线性规划的原问题和对偶问题的可行解，则有CX≤Yb。

﹡﹡﹡

10．若X和Y分别是线性规划的原问题和对偶问题的最优解，则有CX=Y*b。

11．设线性规划的原问题为maxZ=CX，Ax≤b，X≥0，则其对偶问题为min=Yb YA≥c Y≥0_。 12．影子价格实际上是与原问题各约束条

线性规划模型研究

摘要：探讨线性规划在生活中的应用。方法：了解线性规划法及其特点；分析生活中某些问题适合利用线性规划求解的缘由；求解出所需值,同时观察其现实意义。结果：由于生活中很多关于利益最大化、成本最小化的问题，所以线性规划在生活中应用很广泛。而且线性规划求解方法多样；求出的结果能很好反映现实问题。结论：线性规划模型在生活中应用广泛。 关键词：线性规划；生活问题；求解相关值

Linear programming model

Abstract: discuss the application of linear programming in life. Method: to investigate the linear programming method and its characteristics; Analysis of some problems in the life is suitable for using the linear programming to solve the reason; Solving the required value and observe its realistic significance.

线性规划专题复习（教师版）

?2x?y?12,?2x?9y?36,?1．(2004年广东)变量x、y满足下列条件：?

2x?3y?24,???x?0,y?0.则使z=3x+2y的值最小的（x，y）是

A． ( 4.5 ,3 ) B． ( 3,6 )

（ B ） C． ( 9, 2 )

D． ( 6, 4 )

?x?y?2?0,?2．在平面直角坐标系中，不等式组?x?y?2?0,表示的平面区域的面积是（ B ）

?x?2?(A)42 (B)4 (C) 22 (D)2

?x?0?3．若A为不等式组?y?0表示的平面区域，则当a从－2连续变化到1时，动直线

?y?x?2?x?y?a 扫过A中的那部分区域的面积为 ( C )

A．

3 4 B．1 C．

7 4 D．5

?y?x，?4．设变量x，y满足约束条件：?x?2y?2，，则z?x?3y的最小值为（ D ）

?x??2．?A．?2

B．?4

C．?6

D．?8

?x?y?1?0，?5．若实数x，y满足?x?y?0，则z?x?2y的最小值是（ A ）

?x?0，?A．0

B．

1

市场营销应用

案例一：媒体选择

在媒体选择中应用线性规划的目的在于帮助市场营销经理将固定的广告预算分配到各种广告媒体上，可能的媒体包括报纸、杂志、电台、电视和直接邮件。在这些媒体中应用线性规划，目的是要使宣传范围、频率和质量最大化。对于应用中的约束条件通常源于对公司政策、合同要求及媒体的可用性。在下面的应用中，我们将介绍如何应用线性规划这一工具来建立模型进而解决媒体选择问题。 REL发展公司正在私人湖边开发一个环湖社区。湖边地带和住宅的主要市场是距离开发区100英里以内的所有中上收入的家庭。REL公司已经聘请BP&J来设计宣传活动。

考虑到可能的广告媒体和要覆盖的市场，BP&J建议将第一个月的广告局限于5种媒体。在第一个月末，BP&J将依据本月的结果再次评估它的广告策略。 BP&J已经收集到了关于受众数量、广告单价、各种媒体一定周期内可用的最大次数以及评定5种媒体各自宣传质量的数据。质量评定是通过宣传质量单位来衡量的。宣传质量单位是一种用于衡量在各个媒体中一次广告的相对价值的标准，它建立于BP&J在广告业中的经验，将众多因素考虑在内，如受众层次（年龄、收入和受众受教育的程度）、呈现的形象和广告的质量。表4-1列出了收集到

一般非线性规划

标准型为：

min F(X)

s.t AX<=b Aeq G(X)?0 ?X?beq Ceq(X)=0 VLB?X?VUB

其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同.用Matlab求解上述问题，基本步骤分三步： 1. 首先建立M文件fun.m,定义目标函数F（X）: function f=fun(X); f=F(X);

2. 若约束条件中有非线性约束:G(X)?0或Ceq(X)=0,则建立M文件

nonlcon.m定义函数G(X)与Ceq(X): function [G,Ceq]=nonlcon(X) G=... Ceq=... 3. 建立主程序.非线性规划求解的函数是fmincon,命令的基本格式如下：

(1) x=fmincon(‘fun’,X0,A,b) (2) x=fmincon(‘fun’,X0,A,b,Aeq,beq)

(3) x=fmincon(‘fun’,X0,A,b, Aeq,beq,VLB,VUB)

(4) x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’) (5)x=fmincon(‘fun’,X0,