第一章 线性规划模型
第一章 线性规划模型
线性规划（Linear Programming）是数学规划的一个重要组成部分，是最优化与运筹学理论中的一个重要分支和常用的方法，是最优化理论的基础性内容。
第一节 线性规划问题及其数学模型
一、问题的提出
在生产管理和经营活动中经常提出一类问题，即如何利用有限的人力、物力、财力等资源，以便得到最好的经济效果。
例1 生产计划问题
某工厂在计划期内要安排生产Ⅰ、Ⅱ的两种产品，已知生产单位产品所需的设备台时，A、B两种原材料的消耗以及每件产品可获得的利润如下表所示。问应如何安排生产计划使该工厂获利最多？
设备 原材料A 原材料B 单位产品利润（元） Ⅰ 1 4 0 2 Ⅱ 2 0 4 3 资源限量 8(台时) 16(kg) 12(kg) 解：设x1,x2分别表示在计划期内生产产品Ⅰ、Ⅱ的产量。由于资源的限制，所以有：
机器设备的限制条件: x1?2x2?8
原材料A的限制条件： 4x1?16（称为资源约束条件） 原材料B的限制条件： 4x2?12
同时，产品Ⅰ、Ⅱ的产量不能是负数，所以有x1?0,x2?0（称为变量的非负约束）。
显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有许许多多。而工厂的目标是在不超过所有资源限量的条件下，如何确定产量x1,x2以得到最大的利润，即使目标函数z?2x1?3x2的值达到最大。
综上所述，该生产计划安排问题可用以下数学模型表示：
maxz?2x1?3x2
?x1?2x2?8?4x?161s.t.?
?4x2?12??x1,x2?0例2 运输问题
1
第一章 线性规划模型
某公司经销某种产品，三个产地和四个销地的产量、销量、单位运价如下表所示。问在保证产销平衡的条件下，如何调运可使总运费最少？ 销地 单位运价 产地 A1 A2 A3 销量 B1 5 4 4 30 B2 6 1 2 50 B3 10 9 3 40 B4 3 7 8 40 产量 60 40 60 解:（1）决策变量：设xij(i?1,2,3;j?1,2,3,4)为从产地i运到销地j的运量
（2）目标函数：总运费最小minz?（3）约束条件： 产量约束
??cxi?1j?134ijij
?x11?x12?x13?x14?60??x21?x22?x23?x24?40 ?x?x?x?x?60?31323334销量约束
?x11?x21?x31?30?x?x?x?50?122232 ?x?x?x?40?132333??x14?x24?x34?40非负约束
xij?0
模型为：
34minz???cijxiji?1j?1?x11?x12?x13?x14?60?x?x?x?x?40?21222324?x31?x32?x33?x34?60 ?x?x?x?30?112131s..t??x12?x22?x32?50?x13?x23?x33?40??x14?x24?x34?40?x?0(i?1,2,3;j?1,2,3,4)?ij二、线性规划问题的模型
2
第一章 线性规划模型
上述几例所提出的问题，可归结为在变量满足线性约束条件下，求使线性目标函数值最大或最小的问题。它们具有以下共同的特征。 （1）每个问题都可用一组决策变量(x1,x2,,xn)表示某一方案，其具体的值就代表一个具体
方案。通常可根据决策变量所代表的事物特点，对变量的取值加以约束，如非负约束。 （2）存在一组线性等式或不等式的约束条件。
（3）都有一个用决策变量的线性函数作为决策目标（即目标函数），按问题的不同，要求目标函数实现最大化或最小化。
满足以上三个条件的数学模型称为线性规划（LP）问题的数学模型，其一般形式为：
max(或min)z?c1x1?c2x2??cnxn
s.t?a11x2?a12x2?????a1nxn?(?,?)b1?ax?ax?????ax?(?,?)b2nn2?212222??????? ??am1x2?am2x2?????amnxn?(?,?)bm?x1,x2,???,xn?0?或矩阵形式
max(或min)z?CX?AX?(?,?)bs.t??X?0或向量形式
max（或min）z?CX
?n??pjxj?(?,?)bs.t?j?1 ?x?0(j?1,2,...,n)?j其中C?(c1,c2,,cn)，称为价值系数向量；
?a11?aA??21???am1a12a22am2a1n?a2n?? ??amn?称为技术系数矩阵(也称消耗系数矩阵)；b?(b1,b2,,bm)T称为资源限制向量；
X?(x1,x2,,xn)T称为决策变量向量。
三、建立线性规划模型的一般步骤：
（1）确定决策变量； （2）确定目标函数； （3）确定约束条件。
3
第一章 线性规划模型
例3 投资计划问题
某公司经调研分析知，在今后三年内有四种投资机会。第Ⅰ种方案是在三年内每年年初投资，年底可获利15%，并可将本金收回；第Ⅱ种是在第一年的年初投资，第二年的年底可获利45%，并将本金收回，但该项投资不得超过2万元；第Ⅲ种是在第二年的年初投资，第三年的年底可获利65%，并将本金收回，但该项投资不得超过1.5万元；第Ⅳ种是在第三年的年初投资，年底收回本金，且可获利35%，但该项投资不得超过1万元。现在本公司准备拿出3万元来投资，问如何计划可使到第三年年未本利和最大？
解：问题分析.该问题的实际投资背景如下表所示：
年份
（1）决策变量：设xij表示第i年对第j个方案的投资额，i?1,2,3;j?1,2,3,4 （2）目标函数：第三年年未的本利和为maxz?1.65x23?1.15x31?1.35x34 （3）约束条件：
每一年的投资额应等于当年公司拥有的资金数：
一 二 三 四 x11 1.15x11 x12 1.45x12 1.15x21 x21 x23 1.65x23 1.15x31 1.35x34 x31 x34 x11?x12?3; x21?x23?1.15x11; x31?x34?1.45x12?1.15x21
每个方案投资额的限制：
x12?2; x23?1.5; x34?1
非负约束：
xij?0,i?1,2,3;j?1,2,3,4。
例4 混合配料问题 某糖果厂用原料A，B，C加工成三种不同牌号的糖果甲，乙，丙。已知各种牌号糖果中A，B，C含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如下表所示。问该厂每月生产这三种牌号糖果各多少时，使该厂获利最大。试建立这个问题的线性规划模型。
A
甲 >60% 乙 >30% 4 丙 原料成本(元/kg) 第每月限制量(kg) 2.00 2000 第一章 线性规划模型
B C 加工费(元/kg) 售价(元/kg) <20% 0.50 3.40 <50% 0.40 2.85 <60% 0.30 2.25 1.50 1.00 2500 1200 解：(1)设决策变量xij表示生产第j种糖果(j?1,2,3表示甲，乙，丙三种糖果)耗用的第i种原料(i?1,2,3表示A,B,C三种原料)的kg数
(2)目标函数：该厂的获利为三种牌号糖果的售价减去相应的加工费和原料成本。
maxz?(3.40?0.50)(x11?x21?x31)?(2.85?0.40)(x12?x22?x32)?(2.25?0.30)(x13?x23?x33)?2.0(x11?x12?x13)?1.50(x21?x22?x23)?1.0(x31?x32?x33)
(3)约束条件：
?x11?x12?x13?2000?原料月供应量限制?x21?x22?x23?2500?x31?x32?x33?1200??x11?0.6(x11?x21?x31)? ?x31?0.2(x11?x21?x31)?x?0.3(x?x?x)含量成分的限制122232?12?x32?0.5(x12?x22?x32)??x33?0.6(x13?x23?x33)?xij?0?四、LP问题的标准形
1. 标准型
为了讨论LP问题解的概念和解的性质以及对LP问题求解方便，必须把LP问题的一般形式化为下面统一的标准型：
maxz??cjxj或maxz?CX
j?1n?n??aijxj?bi(i?1,2,,m)?AX?b或? ?j?1X?0??x?0(j?1,2,,n)j?标准型的特点：（1）目标函数是最大化类型（2）约束条件均由等式组成
（3）决策变量均为非负 （4）bi?0,i?1,2,2.化一般形式为标准型
①目标函数：minz?max(?z)??CX
②若约束为“?”型?左边+“松驰变量”；若约束为“?”型?左边－“剩余变量”
5
,m.