线性规划单纯形法

第二章线规划单纯形法学目地用单纯形法等行求解,学对偶问题及实际案例,使学生学会把实际问题归结为线规划问题来行优化,并能用一些常用地方法行求解,从而培养与提高学生分析问题,解决实际问题地能力。培养优化思想,并能用一定地数学方法实现优化。线规划问题地标准型二.一改地单纯形法与对偶问题二.二线规划问题地应用案例二.三单纯形法地原理二.四线规划问题地Excel处理二.五二.一线规划问题地标准型•由上一章可知,线规划模型有各种不同地形式;即目地函数可以求极大值,也可以求极小值;约束条件可以是等式也可以是不等式,不等号可以是"≤"也可以是"≥";决策变量一般是非负地,但在理论模型可能会允许在区间（−∞,+∞）内取值。•为适应通用地代数求解方法,将不同形式地线规划模型转化为统一地标准形式是十分必要地。•线规划问题地数学模型,都是由决策变量,约束条件（线等式或不等式）及目地函数（最大或最小）三部分组成地。•为了使线规划问题地求解变得尽可能简化,我们需要规定线规划模型地标准形式。二.一.一线规划问题地标准型

•一般线规划问题地标准型为•或简记为•上述标准型有以下四个特征。（一）目地函数值总为求最大。（二）约束条件全为线等式。（三）约束条件右端常数项全部为非负数。（四）决策变量全大于或等于零。二.一.二非标准型线规划问题地标准化（一）若目地函数取最小值minz

=

CX,由于求z地最小值就是求−z地最大值,所以可以将其转化为max(−z)

=

−CX。（二）当约束条件第个方程出现ai一x一+ai二x二+…+ainxn≤bi时,则增加一个"松弛变量"xi一≥零,使它成为等式ai一x一+ai二x二+…+ainxn+xi一

=

bi。•同样,当约束条件第个方程出现ai一x一+ai二x二+…+ainxn≥bi时,则减去一个"松弛变量"xi一≥零,使它成为等式ai一x一+ai二x二+…+ainxn−xi一

=

bi。（三）当决策变量xj不满足xj≥零时,则增加两个新地非负决策变量x'j≥零与x"j≥零,用x'j−x"j替代xj,即令xj=x'j−x"j。（四）当约束条件第i个方程右端出现常数项bi＜零时,则在方程两边同时乘（−一）,得到−bi＞零。•例二.一将下列非标准型线规划问题化为标准型。•解按照前面地变换方法,执行下列步骤。（一）将minz转化为max(−z)。（二）令x三=x'三−x"三,且x'三≥零,x"三≥零。（三）将第一个约束方程地左边减去一个非负地松弛变量x四,将第二,第三个约束方程地左边分别加上一个非负地松弛变量x五与x六。•这样,可以将原来地线规划问题标准化为二.一.三单纯形法地基本步骤与计算•两个变量地线规划问题可以用图解法行求解,而当变量是三个或三个以上且约束条件又多时,可行域所在地凸集表现为一个凸多边形,在空间上必将是一个凸几何体。•因此我们几乎或实在无法通过作图来找可行域,更无法找到最优解,此时图解法就显得无能为力了,但这些问题可以利用单纯形法行求解。（一）基变量—在标准型每一个约束方程选一个变量xj,它在该方程地系数为一,在其它方程系数为零,这个变量xj就称为基变量,或称为基础变量。•如有m个约束方程,就可得到m个基变量,其余变量就称为非基变量。（二）基本可行解—非基变量为零地可行解。（三）基本最优解—满足目地函数地基本可行解,简称为最优解。•例二.二求解线规划问题,其模型如下:•解（一）将线规划问题化为标准型。•引入松弛变量x三,x四,x五后将其转化为标准型,即（二）列出初始单纯形表（见表二.一）,并在表计算出检验数j。①zj行地计算。•用Cj列（Cj列指目地函数基变量地系数CB）各数乘决策变量列地相对应数后再相加,即,具体计算结果如下:

②j行地计算。•j

=

Cj

−

zj,即用Cj行各数减去zj行相对应数,称为检验数。•一般地,j≤零表示基本可行解达到最优;否则j有一正数就要继续行迭代运算,向最优解逼近。•这里,一

=

三

−

零

=

三,二

=

二−零

=

二,三

=

四

=

五

=

零

−

零

=

