文档介绍：第一章线性规划问题
线性规划是运筹学的一个大分支—数学规划
的组成部分。
数学规划分为静态规划和动态规划;
静态规划又分为线性规划和非线性规划。
静态数学规划一般来说是研究一个n元实函
数(称为目标函数)在一组等式或不等式约束
条件下的极值问题。如果目标函数和约束条件
都是线性的,则称为线性规划;否则,称之为
非线性规划。
一、线性规划问题的三要素
——问题需要求解的未知量。它是通过模型计算来确定的决策因素。
——目标的数学表达式。目标函数是求变量的线性函数的极大值和极小值这样一个极值问题。
——实现目标的制约因素。它包括:生产资源的限制(客观约束条件)、生产数量、质量要求的限制(主观约束条件)、特定技术要求和非负限制。
二、线性规划问题的基本结构
Min Z=10x1+20x2
. x1+x2≥10
3x1+x2≥15
x1+6x2≥15
x1≥0 , x2≥0
约束条件
目标函数
非负限制
三、线性规划模型的一般形式(极大值型)
Max Z=c1x1+c2x2+c3x3+…+cnxn
a11x1+a12x2+…+a1nxn≤ b1 (1)
a21x1+a22x2+…+a2nxn≤ b2 (2)
……
am1x1+am2x2+…+amnxn ≤ bm (m)
x1 ,x2 ,…xn≥0
其简缩形式为
线性规划模型的一般形式(极小值型)
Min Z=c1x1+c2x2+c3x3+…+cnxn
a11x1+a12x2+…+a1nxn ≥ b1 (1)
a21x1+a22x2+…+a2nxn ≥ b2 (2)
……
am1x1+am2x2+…+amnxn ≥ bm (m)
x1 ,x2 ,…xn≥0
四、线性规划问题的标准形式
结构:
目标函数统一成求最小值;约束条件归
结为一组线性方程组和非负性限制。
注意点:
目标函数是求最大值,要化为求最小值;
约束条件是不等式,要化为等式和非负性
限制。
标准形式:
若使用向量和矩阵记号,则标准形式可写为:此标准形式也称为LP。
其中:C=(c1,c2,……cn)