运筹与优化模型

1第六章运筹与优化模型6.1简单的运筹与优化模型

一、

线性规划模型线性规划是运筹学的一个重要分支，它起源于工业生产组织管理的决策问题。在数学上它用来确定多变量线性函数在变量满足线性约束条件下的最优值；随着计算机的开展，出现了如单纯形法等有效算法，它在工农业、军事、交通运输、决策管理与规划等领域中有广泛的应用。例1生产方案问题假设某厂方案生产甲、乙两种产品，这两种产品都要分别在A，B，C三种不同设备上加工．按工艺资料规定：生产每件甲产品需占用设备的小时数分别为2，l，4；生产每件乙产品需占用设备的小时数分别为2，2，0.各设备方案期内用于生产这两种产品的能力(小时数)分别为12，8，16；又知每生产一件甲产品，该厂会获得利润2元，每生产一件乙产品，该厂能获利润3元，问该厂应安排生产两种产品各多少件才能使总的利润收入为最大?解(1)明确决策变量工厂需要确定的是甲、乙两种产品的方案生产量，设x1,x2分别为甲、乙两种产品的方案生产量，总的利润为z．(2)明确约束条件因设备A在方案期内有效时间为12小时，不允许超过．故有对设备B，C也可列出类似的不等式此外产品的产量

只能取非负值，即

≥0≥0这种限制称为变量的非负约束条件．(3)明确目标工厂的目标是在各种设备能力允许的条件下，使总利润收入

为最大．

综合起来，该问题的数学模型为：求一组变量

的值在满足约束条件

的情况下，

为最大．

使利润例运输问题设有三个地方

生产某种物资

简称为产地)

(四个地方

需要该种物资

简称为销地)