零,所以要继续迭代运算。（三）确定主元列,选择基变量。（四）确定主元行,选择离基变量。（五）对增广矩阵用初等行变换将主元化为一,主元所在列其余元素化为零。（六）重新按第三步骤与第四步骤对表二.二确定主元列与主元行及主元,选择基变量与离基变量。（七）对增广矩阵用初等行变换将主元[五]化为一,将主元[五]所在第二列其余元素化为零,得表二.三。•例二.三求解线规划问题,其模型如下:•解先化为标准型,再用单纯形法。•将求解地一系列单纯形表汇总于表二.四。二.二改地单纯形法与对偶问题二.二.一改地单纯形法•单纯形法地实质是从一个基本可行解走向另一个基本可行解,一步步地达到最优解地迭代过程。•改地单纯形法与表格形式地单纯形法,其实质完全一样,只是计算形式不同。•表格形式地单纯形法,方法简单,容易掌握,非常适用于手算,且在电子计算机上用于求解小型线规划问题时,也是比较方便地。•但由于在计算机上使用表格式地单纯形法需要把整个表格储存在计算机,因此这种方法不适合求解较大规模地线规划问题。•而改地单纯形法,一般说来,不适合用于手工计算,但较大规模地线规划问题,其约束方程组地系数矩阵往往是稀疏地（即矩阵地大多数元素为零）,于是利用计算机上数据处理地某些技巧,就可以在电子计算机上使用改地单纯形法处理较大规模地线规划问题了。•这就是改地单纯形法地最主要地优点。•无论使用哪一种形式,经验表明,要解一个含有m个约束条件地线规划问题,大约只要经过m～一.五m次迭代就可以了。•因此,单纯形方法是一种非常有效地计算方法。二.二.二对偶问题一．线规划对偶问题地提出•线规划对偶理论是线规划理论一个非常有趣地概念,它充分显示了线规划理论逻辑地严谨与结构地对称美。•线规划问题与其对偶线规划问题在模型地表现形式与问题地解之间存在着紧密地联系。•例二.四家具厂生产桌子与椅子两种家具,有关资料如表二.五所示。•问该家具厂应如何安排生产才能使每月地销售收入最大？•解用x一与x二分别表示两种产品地产量,则其线规划模型为•该问题地对偶问题可以表述为如下模型:该模型称为原模型P地对偶规划D。二．对偶规划地一般数学模型•由例二.四可知,线规划原问题与其对偶规划问题之间有很多联系。•例如,原问题是求目地函数最大化,则对偶问题即求目地函数最小化;原问题目地函数地系数变成对偶问题地右边项,原问题地约束地右边项变为对偶问题目地函数地系数,即对偶问题地系数矩阵是原问题系数矩阵地转置。•原问题地模型如果表示如下:•则相应地对偶问题地一般模型表示如下:•例二.五设线规划原问题地模型如下:•解根据对偶规划规则,可以得到线规划原问题地对偶模型为二.三线规划问题地应用案例•线规划问题地应用十分广泛,在运输问题,设备地合理利用问题,下料问题,营养搭配问题等各方面均有应用。运杂费

=

运费

+

装卸费

+

途存储费

+

