下载文档原格式
线性规划问题的研究与优化线性规划是运筹学中的一个重要分支，主要研究如何在一系列约束条件下，寻找一组变量的最佳取值，使得某种目标函数的值达到最大或最小。
这是一个数学建模的问题，它的应用十分广泛，涉及到工程、经济、决策等众多领域。
线性规划问题的求解方法有很多，其中最常见的是单纯形法。
单纯形法是一种基于迭代的算法，通过循环改进当前解，逐步接近最优解。
在每一次迭代中，单纯形法通过选取非基变量入基和基变量出基，重新计算目标函数值，来达到不断优化解的目的。
虽然单纯形法在许多实际问题中具有很好的效果，但它的复杂度随着问题规模的增加而增加，对于大规模问题来说，计算时间会相对较长。
为了解决单纯形法在大规模线性规划问题中的效率问题，人们提出了许多优化的方法。
其中比较著名的是内点法和启发式算法。
内点法通过引入中心路径的概念，将原问题转化为一系列等价问题，并通过求解这些等价问题来逼近最优解。
相比于单纯形法，内点法具有更好的稳定性和全局收敛性，适用于复杂的大规模问题。
启发式算法则是一种基于经验和启发性的求解方法，通过寻找问题的局部最优解来接近全局最优解。
尽管启发式算法在求解效率上不如内点法，但在某些特定问题上有着很好的表现，例如在旅行商问题等NP难问题的求解中。
除了求解方法的优化，线性规划问题还有很多其他方面的研究。
例如，在现实生活中，由于各种原因，约束条件的系数可能会发生变化。
针对这种情况，研究人员发展了鲁棒优化方法，通过引入不确定性集合，使得求解结果能够在一定范围内具有鲁棒性。
此外，多目标规划也是线性规划问题的一个重要的扩展，它将问题目标的优化拓展到多个方面，从而在实际应用中更好地体现各种约束条件和目标的权衡。
线性规划问题的研究与优化不仅仅停留在理论层面，也有着广泛的应用。
例如，在运输领域，线性规划可以用来优化货物的调度和运输路径，从而降低成本和提高效率。
在金融领域，线性规划可以应用于投资组合优化问题，帮助投资者在风险和收益之间找到最佳平衡点。
商学院课程实验报告课程名称 运筹学 专业班级 金融工程班 姓 名 指导教师 成 绩2018年 9 月 20日学号：表2 所需营业员统计表星期一二三四五六日需要人数300 300350400480600 5503.建立线性规划模型设x j（j=1，2，…，7）为休息2天后星期一到星期日开始上班的营业员数量，则这个问题的线性规划问题模型为minZ=x1+x2+x3+x4+x5+x6+x7{x1+x4+x5+x6+x7≥300 x1+x2+x5+x6+x7≥300 x1+x2+x3+x6+x7≥350 x1+x2+x3+x4+x7≥400 x1+x2+x3+x4+x5≥480x2+x3+x4+x5+x6≥600x3+x4+x5+x6+x7≥550x≥0,j=1,2,…,7（二）操作步骤1.将WinQSB安装文件复制到本地硬盘，在WinQSB文件夹中双击setup.exe。
图1 WinQSB文件夹2.指定安装软件的目标目录，安装过程中输入用户名和单位名称（任意输入），安装完毕之后，WinQSB菜单自动生成在系统程序中，熟悉软件子菜单内容和功能，掌握操作命令。
图2 目标目录3.启动线性规划和整数规划程序。
点击开始→程序→WinQSB→Linear and Lnteger Programming，屏幕显示如图3所示的线性规划和整数规划界面。
图3 线性规划4.建立新问题或打开磁盘中已有文件。
按图3所示操作建立或打开一个LP问题，或点击File→New Problem建立新问题。
点击File→Load Problem打开磁盘中的数据文件，点击File→New Problem，出现图4所示的问题选项输入界面。
图4 建立新问题5.输入数据。
在选择数据输入格式时，选择Spreadsheet Matrix Form则以电子表格形式输入变量系统矩阵和右端常数矩阵，是固定格式，如图5所示。
选择Normal Model Form则以自由格式输入标准模型。
1.用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。
⎪⎩⎪⎨⎧≤≤≤≤≤++=83105120106max 212121x x x x x x z2.将下述线性规划问题化成标准形式。
（1）⎪⎪⎩⎪⎪⎨⎧≥≥-++-≤+-+-=-+-+-+-=无约束4,03,2,12321422245243min 4321432143214321x x x x x x x x x x x x x x x x x x x x z解：令z z -='，''4'44x x x -=⎪⎪⎩⎪⎪⎨⎧≥=-+-++-=+-+-+=-+-+-+-+-=0,,,,,,232142222455243'max 65''4'43216''4'43215''4'4321''4'4321''4'4321x x x x x x x x x x x x x x x x x x x x x x x x x x x x x z 3.分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中的可行域的哪个顶点。
⎪⎩⎪⎨⎧≥≤+≤++=0,825943510max 21212121x x x x x x x x z解：①图解法：②单纯形法：将原问题标准化：⎪⎩⎪⎨⎧≥=++=+++=0,,,825943510max 432142132121x x x x x x x x x x x x z C j10 5 0 0 θ 对应图解法中的点C B B b x 1 x 2 x 3 x 4 0 x 3 9 3 4 1 0 3 O 点 0x 48 [5] 2 0 1 8/5 σj 0 10 5 0 0 0 x 3 21/5 0 [14/5] 1 -3/5 3/2 C 点 10x 1 8/5 1 2/5 0 1/5 4 σj -16 0 1 0 -2 5 x 2 3/2 0 1 5/14 -3/14 B 点 10x 1 1 1 0 -1/7 2/7 σj35/2-5/14-25/14最优解为（1,3/2,0,0），最优值Z=35/2。
《运筹学》线性规划部分练习题一、思考题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对应的变量xk作为换入变量，可使目标函数值得到最快的减少。
10 . 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。
三、建立下面问题的数学模型1.某公司计划在三年的计划期内，有四个建设项目可以投资：项目I从第一年到第三年年初都可以投资。
线性规划中的最优解求解线性规划是一种在运筹学和数学中广泛应用的数学建模技术，通过确定一组线性约束条件下的最优解，以实现目标最大化或最小化。
最优解是指在满足给定约束条件的前提下，能使目标函数达到最优值的解。
在线性规划问题中，最优解的求解有多种方法。
本文将介绍线性规划中的两种主要方法：图解法和单纯形法。
一、图解法图解法是一种简单直观的方法，适用于只有两个变量的问题。
它通过在平面坐标系上画出约束条件的图形，找到可行域（满足所有约束条件的解集），并在可行域内寻找使目标函数达到最优值的点。
具体步骤如下：1. 绘制坐标系，并画出约束条件的直线或曲线。
每个约束条件都会限制变量的取值范围，在平面上形成一条直线或曲线。
2. 标出可行域。
根据所有约束条件的交集，确定满足所有约束条件的解的集合，即可行域。
可行域通常是一个多边形区域。
3. 确定目标函数。
根据问题的要求确定目标函数，并将其表示为直线或曲线。
4. 在可行域内寻找最优解。
通过平行于目标函数的线，将其移动至与可行域相切，并找到使目标函数取得最优值的点。
图解法的优点是简单易懂，能够提供初步的解决方案。
然而，对于复杂问题和具有多个变量的大规模问题，图解法可能不适用。
二、单纯形法单纯形法是一种基于矩阵运算的高效方法，适用于多变量和大规模问题。
它通过不断进行迭代计算，寻找最优解。
具体步骤如下：1. 将线性规划问题转化为标准形式。
标准形式要求目标函数为最小化问题，并且所有约束条件均为等式形式。
如果原问题不符合标准形式，可以进行线性变换进行转化。
2. 构建初始单纯形表。
将原问题的线性规划模型表示为矩阵形式，并构建单纯形表，包括目标函数系数、基变量和非基变量等信息。
3. 迭代计算。
根据单纯形表中的信息，进行迭代计算，通过选择合适的主元（即最大系数法则）和更新各个单元的值，逐步接近最优解。
4. 判断终止条件。
在每一次迭代计算后，判断是否满足终止条件，即目标函数是否达到最优解。
线性规划和最优解线性规划是一种在数学和运筹学领域常见的问题求解方法，可以应用于各种现实生活中的决策问题。
它是通过一系列线性等式和不等式来建模，并在满足特定约束条件下求解使目标函数取得最优值的变量值。
线性规划的最优解能够帮助我们做出高效的决策，下面将详细介绍线性规划的原理和求解方法。
一、线性规划的基本概念线性规划中，我们首先需要明确问题的目标，并将其表示为一个线性函数，也被称为目标函数。
目标函数可以是最大化或最小化的，具体取决于问题的需求。
其次，我们需要确定一组变量，这些变量的取值将会对目标函数产生影响。
接下来，我们还需要列举出一系列约束条件，这些约束条件通常来自于问题的实际情况，例如资源限制、技术要求等。
最后，我们需要确定这些变量的取值范围，这也是约束条件的一部分。
二、线性规划的数学建模在线性规划中，我们可以通过以下步骤进行数学建模：1. 确定目标函数：根据问题的要求，我们可以定义一个线性函数作为目标函数。
例如，如果我们要最大化某个产品的利润，那么利润就可以是目标函数。
2. 列举约束条件：根据问题的实际情况，我们需要列举出一系列约束条件。
这些约束条件可以是线性等式或不等式，并且通常包含了变量的取值范围。
3. 确定变量的取值范围：根据问题的实际情况，我们需要确定变量的取值范围。
例如，如果某个变量代表一个产品的产量，那么它的取值范围可能是非负数。
4. 构建数学模型：根据目标函数、约束条件和变量的取值范围，我们可以构建一个数学模型，将问题转化为线性规划模型。
三、线性规划的最优解求解方法线性规划的最优解可以通过以下方法求解：1. 图形法：对于只有两个变量的简单线性规划问题，我们可以通过绘制变量的可行域图形，并计算目标函数在图形上的最优解点来求解问题。
2. 单纯形法：单纯形法是一种常用的求解线性规划问题的算法。
它通过逐步迭代改进解向量，从而逼近最优解。
这个方法通常适用于复杂的线性规划问题，可以在较短的时间内得到比较好的结果。
线性规划与最优解线性规划（Linear Programming）是一种数学优化方法，旨在找到一个最优解以满足约束条件。
它广泛应用于经济学、管理学、工程学等领域，用于解决诸如资源分配、生产计划、运输问题等实际情景中的决策问题。
一、线性规划的基本概念线性规划的基本概念包括目标函数、约束条件和决策变量。
目标函数是要最小化或最大化的线性表达式，约束条件则是决策变量需满足的线性不等式或等式。
例如，假设某公司生产A和B两种产品，目标是最大化利润。
假设每单位产品A的利润为10元，每单位产品B的利润为15元。
同时，公司有以下约束条件：A产品的生产时间不得超过40小时，B产品的生产时间不得超过30小时，A和B产品的总产量不得超过1000个。
这个问题可以用线性规划来建模。
二、最优解的求解方法1. 图形法线性规划的最优解可以通过图形法求解。
在二维平面上，将目标函数和约束条件分别画出，找到它们的交点，即可确定最优解。
2. 单纯形法单纯形法是一种高效的求解线性规划问题的方法。
该方法通过一系列迭代计算，逐步接近最优解。
它的核心思想是通过调整决策变量的取值，使目标函数值逐步增大或减小，直到达到最优解。
三、线性规划的应用案例1. 资源分配问题线性规划可以应用于资源分配问题。
例如，某公司有限的资源需要在不同项目之间进行分配。
通过线性规划，可以找到满足约束条件下的最优资源分配方案。
2. 生产计划问题线性规划可以应用于生产计划问题。
例如，某工厂需要在不同生产线上安排不同产品的生产数量，以最大化利润或最小化生产成本。
3. 运输问题线性规划可以应用于运输问题。
例如，某物流公司需要决定不同运输路线的货物数量，以最小化运输成本或最大化运输效率。
四、线性规划的局限性虽然线性规划可以解决许多实际问题，但它也有一定的局限性。
首先，线性规划要求目标函数和约束条件都是线性的，无法处理非线性问题。
其次，线性规划的可行解和最优解并不唯一，可能存在多个相同的最优解。
线性规划问题最优解的确定与改进
线性规划是运筹学的一个重要分支。
自1947年丹捷格（G.B.Dantzig ）提出了一般线性规划问题求解的方法——单纯形法之后，线性规划在理论上趋向成熟，在实用中日益广泛与深入。
线性规划最优解求解问题，在《运筹学》本科版给出了图解法和单纯形法。
一般线性规划问题的标准型为：
1
max (14)n
j j
i z c x ==-∑
1,1,2(15)0,1,2,(16)
n
i j j i j j a x b i m x j n ===-≥=-⎧∑⎪⎨⎪⎩
满足约束条件（1-5）式、（1-6）式的解12(,,,)T n X x x x =，称为线性规划问题的可行解，其中
使目标函数达到最大值的可行解称为最优解。
2009年中国科教创新导刊，第三十期李高秀写的《线性规划中最优解的准确确定》中详细介绍了图解法的过程，图解法适合于二元线性规划问题，对于多元线性规划问题图解法相对较难。
图解法过程：
1 线性目标函数最值的分析
对于线性目标函数Z=ax+by ，若b ≠0时，目标函数可变为a z y x b b =-+，
则是直线a z
y x b b
=-+在y 轴上的截距。
(1)b>0时，随着直线a z
y x b b
=-+的平移，直线在与可行域有公共点的条件下，它在y 轴上的截距
z b 最大时z 最大；当z
b
最小时z 最小。
(2)b<0时，随着直线a z
y x b b
=-+的平移，直线在与可行域有公共点的条件下，它在y 轴上的
截距z b 最大时z 最小；当z
b
最小时z 最大。
由以上两点可知，要求线性目标函数z=ax+by 的最大最小值要注意y 的系数b 的正负和平移直线在y 轴上的截距。
2 在图上分别作出约束函数和目标函数，平移目标函数线到可行域的交点时，要把目标函数的斜率与相交于这一点的直线的斜率进行比较
上述的最值分析是确定平移目标函数的大概方向，而这次是确定最优解的确凿位置。
斜率比较大
小的目的是直观形象的比较两直线的方向和倾斜程度。
具体的做法是：
(1)若目标函数的斜率是正(或负)的，只需要与斜率为正(或负)的直线进行比较，即与斜率同号的比较。
(2)比较斜率的绝对值，绝对值越大所对应的直线的倾斜程度越大，从直观来看直线越陡。
根据上述的1和2，可准确的确定最优解的位置
单纯形法：
单纯形法的一般解题步骤可归纳如下：
① 线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。
② 若基本可行解不存在，即约束条件有矛盾，则问题无解。
③ 若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基
变量取代某一基变量，找出目标函数值更优的另一基本可行解。
④ 按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到
问题的最优解。
⑤ 若迭代过程中发现问题的目标函数值无界，则终止迭代。
2006年甘肃联合大学学报(自然科学版)第三期，在熊洪斌发表的论文《线性规划最优解的进一步研究》中研究了线性规划最优解的参数表示，通过对某一最优解引入参数向量，得到新的LPP 模型．通过求解LPP 模型便可得到LP 最优解的参数表达式。
人们在求解LP 问题时常用单纯形方法求出一组最优解便终止．这样的思想和方法有时是不可取的．因为方案的单一性不便于决策者在短期内根据条件的变化进行灵活调整，从而使原有期望不变．用参数向量表示最优解，便可实现这一目的。
LLP 方法介绍如下：
1 定义与引理
定义1 区间向量：若一向量的每个分量均为一区间数，则称该向量为区间向量．普通向量也是区间向量的一种特殊形式。
引理1 若LP 问题min ...cx s t Ax b =，0x ≥有最优解*x 。
则*x ω+为原LP 问题最优解的充要条件是：0c ω=，0A x =，*0x ω+≥，其中12(,,
,)n c c c c =12(,,
,)T n x x x x =， ****12(,,,)T
n x x x x =，
()ij m n
A a ⨯=，
12(,,
)T
m b b b b =，
1
0(0,0,
,0)T m ⨯=，12(,,,)T n ωωωω=。
2 LPP 模型的建立
考虑标准型LP 问题：min ...cx s t Ax b =，0x ≥。
设其某一最优解*x ，则有与之对应的LPP 模型：
*min 0,0,0cx A x ωω==+≥。
由引理1和LP 理论有以下定理：
定理1 设N ξ为LP 问题非基变量的判别数集．(N 为非基变量下标集)则 (1) ,0j j N ξω∀∈<⇔为零向量⇔问题有惟一最优解． (2) ,0j j N ξω∃∈<⇔为区间向量⇔LP 有无穷组最优解。
含义：ω为零向量，表明决策者选择方案惟一。
ω为区间向量，表明决策者可随时根据条件变化调整既定方案，使原有期望不变。
3 ILPP 模型的建立
考虑ILP 问题：min ...cx s t Ax b =，x Z ∈，0x ≥(z 为整数)，则与之对应的ILPP 模型为
min 0c ω=，...0s t A ω=，*0x ω+≥，Z ω∈。
对ILPP 模型，有以下定理： 定理2：
(1,0j j N ξω∀∈<⇔为零向量⇔lLP 问题有惟一最优解． (2) ,0j j N ξω∃∈<⇔为区间向量⇔lLP 有多重最优解．
4 数值求解
问题：现有一投资商对A 、B 两项产品投资，其投资利润及相关条件如下表：
A 产品
B 产品 数量 情况变化 （1） 情况变化 （2） 利润 1千元/件
1千元/件
机器 2 1 6 2台故障 1台故障 人员
4
5
2
0人请假
1人请假
问：该投资商在正常情况下如何安排生产，利润最大?条件变化又该如何安排生产(A 、B 产品数量需整数)?
解 根据题意，可得下列模型：
12max z x x =+ (1x ，2x 分别是A 、B 的生产数量)．
121226;()..4520;0,1,2.i
x x ILP s t x x x i +≤⎧⎪
+≤⎨⎪≥=⎩
本文用割平面法解上述(ILP)，则上述(ILP)问题对应的LP 松驰问题为：
12123124max .26;
()..4520;
0,1,2,3,4.i
z x x x x x LP s t x x x x i =+++=⎧⎪
++=⎨⎪≥=⎩ LP 单纯性表如下：
对表一单纯选得最优表二
由表二中的1x 为源行，可得割平面方程：134333
s x x =-++，将1s 置于尾行并作为基。
于是得ILP 的一组最优解12x =，22x =，max 4z =。
为了考察情况变化是否直接影响投资者利益，我们有必要考虑如下模型ILPP ：
121231241234
min()0.
20;..450;
2,2,0,0;
,,1,2,3,4.
s t i Z i ωωωωωωωωωωωωω+=⎧
⎪++=⎪⎪++=⎨⎪≥-≥-≥≥⎪∈=⎪⎩
通过求解ILPP 问题，可得ILP 的最优解可表示为：
111111(2,2,,3),[2,0],.Z ωωωωωω+---∈-∈ 由ILP 最优解的参数表达式可知：在正常状况下，投资者有三种方案可供选择，分别为： 方案一 1120,2, 2.x x ω=== 方案二 1121,1, 3.x x ω=-== 方案三 1122,0, 4.x x ω=-==
根据情况变化(1)，投资者只可选择方案三；
根据情况变化(2)，投资者只可选择方案二。
通过LP 和ILP 模型的转换求出其最优解集，可让决策者更好地对其可利用资源进行更合理的分配，获得最佳利润，而不像单纯性表法只有一组最优解，一次LP 和ILP 模型有其优越性，可以用于解决最优化问题。
【参考文献】：
[1] 薛声家，刘 惠．一般形式线性规划最优解集的确定[M]．广州：暨南大学出版社，2001.2
[2] 熊洪斌. 线性规划最优解的进一步研究[M]. 甘肃：甘肃联合大学学报编辑部，2006.6
[3] 李高秀. 线性规划中最优解的准确确定[M].北京：中国科学技术信息研究所（ISTIC ） 科学技术文献出版社，2009。
