当前位置：文档之家 › 线性规划实验举例

线性规划实验举例

  • 格式：doc
  • 大小：143.50 KB
  • 文档页数：5

下载文档原格式

  / 5

合集下载

工程优化 第五章 线性规划2

工程优化 第五章 线性规划2
min f x1 3x2 x3 s.t. x2 2 x3 x4 4 x1 2 x2 x3 x4 x5 4 3x1 3x3 x4 4 x j 0, j 1, ,5
解：只需引入两个人工变量 x6 和 x7 ，相应的辅 助线性规划问题（ALP）如下：
min cT x MeT x s.t. Ax x b x 0,xα 0
（2 ）
其中 A 是 m n 矩阵， b 0, M 0 很大， e 是分量全为 1 的 m 维列向量。
0 ，用单纯形法求解（2） 显然， （2）有初始可行解 ， b
其结果必为下列几种情形之一：
两阶段法的第二阶段。 综上所述，对不具有明显可行基的（ LP ） ，可 先用单纯形法求解辅助性性规划问题（ALP） ，解 的结果或者说明（LP）无可行解，或者找到（LP） 的一个基本可行解， 然后再从这个基本可行解开始 应用单纯形法求解（LP） ，此即两阶段法的第二阶 段。将目标函数 g 用非基变量表示如下：
1/3
-7/2
-1
0
-4/3
21/6
0
0
1/3
7
f
-3/2 -7/2
x1
x2 0 1
x3 1 0
x4 -1/8 1/4
x5 -1/8 -3/4
x6 1/8 -1/4
x7 1/8 3/4 3/8 1/4 0
x3
x2 g
1/4 1/2
0
1/4 x1
0
0 x2 -1/2 2
-1/2
0
0 x3 1 0
0
0
一： 情形 1： x 0 ，这时（LP）无可行解。因为
ˆ 如果（LP）有可行解 x 的可行解，在此点， （ALP）的目标函数值

第1讲线性规划及单纯形法

第1讲线性规划及单纯形法
21
解：目标函数： Min 约束条件：
f = 2x1 + 3 x2
s.t.
x1 + x2 ≥ 350
x1 ≥ 125
2 x1 + x2 ≤ 600
x1 , x2 ≥ 0 采用图解法。如下图：得Q点坐标（250，100）为最优解。
x2
x1 =125
600
500
2x1+3x2 =1200
400
2x1+x2 =600
26
凸集
定义 2.2.1：设 S Rn 是 n 维欧氏空间的点集，若对任意 x S, y S 的和任意 [0,1] 都有 x (1 ) y S 就称 S 是一个凸集。
定理 2.2.1 线性规划的可行域 D { x Ax b, x 0} 是凸集 定理 2.2.2 任意多个凸集 Si 的交还是凸集
例1 目标函数： max 50x1+100x2 约束条件：x1+x2+s1=300，
2x1+x2+s2=400， x2+s3=250.
xj≥0 （j=1，2）,sj≥0 （j=1，2,3）
30
它的系数矩阵 ,
1 1 1 0 0
A(p1,p2,p3,p4,p5)2 1 0 1 0
0 1 0 0 1
其中pj为系数矩阵A第j列的向量。A的秩为3,A的秩m小于此方程组的变
a i1 x 1 a i 2 x 2 a in x n s i b i , s i 0
或
a i1 x 1 a i 2 x 2 a in x n b i
松弛变量
a i1 x 1 a i 2 x 2 a in x n s i b i , s i 0

1.线性规划

1.线性规划
其特征是： 1．解决问题的目标函数是多个决策变量的线性函数，
通常是求最大值或 最小值；
2．解决问题的约束条件是一组多个决策变量的线性不
等式或等式。
【例1.2】某商场决定：营业员每周连续工作5天后连续休息2天， 轮流休息。根据统计，商场每天至少需要的营业员如表1.2所示。
表1.2 营业员需要量统计表
min f (x), s.t. x∈.
约束条件
可行解域
线性规划（Linear Programming,缩写为LP） 是运筹学的重要分支之一，在实际中应用得较广 泛，其方法也较成熟，借助计算机，使得计算更方便， 应用领域更广泛和深入。 线性规划通常研究资源的最优利用、设备最佳运 行等问题。例如，当任务或目标确定后，如何统筹兼 顾，合理安排，用最少的资源（如资金、设备、原标 材料、人工、时间等）去完成确定的任务或目标；企 业在一定的资源条件限制下，如何组织安排生产获得 最好的经济效益（如产品量最多 、利润最大）。
运筹学的主要内容
数 学 规 划 组 合 优 化 随 机 优 化
线性规划 非线性规划 整数规划 动态规划 多目标规划 双层规划 最优计数问题 网络优化 排序问题 统筹图 对策论 排队论 库存论 决策分析 可靠性分析
学 科
内
容
许多生产计划与管理问题都可以归纳为最优 化问题, 最优化模型是数学建模中应用最广泛的 模型之一,其内容包括线性规划、整数线性规划、 非线性规划、动态规划、变分法、最优控制等. 近几年来的全国大学生数学建模竞赛中，几 乎每次都有一道题要用到此方法. 此类问题的一般形式为： 目标函数
星 期 需要 人数 星 期 需要 人数
一
二 三 四
300
300 350 400

