线性规划课件

线性规划的理论与方法y线性规划的理论与方法

线性规划是指目标函数是由线性函数给出，约束条件由线性等式或者不等式给出的优化问题。

最早提出线性规划问题并进行专门研究的学者—康托洛维奇。

康托洛维奇在20世纪30年代就提出了求解线性规划问题的“解乘数法”。

自从1947年美国学者丹青格提出求解线性规划问题的一般方法—单纯形方法后，才使线性规划的理论和方法日臻成熟。（1）由决策变量构成，反映决策的目标是线性函数。（2）一组由决策变量的线性等式或不等式构成约束条件。（3）对决策变量取值范围加以限制的非负约束。1.1线性规划模型的特征

例1：某工厂生产甲、乙两种产品，每件产品的利润、所消耗的材料、工时及每天的材料限额和工时限额，如表1.1所示。试问如何安排生产，使每天所得的利润为最大？1.2线性规划问题的标准型

如下形式的线性规划模型被称作标准型:也可用矩阵形式描述:A:资源消耗系数矩阵b:资源限量向量C:价格向量X:决策变量向量同时我们对标准型作如下假定:一般的线性规划问题通过变换可化成标准型,变换方式可以归结为:可行解基解基可行解1.4线性规划问题的图解法

下面结合例1的求解来说明图解法步骤。例1第一步：在直角坐标系中分别作出各种约束条件，求出可行域（图中阴影部分）。x2Q2(6,4)x13x1+2x2=262x1+3x2=24ZOQ1(26/3,0)Q3(6,4)从理论上来讲,采用“枚举法”找出所有基可行解,并1.6求解线性规划问题的单纯形方法

一一比较,一定会找到最优解。但当m,n较大时,这种方法是不经济和不可取的。下面介绍求解线性规划问题的有效方法——单纯形方法。单纯形法的实质是从一个基可行解向另一个基可行解（极点到极点）的迭代方法。

以下通过例1的求解过程说明单纯形方法的基本步骤。例1：第一步：引进松驰变量x3,x4将原问题化为标准型。标准型第二步：找出初始可行基，建立初始单纯形表。见下表1.2。第四步：换基迭代。同理，确定x2换入，x3换出，继续迭代得表1.3cj4300CBXBb

x1x2x3x434x2x146013/5-2/510-2/53/5Z36001/56/5表1.3表中最后一行的所有检验数都已是正数或零，从而得到基本最优解X*=(6,4,0,0)T,Z*=36。由于x3,x4

是引进的松弛变量，因此原问题的最优解为x1=6,x2=4,最优值Z*=36。例2一奶制品加工厂用牛奶生产A1,A2两种奶制品，1桶牛奶可以在设备甲上用12小时加工成3公斤A1,或者在设备乙上用8小时加工成4公斤A2。根据市场需求，生产的A1,A2全部能售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且设备甲每天至多能加工100公斤A1,设备乙的加工能力没有限制。试为该厂制定一个

我们无意过深涉及线性规划的具体计算方法，而着重介绍的是如何建立若干实际的线性规划模型，如何使用现成的数学软件进行求解，以及如何对结果进行深入的分析。下面以奶制品加工生产计划为例，进行详细的讨论。生产计划，使每天获利最大，并进一步讨论以下3个附加问题：

若用35元可买到1桶牛奶，买吗？若买，每天最多买多少?

若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元?

由于市场需求的变化，A1的获利增加到30元/公斤，应否改变生产计划？解法1：图解法。

x1x20ABCDl1l2l3l4l5约束条件Z=0Z=2400Z=3360c从图中可以看出，在B(20,30)点得到最优解。解法2：软件实现。求解线性规划有不少现成的数学软件，比如用LINDO软件就可以很方便地实现。在LINDO6.1版本下打开一个新文件，像书写模型一样。直接输入：max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end注：LINDO中已规定所有决策变量均为非负，故变量非负的条件不必输入。输入文件中第1行为目标函数，2),3),4)是为了标示各约束条件，便于从输出结果中查找相应信息；程序最后以end结束。将文件存储并命名后，选择菜单“Solve”并对提示“DORANGE(SENSITIVITY)ANALYSIS?”回答“是”，即可得到如下输出：RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目标函数系数允许变化范围DORANGE(SENSITIVITY)ANALYSIS?

Yesx1系数范围(64,96)

x2系数范围(48,72)

A1获利增加到30元/千克，应否改变生产计划x1系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)

1.7线性规划问题经典例题典例1（运输问题）:设某种物资有m个产地A1,A2,······,Am,产量分别为a1,a2,······,am,有n个销地B1,B2,······,Bn,销量分别为b1,b2,······,bn假设产销是平衡的，即有：设cij（i=1,2,······,m;j=1,2,······,n)为由产地Ai

运往销地Bj的单位运费。这些数据汇总于表1.4中，试求总运费最少的运输方案。销地产地

B1B2

············Bn

供应量A1A2:Am需求量

c11c12

············c1n

c21c22

············c2n

:::cm1cm2

············cmnb1b2

············bna1a2:am表１.4假设f为总运费，xij为从Ai运往Bj的物资的数量，则这个问题的数学模型是：前面讨论的是产销平衡的问题，而实际问题中产销往往是不平衡的。对于这样的运输问题，解决的办法是把它转化为平衡的问题来处理。当产大于销时，即：此时，运输问题的数学模型可表示为：由于总产量大于总销量，可虚拟Bn+1为存储地，并设xi,n+1

是产地Ai的存储量，于是有：同样，当总销量大于总产量时，只要增加一个虚拟的产地Am+1,它的产量am+1为

可令，从假想产地Am+1到销地Bj的单位运费cm+1,j=0(j=1,2,······,n),同样可以将这类问题转化为产销平衡的问题。典例2（下料问题）:某工厂有一批长度为300cm的钢管（数量充分多），要把它们截成长度为45cm、80cm、95cm的管料，并要求其根数比例为5:3:2，来配套生产某种零件。问采用怎样的方案进行锯割，才能使得到的三种管料既能配套，又能使残料最少？解：首先，我们用表1.5列出各种可能的截法。截法12345678910长度45cm80cm95cm600410401320211202130121012003残料/cm304025535201503015表1.5解：设xj(j=1,2,······,10)表示按照第j种截法锯割的钢管的根数，那么截出的长45cm管料的根数为：截出的长95cm管料的根数为：截出的长80cm管料的根数为：此时，残料的长度为：因此，下料问题的数学模型为：典例3（投资问题）:一投资公司将1000万元的资金对A、B两个企业投资，对企业A每投资1万元，一年后公司可获利0.7万元；对企业B每投资1万元，两年后公司可获利2万元。对企业A每次投资周期必须是一年，对企业B每次投资周期必须是两年，到期结算后，以本利的和再作为资金继续对A、B两个企业投资。问公司要在第三年底收到最大效益，应该如何分配对A、B两个企业的投资数量？解：设投资公司对A、B两企业在第一年初的投资额分别为x11、x21

万元；在第二年初的投资额分别为x12、x22

万元；在第三年初的投资额分别为x13、x23

万元。在第一年初，投资公司投出总金额为1000万元，所以有：

x11+x21=1000························（1）在第一年底，回收到对A企业投资的本金+利润合计为：x11+0.7x11=1.7x11此资金作为第二年初对A、B两企业投资资金。在第二年初，投资公司对A、B两企业投资金额为1.7x11万元，所以有：

x12+x22=1.7x11························（2）在第二年底，回收的金额是两部分的和一部分是第二年初对A企业投资的本利和为：x12+0.7x