当前位置：文档之家 › 第一章线性规划与单纯形法教学讲义

第一章线性规划与单纯形法教学讲义

  • 格式：ppt
  • 大小：399.50 KB
  • 文档页数：61

下载文档原格式

  / 61

合集下载

第一章线性规划问题及单纯形解法演示文稿

第一章线性规划问题及单纯形解法演示文稿
线性规划问题的可行解集S是凸集 设X属于S,若x=0,则一定为极点；若x 0，则为极点的充要条件是：x的正分量所 对应的系数列向量线性无关。
只要存在可行解，就一定存在极点
极点的个数是有限的
最优解只可能在凸集的极点上，而不可能发生 在凸集的内部
38
第38页，共65页。
关于标准型解的若干基本概念：
Z=15x11+21x12+18x13+
20x21+25x22+16x23, x11+x12+x13≤200, x21+x22+x23≤150, x11+ x21 ＝100, x12+x22＝80, x13+x23≥90, x13+x23≤120, xij≥0 ﹙i=1,2 j=1,2,3﹚.
10
第10页，共65页。
maxz( x) c x c x c x
11
22
nn
s.t.
a x a x a x b
11 1
12 2
1n n
1
ax 21 1
a x 22 2
a x 2n n
b 2
am1
x 1
a x m2 2
a x mn n
b m
x , x ,, x 0
1
2
n
12
第12页，共65页。
1、标准型的几种不同的表示方式
对有限个约束条件则其可行域的顶点也是有限的。
z=10000=50x1+100x
2
z=0=50x1+100x2
x2
x1+x2=300
AB C
E
z=27500=50x1+100x

线性规划与单纯形法PPT课件

线性规划与单纯形法PPT课件
Max Z = 50 x1 + 30 x2
第3步 --表示约束条件
4x1+3x2 120（木工工时限制） 2x1+x2 50 （油漆工工时限制）
x1，x2≥0 （变量取非负值限制）
该计划的数学模型
max Z=50x1+30x2 4x1+3x2 120
s.t.
2x1+ x2 50 x1, x2 0
问如何组织生产才能使每月的销售收入最大？
• 第1步 -确定决策变量
是问题中要确定的未知量
xx •设
1 ——桌子的产量 2 ——椅子的产量
，表明规划中的用数量表 示的方案、措施，可由决 策者决定和控制。
z ——利润
x1
x2
第2步 --定义目标函数
Max Z = 50 x1 + 30 x2
第2步 --定义目标函数
线性规模解决的问题
• 给定一定数量的人力、物力、财力等资源， 研究如何充分利用，以发挥其最大效果
• 已给定计划任务，研究如何统筹安排，用最 少的人力、物力、财力去完成
2、线性规划问题的数学模型
线性规划数学模型三要素：
决策变量、目标函数、约束条件
➢ 每一个线性规划问题都有一组决策变量 (x1, x2, ……, xn) , 这组决策变量的值就代表 一个具体方案。
1、问题的提出
例1.1 生产计划问题（资源利用问题） 某家具厂生产桌子和椅子两种家具。 桌子售价50元/个，椅子销售价格30元/个。 需要木工和油漆工两种工种。 生产一个桌子需要木工4小时，油漆工2小时。 生产一个椅子需要木工3小时，油漆工1小时。 该厂每个月可用木工工时为120小时， 油漆工工时为50小时。
第1工厂投污水的水质要求 ：(2 x1) 2 500 1000

第一章 线性规划及单纯形法

第一章 线性规划及单纯形法
37
线性规划问题的标准形式： 线性规划问题的标准形式：
max f = ∑ c j x
j =1 j n
n ∑ aij x j = bi , i = 1,2,L , m j =1 x j ≥ 0, j = 1,2,L , n
日产量（ 日产量（吨） 9 5 7 21
11
）（模型 例2（运输问题）（模型） （运输问题）（模型）
minf = 2 x11 + 9 x12 + 10 x13 + 7 x14 + x21 + 3 x22 + 4 x23 + 2 x24 + 8 x31 + 4 x32 + 2 x33 + 5 x34 x11 + x12 + x13 + x14 = 9 x +x +x +x =5 23 24 21 22 x31 + x32 + x33 + x34 = 7 x11 + x21 + x31 = 3 s.t. x12 + x22 + x32 = 8 x13 + x23 + x33 = 4 x14 + x24 + x34 = 6 xij ≥ 0(i = 1,2,3; j = 1,2,3,4)
18
3、（线性规划）数学模型的三要素 、（线性规划） 、（线性规划 变量/决策变量 决策变量； ①变量 决策变量； 目标函数（ ②目标函数（max/min）； ）； 约束条件。 ③约束条件。
19
决策变量： ①变量/决策变量：指决策者为实现规划目标采 变量 决策变量 取的方案、措施，是问题中要确定的未知量； 取的方案、措施，是问题中要确定的未知量；

