运筹学总复习

1、运筹学运筹学复习复习第第1章章 绪论绪论用科学方法分析管理及工程问题，为决策提用科学方法分析管理及工程问题，为决策提供依据。供依据。目标：在企业经营内外环境的限制下，实现目标：在企业经营内外环境的限制下，实现资源效用最大。资源效用最大。组织中存组织中存在的问题在的问题定量分析定量分析定性分析定性分析评价与评估评价与评估决策决策第第2章章线性规划及单纯形法线性规划及单纯形法u一般线性规划的数学模型一般线性规划的数学模型u图解法图解法u单纯形法单纯形法u线性规划的一般模型线性规划的一般模型0.,),(.),(.),(.max(min)21221122222121112121112211nmnmmm

2、nnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcz约束条件目标函数u标准形式标准形式0.,.max21221122222121112121112211nmnmmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcz约束条件目标函数I 可行解可行解I 可行域可行域I 最优解最优解I 基基I 基向量基向量I 非基向量非基向量I 基变量基变量I 非基变量非基变量I 基解基解I 基可行解基可行解 建立坐标系建立坐标系 找出可行域找出可行域 绘出目标函数图形绘出目标函数图形 求出最优解求出最优解u 图解法步骤图解法步骤 唯一最优解唯一最优解 无穷多最优解无穷

3、多最优解 无界解（或无最优解）无界解（或无最优解） 无可行解无可行解u线性规划问题解的情况线性规划问题解的情况凸集和顶点凸集和顶点z 线性规划问题的线性规划问题的基可行解基可行解X对应线性对应线性规划问题规划问题可行域（凸集）的顶点可行域（凸集）的顶点。z 若线性规划问题有若线性规划问题有最优解最优解，一定在一，一定在一某个某个顶点得到顶点得到。 单纯形法步骤：单纯形法步骤：K 确定初始基可行解；确定初始基可行解；K 从初始基可行解转换为另一基可行解；从初始基可行解转换为另一基可行解；K 最优性检验和判别。最优性检验和判别。1、线性规划的标准形式、线性规划的标准形式目标函数：目标函数：约束条件

4、：约束条件：1 1221max.nnniiizc xc xc xc x11 11221121 1222221 12212. . .,.0nnnnmmmnnmna xa xa xba xa xa xbsta xaxa xbx xx目标系数目标系数决策决策变量变量技术技术系数系数右右端端项项I 1、min Z=CX max Z= -CXI 2、约束条件为约束条件为“” 转换为转换为“=”方法方法：I 在在s.t.中左端加上一个中左端加上一个“松弛变量松弛变量”，使，使“”变为变为“=”。同时，在目标函数中，令。同时，在目标函数中，令松弛变量的目标系数为松弛变量的目标系数为0。I 3、约束条件为约束

5、条件为“”转换为转换为“=”方法：方法：I 在在s.t.中左端减去一个中左端减去一个“剩余变量剩余变量”，使，使“”变为变为“=”。同时，在目标函数中，令。同时，在目标函数中，令剩余变量的目标系数为剩余变量的目标系数为0。2、非标准形式的标准化方法、非标准形式的标准化方法I 4、决策变量决策变量xi0 xj = - xiI 5、决策变量的符号不受限制决策变量的符号不受限制 xj = xj- xj， xj，xj 0. 2022-3-16143、图解法、图解法 对于只含有两个变量的线性规划问题，可通对于只含有两个变量的线性规划问题，可通过在平面上作图的方法求解。其步骤如下：过在平面上作图的方法求解

6、。其步骤如下： 建立平面直角坐标系；建立平面直角坐标系；图示约束条件，找出可行域；图示约束条件，找出可行域；图示目标函数，即为一条直线；图示目标函数，即为一条直线；将目标函数直线沿其法线方向在可行域边将目标函数直线沿其法线方向在可行域边界平移直至函数达到最优值为止，目标函数界平移直至函数达到最优值为止，目标函数达到最优值的点就为最优点。达到最优值的点就为最优点。4、单纯形法的计算步骤单纯形法的计算步骤R（1）将问题化为标准型；）将问题化为标准型；R（2）求出线性规划的初始基可行解，列出初）求出线性规划的初始基可行解，列出初始单纯形表；始单纯形表；R（3）进行最优性检验：）进行最优性检验： 如果

7、表中所有检验如果表中所有检验数数 ，则表中的基可行解就是问题的最，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。优解，计算停止。否则继续下一步。0 s sjR（4）从一个基可行解转换到另一个目标值）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表。更大的基可行解，列出新的单纯形表。确定换入基的变量。选择确定换入基的变量。选择 ，对应的变，对应的变量量xj作为换入变量，当有一个以上检验数大于作为换入变量，当有一个以上检验数大于0 0时，一般选择最大的一个检验数，即：时，一般选择最大的一个检验数，即： 其对应的其对应的xk作为换入变量。作为换入变量。确定换出变量。根据

8、下式计算并选择确定换出变量。根据下式计算并选择，选，选最小的最小的对应基变量作为换出变量。对应基变量作为换出变量。0|max s ss s s sjjk 0minikikiLaab0 s sj 用换入变量用换入变量xk替换基变量中的换出变量，得到替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表可行解，并相应地可以画出一个新的单纯形表。R（5）重复（）重复（3）、（）、（4）步直到计算结束为止。）步直到计算结束为止。原问题原问题(对偶问题对偶问题)对偶问题对偶问题(原问题原问题)目标函数目标函数m

9、ax目标函数目标函数min约约束束条条件件m个个=m个个00无符号限制无符号限制变变量量变变量量n个个00无符号限制无符号限制n个个=约约束束条条件件资源系数资源系数 b价值系数价值系数 c系数矩阵系数矩阵A 价值系数价值系数 b 资源系数资源系数 c系数矩阵系数矩阵AT 对偶规则表对偶规则表对偶理论对偶理论：1 12211 121 21112 1222221122min( ).0(1,2,).mmmmmmnnmnmniWbyb yb ya ya ya yca ya ya ycDsta ya ya ycyim则其对偶问题的一般形式为则其对偶问题的一般形式为1 12 211 112 21121

10、122 2221 12 2max( ).0(1,2,).n nn nn nmmmn nmjZcxc xc xa xa xa xba xa xa xbPsta xa xa xbxjn对称形式对称形式的线性规划的线性规划原问题的一般形式为原问题的一般形式为对称形式对偶问题对称形式对偶问题一对对偶问题的关系，只能有下面三种情况之一：一对对偶问题的关系，只能有下面三种情况之一： 1. 都有最优解；都有最优解； 2.一个问题无界，则另一个问题无可行解；一个问题无界，则另一个问题无可行解； 3. 两个都无可行解两个都无可行解. 0. .)(maxXbAXtsPCXZ 0. .)(minYCYAtsDYbW

11、n 对偶规划可以用线性规划的单纯形法求解。对偶规划可以用线性规划的单纯形法求解。n由对偶原理可见，原问题与对偶问题之间有由对偶原理可见，原问题与对偶问题之间有紧密联系，因此我们能够通过求解原问题来找紧密联系，因此我们能够通过求解原问题来找出对偶问题的解，反之依然。出对偶问题的解，反之依然。n互补松弛条件就可以解决由原问题的最优解互补松弛条件就可以解决由原问题的最优解直接求出对偶问题的最优解。直接求出对偶问题的最优解。对偶问题解的求法对偶问题解的求法K对偶单纯形法是对偶单纯形法是求解线性规划的另一个基本求解线性规划的另一个基本方法方法，它是根据对偶原理和单纯形法的原理，它是根据对偶原理和单纯形法

12、的原理而设计出来的，因此称为对偶单纯形法。而设计出来的，因此称为对偶单纯形法。K不要简单地将对偶单纯形法理解为求解对偶不要简单地将对偶单纯形法理解为求解对偶问题的单纯形法。问题的单纯形法。ibjs原始单纯形法原始单纯形法对偶单纯形法对偶单纯形法前提条件前提条件所有所有 0所有所有 0最优性检验最优性检验所有所有 0？所有所有 0？换入、出基换入、出基变量的确定变量的确定先确定换入基变量先确定换入基变量后确定换出基变量后确定换出基变量先确定换出基变量先确定换出基变量后确定换入基变量后确定换入基变量原始基本解原始基本解的进化的进化可行可行最优最优（对偶问题的解从（对偶问题的解从不可行到可行）不可行

13、到可行）非可行非可行可行（最优）可行（最优）（原问题的解从不可行（原问题的解从不可行到可行）到可行）ibjs第第4章章 运输问题运输问题1、运输问题的数学模型的建立；、运输问题的数学模型的建立；2、产销平衡下运输问题的、产销平衡下运输问题的基变量个数基变量个数与产地、与产地、销地之间的关系（销地之间的关系（m+n-1），即（），即（m+n-1）个独）个独立约束方程；立约束方程；3、约束方程都是等式。、约束方程都是等式。一、确定初始基可行解一、确定初始基可行解运输问题的初始方案的确定主要有：运输问题的初始方案的确定主要有：最小元素法最小元素法伏格尔法伏格尔法运输问题运输问题找出找出初始基可行解初

14、始基可行解，即在产销平衡表，即在产销平衡表上有（上有（m+n-1）个数字格。）个数字格。1、最小元素法的精髓最小元素法的精髓（就近供应，从单位运就近供应，从单位运价表中最小的运价开始确定供销关系，依次类价表中最小的运价开始确定供销关系，依次类推，只到给出全部方案为止）；推，只到给出全部方案为止）；2、Vogel法的核心法的核心（最大差额处，优先按最小（最大差额处，优先按最小运价进行调整）；运价进行调整）；3、位势法求检验数、闭回路法进行调整位势法求检验数、闭回路法进行调整；4、产销不平衡时的调整方法。、产销不平衡时的调整方法。第第5章章 目标规划目标规划1、目标规划的组成与特点；、目标规划的组

15、成与特点；2、目标规划的模型（如何建立目标函数、目标规划的模型（如何建立目标函数、目标约束建立等）；目标约束建立等）；3、目标函数中偏差变量的取舍目标函数中偏差变量的取舍（利润型目（利润型目标、成本型目标和合同型目标中偏差变量标、成本型目标和合同型目标中偏差变量的取舍）；的取舍）；4、掌握、掌握目标规划应用方法目标规划应用方法（不用求解）。（不用求解）。1、目标规划的特点、目标规划的特点 约束一般包括约束一般包括目标约束目标约束、系统约束系统约束、非、非负约束三个部分；负约束三个部分； 最终目标最终目标转换为求转换为求偏离多个期望目标值偏离多个期望目标值的偏差和最小的偏差和最小； 目标及约束仍

16、为目标及约束仍为线性线性。（1）对于）对于利润型目标利润型目标，要求是可能实现值超，要求是可能实现值超过目标值越多越好，即过目标值越多越好，即d+越大越好，则在目标越大越好，则在目标函数中，函数中，不能对不能对d+求最小求最小；（2）对于）对于成本型目标成本型目标，要求可能实现值低于，要求可能实现值低于目标值越多越好，即目标值越多越好，即d-越大越好，则在目标函越大越好，则在目标函数中数中不能对不能对d-求最小求最小；（3）对于）对于合同型目标合同型目标，要求跟目标保持一致，要求跟目标保持一致，不超过也不短缺，即不超过也不短缺，即要求要求d+和和d-都最小都最小，则在则在目标函数中应将两者综合

17、考虑。目标函数中应将两者综合考虑。2、目标函数中偏差变量的优化、目标函数中偏差变量的优化第第6章章 整数规划整数规划I分支定界法分支定界法I割平面法割平面法I指派问题及匈牙利法指派问题及匈牙利法 分枝定界法分枝定界法：将原整数规划问题分枝将原整数规划问题分枝分分为两个子规划为两个子规划, ,再解子规划的伴随规划再解子规划的伴随规划通过求解一系列子规划的伴随规划及不断通过求解一系列子规划的伴随规划及不断地定界地定界。最后得到原整数规划问题的整数。最后得到原整数规划问题的整数最优解。最优解。K从从( (LP) )的最优解中，任选一个不为整数的分的最优解中，任选一个不为整数的分量量x xr,r, ,

18、将最优单纯形表中该行的系数将最优单纯形表中该行的系数arj和和 br分分解为解为整数部分和非负真分数部分整数部分和非负真分数部分之和，之和， 并以该行为源行，按作割平面方程。并以该行为源行，按作割平面方程。K将所得的割平面方程，作为一个新的约束条件将所得的割平面方程，作为一个新的约束条件置于最优单纯形表中同时增加一个单位列向量），置于最优单纯形表中同时增加一个单位列向量），用对偶单纯形法求出新的最优解用对偶单纯形法求出新的最优解。割平面法割平面法K匈牙利算法。匈牙利算法。K算法主要依据以下事实：如果将系数矩阵算法主要依据以下事实：如果将系数矩阵C=（Cij）中一行（或一列）的每一元素都中一行（

19、或一列）的每一元素都加上或减去同一个数，得到一个新矩阵加上或减去同一个数，得到一个新矩阵B=（bij），），则以则以C和和B为系数矩阵的指派问题为系数矩阵的指派问题具有相同的最优指派。具有相同的最优指派。K系系数矩阵中独立数矩阵中独立 0 元素的最多个数等于能元素的最多个数等于能覆盖所有覆盖所有 0 元素的最少直线数。元素的最少直线数。 指派问题指派问题Step 1、先对效率矩阵进行列变换，使其各行各、先对效率矩阵进行列变换，使其各行各列中都出现列中都出现 0 元素。元素。效率矩阵变换方法为：效率矩阵变换方法为：从效率矩阵从效率矩阵 C 的每行元素的每行元素中减去该行的最小元素中减去该行的最小

20、元素,得矩阵得矩阵 B ；从矩阵；从矩阵 B 中中每列元素中减去该列的最每列元素中减去该列的最小元素得矩阵小元素得矩阵 C1 。21097 2154148 413 14 16 11 11415 139 4C 0875110104235001195B min 0 0 5 01082511054230001145C Step 2、确定、确定C1中线性独立的中线性独立的0元素元素.从第一行开始，若该行只有一个从第一行开始，若该行只有一个0元素，就对这个元素，就对这个0元素元素加圈，然后划去其所在列的其它加圈，然后划去其所在列的其它0元素元素;若该行没有其它若该行没有其它0元素或有两个以上元素或有两个

21、以上0元素（已划去的不计），转下一行；元素（已划去的不计），转下一行；直到最后一行为止。直到最后一行为止。然后，从第一列开始，若该列只然后，从第一列开始，若该列只有一个有一个0元素，就对这个元素，就对这个0元素加元素加圈（同样不考虑已划的）圈（同样不考虑已划的）,再划去再划去其所在行的其它其所在行的其它0元素；若该列没元素；若该列没有有0元素或有两个以上元素或有两个以上0元素，则元素，则转下列直到最后一列为止。转下列直到最后一列为止。182511054230011 45C00重复上述步骤。重复上述步骤。上述步骤可能出现三种情况上述步骤可能出现三种情况情况一：矩阵每行都有一个打情况一：矩阵每行都

22、有一个打圈的圈的 0 元素。此时得到问题的元素。此时得到问题的最优解。最优解。情况二：有多于两行或两列存在两个以上的未处理的情况二：有多于两行或两列存在两个以上的未处理的 0 元素，即出现元素，即出现 0 元素的闭回路。此时，可从中任选一元素的闭回路。此时，可从中任选一个个 0元素加圈，划掉其同行同列的元素加圈，划掉其同行同列的 0 元素，再重复上述元素，再重复上述两个步骤。两个步骤。情况三：矩阵中所有情况三：矩阵中所有 0 元素或被加圈，或被划去，而已元素或被加圈，或被划去，而已加圈的加圈的 0 元素元素m小于矩阵的行数小于矩阵的行数n。即矩阵中至少存在有。即矩阵中至少存在有一行不含加圈的一

23、行不含加圈的 0 元素。转步骤三。元素。转步骤三。182511054230011 45C00Step 3 寻找能覆盖寻找能覆盖C1中所有中所有0元素的最小直线数元素的最小直线数(1)按照从上到下、从左到右的顺序对按照从上到下、从左到右的顺序对C1没有加没有加圈的圈的0元行打元行打号；号；(2)对已打对已打号的行中未加圈号的行中未加圈0元的列打元的列打号；号；(3)对已打对已打号的列中加圈号的列中加圈0元的行打元的行打号；号；(4)重复下去，直到找不出打重复下去，直到找不出打号的行、列为止。号的行、列为止。 (5)对没打对没打号的行划一横线，号的行划一横线，对打对打号的列划一纵线，这号的列划一纵

24、线，这就是覆盖矩阵就是覆盖矩阵C1中所有中所有0元元素的最小直线数素的最小直线数.182511054230011 45C00 Step 4、改进、改进C1(1)寻找寻找 C1 没有被直线覆盖的没有被直线覆盖的所有元素中的最小元素所有元素中的最小元素；例中例中= 2。(2)在已打在已打号的行中减去号的行中减去；(3)在已打在已打号的列中加上号的列中加上；得到一个新矩阵得到一个新矩阵 C2。 182511054230011 45C00 2C -2603-292301340054300用用 C2 代替代替 C1，返回步骤，返回步骤 2。即最优分配方案：即最优分配方案：00100100*0001100

25、0X 206031305443000923C 确定确定C2中线性独立的中线性独立的0元素元素.第第7章章 动态规划动态规划1、熟悉关于动态规划的一些基本概念；、熟悉关于动态规划的一些基本概念；2、状态转移方程的建立方法；、状态转移方程的建立方法；3、动态规划的解题步骤；、动态规划的解题步骤；4、动态规划的求解方法动态规划的求解方法（确定型、逆序法，（确定型、逆序法，P169例例7-3之类）；之类）；第第8 8章章 图与网络图与网络图的基本概念图的基本概念树和图的最小支撑树树和图的最小支撑树最短路问题最短路问题网络最大流问题网络最大流问题最小费用最大流问题最小费用最大流问题概念概念定义（前向弧和

26、后向弧）定义（前向弧和后向弧）:在任意一顶点之在任意一顶点之处，凡离开处，凡离开vi的有向弧称为的有向弧称为vi的前向弧，凡的前向弧，凡进入进入vi的有向弧称为的有向弧称为vi的后向弧。的后向弧。称有向弧称有向弧a为为vi点的前向弧，点的前向弧， vj点的后向弧。点的后向弧。v0vnv2v1定义（道路或通路）定义（道路或通路）在任意一网络中，凡从在任意一网络中，凡从始点始点v0（发点）开始到终点（发点）开始到终点vn（收点）结束（收点）结束的一系列前向弧集合称为道路。的一系列前向弧集合称为道路。如果如果N表示某网络中所有点的集合，将表示某网络中所有点的集合，将N分成两分成两个子集个子集A与与A

27、，使得，使得发点发点v0在在A内，收点内，收点vn在在A 内内，则称（则称（A，A）为分离发点与收点的截集。）为分离发点与收点的截集。截集定义截集定义从从 A 中各顶点到中各顶点到 A中各顶点中各顶点全部容量之和全部容量之和称称为截集的容量（截量）。为截集的容量（截量）。截集的容量截集的容量v0vnv2v1a截集截集a a：v0v1，v0v2，v0vn截量截量: Ca=C01+C02+C0nv0vnv2v1截集截集v1vn，v2vn，v0vn截量截量: Cb=C1n+C2n+C0nv0vnv2v1dSS在截集在截集d中边中边v1v2是反向的，其容量视为零。是反向的，其容量视为零。截集截集：v0

28、v1，v1v2，v2v1，v2vn，v0vn截量：截量： Cd=C01+C21+ C2n+ C0n在将网络分成发集与收集的所在将网络分成发集与收集的所有分法中，容量最小的截集称有分法中，容量最小的截集称为最小截集。为最小截集。I如果链如果链满足以下条件：满足以下条件：（1）在弧（）在弧（vi,vj）+上，有上，有0fijcij， 即即+中的每一条弧是中的每一条弧是非饱和弧。非饱和弧。（2）在弧（）在弧（vi,vj）-上，有上，有0fij cij， 即即-中的每一条弧中的每一条弧是非零流弧是非零流弧。I则称这样的链为则称这样的链为增广链增广链 。增广链增广链练习题练习题K1、最早运用运筹学理论的

29、是（、最早运用运筹学理论的是（ ）KA 二次世界大战期间，英国军事部门将运二次世界大战期间，英国军事部门将运筹学运用到军事战略部署；筹学运用到军事战略部署；KB 美国最早将运筹学运用到农业和人口规美国最早将运筹学运用到农业和人口规划问题上；划问题上；KC 二次世界大战期间，英国政府将运筹学二次世界大战期间，英国政府将运筹学运用到政府制定计划；运用到政府制定计划；KD 50年代，运筹学运用到研究人口，能源，年代，运筹学运用到研究人口，能源，粮食，第三世界经济发展等问题上。粮食，第三世界经济发展等问题上。单项选择题单项选择题 K2、在产销平衡运输问题中，设产地为个，在产销平衡运输问题中，设产地为个

30、，销地为个，那么基可行解中非零变量的个销地为个，那么基可行解中非零变量的个数（数（ ）KA. 不能大于不能大于(m+n-1)； KB. 不能小于不能小于(m+n-1)； KC. 等于等于(m+n-1)；K D. 不确定。不确定。K3、在求解运输问题的过程中运用到下列哪、在求解运输问题的过程中运用到下列哪些方法（些方法（ ）KA 最小元素法最小元素法KB 位势法位势法KC 闭回路法闭回路法KD 伏格尔法伏格尔法KE 以上都是以上都是53 图解法同单纯形法虽然求解的形式不同，图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。但从几何上理解，两者是一致的。 LP模型中增加一个约束条件

31、，可行域的范模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。域的范围一般将扩大。 LP问题的每一个基解对应可行域的一个顶问题的每一个基解对应可行域的一个顶点。点。 如如LP问题存在最优解，则最优解一定对应问题存在最优解，则最优解一定对应可行域边界上的一个点。可行域边界上的一个点。 判断下列说法是否正确判断下列说法是否正确546. 任何任何LP问题存在并具有唯一的对偶问题。问题存在并具有唯一的对偶问题。 7. 对偶问题的对偶问题一定是原问题。对偶问题的对偶问题一定是原问题。8. 根据对偶问题的性质，当原问题为无界解根据

32、对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶时，其对偶问题无可行解，反之，当对偶问题无可行解问题无可行解时，其原问题具有无界解。时，其原问题具有无界解。5. 线性规划问题的可行解如为最优解，则线性规划问题的可行解如为最优解，则该可行解一定是基可行解；该可行解一定是基可行解；因为基可行解因为基可行解可行解。可行解。9.运输问题数学模型的（运输问题数学模型的（m+n）个约束中）个约束中 最多只有（最多只有（m+n-1）个是独立的。）个是独立的。K10.产销平衡的运输问题解的情况有四种：无可产销平衡的运输问题解的情况有四种：无可行解；无界解；唯一最优解；无穷多最优解。行解；无

33、界解；唯一最优解；无穷多最优解。错错 P102K11.运输问题的所有结构约束条件都是等式约束。运输问题的所有结构约束条件都是等式约束。对对填空题填空题 K1 1、用大、用大M法求解法求解Max型线性规划时，人工型线性规划时，人工变量在目标中的系数均为变量在目标中的系数均为 , ,若最优解若最优解的的 中含有人工变量，则原问题无中含有人工变量，则原问题无可行解。可行解。（-M）基变量基变量K2、若某种资源的影子价格为零，则表明该种、若某种资源的影子价格为零，则表明该种资源资源 （应该或不应该）被买进；又当资（应该或不应该）被买进；又当资源的影子价格不为零时，说明该种资源消耗源的影子价格不为零时，

34、说明该种资源消耗 （完毕或剩余）（完毕或剩余）不应该不应该 完毕完毕K3、线性规划原问题中的变量个数与其对偶问、线性规划原问题中的变量个数与其对偶问题中的题中的 个数相等。因此，当原问题增个数相等。因此，当原问题增加一个变量时，对偶问题就增加一个加一个变量时，对偶问题就增加一个 ，从而对偶可行域将可能变从而对偶可行域将可能变 (小还是大小还是大)。小小约束条件约束条件 约束条件约束条件K4、用表上作业法求解、用表上作业法求解m个产地个产地n个销地的平衡运个销地的平衡运输问题，其方案表上数字格的个数为输问题，其方案表上数字格的个数为 个；个；m+n-1K建立线性规划模型（利润最大或者成本最小）建

35、立线性规划模型（利润最大或者成本最小）K线性规划化为标准型线性规划化为标准型K写出问题的对偶规划写出问题的对偶规划建立模型建立模型某人每天食用甲、乙两种食物（如猪肉、鸡蛋），某人每天食用甲、乙两种食物（如猪肉、鸡蛋），如表。问两种食物各食用如表。问两种食物各食用多少，才能既满足需要、多少，才能既满足需要、又使总费用最省？又使总费用最省？设：设：X1 、X2 表示甲、乙表示甲、乙种食物的用量。种食物的用量。 2 1.5原料单价原料单价1.007.5010.00 0.1 0.15 1.7 0.75 1.10 1.30A1A2A3 最最 低低需要量需要量 含含 食物食物 量量成分成分0,00.1030.110.150.775.070.100.115.010.05.12min2121212121xxxxxxxxxxZ甲甲 乙乙cj1018000cBxBbx1x2x3x4x50 x3170521000 x4100230100 x515015001-Z01018000cj1018000cBxBbx1x2x3x4x50 x3540/7001-23/711/710 x150/71005/7-3/718x2200/7010