线性规划

线性规划
1.3 线性规划问题的标准型式
M1 : 目标函数： max z c 1 x 1 c 2 x 2 c n x n a 11 x 1 a 12 x 2 a 1 n x n b1 a x a 22 x 2 a 2 n x n b 2 21 1 约束条件： a x a x a x b m2 2 mn n n m1 1 x 1 , x 2 , , x n 0
24
第2节 应用举例

最终计算表（第3次计算）
c j→ CB 0.1 -0.3 0 XB x2 x4 x1 c j -z j b 10 50 30 0 x1 0 0 1 0 0.1 x2 1 0 0 0 0.2 x3 -1 1 1 0 0.3 x4 0 1 0 0 0.8 x5 -9/10 1/3 13/10 -0.74 -M x6 3/5 0 -1/5 -M + 0.06 -M x7 -3/10 1/3 1/10 -M + 0.12 -M x8 -1/5 0 2/5 -M -0.02 θ
27
第2节 应用举例

表1-7表明这些原材料供应数量的限额。加入到产品A、 B、D的原材料C总量每天不超过100kg，P的总量不超过 100kg，H总量不超过60kg。
表1-7
原材料名称 C P H 每 天 最 多 供 应 量 （ kg） 100 100 60 单 价 /(元 /kg) 65 25 35
29

第2节 应用举例

约束条件可表示为：
1 2 1 4 x1 x1 1 2 3 4 x2 x2 1 2 1 4 x3 x3 x1 x2 x3 x1 , , x 9 0 3 4 1 2 x4 x4 1 4 1 2 x5 x5 1 4 1 2 x6 x6 x7 x5 x6 x8 0 0 0 0 100 100 x 9 60

线性规划模型

线性规划模型

1
(1-7)
标准型的特征
w目标函数最大化 w约束条件为等式 w右端相为非负值 w决策变量非负值
而称以下的形式为标准矩阵形式：
Max z C X
T
s.t. AX b
X 0
(1-8)
如何将线性规划转化为标准型
（１）若目标函数是求最小值 Min S = CX
令 S ˊ = - S,
则
Max Sˊ= - CX
令 z = -f = - 3.6x1 + 5.2x2 - 1.8x3 ，
其次考虑约束，有2个不等式约束，引进
松弛变量x4，x5 ≥0。于是，我们可以得到以
下标准形式的线性规划问题： Max z = - 3.6 x1 + 5.2 x2 - 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 + x4 = 15.7 4.1 x1 x1 + 3.3 x3 + x2 + x3 - x5 = 8.9 = 38
取其等式在坐标系中作出直线，通过判断确定不等
式所决定的半平面。各约束半平面交出来的区域
（存在或不存在），若存在，其中的点表示的解称 为此线性规划的可行解。这些符合约束限制的点集 合，称为可行集或可行域。进行（3）；否则该线 性规划问题无可行解。
（3）任意给定目标函数一个值作一条目标函数的 等值线，并确定该等值线平移后值增加的方向，平移 此目标函数的等值线，使其达到既与可行域有交点又 不可能使值再增加的位置（有时交于无穷远处，此时 称线性规划的解无界）。若有交点时，此目标函数等 值线与可行域的交点即最优解（一个或多个），此目 标函数的值即最优值。
例2 将以下线性规划问题转化为标准形式 Min f = 3.6 x1 - 5.2 x2 + 1.8 x3

混合整数线性规划

混合整数线性规划

