1--线性规划1--入门

第一章线性规划

1 线性规划

在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分-------数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。

自从1947年美国学者丹西格提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。

1.1 线性规划的实例与定义

例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用B

A、机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用C

、三种机器加工，加工

B

A、

时间为每台各一小时。若每天可用于加工的机器时数分别为A机器10小时、B机器8小时和C机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？

上述问题的数学模型：设该厂生产1x 台甲机床和2x 乙机床时总利

润最大，则21,x x 应满足

（目标函数）2134max x x z += (1)

s.t.（约束条件）???????≥≤≤+≤+0

,7

81022122121x x x x x x x （2）

这里变量21,x x 称之为决策变量，（1）式被称为问题的目标函数，

（2）中的几个不等式是问题的约束条件，记为s.t.(即subject to)。上述即为一规划问题数学模型的三个要素(决策变量/ 目标函数/约束条件)。由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。

总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。

1 线性规划的Matlab 标准形式

线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便，Matlab 中规定线性规划的标准形式为

b Ax x

c x

T ≤ that such min 其中c 和x 为n 维列向量，b 为m 维列向量，A 为n m ?矩阵。 例如线性规划

b Ax x

c x

T ≥ that such max 的Matlab 标准型为

b Ax x

c x

T -≤-- that such min 1.3 线性规划问题的解的概念

一般线性规划问题的标准型为

∑==n j j

j x c z 1min

(3)

∑==≤n j i

j ij m i b x a 1,,2,1 s.t.

(4)

