线性规划1

(1-8)
例 1.5 （汽油混合问题） 一种汽油的特性可用两个指标描述：其点火性用“辛烷数” 描述，其挥发性用“蒸汽压力”描述，某炼油厂有四种标准汽油，设其标号分别为 1，2， 3，4，其特性及库存量见表 1.5，将上述标准汽油适量混合，可得到两种飞机汽油，其标 号分别为 1，2，这两种飞机汽油的性能指标及产量需求见表 1.6，问应如何根据库存情况 适量混合各种标准汽油，使既满足飞机汽油的性能指标，而产量又为最高。
注：前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了 12 个变量，10 个约束条件。
表 1.2 资源 住宅体系 砖混住宅 壁板住宅 大模住宅 资源限量 造价 (元/m2) 105 135 120 110000 (千元 钢材 (公斤/m2) 12 30 25 20000 (吨) 例 1.2 的数据表 水泥 (公斤/m2) 110 190 180 150000 (吨) 砖 (块/m2) 210 —— —— 147000 (千块) 人工 (工日/m2) 4.5 3.0 3.5 4000 (千工日)
3．线性规划模型的一般形式 以 MAX 型、≤约束为例 决策变量： x1 ,
(1-4)
, xn
目标函数： Maxz = c1 x1 +
+ cn x n
⎧a11 x1 + + a1n x n ≤ b1 ⎪ ⎪ 约束条件： s.t.⎨ ⎪a m1 x1 + + a mn x n ≤ bm ⎪ ⎩ x1 , , x n ≥ 0
2
Maxz = x1 + x 2 + x3 ⎧0.105 x1 + 0.135 x 2 + 0.120 x3 ≤ 110000 ⎪0.012 x1 + 0.030 x 2 + 0.025 x3 ≤ 20000 数学模型为: ⎪0.110 x1 + 0.190 x 2 + 0.180 x 3 ≤ 150000 (1-3) s.t ⎨ 0.210 x ≤ 147000 ⎪0.00451 x + 0.003x 2 + 0.0035 x 3 ≤ 4000 ⎪x , x , x 1 ≥ 0 ⎩ 1 2 3

所有可行解构成的集合即为可行解集。
最优解（optimal solution）
使目标函数取得最大值（或最小值）的可行解 称为最优解。
LP一般形式
一组决策变量
满足这三个要素的 问题就是线性规划 问题
每个问题都用一组决策变量表示某个方案，通 常要求这些未知数取值是非负的。
一个线性目标函数
max s CX s.t. AX b X 0
一般称C为价值向量，b为资源向量，A为技术系数矩阵
关于标准型要把握几点
决策变量大于等于0 约束条件均为等式 约束条件右端项bi大于等于0 目标函数为求max
如何将一般问题化为标准型？
若目标函数是求最小 值 Min z = CX 令 z’= - z, 则 Max z’= - CX
该问题可行域为空集， 即无可行解，也不存在 最优解
第3部分 线性规划的标准型(SLP)
线性规划标准型(SLP)
写成缩小形式或矩阵形式
max s c j x j
j 1
n
n aij x j bi , i 1,2,, m s.t. j 1 x 0, j 1,2,, n j
产品A 9 4 3 产品B 4 5 10 资源限额
360工时 200台时 300公斤
70
120
问：如何安排生产使该厂获利最大？
解：设x1,x2分别表示A、B两种产品的产量 那么其总利润为： z=70x1+120x2 并且由于资源限制，应有： 9x1＋4x2≤360
4x1+5x2≤200
3x1+10x2≤300 我们的目标是使z最大
可加性假定：每个决策变量对目标函数和约束方程的
影响独立于其他变量的，目标函数值是每个决策变量对 目标函数贡献的总和

凸集的数学定义:设K为n维欧氏空间的一个点集，若K中任意两个 点X1和X2连线上的所有点都属于K，即“X =αX1+(1-α) X2 ∈ K(0≤a ≤ 1)”，则称K为凸集。设X(x1，x2，…，xn)，X1(u1， u2，...，un)，X2(v1，v2，…，vn)，如图1一5所示，“X =αX1+(1α) X2 ∈ K(0≤a ≤ 1)”的证明思路如下:
下一页 返回
图解法步骤：
（1）建立坐标系； （2）将约束条件在图上表示； （3）确立满足约束条件的解的范围； （4）绘制出目标函数的图形 （5）确定最优解
用图解法求解下列线性规划问题
max z 2x1 3x2
4x1 0x2 16
s.t
10xx11
4x2 2x2
12 8
x1, x2 0
1. 1.1问题举例
(1)生产计划问题。 生产计划问题是典型的已知资源求利润最大化的问题，对于此类
问题通常有三个假设:①在某一计划期内对生产做出的安排;②生产 过程的损失忽略不计;③市场需求无限制，即假设生产的产品全部 卖出。
下一页 返回
1.一般线性规划问题的数学模型
例1 用一块连长为a的正方形铁皮做一个容 器，应如何裁剪，使做成的窗口的容积为最 大？
解：设 x1, x2分别表示从A,B两处采购的原油量（单
位：吨），则所有的采购方案的最优方案为：
min z 200x1 290x2
0.15x1 0.50x2 150000
s.t
0.20x1 0.50x1
0.30x2 0.15x2
120000 120000
x1 0, x2 0
1. 1线性规划问题与模型
也可以写成模型(1-6)和模型(1-7)的形式，其中模型(1-7)较为常用。

执笔：李海峰审核人：李海东授课时间：班级：姓名：小组：
教学目标：了解二元一次不等式的几何意义和什么是边界，会用二元一次不等式组表示平面区域
知识与技能：会用二元一次不等式组表示平面区域
过程与方法：经历从实际情境中抽象出二元一次不等式组的过程，提高数学建模的能力
情感态度与价值观：学会用分类讨论的思想方法解决问题。
教学重点：用二元一次不等式（组）表示平面区域
教学难点：用二元一次不等式（组）表示平面区域
【知识链接】
复习1：一元二次不等式的定义___________二元一次不等式定义________
二元一次不等式组的定义_____________________
复习2：解下列不等式：
（1） ；（2） .
【学习过程】
类似的：二元一次不等式x-y>6表示直线x-y=6右下方的区域；如图:
直线叫做这两个区域的边界
结论：
1.二元一次不等式 在平面直角坐标系中表示直线 某一侧所有点组成的平面区域.（虚线表示区域不包括边界直线）
2.不等式中仅 或 不包括；但含“ ”“ ”括；同侧同号，异侧异号.
※典型例题
例1画出不等式 表示的平面区域.
※学习探究
探究1：一元一次不等式（组）的解集可以表示为数轴上的区间，例如， 的解集为.那么，在直角坐标系内，二元一次不等式（组）的解集表示什么图形呢？
探究2：你能研究：二元一次不等式 的解集所表示的图形吗？（怎样分析和定边界？）
从特殊到一般：
先研究具体的二元一次不等式 的解集所表示的图形.
如图：在平面直角坐标系内，x-y=6表示一条直线.
归纳1：画二元一次不等式表示的平面区域常采用“直线定界，特殊点定域”的方法.特殊地，当 时，常把原点作为此特殊点.