文档介绍：1
冯•诺伊曼(Von Neuman)和摩根斯坦(Morgenstern)1944年发表的 《博弈论与经济行为》涉及与线性规划等价的对策问题及线性规划对偶理论
从1964年诺贝尔奖设经济学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作，其中比较著名的还有Simon，Samullson，Leontief，Arrow，Miller等
第1页/共29页
2
研究对象
有一定的人力、财力、资源条件下，如何合理安排使用，效益最高
某项任务确定后，如何安排人、财、物，使之最省
第2页/共29页
3
线性规划模型
是通过对实际问题的分析而建立的表示决策变量、最优目标和约束条件之间关系的一组数学关系式，由决策变量、目标函数和约束条件三部分组成。
在满足一组约束条件下，求一组决策变量的值，使目标函数达到最优。
第3页/共29页
4
线性规划的特点
决策变量连续性：求解出的决策变量值可以是整数、小数；
线性函数：目标函数方程和约束条件方程都是线性方程；
单目标：目标函数是单目标，只有一个极大值或一个极小值；
确定性：只能应用于确定型决策问题。
第4页/共29页
5
A B 备用资源
煤 1 2 30
劳动日 3 2 60
仓库 0 2 24
利润 40 50
例1、生产计划问题
A, B各生产多少, 可获最大利润?
第5页/共29页
6
x1 + 2x2 30
3x1 + 2x2 60
2x2 24
x1，x2 0
max Z= 40x1 +50x2
解:设产品A, B产量分别为变量x1 ， x2
第6页/共29页
7
例2
求：最低成本的原料混合方案
原料 A B Ｃ 每单位成本
1 4 1 0 2
2 6 1 2 5
3 1 7 1 6
4 2 5 3 8
每单位添
加剂中维生 12 14 8
素最低含量
第7页/共29页
8
解：设每单位添加剂中原料i的用量为xi(i =1,2,3,4)
minZ= 2x1 + 5x2 +6x3+8x4
4x1 + 6x2 + x3+2x4 12
x1 + x2 +7x3+5x4 14
2x2 + x3+3x4 8
xi 0 (i =1,…,4)
第8页/共29页
9
一般式
Max(min)Z=C1X1+ C2X2+…+CnXn
a11X1+ a12X2+…+ a1nXn (=, )b1
a21X1+ a22X2+…+ a2nXn (=, )b2
… … …
am1X1+ am2X2+…+ amnXn (=, )bm
Xj 0(j=1,…,n)
第9页/共29页
10
要解决的问题的目标可以用数值指标反映
对于要实现的目标有多种方案可选择
有影响决策的若干约束条件
第10页/共29页