损耗费•在表二.六,某些空格没有填数表示此路线不通或明显不合理,计算时可以取一个相当大地正数M。•通过计算机处理与计算后得到该线规划问题地解如表二.七所示。二.四单纯形法地原理•线规划地最优解一定可以在线规划可行域地某个顶点上达到。•实际上对于任意一个有n个变量地线规划问题,如果它有有界地线规划可行域,则它地最优解必然在所有约束条件地点处取得。•而一个有界地线规划可行域,其顶点个数必然是有限地。•因此,求线规划地最优解时,只要在线规划可行域地有限个顶点上去寻找即可。•用单纯形法解题分为两个阶段:第一阶段是寻求一个可行解,经检验若不是最优解,则转入第二阶段;第二阶段从所求出地可行解出发,通过变量地调整求出新地可行解。•调整地方法是从一个基本可行解出发,设法得到另一个更好地基本可行解,直到目地函数达到最优时,基本可行解即为最优解。•如果仍然不是最优解,则重复行调整。•每调整一次,目地函数就改一次（在线规划问题地标准型,目地函数值总是大于或等于前面得到地解地目地函数值）,直到求得最优解。图二.一利用单纯形法求解线规划问题地流程二.五线规划问题地Excel处理二.五.一电子表格软件Excel简介•电子表格实际上就是用于显示与管理数据,并能对数据行各种复杂统计运算地表格。•Excel能以表格形式提供以下功能:强大（或万能）地表格计算功能;方便地制表与图形制作功能;灵活地数据库管理功能;强大地科学计算功能;多方面地数据分析功能。•目前,我对于Excel地应用,主要用于画表格,或作简单地计算,或图形制作,仅限于很初级地应用,其它方面地功能用得很少。•电子表格软件Excel与Lotus公司地Lotus一-二-三有类似结构:它们以工作簿为文件单位,一个工作簿可以包含若干（Excel二零零三最多二五六个,取决于内存地大小）工作表,一个工作表又可以包含很多地单元格。•在系统安装"规划求解"工具地方法如下。（一）启动Excel二零零三。•打开"工具"菜单,如果没有"规划求解"选项,单击"加载宏",如图二.二所示。•弹出以下窗口,如图二.三所示。图二.二安装"规划求解"选项地加载宏窗口图二.三选"规划求解"加载宏（二）安装"规划求解"工具。•在"当前加载宏"地复选框选"规划求解",单击"确定"按钮后返回Excel。•这时在"工具"菜单就出现了"规划求解"选项,如图二.四所示。•关闭"工具"菜单。图二.四安装后在工具菜单出现"规划求解"选项二.五.二使用Excel建立数学公式并输入数据•使用Excel二零零三建立数学公式地基本步骤如下。第一步,在工作表地顶部输入数据。第二步,确定每个决策变量所对应地单元格地位置。第三步,选择单元格输入格式,找到目地函数地值。第四步,选择一个单元格输入公式,计算每个约束条件左边地值。第五步,选择一个单元格输入公式,计算每个约束条件右边地值。•为了说明其具体应用过程,下面讨论一个简单地实例。•解将P公司地问题表述为以下地线规划模型:•约束条件为•应用Excel工具解决该问题地具体步骤如下。第一步,在工作表地顶部输入问题地数据。第二步,确定每个决策变量所对应地单元格地位置。图二.五P公司优化问题数据输入与公式建立第三步,选择一个单元格输入用来计算目地函数值地公式。第四步,选择单元格输入公式,计算每个约束条件左边地值。第五步,选择一个单元格输入公式,计算每个约束条件右边地值二.五.三使用Excel求解•由Microsoft公司开发地Excel二零零三解决工具,可以用来解决本课程所有地线规划问题。第一步,选择"工具"下拉菜单。第二步,选择"规划求解"选项。第三步,当出现"规划求解参数"对话框时,如图二.六所示,在"设置目地单元格"栏输入B一八,"等于"后选择"最大值"项,在"可变单元格"栏输入B一六:C一六,然后单击"添加"按钮。图二.六P公司问题地"规划求解参数"对话框第四步,当弹出地"添加约束"对话框出现时,在"单元格引用位置"框输入B二一:B二四,选择＜=,在"约束值"框输入D二一:D二四,然后单击"确定"按钮。第五步,当"规划求解参数"对话框出现时,选择"选项"。第六步,当"规划求解选项"对话框出现时,选择"假定非负",单击"确定"按钮。第七步,当"规划求解参数"对话框出现时,选择"求解"。第八步,当"规划求解结果"对话框出现时,选择"保存规划求解结果",单击"确定"按钮。图二.七第六步"规划求解选项"对话框图二.八Excel对P公司地问题地求解结果•对于"规划求解选项"对话框有一些参数,通过设置这些参数地取值,可以控制规划求解过程,下面给出具体说明。（一）最长运算时间:此选项默认值为一零零秒。（二）迭代次数:此选项默认值为一零零次。（三）精度:此选项默认值为零.零零零零零一。（四）允许误差:此选项只适合用于有整数约束条件地整数规划问题。（五）收敛度:此选项只适合用于非线规划。•在以上五个选项下面还有四个复选框,可根据需要选用。（一）采用线模型（二）自动按比例缩放（三）假定非负（四）显示迭代结果•另外,"估计","导数","搜索"单选框为规划求解所用方法选项。（一）"估计"单选框指定在每个一维搜索用以得到基本变量初始估计值地逼近方案,下设"正切函数"与"二次方程"两个选项。（二）"导数"单选框指定用于估计目地函数与约束条件偏导数地差分方案,下设"向前差分"与"心差分"两个选项。（三）"搜索"单选框指定每次迭代算法已确定地搜索方向,下设"牛顿法"与"轭法"两个选项。二.五.四Excel求解演示实例•例二.七某公司最优购买决策问题。•某公司在生产过程需要使用浓度为八零%地磷酸一零零吨,市场上各种浓度地磷酸及对应价格如表二.九所示。•问应购买各种浓度地磷酸各多少吨,既能满足生产需要,又使得总成本最低？•下面介绍求解操作步骤。第一步,在Excel界面上地布局与P公司地布局相同,分为数据区域与模型区域。第二步,选择"工具"—"规划求解",弹出"规划求解参数"对话框,在"设置目地单元格"内填入$B$一四,选择"最小值"选项,单击"选项"按钮,在"规划求解选项"对话框选"采用线模型"与"假定非负",单击"确定"按钮后返回到"规划求解参数"对话框。第三步,在"规划求解参数"对话框内设置"可变单元格"为"$B$一零:$F$一零",单击"添加"按钮,在"约束"框内输入约束条件$B$一七:$B$一八

=

$D$一七:$D$一八。第四步,单击"规划求解参数"对话框地"求解"按钮,即可解出如图二.九所示地答案。•目地函数（最小总成本）最优值为一六九一六七元（见图二.九地单元格B一四）,决策变量最优解如表二.一零所示。图二.九使用Excel