第10章 经管专业应用数学.pptVIP

10.5线性规划问题的单纯形解法其中初始基本可行解为(0,0,12,8).列表如表10-6所示.上一页下一页返回10.5线性规划问题的单纯形解法最优解检验规则:当我们找到一个基本可行解之后，要判断它是不是最优解.判断的方法是检查目标函数中的系数是否还有正的系数，若有正系数存在，则说明还有更好的解.如本例上表中目标函数的(6,7,0,0)，这说明当减少x3，x4，时不会使Z的值减少，而增加x1，x2的值却可以使Z的值增加.这说明目前的解不是最优解，只有当目标函数的全部系数为负值或0时，该解才是最优解.进行迭代:确定换人变量，由目标函数可知x2的系数比x1的系数大，即同样增加一个单位的值，7x2增加7,6x1增加6，所以我们选择x2为换入变量.从约束条件中，我们选择同时满足所有约束条件的x2的最大解min{b/xi}.如下表10一7.上一页下一页返回10.5线性规划问题的单纯形解法上一页下一页返回10.5线性规划问题的单纯形解法上一页下一页返回10.5线性规划问题的单纯形解法上一页下一页返回10.5线性规划问题的单纯形解法10.5.3表解形式的单纯形法上面介绍的单纯形法求解计算比较麻烦，所以我们一般采用表解的方法使其规格化.只是需要指明换人变量就可以了.如上例10-8的求解，用表解形式如表10一10.上一页下一页返回10.5线性规划问题的单纯形解法所以线性规划问题的最优解为(3,2)，目标函数的最大值为32.例10-9用表解单纯形解法解下列线性规划问题上一页下一页返回10.5线性规划问题的单纯形解法建立单纯形表如表10-11.上一页下一页返回10.5线性规划问题的单纯形解法上一页下一页返回10.5线性规划问题的单纯形解法上一页下一页返回10.5线性规划问题的单纯形解法建立单纯形表如表10-12上一页下一页返回10.5线性规划问题的单纯形解法此时目标函数的系数全部为负数或零，故基本可行解(4,0,10)为原线性规划问题的最优解，目标函数的最大值为54.上一页下一页返回10.5线性规划问题的单纯形解法10.5.4单纯形解法中的一些问题及其处理方法1.换入变量的选择问题选择换人变量是根据表中的目标函数的系数的正负.一般选取系数最大的变量为换人变量，但有时这不一定是最佳的选择.进一步计算每一种选择下可能达到的最大值Z，则有助于选择更好的优化方向.2.换出变量的选择问题在确定换出变量时，我们一般选择b/xi中最小的正数或零.如b/xi为负数，则不作考虑.如果其中有两个值相同时，应该如何选择呢?3.存在多个最优解的情况在前面图解法中讲过，有的线性规划问题会出现多个最优解，用单纯形解法一也可以这多个最优解.上一页下一页返回10.5线性规划问题的单纯形解法「思考题]什么情况下，线性规划问题无最优解?当线性规划问题得到的变量较多时，我们一般不再用单纯形解法求解，而是选择用计算机软件——LINGO软件直接求解.上一页返回图10.1返回图10.2返回*第10章经管专业应用数学10.1行列式矩阵及其应用(见第3章)10.2概率统计及应用(见第4章)10.3线性规划的数学模型及其标准形式10.4线性规划问题的图解法10.5线性规划问题的单纯形解法返回10.3线性规划的数学模型及其标准形式线性规划是最重要的优化方法.1947年线性规划被成功地运用于工业、交通、农业和军事等各个领域，随着计算机的普及，它的适应领域越来越广泛.线性规划研究的问题主要有两类:一是一项任务确定后，如何统筹安排，尽量做到用最少的人力物力资源去完成这一任务，数学上即是求“最小值”.二是已有一定数量的人力物力资源，如何安排使用他们，使得完成任务最多，数学上即是求“最大值”.其实这两类问题是一个问题的两个方面，就是所谓寻求整个问题的某个整体指标最优的问题.如:生产的组织与计划问题;运输问题;合理下料问题;配料问题;布局问题;分配问题;投资问题，等等.10.3.1线性规划问题的数学模型下一页返回10.3线性规划的数学模型及其标准形式在生产实践和日常生活中，经常会遇到规划问题.所谓规划问题，简单地说，是指如何最合理地利用有限的资源(如资金、劳力、材料、时间等)，以便使生产的消耗最小，利润最大.如果利用数学方法来进行这种分析，这就是数学规划.当所建立的模型，都是线形代数方程时，这就是一个线性规划问题.这样的例