当前位置：文档库 › [截距法]解线性规划问题

[截距法]解线性规划问题

由于线性规划的目标函数：z ax by b =+≠()0可变形为，则z b 为直线的纵截距，那么我们在用线性规划求最值时便可以得到如下结论：我们在用线性规划求最值时便可以得到如下结论：

（1）当b >0时，直线所经过可行域上的点使其纵截距最大时，便是z 取得最大值的点；反之，使纵截距取得最小值的点，就是z 取得最小值的点。点；反之，使纵截距取得最小值的点，就是z 取得最小值的点。

（2）当b <0时，与b >0时

情形正好相反，直线所经过可行域上的点使其纵截距最大时，是z 取得最小值的点；使纵截距取得最小值的点，便是z 取得最大值的点。时，是z 取得最小值的点；使纵截距取得最小值的点，便是z 取得最大值的点。例1. 设x,y 满足约束条件x y y x y +≤≤≥????

?10,,,求z x y =+2的最大值、最小值。

解：如图1作出可行域，目标函数z x y =+2表示直线y x z =-+2在y 轴上的截距，可见当直线过A （1，0）时，截距值最大z max =?+=2102，当直线过点O （0，0）时，截距值最小z min =0。

图1

例2. 设x y ,满足约束条件x x y x y ≥≤+≤????

?021,,,求z x y =-32的最大值和最小值。

解：如图2作出可行域，因为由图2可知过点B 时纵截距最大，z x y =-32取得最小

值，所以z min =?-?=-30212；过点A 时纵截距最小，z 在A （1313

,）处取最大值，z max =?-?=31321313

。

图2

(完整版)简单的线性规划问题(附答案)

简单的线性规划问题 [ 学习目标 ] 1.了解线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念 .2. 了解线性规划问题的图解法，并能应用它解决一些简单的实际问题．知识点一线性规划中的基本概念知识点二线性规划问题 1．目标函数的最值线性目标函数 z＝ax＋by (b≠0)对应的斜截式直线方程是 y＝－a x＋z，在 y 轴上的截距是z， b b b 当 z 变化时，方程表示一组互相平行的直线．当 b>0，截距最大时， z 取得最大值，截距最小时， z 取得最小值；当 b<0，截距最大时， z 取得最小值，截距最小时， z 取得最大值． 2．解决简单线性规划问题的一般步骤在确定线性约束条件和线性目标函数的前提下，解决简单线性规划问题的步骤可以概括为：“画、移、求、答”四步，即， (1)画：根据线性约束条件，在平面直角坐标系中，把可行域表示的平面图形准确地画出来，可行域可以是封闭的多边形，也可以是一侧开放的无限大的平面区域．(2)移：运用数形结合的思想，把目标函数表示的直线平行移动，最先通过或最后通过的顶点 (或边界 )便是最优解． (3)求：解方程组求最优解，进而求出目标函数的最大值或最小值． (4)答：写出答案．

知识点三简单线性规划问题的实际应用 1．线性规划的实际问题的类型 (1)给定一定数量的人力、物力资源，问怎样运用这些资源，使完成的任务量最大，收到的效益最大； (2)给定一项任务，问怎样统筹安排，使完成这项任务耗费的人力、物力资源量最小．常见问题有： ①物资调动问题例如，已知两煤矿每年的产量，煤需经两个车站运往外地，两个车站的运输能力是有限的，且已知两煤矿运往两个车站的运输价格，煤矿应怎样编制调动方案，才能使总运费最小？ ②产品安排问题例如，某工厂生产甲、乙两种产品，每生产一个单位的甲种或乙种产品需要的A、B、C 三种材料的数量，此厂每月所能提供的三种材料的限额都是已知的，这个工厂在每个月中应如何安排这两种产品的生产，才能使每月获得的总利润最大？ ③下料问题例如，要把一批长钢管截成两种规格的钢管，应怎样下料能使损耗最小？2．解答线性规划实际应用题的步骤 (1)模型建立：正确理解题意，将一般文字语言转化为数学语言，进而建立数学模型，这需要在学习有关例题解答时，仔细体会范例给出的模型建立方法． (2)模型求解：画出可行域，并结合所建立的目标函数的特点，选定可行域中的特殊点作为最优解． (3)模型应用：将求解出来的结论反馈到具体的实例中，设计出最佳的方案．题型一求线性目标函数的最值 y≤2，例 1 已知变量 x，y 满足约束条件 x＋y≥1，则 z＝3x＋y 的最大值为 ( ) x－y≤1， A ． 12 B ．11 C ．3 D ．－ 1 答案 B 解析首先画出可行域，建立在可行域的基础上，分析最值点，然后通过解方程组得最值点的坐标，代入即可．如图中的阴影部分，即为约束条件对应的可行域，当直线y＝－3x＋z 经 y＝2，x＝ 3，

怎么利用EXCEL求解线性规划

