最优化理论与方法第二章2013年9月10日

第二章线性规划第一节线性规划模型第一节线性规划模型

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

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

一.问题提出

问题：工厂应如何安排生产,可获得最大的总利润？解：设变量x1,x2分别,为甲、乙产品的生产件数。根据题意，两种产品的生产受到设备能力（机时数）的限制。对设备A，两种产品生产所占用的机时数不能超过65，3x1

+2x2

≤65；对设备B，两种产品生产所占用的机时数不能超过40，2x1

+x2

≤40；对设备C，两种产品生产所占用的机时数不能超过75，3x2≤75；另外，产品数不可能为负，即x1,x2≥0。同时，目标是获取最大利润。总利润：f=1500x1x2。把目标函数和约束条件放在一起，可以建立如下的线性规划模型：目标函数Maxf=1500x1x2

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

这是一个典型的利润最大化的生产计划问题。其中，“s.t.”是“subjectto”的缩写，表示“满足于……”。模型的含义是：在给定条件限制下，求使目标函数f达到最大的x1,x2

的取值。二.数学模型线性规划问题的标准形线性规划问题的几种表示形式和式标准形向量式标准形其中矩阵式标准形三.非标准形转化标准形目标函数为max第i个约束的bi

为负值第i个约束为型第i个约束为型若xj0，令

xj=-xj

，代入，则有xj

0若xj自由变量，令

xj=xj-xj，xj

0，xj0，代入非标准形例2:将下述线性规划问题化为标准形四.图解法例3目标函数等值线

由图可知：在点Q2(4,2)，目标函数值达到最大值14几种可能出现的情况（1）唯一最优解（2）无穷多个最优解（3）无有限最优解（无界解）（4）无可行解无穷多个最优解目标函数maxf=2x1+4x2

无有限最优解如果在上例模型中增加一个约束条件:该问题的可行域为空集，即无可行解

当存在矛盾的约束条件时，为无可行域。无可行解

结论：两个变量的线性规划问题如果存在最优解，则一定存在可行域的顶点为最优解。第二节单纯形法一.线性规划的基本概念在(LP)标准形中，若B是A中一个可逆子阵,|B|0，则B构成该标准形的一个基，B

由A中m个线性无关列向量构成.B=（

Pj1,Pj2,…,Pjm)Pj1,Pj2,…,Pjm

称为基向量，其余的列向量称为非基向量与基向量对应的变量称为基变量，与非基向量对应的变量称为非基变量

若B=（Pj1,Pj2,…,Pjm)是（LP）的基，XB对应基变量，则BXB=b有唯一解XB=B-1b

在约束条件AX=b

中，令所有非基变量为0，求出的解叫基本解，简称基解。可行解：满足约束条件和非负条件的解

X

称为可行解。基本可行解：非负的基本解。基本可行解的非零分量个数<

m

时，称为退化基解。例1求解线性规划问题的基本思路从线性规划的图解法已得出两个直观结论:1.线性规划问题的可行域为凸集.2.两个变量的线性规划问题如果存在最优一定可以在其可行域的顶点上找到最优解.从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。如可能，从可行域中求出具有更优目标函数值的另一个基础可行解（另一个顶点),以改进初始解。继续寻找更优的基础可行解，进一步改进目标函数值。当某一个基础可行解不能再改善时，该解就是最优解。单纯形法需解决的三个问题:(1)如何寻找一个初始的可行基(2)如何判定当前可行基是否为最优基(3)如何寻找下一个可行基,使目标函数值下降二.解的性质定理1:(LP)问题的可行集D={X|AX=b,X0}是凸集

定理2:(LP)问题中,线性方程组AX=b

的一个解为基解中的非零分量线性无关所对应的列向量证明:.....

定理3:(LP)问题若存在可行解,则一定存在基可行解证明:.....

定理4:(LP)问题若存在最优解,则一定存在基可行解为最优解证明:设x*是(LP)的最优解,若x*是基可行解,命题得证,若x*不是基可行解,类似定理3方法,作新