运筹学实用教程_(1)

《运筹学实用教程_(1)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学实用教程（第二版）第一部分：线性规划海南大学旅游学院第一章线性规划的基本理论及其应用1.1线性规划的数学模型及其标准型1.2线性规划问题的图解法1.3线性规划问题的单纯形解法1.4非标准型线性规划问题的解法1.5对偶问题1.6灵敏度分析1.7运输规划问题1.8整数规划问题1.9工作指派问题1.10线性规划在管理决策中的应用第一节线性规划的数学模型及其标准型线性规划问题的数学模型线性规划问题的标准型线性规划问题的数学模型例1.1某汽车厂生产大轿车和载重汽车，所需资源、资源可用量和产品价格如下表所示:大轿车载重汽车可用量钢材（吨）221600工时(小时)52.52500座椅400

2、（辆）获利(千元/辆)43问应如何组织生产才能使工厂利润最大？例1.1的数学模型s.t.例1.4下料问题某工厂要做100套钢架，每套有长2.9米、2.1米和1.5米的圆钢组成，已知原料长7.4米，问应如何下料使需用的原材料最省。解：如果从每根7.4米长的原料上各截一根2.9米、2.1米和1.5米长的圆钢，则还余0.9米，用100根原料，浪费预料共90米。现采用套裁的办法，设计五种方案，如表1.2所示。表1.2圆钢套裁方案方案长度一二三四五2.92.11.513210221213合计(米）料头(米）7.407.30.17.20.27.10.36.60.8例1.4数学模型标准型标准型的矩

3、阵式例1.1的标准型第二节线性规划问题的图解法例1.1的图解法可行解及可行解集的特性线性规划问题解的特点单纯形法的思路图1-1可行解及可行解集凸集凸集的顶点（角顶）可行解、可行域，基本可行解，可行基线性规划的可行域是凸集，且顶点个数有限基本可行解是凸集的顶点（角顶）图1-2线性规划问题解的特点若线性规划问题存在唯一的最优解，那么它必定在角顶上（基本可行解）若线性规划问题存在多个最优解，那么必有相邻的角顶是最优解，其它最优解可以表示成这几个角顶的凸组合。只存在有限的角顶可行解。若一个角顶的目标函数值比它所有的相邻角顶的目标函数值要好的话，它就是最优解。图1-3单纯形法的思路从某个角顶可

4、行解开始---起步向目标函数值更好的邻近可行顶点移动判断此顶点是否为最优解：检查它是否比它的临近顶点的目标函数值都好，若是，则是最优解；若不是，则重复上述第二步。第三节线性规划问题的单纯形解法线性规划问题解的基本概念单纯形解法解的最优性检验表解形式的单纯形法单纯形解法的一些问题及其处理方法一、线性规划问题解的基本概念可行解最优解基本解可行基及基本可行解代数解与几何解的关系单纯形法的要点图1-4二、单纯形解法建立基本可行解计算变量的检验数判断是否最优若不是最优解，换基计算新的基本可行解迭代计算直到求得最优解或可判断无最优解为止建立初始基本可行基对于小于等于情况，通过标准化，每个约束条件

5、的左边加上了一的松弛变量，该松弛变量的系数矢量时单位矢量。当约束条件的右手项都大于等于零时，可令松弛变量为初始基本可行基。例1.1的标准型线性方程组的增广矩阵表示它的初始可行基初始基本可行解初始基变量是松弛变量。初始可行解（只要满足非负条件）初始基本可行解目标函数与最优性检验第一次迭代确定入基变量，应当是，它的系数是4。确定出基变量，方法如下，得确定新基和求解新的基本可行解新基新的基变量：新的基本可行解新的基本可行解和目标函数基本可行解目标函数第二次迭代确定入基变量：确定出基变量：确定新基和求解新的基本可行解新基新的基变量：新的基本可行解新的基本可行解和目标函数基本可行解目标函数第三

6、次迭代确定入基变量：确定出基变量：确定新基和求解新的基本可行解新基新的基变量：新的基本可行解基本可行解目标函数这是最优解。最大目标函数值为2600。新的基本可行解和目标函数三、关于解的最优性检验设线性规划模型为令基为B，并作相应的矩阵分割，从约束条件得代入目标函数得令则目标函数可写成所以可用σ判断是否最优解，它叫做检验数。四、表解形式的单纯形法表的格式在表上的计算方法表上计算的原理表解单纯形法的实例：例1-1表1-5表1-5五、单纯形解法中的一些问题及其处理方法换入变量的选择问题下标最先原则检验数最大原则换出变量的选择问题比值最小原则下标最先原则无换出变量的情况—无界解非基变量检验数

7、有等于零—多个最优解的情况第四节非标准线性规划问题的解法目标函数求极小问题等式约束—大M方法大于等于的约束条件常数项为负值的情况允许变量为负值的情况一、目标函数求极小问题目标函数标准化检验数最优解检验规则二、等式约束—大M法人工变量标准化后因没有初始单位可行基，故加人工变量表1-7表1-7三、大于等于的约束条件减去一个松弛，变量化为等式约束加人工变量产生初始基本可行基用大M法例如四、常数项为负值的情况约束条件两边同乘以（-1）标准化：加上松弛变量或减去剩余