利用线性回归方法求解生产计划方法一： 1、建立数学模型: ①设变量：设生产拉盖式书桌x台，普通式书桌y台，可得最大利润 ②确定目标函数及约束条件目标函数：y = max+ 115 P90 x 约束条件：200 x .....................⑴ +y 10≤ 20 x .....................⑵ 4≤ +y 16 128 x .....................⑶ +y 10 15≤ 220 y x ..........................⑷ ,≥ 2、在Excel中求解线性规划 ①首先，如图1所示，在Excel工作表格输入目标函数的系数、约束方程的系数和右端常数项：图1 ②将目标方程和约束条件的对应公式输入各单元格中 F2=MMULT（B6:C6,F6:F7)； F3=MMULT（B3:C3,F6:F7)； F2=MMULT（B4:C4,F6:F7)； F2=MMULT（B5:C5,F6:F7)；

出现图2样式：图2 线性规划问题的电子表格模型建好后，即可利用“线性规划”功能进行求解。选择“工具”→“规划求解”出现“规划求解参数”窗口，如图3所示: 图3 在该对话框中，目标单元格选择F2，问题类型选择“最大值”，可变单元格选择F6：F7，点击“添加”按钮，弹出“添加约束条件”窗口，如图4所示: 图4

根据所建模型，共有4个约束条件，针对约束（1）：20 x， +y 20 10≤ 左端“单元格所引用位置”选择F3，右端“约束值”选择D3，符号类型选择“<=”，同理继续添加约束（2）（3）（4），完成后选择“确定”，回到“规划求解参数”对话框，如5图所示：图5 ④点击“选项”按钮，弹出“规划求解选项”对话框，选择“采用线性模型”和“假定非负”两项，如图6所示：图6 ⑤点击“确定”→“求解”，选择“运算结果报告”“敏感性报告”“极限值报告”三项，最后点击“确定”，输出结果：运算结果报告：

必修五——线性规划无数个最优解问题、乘1问题-答案

