（一）线性规划概念：线性规划是一种优化方法，具有以下共同特点，（1）每一个问题都可用一组变量来表示，这组变量的每一组定值就表示一个具体方案，通常要求这些变量是非负的。（2）存在一定的约束条件，这些约束条件都可用变量的线性等式或不等式来表示。（3）都有一个目标，这个目标总可以表示为一组变量的线性函数，并按照问题的要求，求其最大值或最小值。 （二）日常应用的线性规划数学模型。
（1）任务安排问题。例：某工厂用甲乙两种原料生产A,B,C三种产品，已知生产A种产品需甲种原料3吨，乙种原料1吨，生产一吨B种产品需甲原料1吨，乙原料2吨，生产一吨C种产品需甲原料2吨，A,B,C利润为3000,2000,5000元/吨。该工厂现有20吨甲原料，60吨乙原料，问现有条件下如何组织生产才能获得最大利润。 产品 原料 | A | B | C | 原料总量 |
甲 | 3 | 1 | 2 | 20 |
乙 | 1 | 2 | 0 | 60 |
利润 | 3000 | 2000 | 5000 | |
| | | | |
分析：（1）变量为生产A:X1吨，B:X2吨,C:X3吨.
(2)目标求生产ABC各多少吨利润最大。Maxs=3000x1+2000x2+5000x3
（3）约束条件：所用原料不能超出库存量，变量为非负。
数学模型如下：
Maxs=3000x1+2000x2+5000x3
3X1+X2+2X3<=20
X1+2X2<=60
X1,2.>=0
(2)配料问题。某铸造厂生产铸件至少需2个单位的铅，2.4个单位铜，3个单位铝，现有四种合金可供选择，他们每个单位成分如下表，问每种合金选用多少才能费用最省。
成分 | A | b | c | d |
铅 | 0.1 | 0.2 | 0.15 | 0.15 |
铜， | 0.1 | 0.15 | 0.2 | 0.05 |
沈阳师范大学商学院铝 | 0.2 | 0.1 | 0.3 | 0.4 |
价格 | 10 | 15 | 30 | 25 |
| | | | |
(1)变量，设选用合金ABCD,各X1.X2,X3,X4
(2)目标，求四种合金成本最低的最优数量。
(3)限制条件，达到工艺要求，变量不为负。
(4)模型如下：
MINS=10X1+15X2+30X3+25X4
0.1X1+0.2X2+0.15X3+0.15X4>=2
0.1X1+0.15X2+0.2X3+0.05X4>=2.4
0.2X1+0.1X2+0.3X3+0.4X4>=3
X1,X2,X3.X4>=0
（3）运输问题。设有两个煤场B1,B2,每月进煤量分别为60吨和100吨，他们负责供应A1,A2,A3三个居民区用煤，这三个居民区每月用煤量分别为45吨，75吨合40吨，煤场BI离
这三个居民区分别为10公里5公里和6公里，B2为4公里8公里和12公里。问两个煤场如何分配供煤任务，才能使运输的吨公里数最少？
（1）变量，设送煤B1—A1,A2,A3为X11,X12,X13,B2--A1,A2,A3为X21,X22,X23
(2)目标，公里乘变量最小。
（3）约束条件，煤场进煤量，用户需求量。
| A1 | A2 | A3 | 进煤量 |
B1 | X11 | X12 | X13 | 60 |
B2 | X21 | X22 | X23 | 100 |
| 45 | 75 | 40 | 160 |
| | | | |
数学模型如下：
MINS=10X11+5X12+6X13+4X21+8X22+12X23
X11+X12+X13=60
X21+X22+X23=100
X11+X21=45
X12+X22=75
X13+X23=40
X11,X12,X13,X21,X22,X23.>=0
(5)合理下料问题。用长度300厘米的条料，截成长度分别为90厘米和70厘米的两种坯料，要求共截出90厘米坯料9000根，70厘米的坯料18000根，问怎样截法才使用料最省。
| 70 | 90 | 余料 |
A | 3 | 1 | 0 |
B | 1 | 2 | 50 |
C | 0 | 3 | 30 |
D | 4 | 0 | 20 |
| | | |
（1）变量：设A,B,C,D分别为X1,X2,X3,X4.
(2)目标，求四种方法余料的最小值。
（3）约束条件，90厘米坯料9000根，70厘米的坯料18000根基因甲基化
数学模型如下：
MINS=50X2+30X3+20X4
3X1+X2+4X4=18000
X1+2X2+3X3=9000
（三）线性规划的数学通用模型。
MAXS=C1X1+C2X2+,,,,,,,+CnXn
A11X1+A12X2+A1nXn<=B1
A21X1+A22X2+A2nXn<=B2
只拣儿童多处行教学设计
Am1X1+Am2X2+AmnXn<=Bn
Xn>=0
或
MINS=C1X1+C2X2+,,,,,,,+CnXn
A11X1+A12X2+A1nXn>=B1
A21X1+A22X2+A2nXn>=B2
Am1X1+Am2X2+AmnXn>=Bn
Xn>=0
（四）我们还可以把任何形式的线性规划转化为标准形式。
（1）标准形式的特点（1）目标函数求最大值。（2）所有约束条件都用等式来表示。（3）约束常数要求非负。
标准形式为
MAXS=C1X1+C2X2+,,,,,,,+CnXn
A11X1+A12X2+A1nXn=B1
A21X1+A22X2+A2nXn=B2
Am1X1+Am2X2+AmnXn=Bn
Xn>=0
Bn.>=0
（五）非标准转化为标准的几种方法
（1）如果目标函数是MINS=CX,那么由MINS=-MAXS可知，令$=-S,可将问题转化为求MAX$=-CX.
（2）当约束方程是<=约束时，如第i个方程为Ai1X1+ Ai2X2+ AinXn<=Bi
可在上式<=号的左边加上一个非负新变量Xn+i>=0使得揠苗助长教学实录
Ai1X1+ Ai2X2+ AinXn+Xn+i=Bi其中Xn+i为松弛变量。
当约束方程是>=约束时，如第j个方程为Ai1X1+ Ai2X2+ AjnXn>=Bj
可在上式>=号的左边减去一个非负新变量Xn+j>=0使得
Ai1X1+ Ai2X2+ AinXn-Xn+j=Bi其中Xn+j为松弛变量。
(3)当某一个变量Xi无非负约束时，可以用两个非负新变量Xn+i ,Xn+j的差替换，并将Xi= Xn+i -Xn+代入原问题的数学模型中.
(4)当约束常数Bi<0时，只需在第个约束方程的左右两端各乘以-1，便可得-Bi>0
例如：把MINS=-3X1+X2+5X3-2X4
X1-4X2+3X3+2X4>=6
-2X1-X2+X4=-4
2X1+X2-3X3<=3
Xj>=0(j=1,2,3,4)
解：首先检查变量的非负约束情况，原问题中的所有变量都有非负约束即Xj>=0(j=1,2,3,4)，转入下一步。我们将目标函数转化为MAX令$=-S得MAX$=3X1-X2-5X3+2X4
再对含有不等号的约束条件，引入松弛变量X5>=0,X6>=0,使约束条件变为
X1-4X2+3X3+2X4-X5=6
-2X1-X2+X4=-4
2X1+X2-3X3+X6=3
Xj>=0(j=1,2,3,4)
最后再含小于零的约束常数-4所在的方程两边同乘以-1，使之变成
2X1+X2-X4=4
这样我们得到了原问题的标准形式
MAX$=3X1-X2-5X3+2X4
X1-4X2+3X3+2X4-X5=6
kugoo2013下载2X1+X2-3X3+X6=3
陈宜国2X1+X2-X4=4
Xj>=0(j=1,2,3,4)
（六）
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议