线性规划问题的两种求解方式

1、线性规划问题的两种求解方式线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重 要分支，它是辅助人们进行科学管理的一种数学方法。线性规划所研究的是：在 一定条件下，合理安排人力物力等资源，使经济效果达到最好。一般地，求线性 目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。解决线性规划问题常用的方法是图解法和单纯性法，而图解法简单方便，但 只适用于二维的线性规划问题，单纯性法的优点是可以适用于所有的线性规划问 题，缺点是单纯形法中涉及大量不同的算法，为了针对不同的线性规划问题，计 算量大，复杂繁琐。在这个计算机高速发展的阶段，利用Excel建立电子表格模 型，并

2、利用它提供的“规划求解”工具，能轻松快捷地求解线性模型的解。无论利用哪种方法进行求解线性规划问题，首先都需要对线性规划问题建立 数学模型，确定目标函数和相应的约束条件，进而进行求解。从实际问题中建立 数学模型一般有以下三个步骤；1、根据所求目标的影响因素找到决策变量；2、由决策变量和所求目标的函数关系确定目标函数；3、由决策变量所受的限制条件确定决策变量所要满足的约束条件。以下是分别利用单纯形法和Excel表格中的“规划求解”两种方法对例题进 行求解的过程。例题：某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所 需的设备台时分别为1台时、2台时，所需原材料A分别为4单位、0单位，

3、所 需原材料B分别为0单位、4单位，工厂中设备运转最多台时为8台时，原材料 A、B的总量分别为16单位、12单位。每生产出I、II产品所获得的利润为2和 3,问I、II两种产品的生产数量的哪种组合能使总利润最大？这是一个典型的产品组合问题，现将问题中的有关数据列表1-1如下：表1-1III限量设备128台时原材料A4016单位原材料B0412单位所获利润23首先对例题建立数学模型。问题的决策变量有两个：产品I的生产数量和产品II的生产数量；目标是总利润最大；需满足的条件是：(1)两种产品使用设备的台时 =台时限量值(2)生 产两种产品使用原材料A、B的数量 =0。一设x1、x2分别表示产品I、

4、II的产量，由于资源限量的限制，可用不等式表示资源总量的约束条件：x1+2 x2 8 ； 4 x1 16 ； 4 x2 12 ；该工厂的目标是在不超过所有资源限量的条件下，如何确定产量x1、x2以得到最大的利润。若用z表示利润，这时z=2x1+3x2综合上述，该问题可用数学模型表示为：目标函数 max z=2x1+3x2满足约束条件：f x1+2 x2 84 x1 16| 4 x2 0利用单纯形法进行求解，则例题的标准型为：maxZ=2x 1+3x2+0 x3+0 x4+0 x5x1+2 x2+x3=84 x1+x4T64 x2+x5=12x. 0 j=1,2,5(1)根据标准型，取松弛变量x

5、3,x4,x5为基变量，它对应的单位矩阵为基，这就得 到初始基可行解X(0)=(0,0,8,16,12)t将有关数字填入表中，得到初始单纯形表，见表1-2表1-2c230000CbXbbx1x2x3x4x50 x381210040 x41640010一0X512040013。23000(2)因检验数都大于零，且须找出换入换出变量，继续进行计算;Max(。1,。2)=max(2,3)=3，对应的 变量x2为换入变量，计算。=min(8/2,-,12/4)=3所以它所在行对应的x5为换出变量。x2所在列和x5所在行的交叉处4称为主 元素。(4)以4为主元素进行初等行变换，使P2变换为(0,0,1)

6、 t，在XB列中将x2 替换x5，于是得到新表1 -3。c230000CbXbbx1x2x3x4x50 x321010-1/220 x4164001043x.301001/4一。2000-3/4b 列的数字是 x3=2, x4 =16, x2=3于是得到新的基可行解X(1)=(0,3,2,16,0)t,目标函数的取值z=9(5)检查表1-3的所有。，这时有。j2 ；说明x1应为换入变量。重复(2)(4)的计 算步骤，得表1-4。c230000CbXbbx1x2x3x4x52x121010-1/2一0 x4800-41243x2301001/412。00-201/4c230000CBXbbx1x