B1 B 2 c11 c12 c 21 c 22
cm1 cm 2 b1 b 2
生产 建设
Bn 能力 费用 c1n a1 f1 c2n a2 f2
c mn a m f m bn
设： xij 表示从工厂运往销地的运量(i=1.2…m、
j=1.2…n), 1 在Ai建厂
又设 Yi＝
（i=1.2…m）
⑵ ⑴
A
(18/11,40/11)
BCD
E
F
⑶
求（LP6），如图所示。 1
此时 F在点取得最优解。
x1＝3, x2 =2.5,
1
3
x1
Z(6)＝－31/2≈－15.5 > Z(5)
如对 Z(6) 继续分解，其最小值也不会低于－15.5 ，问 题探明,剪枝。
至此，原问题 （IP）的最优解 为：
x1=2， x2 =3, Z* = Z(5)
x1≥3
LP4 无可 行解
＃
LP5 x1=2, x2=3 Z(5) ＝－17
＃
LP6 x1=3, x2=5/2 Z(6) ＝－15.5
＃
三、0－1 整数规划
0－1 整数规划是一种特殊形式的整数规划，这时的 决策变量xi 只取两个值0或1，一般的解法为隐枚举法。
例一、求解下列0－1 规划问题
max Z 3 x 1 2 x 2 5 x 3
4、修改上、下界：按照以下两点规则进行。 ⑴.在各分枝问题中，找出目标函数值最大者作为新 的上界； ⑵.从已符合整数条件的分枝中，找出目标函数值最 大者作为新的下界。
5、比较与剪枝 ：
各分枝的目标函数值中，若有小于Z 者，则剪掉此 枝，表明此子问题已经探清，不必再分枝了;否则继续 分枝。

线性规划模型举例

线性规划模型举例

A1 Am
原料单价
a11 a1 n a m 1 a mn
b1ห้องสมุดไป่ตู้ bm
8
c1 c n
设x j 表示第j 种饲料所用的数量， 其模型如下： min Z c j x j
j 1 n
n a ij x j bi j 1 xj 0
(i 1,2 m)
9
例题2：
某人每天食用甲、乙两种食物 （如猪肉、鸡蛋），其资料如下： 问两种食物各食用多少，才能既 满足需要、又使总费用最省？ 设：Xj 表示Bj 种食物用量。
食 量 物 成分 含
甲
0.1 1.7 1.10 2
乙
0.15 0.75 1.30 1.5
最 低 需要量
A1 A2 A3
原料单价
1.00 7.50 10.00
线性规划的几个应用模型
一般而言，一个经济、管理问题满足以 下条件时，才能建立线性规划模型。 ⑴.要求解问题的目标函数能用数值指标 来反映，且为线性函数； ⑵.存在着多种方案； ⑶.要求达到的目标是在一定条件下实现 的，这些约束可用线性等式或不等式描述。
1
（一）资源的合理利用
一般描述： 某厂计划在下一生产周期内生产B1,B2, … Bn种产品， 要消耗A1,A2, … Am种资源，已知每件产品所消耗的资源 数、每种资源的数量限制以及每件产品可获得的利润如表 所示，问如何安排生产计划，才能充分利用现有的资源， 使获得的总利润最大？
下料 下料 毛 件数 方式 坯型号
B1

Bn

需 要 毛坯数
A1 Am
a11 a1n am1 amn
b1 bm
5
设：x j 表示用B j ( j 1,2 n)种方式 下料的原材料件数，其 数学模型为： min Z x1 x 2 x n a11 x1 a1n x n b1 a x a x b m 1 1 mn n m x 0 ( j 1 , 2 n ) j

线性规划

线性规划

§2.1 线性规划问题及其模型 Mathematical Model of LP
Linear Programming
【例2.1】美佳公司计划制造I、II两种家电产品。已知
各制造一件时分别占用的设备 A 、 B 的台时、调试工序 时间及每天可用于这两种家电的能力、各售出一件时 的获利情况，如下表所示。问：该公司应制造两种家 电各多少件，使获取的利润最大？ 项目 设备A(h) 设备B(h) 调试工序(h) 利润(元) I 0 6 1 2 II 5 2 1 1 每天可用能力 15 24 5
≥ 60, x1 + x 2 ≥ 70 ≥ 60, x3 + x 4 ≥ 50 ≥ 20, x5 + x6 ≥ 30 x1−6 ≥ 0
x6 + x1 x + x 2 3 s.t. x 4 + x5
§2.2 线性规划应用举例
Linear Programming
例2.4 一家中型的百货商场，它对售货员的需求经 过统计分析如下表所示。为了保证售货人员充分休 息，售货人员每周工作5天，休息两天，并要求休息 的两天是连续的。问应该如何安排售货人员的作息， 既满足工作需要，又使配备的售货人员的人数最少？
§2.1 线性规划问题及其模型 Mathematical Model of LP
Linear Programming
假设决策变量 x j 的取值受到 m 项资源的限制，
bi ， i = 1,2, , m 表示第 i 种资源的拥有量，
aij 表示决策变量 x j 取值为1个单位时所消耗的 第 i 种资源的数量；我们通常把 aij 称为工艺系数。
设备 A1 A2 B1 B2 B3 原料（元/件） 售价（元/件） 产品单件工时 Ⅰ Ⅱ Ⅲ 5 10 7 9 12 6 8 4 11 7 0.25 0.35 0.50 1.25 2.00 2.80 设备的 有效台时 6000 10000 4000 7000 4000 设备加工费 (元/h) 0.05 0.03 0.06 0.11 0.05

