第三章线性规划的解法习题解答090426y

为了求解这个最小化问题，我们把原目标函数改写成：

minZ?x1?x2?x3?x4?x5?x6?0x7?0x8?0x9?Mx10?Mx11?Mx12

这个问题的初始单纯形表如3-18所示：

表3-18 Cj CB XB 1 1 x2 1 x3 1 x4 1 x5 1 x6 0 x7 0 x8 0 x9 M x10 M x11 M x12 b 400 600 900 1900M x1 M x10 M x11 M x12 zj -C j 2 0 0 2M-1 1 1 1 3M-1 1 0 3 4M-1 0 1 3 4M-1 0 2 1 3M-1 0 0 6 6M-1 -1 0 0 ?M 0 -1 0 ?M 0 0 -1 ?M 1 0 0 0 0 1 0 0 0 0 1 0 最终单纯形表如表3-19所示。

表3-19 Cj CB 1 1 1 XB x2 x5 x6 1 1 x2 1 0 0 1 x3 1 -1/2 5/12 1 x4 0 1/2 5/12 1 x5 0 1 0 1 x6 0 0 1 0 x7 -1 1/2 1/12 0 x8 0 -1/2 1/12 0 x9 0 0 -1/6 M x10 1 -1/2 -1/12 5/12 M x11 0 1/2 -1/12 5/12 -M M x12 0 0 1/6 1/6 -M b 400 100 50 550 x1 2 -1 -1/6 5/6 zj -C j 0 -2M -1/12 -1/12 0 0 -5/12 -5/12 -1/6 -M 由最终单纯形表可知：最优解为X=( x1，x2，x3，x4，x5，x6)=(0，400，0，0，100，50)，最优值为minZ?x1?x2?x3?x4?x5?x6?550。即按第2种截法截400根，按第5种截法截100根，按第6种截法截50根，可使用料最省为550根。

本例可推广至一般情形（一维下料问题)，描述如下： 要用某原料（条材或板材）下m种零件A1,A2,,Am的毛坯。根据既节省原

材料又易于现场操作的原则，在一件原材料上已设计出m 种不同的下料方式，其中第j种方式可下得Ai零件aij个(i=1,2,……,m;j=1,2,……,n)。若Ai零件的需要量为bi(i=1,2,……,m)。则应如何下料，才能既满足需要又使所用的原材料最少？

设用第j种下料方式套裁原材料xj (j=1,2,……,m)件，所用原材料总数为z件，则该问题的线性规划模型为：

33

minZ??xjj?1n ?nax?b,(i?1,2,m)i??ijjs.t?j?1?x?0(j?1,2,,n)?j

题型VI 用电子表格(EXCEL)法求解线性规划问题

利用EXCEL中的“规划求解”工具，可以方便地求解线性规划问题。在EXCEL窗口菜单栏的“工具”菜单中选择“加载宏”选项，打开“加载宏”对话框选择添加“规划求解”项。

在应用规划求解工具前，要在EXCEL电子表格中进行合理布局，将决策变量系数A、资源限量常数b、目标函数系数C，以及决策变量、约束函数和目标函数等信息的单元格或单元格区域确定。布局后，再利用EXCEL 的“规划求解”工具求解，得到决策变量和目标函数的最优值，即最优解和最优值。

例3-13 某家具制造厂生产五种不同规格的家具，每件家具都要经过机械成型、打磨和上漆等主要生产工序。每种家具在每道工序所使用的时间、每道工序的可用时间、每种家具的利润等数据如表3-20所示。问工厂应如何安排生产，才能使总利润最大？

表3-20 家具生产数据表

解：根据题意，假设家具制造厂分别生产规格一家具的产量为x1单位，规格二家具的产量为x2单位，规格三家具的产量为x3单位，规格四家具的产量为x4单位，规格五家具的产量为x5单位。因此，可建立线性规划模型如下：

maxz?2.7x1?3x2?4.5x3?2.5x4?3x5?3x1?4x2?6x3?2x4?3x5?3600?4x?3x?5x?6x?4x?3950 ?12345s..t??2x1?3x2?3x3?4x4?3x5?2800??x1,x2,x3,x4,x5?0下面用电子表格(EXCEL)方法求解该线性规划问题。 (1)数据在表格中的布局。家具生产数据布局如表3-21所示。

在表3-21中，数据布局与表3-20中的格式基本相同。为了计算方便，

34

我们任意设定一些单元格，以存放计算公式、决策变量，以及有助于辨识的符号等。在本例中，增加H列中的单元格H5，H6，H7，用于存放约束条件左端的计算公式，其数据表示每个约束条件在对应可行解下的实际取值；增加第11行中的单元格C11，D11，E11，F11，G11，用于存放决策变量及其取值数据，它也是最优解取值的单元格；增加单元格J11，用于存放目标函数计算公式及其目标函数在对应可行解下的取值数据。增加I列中的单元格I5，I6，I7，用于书写约束条件中的连接符号，本例中为“?”。单元格I5，I6，I7不参加实际运算，只用于标识。

表3-21 家具生产数据布局表

(2)输入计算公式。家具生产数据计算公式如表3-22所示。

表3-22 家具生产数据计算公式

在单元格H5，H6，H7中，分别输入计算公式： H5：=SUMPRODUCT(C5:G5,$C$11:$G$11) H6：=SUMPRODUCT(C6:G6,$C$11:$G$11) H7：=SUMPRODUCT(C7:G7,$C$11:$G$11) 在单元格J11中输入计算公式：

J11：=SUMPRODUCT(C9:G9,$C$11:$G$11)

35

(3)应用线性规划求解工具求解。求解步骤如下：

①选中单元格J11，在工具栏中，单击加载宏，选择规划求解； ②在工具栏中，单击规划求解，出现“规划求解参数”界面，如图3-9；

图3-9

在该界面中，要确定四项内容：(A)目标单元格：$J$11 ；(B)等于：指目标函数优化目标，在等于栏中选最大值；(C)可变单元格：$C$11:$G$11 ；(D)约束：$C$11:$G$11。

③在规划求解参数栏中，单击“选项”栏，出现“规划求解选项”界面，如图3-10所示。

图3-10

在界面中分别选择：采用线性模型；假定非负；正切函数；向前差分；牛顿法。单击“确定”按钮，返回到图3-9规划求解参数界面。

④单击求解按钮，出现规划求解结果对话框，如图3-11所示。

36