文档介绍：第二章线性规划问题与计算机求解
§1 问题的提出
§2 图解法
§3 单纯形法
§4 计算机求解
例1(生产计划问题) 某工厂生产A、B两种产品,其成本决定于所用的材料。已知单位产品所需材料量、材料日供应量及单价如表1-1所示。若每生产A或B产品一个单位,所费工资同为30元,又A、B的每单位销售价分别为120元和150元。问:工厂应如何安排生产,才能使所获总利润最大?
产品生产所需原材料
材料单价
资源限制
日供给给量kg
产品A
产品B
原料a
6
2
1元/ kg
180kg
原料b
4
10
/ kg
400kg
原料c
3
5
/ kg
210kg
销售单价(元)
120
150
单位产品利润(元)
31
22
相关数据
§1 问题的提出
产品A利润:120 –(×6 + ×4 + ×3 )(材料) – 30(工资) = 31 (元)
数学模型
设工厂日产A、B产品分别为x1,x2单位(决策变量)
线性规划模型:
目标函数: Max z = 31 x1 + 22 x2
约束条件(subject to):.
材料的a约束 6x1 + 2 x2 ≤ 180
4 x1 + 10x2 ≤ 400
3 x1 + 5x2 ≤ 210
x1 , x2 ≥ 0
产品A利润:120 –(×6 + ×4 + ×3)(材料) – 30(工资) = 31 (元)
产品A利润:150 –(×2 + ×10 +×5 )(材料) – 30(工资) = 22 (元)
§1 问题的提出
例2. 某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产,已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制,如下表:
问题:工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多?
设工厂生产产品A、B分别为x1,x2单位, 则线性规划模型:
目标函数:Max z = 50 x1 + 100 x2
约束条件:. x1 + x2 ≤ 300
2 x1 + x2 ≤ 400
x2 ≤ 250
x1 , x2 ≥ 0
产品Ⅰ
产品Ⅱ
设备使用成本和单价
资源限制
设备
1
1
10元/ 时
300台时
原料A
2
1
12元/ kg
400kg
原料B
0
1
18元/ kg
250kg
销售单价(元)
84
140
单位产品利润(元)
50
100
例3. 某饲料公司希望用玉米、红薯两种原料来配置一种混合饲料,已知两种原料含三种营养成分和混合饲料对营养成分的要求如下表:
问题:公司应任何采购两种原材料,使即满足营养要求,又使成本最少?
设公司采购用于混合饲料中玉米数量x1 kg ,红薯数量x2 kg 线性规划模型:
目标函数:Min z = 2 x1 + x2
约束条件:. 8 x1 + 4x2 ≥ 20
3x1 + 6 x2 ≥18
x1 + 5x2 ≥ 16
x1 , x2 ≥ 0
营养成分
每公斤玉米
每公斤红薯
饲料对营养要求
碳水化合物
8
4
20
蛋白质
3
6
18
维他命
1
5
16
采购成本(元/KG)
2
线性规划问题主要类型
资源分配问题(resource-allocation)以符号表示的函数约束称为资源约束,这些限制要求使用的资源必须小于等于所能提供的资源的数量。资源分配问题的共性就是它们的函数约束全部为资源约束。例1、2
成本收益平衡问题(cost-benefit-trade-off)以符号表示的函数约束为收益约束,形式为收益取得的水平必须大于等于最低可接受水平。收益约束反映了管理层所规定的目标。如果所有约束均为收益约束,这一问题为成本收益平衡问题。例3
网络配送问题(work)以=符号表示的函数约束称为确定需求的约束,它们表示了一定数量的确定的需求,提供的数量等于要求的数量。网络配送问题的共性就是它们的主要函数约束为一种特定形式的确定需求的约束。
混合问题(mixed Problem)除以上三类以外的问题
建模过程
,了解解题的目标和条件;
( x1 ,x2 ,…,xn ),每一组值表示一个方案; Decision variables 决策变量
,确定最大化或最小化目标; Objective function 目标函数
; Cons