可行解 满足约束条件（4）的解),,,(21n x x x x =，称为线性规划问题的可行解，而使目标函数（3）达到最小值的可行解叫最优解。

可行域 所有可行解构成的集合称为问题的可行域，记为R 。

1.4 线性规划的图解法

图解法简单直观，有助于了解线性规划问题求解的基本原理。我们先应用图解法来求解例1。如上图所示，阴影区域即为LP 问题的可行域R 。对于每一固定的值z ，使目标函数值等于z 的点构成的直线称

为目标函数等位线（图中的虚线是当z=12时），当z 变动时，我们得到一族平行直线。让等位线沿目标函数值减小的方向移动，直到等位线与可行域有交点的最后位置，此时的交点（一个或多个）即为LP 的最优解。

对于例1，显然等位线越趋于右上方，其上的点具有越大的目标函数值。不难看出，本例的最优解为T x )6,2(*=，最优目标值26*=z 。

从上面的图解过程可以看出并不难证明以下断言：

（1）可行域R 可能会出现多种情况。R 可能是空集也可能是非空集合，当R 非空时，它必定是若干个半平面(一条直线分平面为两个半平面)的交集（除非遇到空间维数的退化）。R 既可能是有界区域，也可能是无界区域。

（2）在R 非空时，线性规划既可以存在有限最优解，也可以不存在有限最优解（其目标函数值无界）。

（3）R 非空且LP 有有限最优解时，最优解可以唯一或有无穷多个。

（4）若线性规划存在有限最优解，则必可找到具有最优目标函数值的可行域R 的“顶点”。

上述论断可以推广到一般的线性规划问题，区别只在于空间的维数。

在一般的n 维空间中，满足一线性等式∑==n

i i i b x a 1的点集被称为一

个超平面，而满足一线性不等式∑=≤n i i i b x a 1（或∑=≥n

i i i b x a 1）的点集被称

为一个半空间（其中),,(1n a a 为一n 维行向量，b 为一实数）。有限个半空间的交集被称为多胞形，有界的多胞形又被称为多面体。易见，线性规划的可行域必为多胞形（为统一起见，空集Φ也被视为多胞形）。

在一般n 维空间中，要直接得出多胞形“顶点”概念还有一些困难。二维空间中的顶点可以看成为边界直线的交点，但这一几何概念的推广在一般n 维空间中的几何意义并不十分直观。为此，我们将采用另一途径来定义它。

定义1 称n 维空间中的区域R 为一凸集，若R x x ∈?21,及)1,0(∈?λ，有R x x ∈-+21)1(λλ。（定义1 说明凸集中任意两点的连线必在此凸集中；）

定义2 设R 为n 维空间中的一个凸集，R 中的点x 被称为R 的一个极点，若不存在R x x ∈21、及)1,0(∈λ，使得21)1(x x x λλ-+=。（而定义2 说明，若x 是凸集R 的一个极点，则x 不能位于R 中任意两点的连线上。）

不难证明，多胞形必为凸集。同样也不难证明，二维空间中可行域R 的顶点均为R 的极点（R 也没有其它的极点）。

1.5 求解线性规划的Matlab 解法

单纯形法是求解线性规划问题的最常用、最有效的算法之一。单纯形法是首先由George Dantzig(美国学者丹西格)于1947年提出的，近60年来，虽有许多变形体已被开发，但却保持着同样的基本观念。

由于有如下结论：若线性规划问题有有限最优解，则一定有某个最优解是可行区域的一个极点。基于此，单纯形法的基本思路是：先找出可行域的一个极点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一极点，并使目标函数值更优；如此下去，直到找到某一最优解为止。

下面我们介绍线性规划的Matlab 解法。

Matlab5.3中线性规划的标准型为

b Ax x

c T x

≤ such that min 基本函数形式为linprog(c,A,b)，它的返回值是向量x 的值。还有其它的一些函数调用形式（在 Matlab 指令窗运行 help linprog 可以看到所有的函数调用形式），如：

[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X 0,OPTIONS)

这里fval 返回目标函数的值，Aeq 和beq 对应等式约束beq x Aeq =*，LB 和UB 分别是变量x 的下界和上界，0x 是x 的初始值，OPTIONS 是控制参数。

例2 求解下列线性规划问题

321532m a x x x x z -+=

?????≥≥+-=++0,,105273

21321321x x x x x x x x x

解 （i ）编写M 文件

c=[2;3;-5];

a=[-2,5,-1]; b=-10;

aeq=[1,1,1];

beq=7;

x=linprog(-c,a,b,aeq,beq,zeros(3,1))

value=c'*x---%得到的最大值

（ii ）将M 文件存盘，并命名为example1.m 。(不能以数字开头,一般四个字符以上)

（iii ）在Matlab 指令窗运行example1即可得所求结果。 例3 求解线性规划问题

32132 min x x x z ++=

?????≥≥+≥++0,,6238243

2121321x x x x x x x x

解 编写Matlab 程序如下：

c=[2;3;1];

a=[1,4,2;3,2,0];

b=[8;6];

[x,y]=linprog(c,-a,-b,[],[],zeros(3,1))

1.6 可以转化为线性规划的问题

很多看起来不是线性规划的问题也可以通过变换变成线性规划问题来解决。如：

例4 问题为

b Ax x x x n ≤+++ t.s.|

|||||min 21

其中T n x x x ][1 =，A 和b 为相应维数的矩阵和向量。

要把上面的问题变换成线性规划问题，只要注意到事实：对任意的i x ，存在0,>i i v u 满足

i i i v u x -=，i i i v u x +=||

这样一变换，就把绝对值去掉了。 事实上，我们只要取2||i i i x x u +=，2

||i i i x x v -=就可以满足上面的条件。 这样，记T n u u u ][1 =，T n v v v ][1 =，从而我们可以把上面的问题变成

∑=+n i i i v u

1)(min

?

??≥≤-0,)( t.s.v u b v u A 变成了二维向量的线性规划问题。

《管理线性规划入门》考试资料

《管理线性规划入门》 一、单项选择题 1．已知矩阵1212377x x ???? ==????-???? A B ，，并且A B =，则 x ＝（C ）。 A. 0 B. 2 C. 32 D.3 2．建立线性规划模型时。首先应（B ）。 A ．确定目标函数 B ．设置决策变量 C ．列出约束条件 D ．写出变量的非负约束 3．在MATLAB 软件中，乘法运算的运算符是(A)。 A ．^ B ．／ C ．* D ．+ 4．在MATLAB 软件的命令窗口(command window)中矩阵1143210 2B -?? ??=-?? ???? 的正确输入方式为（A ）。 A ．>>B=[-1 1 4;3 -2 1;0 0 2] B ．>>B=[-1 3 0;1 -2 1;4 1 2] C ．>>B=[-1 1 4 3 -2 1 0 0 2] D ．>>B=[-1 1 ；4 3 ； -2 1 ；0 0 2] 5．在MATLAB 软件中，命令函数clear 的作用为(D)。 A ．关闭MATLAB B ．查询变量的空间使用情况 C ．清除命令窗口的显示内容 D ．清除内存中变量 (D) 2．线性规划模型的标准形式要求约束条件(D)。 A ．只取大于等于不等式 B ．只取小于等于不等式 C ．没有限制 D ．取等式或小于等于不等式 3．在MATLAB 软件中，乘法运算的运算符是(C)。 A ．A B ．／ C ．* D ．+ 4．用MATLAB 软件计算矩阵2A+B T 输入的命令语句为(A)。 A ．>>2*A+B ’ B ．>>2*A+B T C ．>>2A+BT D ．>>2A+B ’ 5．在MATLAB 软件的命令窗口(command window)中输入的命令语句为：>>rref(A)，则进行的运算为(B)。 A ．求矩阵A 的逆 B ．将矩阵A 化为行简化阶梯型矩阵 C ．将矩阵A 化为单位矩阵 D ．求矩阵A 的乘方 ( B ) ．线性规划模型的标准形式中，要求( A ) ．目标函数取最小值 B ．目标函 ．约束条件取大于等于不等式 D ．约束条 ．在MATLAB 软件中，运算符"/"表示( B )运算。 ．乘方 B ．除 ．矩阵转置 D ．乘 ．在MATLAB 软件的命令窗口(command window)中矩阵 101221A ?? ?? =-?????? 的输入方式为（D ）。 ．用 MATLAB 软件求逆矩阵的命令函数为( C )。 ． rref B ． clear ． inv D ． eye ．将下列线性规划模型的标准形式表示成矩阵形式： ．某线性方程组的增广矩阵D 对应的行简化阶梯形矩阵为 0=d(≠0)，所以该方程组有解，且线性方程的3，等于变量的个数3，所以该线性方程组有惟一解。 ．将线性方程组 D 。 AX=B ．某线性方程组的增广矩阵D 对应的行简化阶梯形矩阵为 0=d(≠0)，所以该方程组有解，且线性方程的3，小于变量的个数4，所以该线性方程组有无穷多个解。 ．将下列线性规划模型的标准形式表示成矩阵形式： ．某线性方程组的增广矩阵D 对应的行简化阶梯形矩阵为： 0=d(d>0)，所以该方程组有解，且线性方程的 2，小于变量的个数4，所以该线性方程组有无穷多解。 ．某食品企业生产饼干和蛋糕，主要用料是面粉、鲜奶和食用油，0．7千克、鲜奶0．2千克、食用0．1千克；生产一千克蛋糕需要面粉0．4千克、鲜奶0．50．1千克。每天生产需要面粉至少1000千克，鲜600千克，食用油至少200千克。生产一千克饼干的成本3．6元，生产一千克蛋糕的成本为4．8元。 试写出该企业生产成本最小的线性规划模型；

《管理线性规划入门》考核标准

《管理线性规划入门》考核说明 一、有关说明 1. 考核对象 国家开放大学开放教育专科城市轨道运营管理专业学生。 2. 启用时间 从2011年春季开始使用。 3. 考核目标 本课程是学习专业理论必不可少的定量分析工具。通过考核，使学生理解管理线性规划的基本案例，掌握线性规划模型的基本概念和建模方法。理解矩阵的基本概念，掌握矩阵计算的基本方法。了解MATLAB软件，掌握用MATLAB软件求解线性规划的方法，提高学生使用计算机解决实际问题的能力。课程的考核合格水准应达到高等学校经济管理类专业专科应用数学教学的要求。 4. 考核依据 本课程考核说明是依据中央广播电视大学《管理线性规划入门教学大纲》、文字教材《管理线性规划入门》（胡新生主编，中央广播电视大学出版社，2010年1月第一版）制定的。本课程考核说明是形成性考核和终结性考试命题的基本依据。 5. 考核方式及计分方法 本课程考核分为两种方式，形成性考核与终结性考试。形成性考核占综合成绩的30%，终结性考试占综合成绩的70%。 二、考核方式与要求 （一）形成性考核 1.考核目的 加强对学生平时自主学习过程的指导和监督，重在对学生自主学习过程进行指导和检测，引导学生按照教学要求和学习计划完成学习任务，达到掌握知识、提高能力的目标，提高学生的综合素质。 2.考核手段 网上布置，纸质答题。 3.考核形式 形成性考核由计分作业和和计算实验报告构成。 4.考核形式形成性考核各形式所占比重及计分方法 形成性考核按百分制计分，每次形考任务也按照百分制计分。形考任务共6次，其

中3次形考作业占50%，5次实训占50%。 5.考核要求 本课程每位学生应交三次作业和至少五次计算实验报告。三次平时作业按网上提供的两本教材中的作业题要求完成；计算实验报告应包括：题目，输入与计算结果的界面及结果分析。辅导教师根据学生完成平时作业及计算实验的情况和质量，对其进行评分。 注：“布置时间”与“提交时间”可根据教学班的具体情况作适当调整。 （二）终结性考试 1. 考试目的 终结性考试是在形成性考核的基础上，对学生学习情况和学习效果进行的一次全面检测。 2. 命题原则 第一，本课程的考试命题严格控制在教学大纲规定的教学内容和教学要求的范围之内； 第二，考试命题覆盖《管理线性规划入门》教材，既全面，又突出重点； 第三，每份试卷所考的内容，覆盖本课程教材所学内容的70%以上的章节； 第四，试题应难易适中，一般来讲，可分为：容易、适中、较难三个程度，所占比例大致为：容易占30%，适中占50%，较难占20%。 3. 考试手段 终结性考试采用纸质笔试。 4.考试方式 终结性考试采用闭卷方式。 5. 考试时限 终结性考试时间长度是90分钟。 6. 特殊说明 终结性考试不允许携带任何资料与工具。

第一章 线性规划

第一章 线性规划 §1 线性规划 在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947年G. B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。 1.1 线性规划的实例与定义 例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用B A 、机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用C B A 、、三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A 机器10小时、B 机器8小时和C 机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？ 上述问题的数学模型：设该厂生产1x 台甲机床和2x 台乙机床时总利润最大，则 21,x x 应满足 （目标函数）2134m ax x x z += (1) s.t.（约束条件）???????≥≤≤+≤+0 ,781022122 121x x x x x x x （2） 这里变量21,x x 称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式 是问题的约束条件，记为s.t.(即subject to)。上述即为一规划问题数学模型的三个要素。由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。 总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。 在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往也是困难的一步，模型建立得是否恰当，直接影响到求解。而选取适当的决策变量，是我们建立有效模型的关键之一。 1.2 线性规划的Matlab 标准形式 线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便，Matlab 中规定线性规划的标准形式为 b Ax x c x T ≤ that such min 其中c 和x 为n 维列向量，b 为m 维列向量，A 为n m ?矩阵。 例如线性规划 b Ax x c x T ≥ that such max 的Matlab 标准型为

《运筹学》习题线性规划部分练习题及答案.doc

《运筹学》线性规划部分练习题 一、思考题 1.什么是线性规划模型，在模型中各系数的经济意义是什么？ 2 .线性规划问题的一般形式有何特征？ 3. 建立一个实际问题的数学模型一般要几步？ 4. 两个变量的线性规划问题的图解法的一般步骤是什么？ 5. 求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 6. 什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 7?试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8?试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9. 在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 10. 大M法中，M的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问 题呢？ 11 ?什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续 第二阶段？ 二、判断下列说法是否正确。 1 .线性规划问题的最优解一定在可行域的顶点达到。 2 .线性规划的可行解集是凸集。 3. 如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。 4. 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的 范围一般将扩大。 5 .线性规划问题的每一个基本解对应可行域的一个顶点。 6. 如果一个线性规划问题有可行解，那么它必有最优解。 7. 用单纯形法求解标准形式（求最小值）的线性规划问题时，与j 0对应的变量都可以被 选作换入变量。 8 .单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一 个基变量的值是负的。 9. 单纯形法计算中，选取最大正检验数k对应的变量x k作为换入变量，可使目 标函数值得到最快的减少。 10 . 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形 表中删除，而不影响计算结果。 三、建立下面问题的数学模型 1 .某公司计划在三年的计划期内，有四个建设项目可以投资：项目I从第一年到 第三年年初都可以投资。预计每年年初投资，年末可收回本利120%，每年又可以重新将所获本利纳入投资计划；项目n需要在第一年初投资，经过两年可收回本利150% , 又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目川需要在第二年年初投资，经过两年可收回本利160%，但用于该项目的最大投资额 不得超过15万元；项目"需要在第三年年初投资，年末可收回本利140%，但用于该项目的最大投资额不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有 30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？ 2 .某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、 100克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单 价如下表2—1所示：

《运筹学》习题线性规划部分练习题及答案.doc

《运筹学》线性规划部分练习题 一、思考题 1． 什么是线性规划模型，在模型中各系数的经济意义是什么？ 2． 线性规划问题的一般形式有何特征？ 3． 建立一个实际问题的数学模型一般要几步？ 4． 两个变量的线性规划问题的图解法的一般步骤是什么？ 5． 求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 6． 什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 7． 试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8． 试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9． 在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 10．大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？ 11．什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？ 二、判断下列说法是否正确。 1． 线性规划问题的最优解一定在可行域的顶点达到。 2． 线性规划的可行解集是凸集。 3． 如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。 4． 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。 5． 线性规划问题的每一个基本解对应可行域的一个顶点。 6． 如果一个线性规划问题有可行解，那么它必有最优解。 7． 用单纯形法求解标准形式（求最小值）的线性规划问题时，与0 >j σ对应的变量都可以被选作换入变量。 8． 单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一个基变量的值是负的。 9． 单纯形法计算中，选取最大正检验数k σ对应的变量k x 作为换入变量，可使目 标函数值得到最快的减少。 10． 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。 三、建立下面问题的数学模型 1． 某公司计划在三年的计划期内，有四个建设项目可以投资：项目Ⅰ从第一年到 第三年年初都可以投资。预计每年年初投资，年末可收回本利120% ，每年又可以重新将所获本利纳入投资计划；项目Ⅱ需要在第一年初投资，经过两年可收回本利150% ，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目Ⅲ需要在第二年年初投资，经过两年可收回本利160% ，但用于该项目的最大投资额不得超过15万元；项目Ⅳ需要在第三年年初投资，年末可收回本利140% ，但用于该项目的最大投资额不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？ 2．某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、 100克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单 价如下表2—1所示：

第一章线性规划

-1- 第一章 线性规划 §1 线性规划 在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947年G . B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。 1.1 线性规划的实例与定义 例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用B A 、机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用C B A 、、三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A 机器10小时、B 机器8小时和C 机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？ 上述问题的数学模型：设该厂生产1x 台甲机床和2x 乙机床时总利润最大，则2 1,x x 应满足 （目标函数）2134max x x z += (1) s.t.（约束条件）???????≥≤≤+≤+0 ,781022122 121x x x x x x x （2） 这里变量21,x x 称之为决策变量， （1）式被称为问题的目标函数，（2）中的几个不等式是问题的约束条件，记为s.t.(即subject to)。由于上面的目标函数及约束条件均为线性 函数，故被称为线性规划问题。 总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。 在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往也是困难的一步，模型建立得是否恰当，直接影响到求解。而选适当的决策变量，是我们建立有效模型的关键之一。 1.2 线性规划的Matlab 标准形式 线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便，Matlab 中规定线性规划的标准形式为 x c x T min s.t. ?? ? ??≤≤=?≤ub x lb beq x Aeq b Ax 其中c 和x 为n 维列向量，A 、Aeq 为适当维数的矩阵，b 、beq 为适当维数的列向量。

管理线性规划入门—形考答案

. 1任务 分）题（满分30客观题共6 5分）一、单项选择题（共6题，每题). (已答第1题）。MATLAB在软件中，求解线性规划的命令函数为（A. rref B. inprog C. inv D. eye A【参考答案】 Linprog【答案解析】 。）（A=软件中，在已答题第2(). MATLAB矩阵的正确输入方式是

专业资料 . A. B. C. D. A【参考答案】A【答案解析】 第(已答3题). A. B. C. D.

D【参考答案】 【答案解析】 4第题下列（). (已答）为单位矩阵。专业资料 . A. B. C. D. A【参考答案】 【答案解析】 ). 已答题(第5 ）。线性规划问题中，通常要求决策变量（

A. 非负 B. 0小于 C. 0大于 专业资料 . D. 没有限制 A【参考答案】 【答案解析】非负 ). (已答第6题线性规划模型的标准形式要求目标函数（）。A. 求最大值 B. 求最小值 C. 没有限制 D.

不求最优值 B【参考答案】 【答案解析】求最小值 分）题（满分70 主观题共8 分）56二、填空题（共题，每题专业资料. 题(). 第已答710【参考答案】 10【答案解析】 分【本题分数】5 分0.0【本题得分】 题(第8已答). 9【参考答案】 9【答案解析】 分【本题分数】5 分【本题得分】5.0

）运算。软件的算术运算符中，“). 在MATLAB^”表示（已答题第9(【参考答案】乘方 【答案解析】乘方 分【本题分数】5 专业资料 . 分【本题得分】5.0 题(). 第已答101.5【参考答案】 1.5【答案解析】 分【本题分数】5 分5.0【本题得分】 )的逆矩阵的命令函数为：( 。计算矩阵). 11第题(已答在MARLAB软件中，Ainv(A)【参考答案】 inv(A)【答案解析】 分【本题分数】5

第一章线性规划及单纯形法习题

第一章 线性规划及单纯形法习题 1.用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。 （1）??? ??≥≥+≥++=0,42266432min 2 121212 1x x x x x x x x z (2) ??? ??≥≥+≥++=0,12432 223max 2 121212 1x x x x x x x x (3) ??? ??≤≤≤≤≤++=83105120106max 21212 1x x x x x x z (4) ?????≥≤+-≥-+=0 ,2322 265max 1 221212 1x 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,0232624 322min 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(01022274322325min 432143214321 j x x x x x x x x x x x x x z j 4.分别用图解发法和单纯形法求解下述问题，并对照单纯形表中的各基本可行解对应图解法中可行域的哪一顶点。 (1) ??? ??≥≤+≤++=0,825943510max 1 221212 1x x x x x x x x z (2) ?????≥≤+≤++=0,242615 532max 1 221212 1x x x x x x x x z 5.上题（1）中，若目标函数变为21m ax dx cx z +=，讨论c,d 的值如何变化，使该问题可行域的每一顶点依次使目标函数达到最优。 6.考虑下述线性规划问题： ? ????≥≤+≤++=0 ,max 122221212121112 1x x b x a x a b x a x a dx cx z 式中311≤≤c ,642≤≤c , 3111≤≤-a ,5212≤≤a ,1281≤≤b , 5221≤≤a ,6422≤≤a ,14102≤≤b ，试确定目标函数最优值的下界和上 界。 7.分别用单纯形法中的大M 法和两阶段法求解下列线性规划问题，并指出属哪一类解。 (1) ??? ?? ? ?=≥≥-≥+-≥+++-=)3,2,1(0022 2622max 32313213 21j x x x x x x x x x x x z j (2) ??? ??≥≥+≥++++=0,,62382432min 3 21213213 21x x x x x x x x x x x z

02375_运筹学基础试题及答案_200504

2005年上半年高等教育自学考试全国统一命题考试 运筹学基础试题 （课程代号：2375） 第一部分选择题（共15分） 一、单项选择题(本大题共15小题，每小题1分，共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.当线性规划问题的一个基解满足下列哪项要求时称之为一个可行基解？（C） A.大于0 B.小于0 C.非负 D.非正 2.下列说法正确的是（B） A.修正分配法是闭合回路法的基础 B.在判别某个方案是否最优时，修正分配法比闭合回路法简单 C.在判别某个方案是否最优时，修正分配法对所有空格寻求闭合的改进路线 D.所有运输问题都是供需相等的 3.对于总运输费用最小的运输问题，若已得最优运输方案，则其中所有空格的改进指数必（A） A.大于或等于0 B.小于或等于0 C.大于0 D.小于0 4.蒙特卡洛法是一个（D） A.随机数技术 B.排队技术 C.不确定决策技术 D.模拟技术 5.下列选项中结果为1的是（B） A.根据最大最大决策标准，每个方案在未来可能遇到最差的自然状态的概率值 B.根据最大最小决策标准，每个方案在未来可能遇到最差的自然状态的概率值 C.根据现实主义决策标准，每个方案在未来可能遇到最佳的自然状态的概率值 D.根据现实主义决策标准，每个方案在未来可能遇到最差的自然状态的概率值 6.下列说法正确的是（B） A.决策树是在不确定条件下进行决策的一种方法 B.决策树和贝叶斯标准都可以用在风险的条件下决策 C.期望利润标准就是现实主义决策标准 D.乐观主义决策标准和保守主义者的决策标准应用于同一决策问题时的答案往往是一致的 7.箭线式网络图的三个组成部分是（A） A.活动、线路和结点 B.结点、活动和工序 C.工序、活动和线路 D.虚活动、结点和线路 8.下列不属于 ．．．网络计划优化的内容是（A） A.成本优化 B.时间与资源优化 C.时间优化 D.时间与成本优化 9.设T=(t 1,t 2 ,……,t n )为概率向量，P=(p ij )n×n为概率矩阵，则当k→∞时，必有（C）

管理线性规划入门考试资料

《管理线性规划入门》 一、单项选择题 1．已知矩阵1212377x x ???? ==???? -???? A B ，，并且A B =，则x ＝（C ）。 A. 0 B. 2 C. 3 2 D.3 2．建立线性规划模型时。首先应（B ）。 A ．确定目标函数 B ．设置决策变量 C ．列出约束条件 D ．写出变量的非负约束 3．在MATLAB 软件中，乘法运算的运算符是(A)。 A ．^ B ．／ C ．* D ．+ 4．在MATLAB 软件的命令窗口(command window)中矩阵 114321002B -?? ??=-?? ???? 的正确输入方式为（A ）。 A ．>>B=[-1 1 4;3 -2 1;0 0 2] B ．>>B=[-1 3 0;1 -2 1;4 1 2] C ．>>B=[-1 1 4 3 -2 1 0 0 2] D ．>>B=[-1 1 ；4 3 ； -2 1 ；0 0 2] 5．在MATLAB 软件中，命令函数clear 的作用为(D)。 A ．关闭MATLAB B ．查询变量的空间使用情况 C ．清除命令窗口的显示内容 D ．清除内存中变量 (D) 2．线性规划模型的标准形式要求约束条件(D)。 A ．只取大于等于不等式 B ．只取小于等于不等式 C ．没有限制 D ．取等式或小于等于不等式 3．在MATLAB 软件中，乘法运算的运算符是(C)。 A ．A B ．／ C ．* D ．+ 4．用MATLAB 软件计算矩阵2A+B T 输入的命令语句为(A)。 A ．>>2*A+B ’ B ．>>2*A+B T C ．>>2A+BT D ．>>2A+B ’ 5．在MATLAB 软件的命令窗口(command window)中输入的命令语句为：>>rref(A)，则进行的运算为(B)。 A ．求矩阵A 的逆 B ．将矩阵A 化为行简化阶梯型矩阵 C ．将矩阵A 化为单位矩阵 D ．求矩阵A 的乘方 ( B ) 2．线性规划模型的标准形式中，要求( A ) A ．目标函数取最小值 B ．目标函数取最大值 C ．约束条件取大于等于不等式 D ．约束条件只取等式 3．在MATLAB 软件中，运算符"/"表示( B )运算。 A ．乘方 B ．除法 C ．矩阵转置 D ．乘法 4．在MATLAB 软件的命令窗口(command window)中矩阵 101221A ???? =-?????? 的输入方式为（D ）。 5．用 MATLAB 软件求逆矩阵的命令函数为( C )。 A ． rref B ． clear C ． inv D ． eye 二、计算题 7．将下列线性规划模型的标准形式表示成矩阵形式： 8．某线性方程组的增广矩阵D 对应的行简化阶梯形矩阵为 判断该线性方程组解的情况，若有解，写出该方程组的解。 因为没有出现方程0=d(≠0)，所以该方程组有解，且线性方程的个数为3，等于变量的个数3，所以该线性方程组有惟一解。 该线性方程组的解为： 7．将线性方程组 表示成矩阵形式，并写出该线性方程组的增广矩阵D 。 该线性方程组的矩阵形式为：AX=B 8．某线性方程组的增广矩阵D 对应的行简化阶梯形矩阵为 判断该线性方程组解的情况，若有解，写出该方程组的解． 行简化阶梯形矩阵对应的线性方程组为 因为没有出现方程0=d(≠0)，所以该方程组有解，且线性方程的个数为3，小于变量的个数4，所以该线性方程组有无穷多个解。 该线性方程组的一般解为 7．将下列线性规划模型的标准形式表示成矩阵形式： 8．某线性方程组的增广矩阵D 对应的行简化阶梯形矩阵为： 判断该线性方程组解的情况，若有解，写出该方程组的解。 因为没有出现方程0=d(d>0)，所以该方程组有解，且线性方程的个数为2，小于变量的个数4，所以该线性方程组有无穷多解。 该线性方程组的一般解为： 三、应用题 9．某食品企业生产饼干和蛋糕，主要用料是面粉、鲜奶和食用油，已知生产一千克饼干需要面粉0．7千克、鲜奶0．2千克、食用油0．1千克；生产一千克蛋糕需要面粉0．4千克、鲜奶0．5千克、食用油0．1千克。每天生产需要面粉至少1000千克，鲜奶至少600千克，食用油至少200千克。生产一千克饼干的成本为3．6元，生产一千克蛋糕的成本为4．8元。 (1)试写出该企业生产成本最小的线性规划模型； 解：设该企业每天生产饼干、蛋糕分别为x 1，x 2(千克)，则线性规划模型为： (2)将该线性规划模型化为标准形式，并写出用MATLAB 软件计算该线性规划问题的命令语句。 解：此线性规划模型的标准形式为： 10．某运输问题的运输平衡表(单位：吨)与运价表(单位：百元／吨)如下表所示： 试写出使运输总费用最小的线性规划模型。 解：设产地A 运送到销地I ，Ⅱ，Ⅲ的运输量分别为x 1，x 2，x 3(吨)；产地B 运送到销地I ，Ⅱ，Ⅲ的运输量分别为x 4，x 5，x 5(吨)；产地C 运送到销地I ，Ⅱ，Ⅲ的运输量分别为x 7，x 8，x 9(吨)。又设运输总费用为S ，则线性规划模型为： 11．某厂生产甲、乙、丙三种电子产品，需要通过加工、装配、检验三道工序。已知每生产 一件产品甲，三道工序所需工时分别为10，2，1小时；每生产一件产品乙，三道工序所需工时分 别为5，2，1小时；每生产一件产品丙，三道工序所需工时分别为5，6，1小时。每道工序能提供 的工时分别为600小时、300小时和100小时。又知道每生产一件产品甲，可获得10万元的 利润；每生产一件产品乙，可获得8万元的利润；每生产一件产品丙，可获得12万元的利润。 问企业如何安排生产，可获得最大利润? (1)试写出利润最大的线性规划模型； 解：设甲、乙、丙三种产品分别生产x 1，x 2，x 3 (件)，则线性规划模型为： (2)若用MATLAB 软件计算该线性规划问题后得结果为： Optimization terminated successfully ． X= 20．0000 55．0000 25．0000 fval= —940．0000 试写出利润最大时的甲、乙、丙三种产品的产量和最大利润。

管理线性规划入门模拟试题

《管理线性规划入门》模拟试题 一、单项选择题（每小题4分，共20分） 1．已知矩阵 10122103-????==????-???? ，A B ，则A －2B T ＝（ ）。 A. 3027?? ??-?? B. 3427-?? ??-?? C. 3027????--?? D. 2004????-?? 2．线性规划模型的标准形式要求目标函数（ ）。 A. 求最大值 B. 求最小值 C. 没有限制 D. 不求最优值 3．在MATLAB 软件的算术运算符中，运算符“*”表示（ ）运算。 A. 乘方 B. 除法 C. 矩阵转置 D. 乘法 4．在MATLAB 软件的命令窗口中输入的矩阵A=[1 0 1; -2 2 1]，则矩阵A 表示为（ ）。 A. 101221?? ? ?-?? B. 112021?? ? ?-?? C. 120211-?? ???????? D. 101221?? ??-?????? 5．用MATLAB 软件求逆矩阵的命令函数为（ ）。 A. rref B. clear C. inv D. eye 二、计算题（每小题10分，共30分） 6．设111102*********-???? ????=-=???? ????--???? ，A B ，计算BA 。 7．将下列线性规划模型的标准形式化为矩阵形式： 12345 5125345min 802101205006040020.5040.300(1,2,,5)j S x x x x x x x x x x x x x j '=----+≤? ?+-=?? +-=? ?≥=? 8．某线性方程组的增广矩阵D 对应的行简化阶梯形矩阵为

运筹学中线性规划实例汇总

实验报告 课程名称：运筹学导论 实验名称：线性规划问题实例分析专业名称：信息管理与信息系统 指导教师：刘珊 团队成员：邓欣(20112111 蒋青青(20114298 吴婷婷(20112124 邱子群(20112102 熊游(20112110 余文媛(20112125 日期：2013-10-25 成绩：___________

1．案例描述 南部联盟农场是由以色列三个农场组成的联合组织。该组织做出了一个关于农场农作物的种植计划，如下： 每一个农场的农业产出受限于两个量，即可使用的灌溉土地量和用于灌溉的水量。数据见下表： 适合本地区种植的农作物包括糖用甜菜、棉花和高粱。这三种作物的差异在于它们每亩的期望净收益和水的消耗量不同。另外农业部门已经制定了南部联盟农场作物总亩数的最大配额，见下表： 作物的任何组合可以在任何农场种植，技术部门的任务是找出一个种植方案使南部联盟农场的净收益最大化。 2.建立模型 决策变量为Xi(i=1,2,……,9,表示每个农场每种作物的种植量。 MAX Z=1000(X1+X2+X3+750(X4+X5+X6+250(X7+X8+X9 约束条件： （1）每一个农场使用的土地 X1+X4+X7≤400

X2+X5+X8≤600 X3+X6+X9≤300 (2每一个农场的水量分布 3X1+2X4+X7≤600 3X2+2X5+X8≤800 3X3+2X6+X9≤375 (3每一种作物的总种植量 X1+X2+X3≤600 X4+X5+X6≤500 X7+X8+X9≤325 非负约束Xi≥0 , i=1,2, (9) 3.计算机求解过程 步骤1.生成表格 步骤2.输入数据

《管理线性规划入门》教学大纲

《管理线性规划入门》课程教学大纲 第一部分大纲说明 一、课程的性质与任务 《管理线性规划入门》课程是国家开放大学城市轨道运营管理专业专业的一门必修的重要基础课。它是为培养符合社会主义市场经济要求的大专应用型经济管理人才服务的。 通过本课程的学习，使学生获得线性规划、线性代数的基础知识，能学会线性规划建模，培养学生的矩阵代数基本运算能力，增强学生用定性与定量相结合的方法处理管理问题的初步能力。 通过本课程的学习，使学生获得用软件求解线性规划、矩阵代数等技能，增强学生使用软件的操作能力。 通过本课程的学习，要为学习城市轨道交通运营管理专业的后续课程和今后工作需要打下必要的数学基础。 二、课程的目的与要求 1．使学生初步熟悉线性代数的研究方法，提高学生抽象思维和运算能力，能熟悉矩阵基本知识、线性方程组、线性规划以及MATLAB软件求解矩阵、线性方程组和线性规划问题。 2．使学生对极限的思想和方法有初步认识，对具体与抽象、特殊与一般、有限与无限等辩证关系有初步的了解，初步掌握函数与极限、导数与微分、不定积分与定积分的基本知识、基本理论和基本技能，以及MATLAB软件求解微积分问题。熟悉微积分建立变量的思想，培养辩证唯物主义观点，并受到运用变量数学方法解决经济问题的初步训练。 三、课程的教学要求层次 教学要求由低到高分三个层次，有关定义、定理、性质、特征等为“知道、了解、理解”；有关计算、解法、公式、法则等为“会、掌握、熟练掌握”。

第二部分教学媒体和教学建议 一、学分与学时 1．学分：本课程3学分。 2．学时分配 （1）第一章，管理线性规划案例与模型，16学时； （2）第二章，矩阵基本知识，8学时； （3）第三章，MATLAB软件基础与应用，24学时。 （4）模拟测试与综合期末复习，6学时 二、教材 本课程教材是由文字教材物流管理管理定量分析方法和IP课件等多种媒体组成的一体化教材，要求学时正确使用、充分利用本课程的多种媒体一体化教材。 1．文字教材 主教材是学生学习的主要用书，主教材是教和学的主要依据。根据远距离教育要求和电大学生入学时水平参差不齐的实际情况，文字主教材配导学内容。导学内容包括梯度知识内容和配合主教材的辅导内容，以及便于学生深入学习的参考内容。 文字教材是学生获得知识和能力的重要媒体之一。教材中对概念的叙述要直观无误，论证要清楚，要适合成人、以业余学习为主的特点，便于自学。 2．网络课程 网络课程集文本、视频、音频、虚拟实验等多种媒体为一体的网上学习、面试辅导、在线测试和网上交互等多种手段的教、学、评的开放式的学习环境网络课件可以让学生的学习不受时间和地点的限制，体现学生的自主学习，能及时解决学生在学习中的疑难问题。（网络课程网址：https://www.wendangku.net/doc/fb2857658.html,/glxxghrm/）。 三、教学环节 本课程的教学将采用基于网络课程的融合式教学模式组织实施教学，以适应开放教育成人学习者的学习特征，最大限度的满足学习者自主学习的需求。

第五版运筹学基础与应用-大题模拟试题及答案

计算题一 1. 下列线性规划问题化为标准型。(10分) 123min +5-2Z x x x =- 123 123121236 23510 0,0,x x x x x x x x x x x +-≤-+≥+=≥≤符号不限 2. 写出下列问题的对偶问题 (10分) 123min 42+3Z x x x =+ 123123121234+56=7 891011121314 0,0x x x x x x x x x x x --+≥+≤≤≥无约束， 3. 用最小元素法求下列运输问题的一个初始基本可行解(10分) 4．某公司有资金10万元，若投资用于项目 (1,2,3)i i i x =的投资额为时，其收益分别为11122()4,()9,g x x g x x == 33()2,g x x =问应如何分配投资数额才能使总收益最大？(15分) 5． 求图中所示网络中的最短路。（15分） 计算题二 满足 满足

1、某工厂拥有A,B,C 三种类型的设备，生产甲、乙两种产品，每件产品在生产中需要使用的机时数，每件产品可以获得的利润，以及三种设备可利用的机时数见下表： 求：（1）线性规划模型；（5分） （2）利用单纯形法求最优解；（15分） 4. 如图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从 1v 出发，经过这个交通网到达8v ，要寻求使总路程最短的线路。 （15分） 5. 某项工程有三个设计方案。据现有条件，这些方案不能按期完成的概率分别为0.5,0.7,0.9,

即三个方案均完不成的概率为0.5×0.7×0.9=0.315。为使这三个方案中至少完成一个的概率尽可能大，决定追加2万元资金。当使用追加投资后，上述方案完不成的概率见下表，问应如何分配追加投资，才能使其中至少一个方案完成的概率为最大。(15分) 计算题三 1、某工厂要制作100套专用钢架，每套钢架需要用长为2.9m , 2.1m , 1.5m的圆钢各一根。已知原料每根长7.4m ，现考虑应如何下料，可使所用的材料最省？ 产品甲产品乙设备能力/h 设备A 3 2 65 设备B 2 1 40 设备C 0 3 75 利润/(元/件) 1500 2500 求：（1 （2）将上述模型化为标准型（5分） 2、求解下列线性规划问题，并根据最优单纯形法表中的检验数，给出其对偶问题的最优解。（15分） 123 ax437 m z x x x =++ 123 22100 x x x ++≤ 123 33100 x x x ++≤ 123 ,,0 x x x≥ 3．断下表中方案是否可作为运输问题的初始方案，为什么？（10分） 4.用Dijkstra算法计算下列有向图的最短路。（15分） 追加投资 （万元） 各方案完不成的概率 1 2 3 1 2 0.50 0.30 0.25 0.70 0.50 0.30 0.90 0.70 0.40 满足

(完整word版)第二章运筹学 线性规划

第二章 线性规划 主要内容：1、线性规划问题及数学模型 2、线性规划问题的解及其性质 3、图解法 4、单纯形法 5、大M 法和两阶段法 重点与难点：线性规划数学模型的建立：一般形成转化为标准型的方法：单纯形法的求解步骤。 要 求：理解本章内容，掌握本章重点与难点问题；深刻理解线性规划问题的基本概念、基本性质，熟练掌握 其求解技巧；培养解决实际问题的能力。 §1 线性规划的数学模型及解的性质 一、数学模型（一般形式） 例 1 已知某市有三种不同体系的建筑应予修建，其耗用资源数量及可用的资源限量如下表，问不同体系的面积应各建多少，才能使提供的住宅面积总数达到最大？ 解：设三种体系的建筑面积依次为1x ,2x ,3x 万平方米， 则目标函数为 321max x x x z ++= 约束条件为 ?? ?? ???????=≥≤++≤≤++≤++≤++3,2,10 4005.335.41470021015000 180190110200025301211000 122137105 3211321321321j x x x x x x x x x x x x x x j 例2 某工厂要安排生产甲、乙两种产品。已知：

问：如何安排两种产品的生产数量，才能使总产值最高？ 解：设 21,x x 分别为甲、乙两种产品的生产量： 则目标函数为 21127m ax x x z += 约束条件为??? ??? ?=≥≤+≤+≤+2,1,03001032005436049112121j x x x x x x x j 从以上两例可以看出，它们都属于一类优化问题。它们的共同特征： ①每一个问题都有一组决策变量（n x x x 21,）表示某一方案；这组决策变量的值就代表一个具体方案。一般这 些变量的取值是非负的。 ②存在一定的约束条件，这些约束条件可以用一组线性等式或不等式来表示。 ③都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示；按问题的不同，要求目标函数实现最大化或最小化。 满足以上三个条件的数学模型称为线性规划的数学模型。其一般形式为： 目标函数 n n x c x c x c z +++= 2211m ax (m in) 约束条件 ()()()????? ????=≥=≥≤+++=≥≤+++=≥≤+++n j x b x a x a x a b x a x a x a b x a x a x a j m n mn m m n n n n ,,2,1,0,,,22112222212111212111 可行解：满足约束条件的一组决策变量，称为可行解。 最优解：使目标函数取得最大（小）值的可行解，称为最优解。 最优值：目标函数的最大（小）值，称为最优值。 二、标准型 （一）问题的标准形式： n n x c x c x c z +++= 2211ma x ????? ?? ??=≥=+++=+++=+++n j x b x a x a x a b x a x a x a b x a x a x a j m n mn m m n n n n ,,2,1,022112222212111212111