文档介绍：上堂课的主要内容:
1、线性规划的标准形式
2. 线性规划问题的矩阵表达式:
3、线性规划的解
(1)可行解:
(2)可行域:
(LP)的全体可行解构成的集合称为可行域
(3)最优解及最优值:
设S是(LP)的可行域
不唯一
唯一
(4)若对任意大的M>0,都存在可行解X,
,则称该线性规划问题无界
其目标函数值
4、图解法的基本步骤:
(一般是一个凸多边形)
注意:若是求目标函数的最小值,
目标函数直线向下移动
在(LP)问题中,A的任意一个m×m阶
的非奇异子方阵B(即|B|≠0)称为
(LP)问题的一个基
设r(A)=m<n
有限个
不妨设A的前m列构成A的一个基
A=(B,N),
5、基本概念
由于B 可逆
基本解
,A=(B,N),
可行基
基本可行解
退化基本可行解:基本可行解中,存在取0值的基变量
非退化基本可行解:基本可行解中,基变量的取值均>0
对应的基称为退化基
对应的基称为非退化基
线性规划问题
:存在退化基
:所有基均非退化
设X为基本可行解,
则X的n个分量中,最多有个分量>0
m
结论:
(LP)问题有可行解,则可行域是一个凸多边形
(LP)问题有最优解,则最优解一定可以在凸多边
形的某个顶点达到

若(LP)问题有最优解,则最优解一定可以在某个
基本可行解达到
找最优解可从一个基本可行解入手,通过某种方法,调整基变量,转到另一个基本可行解,并使目标函数
值不断增大,通过有限次的迭代就能找到最优解
单纯形法
§
单纯形法的基本思路:
1、找出一个可行基,并得到一个基本可行解
2、检验该基本可行解是否是最优解,即目标函数值
是否最大,或看看是否存在目标函数值比它大的
基本可行解
3、换一个目标函数值比他大的基本可行解
4、重复以上步骤,直至找不到更好的基本可行解