(1.4.1)--3线性规划的图解法.pdf

运运 筹筹 学学第二章第二章线性规划的图解法线性规划的图解法图解法特点2主 要 内 容1图解法求解线性规划问题例1：某基地有甲、乙两种飞机和 A、B、C 三种类型导弹，已知每种飞机能够携带的导弹数、每种导弹的总数以及各种飞机单次任务毁伤敌方目标的概率如下：一、引入该基地应该如何安排飞机配置导弹，才能最大平均期望数地毁伤敌方目标？一、引入每种飞机可携带的各类导弹数量甲型飞机乙型飞机导弹总数A类导弹4324B类导弹2630C类导弹105单次任务毁伤敌方目标概率0.40.6一、引入线性规划数学模型三要素：决策变量、目标函数、约束条件解：假设x1为使用甲型飞机的数量 x2为使用乙型飞机的数量，数学模型为：一、引入1212121120.40.643242630.500Maxzxxxxxxstxxx且为整数一、引入怎么怎么进行求解呢？进行求解呢？在平面上作图进行求解的方法在平面上作图进行求解的方法。一个线性规划问题建立数学模型之后，就面临着如何求解的问题。这里先介绍含有两个决策变量的线性规划问题的图解法。它简单直观，有助于了解线性规划问题求解的基本原理。12,x x二、图解法求解二、图解法求解图解法的步骤可概括为：（1）在平面上建立直角坐标系；(2)图示约束条件，找出可行域（由于，可行域必位于第一象限）；（3）图示目标函数，即画出目标函数等值线；12ox x120,0 xx二、图解法求解图解法的步骤可概括为：（4）对（或）问题朝着增大（或减少）纵截距的方向平行移动目标函数等值线，至与可行域的边界相切时为止，切点（即某个边界点）就是代表最优解的点；（5）寻找该点的坐标得到最优解。max fmin f二、图解法求解二、图解法求解x286422468x1 1100二、图解法求解二、图解法求解1243=24xx121243240,0 xxxx由围成的区域x2x x1 164224681012二、图解法求解二、图解法求解1226=30 xx121226300,0 xxxx由围成的区域x28x x1 1642024681012可行域可行域x x1 1 5 5二、图解法求解二、图解法求解121211243242630500 xxxxxxx由围成的区域122630 xx124324xxx286422468x x1 11012可行域可行域可行域是由约束条件围成的区域，该区域内的每一点都代表着一个可行解，它的全体组成问题的解集合。本问题的可行域是由O，A，B，C，D作为顶点围成的一个凸多边形OABCD二、图解法求解二、图解法求解x286422468x11012可行域可行域OABCD凸集凸集是指集合内任意两点是指集合内任意两点，其两点的连线都在这个集合其两点的连线都在这个集合内内，我们称这个集合为我们称这个集合为凸集凸集。线性规划可行域为线性规划可行域为凸集凸集。二、图解法求解二、图解法求解x286422468x11012可行域可行域OABCD可行域上所求的解可行域上所求的解，我们我们称为称为可行解可行解。使目标函数达到最值的可使目标函数达到最值的可行解行解，我们称为我们称为最优解最优解。二、图解法求解x286422468x x1 11012可行域可行域OABCD目标函数是以目标函数是以Z Z作为作为参数的一组平行线参数的一组平行线二、图解法求解二、图解法求解120.40.6Maxzxx2125=-33xxzx286422468x x1 11012可行域可行域OABCD当该直线移到当该直线移到B B点时，点时，Z（目标函数）（目标函数）值达到最大：值达到最大：Max Z=3.6此时最优解此时最优解=（3，4）二、图解法求解二、图解法求解图解法的优、缺点：优点：简单、好学，计算方便。缺点：只能解决二维的问题。图解法给我们的启示：(1)可行域是一个凸集；(2)最优解在可行域的顶点达到。三、图解法的特点三、图解法的特点结结语语图解法特点21图解法求解二维线性规划问题