运筹学教程胡云权-第五运筹学-1线性规划图解法

运筹学规划论图论排队论存储论对策论决策论线性规划非线性规划整数规划动态规划目标规划一般线性规划特殊线性规划运筹学的分支运筹学解决问题的过程1）提出问题：认清问题。2）寻求可行方案：建模、求解。3）确定评估目标及方案的标准或方法、途径。4）评估各个方案：解的检验、灵敏性分析等。5）选择最优方案：决策。6）方案实施：回到实践中。7）事后评估：考察问题是否得到完满解决。

内容提要线性规划问题及其数学模型线性规划解的概念、图解法线性规划应用——建模单纯形法原理和Excel求解第一章线性规划问题的提出如何合理地利用有限的人、财、物等资源，得到最好的经济效果?

线性规划问题及数学模型

例1.1：某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数见下表：

问题：工厂应如何安排生产可获得最大的总利润？

产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）15002500

目标函数maxz=1500x1+2500x2

约束条件s.t.3x1+2x2≤652x1+x2≤403x2≤75

x1

,x2

≥0

这是一个典型的利润最大化的生产计划问题。营养配餐问题

假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？各种食物的营养成分表9解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：

minS=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4

300050x1+60x2+20x3+10x4

55400x1+200x2+300x3+500x4

800x1，x2，

x3，x4

0线性规划数学模型的构成三要素决策变量表示某种重要的可变因素，变量的一组数据代表一个解决的方案或措施，用x1,x2,···,xn表示目标函数决策变量的函数，目标可以是最大化或最小化约束条件对决策变量取值的限制条件，由决策变量

x1,x2,···,xn

的不等式组或方程组构成max(min)z=c1x1+c2x2+…+cnxn

Subjectto（s.t.）

a11

x1+a12

x2+…+a1nxn≤(=,≥)b1a21

x1+a22

x2+…+a2nxn≤(=,≥)b2

...

am1

x1+am2x2+…+amnxn≤(=,≥)bmx1

,x2,…,xn≥0线性规划的一般形式

线性规划的简化形式

向量形式C=(c1,c2,…,cn)价值向量,资源向量变量xj对应的系数列向量线性规划的向量形式

矩阵形式约束条件系数矩阵线性规划的矩阵形式

maxz=c1x1

+c2x2

+…+cnxn

s.t.a11x1

+a12x2

+…+a1nxn=b1a21x1

+a22x2+…+a2nxn=b2

…

…

am1x1+am2x2

+…+amnxn

=bmx1,x2,…,xn≥0其中bi

≥0

，i=1,2,…,m线性规划的标准形式标准形式

标准形式：用向量和矩阵表述

目标最大化约束为等式决策变量均非负右端项非负

对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式。线性规划的标准形四个特点1目标函数求极小时MinZ=3x1+6x24x1+8x2=9x1,x2≥04x1+8x2=9x1,x2≥0标准形式为:MaxZ=-3x1-6x2-kkZ’Z’’Z=-Z非标准形式化为标准形2约束条件≤时MaxZ=x1+2x2

2x1+2x2=80x1+2x2=4x1,x2≥0标准形为MaxZ=x1+2x2

2x1+2x2≤80x1+2x2≤4x1,x2≥0x3≥0x4≥082x12x2x3X3为松弛变量,经济意义是没有被充分利用的资源数X4也为松弛变量,经济意义是没有被充分利用的资源数+x3+0x3+x4

+0x4

3约束条件≥时MaxZ=2x1+5x26x1+3x2≥24x1,x2≥0标准形为MaxZ=2x1+5x26x1+3x2=24x1,x2≥0x3≥0-x3+0x3246x13x2x3X3是剩余变量,或负松弛变量,经济意义是超用的资源数4变量取值无约束时MaxZ=3x1+7x22x1+6x2=8x1≥0,x2取值无约束设x2’≥0,x2’’≥0,令x2=x2’-

x2’’,则MaxZ=3x1+7x2’-7

x2’’

2x1+6x2’-6

x2’’

=8x1≥0,x2’≥0,x2’’≥0

5右端项有负值的问题在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi<0，则把该等式约束两端同时乘以-1，得到：

-ai1

x1-ai2x2-…-ainxn

=-bi。6xj

≤

0问题：令xj’=-xj

即可。例：将以下线性规划问题转化为标准形式

minf=-3x1+5x2+8x3-7x4s.t.2x1-3x2+5x3+6x4≤284x1+2x2+3x3-9x4≥396x2+2x3+3x4≤-58

x1,x3

≥0,x4≤0

maxz=3x1–5x2’+5x2”–8x3

-7x4’s.t.2x1–3x2’+3x2”+5x3-6x4’+x5=284x1+2x2’-2x2”+3x3+9x4’-x6=39-6x2’+6x2”-2x3+3x4’-x7

=58

x1

,x2’,x2”,x3

,x4’

,x5

,x6

,x7≥0

minf=-3x1+5x2+8x3-7x4s.t.2x1-3x2+5x3+6x4≤284x1+2x2+3x3-9x4≥396x2+2x3+3x4≤-58

x1,x3

≥0,x4≤0（原问题）(标准型)练习将下列线性规划问题化为标准形:MinZ=x1+2x2+3x34x1+5x2+6x3=-78x1+9x2+10x3≥1112x1+13x2+14x3≤15x1≥0,x2≤0,x3取值无约束作业教材P43习题1.21.101.13建模1.14建模（1）

§2.线性规划的求解

(1)图解法——只适用两个变量（2）单纯型法——适用多个变量

线性规划的图解法

对于只有两个变量的线性规划问题，可以二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。MaxZ=x1+2x22x1+2x2≤80x1+2x2≤4x1,x2≥0ox1x2123443212x1+2x2=82x2=4Z=2Z=6最优解为:x1=2,x2=2例1MinZ=x1+2x2x1+x2≥1x1-x2≤0x1,x2≥0ox1x21221x1+x2=1x1-x2=0Z=2Z=1.5最优解为:x1=0.5,x2=0.5例2

LP问题解的四种情况

——唯一最优解32MaxZ=x1+2x22x1+2x2≤80x1+2x2≤4x1,x2≥0ox1x2123443212x1+2x2=82x2=4Z=2Z=6最优解为:x1=2,x2=2[例1]MaxZ=2x1+2x22x1+2x2≤80x1+2x2≤4x1,x2≥0ox1x2123443212x1+2x2=82x2=4最优解有:1x1=2,x2=22x1=4,x