线性规划-讲义-12章

线性规划-讲义-12章
第一章 线性规划 第二章 对偶单纯形法与灵敏度分析 第三章 运输问题 第四章
整数规划
第五章 动态规划
第六章 图论与问题及其数学模型 1.1.1 线性规划问题的数学模型
例1、生产计划问题 I 1 3 0 40 II 2 2 2 50
原材料A 原材料B 台时 利润
例6 max S=2x1+ 4x2 2x1+x2 8
x2
8
-2x1+ x2=2
-2x1+x2 2
x1 , x2 0 无界解(无最优解) 无界解=>可行域无界 <=
6
4
2
0
4
x1
2x1+ x2=8
例7 max S=3x1+2x2 -x1 -x2 1
x1 , x2 0 有解 无可行解 唯一解 无穷多解 无有限最优解 无可行解
(3) 变量 若xj 0, 令 xj = -xjˊ, 其中: xjˊ 0 若xj是无限制变量. 令 xj = xjˊ- xj〞, 其中: xjˊ、 xj〞 0
例 3x1+2x2 8
x1 –4x2 14
x2 0 令x1= x1'- x1 " 3 x1' –3x1 " +2x2 8 x1' - x1 " – 4x2 14 x1' , x1" ,x2 0
2x3 +2x4+ x5=100 3x1+ x2+2x3 +3x5=100
xi 0 (i =1,…,5)，且为整数
最优方案是：按方案I-30根, II-10根；III-50根 即只要90根原料--制造100套
运输问题

第1章-线性规划及单纯形法-课件(1)

第1章-线性规划及单纯形法-课件(1)

✓ x1、 x2 0
IБайду номын сангаас
设备
1
原材料 A 4
原材料 B 0
利润
2
II 资源限量
2 8 台时
0
16kg
4
12kg
3
第一章 线性规划及单纯形法 运筹学
该计划的数学模型
✓ 目标函数 ✓ 约束条件
Max Z = 2x1 + 3x2
x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0
x1
✓ 美国航空公司关于哪架飞机用于哪一航班和哪些 机组人员被安排于哪架飞机的决策。
✓ 美国国防部关于如何从现有的一些基地向海湾运 送海湾战争所需要的人员和物资的决策。
✓ ……
第一章 线性规划及单纯形法 运筹学
二、线性规划问题的数学模型
✓ 1、一般形式 ✓ 2、简写形式 ✓ 3、表格形式 ✓ 4、向量形式 ✓ 5、矩阵形式
1、唯一最优解
max Z 2 x 1 3 x 2
2 x 1 2 x 2 12 ⑴
x1 4 x1
2 x2
8 16
⑵ ⑶
4 x 2 12 ⑷
x 1 0 , x 2 0
1 234 56
x2
⑶ ⑷
(4，2)
0 1 234 5678
x1
⑵
⑴
✓最优解：x1 = 4,x2 = 2，有唯一最优解Z=14。
第一章 线性规划及单纯形法 运筹学
三、线性规划模型的标准形式
✓ 1、标准形式 ✓ 2、转换方式
第一章 线性规划及单纯形法 运筹学
1、标准形式
maZx cjxj
xj
aijxj 0
bi

运筹学第1章：线性规划问题及单纯型解法

运筹学第1章：线性规划问题及单纯型解法