线性规划与计算复杂性简介(全部)

线性规划与计算复杂性简介(全部)

图的着色问题
给定一个无向图和k种颜色，图的着 色问题要求用这k种颜色为图的顶点 着色，使得相邻的顶点颜色不同且使 用的颜色数最少。这是一个NP完全 问题，因为验证一个给定的着色方案 是否满足条件可以在多项式时间内完 成，但找到最优的着色方案却是一个 难题。
06
线性规划与计算复杂性关系探讨
线性规划在计算复杂性中的地位
1
线性规划是计算复杂性理论中的重要问题之一， 其求解算法的复杂性直接影响了许多实际问题的 计算效率。
2
线性规划问题的求解算法在计算复杂性理论中具 有重要的理论价值，对于推动计算复杂性理论的 发展具有重要意义。
3
线性规划问题的求解算法也是评价计算复杂性理 论的重要指标之一，其求解效率的高低直接反映 了计算复杂性理论的水平。
线性规划与计算复杂性简介(全部)
• 线性规划基本概念 • 单纯形法求解线性规划 • 内点法求解线性规划 • 线性规划应用举例 • 计算复杂性理论简介 • 线性规划与计算复杂性关系探讨
01
线性规划基本概念
定义与特点
定义
线性规划是一种数学优化技术， 用于优化一组线性不等式约束下 的线性目标函数。
特点
目标函数和约束条件均为线性函 数；可行域为凸多边形或凸多面 体；最优解存在于可行域的顶点 上。
线性规划问题分类
有界与无界问题
01
根据可行域是否有界进行分类。
标准型与非标准型问题
02
根据目标函数和约束条件的形式进行分类。
整数规划与非整数规划
03
根据决策变量的取值范围进行分类。
标准形式与转化
标准形式
求解线性规划问题的复杂性分析
求解线性规划问题的算法通常包括多项式时间算法和指数 时间算法两类，其中多项式时间算法具有较高的计算效率， 而指数时间算法则具有较高的计算精度。

第一章 线性规划

第一章 线性规划
对于标准形式的线性规划问题若约束方程系数矩阵中不存在现成的初始可行基则不能简单的用上述单纯形法而通常采用所谓的人工变量法
第一章 线性规划
(Linear Programming, LP)
概述
• 线性规划问题的提出最早是1939年由前苏联 数学家康托洛维奇在研究铁路运输的组织问题、 工业生产的管理问题时提出来的。
（5）若bi < 0，则－bi > 0
举例: 化下列线性规划为标准形
max z=2x1+2x2－4x3 x1 + 3x2－3x3 ≥30 x1 + 2x2－4x3≤80 x1、x2≥0，x3无限制
max z=2x1+2x2－4x3’+4x3” x1 + 3x2－3x3’+3x3” –x4 = 30 x1 + 2x2－4x3+ 4x3” + x5 = 80 x1、x2 、x3’、x3” 、x4、x5 ≥0
称X0为该线性规划对应与基B的一个基本解。
同样，在A中任选m个线性无关的列向量都可以组成一个基， 对应基一个基本解。对于一个LP最多有多少呢？从n个中 选m个进行组合，即：
Cnm=n！/[（n－m）！m！] 因此，基本解是有限的。
举例：找出下列LP所有的基及其对应的基本解 max z=6x1+4x2 2x1 + 3x2≤100 4x1 + 2x2≤120 x1、x2≥0
资源
产品
甲
乙 资源限制
A
1
B
2
C
0
单位产品利润(元/件) 50
1
300kg
1
400kg
1
250kg
100
• 决策变量：x1、x2——分别代表甲、乙两

二丶 线性规划的图解法

二丶 线性规划的图解法