产地的产量和销地的销量以及问如何组织物资的运输，才能在满足供需的条件下使总的运费最少．产地到销地的单位运价表见表1(表1产销运输表例3合理下料问题(后面详述其解法)

某工厂生产某一种型号的机床，每台机床上需要2.9m，2.1m，1.5m的轴分别为一根、二根、一根，这些轴需用同一种圆钢制作，圆钢的长度为7.4m，如果要生产100台机床，问应如何安排下料，才能使用料最省?7例4、某工厂制造A.B两种产品，制造A每吨需用煤9t，电力4kw，3个工作日；制造B每吨需用煤5t，电力5kw，10个工作日。制造产品A和B每吨分别获利7000元和12000元，现工厂只有煤360t，电力200kw，工作日300个可以利用，问A、B两种产品各应生产多少吨才能获利最大？解：设,〔单位为吨〕分别表示A、B产品的方案生产数；f表示利润〔单位千元〕那么问题归结为如下线性规划问题：8目标函数约束条件

其中(,)为决策向量，

满足约束条件的(,)称为可行决策。

线性规划问题就是指目标函数为诸决策变量的线性函数，给定的条件可用诸决策变量的线性等式或不等式表示的决策问题。线性规划求解的有效方法是单纯形法〔进一步了解可参考有关书籍〕，当然简单的问题也可用图解法。

线性规划的图解法(解的几何表示)：对于只有两个决策变量的线性规划问题，可以二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。图解法求解线性规划问题的步骤如下：

(1)建立直角坐标系：分别取决策变量x1,x2

为坐标向量。

〔2〕绘制可行域：对每个约束〔包括非负约束〕条件，作出其约束半平面〔不等式〕或约束直线〔等式〕。各半平面与直线交出来的区域假设存在，其中的点为此线性规划的可行解。称这个区域为可行集或可行域。然后进行下步。否那么假设交为空，那么该线性规划问题无可行解。〔3〕绘制目标函数等值线，并移动求解：目标函数随着取值不同，为一族相互平行的直线。首先，任意给定目标函数一个值，可作出一条目标函数的等值线〔直线〕；然后，确定该直线平移使函数值增加的方向；最后，依照目标的要求平移此直线。结果假设目标函数等值线能够移动到既与可行域有交点又到达最优的位置，此目标函数等值线与可行域的交点即最优解〔一个或多个〕，此目标函数的值即最优值。否那么，目标函数等值线与可行域将交于无穷远处，此时称无有限最优解。

Max

z=1500x1

+2500x2

s.t.3x1+2x2

≤65(A)

2x1+x2

≤40(B)

3x2

≤75(C)

x1,x2

≥0(D,E)例题作图〔1〕按照图解法的步骤：〔1〕以决策变量x1，x2为坐标向量作平面直角坐标系；〔2〕对每个约束〔包括非负约束〕条件作出直线〔A、B、C、D、E〕，并通过判断确定不等式所决定的半平面。各约束半平面交出来的区域即可行集或可行域如以下图阴影所示。

例题作图〔2〕第2步图示(1)分别作出各约束半平面X2≥0x1

≥03x2

≤753x1+2x2

≤65

2x1+x2

≤40

例题作图〔3〕第2步图示(2)各约束半平面的交－可行域〔3〕任意给定目标函数一个值〔例如37500〕作一条目标函数的等值线，并确定该等值线平移后值增加的方向〔向上移动函数值增大〕，平移此目标函数的等值线，使其到达既与可行域有交点又不可能使值再增加的位置，得到交点(5,25)T，即最优解。此目标函数的值为70000。例题作图〔4〕第3步图示作出目标函数等值线函数值增大2.线性规划的图解法例题作图〔5〕第3步图示(2)求出最优解121一般线性规划问题的数学表达式：

s.t线性规划问题可以用单纯形方法求解，但是比较复杂，可以用常用的数学软件如MATLAB，MATHEMATICA,LINGO等求解，这里只介绍用LINGO求解的方法。当你在windows下开始运行LINGO系统时，会得到类似下面的一个窗口：外层是主框架窗口，包含了所有菜单命令和工具条，其它所有的窗口将被包含在主窗口之下。在主窗口内的标题为LINGOModel–LINGO1的窗口是LINGO的默认模型窗口，建立的模型都都要在该窗口内编码实现。例4

如何在LINGO中求解如下的LP问题：在模型窗口中输入如下代码：min=2*x1+3*x2;x1+x2>=350;x1>=100;2*x1+x2<=600;然后点击工具条上的按钮即可。24钢管下料问题某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出，从钢管厂进货时得到的原料钢管都是19m。〔1〕现有一客户需要50根4m、20根6m和15根8m的钢管，应如何下料最节省？〔2〕零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理本钱，所以该零售商规定采用的不同切割模式不能超过3种。此外，该客户除需要〔1〕中的三种钢管外，还需要10根5m的钢管。应如何下料最节省。〔了解〕问题〔1〕的求解问题分析首先，应当确定哪些切割模式是可行的。25

所谓一个切割模式，是指按照客户需要在原料钢管上安排切割的一种组合。

例如：我们可以将19m的钢管切割成3根4m的钢管，余料为7m；或者将19m的钢管切割成4m、6m和8m的钢管各1根，余料为1m。显然，可行的切割模式是很多的。其次，应当确定哪些切割模式是合理的。

通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸。例如：将19m的钢管切割成3根4m的钢管，余料为7m，可进一步将7m的余料切割成4m钢管〔余料为3m〕，或者将7m的余料切割成6m钢管〔余料为1m〕。26

在这种合理性假设下，切割模式一共有7种，如表9所示。4m钢管根数6m钢管根数8m钢管根数余料（m）模式14003模式23101模式32013模式41203模式51111模式60301模式70023

问题化为在满足客户需要的条件下，按照哪些种合理的模式，切割多少根原料钢管，最为节省。而所谓节省，可以有两种标准：

27一是切割后剩余的总余料量最小，

二是切割原料钢管的总根数最小。

下面将对这两个目标分别讨论。模型建立决策变量表示按照第i种模式〔〕切割的原料钢管的根数，显然它们应当是非负整数。决策目标

以切割后剩余的总余料量最小为目标，那么由表9可得以切割原料钢管的总根数最少为目标，那么有284m钢管根数6m钢管根数8m钢管根数余料（m）模式14003模式23101模式32013模式41203模式51111模式60301模式70023约束条件为满足客户的需求，按照表9应有模型求解291．将〔1〕，〔3〕，〔4〕，〔5〕构成的整数线性规划模型〔加上整数约束〕输入LINDO如下：Min3x1+x2+3x3+3x4+x5+x6+3x7s.t.4x1+3x2+2x3+x4+x5>=50x2+2x4+x5+3x6>=20x3+x5+2x7>=15endgin7求解可以得到最优解如下：30OBJECTIVEFUNCTIONVALUE1)27.00000VARIABLEVALUEREDUCEDCOSTX10.0000003.000000X212.0000001.000000X30.0000003.000000X40.0000003.000000X515.0000001.000000X60.0000001.000000X70.0000003.000000

即按照模式2切割12根原料钢管，按照模式5切割15根原料钢管，共27根，总余料量为27m。显然，在总余料量最小的目标下，最优解将是使用余料尽可能小的切割模式〔模式2和5的余料为1m〕，这会导致切割原料钢管的总根数较多。312．将〔2〕～〔5〕构成的整数线性规划模型〔加上整数约束〕输入LINDO求解，可以得到最优解如下：OBJECTIVEFUNCTIONVALUE1〕25.00000VARIABLEVALUEREDUCEDCOSTX10.0000001.000000X215.0000001.000000X30.0000001.000000X40.0000001.000000X55.0000001.000000X60.0000001.000000X75.0000001.000000

即按照模式2切割15根原料钢管、按模式5切割5根、按模式7切割5根、共25根，可算出总余料量为35m。