7、2x3x4x52x141001/400 x5400-21/213x22011/2-1/80000-3/2-1/80(4)表1-4最后一行的所有检验数已为负数或零，这表示目标函数值已不可能再 增大，于是得到最优解X*=X(3)=(4,2,0,0,4)t目标函数值z=14二、利用Excel表格进行线性规划求解将单纯形表中的有关数据输入到Excel中，建立如图1所示的电子表格模型。 被输入已知数据的单元格是数据单元格，如单元格C5:D8,G5:G7。决策变量(即 两种产品每周的生产量)放在单元格C9和D9，正好定位在这些产品所在列的数 据单元格下面，这种含有需要做出决策的单元格是可变单元格。单元格E

8、5:E7 是用来计算各个工厂每周的总生产时间，如单元格E5就是用C5:D5和C9:D9的 对应数值各自相乘再总加得到。Excel中有一个叫SUM PRODUC I的函数能对相 等行数和相等列数的两个变化范围的单元格中的值乘积后进行加和。被加和的每 个值是对每一个变化范围的一些值和对应位置的第二个变化范围的一些值的积。 如E5=SUM PRODUCT(C5:D5,C9:D9)是把C5:D5变化范围的每个值与C9:D9变 化范围中对应的每个值相乘，然后各个积相加。同样E6=SUM PRODUCT(C6:D6,C9:D9)，E7=SUM PRODU CT(C7:D7,C9:D9)，E5、E6、E7这

9、些单元格的数值是依赖于可变单元格的，它们是输出单元格。单 元格F5、F6、F7中的“=”符号表示它们左边的总值不允许超过列G中的对应 数值，体现了函数的约束条件。目标函数值(利润)被放在E8单元格，正好在用 来帮助计算总利润的数据单元格右边，与列E中的其它的数据相象，它也是一 些乘积的加和，E8=SUM PRODUCT(C8 : D8,C9 : D9)，E8是特殊的输出单元格，是显示目标函数值的，是目标单元格。在没有计算之 前，可变单元格和输出单元格的数值均显示为0。图1ABCDEFG1234III使用资源量资源总量5设备120=86A400=167B040=128所荻利润2309结论ouEx

10、cel中有一个叫“规划求解”的工具，能快速求解线性规划问题，步骤如 下：1在工具菜单中选择“规划求解”，会弹出一个对话框。在对话框中，将 E8键入目标单元格，将C9:D9键入可变单元格，既然目标是要最大化目标单元 格，还必须选中“最大值”。2点击对话框中的“添加”按纽，弹出添加约束对话框，将约束条件具体 化。左端输入范围E5:E7，右端输入范围G5:G7，中间的符号可选择“=”。如 果还要添加更多的函数约束就再点击“添加”按钮以弹出一个新的添加约束对话 框，在这个例子中没有其它约束了。下一步只要点击“确定”按钮回到“规划求 解”对话框。3点击“选项”按钮，在新弹出的对话框中，选中“采用线性模型

11、”和“假 定非负”选项，这就告诉了计算机要求解的问题是一个线性规划问题以及非负约 束，点击“确定”再回到“规划求解”对话框。4点击“求解”按钮，计算机会在后台开始对问题进行求解。几秒钟之后 会显示运行结果，一般而言，它会显示已经找到一个最优解。如果模型没有可行 解或没有最优解，对话框会显示“规划求解找不到可行解”。求解模型之后，最 优值就代替了可变单元格中的初始值，最优解是每周4个I产品和2个II产品， 目标单元格的对应数值（最大利润）为14。求解的电子表格模型（图2）如下：图2ABCDEG1234III使用资源量资源总量5设备128=86A4016=167B048=128所获利润23149结论42线性规划问题的数学模型是描述实际问题的抽象的数学形式，它反映了客观 事物数量间的本质规律。电子表格模型和数学模型两种形式是等价的。电子表格 模型的建