a<0，b<0
a a>0，b<0
. #;
图解法小结
使用条件：仅有两个至多不超过三个决 策变量的线性规划。
基本步骤：
第一步－－建立平面直角坐标系； 第二步－－根据约束条件和非负条件画出
可行域。 第三步－－作出目标函数等值线（至少两
条）， 结合目标函数优化要求，平移目 标函数等值线求出最优解。
图解法的优缺点： 简单、直观但有局 限性。
. #;
综上，用图解法求解线性规划时，各种 求解结果与各种类型的可行域之间的对应 关系可以用下图加以描述：
解的类型
可行域类型
唯一最优解
无穷多个最优解
非空有界
最优解无界 （无“有限最优解”）
无界
无解 （不存在可行域）
空集
. #;
课堂练习1-2：用图解法求解下面的线性规划
MaxZ 2 x 1 5 x 2
或“最优解无界”。如果一个实际问题抽象成像例1－4这样的
线性规划模型，比如是一个生产计划问题，其经济含义就是某 些资源是无限的，产品的产量可以无限大，解释不合理。此时 应重新检查和修改模型，否则就没有实际意义。
注意，对于无界可行域的情况，也可能有唯一最优解或无穷 多个最优解。比如目标要求为minZ=x1+2x2或maxZ=－2x1+x2， 而约束条件不变的例子。
. #;
第一次作业—— P69 习题1：1-2；P70 1-3 交作业时间：
下周周二（9月17日） 按小组交
/ /
3y 2 3y 2
2 3
y1 , y2 0
. #;
它的图解见右图。其中L1和L2分别为两个 约束半平面的边界，虚线为目标函数等值线， 可行域为图中阴影部分，沿着与箭头（目标函 数值递增的方向）相反的方向平移目标函数等 值线（注意：对偶规划中 要求对目标函数极小化）

最优化理论和方法-第二章 线性规划基本理论和算法

最优化理论和方法-第二章 线性规划基本理论和算法

其中 向量表示：
给定，变量是
定义标准形 有必要吗?
其中
给定，变量是
标准形的特征：极小化、等式约束、变量非负
第 2 章 线性规划: 基本理论与方法
数学规划基础
LHY-SMSS-BUAA
例4. 化成标准形
等 价 于
最优化问题的等价表述指 两个问题的最优值相等、差一个常数、或者互为相反数， 由其中一个问题的最优解可以得到另一个的最优解。
cT
( x* )T
( 1, 1)
( 0, 0)
( 0, 1) (x1, 0), x1 ≥ 0 ( 1, 0) (0, x2), x2∈[0,1] (-1, -1) 没有 有限 解
解的几何特征
惟一的顶点 一条边 一条边 无(下)界
第 2 章 线性规划: 基本理论与方法
数学规划基础
LHY-SMSS-BUAA
只要有 m 个单位列 e1 , e2 , … , em 即可，次序可以打乱！
◎ 规范形的系数的一种解释
yj B1aj aj y1ja1 y2 ja2 ymjam
规范形第 j 列的系数是用当前基表示 aj 时的系数！
第 2 章 线性规划: 基本理论与方法
数学规划基础
LHY-SMSS-BUAA
第 2 章 线性规划: 基本理论与方法
数学规划基础
LHY-SMSS-BUAA
线性规划问题解的几种情况
提示: 学习单纯形法之前,请务必学习并理解书上 p.19, 例2.2.1.
第 2 章 线性规划: 基本理论与方法
数学规划基础
LHY-SMSS-BUAA
2.2 单纯形法
• 适用形式：标准形(基本可行解等价于极点) • 理论基础：线性规划的基本定理！ • 基本思想：从约束集的某个极点/BFS开始，依次

线性规划1

线性规划1

习题一1.1 用图解法求解下列线性规划问题，并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。

(1) min z ＝6x1＋4x2(2) max z ＝4x1＋8x2st. 2x1＋x2≥1 st. 2x1＋2x2≤103x1＋4x2≥1.5 －x1＋x2≥8x1, x2≥0 x1, x2≥0(3) max z ＝x1＋x2(4) max z ＝3x1－2x2st. 8x1＋6x2≥24 st. x1＋x2≤14x1＋6x2≥－12 2x1＋2x2≥42x2≥4 x1, x2≥0x1, x2≥0(5) max z ＝3x1＋9x2(6) max z ＝3x1＋4x2st. x1＋3x2≤22 st. －x1＋2x2≤8－x1＋x2≤4 x1＋2x2≤12x2≤6 2x1＋x2≤162x1－5x2≤0 x1, x2≥0x1, x2≥01.2. 在下列线性规划问题中，找出所有基本解，指出哪些是基本可行解并分别代入目标函数，比较找出最优解。

(1) max z ＝3x1＋5x2(2) min z ＝4x1＋12x2＋18x3st. x1＋x3＝4 st. x1＋3x3－x4＝32x2＋x4＝12 2x2＋2x3－x5＝5 3x1＋2x2＋x5＝18 x j≥0 （j＝1, (5)x j≥0 （j＝1, (5)1.3. 分别用图解法和单纯形法求解下列线性规划问题，并对照指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点。