与上面得到的结果相比，总余料量增加了8m，但是所用的原料钢管的总根数减少了2根。在余料没有用途情况下，通常选择总根数最小为目标。32问题〔2〕的求解问题〔2〕：零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理本钱，所以该零售商规定采用的不同切割模式不能超过3种。此外，该客户除需要〔1〕中的三种钢管外，还需要10根5m的钢管。应如何下料最节省。问题分析按照〔1〕的思路，可以通过枚举法首先确定哪些切割模式是可行的。但由于需求的钢管规格增加到4种，所以枚举法的工作量较大。下面介绍的整数非线性规划模型，可以同时确定切割模式和切割方案，是带有普遍性的方法。33同〔1〕类似，一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸〔此题中为4m〕，切割方案中只使用合理的切割模式，而由于此题中参数都是整数，所以合理的切割模式的余量不能大于3m。此外，这里我们仅选择总根数最小为目标进行求解。模型建立决策变量由于不同切割模式不能超过3种，可以用表示按照第i种模式〔〕切割的原料钢管的根数，显然它们应当是非负整数。34

设所使用的第i种切割模式下每根原料钢管生产4m，5m，6m和8m的钢管数量分别为〔非负整数〕。决策目标

切割原料钢管的总根数最小，目标为约束条件为满足客户的需求，应有35每一种切割模式必须可行、合理，所以每根原料钢管的成品量不能超过19m，也不能少于16m〔余量不能大于3m〕，于是模型求解在〔7〕～〔10〕式中出现决策变量的乘积，是一个整数非线性规划模型，虽然用LINGO软件可以直接求解，但我们发现运行很长时间也难以得到最优解。

为了减少运行时间，可以增加一些显然的约束条件，从而缩小可行解的搜索范围。36

例如，由于3种切割模式的排列顺序是无关紧要的，所以不妨增加以下约束

又例如，我们注意到所需原料钢管的总根数有着明显的上界和下界。首先，无论如何，原料钢管的总根数不可能少于根即至少需26根。其次，考虑一种非常特殊的生产方案：

第一种切割模式下只生产4m钢管，一根原料钢管切割成4根4m钢管，为满足50根4m钢管的需求，需要13根原料钢管；37

第二种切割模式下只生产5m、6m钢管，一根原料钢管切割成1根5m钢管和2根6m钢管，为满足10根5m和20根6m钢管的需求，需要10根原料钢管；

第三种切割模式下只生产8m钢管，一根原料钢管切割成2根8m钢管，为满足15根8m钢管的需求，需要8根原料钢管。于是满足要求的这种生产方案共需13+10+8=31根原料钢管，这就得到了最优解的一个上界。所以可增加以下约束将〔6〕～〔15〕构成的模型输入LINGO如下：38model：min=x1+x2+x3；x1*r11+x2*r12+x3*r13>=50；x1*r21+x2*r22+x3*r23>=10；x1*r31+x2*r32+x3*r33>=20；x1*r41+x2*r42+x3*r43>=15；4*r11+5*r21+6*r31+8*r41<=19；4*r12+5*r22+6*r32+8*r42<=19；4*r13+5*r23+6*r33+8*r43<=19；4*r11+5*r21+6*r31+8*r41>=16；4*r12+5*r22+6*r32+8*r42>=16；4*r13+5*r23+6*r33+8*r43>=16；x1+x2+x3>=26；x1+x2+x3<=31；x1>=x2；x2>=x3；@gin(x1)；@gin(x2)；@gin(x3)；@gin(r11)；@gin(r12)；@gin(r13)；@gin(r21)；@gin(r22)；@gin(r23)；@gin(r31)；@gin(r32)；@gin(r33)；@gin(r41)；@gin(r42)；@gin(r43)；end39Localoptimalsolutionfoundatiteration：12211Objectivevalue：28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.000001.000000R113.000000.000000R122.000000.000000R210.000000.000000R221.000000.000000R311.000000.000000R321.000000.000000R330.000000.000000R410.000000.000000R420.000000.000000R432.000000.00000040

即按照模式1，2，3分别切割10，10，8根原料钢管，使用原料钢管总根数为28根，

第一种切割模式下一根原料钢管切割成3根4m钢管和1根6m钢管；

第二种切割模式下一根原料钢管切割成2根4m钢管、1根5m钢管和1根6m钢管；第三种切割模式下一根原料钢管切割成2根8m钢管。41二、非线性规划模型非线性规划模型的一般形式为：

f(X)为目标函数，

(2)、(3)为约束条件，

