线性规划和匈牙利法
二、生产任务分配的匈牙利法
在实际的生产管理工作中，常会遇到这样的问题，就是如何根据生产作业汁划将不同任务在不同的工人(或班组)之间分配，使完成任务总的消耗时间或费用最小。解决这类问题的简便而有效的方法是匈牙利法，它是由匈牙利数学家D. Konig所提出。
例有4项任务A、B、C、D，分别由甲、乙、丙、丁4个人去完成，规定每人承担其中一项任务，不同的人完成同一任务所花时间(h)不同，见表3-3，求如何分配，使完成这4项任务的总时间最小。
匈牙利法求解此问题的步骤是：
1）按表3-3列出矩阵
2)将矩阵作行、列约简：首先进行行约简。在矩阵的每一行中选取最小元素，
然后将该行的各元素都减去此数，得到如下新矩阵
行约简是比较一名工人担任不同任务时所花的时间，各行中减去最小值后的时间表示该工人担任其它任务时，所多花费的时间，每行中的“0”表示该工人承担这项任务最有利。然后将经过行约筒后的矩阵中没有“0”的列再进行约简，即从该列中选出最小元素，并将其它元素减去此数，得到新矩阵
列约简是比较一项任务有不同工人承担所托时间，各列中减去最小值后的时间表示任务由其他工人担任时，所多花费的时间，每列中的“0”表示这项任务由该工人承担最有利。
3) 检验是否已得最优分配方案；作零的覆盖线，即对有“0”的行和列，划上一条覆盖线，能覆盖所有零元素的最少覆盖线数称为维数，当覆盖线的维数等于矩阵阶数时，可知已得最优分配方案，若维数小于阶数，再作调整。本例可用三条覆盖线覆盖住所有零元素，维数是3，矩阵的阶数是4，维数不等于阶数，因此矩阵还必须调整。
4) 矩阵的调整。在上述矩阵中．有三种元素，一种是无线覆盖元素，另一种是单线覆盖元素，还有一种是双线覆盖元素。在无线覆荒元素中找出最小值，本例为“1”，将无线覆盖得元素都减去“1”，而双线覆盖的元素加上“1”，单线覆盖的元素不变。这样得到新矩阵
5) 再检验——作覆盖线，方法与步骤3相同。现在的最少覆盖线数为4，与矩阵阶数相等，可知已能进行最优分配。
6) 确定最优分配方案。进行具体分配时，可以对只有一个零元素的列(行)先分配(记√号)，分配后，划去与该零元素同行(列)的其他零元素(记×号)这样依改做完各列(行)，得到分配结果。如果矩阵能通过直接观察找到位于不同行不同列的零元素，那么就可以直接确定分配方案。
最优分配方案：甲——D，乙——B，丙——A，丁——C。
总消耗工时为：Z=7+5+4+5=21 (h)。
（注：文件素材和资料部分来自网络，供参考。请预览后才下载，期待你的好评与关注。）
图解法和单纯形法求解线性规划问题
图解法和单纯形法求解以下线性规划问题 1.1 图解法解线性规划问题 只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下： (1)以变量x1为横坐标轴，x2为纵坐标轴，适当选取单位坐标长度建立平面坐标直 角坐标系。由变量的非负性约束性可知，满足该约束条件的解均在第一象限内。 (2)图示约束条件，找出可行域（所有约束条件共同构成的图形）。 (3)画出目标函数等值线，并确定函数增大（或减小）的方向。 (4)可行域中使目标函数达到最优的点即为最优解。 然而，由于图解法不适用于求解大规模的线性规划问题，其实用意义不大。 1.2 单纯形法解线性规划问题 它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。 单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。 单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 1.3 线性规划问题的标准化 使用单纯形法求解线性规划时，首先要化问题为标准形式
16991-运筹学-习题答案选01_线性规划和单纯形法
运筹学教程（胡运权主编，清华第4版）部分习题答案（第一章）1.1 （1）无穷多解：α (6/5, 1/5) + (1- α) (3/2, 0)，α∈ [0,1]。 （2）无可行解； （3）x* = (10,6)，z* = 16； （4）最优解无界。 1.2 （1）max z’ = 3x1 - 4x2 + 2x3 - 5x’4 + 5x’’4 s.t. –4x1 + x2 – 2x3 + x’4– x’’4 = 2 x1 + x2 – x3 + 2x’4– 2x’’4 + x5 = 14 –2x1 + 3x2 + x3 – x’4+ x’’4– x6 = 2 x1, x2, x3, x’4, x’’4, x5, x6 ≥ 0 （2）max z’ = 2x’1 + 2x2 – 3x’3 + 3x’’3 s.t. x’1 + x2 + x’3 – x’’3 = 4 2x’1 + x2 – x’3 + x’’3 + x4 = 6 x’1, x2, x’3, x’’3, x4, ≥ 0 1.3 （1）基解：(0, 16/3, -7/6, 0, 0, 0)； (0, 10, 0, -7, 0, 0)； (0, 3, 0, 0, 7/2, 0)，是基可行解，z = 3，是最优解； (7/4, -4, 0, 0, 0, 21/4)； (0, 16/3, -7/6, 0, 0, 0)； (0, 0, -5/2, 8, 0, 0)； (1, 0, -1/2, 0, 0, 3)； (0, 0, 0, 3, 5, 0)，是基可行解，z = 0； (5/4, 0, 0, -2, 0, 15/4)； (3/4, 0, 0, 0, 2, 9/4)，是基可行解，z = 9/4； (0, 0, 3/2, 0, 8, 0)，是基可行解，z = 3，是最优解。 （2）基解：(-4, 11/2, 0, 0)； (2/5, 0, 11/5, 0)，是基可行解，z = 43/5； (-1/3, 0, 0, 11/6)； (0, 1/2, 2, 0)，是基可行解，z = 5，是最优解；
匈牙利法真题演练
匈牙利法真题演练（07年5月）： 某车间产品装配组有王成、赵云、江平、李鹏四位员工.现有A、B、C、D 四项任务，在现有生产技术组织条件下，每位员工完成每项工作所需要的工时如表1所示。问：请运用匈牙利法求出员工与任务的配置情况，以保证完成任务的总时间最短，并求出完成任务的量短时间。 表1 王成赵云江平李鹏 工作 任务 员工 A 10 5 9 18 B 13 18 6 12 C 3 2 4 4 D 18 9 10 16 解题步骤： 1、建立矩阵 105918（-5） 1318612（-6） 3244（-2） 1891016（-9） 2、行列约减 5 0 4 13 7 12 0 6 1 0 2 2 9 0 1 7 （-1）（-2） PS：行约减以后需要检查列是否都有“0”
3、盖“0” 4 0 4 11 6 12 0 4 0 0 2 0 8 0 1 5 “盖0”只有三条，需要找出剩下数字中最小约数 4、继续约减，交叉处加上约数 3 0 3 10 6 13 0 4 0 1 2 0 7 0 0 4 当我们做完第三步会发现盖0线的数目仍然小于矩阵维数，继续寻找最小约数 将未被盖0线覆盖的数字都减去最小约数，同时在盖0线交叉点上的数字加上这个最小约数 5、数据转化 0 0 3 7 3 13 0 1 0 4 5 0 4 0 0 1 四条盖0线，四个维度，进行求最优解，首先只有一个0的行列，打钩 6、求最优解 0√0× 3 7 3 13 0√ 1 0× 4 5 0√ 4 0√0× 1 得到最优解如下：王—A；赵—D；江—B；李—C。 对照工时消耗表，完成任务的总时间为10+9+6+4=29
线性规划和匈牙利法
二、生产任务分配的匈牙利法 在实际的生产管理工作中，常会遇到这样的问题，就是如何根据生产作业汁划将不同任务在不同的工人(或班组)之间分配，使完成任务总的消耗时间或费用最小。解决这类问题的简便而有效的方法是匈牙利法，它是由匈牙利数学家D. Konig所提出。 例有4项任务A、B、C、D，分别由甲、乙、丙、丁4个人去完成，规定每人承担其中一项任务，不同的人完成同一任务所花时间(h)不同，见表3-3，求如何分配，使完成这4项任务的总时间最小。 匈牙利法求解此问题的步骤是： 1）按表3-3列出矩阵 2)将矩阵作行、列约简：首先进行行约简。在矩阵的每一行中选取最小元素， 然后将该行的各元素都减去此数，得到如下新矩阵 行约简是比较一名工人担任不同任务时所花的时间，各行中减去最小值后的时间表示该工人担任其它任务时，所多花费的时间，每行中的“0”表示该工人承担这项任务最有利。然后将经过行约筒后的矩阵中没有“0”的列再进行约简，即从该列中选出最小元素，并将其它元素减去此数，得到新矩阵 列约简是比较一项任务有不同工人承担所托时间，各列中减去最小值后的时间表示任务由其他工人担任时，所多花费的时间，每列中的“0”表示这项任务由该工人承担最有利。 3) 检验是否已得最优分配方案；作零的覆盖线，即对有“0”的行和列，划上一条覆盖线，能覆盖所有零元素的最少覆盖线数称为维数，当覆盖线的维数等于矩阵阶数时，可知已得最优分配方案，若维数小于阶数，再作调整。本例可用三条覆盖线覆盖住所有零元素，维数是3，矩阵的阶数是4，维数不等于阶数，因此矩阵还必须调整。
4) 矩阵的调整。在上述矩阵中．有三种元素，一种是无线覆盖元素，另一种是单线覆盖元素，还有一种是双线覆盖元素。在无线覆荒元素中找出最小值，本例为“1”，将无线覆盖得元素都减去“1”，而双线覆盖的元素加上“1”，单线覆盖的元素不变。这样得到新矩阵 5) 再检验——作覆盖线，方法与步骤3相同。现在的最少覆盖线数为4，与矩阵阶数相等，可知已能进行最优分配。 6) 确定最优分配方案。进行具体分配时，可以对只有一个零元素的列(行)先分配(记√号)，分配后，划去与该零元素同行(列)的其他零元素(记×号)这样依改做完各列(行)，得到分配结果。如果矩阵能通过直接观察找到位于不同行不同列的零元素，那么就可以直接确定分配方案。 最优分配方案：甲——D，乙——B，丙——A，丁——C。 总消耗工时为：Z=7+5+4+5=21 (h)。
线性规划及单纯形法习题
第一章 线性规划及单纯形法习题 1.用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。 （1）??? ??≥≥+≥++=0,42266432min 2121212 1x x x x x x x x z (2) ??? ??≥≥+≥++=0,12432 223max 2 121212 1x x x x x x x x (3) ?? ? ??≤≤≤≤≤++=8 3105120 106max 21212 1x x x x x x z (4) ??? ??≥≤+-≥-+=0,2322 265max 1 2212121x x x x x x x x z 2.将下列线性规划问题化成标准形式。 (1)????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43214321432143214321,0,,2321422 245243min x x x x x x x x x x x x x x x x x x x x z (2) ????? ? ?≥≤≥-++-≤-+-=++-+-=无约束 32143213213213 21,0,023*******min x x x x x x x x x x x x x x x x z 3.对下列线性规划问题找出所有基本解，指出哪些是基可行解，并确定最优解。 (1) ??? ?? ? ?=≥=-=+-+=+++++=)6,,1(0231024893631223min 61432143213 21Λj x x x x x x x x x x x x x x z j (2) ??? ??=≥=+++=+++++-=)4,,1(0102227 4322325min 432143214321Λj x x x x x x x x x x x x x z j 4.分别用图解发法和单纯形法求解下述问题，并对照单纯形表中的各基本可行解对应图解法中可行域的哪一顶点。
匈牙利算法
匈牙利算法是一种用于在多项式时间内解决任务分配问题的组合优化算法，它推广了后来的原始对偶方法。美国数学家哈罗德·库恩（Harold Kuhn）于1955年提出了该算法。该算法之所以称为匈牙利算法，是因为该算法的很大一部分是基于前匈牙利数学家DéNESK?nig和Jen?egerváry的工作。 概念 在介绍匈牙利算法之前，我想介绍一些概念。接下来的M是G 的匹配项。 如果是，则边缘已经在匹配的M上。 M交织路径：P是G的路径。如果P中的边缘是属于m的边缘，而不属于m但属于G的边缘是交替的，则p是M交织的路径。例如：路径。 M饱和点：例如，如果V与M中的边相关联，则称V为m饱和，否则V为非m饱和。如果它们全部属于m饱和点，则其他点都属于非m饱和点。 M扩展路径：P是m隔行扫描路径。如果P的起点和终点均为非m饱和点，则p称为m增强路径。例如（不要与流网络中的扩展路径混淆）。 寻找最大匹配数的一种显而易见的算法是先找到所有匹配项，然后保留匹配数最大的匹配项。但是该算法的时间复杂度是边数的指数函数。因此，我们需要找到一种更有效的算法。本文介绍了一种使用扩展路径查找最大匹配的方法（称为匈牙利算法，由匈牙利的
Edmonds于1965年提出）。 增强导轨（也称为增强导轨或交错导轨）的定义 如果P是连接图G中两个不匹配顶点的路径，并且属于m和不属于m的边缘（即，匹配边缘和待匹配边缘）在P上交替，则p称为相对于M. 从增强路径的定义可以得出三个结论 （1）P的路径数必须为奇数，并且第一个边缘和最后一个边缘都不属于M。 （2）通过将m和P取反可以获得更大的匹配度。 （3）当且仅当没有M的增强路径时，M是G的最大匹配。 算法概述： （1）将M设置为null （2）通过XOR操作找到扩展路径P并获得更大的匹配项而不是m （3）重复（2），直到找不到增强路径
最新单纯形法解线性规划问题
一、用单纯形第Ⅰ阶段和第Ⅱ阶段解下列问题 s.t. 解：1)、将该线性问题转为标准线性问题 一、第一阶段求解初始可行点 2)、引入人工变量修改约束集合 取人工变量为状态变量，问题变量和松弛变量为决策变量，得到如下单纯形表，并是所有决策变量的值为零，得到人工变量的非负值。 2 -2 -1 1 2 1 1 -1 -1 1 2 -1 -2 1 2 5 -2 -4 1 -1 1 5 0 0 0 0 0 3)、对上述单纯形表进行计算，是目标函数进一步减小，选为要改变的决策变量，计算改变的限值。 2 -2 -1 1 2 1 1 1 -1 -1 1 0 2 -1 -2 1 2 0 5 -2 -4 1 -1 1 5 1 0 0 0 0 0 0 1 0 0 0 4)、由于，为人工变量，当其到达零值时，将其从问题中拿掉保证其值不会再变。同时将以改变的决策变量转换为状态变量。增加的值使目标函数值更小。 1 -3 1 1 1 0 1 1 -1 1
1 -3 1 1 1 0 0 0 0 0 0 0 0 5）使所有人工变量为零的问题变量的值记为所求目标函数的初始可行点，本例为， 二、第二阶段用单纯形法求解最优解 -2 2 1 0 1 1 -1 0 -2 1 2 1 5 1 3 要使目标函数继续减小，需要减小或的值，由以上计算，已经有两个松弛变量为零，因此或不能再减小了，故该初始可行点即为最优解。
2、求解问题 s.t. 如果目标函数变成，确定使原解仍保持最优的c值范围，并把目标函数最 大值变达成c的函数。 解：先采用单纯形法求解最优解，再对保持最优解时C值的范围进行讨论。 1）将问题华为标准线性问题 s.t. 2）用单纯形表表示约束条件，同时在不引入人工变量的前提下，取松弛变量得初始值为零值，求解初始解和最优解 10 -1 -1 -1 10 -20 1 5 1 -20 -2 -1 -1 0 0 0 0 要使目标函数继续减小，可以增大，增大的限值是10。 10 -1 -1 -1 10 0 -20 1 5 1 -20 -10 -2 -1 -1 0 -20 0 0 0 10 0 0 3）转轴。将为零的松弛变量和决策变量交换进行转轴 10 -1 -1 -1 10 -10 4 0 -1 -10 0 -20 1 1 2 -20
线性规划单纯形法(例题)
《吉林建筑工程学院城建学院人文素质课线性规划单纯形法例题》 ? ? ??≥=+ +=+++++=?? ? ??≥≤+≤++=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
浅析指派问题的匈牙利解法成稿讲解
浅析指派问题的匈牙利解法 胡小芹 数学科学学院数学与应用数学学号:040414057 指导教师:苏孟龙 摘要:对于指派问题,可以利用许多理论进行建模并加以解决,但匈牙利解法是解决指派问题的一种非常简单有效的方法,并且可以解决多种形式的指派问题,但匈牙利算法本身存在着一些问题,本文主要介绍了匈牙利算法的基本思想,基本步骤,以及它的改进方法.在匈牙利算法的基础上,本文还介绍了两种更简便实用的寻找独立零元素的方法——最小零元素消耗法和对角线法. 关键词:指派问题;匈牙利解法;最小零元素消耗法;对角线法 0 引言 在现实生活中经常会遇到把几个任务分派给几个不同的对象去完成,由于每个对象的条件不同,完成任务的效率和效益亦不同.指派问题的目标就是如何分派使所消耗的总资源最少（或总效益最优）,如给工人分派工作,给车辆分配道路,给工人分配机床等等,同时许多网络问题（如旅行问题,任务分配问题,运输问题等）,都可以演化成指派问题来解决.在现实生活中,指派问题是十分常见的问题,而匈牙利解法是解决指派问题的一种非常简单有效的方法.本文主要介绍匈牙利解法的基本原理及思想,解题步骤,不足与改进,以使匈牙利法更能有效地解决指派问题. 1 指派问题及其数学模型 指派问题是指由m项任务,需要n个人来承担,每人只能承担一项任务,且每项
任务只能有一人来承担,由于各人的专长不同,各人完成的任务不同,导致其效率也各不相同.因此,就产生怎样科学地指派任务,才能使完成各项任务所消耗的总资源最少（或总成本最低等）,由于n m ,不同,指派问题可分为以下三种情况: 第一、当n m =时,即为每人指派一项任务. 第二、当n m >时,即任务数〉人数,这时可虚设)(n m -个人构成m m ?的 效率矩阵,并且这)(n m -个人在执行这m 项任务时的效率应该是效率最高. 第三、当n m <时,即配置人数〉任务数,这时应虚设)(m n -项任务,并且这n 个人在执行这)(m n -项任务时的成本最低. 通过虚设任务或人,指派问题的效率矩阵都可以转化成方阵.匈牙利解法要求指派问题最小化,其数学模型为 设用0ij c >(,1,2, ,)i j n =表示指派第i 个人去完成第j 项任务时所用的时间, 定义决策变量 10ij i j x i j ?=??表示第个人完成第项任务, 表示不指派第个人完成第项任务. 则问题可转化为0-1线性规划问题: ∑∑===n j ij n i c Z 11min t s ? 1 1 1,1,2,,, 1,1,2,,,01,i,j 1,2,,n n ij i n ij j ij x j n x i n x ==?==???==???==?? ∑∑或. 如果指派问题要求的是最大化问题如F max ,则可以转化为最小化问题,一般方法是:取max (,1,2 ),ij M c i j n ==令(,1,2,)ij ij b M c i j n =-=,则11 min ,n n ij i j f b ===∑∑,max F nM f F =-有从而求. 2 指派问题的解法——匈牙利解法
线性规划与单纯形法
第1章 线性规划与单纯形法 1、用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷最优解、无界解还是无可行解。 ??? ??≥≥+≥++=0 x x 42x 4x 66x 4x 3x 2x minz )a (21 21212 1， ?? ? ??≥≥+≤++=0 x ,x 124x 3x 2 x 2x 2x 3x maxz )b (2121212 1 ?? ???≤≤≤≤≤++=8x 310x 5120 10x 6x x x maxz )c (21 212 1 ?? ? ??≥≤+-≥-+=0 x ,x 23x 2x 2x 2x 6x 5x maxz )d (2121212 1 2、用单纯形法求解下列线性规划问题。 ?????≥ ≤+≤++=0 x ,x 82x 5x 94x 3x 5x 10x maxz )a (21 2 121 2 1 ????? ? ? ≥ ≤+≤+≤+=0 x ,x 5x x 242x 6x 155x x 2x maxz )b (2 1 212 122 1 3、用大M 法和两阶段法求解下列线性规划问题，并指出属于哪一类解。 ??? ?? ??≥≥-≥+-≥+++-=0 x x x 0 x 2x 2x 2x 6 x x x 2x x 2x maxz )a (3 , 2,132 3 13213 21 ??? ??≥≥+≥++++=0 x , x ,x 6 2x 3x 82x 4x x x 3x 2x minz )b (3 21 2 1 3 21 3 21 4、已知线性规划问题的初始单纯形表（如表1所示）和用单纯形法迭代后得到的表（如表2所示）如下，试求括弧中未知数a ～l 的值。 表1
第一章线性规划及单纯形法习题
第一章 线性规划及单纯形法习题 1.用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。 （1）??? ??≥≥+≥++=0,42266432min 2121212 1x x x x x x x x z (2) ??? ??≥≥+≥++=0,12432 223max 2 121212 1x x x x x x x x (3) ?? ? ??≤≤≤≤≤++=8 3105120 106max 21212 1x x x x x x z (4) ??? ??≥≤+-≥-+=0,2322 265max 1 2212121x x x x x x x x z 2.将下列线性规划问题化成标准形式。 (1)????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43214321432143214321,0,,2321422 245243min x x x x x x x x x x x x x x x x x x x x z (2) ????? ? ?≥≤≥-++-≤-+-=++-+-=无约束 32143213213213 21,0,023*******min x x x x x x x x x x x x x x x x z 3.对下列线性规划问题找出所有基本解，指出哪些是基可行解，并确定最优解。 (1) ??? ?? ? ?=≥=-=+-+=+++++=)6,,1(0231024893631223min 61432143213 21 j x x x x x x x x x x x x x x z j (2) ??? ??=≥=+++=+++++-=)4,,1(0102227 4322325min 432143214321 j x x x x x x x x x x x x x z j 4.分别用图解发法和单纯形法求解下述问题，并对照单纯形表中的各基本可行解对应图解法中可行域的哪一顶点。
2-线性规划问题的图解法
第二节 线性规划问题的图解法 对一个线性规划问题，建立数学模型之后，面临着如何求解的问题。这里先介绍含有两个未知变量的线性规划问题的图解法，它简单直观。 图解法的步骤： 步骤1：确定可行域。 第1步： 绘制约束等式直线，确定由约束等式直线决定的两个区域中哪个区域对应着由约束条件所定义的正确的不等式。我们通过画出指向正确区域的箭头，来说明这个正确区域。 第2步：确定可行域。 步骤2：画出目标函数的等值线，标出目标值改进的方向。 步骤3：确定最优解。用图示的方式朝着不断改进的目标函数值的方向，移动目标函数的等值线，直到等值线正好接触到可行域的边界。等值线正好接触到可行城边界的接触点对应着线性优化模型的最优解。 例1－3，用图解法求解线性规划问题 12 12121212max 23221228..416412,0 z x x x x x x s t x x x x =++≤??+≤??≤??≤?≥?? 解： 图1－3 （1） 画出线性规划问题的可行域，它是为以O(0,0)、A(0,3)、B(2,3)、C(4,2)、 D(0,4)为顶点的凸5边形，如图1－3。 （2） 画出一条目标函数的等值线12236x x +=，图1－3中红颜色的虚 线。
（3） 目标函数的等值线往上移动时，目标函数值增大（图1－3中红颜 色的实线）。由于问题的解要满足全部约束条件，因此目标函数的 等值线要与可行域有交点。当目标函数的等值线移动到 122314x x +=时，它与可行域只有一个交点，再往上移动时，与 可行域不再有交点。这就是说最优解为：124,2x x ==，最优目标 函数值为14。 例1-3中求解得到问题的最优解是唯一的，但对一般线性规划问题，求解结果还可能出现以下几种情况： （1）唯一最优解（2）多重最优解。 （3）无界解。 （4）无可行解。 这里我们不再举例，请大家自己阅读教材。 当线性规划问题的求解结果出现（3）、（4）两种情况时，一般说明线性规划问题建模有错误。前者缺乏必要的约束条件，后者是有矛盾的约束条件，建模时应注意。
使用单纯形法解线性规划问题
使用单纯形法解线性规划 问题 The Standardization Office was revised on the afternoon of December 13, 2020
使用单纯形法解线性规划问题 要求：目标函数为：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 =-=-++ .： 1234123561371234567211 42321,,,,,,0x 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，做出单纯形表如下： 表一：最初的单纯形表 3） 换入变量有两种取法，第一种取为x 2，相应的换出变量为x 6，进行第一 次迭代。迭代后新的单纯形表为： 表二：第一种换入换出变量取法迭代后的单纯形表
由于x1和x5对应的系数不是0就是负数，所以此时用单纯形法得不到最优解。 表一中也可以把换入变量取为x3，相应的换出变量为x7，进行一次迭代后的单纯形表为： 表三：第二种换入换出变量取法迭代后的单纯形表 4）表三中，取换入变量为x2，换出变量为x6，进行第二次迭代。之后的单纯形表为： 表四：第二次迭代后的单纯形表 5）表四中，取换入变量为x7，换出变量为x3，进行第三次迭代。之后的单纯形表为： 表五：第三次迭代后的单纯形表
线性规划的单纯形法表格方法
线性规划的单纯形法表格方法 Max. z=5x 1+2x 2+3x 3 -x 4 +x 5 s.t. x 1+2x 2+2x 3 +x 4 =8 3x 1+4x 2+x 3 +x 5 =7 x j ≥0 j=1,2,3,4,5 表1 由表的中间行可求出基本可行解，令x1=x2=x3=0,由约束条件得 x4=8,x5=7. 表中最后一行分别为： ()1787811-=+-=???? ??-=z ()3)31(53111511=+--=???? ??--=-z c ()0)42(24211222=+--=???? ??--=-z c ()4)12(31211333=+--=??? ? ??--=-z c 因为c j -z j 行中存在正值，所以当前基本可行解不是最优解。c j -z j 行中的4最大因而非基变量 X 3使z 有最大的单位增量，把X 3选作新的（换入）基变量。 为确定被换出的基变量，采用最小比值法。用X 3列的值除以约束条件的常数（8/2=4，7/1=7）。第一行有最小比值，把它叫做旋转行。第一行原来的基变量是X 4 ，此时X 4为换出基变量，新的基变量为X 3、X 5。为此需要把表中X 3对应在约束条件中系数变为单位值（1，0）。在表1中：1）用2除旋转行使X 3系数为1；2）用-1/2乘旋转行加到第二行消去X 3。 ()153123413=+=???? ??=z ()1455/2/2113511=-=???? ??-=-z c ()-4623113222=-=???? ??-=-z c ()-21-11/2-21/13-133=-=??? ? ??-=-z c 因为c j -z j 行中仍存在正值，所以当前基本可行解不是最优解。c j -z j 行中的1最大因而非基变 量X 1使z 有最大的单位增量，把X 1选作新的（换入）基变量。
单纯形法求解线性规划的步骤
单纯形法求解线性规划的步骤 1>初始化 将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都是非负的(否则无解),接下来的m列组成一个m*m的单元矩阵(目标行的单元格则不必满足这一条件),这m列确定了初始的基本可行解的基本变量,而表格中行用基本变量来表示 2>最优化测试 如果目标行的所有单元格都是非负的(除了最右列中代表目标函数值的那个单元格),就可以停止了,该表格代表了一个最优解,它的基本变量的值在最右列中,而剩下的非基本变量都为0 3>确定输入变量 从目标行的前n个单元格中选择一个负的单元格(选择绝对值最大的那个)该单元格所在的列确定的输入变量及主元列 4>确定分离变量 对于主元列的每个正单元格,求出θ比率(如果主元格的单元格为负或为0,说明该问题是无解的,算法终止),找出θ比率最小的列,改行确定了分离变量和主元行 5>建立下一张表格 将主元行的所有单元格除以主元得到新的主元行,包括主元行在内的每一行,要减去改行主元列单元格和新主元行的成绩(除主元行为1外,这一步将主元列的所有单元格变成0).把主元列的变量名进行代换,得到新的单纯形表,返回第一步 为求简单 在本程序中,需要自己建立标准矩阵(比如加入松弛变量等工作需要用户自己完成),程序的输入有两种方式: 1:指定行和列,由用户自行输入每一个元素SimpleMatrix(introw=0,int col=0); 2:直接在主程序中初始化一个二维数组,然后利用构造函数SimpleMatrix(introw,int col,double **M) 来初始化和处理(本程序所用的实例用的是这种方法) 程序中主要的函数以及说明 ~SimpleMatrix(); 销毁动态分配的数组.用于很难预先估计矩阵的行和列,所以在程序中才了动态的内存分配.需要重载析构函数 bool Is_objectLine_All_Positive();其中row2为主元所在的行,col为主元所在的列,row1为要处理的行 void PrintAnswer();数不合法"<