(1) max z ＝10x1＋5x2st. 3x1＋4x2≤95x1＋2x2≤8x1, x2≥0(2) max z ＝100x1＋200x2st. x1＋x2≤500x1≤2002x1＋6x2≤1200x1, x2≥0９１０1.4. 分别用大M 法和两阶段法求解下列线性规划问题，并指出问题的解属于哪一类：(1) max z ＝4x 1＋5x 2＋ x 3 (2) max z ＝2x 1＋ x 2＋ x 3st. 3x 1＋2x 2＋ x 3≥18 st. 4x 1＋2x 2＋2x 3≥42x 1＋ x 2 ≤4 2x 1＋4x 2 ≤20x 1＋ x 2－ x 3＝5 4x 1＋8x 2＋2x 3≤16x j ≥0 （j ＝1,2,3） x j ≥0 （j ＝1,2,3）(3) max z ＝ x 1＋ x 2 (4) max z ＝x 1＋2x 2＋3x 3－x 4st. 8x 1＋6x 2≥24 st. x 1＋2x 2＋3x 3＝154x 1＋6x 2≥－12 2x 1＋ x 2＋5x 3＝202x 2≥4 x 1＋2x 2＋ x 3＋ x 4＝10x 1, x 2≥0 x j ≥0 （j ＝1, (4)(5) max z ＝4x 1＋6x 2 (6) max z ＝5x 1＋3x 2＋6x 3st. 2x 1＋4x 2 ≤180 st. x 1＋2x 2＋ x 3≤183x 1＋2x 2 ≤150 2x 1＋ x 2＋3x 3≤16x 1＋ x 2＝57 x 1＋ x 2＋ x 3＝10x 2≥22 x 1, x 2≥0，x 3无约束x 1, x 2≥01.5 线性规划问题max z ＝CX ，AX ＝b ，X ≥0，如X*是该问题的最优解，又λ＞0为某一常数，分别讨论下列情况时最优解的变化：（1） 目标函数变为max z ＝λCX ；（2） 目标函数变为max z ＝（C ＋λ）X ；（3） 目标函数变为max z ＝C X ，约束条件变为AX ＝λb 。

线性规划对偶问题

线性规划对偶问题

MaxZ 2 x1 3 x 2 3 x3 x1 x 2 x3 3 s.t. x1 4 x 2 7 x3 9 x , x , x 0 1 2 3
它的对偶问题就是一个价格系统，使在平衡了劳动力和原材料 的直接成本后，所确定的价格系统最具有竞争力：
5
11
2、非对称形式的对偶关系： （1） 原问题
max Z c j x j
j 1 n
对偶问题
min W bi xi
i 1 m
aij x j bi i 1,2, , m s.t. j 1 x 0 j 1,2, , n j
n
m aij yi c j j 1, 2, , n s.t. i 1 y 符号不限， i 1, 2, , m i
17
(4) 对于极小化问题的具有非负限制的变量(极大化问题的具 有非正限制的变量)，在其对偶问题中，相应的约束为“≤” 型不等式；对于极小化问题的具有非正限制的变量(极大化问 题的具有非负限制的变量)，在其对偶问题中，相应的约束为 “≥”型不等式；对于原问题中无正负限制的变量，在其对偶 问题中，相应的约束为等式。
“上、下”交换，“左、右”换位， 不等式变号，“极大”变“极小”
(4) 对称性: 对偶问题的对偶是原问题.
9
例：写出下面线性规划的对偶规划模型：
max z c1 x1 c2 x2 c3 x3 a11 x1 a12 x2 a13 x3 b1 a x a x a x b 21 1 22 2 23 3 2 s.t. a31 x1 a32 x2 a33 x3 b3 x1 0, x2 0, x3无约束
19
第二节

高中线性规划

高中线性规划

高中线性规划高中线性规划是高中数学课程中的一个重要内容，它是线性代数的一个应用领域。

线性规划是一种数学优化方法，用于解决在给定约束条件下，求解线性目标函数的最优解的问题。

在高中数学中，线性规划通常是在二维平面上进行的。

一、线性规划的基本概念线性规划的基本概念包括目标函数、约束条件和可行域。

1. 目标函数：线性规划的目标是最大化或者最小化一个线性函数，这个线性函数称为目标函数。

在高中线性规划中，常见的目标函数是求解最大值或者最小值。

2. 约束条件：线性规划的约束条件是一些不等式或者等式，用于限制变量的取值范围。

约束条件可以是线性不等式、线性等式或者非负约束。

3. 可行域：可行域是满足所有约束条件的变量取值的集合。

在二维平面上，可行域通常是一个多边形。

二、线性规划的求解方法高中线性规划通常使用图形法进行求解。

具体步骤如下：1. 确定目标函数：根据问题的描述，确定目标函数是求解最大值还是最小值，并写出目标函数的表达式。

