- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
添加松弛变量x3,x4,x5,则标准型为
max Z 50x1 100x2 0x3 0x4 0x5
x1 x2 x3
300
s.t.2x2x1 x2
x4 400 x5 250
x1, x2, x3, x4, x5 0
Operation Research
第二讲
该解是否为最优解
Y 结束
N 确定入基变量 和出基变量
进行基变换， 求出基可行解
Operation Research
第二讲
单纯形法的基本原理（2）
实例
工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产 品所需的设备台时及A、B两种原材料的消耗，以及资源的限制， 如下表所示。
每生产一单位产品I可获利50元，每生产一单位产品Ⅱ可获利100 元，问工厂应如何安排生产获利最多?
第二讲
线性规划问题的几何性质（1）
定义
凸集、顶点
定理
1.线性规划问题存在可行域，则其可行域是凸 集。
2.线性规划问题的基可行解对应于可行域的顶 点。
3.若可行域有界，线性规划问题的目标函数一 定可以在其可行域的顶点上达到最优。
Operation Research
第二讲
线性规划问题的几何性质（2）
形区域。
任何两个凸多边形区域的集合仍为凸多边形区域。
顶点
设x为凸多边形区域中的一点，若x不能用凸多边形区域种不同两点的 线性组合来表示，则称x为凸多边形区域的一个顶点。
Operation Research
第二讲
线性规划问题的图解法（2）
问题实例
max Z 6x1 4x2
2 s.t.4
Operation Research
第二讲
线性规划模型的几种形式（3）
一般形式转化为标准型
若原模型中的目标函数实现最小化，即minZ=CX，则令Z/=-Z，可 得到maxZ/=-CX，这就同标准型的目标函数形式相一致；
若原模型中的约束条件为不等式，两种情况
原约束条件左端≥右端，则添加剩余变量，约束条件化为 原约束条件左端-剩余变量=右端 (剩余变量≥0)
Operation Research
几何概念
约束直线 约束半平面 约束半平面的交集： 凸多边形 约束直线的交点 可行域的顶点 目标函数等值线： 一组平行线
代数概念
第二讲
满足一个等式约束的解 满足一个不等式约束的解 满足一组不等式约束的解
基解
基可行解
目标函数值等于一个常 数的解
Operation Research
满足非负条件的基解，成为基可行解。 对应于基可行解的基，称为可行基。
讨论：一个线性规划问题最多有多少个基可行解？
实例
max Z 6x1 4x2
2x1 3x2 100 s.t.4x1 2x2 120
x1, x2 0
Operation Research
s.t.a21x1a22 x2a2n xn b2 am1 x1 am2 x2 amn xn bm x1, x2 ,, xn 0
max Z CX
s.t.
n j 1
Pj
x
j
b
x
j
0
j 1,2,, n
第二讲
单纯形法的基本原理（5）
4.最优解检验
检验方法：将基变量用非基变量线性表示，然后带入目标函数， 如果非基变量前面的某个系数大于零，说明仍没有达到最优解； 否则，该解为问题最优解。
x1 x2 x3 300 x3 300 x1 x2 2x1 x2 x4 400 x4 400 2x1 x2 x2 x5 250 x5 250 x2
Operation Research
第二讲
单纯形法的基本原理（3）
1.建立模型
设决策变量xj （j=1,2)表示生产成品j的数量，则问题可归结为
max Z 50x1 100x2
x1 x2 300 s.t.2x2x12x520 400
x1, x2 0
2.转化为标准型
目标函数 约 束 条 件
=
右边常数
行列式≠0
基
=
Operation Research
第二讲
线性规划问题解的性质（3）
基解、基可行解、可行基
设XB=（x1,x2,…,xm)为基B所对应的基变量,令非基变量 xm+1,xm+2,…,xn=0，可以求出一个解XB=（x1,x2,…,xm,0,0,…,0)，该 解的称为基B的基解。
第二讲
线性规划问题的图解法（4）
无可行解区域
用图解法求解 max Z x1 x2
x1 x2 10 s.t.2x1 x2 30
x1, x2 0
图解法的几点讨论
(1)若线性规划问题有可行解．则可行解区域是一个凸多边形，它可能是 有界的；也可能是无界的。
s.t.a21x1a22 x2a2n xn , b2 am1x1 am2 x2 amn xn , bm
x1, x2 ,, xn 0
Operation Research
第二讲
线性规划模型的几种形式（2）
线性规划问题图解法的几种特殊情况
有多重最优解
将上例中目标函数由Z=6x1+4x2 变为Z=4x1+6x2 后，再用图解法进行求 解
可行解区域无界
用图解法求解 max Z x1 x2
2x1 x2 4 s.t.x1 x2 2
x1, x2 0
Operation Research
x1 x1
3x2 2x2
100 120
x1, x2 0
求解步骤
求满足约束条件的可行域
建立直角坐标系，以x1为横轴，x2为纵轴； 确定非负约束x1 ≥0， x2 ≥0的各点集合，即第一象限； 确定满足约束条件2x1+3x2 ≤100的各点集合。在坐标系中画出直线
2x1+3x2 =100，该直线为边界的左下方的半平面即为满足约束条件 2x1+3x2 ≤100的各点集合； 同理，确定其他各约束条件的点集合；
点集合的交叉区域即为该问题的可行域。
Operation Research
第二讲
线性规划问题的图解法（3）
从可行域中找出目标函数的最优解
画目标函数的等值线； 平移等值线，在可行解区域内找到目标函数的最优解。
原约束条件左端≤右端，则添加松弛变量，约束条件化为 原约束条件左端+松弛变量=右端 (松弛变量≥0) 在原模型中引入剩余变量(或松弛变量)后，使问题的变量维数增加，目
标函数并不发生改变，即在目标函数中，附加变量的系数为0。
若原模型中变量xk自由变量，即xk ∈(∞,-∞)，则令 xk = x/k – x//k，其中x/k，x//k ≥0，目标函数相应变化。
运筹学课程
Operation Research
第二讲
线性规划问题的图解法（1）
相关概念
可行解
满足线性规划问题约束条件的解，都称为该线性规划问题的可行解， 所有可行解集合称为可行解集（或可行域）。
最优解
是目标函数达到最优值（最大值或最小值）的可行解，称为最优解。
凸多边形区域
设x1,x2为多边形区域中的两点，若两点连线上的任意一点，即 ax1+（1-a)x2,(0≤a≤1)仍属于该多边形区域，则该多边形区域为凸多边
Operation Research
第二讲
线性规划模型的几种形式（4）
实例
Operation Research
第二讲
线性规划模型的几种形式（5）
标准型的几种表示形式
向量形式
max Z c1x1 c2 x2 cn xn a11x1 a12 x2 a1n xn b1
(2)若线性规划问题有最优解，则最优解可能是唯一的；也可能是无穷多 个。如果是唯一的，这个最优解一定在该凸多边形的某个顶点上；如果 是无穷多个，那末这些最优解一定是凸多边形的一条边界（包括此边界 的两个端点）。总之，如果线性规划问题有最优解，则这个最优解一定 可以在凸多边形的顶点达到。
(3)若线性规划问题有可行解，但是没有有限最优解。这时凸多边形是无 界的。
单纯形法的基本原理（4）
3.确定初始基，并求出基解
系数矩阵为
x3 x4 x5
1 0 0 A 0 1 0
0 0 1
x1 x2
1 1 2 1 0 1
则可令x3,x4,x5位初始基变量，则基解为(0,0,300,400,250) 是基可行解
第二讲
Operation Research
称为线性规划问题的可行解；在可行解中，目标函数达到最大值的 解，称为最优解。
因此，线性规划问题可行解的求取可转化为求解有约束条件组成的非齐次线 性方程组。
Operation Research
第二讲
线性规划问题解的性质（2）
基、基变量、非基变量
设A是约束条件方程组的m*n为系数矩阵，其秩为m，B是矩阵A中 m*m阶非奇异子矩阵（|B|≠0)，则称B为线性规划问题的一个基。 与基对应的决策变量称为基变量，否则称为非基变量。
am1 x1 am2 x2 amn xn bm x1, x2 ,, xn 0
两端乘以“-1” 决策变量一定是非负。
n
可见简写为： max Z c j x j j 1
s.t.