(2)为不等式约束，(3)为等式约束；假设只有(1)称为无约束问题。42注：LINGO软件用于求解非线性规划〔包括含有整数变量的〕，输入总是以“model：〞开始，以“end〞结束；中间的语句必须以“；〞分开。约束中“@gin(x1)〞表示x1为整数，其他类似〔如果要表示x1为0-1整数，应该用“@int(x1)〞〕。43例容器的设计问题某公司专门生产储藏用容器，定货合同要求该公司制造一种敞口的长方体容器，容积恰好为12立方米，该容器的底必须为正方形，容器总重量不超过68公斤。用作容器四壁的材料为每平方米10元，重3公斤；用作容器底的材料每平方米20元，重2公斤。试问制造该容器所需的最小费用是多少？模型建立设该容器底边长和高分别为米、米，

那么问题的数学模型为〔容器的费用〕44一般来说，非线性规划模型的求解要比线性规划模型求解困难得多，虽然现在已经开展了许多非线性规划的算法，但到目前为止，还不象线性规划那样有通用的单纯形算法，而是各种算法都有自己特定的适用范围，如求解法有：最速下降法、牛顿法、可行方向法、惩罚函数法等。尽管如此，非线性规划的实际应用还是相当广泛的。45

实际问题中的优化模型一、投资策略(了解)某部门现有资金10万元，五年内有以下投资工程供选择：工程A,从第一年到第四年每年初投资，次年末收回本金且获利15%；工程B，第三年初投资，第五年末收回本金且获利25%，最大投资额为4万元；工程C，第二年初投资，第五年末收回本金且获利40%，最大投资额为3万元；工程D，每年初投资，年末收回本金且获利6%。问如何确定投资策略使第五年末本息总额最大。46问题的目标函数是第五年末的本息总额，

决策变量是每年初各个工程的投资额，约束条件是每年初拥有的资金。

用表示第年初〔〕工程分别代表A,B,C,D)的投资额，

根据所给条件只有下表1列出的才是需要求解的。

项目

年份

ABCD

12345

47因为工程D每年初可以投资，且年末能收回本息，所以每年初都应把资金全部投出去，工程A,从第一年到第四年每年初投资，次年末收回本金且获利15%；工程B，第三年初投资，第五年末收回本金且获利25%，最大投资额为4万元；工程C，第二年初投资，第五年末收回本金且获利40%，最大投资额为3万元；工程D，每年初投资，年末收回本金且获利6%。由此可得如下的约束条件：

第一年初：

第二年初：第三年初第四年初：第五年初：

工程B,C对投资额的限制：48工程A,从第一年到第四年每年初投资，次年末收回本金且获利15%；工程B，第三年初投资，第五年末收回本金且获利25%，最大投资额为4万元；工程C，第二年初投资，第五年末收回本金且获利40%，最大投资额为3万元；工程D，每年初投资，年末收回本金且获利6%。

每项投资应为非负的：第五年末本息总额为49由此得投资问题的线性规划模型如下：s.t.50求解得

即第1年工程A,D分别投资3.8268和6.1732(万元)；第2年工程A,C分别投资3.5436和3(万元)；第3年工程A,B分别投资0.4008和4(万元)；第4年工程A投资4.0752(万元)；第5年工程D投资0.4609(万元)；5年后总资金14。375万元，即盈利43.75%.51二、货机装运〔了解〕问题某架货机有三个货舱：前仓、中仓、后仓。三个货舱所能装载的货物的最大重量和体积都有限制，如表3所示。并且，为了保持飞机的平衡，三个货舱中实际装载货物的重量必须与其最大容许重量成比例。前仓中仓后仓重量限制（吨）10168体积限制（米3）680087005300

现有四类货物供该货机本次飞行装运，其有关信息如表4，最后一列指装运后所获得的利润。52重量（吨）空间（米3/吨）利润（元/吨）货物1184803100货物2156503800货物3235803500货物4123902850应如何安排装运，使该货机本次飞行获利最大？模型假设

问题中没有对货物装运提出其它要求，我们可作如下假设：1〕每种货物可以分割到任意小；2〕每种货物可以在一个或多个货舱中任意分布；533〕多种货物可以混装，并保证不留空隙。模型建立决策变量：

表示第i种货物装入第j个货舱的重量〔吨〕，货舱j=1,2,3分别表示前仓、中仓、后仓。

决策目标是最大化总利润，即约束条件包括以下4个方面：1〕从装载的四种货物的总重量约束，即542〕三个货舱的重量限制，即3〕三个货舱的空间限制，即554〕三个货舱装入重量的平衡约束，即模型求解将以上模型输入LINDO求解，可以得到：56OBJECTIVEFUNCTIONVALUE1)121515.8VARIABLEVALUEREDUCEDCOSTX110.000000400.000000X120.00000057.894737X130.000000400.000000X2110.0000000.000000X220.000000239.473679X235.0000000.000000X310.0000000.000000X3212.9473690.000000X333.0000000.000000X410.000000650.000000X423.0526320.000000X430.000000650.000000实