优化与策略教学课件作者李卫国第1章优化方法之线性规划篇

第1章 优化方法之线性规划篇,1. 1 线性规划问题与数学模型 1. 2 线性规划的基本性质与基本定理,返回,1. 1 线性规划问题与数学模型,max z = 1 200x1+ 1 000x2，称为问题的目标函数。每天安排生产使产值最大是问题的目标。x1 , x2不能取负值且只能取整数值。max是maximize的缩写，s.t.是Subject to的缩写，意为“满足”或“受约束于”。变量x1，x2被称为决策变量。给定x1，x2的一组值，称为确定一个决策。使目标函数z的值达到最大的决策称为最优解或最优决策。 为了研究算法的方便，可在每个线性不等式约束条件中减去一个新的非负变量(称为剩余变量)或加上一个新的非负变量(称为松弛变量)，将不等式约束化为等式约束，也就是说，把约束条件变为线性方程组与变量非负约束，对于n个变量x1 , x2 ，xn的线性规划问题，其数学模型的形式如下:,返回,1. 2线性规划的基本性质与基本定理,定义1.2.1凸集 X为n维欧氏空间的集合。若对于X中任意两个不同的点x1与x2， x1x2 ，均有点 ，对任意的a0, 0, a + = 1成立，则称X为凸集。点表示x(1)与x(2)连线上的点，它们构成线段x(1)x(2)。对于上述的a , ，称ax(1)+ x(2)为x(1)与x(2)的凸组合· 线段AB, DABC，平面上的正四边形与多边形以及圆等都是凸集。不包含边界点的凸集称为开凸集，否则为闭凸集。 定义1.2.2 一个集合X，若xX，则axX (a0)也成立，则称X为一个锥。 考察两个具体的Ox1 x2平面上的约束集合S1与S2及其几何特性(见图1.2. 1)。,下一页,返回,1. 2线性规划的基本性质与基本定理,定义1.2.3 若x是凸集S的点，在S中不存在不同的两点到x(1) ，x(2) ，使得: 成立，则称x为该凸集的极点。 凸集s2(见图1.2.2),上一页,返回,图1. 2. 1凸集S1,返回,图1.2.2 凸集S2,返回,谢谢观赏,