对偶问题
• 由上面的表可知，生产一件产品A1需要各设 备台时分别为2h，4h，3h，2h，如果将2h， 4h，3h，2h不用于生产产品A1，而是用于出 租，租费应满足（为了不蚀本，租费不能少 于利润，否则还不如自己生产产品合算呢！） 2 y1+4y2+3 y3+2 y4≥8，依次可分析得线性规划 模型如下
• （3）出基变量为当进基变量增大时， 首先下降为零的基变量，本例为x5
线性规划例
• 第二次迭代
（1）取x2，x3，x4为基变量，x1，x5为非 基变量 ，可行解为（0，25，15，15， 0），f＝62500
f 62500 1500x1 2500x5 / 3

x2 x3

线性规划中的一些名词和术语
• 可行解——满速线性规划全部约束条件 的解
• 可行域——全体可行解的集合 • 最优解——使得目标函数实现最小值
（或最大值）的可行解 • 最优值——最优解的目标函数值
线性规划模型标准型
• LP
n
min f c j x j j 1

s.t.

n j 1
• 解：设xj为第j种（甲、乙）产品的生产 件数 j＝1，2 ，则由题意知，问题可转 化为
线性规划例
Max f 1500x1 2500x2
3x1 2x2 65
s.
t.


2 x1
x2 3x2

40 75
x1, x2 0
• 注：Max为Maximize求f的最大值，s.t. 为Subject to约束，限制，满足于
欧美，在20世纪前叶，1914年提出了军 事运筹学中的兰彻斯特（Lanchester） 战斗方程；1917年排队论的先驱者丹麦 工程师爱尔朗（Erlang）在哥本哈根电
话公司研究电话通信系统时，提出了排 队论的一些著名公式；20世纪20年代初 提出了存贮论的最优批量公式；20世纪 30年代，在商业方面列温逊已经运用运
求线性规划方法－软件
LINDO软件包首先由Linus Schrage开 发，现在，美国的LINDO系统公司 （LINDO System Inc.）拥有版权，是 一种专门求解数学规划（优化问题）的 软件包。它能求解线性规划、（0，1） 规划、整数规划、二次规划等优化问题， 并能同时给出灵敏度分析、影子价格以 及最优解的松弛分析，非常方便实用。
25 15
3x1
x5 2x5
/3 /3
x4 15 2x1 x5 / 3
线性规划例
• （2）选择进基变量：方法同第一次迭 代，本例为x1
• （3）出基变量：方法同第一次迭代， 本例为x3
线性规划例
• 第三次迭代：
（1）取x1，x2，x4为基变量，x3，x5为非 基变量 ，可行解为（5，25，0，5，0）， f＝70000
• 约束条件： a11x1 a12x2
s.
t.
a21x1

a22
x2

a1n xn b1 a2n xn b2
am1x1 am2 x2 amn xn bm
x1, x2 , , xn 0
称xj为决策变量，cj为价值系数和费用系数， aij为约束系数或技术系数，bi为资源系数。
线性规划例
引例：某工厂拥有A、B、C三种类型的设备， 生产甲、乙两种产品，每种产品在生产中需 要占用的设备机时数，每件产品可以获得的 利润以及三种设备可利用的机时数如下表
设备A 设备B 设备C 利润（元/件）
产品甲 3 2 0
1500
产品乙 设备能力（h）
2
65
1
40
3
75
2500
线性规划例
• 问：工厂应如何安排生产可获得最大的 总利润？
线性规划一般模型
• 其它形式
n
Max f c j x j j 1

s.
t.

n j 1
aij x j

bi
i 1,
,m

xj 0
j 1,
,n
Max f CT X
s.t.
AX X

b 0
线性规划中的一些名词和术语
• 线性规划模型三要素： • 决策变量 • 约束条件 • 目标函数
f 70000 500x3 500x5

x1 x2

5 25
x3
/
3

2x5 x5 /
/ 3
9
x4 5 2x1 / 3 x5 / 9
线性规划例
• 2）选择进基变量：已无 ，因此该可行 解即为最优解，结束。
线性规划一般模型
• 目标函数： Max f c1x1 c2 x2 cn xn
aij x j

bi
i 1,
,m

