线性规划问题1.docx

线性规划问题一、线性规划问题的基本概念几个典型实例例 1 生产计划问题某工厂拥有a、b两种原材料生产A、B两种产品，现有设备使用限量为8台时，已知每件产品的利润、所需设备台数及原材料的消耗如下表所示f产品原材料 、AB质材料总量a(kg)4016b(kg)0412利润（万元）23设备（台）12试问:在计划期内应如何安排计划才能使工厂获得的利 润最大？解设x、x分别表示在计划期内产品A、B的产量，12设备有效台数的限制 x + 2x < 8 ,12原材料的限量， 4x <16, 4x <12 12因此，生产计划就是满足如下约束条件的一组变量X］、 x 的值:2广 x + 2x < 8,1 2约束条件」4xi16,4x2 <12,x > 0, x > 012显然,可行的生产1 计划2有限多个,现在问题就是要在很 多个可行计划中找一个利润最大的，即求一组变量 x 、x12 的值，使它满足约束条件，并使目标函数 L=2x ＋3x 的值最大(即利润最大) 1 2例 2 资金分配问题某商店拥有 100 万元资金，准备经营 A、B、C 三种商品 其中A商品有A、A两种型号，B商品有B、B两种型号，1 2 1 2每种商品的利润率如下表所示：商品ABCA1A2B1B2利润率(%)7.310.36.47.54.5在经营中有以下限制：(1) 经营 A 或 B 的资金各自都不能超过总资金的 50%；(2) 经营 C 的资金不能少于经营 B 的资金的 25%；(3) 经营 A 的资金不能超过经营 A 的总资金的 60%；2试问应怎样安排资金的使用才能使利润最大？解 设经营 A 、 A 、 B 、 B 、 C 的资金分别为 x ， x ,x ,x1 2 1 2 1 2 3 4x (万元)，这一问题的数学模型为求一组变量 x 、 x ，…5 1 2x 的值，使它满足x + X +•••+ X =100,1 2 5x + x <50,12釣束条件:并使x + x < 50,34025x + 0.25x-x < 03 4 50.6x -0.4x > 0,12x >0 ( j=1, 2,..., 5)j目标函数L=0.073x +0.103x +0.064x +0.075x +0.045x12345的值最大（利润最大）上面我们建立了几个实际问题的数学模型,虽然实际问 题各不相同,但是它们的数学模型却有相同的数学形式,这 就是：表示约束条件的数学式子都是线性等式或线性不等 式，表示问题最优化指标的目标函数都是线性函数，因为 药束条件和目标函数都是线性的，所以把具有这种模型的问 题称为线性规划问题。

线性规划问题的数学模型的一般形式是Max(Min)L=c x + c x + ...+cx.1 1 2 2 n nf- a x + a x +•+ a x < b (或 > b ,11 1 12 2 1n n 1 1a x + a x +•+ a x < b (或>b ,21 1 22 2 2n n 2 2约束条件Y(1)或“),1或“),2»(2)—a x + a x +•+ a x < b （或>b ,mmm1 1 m2 2 mn n m(3)x > 0（ j=1，2，.，n） .即求一组变量X （ j=1, 2,…，n）的值，满足约束条 件，使目标函数L的值最大（或最小），其中，x 称为决策变量，简称变量，约束条件（3）称为变量的非 n 负约束—足约束条件的一组变量的值称为线性规划问题的一 个可行解，使目标函数L取得最大值（或最小值）的可行解 称为最优解，此时，目标函数的值称为最优值，“s.t. ”表 示约束条件例如，在例 1 中，若变量 x ， x 取值为 x=1， x=2 时，1 2 1 2它们满足约束条件，因此X =1，=2是该问题的一个可行解， 此时目标函数的值为 8。

求解线性规划问题有不少现成的数 学软件， LINDO 软件就是其中之一，在 LINDO6.1 版本下打 开，直接输入数学模型，Max 2X1 + 3X2s.t.X1 + 2X2<=84X1 <=164X2 <=12end注：LINDO中已规定所有决策变量均为非负，因此不必输入约束条件中 的非负约束条件，程序最后以“end”结束将文件存储并命名后，选择菜单“Solve”，得输出OBJECTIVEFUNCTION VALUE1) 14.000000VARIABLEVAL UEREDUCEDCOSTX14.000000X22.000000得到本题的最优解为即，生产A产品4件、B产品2件，利润为14万元例 3 工作人员的选择设有A、A、A、A四个人完成B、B、B、B四项工作， 每人只做一1件工2 作且3 每4件工作仅由一1人担2 任，3 A4 完成工作 B所需时间为C (i, j=1, 2, 3, 4)(单位：天)，如下表 所示 "B]B2B3B4Ai8131823A210141627A32102126A14222628试问应指派哪个人去承担哪件工作,才能使总的花费时 间最少？分析: 这个问题与上述各例有所不同,上述各例所设的 变量都是问题中所要求的数量，而这个例题中我们要引入的 变量必须具有指定某人做某件工作,而其他人不能做该工 作。