必修五——线性规划无数个最优解问题、乘1问题答案和解析【答案】 1.D 2.A 3.C 4.C 5.A 6.B 7.D 8.B 9.C 10.B 11.B 【解析】 1. 解：作出不等式组{x +y ≥1 x ?y ≥?12x ?y ≤2 表示的平面区域，得到如图的△ABC 及其内部，其中A （1，0），B （0，1），C （3，4）设z =F （x ，y ）=ax +by （a ＞0，b ＞0），将直线l ：z =ax +by 进行平移，当l 经过点C 时，目标函数z 达到最大值 ∴z 最大值=F （3，4）=3a +4b =7，可得17（3a +4b ）=1因此，3a +4b =17 （3a +4b ）（3a +4b ）=17（25+12b a +12a b ） ∵12b a +12a b ≥2√12b a ?12a b =24∴17（25+24）≥17×49=7，即当且仅当a =b =1时，3a +4b 的最小值为7故选：D 作出题中不等式组表示的平面区域，得如图的△ABC 及其内部，再将目标函数z =ax +by 对应的直线进行平移，可得当x =3，y =4时，z 最大值为3a +4b =7．然后利用常数代换结合基本不等式，可得当且仅当a =b =1时，3a +4 b 的最小值为7．本题给出二元一次不等式组，在已知目标函数z =ax +by 最大值为7的情况下求3a +4b 的最小值．着重考查了运用基本不等式求最值和简单的线性规划等知识，属于中档题． 2. 解：满足约束条件{x +y ?4＜0y ≥x x ≥0的可行域如下图所示

∵y?5x?1表示可行域内一点（x ，y ）与P （1，5）连线的斜率又∵k PA =5?41?0=1，k PB =5?22?1=-3， ∴y?5x?1的范围是（-∞，-3）∪（1，+∞）故选A 画出满足约束条件的可行域，分析目标函数的几何意义，数形结合即可分析出目标函数的取值范围．本题考查的知识点是简单线性规划的应用，其中分析出目标函数的几何意义是表示可行域内一点（x ，y ）与P （1，5）连线的斜率是解答的关键． 3. 解：由约束条件{y ≥0 y ?x +1≤0y ?2x +4≥0作出可行域如图，由z =y -ax （a ≠0），得y =ax +z ， ∵a ≠0， ∴要使z =y -ax （a ≠0）取得的最优解（x ，y ）有无数个， a 不能为负值，当a ＞0时，直线y =ax +z 与线段AC 所在直线重合时，使z =y -ax 取得最大值的最优解有无数个；直线y =ax +z 与线段BC 所在直线重合时，使z =y -ax 取得最小值的最优解有无数个．

使用Excel规划求解解线性规划问题

使用Excel规划求解解线性规划问题引言最近，开始学习运筹学，期望通过学习后能够解决许多困扰自已的难题。刚开始时，选了很多教材，最后以Hamdy A.Taha著的《Operations Research:An Introduction》开始学习。（该书已由人民邮电出版社出版，书名《运筹学导论-初级篇（第8版）》，不知为什么，下载链接中只有该书配套的部分习题解答，而书中所说的光盘文件找不到下载的地方，因为中译本没有配光盘，因此也就错过了许多示例文件。不知道哪位有配套光盘文件，可否共享？？？）线性规划求解的基本知识线性规划模型由3个基本部分组成： ?决策变量（variable） ?目标函数（objective） ?约束条件（constraint）示例：营养配方问题（问题）某农场每天至少使用800磅特殊饲料。这种特殊饲料由玉米和大豆粉配制而成，含有以下成份：特殊饲料的营养要求是至少30%的蛋白质和至多5%的纤维。该农场希望确定每天最小成本的饲料配制。（解答过程）因为饲料由玉米和大豆粉配制而成，所以模型的决策变量定义为： x1=每天混合饲料中玉米的重量（磅） x2=每天混合饲料中大豆粉的重量（磅）目标函数是使配制这种饲料的每天总成本最小，因此表示为： min z=0.3×x1+0.9×x2 模型的约束条件是饲料的日需求量和对营养成份的需求量，具体表示为： x1+x2≥800 0.09×1+0.6×2≥0.3(x1+x2) 0.02×1+0.06×2≤0.05(x1+x2) 将上述不等式化简后，完整的模型为：

min z=0.3×1+0.9×2 s.t.x1+x2≥800 0.21×1-0.3×2≤0 0.03×1-0.01×2≥0 x1,x2≥0 可以使用图解法确定最优解。下面，我们介绍使用Excel的规划求解加载项求解该模型。使用Excel规划求解解线性规划问题步骤1安装Excel规划求解加载项单击“Office按钮——Excel选项——加载项——（Excel加载项）转到”，出现“加载宏”对话框，如下图所示。选择“规划求解加载项”，单击“确定”。此时，在“数据”选项卡中出现带有“规划求解”按钮的“分析”组，如下图所示。步骤2设计电子表格使用Excel求解线性规划问题时，电子表格是输入和输出的载体，因此设计良好的电子表格，更加易于阅读。本例的电子表格设计如下图所示：

简单线性规划问题教案

332简单线性规划问题 “简单的线性规划”是在学生学习了直线方程的基础上，介绍直线方程的一个简单应用，这是《新大纲》对数学知识应用的重视?线性规划是利用数学为工具，来研究一定的人、财、物、时、空等资源在一定条件下，如何精打细算巧安排，用最少的资源，取得最大的经济效益?它是数学规划中理论较完整、方法较成熟、应用较广泛的一个分支，并能解决科学研究、工程设计、经营管理等许多方面的实际问题?中学所学的线性规划只是规划论中的极小一部分，但这部分内容体现了数学的工具性、应用性，同时也渗透了化归、数形结合的数学思想，为学生今后解决实际问题提供了一种重要的解题方法一一数学建模法.通过这部分内容的学习，可使学生进一步了解数学在解决实际问题中的应用，培养学生学习数学的兴趣和应用数学的意识和解决实际问题的能力依据课程标准及教材分析，二元一次不等式表示平面区域以及线性规划的有关概念比较抽象，按学生现有的知识和认知水平难以透彻理解，再加上学生对代数问题等价转化为几何问题以及数学建模方法解决实际问题有一个学习消化的过程，故本节知识内容定为了解层次本节内容渗透了多种数学思想，是向学生进行数学思想方法教学的好教材，也是培养学生观察、作图等能力的好教材本节内容与实际问题联系紧密，有利于培养学生学习数学的兴趣和“用数学”的意识以及解决实际问题的能力教学重点重点是二元一次不等式（组）表示平面的区域教学难点难点是把实际问题转化为线性规划问题，并给出解答?解决难点的关键是根据实际问题中的已知条件，找出约束条件和目标函数，利用图解法求得最优解?为突出重点，本节教学应指导学生紧紧抓住化归、数形结合的数学思想方法将实际问题数学化、代数问题几何化课时安排2课时三维目标一、知识与技能 1. 掌握线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念； 2. 运用线性规划问题的图解法，并能应用它解决一些简单的实际问题I 二、过程与方法 1. 培养学生观察、联想以及作图的能力，渗透集合、化归、数形结合的数学思想，提高学生“建模”和解决实际问题的能力； 2. 结合教学内容，培养学生学习数学的兴趣和“用数学”的意识，激励学生创新. 三、情感态度与价值观 1. 通过本节教学着重培养学生掌握“数形结合”的数学思想，尽管侧重于用“数”研究“形”，但同时也用“形”去研究“数”，培养学生观察、联想、猜测、归纳等数学能力； 2. 结合教学内容，培养学生学习数学的兴趣和“用数学”的意识，激励学生勇于创新.

图解法和单纯形法求解线性规划问题

图解法和单纯形法求解以下线性规划问题 1.1 图解法解线性规划问题只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下： (1)以变量x1为横坐标轴，x2为纵坐标轴，适当选取单位坐标长度建立平面坐标直角坐标系。由变量的非负性约束性可知，满足该约束条件的解均在第一象限内。 (2)图示约束条件，找出可行域（所有约束条件共同构成的图形）。 (3)画出目标函数等值线，并确定函数增大（或减小）的方向。 (4)可行域中使目标函数达到最优的点即为最优解。然而，由于图解法不适用于求解大规模的线性规划问题，其实用意义不大。 1.2 单纯形法解线性规划问题它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 1.3 线性规划问题的标准化使用单纯形法求解线性规划时，首先要化问题为标准形式

表格法解线性规划问题

表格法解线性规划问题【教学目标】知识目标：理解用表格法解线性规划问题的方法和步骤. 能力目标：通过例子详细地介绍了表格法解线性规划问题的过程，并引入了线性规划标准型的概念，归纳总结了表格法解线性规划问题的步骤. 【教学重点】理解用表格法解线性规划问题的方法和步骤. 【教学难点】理解用表格法解线性规划问题的方法和步骤. 【教学设计】 1、表格法也称单纯形法，是解线性规划问题的常用方法，使用该方法时，首先要将一般的线性规划问题化为标准型.在教材中给出了化标准型的方法.讲解时一定要注意b≥0以及变量的非负性. 2、表格法解线性规划问题的过程，教材中归纳为五个步骤，这实际上是一个算法，可以利用前面介绍过的算法知识来学习. 3、初始表格中初始解组的确定是关键，一般可取松弛变量，但当标准型中没有这样的变量满足初始解组的要求时，通常要通过添加人工变量来解决，本教材没有就这方面的问题进行深入讨论（一般的运筹学教材中都可找到该容）. 4、表格在转换时（通常称为转轴），教材中提到用加减消元法来转轴.教师可就这部分容作适当的讲解. 5、由于通常的表格转换要进行多次，而表头部分是不变的，因此可以将多表格合并起来，具体样式可参见5.5节表5-16.

【教学过程】 5.3.1线性规划问题的标准形式求线性规划问题的图解法虽然直观简便，但对多于两个变量的情况就不能适用了，对于多于两个决策变量的线性规划问题，可以用什么方法呢？下面介绍一种用表格的方法来求解线性规划问题的解. 表格法是根据单纯形法而专门设计的一种计算表格. 单纯形法（Simple Method ）是求解线性规划问题的主要方法，该法由丹赛（Dantzig ）于1947年提出，后经过多次改进而成，是求解线性规划问题的实用算法.由上节的叙述可知，如果线性规划问题的最优解存在，则必定可以在其可行解集合的顶点（极点）中找到．因此，寻求一个最优解就是在其可行域的各个极点中搜索最优点.单纯形法实质上是一个迭代过程，该迭代即是从可行域的一个极点移到另一个近邻的极点，直到判定某一极点为最优解为止. 为使用表格法，首先介绍线性规划问题的标准形式. 一般的线性规划问题中目标函数可能是求最大(或最小)值，而线性约束条件中可能是线性方程，也可能是线性不等式，约束条件中约束方程（或不等式）的个数也未必就比决策变量的个数少，这些问题对于线性规划的求解，带来极大的不便，为此，引入下述标准形式：求目标函数最大值 n n x c x c x c x c Z ++++=...m ax 332211 (用和式表示为j j n j x c Z ∑==1max )

如何认识线性规划实际问题中有关最优解的精确问题

如何认识线性规划实际问题中有关最优解的精确问题课本线性规划第二节，提到两个实际问题，一个要求将最优解精确到0.1，一个要求将最优解是整数，如果说师生们对例4的答案还可接受的话，那么，例3到最后四舍五入式的解答实在让人难以把握，况且最优解应为（12.3，34.5），那么关于这种最优解需要得到精确的题目有没有统一的解答步骤，我的回答是有。在实际问题中，可行域一般都是一整片区域不存在间断现象，所以题目所要求的最优解无论精确到0.1还是精确到0.01，符合要求的最优解都确实存在在可行域中，我们要做的应该是把它找出来，而不是通过任何手段去精确。如何才能把它找出来呢？我的办法是，不考虑x、y需要精确的要求，先依其他条件列出不等式组，作出可行域，求出符合题中其他条件的最优解，然后看此最优解是否符合题目要求，若符合，则即为所求解．若不符合，则应继续滑动参照线，求出经过可行域内的符合要求的且与原点距离最远（或最近）的点的直线，在该线经过可行域的部分上寻找最优解即可。具体操作请看以下示范课本例3、某工厂生产甲、乙两种产品，已知生产甲种产品1t需消耗A种矿石10t、B种矿石5t、煤4t；生产乙种产品1t需消耗A种矿石4t、B种矿石4t、煤9t。每1 t甲种产品的利润是600元，每1 t甲种产品的利润是1000元。工厂在生产这两种产品的计划中要求消耗A种矿石不超过300t、B种矿石不超过200t、煤不超过360t。甲、乙两种产品应各生产多少（精确到0.1t），能使利润总额达到最大？解：设生产甲、乙两种产品分别为x t、y t，利润总额为z元，那么

104300542004936000 x y x y x y x y +≤??+≤?? +≤??≥?≥?? Z=600x+1000y 作直线l ：600x+1000y=0 即直线l ：3x+5y=0 把直线l 向右上方平移，使其划过可行域，此时3x+5y>0 当直线经过点M 3601000 (,)2929时3x+5y 达到最大,即z 也达到最大，此时3x+5y=6080 29 ≈209.655, 若要将最优解精确到0.1，需将直线向回平移到3x+5y=209.6 由35209.649360 x y x y +=??+=? 得到3x+5y=209.6与可行域左边界的交点A （12.343,34.514）由35209.654200x y x y +=??+=? 得到3x+5y=209.6与可行域右边界的交点B （12.431,34.462）可知有可能成为最优解的点的横坐标为12.4 代入3x+5y=209.6得到纵坐标约为34.48，不符合题目精确到0.1要求

线性规划单纯形法(例题)

《吉林建筑工程学院城建学院人文素质课线性规划单纯形法例题》 ? ? ??≥=+ +=+++++=?? ? ??≥≤+≤++=0 ,,,24 261553).(002max ,,0,24 261553).(2max 14.1843214213 214 321432121212 1x x x x x x x x x x t s x x x x z x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。分别用图解法和单纯形）】（页【为初始基变量，选择43,x x )1000(00)0010(01 )2050(12)6030(24321=?+?-==?+?-==?+?-==?+?-=σσσσ 为出基变量。为进基变量，所以选择41x x

3 /1)6/122/10(00 )0210(03 /1)3/1240(10)1200(24321-=?+-?-= =?+?-==?+?-==?+?-=σσσσ 为出基变量。为进基变量，所以选择32x x 24 /724/528/11012/112/124/1100 021110 120124321-=?+-?-=-=-?+?-==?+?-==?+?-=）（）（）（）（σσσσ 4 33 4341522max , )4 3,415(),(2112= +?=+===x x z x x X T T 故有：所以，最优解为

??? ??? ?≥=+ +=+=+ ++++=?????? ?≥≤+≤≤+=0,,,,18232424).(0002max ,,,0 ,182312212 ).(52max 24.185432152142315 43215432121212 1x x x x x x x x x x x x t s x x x x x z x x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。分别用图解法和单纯形）】（页【 )000010(00001000000000100520200052300010254321=?+?+?-==?+?+?-==?+?+?-==?+?+?-==?+?+?-=σσσσσ）（）（）（）（为出基变量。为进基变量，所以选择42x x

1用“线性规划问题的最优解在边界上”简解高考题

用“线性规划问题的最优解在边界上”简解高考题线性规划问题是指在线性约束条件(即关于变量y x ,的二元一次不等式或不等式组)下，求线性目标函数by ax z +=的最大值或最小值问题.在线性规划问题中，满足线性约束条件的解),(y x 叫做可行解，可行解的集合叫做可行域(可行域的边界是直线、射线或线段)，使目标函数取得最值的可行解叫做这个线性规划问题的最优解.求解线性规划问题，通常是通过平移初始直线0=+by ax 来解决的，所以有下面的结论： (1)若线性规划问题存在最优解，则最优解一定在边界上. (2)若目标函数by ax z +=在两个不同的点B A ,处均取到最大值或均取到最小值，则初始直线0=+by ax 与直线AB 平行(此时线段AB 一定是可行域的边界，且线段AB 上的所有点都是最优解). (3)若可行域有凸顶点，则目标函数在可行域的所有凸顶点处的函数值中的最大(小)值就是目标函数的最大(小)值. 下面用这些结论简解几道线性规划题. 题1 (2015年高考山东卷理科第6题)已知x ，y 满足约束条件?????x －y ≥0，x ＋y ≤2，y ≥0. 若z ＝ax ＋y 的最大值为4，则a ＝( ) A ．3 B ．2 C ．－2 D ．－3 解 B.题中的可行域为图1中的OAB ?(其顶点坐标分别是)0,2(),1,1(),0,0(B A O )及其内部的区域. 图1 再由结论(3)，可得3=a 或2.再检验，得2=a . 题2 (2015年高考福建卷文科第10题)变量x ，y 满足约束条件?????x ＋y ≥0，x －2y ＋2≥0，mx －y ≤0. 若z ＝

使用单纯形法解线性规划问题

使用单纯形法解线性规划问题要求：目标函数为：123min 3z x x x =-- 约束条件为： 123123 1312321142321,,0 x x x x x x x x x x x -+≤??-++≥?? -+=??≥? 用单纯形法列表求解，写出计算过程。解： 1）将线性规划问题标准化如下：目标函数为：123max max()3f z x x x =-=-++ s.t.： 123412356 1371234567211 42321,,,,,,0 x x x x x x x x x x x x x x x x x x x -++=??-++-+=??-++=??≥? 2）找出初始基变量，为x 4、x 6、x 7，做出单纯形表如下：表一：最初的单纯形表变量基变量 x 1 x 2 x 3 x 4 x 5 x 6 x 7 b i x 4 1 -2 1 1 0 0 0 11 x 6 -4 1 2 0 -1 1 0 3 x 7 -2 0 1 0 0 0 1 1 -f -3 1 1 3）换入变量有两种取法，第一种取为x 2，相应的换出变量为x 6，进行第一次迭代。迭代后新的单纯形表为：表二：第一种换入换出变量取法迭代后的单纯形表变量基变量 x 1 x 2 x 3 x 4 x 5 x 6 x 7 b i x 4 -7 5 1 -2 2 3

x2-4120-1103 x7-20100011 -f10-101-10-3 由于x1和x5对应的系数不是0就是负数，所以此时用单纯形法得不到最优解。表一中也可以把换入变量取为x3，相应的换出变量为x7，进行一次迭代后的单纯形表为：表三：第二种换入换出变量取法迭代后的单纯形表变量基变量x1x2x3x4x5x6x7 b i x43-20100-110 x60100-11-21 x3-20100011 -f-110000-1-1 4）表三中，取换入变量为x2，换出变量为x6，进行第二次迭代。之后的单纯形表为：表四：第二次迭代后的单纯形表变量基变量x1x2x3x4x5x6x7 b i x43001-22-512 x20100-11-21 x3-20100011 -f-10001-11-2 5）表四中，取换入变量为x7，换出变量为x3，进行第三次迭代。之后的单纯形表为：表五：第三次迭代后的单纯形表变量基变量x1x2x3x4x5x6x7 b i x4-7051-22017 x2-4120-1103 x7-20100011 -f10-101-10-3可以看出，此时x1，x5对应的系数全部非零即负，故迭代结束，没有最优解。结论：综上所述，本线性规划问题，使用单纯形法得不到最优解。

《运筹学》使用Excel求解线性规划问题

第三节使用Excel 求解线性规划问题利用单纯形法手工计算线性规划问题是很麻烦的。office 软件是一目前常用的软件，我们可以利用office 软件中的Excel 工作表来求解本书中的所有线性规划问题。对于大型线性规划问题，需要应用专业软件，如Matlab ，Lindo ，lingo 等，这些软件的使用这里我们不作介绍，有需要的，自己阅读有关文献资料。用Excel 工作表求解线性规划问题，我们需要先设计一个工作表，将线性规划问题中的有关数据填入该工作表中。所需的工作表可按下列步骤操作：步骤1 确定目标函数系数存放单元格，并在这些单元格中输入目标函数系数。步骤2 确定决策变量存放单元格，并任意输入一组数据。步骤3 确定约束条件中左端项系数存放单元格，并输入约束条件左端项系数。步骤4 在约束条件左端项系数存放单元格右边的单元格中输入约束条件左端项的计算公式，计算出约束条件左端项对应于目前决策变量的函数值。步骤5 在步骤4的数据右边输入约束条件中右端项（即常数项）。步骤6 确定目标函数值存放单元格，并在该单元格中输入目标函数值的计算公式。例建立如下线性规划问题的Excell 工作表： 12 121 21212max 1502102310034120..55150,0 z x x x x x x s t x x x x =++≤??+≤??+≤??≥? 解：下表是按照上述步骤建立的线性规划问题的Excell 工作表。其中： D4=B2*B4+C2*C4, D5=B2*B5+C2*C5 , D6=B2*B6+C2*C6, C7= B2*B1+C2*C1 。建立了Excel 工作表后，就可以利用其中的规划求解功能求相应的线性规划问题的解。求解步骤如下：步骤1 单击[工具]菜单中的[规划求解]命令。步骤2 弹出[规划求解参数]对话框，在其中输入参数。置目标单元格文本框中输入目标单元格；[等于]框架中选中[最大值＼最小值］单选按钮。步骤3 设置可变单元格区域，按Ctrl 键，用鼠标进行选取，或在每选一个连续区域后，在其后输入逗号“，”。步骤4 单击[约束］框架中的[添加]按钮。步骤5 在弹出的[添加约束]对话框个输入约束条件．步骤6 单击[添加]按钮、完成一个约束条件的添加。重复第5步，直到添加完所有条件步骤7 单击[确定]按钮，返回到[规划求解参数]对话框，完成条件输入的[规划

线性规划最优解的几种可能情况

线性规划最优解的几种可能情况： 1.有唯一的最优解（可行域为封闭的有界区域、可行域为非封闭的无界区域） 2.有一个以上的最优解（可行域为封闭的有界区域、可行域为非封闭的无界区域） 3.无界解（目标函数无界，即虽有可行解，但在可行域中，目标函数可以无限增大或无限减小） 4.无可行解（可行域为空集） Min型与Max型单纯形表的唯一区别：检验数反号 Min型单纯形表中 -当检验数均大于等于零时为最优； -令负检验数中最小的对应变量为换入变量。 Max型单纯形表中 -当检验数均小于等于零时为最优； -令正的检验数中最大的对应变量为换入变量。 ①②②③④⑤⑤⑥⑴⑵⑵⑶ 解的几种情况在单纯形表上的体现（Max型）： 1）唯一最优解判别：最优表中所有非基变量的检验数非零,则线性规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。 3）无界解判别：某个检验数大于零且换入变量对应的列中所有的分量皆非正，则线性规划具有无界解。 4）无可行解的判断：当用大M单纯形法计算得到最优解并基变量中还存在非零人工变量时，则表明原问题无可行解。 5）退化解的判别：存在某个基变量为零的基本可行解。 4.2 对偶问题的基本性质 1.对称性对偶问题的对偶是原问题。 2.弱对偶性若X是原问题的可行解，Y是对偶问题的可行解，则存在求目标函数最大化时，在单纯形表中： ①如果检验数均非正，而b列中有负值，这时使用对偶单纯形法； ②如果所有bi ≥0, 检验数有正值，使用单纯形法: ③如果b列中有负值，且检验数中有正值，这时必须引入人工变量，建立新的单纯形表，重新计算

若是某线性规划问题的最优解,则也是该问题的最优解 ( )

试题 16 一、填空题 1. 滞后效应速度分析的常用指标有_____________________，____________________。 2. 使用阿尔蒙估计法须事先确定：__________________，_______________________。 3. 考耶克模型可以描述的两个最著名的理论假设是：__________________________和_______________________。 4. 联立方程中的变量分为：_________________和__________________。 5. 联立方程模型有两种基本形式：__________________和___________________。二、判断题 1. 若21,X X 是某线性规划问题的最优解，则）（）101(21≤≤-+=λλλX X X 也是该问题的最优解。（） 2. 用单纯形法求解标准型的线性规划问题，当所有检验数0≤-j j z c 时，即可判定表中解即为最优解。（） 3. 数学模型123 1231231212max 3572685820.3412 ,0f x x x x x x x x x s t x x x x =++-≥??++≤??+=??≥?＋为线性规划模型。（） 4. 表达形式i i bx a y +=是正确的。（） 5. 表达形式i i i bx a y ε++=是正确的。（） 6. 表达形式i i x b a y ??+=是正确的。（） 7. 表达形式i i x b a y ???+=是正确的。（） 8. 在存在异方差情况下，常用的OLS 法总是高估了估计量的标准差。（） 9. 当存在序列相关时，OLS 估计量是有偏的并且也是无效的。（） 10. 消除序列相关的一阶差分变换假定自相关系数ρ必须等于1。（）三、问答题 1. 简述古典回归模型的基本假定。 2. 试举出三个模糊集合的例子。 3. 叙述Leslie 人口模型的特点。并讨论稳定状况下种群的增长规律。 4. 静态贝叶斯博弈中参与人的策略有什么特点？为什么？ 5. 有了海萨尼转换，不完全信息动态博弈和完全但不完美信息动态博弈基本上是相同的，，这种论述是否正确？四、计算题 1. 在超市购物时你注意到大包装商品比小包装商品便宜这种现象了吗。比如洁银牙膏50g

线性规划问题及其数学模型

第二章线性规划的对偶理论与灵敏度分析习题 1. 写出下列线性规划问题的对偶问题。 (1)????? ? ?≥=++≤++≥++++=无约束 3213213213213 21,0,5343 32243422min x x x x x x x x x x x x x x x z (2) ????? ? ?≤≥≤++≥-+-=++++=0 ,0,8374355 22365max 3213213213213 21x x x x x x x x x x x x x x x z 无约束 (3)?? ??? ??? ???==≥=====∑∑∑∑====) ,,1;,,1(0) ,,1(),,1(min 1 111n j m i x n j b x m i a x x c z ij m i j ij n j i ij m i ij n j ij (4)???????????=≥++==<=<=∑∑∑===),,,,1(0),,2,1() ,,1(min 1 211111n n j x m m m i b x a m m i b x a x c z j n j i j ij n j i j ij n j j j 无约束 2. 判断下列说法是否正确，为什么? (1)如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； (2)如果线性规划的对偶问题无可行解，则原问题也一定无可行解； ( 3)在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值； (4)任何线性规划问题具有唯一的对偶问题。 3. 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。

用Excel求解线性规划及线性方程组的方法

第23卷总第44期西北民族学院学报(自然科学版)Vol.23,No.2 2002年6月 Journal of N orthw est Minorities U niversity(Natural Science)J une,2002 用Excel求解线性规划及线性方程组的方法王培麟 (番禺职业技术学院,广东番禺511483) [摘　要]对利用美国微软公司开发的Office组件中的电子表格软件Excel求解线性规划的方法给予了介绍,并将该功能给予扩充,给出了用该软件求解线性方程组的方法1 [关键词]Excel;线性规划;求解方法 [中图分类号]TP271+.7 [文献标识码]A [文章编号]1009-2102(2002)02-0037-03 Excel是美国微软公司开发的Office组件中的电子表格软件,它具有强大的电子表格处理功能,使用户能够轻松地制作表格,并具有对数据进行检索、分类、筛选、排序、计算、分析与统计等功能1对大多数用户而言,也许更注重于Excel的表格功能,而对于它的计算功能,特别是数学计算功能可能就不是十分熟悉1本文将介绍用Excel解线性规划及线性方程组的方法与技巧1 1　用Excel解线性规划用Excel解线性规划,必须在Excel系统中加载“规划求解”项目1如果没有,可以启动Excel软件,进入Excel用户界面,然后使用“工具”菜单下“加载宏”菜单项之“规划求解”子项,则可完成“规划求解”项的加载1 下面通过例1的求解来说明使用Excel解线性规划问题的方法1 例1　线性规划模型为: min s=2x1+7x2+4x3+9x4+5x51 S.t　3x1+2x2+x3+6x4+18x5≥700 x1+0.5x2+0.2x3+2x4+0.5x5≥30 0.5x1+x2+0.2x3+2x4+0.5x5=200 x1≤50;x2≤60;x3≤50;x4≤70;x5≤40; x1,x2,x3,x4,x5≥0 1 求解的具体方法为:首先要建立电子表格模型,输入如图1所示的工作表1 工作表的格式不是固定不变的,可根据具体的需要进行调整1建立工作表的步骤为: 1)确定一些单元格来代表决策变量,本例中x1,x2,…,x5为决策变量,需要将它们放到一些单元格中,称为可变单元格1一般地,可变单元格使用Excel的某行一块连续的区域,如 [收稿日期]2002-04-01 [作者简介]王培麟(1963—),男,副教授,硕士,主要从事数学和计算机方面的教学与研究1 — 7 3 —

线性规划问题的最优解

线性规划问题的最优解引言线性规划是运筹学的一个基本分支，其应用极其广泛，其作用以为越来越多的人所重视。线性规划主要就实际问题抽象成数学形式，即求一组变量的值，在满足一定的约束条件下，是某个目标达到最小或最大，而这些约束条件用可以用一组线性不等式或线性方程来表示。而求得目标函数的最优解尤为重要，本文就线性规划问题的最优解求解方法作出阐述，并举出实例加以强化，同时也指出了线性规划问题应用于生产与运作管理的重要性。 1.线性规划问题的最优解探讨 1.1线性规划问题的提出考虑下面的线性规划问题的标准型：目标函数： CX Z =min (1) 约束条件： ? ??≥=0X b AX (2) 其中，),,,(21n c c c C =,T n x x x X ),,,(21 =,T m b b b b ),,,(21 =,n m ij a A ?=)(阶矩阵。设B 是A 中m 个线性无关的列向量构成的一个基，m m ij a B ?=)( 阶矩阵，这样将矩阵A 分成两个部分，即A=),(N B ,X=),(N B X X ,C=()N B C C ,,B X ,B C 为基B 对应的非基变量和系数，N X ,N X 为N 对应的非基变量和系数，这样将线性规划问题改写为： minZ ()N B C C ,=?? ? ???B B X X (3) 约束条件：

?????≥=?? ????0),(N B N B X X b X X N B (4) 经过矩阵变换，得出关于基B 的标准型如下： 1min -=B C Z B +(N C -1-B C B N)N X (5) 约束条件： ???≥=+--0,11N B N B X X b B NX B X (6) T m b b b b B ),,,(' '21'1 =- ?????? ? ? ? =++++++-mn mm mm n m m n m m a a a a a a a a a N B 212221 2121111 将（5）（6）展开为： =Z min ' 1i m i i b c ∑=+ ∑ +=n m j 1 (' 1 ij m i i j a c c ∑=-)j x (7) 约束条件： i n m j j ij i b x a x '1 ' =+ ∑+= ,m i ,,2,1 = (8) 0≥j x ,n j ,,2,1 = (9) 令 ' 1 0i m i i b c Z ∑== , =j σ' 1 ij m i i j a c c ∑=- ,n m m j ,,2,1 ++= ,称j σ为检验数。 1.2最优解判别准则准则一：若 T m b b b X )0,,0,,,,('2'1')1( = ，为对应于基B 的基本可行解，且对于一切的 n m m j ,,2,1 ++= ，j σ>0 ，则X 为线性规划问题的最优解。