2. 确定约束条件：根据问题的描述，确定约束条件，并将其转化为不等式或者等式的形式。

3. 画出可行域：根据约束条件，画出可行域在二维平面上的图形。

4. 确定最优解：在可行域内，找到使目标函数取得最大值或者最小值的点，这个点就是最优解。

条件，并确定最优解的实际意义。

三、线性规划的应用举例线性规划在实际生活中有广泛的应用，以下是一个简单的例子：某公司生产两种产品A和B，每天能生产的产品A的数量不超过100个，产品B的数量不超过200个。

产品A每一个利润为10元，产品B每一个利润为15元。

生产一个产品A需要消耗2个单位的材料和3个单位的人力，生产一个产品B需要消耗1个单位的材料和4个单位的人力。

公司每天有200个单位的材料和300个单位的人力可供使用。

问如何安排生产，使得利润最大化？解题步骤如下：1. 确定目标函数：设产品A的数量为x，产品B的数量为y，则目标函数为10x + 15y。

2. 确定约束条件：根据题目中的描述，可以得到以下约束条件：a) x ≤ 100b) y ≤ 200c) 2x + y ≤ 200d) 3x + 4y ≤ 300e) x ≥ 0, y ≥ 03. 画出可行域：根据约束条件，可以画出可行域在二维平面上的图形。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

最优化算法实验指导书
1.线性规划求解
1.1 生产销售计划
问题 一奶制品加工厂用牛奶生产A 1、A 2两种普通奶制品，以及B 1、B 2两种高级奶制品，分别是由A 1、A 2深加工开发得到的，已知每1桶牛奶可以在甲类设备上用12h 加工成3kg A 1，或者在乙类设备上用8h 加工成4kg A 2；深加工时，用2h 并花1.5元加工费，可将1kg A 1加工成0.8kg B 1，也可将1kg A 2加工成0.75kg B 2，根据市场需求，生产的4种奶制品全部能售出，且每公斤A 1、A 2、 B 1、B 2获利分别为12元、8元、22元、16元。

现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间最多为480h ，并且乙类设备和深加工设备的加工能力没有限制，但甲类设备的数量相对较少，每天至多能加工100kg A 1，试为该厂制定一个生产销售计划，使每天的净利润最大，并讨论以下问题： （1）若投资15元可以增加供应1桶牛奶，应否作这项投资；
（2）若可以聘用临时工人以增加劳动时间，支付给临时工人的工资最多是每小时几
元？
（3）如果B 1、B 2的获利经常有10%的波动，波动后是否需要制定新的生产销售计划？ 模型 这是一个有约束的优化问题，其模型应包含决策变量、目标函数和约束条件。

决策变量用以表述生产销售计划，它并不是唯一的，设A 1、A 2、 B 1、B 2每天的销售量分别为1234,,,x x x x （kg ），34,x x 也是B 1、B 2的产量，设工厂用5x （kg ）A 1加工B 1，6x （kg ）A 2加工B 2（增设决策变量5x 、6x 可以使模型表达更清晰）。

目标函数是工厂每天的净利润z ，即A 1、A 2、 B 1、B 2的获利之和扣除深加工费，容易写出1234561282216 1.5 1.5z x x x x x x =+++--(元)。

约束条件
原料供应：A 1每天的产量为15x x +（kg ），用牛奶13()/3x x +（桶），A 2的每天产量为26x x +（kg ），用牛奶26()/4x x +（桶），二者之和不得超过每天的供应量50（桶）。

劳动时间：每天生产A 1、A 2的时间分别为154()x x +和262()x x +，加工B 1、B 2的时间分别为52x 和62x ，二者之和不得超过总的劳动时间480h 。

设备能力：A 1每天的产量15x x +，不得超过甲类设备的加工能力100（kg ）。

加工约束：1（kg ）A 1加工成0.8（kg ）B 1，故350.8x x =；类似的460.75x x =。

非负约束：123456,,,,,x x x x x x 均为非负。

