文档介绍：. 问题中变量个数多于 2 时,图解法失效
即使是计算机求解,首先也要有有效算法,然后才可能利用程序去实现它
单形法,是 . 问题算法之基础。本质上,它是代数方法,可以用线性代数的理论证明方法的合法性,清楚地说明算法背后的“为什么”。由于课时限制我们不准备这么做,将把有限的精力和时间浅尝辄止:了解算法本身的使用,并不证明“为什么”。
第五章 . 单纯形法
凌晨:
凌晨:
一、例子
假设 HT 公司正在计划下周两种计算机产品的生产
台式机/台:利润:50 装配工时:3 占地:8
便携机台/:利润:40 装配工时:5 占地:5
资源限制:
下周最大可用工时:150
便携式显示器目前只有:20 pcs
仓储可用面积:300 平方英尺
若以最大化利润为目标,如何安排生产?
第一节单形法的代数说明
凌晨:
凌晨:
二、模型及其标准形
设:x1 -计划的台式机数量 x2 - 计划的便携机数量
max 50x1 + 40x2
.
3x1 + 5x2 150 工时约束
x2 20 便携机显示器约束
8x1 + 5x2 300 仓储面积约束
x1,x2 0 非负约束
为了获得标准形,分别为约束式引入松弛变量:s i。
第一节单形法的代数说明
凌晨:
凌晨:
二、模型及其标准形
max 50x1 + 40x2 + 0s1 + 0s2 + 0s3 ()
.
3x1 + 5x2 + s1 = 150 ()
x2 + s2 = 20 ()
8x1 + 5x2 + s3 = 300 ()
x1,x2,s1,s2,s3 0
即为模型之标准形。除非负约束之外,() -() 刚好构成一个 5个变量、3 个方程的线性方程组。
第一节单形法的代数说明
凌晨:
凌晨:
三、从代数观点思考标准形--解题思路
1、将() -() 线性方程组表示为增广阵:( A B ),则其一般解法是通过初等变换(保证既化简又同解):
其中 B’含自由变量
可能有无穷多个解
2、因为不满足非负要求的线性方程组的解是非可行解,即使得到也要去除并重新求解(换基)
3、从满足非负约束的线性方程组的解中找出(迭代方法)使得目标函数取值最好的解,即为最优解。
第一节单形法的代数说明
凌晨:
凌晨:
四、基解(basic solution)
1、定义:在 m 个方程、n 个变量之线性方程组中若令 n-m 个变量为 0,然后求出的线性方程组解称为基解,其中被令成 0 的变量称为非基变量,没有被令成 0 的变量称为基变量
2、上例中,m = 3,n = 5,令(实际上可以任选 2 个):x2 = 0,s1 = 0,代入方程组易得:
x1 = 50,x2 = 0,s1 = 0,s2 = 20,s3 = -100
即为 . 问题一个基解,不过,非可行解!
第一节单形法的代数说明
凌晨:
凌晨:
五、基可行解
1、定义:满足非负要求的基解称为基可行解
很明显,我们要的是基可行解,是最优的基可行解
2、上例中,若令 x1 = 0,x2 = 0,则可得基解:
x1 = 0,x2 = 0,s1 = 150,s2 = 20,s3 = 300
正是一个基可行解!称之为初始基可行解
3、基可行解的几何解释
作出本 . 问题的可行区域,可见: x1 = 0,x2 = 0 正是可行域的端点(1)!这不是偶然的,我们有一般的结论。
第一节单形法的代数说明
凌晨:
凌晨:
五、基可行解
4、可行域及其初始基可行解的图形表示:
端点(1)即为初始基可行解。
第二节单形法用于最简单例子
凌晨:
凌晨:
(1)
(2)
(3)
(4)
(5)
五、基可行解
5、定理一
. 问题中,约束线性方程组的基可行解就是其可行域的端点,反之亦然
6、定理二
. 问题最优解必是基可行解中的一个
7、单形法的迭代
从任意一个初始基可行解出发(只要令 n-m 个变量为零即可),在不断改善目标函数前提下,设法将其变化(迭代)成另一个基可行解,直至求出最优的。
第一节单形法的代数说明
凌晨:
凌晨:
一、. 的表格形式
1、表格形式的意义
将 . 模型化成表格形式,可为单形法迅速提供一个初始基可行解!然后才开始迭代过程
2、例子
max 50x1 + 40x2 + 0s1 + 0s2 + 0s3 ()
.
3x1 + 5x2 + s1 = 150 ()
x2 + s2 = 20 ()
8x1 + 5x2 + s3 = 300 ()