原料甲 原料乙 最低含量 VA 0.5 0.5 2 VB1 1.0 0.3 3 VB2 0.2 0.6 1.2 VD 0.5 0.2 2 0.3 0.5 单价
分别代表每粒胶丸中甲, 设 x1, x2分别代表每粒胶丸中甲, 乙两种原料的用量
5
例3,合理下料问题 , 分别代表采用切割方案1~8的套数, 的套数, 设 xj 分别代表采用切割方案 的套数
19
( f(x
)= 3
6
1.2.2 单纯型法的基本思路
确定初试基础可行解
检查是否为 最优解? 最优解?
是
求最优解的目标函数值
否 确定改善方向
求新的基础可行解
20
1.2.3 单纯型表及其格式
IV CB III XB II x1 b c1 a11 a21 c1′′= cn+1 xn+1 b1 c2′′= cn+2 xn+2 b2 x2 … xn c2 … cn a12 … a1n a22 … a2n I xn+1 cn+1 1 0 0 zn+1 xn+2 cn+2 0 1 0 zn+2 … … … … … … xn+m cn+m 0 0 1 zn+m
OBJ : max f ( x) = 6x1 + 4x2 2x1 + x2 ≤ 10 铜资源约束 x1 + x2 ≤ 8 铅资源约束 s.t. x2 ≤ 7 产量约束 x1, x2 ≥ 0 产量不允许为负值 最优解: x1 = 2, x2 = 6, max f ( x) = 36.
4
例2,配料问题(min, ≥) ,配料问题(
2 max 1 O 1 2 3 4 D 5 6 7 H 8

1_LP及单纯形法

1_LP及单纯形法

max(min) Z CX
n Pj x j (, )b s.t j 1 X 0
线性规划问题可记为矩阵形式：
max(min) Z CX
AX (, )b s.t X 0
线性规划解的定义： (1)满足线性规划问题所有约束条件的解是该问题的 可行解。 (2)线性规划问题全部可行解的集合构成线性规划问 题的可行域（或称可行解集）,记做R 。 (3)使目标函数达到极值的可行解称为线性规划问题 的最优解。记作X*。则对任何目标函数求最大值 的线性规划，存在 : CX≤ CX*
例题1. 1 如何排产，获利最大？
产品P 解：将一个实 原料A 1 际问题模型化 原料B 5 原料C 0 需要四步： Step1 产品单价 x 2万元
1
确定决策变量：制造P产品x1件， Q产品x2件。 Step2 确定目标函数： MaxZ=2 x1+ 5x2 Step3 确定约束方程： x1+ 2x2≤8 5x1+ 2x2≤20 4x2≤12 Step4 确定变量取值限制 x1，x2≥0
可能在建模过程中，约束条 件自相矛盾的错误。
O
x1
图解法的观察
最优解：总是在可行域的边界上，一般由可行域的
极点表示。
可行域：由约束平面围起来的凸多边形区域，可行域
内的每一个点代表一 个可行解。
如果目标函数等值线可以无限制地在可行域内向改
善的方向移动，线性规划问题无界;
线性规划问题也可能存在无穷多个最优解。 如果可行域为空集，线性规划 问题无可行解；
第二节
线性规划的标准形式和解的性质
max Z c1 x1 c2 x2 cn xn
一、Linear Programming标准形式

运筹学课程讲义

运筹学课程讲义

运筹学课程讲义第一部分 线性规划 第一章 线性规划的基本性质 1.1 线性规划的数学模型一、 线性规划问题的特点胜利家具厂生产桌子和椅子两种家具。

桌子售价50元/个，椅子售价30元/个。

生产桌子和椅子需木工和油漆工两种工种。

生产一个桌子需要木工4小时，油漆工2小时。

生产一个椅子需要木工3小时，油漆工1小时。

该厂每月可用木工工时为120小时，油漆工工时为50小时。

问该厂如何组织生产才能使每月的销售收入最大？213050m ax x x z +=⎪⎩⎪⎨⎧≥≤+≤+0,50212034212121x x x x x x 例：某工厂生产某一种型号的机床。

每台机床上需要 2.9m 、2.1m 、1.5m 的轴，分别为1根、2根和1根。

这些轴需用同一种圆钢制作，圆钢的长度为74m 。

如果要生产100台机床，问应如何安排下料，才能用料最省？二、 数学模型的标准型 1. 繁写形式 2. 缩写形式 3. 向量形式 4. 矩阵形式三、 任一模型如何化为标准型？1. 若原模型要求目标函数实现最大化，如何将其化为最小化问题？2. 若原模型中约束条件为不等式，如何化为等式？3. 若原模型中变量x k 是自由变量，如何化为非负变量？4. 若原模型中变量x j 有上下界，如何化为非负变量？⎪⎪⎩⎪⎪⎨⎧≥≤-=--≤+--≥-+----=无约束321321321321321,0,052010651535765max x x x x x x x x x x x x x x x z 令'''3'3''3'331'1,0,,,Z Z x x x x x x x =-≥-=-=⎪⎪⎩⎪⎪⎨⎧≥-=+-++=+-+-=+-+-+--+-++-=0,,,,,,,5201010651533507765min 7654''3'32'17''3'32'15''3'32'164''3'32'1765''3'32'1'x x x x x x x x x x x x x x x x x x x x x x x x Mx Mx x x x x x z 1. 2图解法该法简单直观，平面作图适于求解二维问题。

第一章线性规划及单纯形法

第一章线性规划及单纯形法

第一章线性规划及单纯形法6.6单纯形法小结Drawingontheexampl,thetwoaxisinterceptsareplotted.2、求初始基可行解并进行最优性检验Cj比值CBXBb 检验数?jx1x2x3x4x53500081010012020103634001x3x4x5000035000令非基变量x1=0，x2=0，找到一个初始基可行解：x1=0，x2=0，x3=8，x4=12，x5=36，σj＞0，此解不是最优（因为z=3x1+5x2+0x3+0x4+0x5)即X0=(0,0,8,12,36)T，此时利润Z=03、寻找另一基可行解Cj比值CBXBb检验数?jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9主元首先确定入基变量再确定出基变量检验数?j81010060101/2012300-21x3x2x5050-30300-5/20Cj比值CBXBb检验数?jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9令x1=0，x4=0，得x2=6，x3=8，x5=12，即得基可行解X1=(0,6,8,0,12)T此时Z＝30σ1=3＞0，此解不是最优迭代4、寻找下一基可行解Cj比值CBXBb检验数?jx1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4检验数?j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1令x4=0，x5=0，得x1=4，x2=6，x3=4，即X0=(4,6,4,0,0)T?j＜0最优解:X=(4,6,4,0,0)T最优值:Z=42小结：单纯形表格法的计算步骤①将线性规划问题化成标准型。

②找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。

运筹学第一章

运筹学第一章
max z = - x1’ +2x2 +3（ x3’ - x3” ） - x1’ +x2 – ( x3’ - x3” )-x4 = 9 st. 3x1’ +2x2 -4 ( x3’ - x3” )-x5= 7 x1’ +2x2 - 3 ( x3’ - x3” ) = 6 x1’ ≥ 0, x2 ≥ 0, x3’ ≥0 x3” ≥0
3.线性规划问题的标准形式 线性规划问题的标准形式 max z =- x1-2x2 -3x3 2 x1’+x2 +(x3’ - x3” )+ x4 = 9 3 x1’ +x2 +2 (x3’ - x3” ) –x5 = 4 st. -4 x1’ +2x2 +3 (x3’ - x3” ) =6 x1’ ≥ 0, x2 ≥0, x3’ ≥0 x3” ≥0
例1-1-2 ---1 min z = x1+2x2 +3x3 ﹣2 x1+x2 +x3 ≤9 st. ﹣3 x1+x2 +2x3 ≥ 4
4 x1－2x2 － 3x3 =﹣6
x1 ≤0, x2 ≥0, x3 无约束。 （1）min z = x1+2x2 +3x3 令Z=-Z’ min Z=min（-z ’）=max z ’
第一章 讲解内容
第一节： 第一节：线性规划问题及其数学模型 第二节： 第二节：线性规划问题的几何意义 第三节：单纯形法 第三节： 第四节： 第四节：单纯形法的计算过程 第五节： 第五节：单纯形法的进一步讨论 第六节： 第六节：应用案例
第一章 线性规划问题及其数学模型 1. 问题的提出 2.图解法（重点） 3. 线性规划问题的标准形式 4.线性规划问题的解的概念（重点、难点）

运筹学基础及应用第五版胡运权第一章

运筹学基础及应用第五版胡运权第一章
问题的提出 某企业计划生产Ⅰ、Ⅱ两种产品。这两种产品都要分别在A、B、C、D四种不同设备上加工。生产每件产品Ⅰ需占用各设备分别为2、1、4、0h，生产每件产品Ⅱ，需占用各设备分别为2、2、0、4h。已知各设备计划期内用于生产这两种产品的能力分别为12、8、16、12h，又知每生产一件产品Ⅰ企业能获得2元利润，每生产一件产品Ⅱ企业能获得3元利润，问企业应安排生产两种产品各多少件，使总的利润收入为最大。
xi 0
aij
aLj
xL 0
i
∴ P1 , P2,······,PL-1, PL+1,······ Pm, Pj 线性无关。
∴ X1 也为基本可行解。
四、最优性检验和解的判别
令
，其中 随基的改变而改变
X1 = (x1 0- a1j ,x2 0- a2j ,···,xm 0- amj ,0,···,,···,0)T
必要性：X非基本可行解 X非凸集顶点 不失一般性，设X=(x1,x2,······,xm,0,0,······,0)T，为非基本可行解， ∵ X为可行解，
证：等价于 X非基本可行解X非凸集顶点
又 X是非基本可行解， ∴ P1,P2,······,Pm线性相关，即有 1P1+2P2+······+mPm=0， 其中1，2，······，m不全为0，两端同乘≠0，得 1P1+2P2+······+mPm=0，······（2）
∵ >0, 1->0 ，当xj=0， 必有yj=zj=0
∴
pjyj =
j=1
n
pjyj=b ······(1)
j=1
r
pjzj =
j=1
n
pjzj=b ······(2)

线性规划讲义

线性规划讲义

线性规划讲义一、引言线性规划是一种数学建模和优化方法，用于解决具有线性约束条件和线性目标函数的问题。

它可以应用于各种领域，如生产计划、资源分配、运输问题等。

本讲义将介绍线性规划的基本概念、模型建立方法、解法和应用案例。

二、基本概念1. 线性规划问题的定义线性规划问题是指在一组线性约束条件下，寻找使线性目标函数取得最大（小）值的决策变量的取值。

2. 线性规划问题的数学表达线性规划问题的数学表达可以用如下形式表示：最大化（最小化）目标函数：Z = c₁x₁ + c₂x₂ + ... + cₙxₙ约束条件：a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂...aₙ₁x₁ + aₙ₂x₂ + ... + aₙₙxₙ ≤ bₙx₁, x₂, ..., xₙ ≥ 03. 线性规划问题的基本要素线性规划问题包含以下基本要素：目标函数：决策变量的线性组合，表示待优化的目标。

约束条件：对决策变量的约束，限制了可行解的范围。

决策变量：问题中需要决策的变量。

可行解：满足所有约束条件的决策变量取值。

最优解：使目标函数取得最大（小）值的可行解。

三、模型建立方法1. 确定决策变量根据问题的实际情况，确定需要决策的变量，如生产数量、资源分配比例等。

2. 建立目标函数根据问题的目标，将决策变量线性组合，构建目标函数。

3. 建立约束条件根据问题的约束条件，将决策变量的线性组合与约束条件进行比较，建立约束方程。

4. 确定变量的取值范围根据问题的实际情况，确定决策变量的取值范围，如非负约束条件。

四、解法1. 图形法图形法适用于二维线性规划问题，通过绘制约束条件的直线和目标函数的等高线，找到最优解的图形位置。

2. 单纯形法单纯形法是一种迭代求解线性规划问题的方法，通过不断移动基变量，找到最优解。

3. 整数规划法整数规划法适用于决策变量需要取整数值的线性规划问题，通过引入整数变量和约束条件，将问题转化为整数规划问题，并应用相应的求解方法。

运筹学第一章

运筹学第一章

第一章、 线性规划和单纯形法1.1 线性规划的概念一、线性规划问题的导出1．(引例) 配比问题——用浓度为45%和92%的硫酸配置100t 浓度为80%的硫酸。

取45%和92%的硫酸分别为x1和x2t,则有： 求解二元一次方程组得解。

目的相同，但有5种不同浓度的硫酸可选（30%，45%，73%，85%，92%）会出现什么情况？设取这5种硫酸分别为 x1、x2、x3、x4、x5 t, 则有： ⎩⎨⎧⨯=++++=++++1008.092.085.073.045.03.01005432154321x x x x x x x x x x 请问有多少种配比方案？为什么？哪一种方案最好？假设5种硫酸价格分别为：400，700，1400，1900，2500元/t ，则有：2.生产计划问题如何制定生产计划，使三种产品总利润最大？考虑问题：⎩⎨⎧⨯=+=+1008.092.045.01002121x x x x ⎪⎩⎪⎨⎧=≥⨯=++++=++++++++=5,,2,1,01008.092.085.073.045.03.0100..250019001400700400543215432154321 j x x x x x x x x x x x t s x x x x x MinZ j（1）何为生产计划？（2）总利润如何描述？（3）还要考虑什么因素？（4）有什么需要注意的地方（技巧）？（5）最终得到的数学模型是什么？二、线性规划的定义和数学描述（模型）1．定义：对于求取一组变量xj (j =1,2,......,n)，使之既满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划。

2.配比问题和生产计划问题的线性规划模型的特点：用一组未知变量表示要求的方案，这组未知变量称为决策变量；存在一定的限制条件，且为线性表达式；有一个目标要求（最大化，当然也可以是最小化），目标表示为未知变量的线性表达式，称之为目标函数； 对决策变量有非负要求。

第1章线性规划与单纯形法

第1章线性规划与单纯形法
26
线性规划问题的数学模型
7. 线性规划问题的解
线性规划问题
n
max Z cj xj (1) j 1
s.t
n j 1
aij
xj
bi
(i 1, 2,
, m) (2)
x
j
0,
j
1, 2,
, n (3)
求解线性规划问题，就是从满足约束条件(2)、(3)的方程组 中找出一个解，使目标函数(1)达到最大值。
解： Max z = 3x1–5x2’+5x2”–8x3 +7x4 s.t. 2x1–3x2’+3x2”+5x3+6x4+x5= 28 4x1+2x2’-2x2”+3x3-9x4-x6= 39 -6x2’+6x2”-2x3-3x4-x7 = 58 x1 ,x2’,x2”,x3 ,x4 ,x5 ,x6 ,x7 ≥ 0
x1 , x2 0, x3无约束
解:（１）因为x3无符号要求 ，即x3取正值也可取负值，标准 型中要求变量非负，所以
用 x3 x3 替换 x3 ，且 x3 , x3 0
20
线性规划问题的数学模型
(2) 第一个约束条件是“≤”号，在“≤”左端加入松驰变量x4， x4≥0,化为等式；
(3) 第二个约束条件是“≥”号，在“≥”左端减去剩余变量x5， x5≥0；
11
线性规划问题的数学模型
3. 建模条件 (1) 优化条件：问题所要达到的目标能用线型函数描述，且 能够用极值 （max 或 min）来表示；
(2) 限定条件：达到目标受到一定的限制，且这些限制能够 用决策变量的线性等式或线性不等式表示；
(3) 选择条件：有多种可选择的方案供决策者选择，以便找 出最优方案。

《运筹学》考研考点讲义

《运筹学》考研考点讲义

《 运筹学》 考点精讲及复习思路
第一章 ㊀ 线性规划与单纯形法
一、 本章考情分析：
常考题型： 选择、 填空、 简答、 判断和计算 分值： 必考知识点， 分值占 ３ ０分以上 重要性： 作为前五章的基础铺垫， 非常重要！ 重要程度： ★★★★★
二、 本章基本内容：
１ ） 掌握线性规划的数学模型的标准型； ２ ） 掌握线性规划的图解法及几何意义； ３ ） 了解单纯形法原理； ４ ） 熟练掌握单纯形法的求解步骤； ５ ） 能运用大 Ｍ 法与两阶段法求解线性规划问题； ６ ） 熟练掌握线性规划几种解的性质及判定定理．
㊀ 目 ㊀㊀ 录 ㊀
第一章㊀线性规划与单纯形法 （ １ ） 第二章㊀对偶问题与灵敏度分析 （ ２ ４ ） 第三章㊀运输问题 （ ６ ２ ） 第四章㊀目标规划 （ ７ ９ ） 第五章㊀整数规划 （ ９ ０ ） 第六章㊀动态规划 （ １ ０ ８ ） 第七章㊀图与网络优化 （ １ ４ ０ ） 第八章㊀网络计划技术 （ １ ７ ４ ） 第九章㊀存储论 （ １ ９ ５ ） 第十章㊀排队论 （ ２ １ １ ） 第十一围和等值线移动方向上犯错； ·图解法的知识点通常出现在选择、 填空、 判断等小题型中！大致分值在 １ ０分以内． 思考题［ １－ １ ］ ㊀（ 留待以后课程讲解） 南京航空航天大学 ２ ０ ０ ４ ， 一、 多项选择 ２ 、 ３ ， 各 ５分 ２ ． 线性规划的最优解可在（ ㊀㊀） Ａ ． 可行集内 Ｃ ． 可行集顶点上 ３ ． 线性规划的可行集可以（ ㊀㊀） Ａ ． 不含有任何可行解 Ｃ ． 恰含有两个可行解 思考题［ １－ ２ ］ ㊀（ 留待以后课程讲解） 南京航空航天大学 ２ ０ ０ ６ ， 第二题， １ ０分 二、 （ １ ０分） 用图解法求解线性规划问题． ｍ ａ ｘ ｚ＝４ ０ ｘ ８ ０ ｘ １＋ ２ ２ ｘ ０ １＋ ２≤ ３ ｘ ｘ ２ ｘ ０ ３ １＋ ２≤ ６ ｓ ． ｔ ． ｘ ４ ２ ２≤ ２ ｘ， １ ｘ ２≥ ０ 要点 ３ ㊀单纯形法原理 ·解的概念与关系 ·单纯形法迭代原理 ［ １ ］ 解的概念与关系 线性规划的标准型为

第讲线性规划与单纯形法演示文稿

第讲线性规划与单纯形法演示文稿
第二十三页，共155页。
1. 线性规划问题的一般形式 由以上两个例子，我们可以归纳出线性规划 问题的一般形式是：
求一组决策变量 xj (j=1 ,2 , … , n)使得
Max(Min)z c1x1 c2 x2 c j x j cn xn ;
• 第一，求一组决策变量(decision variables) xj(j=1 ,2 , … , n)，一般这些变量取值是非负的；
• 第二，确定决策变量可能受到的约束，称为约束条件
（constraints），它们可以用决策变量的线性等式或 不等式来表示； • 第三，在满足约束条件的前提下，使某个函数值 达到最大（如利润、收益等）或最小（如成本、 运价、消费等），这种函数称为目标函数 (objective function)，它是决策变量的线性函数．
其单位产品的利润见表2.2所示：
产品 单位消耗 原料
B1 , B2 ,… , Bn
原料限制 （吨）
A1
a11 a12 … a1n
b1
A2
a21 a22 … a2n
b2
⋮
⋮⋮ ⋮
⋮
Am
am1 am2 … amn
bm
单位利润（万元）
c1 c2 … cn
问该工厂应如何安排生产计划，使得既能充分利用现有原料，又 能使总利润最大？
第五页，共155页。
• 到1947年，美国学者丹捷格（G.B.Dantzig）提
出了线性规划问题的一般解法——单纯形法 ，为线性规划的理论发展奠定了基础，尤其 是1979年哈奇安首次提出求解线性规划问题的 一个多项式算法——椭球算法．1984年卡玛 卡（N . Karmarkar）提出了解线性规划问题的
一个更为有效的一种新的内点算法，使得线性 规划的理论发展趋于成熟．60多年来，随着电 子计算机的发展，线性规划已广泛应用于工业 、农业、商业、交通运输、经济管理和国防等 各个领域，成为现代化管理的有力工具之一．
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

线性规划的一般形式为：
max(min) z c1x1 c2 x2 L cn xn
（1-1）
a11x1 a12 x2 L a1n xn (, )b1
a21
x1
a22
x2
L a2n xn LLLLL
(,
)b2
am1
x1
am2 x2
L
amn xn (, )bm
x1, x2 ,L , xn 0
当z取定值时，方程z=2x1+5x2或x2=－ 2/5x1+z/5表示一条斜率为－2/5的直线 l ， 称为 z的等值线，它在x2轴上的截距为z/5。当l向右 上方平行移动且保持与R有共同部分时，z值不
断上升，由于l的斜率为－2/5，因此当l向右上
方平移的过程中，与R最后的公共点是Q3，z在
x
21
x22
x23
40
x11 x21
x12
x22
20 25
x13
x23
18
xij 0 i 1, 2 j 1, 2, 3
上述三个问题属于同一类型的决策优化问题，它 们具有下列共同特点：
（1）每个行动方案可用一组变量（x1，…，xn）的 值表示，这些变量一般取非负值；
（2）变量的变化要受某些限制，这些限制条件用一 些线性等式或不等式表示；
j1
max(min)z CX AX (, )b
x1 ,L , xn 0
X
0
式中：X=（x1，x2，…，xn）T
C=（c1，c2，…，cn）
b=（b1，b2，…，bm）T
A=（aij）m×n
Pj=（a1j，a2j，…，amj）T
二、图解法
当决策变量个数n=2时，LP问题可以通过在 平面上作图的方法求解，称为图解法。
（1-2） （1-3）
变量x1，x2，…，xn称为决策变量，目标函数中变量系数 cj，称为价值系数，bi称为右端常数，约束条件（1-3）称为非负 约束，（1-2）称为技术约束，系数aij称为技术系数。满足全部约 束条件的变量值（x1，…xn）称为可行解，可行解的集合称为可 行域，记为R；使目标函数取得最大（最小）值的可行解
要消耗A、B、C三种原料，已知单位产品的 原料消耗数量等资料如表1-1所示。
产品ห้องสมุดไป่ตู้
P
Q
原料总量/吨
单位消耗
原料
A
1
2
8
B
5
2
20
C
0
4
12
产品单价
2万元
5万元
解：设P、Q的产量分别为x1，x2，则问题的模
型为
m a x z 2 x1 5 x 2
x1 2 x 2 8
5
x1
2 x2 20 4 x2 12
1．已有一定数量的人力、物力、财力资源，研 究如何充分合理地使用才能使完成的任务量最 大。（如：利润、产值等最大。 maximum）
2．当一项任务量确定以后，研究如何统筹安排， 才能使完成任务耗费的资源量为最小。（如： 成本最小。minimum）
第一节 线性规划的基本概念
一、线性规划的数学模型 【例1-1】 某厂生产P、Q两种产品，主
（x1，…xn）称为最优解。
采用求和符号Σ，线性规划的一般形式可以 简写为：
n
max(min)z cj xj j1
n
aij xj
(,)bi
j1
xj 0
i 1,2,L ,m j 1,2,L , n
用向量形式可表示为： 用矩阵和向量形式
max(min)z CX
表示为：
n
Pjx j (, )b
（1）确定问题的可行域R。 x 1 2 x 2 8
x2 5
4 3 Q4
l2 Q3
5
x1
2 x2 4 x2
20 12
l3 x 1 , x 2 0
2
Q2
1 0
123
Q1 456
l1 x1
图1-1
可行域R是凸多角形OQ1Q2Q3Q4
（2）分析目标函数Z的等值线平行移动与 Z值的关系，确定最优解的位置。
x 1 , x 2 0
【例1-2】 某公司打算利用甲、乙、丙3种原料配置一 种新型保健饮料，已知每千克原料中两种主要保健成 分A，B的含量及原料单价如表1-2所示。
含量
原料
甲
乙
丙
成分
A
20
40
0
B
10
0
20
原料单价（元/千克）
2
2
3
产品质量标准规定每千克饮料中，营养成分A，B 的含量不低于10个与8个单位。如何制定饮料配方， 既满足质量标准又使成本最低？
第一章 线性规划与单纯形法
第一节 第二节 第三节 第四节 第五节
线性规划的基本概念 线性规划的标准形式和解的性质 单纯形法 人工变量法 线性规划应用举例
本章学习目的和要求
通过本章的学习，要求学生掌握线性 规划的图解法，深刻理解单纯形法的解题 思路，熟练掌握其运算步骤，并能在实际 问题中加以运用。
主要研究目的
（3）有一个需要优化的目标，它也是变量的线性函 数。
具备以上三个特点的数学模型称为线性规划 （Linear Programming，简记为LP）。
实际问题中线性的含义
一是严格的比例性，如生产某产品 对资源的消耗量和可获取的利润，同其 生产数量严格成比例。
二是可叠加性，如生产多种产品时 对某项资源的消耗量应等于各产品对该 项资源的消耗量之和。
含量
原料
甲
乙
丙
成分
A
20
40
0
B
10
0
20
原料单价（元/千克）
2
2
3
解：设每千克饮料中原料甲，乙，丙的投入量 分为x1，x2，x3千克，则问题的模型为：
min z 2x1 2x2 3x2
20x1 40x2
10
10 x1
20x3 8
x1
,
x2 ,
x3
0
【例1-3】 A1，A2是两个粮库，每月分别可调出粮 食30吨与40吨，三个粮店B1，B2，B3每月的需求量 分别为20吨，25吨与18吨。粮库与粮店之间每吨粮 食的运费如下表1-3所示（单位：元/吨）。
运费 粮库
粮店
A1 A2
B1
B2
B3
2
3
5
4
6
3
要求安排粮食调运方案，在满足需求的前提下， 使总运费最低。
解：设从粮库Ai到粮店Bj的调运量为xij，i=1，2， j=1，2，3，则问题的模型为：
min z 2 x11 3 x12 5 x13 4 x21 6 x22 3 x23
x11 x12 x13 30
图解法求解的目的： 1.判别线性规划问题的求解结局。 2.在存在最优解的条件下，把问题的最优解找出来。
【例1-4】 求下列问题的最优解。
m ax z 2 x1 5 x2
x1 2 x2 8
5
x
1
2 x2 4 x2
20 12
x 1 , x 2 0
m ax z 2 x1 5 x2