由此得如下基本模型：
123456max 1282216 1.5 1.5z x x x x x x =+++--
1526
152656153546
123456
50344()2()22480100.0.80.75,,,,,0x x x x x x x x x x x x s t x x x x x x x x x x ++⎧+≤⎪⎪
+++++≤⎪⎪
+≤⎨⎪=⎪
=⎪⎪≥⎩
显然，目标函数和约束函数都是线性的，这是一个线性规划问题，求出的最优解将给出使净利润最大的生产销售计划，要讨论的问题需考虑参数的变化对最优解和最优值的影响，即灵敏度分析，整理后为： 12345m a x 1282216 1.5 1.5
z x x x x x x =++
+--
12561
256153
5461234564343600
232240
100
.0.800.750,,,,,0
x x x x x x x x x x s t x x x x x x x x x x +++≤⎧⎪+++≤⎪⎪+≤⎪⎨-=⎪⎪-=⎪≥⎪⎩
编程计算如下：
c=[-12 -8 -22 -16 1.5 1.5];
>> A1=[4 3 0 0 4 3;2 1 0 0 3 2;1 0 0 0 1 0]; >> c=[-12 -8 -22 -16 1.5 1.5];
>> a=[4 3 0 0 4 3;2 1 0 0 3 2;1 0 0 0 1 0]; b=[600 240 100];
aeq=[0 0 1 0 -0.8 0;0 0 0 1 0 -0.75]; beq=[0 0];
lb=[0 0 0 0 0 0]; ub=[];
[x,fval]=linprog(c,a,b,aeq,beq,lb,ub) Optimization terminated successfully. x =
0.0000 168.0000 19.2000 0.0000 24.0000 0.0000
fval =
-1.7304e+003
1.2 配料问题
例 某炼油厂生产3种规格的汽油：70号，80号与85号，它们各有不同的辛烷值与含硫量的质量要求，这3种汽油由3种原料油调和而成，每种原料油每日可用量、质量指标及生产成本见下表1，每种汽油的质量要求和销售价格见表2，假定在调和中辛烷值和含硫量指标都符合线性可加性，问该炼油厂如何安排生产才能使其利润最大？
解 本例建立数学模型的关键是决策变量的选择，如果选择各种汽油产品的质量，在建立数学模型时会遇到一些困难，定义决策变量ij x 为第i 种原料调入第j 种产品油中的数量，记
j p 表示单位第j 种产品的销售价格，i c 为单位第i 种原料的生产成本，i e 及'j e 分别为原料
油和产品油的辛烷值，i h 和'j h 分别为原料油和产品油的含硫量，i s 为原料油每日的可用量，首先考虑问题的目标函数，第j 种汽油产品所产生的利润为
3
1
()j
i ij i p
c x =-∑
因此目标函数为
33
11
()j
i ij j i p
c x ==-∑∑
约束条件应有3组：
汽油产品的辛烷值要求：
112233123'(),1,2,3j j j j j j j e x e x e x e x x x j ++≥++= 汽油产品的含硫量要求：
112233123'(),1,2,3j j j j j j j h x h x h x h x x x j ++≥++=
原料油可用量的限制：
123,1,2,3i i i i x x x s i ++≤= 因此本题的数学模型为 33
11
max
()j
i ij j i p
c x ==-∑∑；
3
13
13
1
(')0,1,2,3(')0,1,2,3..,1,2,30,,1,2,3i j ij i i j ij i ij i j ij
e e x j h h x j s t x s j x i j ===⎧-≥=⎪⎪⎪-≥=⎪⎨⎪≤=⎪⎪⎪≥=⎩∑∑∑ 将已知数值代入并化简后，其数学模型为
11213112223213max 3000500600300200900z x x x x x x x =+-++-+ 2333600100x x ++
11213112223213233311213112223213233311121321222331323388200182100
237500.50.20.800.50.20.80..0.90.20.40200010005000,,1,2,3
ij x x x x x x x x x x x x x x x s t x x x x x x x x x x x x x i j -++≥⎧⎪--+≥⎪
⎪--+≥⎪
--≤⎪⎪--≤⎪⎨+-≤⎪
⎪++≤⎪
++≤++≤≥=⎩⎪⎪⎪⎪
>> c=[-300 0 500 -600 -300 200 -900 -600 -100];
>> a=[8 -8 -20 0 0 0 0 0 0;0 0 0 18 2 -10 0 0 0;0 0 0 0 0 0 23 7 -5;0.5 0.2 -0.8 0 0 0 0 0 0;0 0 0 0.5 -0.2 -0.8 0 0 0;...
0 0 0 0 0 0 0.9 0.2 -0.4;1 0 0 1 0 0 1 0 0;0 1 0 0 1 0 0 1 0;0 0 1 0 0 1 0 0 1]; >> b=[0 0 0 0 0 0 2000 1000 500]; >> aeq=[]; beq=[];
lb=[0 0 0 0 0 0 0 0 0];
ub=[];
[x,fval]=linprog(c,a,b,aeq,beq,lb,ub)
Optimization terminated successfully.
x =
0.0000
0.0000
0.0000
0.0000
750.0000
150.0000
0.0000
250.0000
350.0000
fval =
-3.8000e+005
作业布置：建立模型并求解1.34 1.35（抄题目）。