数 0、1 就起到了这种作用,变量取 1,说明该人做这 件事,在总的花费时间中贡献时间,变量取0表示不做这件 事,从而在总的花费时间中不作出贡献解 引入 16 个变量xij1,当指派 A 承担工作 B 时iji,j=1,2,3,40,当指派A不承担工作B时，ij推主：变量X23表示第二个人A?做第三项工作耳其他依次类由于每人只做一件工作,得x + x + x + x =1 可表示为 f x = 111 12 13 14 1 jj=1x＋x ＋x ＋x =122x ＋ x ＋ x ＋ x =1f4 x =31 32 33 34«/v3j j=1x ＋ x ＋ x ＋ x =1f4 x =41 42 43 444jj=1由于每件工作仅由一个担任,得x + x + x + x =1 可表示为 fx = 111 21 31 41i1 i=1x ＋x ＋x ＋x =1f4 x =112 22 32 42i2i=1x ＋x ＋x ＋x =1f4 x =113 23 33 43i3i=1x ＋x ＋x ＋x =1f4 x =114 24 34 44i4i=12423121f x = 12jj=11得线性规划模型如下MinT=8x ＋ 13x ＋ 18x ＋ 23x11 12 13 14 ＋10x ＋14x ＋16x ＋27x21 22 23 24 ＋2x ＋10x ＋21x ＋26x31 32 33 34 ＋14x ＋22x ＋26x ＋28x41 42 43 44s.t s x =1l X =1 i, j=1, 2, 3, 4x =0 或 1这种线性规划称为0-1规划，这类问题也称为指派问题 将模型输入LINDOMIn 8x11 + 13x12 + 18x13 + 23x14+ 10x21 + 14x22 + 16x23 + 27x24+ 2x31 + 10x32 + 21x33 + 26x34+ 14x41 + 22x42 + 26x43 + 28x44s.tx11 + x12 + x13 + x14=1x21 + x22 + x23 + x24=1x31 + x32 + x33 + x34=1x41 + x42 + x43 + x44=1xll + x21 + x31 + x41=lxl2 + x22 + x32 + x42=1x13 + c23 + x33 + x43=1x14 + x24 + x34 + x44=1endintl6注：intl6表示16个变量全部为0-1变量求解得 x =x =x =x =1,其余 x =0，即 A 承担工作B, A承担工作B,A承担工作B , A承担工作R，花费的 总2时间2 最少为 59 3天。

3 1 4 4整数规划例 4 汽车厂生产计划一汽车厂生产小、中、大三种类型的汽车，已知各类型 每辆车对钢材、劳动时间的需求、利润以及每月工厂钢材、 劳动时间的现有量如下表所示，试制订月生产计划，使工厂 的利润最大小型中型大型现有量钢材（吨）1.535600劳动时间（小时）28025040060000利润（万元）234解设每月生产小、中、大型汽车的数量分别为x、X、X， 工厂的月利润为L，在题目所给参数均不随生产数量变化的 假设下，可得线性规划模型：MaxL=2x ＋3x ＋4xs.t l・5x + 3x + 5x < 600 280X1+ 250x + 400X < 60000 1 X , X ,，X > 0 3 求解得到输出 1 2 3ORJECTIVE FUNCTION VALUE1 ) 632.2581VARIABLEVAL UEREDUCED COSTX164.5161290.000000X2167.7419280.000000X30.0000000.946237ROW SLACK OR SURPLUS DUAL PRICES2)0.0000000.7311833)0.0000000.003226我们看到最优解 x=64・516129,x=167.741928, x=0,出 现小数，显然不合适 1 2 3对于这个实际问题，变量 x ， x ， x 只能取整数，我们 必须在上述所建立的线性规划模1 型中2 增加3 约束条件x ， x ， x 为整数1 2 3得来的线性规划模型如下：MaxL=4x + 3x + 2xs.t 1.5x + 3x + 5x < 6001 2 3280x1 + 252x + 4300x < 60000x > 0, x >20, x >30x ， x ， x 均为整数附加了整数约束条件的线性规划模型称为整数规划用LINDO直接求解，输入文件：Max 2x1 + 3x2 + 4x3s.t1.5x1 + 3x2 + 5x3 <600280x1 + 250x2 + 400x3 < 60000endgin3注：最后一行“gin3”是“3个变量均为整数”的说明语句。

求解得到输出（只列出需要的结果）：OBJECTIVE FUNCTION VALUE1）632.0000VARIABLE VALUE RE。