xj 0
j 1,
,n
min f CT X
AX b
s.t.
X 0
min{CT X | AX b, X 0}
求线性规划方法－单纯形法
G.B.Danting在1947年提出了求解线性 规划问题的方法——单纯形法(simplex method)，其原理是：如果（LP）的可 行域K不是空集，我们从K的某一顶点 X0出发，判别它是否为最优解？若不是， 沿着边界找它邻近的另一个顶点，它应 比原来的顶点优，看它是否为最优解？ 若不是，再沿着边界找它邻近的顶点。 通过逐次迭代，直至找出最优解。
对偶问题
产品 设备
A1
A2
A3 总工时限
制/h
甲
2
1
3
70
乙
4
2
2
80
丙
3
0
1
15
丁
2
2
0
50
单位利润 8
10
2
/千元
对偶问题
• 解：设xj为产品Aj的生产件数 j＝1,2,3，则由 题意知，问题可转化为如下的线性规划问题
Max f 8x1 10x2 2x3
2x1 x2 3x3 70
运筹学的来源和组成
• 运筹学的三个来源：军事、管理和经济。 • 运筹学的三个组成部分：运用分析理论、
竞争理论和随机服务理论（排队论）
运筹学分支
线性规划是由美国运筹学工作者 G.B.Dantzig在1947年发表的结果，提出 单纯形法。列昂杰夫在1932年提出了投 入产出模型；冯·诺伊曼（Von Neumman）和O.Moogenstern合著 （1944年）的《对策论与经济行为》是 对策论的奠基作，同时该书已隐约地提 出了对策论与线性规划对偶理论地紧密 联系。
cj
j 1,
,n
yi 0 i 1, , m
设 yˆ* ( y1*, y2*, , ym* )T 为对偶问题（D）的最优解，
则称 为y原i* 有问题（P）第i个约束对应的影子价格 （Shadow Price）
对偶规划－影子价格
• 影子价格的经济含义：（1）影子价格是对现 有资源实现最大效益的一种估价。根据上例， 企业可以根据现有资源的影子价格，对资源 的使用有两种考虑：第一，是否将设备用于 出租，若租费高于某设备的影子价格，可考 虑出租该设备，否则不宜出租；第二，是否 将投资用于购买设备，以扩大生产能力，若 市价低于某设备的影子价格，可考虑买进该 设备，否则不宜买进。
对偶问题
Min f 70 y1 80 y2 15y3 50 y4
2 y1 4 y2 3y3 2 y4 8
s. t. 3y1y122y2y22yy33
10 2
y1, y2 , y3 0
• 说明：企业为了能够得到租用设备的用户， 使出租设备的计划成交，在价格满足约束条
筹思想来分析商业广告和顾客心里等； 20世纪30年代末，美英对付德国……， 20世纪50年代中期，我国著名的科学家
钱学森、许国志等将运筹学从西方引入 中国……。
运筹学在管理方面的应用
• 生产运作，物资库存管理，物资运输， 组织人事管理，市场营销，财务管理和 会计，计算机应用和信息系统开发，城 市管理等。
• 4.运输问题 ：m个物资产地B1, B2, …, Bm，n个物资销地A1, A2,…, An，si为 产地Bi产量，dj为销地Aj的销量，cij表 示把物资从产地Bi运到销地Aj的单位 运价，xij表示把物资从产地Bi运到销 地Aj的运输量，问应如何运输才能使
运费最小？
对偶问题
• 引例：某工厂计划在下一生产周期生产3种 产品A1, A2, A3，这些产品都要在甲、乙、 丙、丁4种设备上加工，根据设备性能和以 往的生产情况知道单位产品的加工工时、 各种设备的最大加工工时限制，以及每种 产品的单位利润，如下表。问如何安排生 产计划，才能使工厂得到最大利润？
• （2）运筹学是一门应用科学，它广泛应用现 有的科学技术知识和数学方法，解决实际中 提出的专门问题，为决策者选择最优决策提 供定量依据。
• （3）运筹学是给出问题坏的答案的艺术，否 则的话问题的结果会更坏。
运筹学的原则
为了有效地应用运筹学，必须遵循下列六 条原则：
（1）合伙原则 （2）催化原则 （3）互相渗透原则 （4）独立原则 （5）宽容原则 （6）平衡原则
（1）取x3，x4，x5为基变量，x1，x2为非 基变量 ，基本可行解为（0，0，65，40， 75），f＝0
f 1500x1 2500x2

x3 x4

65 3x1 2x2 40 2x1 x2
x5 75
3x2