下载文档原格式
（第三版）《运筹学》教材编写组编清华大学出版社运筹学第1章线性规划与单纯形法第1节线性规划问题及其数学模型二.线性规划与目标规划第1章线性规划与单纯形法第2章对偶理论与灵敏度分析第3章运输问题第4章目标规划第1章线性规划与单纯形法第1节线性规划问题及其数学模型第2节线性规划问题的几何意义第3节单纯形法第4节单纯形法的计算步骤第5节单纯形法的进一步讨论第6节应用举例第1节线性规划问题及其数学模型•1.1 问题的提出•1.2 图解法•1.3 线性规划问题的标准形式•1.4 线性规划问题的解的概念第1节线性规划问题及其数学模型线性规划是运筹学的一个重要分支。
线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。
特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。
从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。
它已是现代科学管理的重要手段之一。
解线性规划问题的方法有多种，以下仅介绍单纯形法。
1.1 问题的提出从一个简化的生产计划安排问题开始例1某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。
资源产品ⅠⅡ拥有量设备 1 2 8台时原材料A40 16kg原材料B0 4 12kg续例1该工厂•每生产一件产品Ⅰ可获利2元，•每生产一件产品Ⅱ可获利3元，•问应如何安排计划使该工厂获利最多?如何用数学关系式描述这问题，必须考虑称它们为决策变量。
产品的数量，分别表示计划生产设II I,,21x x ∙12416482212121≤≤≤+∙x ;x ;x x ,x ,x 这是约束条件。
即有量的限制的数量多少，受资源拥生产021≥∙x ,x ,即生产的产品不能是负值这是目标。
最大如何安排生产，使利润,∙数学模型⎪⎪⎩⎪⎪⎨⎧≥≤≤≤++=0124164823221212121x ,x x x x x :x x z max 约束条件目标函数例2. 简化的环境保护问题靠近某河流有两个化工厂(见图1-1)，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。
运筹学详解答案：1.1分别用图解法和单纯形法求解下列线性规划问题，（1）指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解；（2）当具有有限最优解时，指出单纯形表中的各基可行解对应可行域的那一顶点。
A. 图解法图中蓝线代表目标函数线，箭头代表其运动的方向，根据可行域的形状可知此题无最优解。
B. 单纯形法1.行变换法写出此线性规划问题的标准形式max z =5x 1+6x 2s.t.{2x 1−x 2−x 3=2−2x 1+3x 2+x 4=2x i ≥0,(i =1,2,3,4)系数矩阵经过行变换后可的到等价的约束条件如下max z =5x 1+6x 2⎪⎩⎪⎨⎧≥≤+-≥-+=0,23222.65max )4(21212121x x x x x x st x x Zs.t.{x 1−12⁄x 2−12⁄x 3+0x 4=10x 1+2x 2−x 3+x 4=4x i ≥0,(i =1,2,3,4)显然x 1,x 4是基变量利用单纯形表可以求出此题具有无界解。
当然还可以采用其他变量为基变量，例如将约束条件转化为s.t.{x 1+0x 2−34⁄x 3+14⁄x 4=20x 1+x 2−12⁄x 3+12⁄x 4=2x i ≥0,(i =1,2,3,4)此时x 1,x 2成为了基变量。
然后在利用单纯形法可以解出此题具有无界解。
C. 大M 法易知转换成标准形式后，约束问题的系数矩阵中不包含单位矩阵，这时我们可以添加一个人工变量x 5，并在系数矩阵中添加一列单位向量，同时令目标函数中人工变量的系数为任意大的负值，用“-M ”表示。
具体形式如下max z =5x 1+6x 2−Mx 5s.t.{2x 1−x 2−x 3+x 5=2−2x 1+3x 2+x 4=2x i ≥0,(i =1,2,3,4,5)1.在进行第二次迭代时，因为人工变量已经移除基了，我们可以在后续的计算中不考虑它。
2.在进行第三次迭代时，进基的变量是x 3，而其对应的列向量都是小于0的，故此我们可以判断此问题有无界解。
