线性规划

单纯形法是一种用于求解线性规划问题的方法，其中基变量转换是这个过程中的一个重要步骤。在进行基变量转换时，需要遵循以下条件：1.新的基变量必须是非基变量中系数为正的变量。2.新的基变量必须要与非基变量之间存在唯一的原始变量关系。3.将新的基变量代入目标函数中后，必须保证目标函数值有望被优化，即系数为正，否则要进行人工变量的添加。同时，还_

首先得明白什么是线性规划，通俗地可理解为单变量或多变量求目标函数极值的问题。既然这样，我们就可以下手了。所有的变量在EXCEL中就是单元格。一个单元格可以看成一个变量。多变量就用多个单元格。例A3为变脸既然有变量和目标函数，那么肯定有条件函数。条件函数可理解为变量必须满足的条件，例A3+5>=10。这些条件函数也可以用单元格之间的公式计算表示出来。最后一步就是进入“线性规划”或“规划求解”（一般是在“工具那一栏”），把上述的信息按要求输入，点击“求解”，即可得到结果。结果一般为近似最优解，即当变量在这个值时，目标函数得到最优。以上是我个人总结的基础概念。若要具体步骤，可以看EXCEL帮助，或找其他教程。希望你采纳，谢谢

残差图怎么会是线性规划呢？ 残差图指以残差为纵坐标，以任何其他指定的量为横坐标的散点图，可以用来判断回归模型是否是线性和等方差。 残差图上的点是无规律，随机分布的。在分析测试中常用的散点图是以自变量为横坐标的残差图。可用它来检查回归线的异常点。 残差图”以回归方程的自变量为横坐标，以残差为纵坐标，将每一个自变量的残差描在该平面坐标上所形成的图形。当描绘的点围绕残差等于0的直线上下随机散布，说明回归直线对原观测值的拟合情况良好。否则，说明回归直线对原观测值的拟合不理想。 高考一般就最多出个选择题或填空题吧，

偶形式： 2y1-y2-y3=-2 3y1-2y2-3y3=-4 求 max -24y1+10y2+15y3 优解 y1=0,y2=2,y3=0 优值 20 设原始问题min{cx|Ax=bx≥0}则其偶问题 max{yb|yA≤c}

线性规划模型的对偶性，对线性规划模型理论、求解有着很重要的意义。特别在应用上，线性规划对偶问题的最优解，就是资源的影子价格，它对于线性规划模型的经济分析，用于对经济管理工作的指导起了极为重要的作用。市场价格是已知的，而影子价格则与资源的利用情况有关，利用的好，影子价格就高，反之亦然。影子价格是一种边际价格（对偶变量在经济上表示原问题第i种资源的边际价值） 。影子价格又是一种机会成本。当市场价大于影子价格，卖出资源；当市场价小于影子价格，买入资源，组织生产。影子价格说明了不同资源对总的经济效益产生的影响，因此对企业经营管理提供一些有价值的信息。扩展资料对偶理论则广泛应用于经济分析中。例如，在经济均衡的分析中，可以通过设计优化模型，运用对偶理论和模型体系研究市场均衡及其实现均衡所需要的基本条件。对偶原理在现代数学特别是几何学、代数学、拓扑学等学科中有着广泛的应用，对于推动数学的发展起着很好的作用。举例来讲，在范畴论中，借助于对偶变换（对偶化），由始对象便可得终对象、由单态射得满态射、由核得上核、由积得上积；在同调代数中，由正向极限得反向极限、由内射模得投射模、由内射包得投射包、由投射分解（维数）得内射分解（维数）、由复形得上复形、由双复形得上双复形、由同调得上同调等。参考资料来源：百度百科-对偶参考资料来源：百度百科-对偶问题

线性规划模型的对偶性，对线性规划模型理论、求解有着很重要的意义。特别在应用上，线性规划对偶问题的最优解，就是资源的影子价格，它对于线性规划模型的经济分析，用于对经济管理工作的指导起了极为重要的作用。市场价格是已知的，而影子价格则与资源的利用情况有关，利用的好，影子价格就高，反之亦然。影子价格是一种边际价格（对偶变量在经济上表示原问题第i种资源的边际价值） 。影子价格又是一种机会成本。当市场价大于影子价格，卖出资源；当市场价小于影子价格，买入资源，组织生产。影子价格说明了不同资源对总的经济效益产生的影响，因此对企业经营管理提供一些有价值的信息。扩展资料对偶理论则广泛应用于经济分析中。例如，在经济均衡的分析中，可以通过设计优化模型，运用对偶理论和模型体系研究市场均衡及其实现均衡所需要的基本条件。对偶原理在现代数学特别是几何学、代数学、拓扑学等学科中有着广泛的应用，对于推动数学的发展起着很好的作用。举例来讲，在范畴论中，借助于对偶变换（对偶化），由始对象便可得终对象、由单态射得满态射、由核得上核、由积得上积；在同调代数中，由正向极限得反向极限、由内射模得投射模、由内射包得投射包、由投射分解（维数）得内射分解（维数）、由复形得上复形、由双复形得上双复形、由同调得上同调等。参考资料来源：百度百科-对偶参考资料来源：百度百科-对偶问题

线性规划模型的对偶性，对线性规划模型理论、求解有着很重要的意义。特别在应用上，线性规划对偶问题的最优解，就是资源的影子价格，它对于线性规划模型的经济分析，用于对经济管理工作的指导起了极为重要的作用。市场价格是已知的，而影子价格则与资源的利用情况有关，利用的好，影子价格就高，反之亦然。影子价格是一种边际价格（对偶变量在经济上表示原问题第i种资源的边际价值） 。影子价格又是一种机会成本。当市场价大于影子价格，卖出资源；当市场价小于影子价格，买入资源，组织生产。影子价格说明了不同资源对总的经济效益产生的影响，因此对企业经营管理提供一些有价值的信息。扩展资料对偶理论则广泛应用于经济分析中。例如，在经济均衡的分析中，可以通过设计优化模型，运用对偶理论和模型体系研究市场均衡及其实现均衡所需要的基本条件。对偶原理在现代数学特别是几何学、代数学、拓扑学等学科中有着广泛的应用，对于推动数学的发展起着很好的作用。举例来讲，在范畴论中，借助于对偶变换（对偶化），由始对象便可得终对象、由单态射得满态射、由核得上核、由积得上积；在同调代数中，由正向极限得反向极限、由内射模得投射模、由内射包得投射包、由投射分解（维数）得内射分解（维数）、由复形得上复形、由双复形得上双复形、由同调得上同调等。参考资料来源：百度百科-对偶参考资料来源：百度百科-对偶问题

对应的对偶变量无约束，选D

大M法和两阶段法同属于人工变量法,针对线性规划问题中约束条件是大于等于形式的情况,不能直接找到初始基可行解（单位矩阵）,采用人造基的方法. 对偶单纯形法是在原问题的初始解不一定是基可行解的情况下,利用对偶理论,从非基可行解开始迭代,适用于变量较少但约束条件很多的线性规划问题.

Farkas 引理在对偶理论中有重要的应用，并且还被用来证明KKT条件。 这个引理代数形式可以有多种，但是它的几何意义是恒定而简明的。 一个矩阵 的所有列向量可以张成一个锥，另一个向量 ，与这个锥的位置关系只有两种：在锥内，不然就在锥外。所以 在锥内和 在锥外时成立的代数关系，恰好只有一个也必然有一个是成立的，同时另一个就不成立了。 如果 在锥内，那么可以找到一组非负的系数，使得 能被 的列向量线性表示，即存在 。 如果 在锥外，那么根据点与凸集的分离定理， 和 的列向量张成的锥，可以被一个（过原点的）超平面分离，设这个超平面的法向量为 ，那么可以有： 。 这个定理也可以通过替代定理的方式去证明：上面两式与之前的代数形式本质上是一样的。现考虑一个线性规划问题和它的对偶问题：如果(1)式无解，那么LP问题的最优值 ，因为强对偶性成立，所以下方的对偶问题 ，从而(2)式必然有解（如果(2)式无解，那么 ）；如果(1)式有解，那么 ，(2)式无解。 这里很重要的一点就是LP成立强对偶性！ 除此以外，Farkas引理还有纯代数的证明：如果 ，使得 ，那么如果 ，就有 ；如果存在 使得 并且 ，那么如果 ， ，从而 。 Farkas引理可以用来论证线性规划的强对偶性。 设线性规划的原问题 和对偶问题 分别具有最优值 和 。弱对偶性是显然的，因为如果 满足 是原问题的最优值，那么 ，从而 。 现在借助Farkas引理说明强对偶性，设 ，以及： 现在 是原问题的一个严格下界，所以 是可行的，而 是不可行的。应用两次Farkas引理，设 ，我们有： 可知 、 ，从而 这样其实找到了对偶问题的一个可行点 ，从而： 因为 是任意的，所以 ，强对偶性成立！ 从强对偶性出发，关于对偶变量，我们能够得到以下等式： 上面的 是约束条件 的对偶变量。我们有： 因为 ，所以 必有一为0。

给定线性规划的原始问题, 本文介绍写如何方便地写出其对偶问题. 我们先给出互为对偶问题的两种基本形式, 作为后续写对偶问题的基础. 1. 原问题的约束是不等式 2. 原问题的约束是等式 总结 对原问题的每一个约束, 定义一个对偶变量 . 如果一个约束是等式, 其对偶变量无非负限制. 把对偶变量乘以原问题的约束. 约束右端 即为对偶问题的目标. 上一步把对偶变量乘以原问题的约束之后, 接着计算原问题约束中决策变量 的系数 , 从而得到对偶问题的约束 (假设原问题是最小化问题). 原问题 定义对偶变量 , , 分别对应原问题的约束 和 . 对偶问题 原问题 如上面所示, 我们定义对偶变量 , . 原问题的约束是等式约束, 因此不要求 非负. 用 乘以每个等式, 得到对偶问题的目标: . 下面计算对偶问题的约束: 为了方便描述, 我们使用新的下标 , 并计算 的系数. 详细的计算过程如下: 综合上面所有对偶问题的约束, 我们得到: 对偶问题 Ex1 原问题 对偶问题 Ex2 原问题 对偶问题

1、线性规划一般模型中，自由变量可以用两个非负变量的 （ ）代换。A．和 B．差 C．积 D．商2、对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足 （ ）A．等式约束 B．“≤”型约束 C．“≥”约束 D．非负约束3、原问题的第i个约束方程是“=”型，则对偶问题的变量yi是 （ ）A．多余变量 B．自由变量 C．松弛变量 D．非负变量1 选B 即任意变量X=X"-X""2 选D 对偶单纯型法 是保持检验数≤0，但逐步使基变量值变成非负，即一开始 迭代之前 b 是小于零的 即基变量的值开始是小于等于0的。3 选B 对偶变量yi无约束。

matlab自己带的函数是没带影子价格的。不过你可以自己调整约束条件，计算影子价格。影子价格实际上是描述一种边际效应。假设现在已经求解出当前约束下的最优值了，现在思考个问题：这个最优解是在这些约束下求解得到的，假如放宽某个约束（比方说，原来约束是原料X最多只有100kg，现在放宽到最多有101kg），会给目标函数带来多大的改进呢？假设原料X放宽一个单位，目标函数（假设代表利润）可以多出500元，那么500元/kg就是原料X的影子价格。（此段转自知乎，作者：吴俊）你可以自己修改约束条件来计算，不过存在边际效应递减等边际效应的变化，所以更改约束条件时请注意这一点。

不会

混合离散非线性规划（Mixed Integer Nonlinear Programming，MIPNLP）是一种求解约束型非线性优化问题的方法。它将非线性规划中的离散变量和连续变量结合起来，既能够处理离散变量又可以处理连续变量。该方法通过将不确定的变量限制在一定的范围内，使其解决问题的空间减少，从而提高求解的效率。MIPNLP的优点在于可以灵活的处理复杂的非线性规划问题，但是这种方法也有一定的局限性，一般只适用于小规模的问题。

看看百科吧，【单纯形法】http://baike.baidu.com/view/471090.htm是用来求最优解的

可以尝试LINGO 11.0，这是专业的规划求解软件，语法简单，求解速度快，而且资源占用小，特别适合大规模规划。我做数学建模的时候基本遇到规划问题就用lingo去求。建议用Lingo 11，不受规模限制。Lingo 12及以上的免费版对最大规模有限制。

1/11 分步阅读开始第一步我们打开在电脑桌面找到matlab小程序，然后鼠标右击打开桌面上matlab程序，运行起来。由于不同人电脑的配置不一样，软件打开的速度也有所不同，一般固态硬盘比机械硬盘运行的要快好多。大家稍微等待一下。2/11我们为了便于保存数据，我们点击matlab左上角新建脚本命令，创建新的脚本，创建M文件，也便于程序的保存，我们可以将其保存在电脑的其他盘，以便于我们的寻找和使用，这也是比较常见的方式。3/11这是一个常见的二次非线性规划的方程，有目标函数，有约束条件，让其在约束条件的情况下求其的最优解和最优值下面问题有五个约束条件求约束条件的最小值4/11首先建立一个M文件fun_ex5.m文件输入程序如下 function f=fun_ex5(x); f=2*x(1)-x(2)*exp(x(1)); 其中exp代表指数函数*代表乘5/11新建的文件如下图所示是一个m文件m文件只能通过matlab打开不能再桌面上直接双击打开大家注意下6/11建议另一个m文件，文件名为mycon_ex5.m，定义非线性的约束程序如下function [g,ceq]=mycon_ex5(x) g=[x(1)^2+(x2)^2-12;x(1)^2-x(2)^2-5]; ceg=[ ];注意符号书写的方式以及字母书写方式7/11新建的文件如下图所示是一个m文件m文件只能通过matlab打开不能再桌面上直接双击打开大家注意下8/11输入程序：>> x0=[1;1];>> lb=[0;0];>> ub=[5;8];9/11输入程序：>> [x,fval,exitflag,output]=fmincon("fun_ex5",x0,[],[],[],[],lb,ub,"mycon_ex5")记住字母书写的方式以及输入状态10/11最优值为fval=-28.700011/11最优解为x=2.91551.8708

说清楚点

现在有解决过程了吗 同求做法

是惩罚吧，现在解线形规划都用LINDO这个软件来解了，要是非线形规划就用LINGO来解大M法（通过下例简略介绍其方法与步骤）例，用大M法求解MinZ=x1+1.5x2解：MinZ=x1+1.5x2+0.x3+0.x4+Mx5+Mx6其中x3,x4为松驰变量，x5,x6为人工变量，M为任意大的正数。注意到：①分别在约束条件增加人工变量x5,x6是为了构成“人工基”②对于Min的目标函数采用(+M)，而对于Max的目标函数则采用(-M)作为人工变量的系数,是强加于人工变量的一种惩罚,其目的是为了强制人工变量由变量转为非基变量，使之恢复原问题，或与原问题等价。③对于minZ判别最优性准则应是Cj－Zj≤0。④大M法适合于手算，不适用于计算机求解。

线性规划来源：《信息系统项目管理师教程（第3版）》第27章 管理科学基础知识P875线性规划是研究在有限的资源条件下，如何有效地使用这些资源达到预定目标的数学方法。用数学的语言来说，也就是在一组约束条件下寻找目标函数的极值问题。求极大值（或极小值）的模型表达如下。1.图解法解线性规划问题的方法有很多，最常用的有图解法和单纯形法。图解法简单直观，有助于了解线性规划问题求解的基本原理，下面，通过一个例子来说明图解法的应用。【例】某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原料的消耗，如表27-5所示。该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应该如何安排计划使该工厂获利最多？的点，必然落在由这三个半平面相交组成的区域内，如图27-13中的阴影部分所示。阴影区域中的每一个点（包括边界点）都是这个线性规划问题的解（称可行解），因而此区域是本题的线性规划问题的解的集合，称它为可行域。图27-13图解法。这说明该厂的最优生产计划方案是：生产4件产品Ⅰ，2件产品Ⅱ，可得最大利润为14元。2.解的讨论在上述例题中，得到的最优解是唯一的，但对一般线性规划问题而言，求解结果还可能出现以下几种情况：无穷多最优解（多重解），无界解（无最优解），无可行解。当求解结果出现后两种情况时，一般说明线性规划问题的数学模型有错误。无界解源于缺乏必要的约束条件，无可行解源于矛盾的约束条件。从图解法中直观地看到，当线性规划问题的可行域非空时，它是有界或无界凸多边形。若线性规划问题存在最优解，它一定在可行域的某个顶点得到；若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷多最优解。3.单纯形法图解法虽然直观，但当变量数多于3个以上时，它就无能为力了，这时需要使用单纯形法。单纯形法的基本思路是：根据问题的标准，从可行域中某个可行解（一个顶点）开始，转换到另一个可行解（顶点）。并且使目标函数达到最大值时，问题就得到了最优解。限于篇幅，本书不再介绍单纯形法的详细求解过程。4.线性规划的适用性线性规划模型用在原材料单一、生产过程稳定不变、分解型生产类型的组织是十分有效的，例如，石油化工厂等。对于产品结构简单、工艺路线短，或者零件加工组织，有较大的应用价值。需要注意的是，对于机电类组织用线性规划模型只适用于作年度的总生产计划，而不用来做月度计划。这主要与工件在设备上的排序有关，计划期太短，很难安排过来。一般来说，一个经济管理问题满足以下条件时，才能建立线性规划的模型。(1)要求解问题的目标函数能用数值指标来反映，且为线性函数。(2)存在着多种方案。(3)要求达到的目标是在一定约束条件下实现的，这些约束条件可用线性等式或不等式描述。

网页链接

单位矩阵，就是高等代数里面的单位矩阵的行（或列）次序打乱。 添加人工变量，在大学运筹学上将的很清楚，你参考下就好了，做两个问题，你就知道了！

用人工变量法的时候 最优解人工变量没有出基 或者两阶段法中第一阶段最优解的目标函数不为0，即接种有非0的人工变量，即无可行解。

#include <stdio.h>#include <stdlib.h>#define MAX 100#define STP 100 int stop=1; //迭代记数变量int status; //iterative迭代返回值：1唯一最优，0无界解，-1无穷多最优解 -2迭代超过限制次数int step=1; //目前阶段 double a[MAX][MAX],b[MAX],c[MAX],temp_c[MAX],max=0; //方程组相关系数int num_x; //变量个数 int num_st; //约束方程数int num_ar=0; //人工变量个数int arti[MAX]; //人工变量下标int base[MAX]; //基变量下标int ma_mi; //1为求最大值，2为求最小值 void create(); //建立方程组void iterative(); //单纯型法迭代void output(); //输出结果void banner(); //打印程序标题void exchange(); //交换两阶段价值系数void show(); //输出方程组 void main() {int i,j,k;banner();create();//保存原价值系数，转换为第一阶段价值系数for(i=1;i<=num_x;i++) {k=0;for(j=1;j<=num_ar;j++) if(i==arti[j]) k=1;if(k==1) temp_c=-1;else temp_c=0;}exchange(c,temp_c); printf(" 第一阶段问题为： ");show();step++;printf(" 按回车开始第一阶段迭代");getchar(); getchar();iterative();if(status==-2) {puts("迭代超过限制次数强行终止！ ");puts(" 按回车结束");getchar();exit(0);}output(); if(max!=0) {puts(" 原问题无可行解。 ");puts(" 按回车结束");getchar();exit(0);} //转换为第二阶段价值系数exchange(c,temp_c);//把人工变量列全设为0for(i=1;i<=num_ar;i++) {c[arti]=0;for(j=1;j<=num_st;j++) a[j][arti]=0;} puts(" 第二阶段问题为： ");show();puts(" 按回车开始第二阶段迭代");getchar(); iterative();switch(status) {case 1:output();puts(" 原问题有唯一最优解。 ");puts(" 按回车结束");getchar();exit(0);case 0:puts(" 原问题为无界解。 ");puts(" 按回车结束");getchar();exit(0);case -1:output();puts(" 原问题有无穷多最优解。 ");puts(" 按回车结束");getchar();exit(0);case -2:puts("迭代超过限制次数强行终止！ ");puts(" 按回车结束");getchar();exit(0);}//switch} void banner() {printf(" **************************************** ");printf(" 单纯型法解线性规划问题 ");printf(" 作者：Thunder ");printf(" **************************************** ");printf(" ");} void show() {//对方程组以自然的格式输出，系数为零的x不显示//为1的不显示系数1，-1系数只显示负号int i,j,k;switch(step) {case 1:printf("min z= ");printf("x[%d]",arti[1]);for(i=2;i<=num_ar;i++) printf(" + x[%d]",arti);break;case 2:printf("max z= ");printf("%lg x[%d]",c[1],1);for(i=2;i<=num_x;i++) {if(c==1) printf(" + x[%d]",i);else if(c==-1) printf(" - x[%d]",i);else if(c>=0) printf(" +%lg x[%d]",c,i);else printf(" %lg x[%d]",c,i);}break;} printf(" st: ");for(i=1;i<=num_st;i++) {k=0;for(j=1;j<=num_x;j++) { if(a[j]!=0) {if(a[j]==1&&k!=0) printf(" + x[%d]",j);else if(a[j]==1&&k==0) printf(" x[%d]",j);else if(a[j]==-1) printf(" - x[%d]",j);else if(a[j]>=0&&k!=0) printf(" +%lg x[%d]",a[j],j);else if(a[j]>=0&&k==0) printf(" %lg x[%d]",a[j],j);else printf(" %lg x[%d]",a[j],j);k=1;}}printf(" == %lg ",b); }printf(" x[1]~x[%d]>=0",num_x);} void exchange() {int i;double temp[MAX];for(i=1;i<=num_x;i++) {temp=temp_c;temp_c=c;c=temp;}} void create() {//输入方程组系数，每个方程输完后回显确认int i,j,k,re_st[MAX],tnum_x,num_addv=0,num_ba=0;char confirm;while(1) {printf("请选择：1、求最大值，2、求最小值：(1/2)");scanf("%d",&ma_mi);if(ma_mi!=1&&ma_mi!=2) printf("输入错误，重新选择。");else break;}while(1) {printf("指定变量个数：");scanf("%d",&num_x);printf("输入价值系数c1-c%d: ",num_x);for(i=1;i<=num_x;i++) { printf("c%d=",i);scanf("%lf",&c);}if(ma_mi==1) printf("max z= ");else printf("min z= ");printf("%lg x[%d]",c[1],1);for(i=2;i<=num_x;i++) {if(c>=0) printf(" +%lg x[%d]",c,i);else printf(" %lg x[%d]",c,i);}printf(" 正确吗？：(y/n)");getchar();confirm=getchar();if (confirm=="y") break;else if(confirm=="n") continue;} printf("输入约束方程组个数：");scanf("%d",&num_st);for(i=1;i<=num_st;i++) {printf("st.%d: ",i);while(1) {printf("请选择：1、==，2、>=，3、<= ：(1/2/3)");scanf("%d",&re_st);if(re_st!=1&&re_st!=2&&re_st!=3) printf("输入错误，请重新选择。");else break;}printf("输入技术系数： ");for(j=1;j<=num_x;j++) { printf("a%d=",j);scanf("%lf",&a[j]);}printf("输入资源拥有量： b%d=",i);scanf("%lf",&b);printf("st.%i: ",i);printf("%lg x[%d]",a[1],1);for(j=2;j<=num_x;j++) {if(a[j]>=0) printf(" +%lg x[%d]",a[j],j);else printf(" %lg x[%d]",a[j],j);}switch(re_st) {case 1: printf(" == %lg",b); break;case 2: printf(" >= %lg",b); break;case 3: printf(" <= %lg",b); break;} while(1) {printf(" 正确吗？(y/n)");getchar();confirm=getchar();if (confirm=="y") break;else if(confirm=="n") {i-=1; break;}}} //显示输入的方程组printf(" 原问题为： ");if(ma_mi==1) printf("max z= ");else printf("min z= ");printf("%lg x[%d]",c[1],1);for(i=2;i<=num_x;i++) {if(c==1) printf(" + x[%d]",i);else if(c==-1) printf(" - x[%d]",i);else if(c>=0) printf(" +%lg x[%d]",c,i);else printf(" %lg x[%d]",c,i);} printf(" st: ");for(i=1;i<=num_st;i++) { k=0;for(j=1;j<=num_x;j++) {if(a[j]!=0) {if(a[j]==1&&k!=0) printf(" + x[%d]",j);else if(a[j]==1&&k==0) printf(" x[%d]",j);else if(a[j]==-1) printf(" - x[%d]",j);else if(a[j]>=0&&k!=0) printf(" +%lg x[%d]",a[j],j);else if(a[j]>=0&&k==0) printf(" %lg x[%d]",a[j],j);else printf(" %lg x[%d]",a[j],j);k=1;}}switch(re_st) {case 1: printf(" == %lg ",b); break;case 2: printf(" >= %lg ",b); break;case 3: printf(" <= %lg ",b); break;}}printf(" x[1]~x[%d]>=0 ",num_x); tnum_x=num_x;for(i=1;i<=num_st;i++) {switch(re_st) {case 1:case 3:num_x+=1;break;case 2:num_x+=2;break;}} //化为标准形式if(ma_mi==2) for(i=1;i<=tnum_x;i++) c*=-1; //求最小值时，系数变相反数for(i=1;i<=num_st;i++) {switch(re_st) {case 1:num_addv++;num_ba++;num_ar++;c[tnum_x+num_addv]=0; base[num_ba]=arti[num_ar]=tnum_x+num_addv;for(j=tnum_x+1;j<=num_x;j++) if(j==tnum_x+num_addv) a[tnum_x+num_addv]=1;else a[j]=0;break;case 2:num_addv++;c[tnum_x+num_addv]=0;num_addv++;num_ba++;num_ar++;c[tnum_x+num_addv]=0; base[num_ba]=arti[num_ar]=tnum_x+num_addv;for(j=tnum_x+1;j<=num_x;j++) if(j==tnum_x+num_addv-1) a[tnum_x+num_addv-1]=-1;else if(j==tnum_x+num_addv) a[tnum_x+num_addv]=1;else a[j]=0;break;case 3:num_addv++;num_ba++;c[tnum_x+num_addv]=0;base[num_ba]=tnum_x+num_addv;for(j=tnum_x+1;j<=num_x;j++) if(j==tnum_x+num_addv) a[tnum_x+num_addv]=1;else a[j]=0;break;}//switch}//增加松弛变量、剩余变量、人工变量、确定基变量 //显示标准化后的方程组printf(" 化为标准形式后： ");if(ma_mi==1) printf("max z= ");else printf("max z"= ");printf("%lg x[%d]",c[1],1);for(i=2;i<=num_x;i++) { k=0;for(j=1;j<=num_ar;j++)if(i==arti[j]) k=1;if(k==1) printf(" -M x[%d]",i);else if(c==1) printf(" + x[%d]",i);else if(c==-1) printf(" - x[%d]",i);else if(c>=0) printf(" +%lg x[%d]",c,i);else printf(" %lg x[%d]",c,i);} printf(" st: ");for(i=1;i<=num_st;i++) {k=0;for(j=1;j<=num_x;j++) {if(a[j]!=0) {if(a[j]==1&&k!=0) printf(" + x[%d]",j);else if(a[j]==1&&k==0) printf(" x[%d]",j);else if(a[j]==-1) printf(" - x[%d]",j);else if(a[j]>=0&&k!=0) printf(" +%lg x[%d]",a[j],j);else if(a[j]>=0&&k==0) printf(" %lg x[%d]",a[j],j);else printf(" %lg x[%d]",a[j],j);k=1;}}printf(" == %lg ",b); }printf(" x[1]~x[%d]>=0",num_x);} void iterative() {int i,j,k,k_a,k_f,l; //k_a,k_f值为0或1，记录当前下标在arti[]或base[]里的搜索结果int base_elem;int base_out,base_in;double sigma[MAX],temp;double value_be; //高斯消元里保存主元素值 printf(" 第%d次迭代： ",stop); for(i=1;i<=num_st;i++) {printf("c%d=%lg ",base,c[base]);printf("b%d=%lg ",i,b); switch(step) {case 1:for(j=1;j<=num_x;j++){printf("a[%d][%d]=%lg ",i,j,a[j]);}printf(" ");break;case 2:for(j=1;j<=num_x;j++) {k_a=0;for(l=1;l<=num_ar;l++) if(j==arti[l])k_a=1;if(k_a!=1) printf("a[%d][%d]=%lg ",i,j,a[j]);}printf(" ");break;}}//求检验数sigmafor(i=1;i<=num_x;i++) {sigma=c;for(j=1;j<=num_st;j++) sigma-=c[base[j]]*a[j];for(j=1;j<=num_st;j++) if(i==base[j]) sigma=0;switch(step) {case 1:printf("sigma[%d]=%lg ",i,sigma);break;case 2:k_a=0;for(l=1;l<=num_ar;l++) if(i==arti[l]) k_a=1;if(k_a!=1) printf("sigma[%d]=%lg ",i,sigma);break;}}putchar(" ");//检验检验数sigma是否全小于等于0k=0;for(i=1;i<=num_x;i++) {if(sigma>0) k=1;}if(k==0) {//sigma是全小于等于0时，检查是否为无穷多最优解for(i=1;i<=num_x;i++) { k_f=k_a=0;for(j=1;j<=num_ar;j++)if(i==arti[j]) k_a=1;if(sigma==0&&k_a!=1) {for(j=1;j<=num_st;j++) if(i==base[j]) k_f=1;if(k_f==0) {status=-1; return;}}}status=1; return;}//检查是否为无界解for(i=1;i<=num_x;i++) { k_f=0;if(sigma>0) {for(j=1;j<=num_st;j++) if(a[j]>0) k_f=1;if(k_f!=1) {status=0; return;}}} //确定换入变量for(i=1;i<=num_x;i++) { k=0;for(j=1;j<=num_st;j++) if(i==base[j]) k=1;if(k==0&&sigma>0) temp=sigma-1;}//temp赋初值for(i=1;i<=num_x;i++) {k=0;for(j=1;j<=num_st;j++) if(i==base[j]) k=1;if(k==0)if(sigma>temp&&sigma>0) {base_in=i;temp=sigma;}} //确定换出变量for(i=1;i<=num_st;i++) if(a[base_in]>0) {temp=b/a[base_in]+1;break;}//temp赋初值for(i=1;i<=num_st;i++) {if(b/a[base_in]<=temp&&a[base_in]>0) {for(j=1;j<=num_ar;j++)if(base==arti[j]) { base_out=base;base_elem=i;temp=b/a[base_in];break;}}//人工变量优先换出if(b/a[base_in]<temp&&a[base_in]>0) {base_out=base;base_elem=i;temp=b/a[base_in];}} printf(" 基变量：");for(i=1;i<=num_st;i++) printf("x[%d] ",base);printf("换入变量：x[%d] 换出变量：x[%d]",base_in,base_out);//基变量变换，进行新方程初始化后迭代for(i=1;i<=num_st;i++) {if(base==base_out) base=base_in;}//初始化主元素行系数value_be=a[base_elem][base_in];b[base_elem]/=value_be;for(i=1;i<=num_x;i++) a[base_elem]/=value_be; for(i=1;i<=num_st;i++) {if(i!=base_elem) {b-=b[base_elem]*a[base_in];value_be=a[base_in];for(j=1;j<=num_x;j++) a[j]-=a[base_elem][j]*value_be;}}stop++;if(stop>STP) {status=-2; return;}iterative();} void output() {int i,j;double X[MAX];printf(" 结果如下： ");printf(" X=(");for(i=1;i<=num_x;i++) {for(j=1;j<=num_st;j++)if(i==base[j]) {X=b[j];break;}else X=0;printf("%lg ",X);}printf(")");for(i=1;i<=num_x;i++) max+=c*X;if(ma_mi==1) printf(" Max z= %lf ",max);else printf(" Min z= %lf ",-max);}

第二阶段的检验数 就是第一阶段最终单独形表中去掉人工变量之后的系数，用该系数换上原模型的价值系数。

这是一个标准的线性规划问题，可以使用单纯形法进行求解。下面是解题过程：首先将目标函数和约束条件转化为矩阵形式：目标函数矩阵：C = [0.1 0.15 0.2 0.25 0.3]约束条件矩阵：A = [1 1 1 1 1; 0.15 0.2 0.25 0.3 0.35]将约束条件中的等式 x1+x2+x3+x4+x5=100 转化为不等式，得到：x1+x2+x3+x4+x5≤100x1+x2+x3+x4+x5≥100将不等式转化为标准形式，得到：x1+x2+x3+x4+x5+s1=1000.15x1+0.2x2+0.25x3+0.3x4+0.35x5+s2=0.3其中 s1 和 s2 分别为人工变量，用来将不等式转化为等式。将约束条件和目标函数写成标准形式：目标函数：z = 0.1x1+0.15x2+0.2x3+0.25x4+0.3x5+0s1+0s2约束条件：x1+x2+x3+x4+x5+s1=1000.15x1+0.2x2+0.25x3+0.3x4+0.35x5+s2=0.3x1≥0，x2≥0，x3≥0，x4≥0，x5≥0s1≥0，s2≥0初始化单纯形表格：基变量 x1 x2 x3 x4 x5 s1 s2 右端项s1 1 1 1 1 1 1 0 100s2 0.15 0.2 0.25 0.3 0.35 0 1 0.3z 0.1 0.15 0.2 0.25 0.3 0 0 0选取进入变量和离开变量：由于目标函数中的系数都为正数，所以选取进入变量时应该选择系数最大的变量，即 x5。然后根据约束条件和单纯形表格计算出各个变量的单位贡献，得到：x1: 0.1/1 = 0.1x2: 0.15/1 = 0.15x3: 0.2/1 = 0.2x4: 0.25/1 = 0.25x5: 0.3/1 = 0.3s1: 0/1 = 0s2: 0/0.35 = 0由于 x5 的单位贡献最大，所以将 x5 作为进入变量，然后选取离开变量。根据单纯形表格计算出各个变量的限制系数，得到：x1: 1/0.35 = 2.857x2: 1/0.35 = 2.857x3: 1/0.35 = 2.857x4: 1/0.35 = 2.857s1: 1/0.35 = 2.857s2: 1/0.35 = 2.857由于 s2 的限制系数最小且大于 0，所以将 s2 作为离开变量。进行高斯－约旦消元法计算：基变量 x1 x2 x3 x4 x5 s1 s2 右端项s1 0.35 0.35 0.35 0.35 0

大M法 两阶段法

化标准型不需要增加人工变量。人工变量的目的是为了应用单纯形法求解时得到一个初始可行基为单位矩阵。

补充两个变量x4,x5,将不等式化成等式,然后求解:max:z=3x1+5x2+x34x1+2x2+x3+x4=4x1+x2+x3+x5=4x1~x5≥0

人工变量赋值为零，影响结果。M指的是一个绝对值无限大的值，一般情况下在函数为Min时要用M，在Max情况下要用-M。目的是保证人工变量一定能够被替换，出基，因为最后大M法中所引入的人工变量最后的赋值均为0，否则等式也不会成立。

对，保证b 大于零，X为可行解

例1（投资决策问题）某企业有n个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金A元，投资于第i个项目需花资金ai元，并预计可收益bi元。试选择最佳投资方案。解:设投资决策变量为则投资总额为∑aixi，投资总收益为∑bixi。因为该公司至少要对一个项目投资，并且总的投资金额不能超过总资金 ，故有限制条件另外，由于 xi只取值0或1，所以还有最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为：上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问题，其中目标函数或约束条件中至少有一个非线性函数，这类问题称之为非线性规划问题，简记为（NP）。可概括为一般形式（NP)其中x=[x1 ... xn]称为模型（NP）的决策变量，f称为目标函数，gi和hj 称为约束函数。另外，gi(x)=0称为等式约束，hj(x)<=0称为不等式约束。 对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点：（i）确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。（ii）提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。（iii）给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或“坏”的价值标准，并用某种数量形式来描述它。（iv）寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示。 对实际规划问题作定量分析，必须建立数学模型。建立数学模型首先要选定适当的目标变量和决策变量，并建立起目标变量与决策变量之间的函数关系，称之为目标函数。然后将各种限制条件加以抽象，得出决策变量应满足的一些等式或不等式，称之为约束条件。非线性规划问题的一般数学模型可表述为求未知量x1，x2，…，xn，使满足约束条件：gi(x1，…，xn）≥0　i=1，…，mhj(x1，…，xn)=0　j=1，…，p并使目标函数f(x1，…，xn）达到最小值（或最大值）。其中f，诸gi和诸hj都是定义在n维向量空间Rn的某子集D（定义域）上的实值函数，且至少有一个是非线性函数。上述模型可简记为：min f(x)s.t. gi(x）≥0　i=1，…，mhj(x)=0 j=1，…，p其中x=(x1，…，xn）属于定义域D，符号min表示“求最小值”，符号s.t.表示“受约束于”。定义域D 中满足约束条件的点称为问题的可行解。全体可行解所成的集合称为问题的可行集。对于一个可行解x*，如果存在x*的一个邻域，使目标函数在x*处的值f(x*）优于 （指不大于或不小于）该邻域中任何其他可行解处的函数值，则称x*为问题的局部最优解（简称局部解）。如果f(x*）优于一切可行解处的目标函数值，则称x*为问题的整体最优解（简称整体解）。实用非线性规划问题要求整体解，而现有解法大多只是求出局部解。 指寻求一元函数在某区间上的最优值点的方法。这类方法不仅有实用价值，而且大量多维最优化方法都依赖于一系列的一维最优化。常用的一维最优化方法有黄金分割法、切线法和插值法。①　黄金分割法　又称0.618法。它适用于单峰函数。其基本思想是：在初始寻查区间中设计一列点，通过逐次比较其函数值，逐步缩小寻查区间，以得出近似最优值点。②　切线法　又称牛顿法。它也是针对单峰函数的。其基本思想是：在一个猜测点附近将目标函数的导函数线性化，用此线性函数的零点作为新的猜测点，逐步迭代去逼近最优点。③　插值法　又称多项式逼近法。其基本思想是用多项式（通常用二次或三次多项式）去拟合目标函数。此外，还有斐波那契法、割线法、有理插值法、分批搜索法等。 指寻求 n元实函数f在整个n维向量空间Rn上的最优值点的方法。这类方法的意义在于：虽然实用规划问题大多是有约束的，但许多约束最优化方法可将有约束问题转化为若干无约束问题来求解。无约束最优化方法大多是逐次一维搜索的迭代算法。这类迭代算法可分为两类。一类需要用目标函数的导函数，称为解析法。另一类不涉及导数，只用到函数值，称为直接法。这些迭代算法的基本思想是：在一个近似点处选定一个有利搜索方向，沿这个方向进行一维寻查，得出新的近似点。然后对新点施行同样手续，如此反复迭代，直到满足预定的精度要求为止。根据搜索方向的取法不同，可以有各种算法。属于解析型的算法有：①梯度法：又称最速下降法。这是早期的解析法，收敛速度较慢。②牛顿法：收敛速度快，但不稳定，计算也较困难。③共轭梯度法：收敛较快，效果较好。④变尺度法：这是一类效率较高的方法。其中达维登-弗莱彻-鲍威尔变尺度法，简称 DFP法，是最常用的方法。属于直接型的算法有交替方向法（又称坐标轮换法）、模式搜索法、旋转方向法、鲍威尔共轭方向法和单纯形加速法等。 这是一类特殊的非线性规划。在前述非线性规划数学模型中，若f是凸函数，诸gi都是凹函数，诸hj都是一次函数，则称之为凸规划。所谓f是凸函数，是指f有如下性质：它的定义域是凸集，且对于定义域中任意两点x和y及任一小于1的正数α，下式都成立：f(（1-α）x +αy）α≤（1-α）f(x)+αf(y)将上述不等式中的不等号反向即得凹函数的定义。所谓凸集，是指具有如下性质的集合：连结集合中任意两点的直线段上的点全部属于该集合。对于一般的非线性规划问题，局部解不一定是整体解。但凸规划的局部解必为整体解，而且凸规划的可行集和最优解集都是凸集。 几何规划　一类特殊的非线性规划。它的目标函数和约束函数都是正定多项式（或称正项式）。几何规划本身一般不是凸规划，但经适当变量替换，即可变为凸规划。几何规划的局部最优解必为整体最优解。求解几何规划的方法有两类。一类是通过对偶规划去求解；另一类是直接求解原规划，这类算法大多建立在根据几何不等式将多项式转化为单项式的思想上。

单纯形法计算线性规划的步骤：（1）把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基可行解。（2）若基本可行解不存在，即约束条件有矛盾，则问题无解。（3）若基本可行解存在，从初始基本可行解作为起点，根据最优

f=[1,2,-1];%目标矩阵A=[2,1,-1;1,-2,2;1,1,1];%系数矩阵B=[4;8;5];lb=zeros(1,3);[x,fv]=linprog(f,A,B,[],[],lb)

1、目标函数左右同乘（-1）将min转化为max，所以max = x1-2x2。2、令 ：x" = -x1，引入松弛变量x3，剩余变量x4，s.t-x"-2x2+x3=5-8x"+3x2-x4=-2，x">=0，x2，x3，x4>=0。线性规划标准型的特征：1、求目标函数的最大值（目标函数是求最大值，而不是最小值）。2、约束条件中变量满足线性方程组与非负性两部分（约束条件中所有x是大于0的）。3、方程组中右端常数项皆非负（常数项b是非负的）。扩展资料：注意事项：1、可行域K != NULL 时，K为第一卦限中的凸多边形，且必存在顶点。2、最优解存在则必有基本最优解，可行解存在则必存在基本可行解。3、在求解之前首先观察决策变量定义域，约束条件的格式，若非标准型，则化为标准型。4、最优条件，由 f(X)=f(X0)+Σrjxj (j 属于ID)，若rj>=0，则基本可行解X0为最优解(若标准型设为 max ，则零rj<=0即可)。参考资料来源：百度百科-线性规划的标准型

单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代.按照上面说的，如果基本可行解不存在，问题无解了而且初始解就是“初始可行解”当然不可能是非可行解

线性规划线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好. 单纯形法求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得。 改进单纯形法 原单纯形法不是很经济的算法。1953年美国数学家G.B.丹齐克为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法。其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量。 对偶单纯形法 1954年美国数学家C.莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为min{cx|Ax=b，x≥0}，则其对偶问题为 max{yb|yA≤c}。当原始问题的一个基解满足最优性条件时,其检验数cBB-1A-c≤0。即知y＝cBB-1（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。 数学优化中，由George Dantzig发明的单纯形法是线性规划问题的数值求解的流行技术。有一个算法与此无关，但名称类似，它是Nelder-Mead法或称下山单纯形法，由Nelder和Mead发现（1965年），这是用于优化多维无约束问题的一种数值方法，属于更一般的搜索算法的类别。 这二者都使用了单纯形的概念，它是N维中的N + 1个顶点的凸包，是一个多胞体：直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体，等等。

单纯形法的基本想法是从线性规划可行集的某一个顶点出发，沿着使目标函数值下降的方向寻求下一个顶点，面顶点个数是有限的，所以，只要这个线性规划有最优解，那么通过有限步选代后，必可求出最优解 。为了用选代法求出线性规划的最优解，需要解决以下三个问题  ：(1)最优解判别准则，即迭代终止的判别标准  ；(2)换基运算，即从一个基可行解迭代出另一个基可行解的方法 ；(3)进基列的选择，即选择合适的列以进行换基运算，可以使目标函数值有较大下降

还没学

线性规划模型结构（决策变量，约束不等式、等式，目标函数）；线性规划标准形式；可行解、可行集（可行域、约束集），最优解；基、基变量、非基变量、基向量、非基向量；基本解、基本可行解、可行基、最优基。复习思考题：1、线性规划问题的一般形式有何特征？2、建立一个实际问题的数学模型一般要几步？3、两个变量的线性规划问题的图解法的一般步骤是什么？4、求解线性规划问题时可能出现几种结果，哪种结果反映建模时有错误？5、什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。6、试述线性规划问题的可行解、基本解、基本可行解、最优解、最优基本解的概念及它们之间的相互关系。7、试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。8、在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？9、大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？10、什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？作业习题1、将下列线性规划问题化为标准型（1） （2）2、（1）求出下列不等式组所定义的多面体的所有基本解和基本可行解（极点）：（2）对下述线性规划问题找出所有基本解,指出哪些是基本可行解,并确定最优解.3、用图解法求解下列线性规划问题（1） （2）4、在以下问题中，列出所有的基，指出其中的可行基，基础可行解以及最优解。5、用单纯形法求解以下线性规划问题（1） （2）6、用大M法及两阶段法求解以下线性规划问题（1） （2）7、某工厂生产过程中需要长度为 3.1 米、2.5 米和 1.7 米的同种棒料毛坯分别为 200 根、100 根和 300 根。现有的原料为 9 米长棒材，问如何下料可使废料最少？

单纯形法的基本想法是从线性规划可行集的某一个顶点出发，沿着使目标函数值下降的方向寻求下一个顶点，面顶点个数是有限的，所以，只要这个线性规划有最优解，那么通过有限步选代后，必可求出最优解 。为了用选代法求出线性规划的最优解，需要解决以下三个问题  ：(1)最优解判别准则，即迭代终止的判别标准  ；(2)换基运算，即从一个基可行解迭代出另一个基可行解的方法 ；(3)进基列的选择，即选择合适的列以进行换基运算，可以使目标函数值有较大下降

1、先划LP标准型2、看是否有现成的可行基(之后看检验数，换基迭代)3、没有现成的可行基就用两阶段法先求解辅助问题，判断原问题是否有可行基

先将原题转化为标准模式，令z=-f，添加松弛变量x3,x4max z = 2x1+3x2+0x3+0x4st. x1 + x2 + x3 = 2 4x1 +6x2 + x4 = 9建立初始单纯形表 cj 2 3 0 0 cB xB b x1 x2 x3 x4 θ 0 x3 2 1 1 1 0 0 x4 9 4 6 0 1 σj 2 3 0 0将x2作为入基变量，求得θ为2, 3/2写入上表 cj 2 3 0 0 cB xB b x1 x2 x3 x4 θ 0 x3 2 1 1 1 0 2 0 x4 9 4 6 0 1 3/2 σj 2 3 0 0将x4作为离基变量，重新计算单纯形表 cj 2 3 0 0 cB xB b x1 x2 x3 x4 θ 0 x3 1/2 1/3 0 0 -1/6 3 x4 3/2 2/3 1 0 1/6 σj 0 0 0 -1/2存在非基变量x1的检验数σj=0，因此该题有无穷多最优解其中一个最优解是x1=0,x2=3/2得到max z = 9/2得到min f = -9/2

如果依靠软件，比如MATLAB，MATHEMATICA什么的（甚至EXCEL），都有现成的线性规划的解决方案，照你图里面的条件输入就可以了（不知道具体的软件无法回答）。以下说明不用软件的手动计算单纯形法的标准方法。首先添加松弛变量，因为有3个方程，故添加3个松弛变量S1,S2,S3。约束方程组变为：2X1+X2+X3+S1=2(注意小于等于号变成了等于号，这就是添加松弛变量的作用）。X1+2X2+3X3+S2=52X1+2X2+X3+S3=6X1,X2,X3,S1,S2,S3>=0这是一个6个未知数（n），3个方程的方程组（m）。则选择n-m=3个变量作为“基变量”，让其余变量为0（非基变量）。使得方程组退化为：3个未知数，3个方程的方程组。然后根据对目标函数的影响迭代求解。注意：单纯形法是一个迭代（或者说尝试的过程）。先列出单纯形表(一个矩阵，里面的数据是目标函数和方程组的系数)。当我们选择从原点开始（令X1,X2,X3为0，则得到一个基本解：S1=2,S2=3,S3=6 , 目标函数X0=0；），则单纯形矩阵如下：( { {1, -3, -1, -3, 0, 0, 0, 0}, {0, 2, 1, 1, 1, 0, 0, 2}, {0, 1, 2, 3, 0, 1, 0, 5}, {0, 2, 2, 1, 0, 0, 1, 6} } )呃，不知道怎么在百度里面输入矩阵这种东西。。。反正第一行就是目标函数的方程的系数：X0-3X1-X2-X3+S1+S2+S3=0其他行就是下面的方程组。矩阵的最右边一列是方程的右边项。此时的矩阵是令X1,X2,X3为非基，S1,S2,S3为基的，代表“原点”（起始点）的矩阵，此时的目标：X0=0然后选择目标函数中系数最大的变量为“进基”（就是选他进入基变量组，设为0），选择解和“进基”变量之比为最小非负数的变量为“离基”（就是让他离开基变量组，不设为0）。在这里，选择X1作为进基（因为其在目标方程中的系数最小（负得最多，此题选X3也可），S1为离基（因S1行的解与X1系数之比为1，为最小非负数），然后进行矩阵运算（线性代数里面学的那些东西），使得矩阵的第一行中，代表X1,S2,S3的系数为0，S1不为0。继续矩阵变换，选择进基和离基，直到目标函数的所有系数非负（停止条件），如果是最小化问题则是非正。懒得算了，告诉你个结果吧。x0=27/5x1=1/5x2=0x3=8/5

化成标准形式后，可以用手机下载单纯形法计算器，很方便、好用

先将原题转化为标准模式，令z=-f，添加松弛变量x3,x4maxz=2x1+3x2+0x3+0x4st.x1+x2+x3=24x1+6x2+x4=9建立初始单纯形表cj2300cbxbbx1x2x3x4θ0x3211100x494601σj2300将x2作为入基变量，求得θ为2,3/2写入上表cj2300cbxbbx1x2x3x4θ0x32111020x4946013/2σj2300将x4作为离基变量，重新计算单纯形表cj2300cbxbbx1x2x3x4θ0x31/21/300-1/63x43/22/3101/6σj000-1/2存在非基变量x1的检验数σj=0，因此该题有无穷多最优解其中一个最优解是x1=0,x2=3/2得到maxz=9/2得到minf=-9/2

单纯形法是一种求解线性规划问题的有效算法，可以解决任何线性规划问题。所有的线性规划问题都可以转化成标准型。

线性规划问题的基本解法,利用图解法、单纯形法、数值模拟三种方法对同一道题进行分析解答,并列出详细步骤。将单纯形法的每一步所得结果与线性规划问题的图解法做出比较,通过几何意义,提高学生的解题能力和实际应用能力

混合整数线性规划是整数线性规划模型的一种。整数线性规划模型分类:若i={0,1},j={1,…,n},即全部的决策变量仅取0或1,称之为0-1规划;若j是{1,2…n}的非空真子集,即仅有部分决策变量要求取整数,称为混合整数线性规划;若j={1,2,…n},即全部的决策变量都取整数,称为纯整数线性规划;

这关系到 对最终解的影响程度，大部分线性规划都是整数规划放松后的结果。对有些整数特性严格的问题，放松后优化结果已经不可行了，因此不能放松。如1-0证书规划等。

如果整数规划是求最小问题,那么对应的线性规划的最优值比原问题的最优值要小； 如果整数规划是求最大问题,那么对应的线性规划的最优值比原问题的最优值要大. 但从目标值上,松弛线性规划的更优,但它不是整数规划问题的可行解.

混合整数线性规划模型的含义：线性规划模型(Linear Programming, LP)：LP的定义比较简单，它指的就是目标函数是线性的，所有约束也是线性的，最后，决策变量可以取任何的实数。如果在线性规划问题中有部分决策变量要求必须是整数， 那么这时的规划问题就转变成混合整数线性规划问题了。也就是说优化问题不止有条件约束，还有整数约束。要了解什么是混合整数线性规划模型，第一步是要了解什么是线性规划模型(Linear Programming, LP)。LP的定义比较简单，它指的就是目标函数是线性的，所有约束也是线性的，最后，决策变量可以取任何的实数。举个例子：超市里头有卖3种食品，玉米，牛奶和面包，价格，所含的维他命A和卡路里的信息见上表。现在的问题是买多少份的玉米，牛奶，面包，使得总价格最低，而维他命A的总摄取量不小于500但不大于50000，卡路里的总摄取量不小于2000但不大于2250。现在回到之前的问题，如果在线性规划问题中有部分决策变量，比如上面的X_corn要求必须是整数， 那么这时的规划问题就转变成混合整数线性规划问题了。

内容不同。整数规划的对偶是指每个整数规划问题都能与之对应的对偶问题；线性规划的对偶指每个线性规划问题都有一个与之对应的对偶问题对偶是用字数相等、结构相同、意义对称的一对短语或句子来表达两个相对应或相近或相同的意思的修辞方式。

线性规划是所有约束条件和目标函数都是线性的，即未知数的次数均为一次。整数规划是线性规划中未知数只能取整数的那种特例。非线性规划是约束条件或目标函数中含有非线性的规划问题。

规划中的变量（全部或部分）限制为整数，称为整数规划。若在线性模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法往往只适用于整数线性规划。一类要求问题的解中的全部或一部分变量为整数的数学规划。从约束条件的构成又可细分为线性，二次和非线性的整数规划。

1, 线性规划包括线性整数规划；2,一般的线性规划是由最优解的，一般的整数规划是NP的。

整数规划 integer programming 一类要求问题中的全部或一部分变量为整数的数学规划。 一般认为非线性的整数规划可分成线性部分和整数部分，因此常常把整数规划作为线性规划的特殊部分。在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求解答必须是整数。例如，所求解是机器的台数，工作的人数或装货的车数等。为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是01规划，它的变数仅限于0或1。 整数规划与组合最优化从广泛的意义上说，两者的领域是一致的，都是在有限个可供选择的方案中，寻找满足一定标准的最好方案。有许多典型的问题反映整数规划的广泛背景。例如，背袋（或装载）问题、固定费用问题、和睦探险队问题（组合学的对集问题）、有效探险队问题（组合学的覆盖问题）、送货问题等。因此整数规划的应用范围也是极其广泛的。它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。 整数规划是从1958年由R.E.戈莫里提出割平面法之后形成独立分支的 ，30多年来发展出很多方法解决各种问题。解整数规划最典型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题（衍生问题称为松弛问题的源问题）。通过松弛问题的解来确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。随即 ，再选择一个尚未被舍弃的或替代的原问题的衍生问题，重复以上步骤直至不再剩有未解决的衍生问题为止。目前比较成功又流行的方法是分枝定界法和割平面法，它们都是在上述框架下形成的。 0—1规划在整数规划中占有重要地位，一方面因为许多实际问题，例如指派问题、选地问题、送货问题都可归结为此类规划，另一方面任何有界变量的整数规划都与0—1规划等价，用0—1规划方法还可以把多种非线性规划问题表示成整数规划问题，所以不少人致力于这个方向的研究。求解0—1规划的常用方法是分枝定界法，对各种特殊问题还有一些特殊方法，例如求解指派问题用匈牙利方法就比较方便。

如果整数规划是求最小问题,那么对应的线性规划的最优值比原问题的最优值要小；如果整数规划是求最大问题,那么对应的线性规划的最优值比原问题的最优值要大.但从目标值上,松弛线性规划的更优,但它不是整数规划问题的可行解.

整数线性规划模型分类:若I={0,1},J={1,…,n},即全部的决策变量仅取0或1,称之为0-1规划;若J是{1,2…n}的非空真子集,即仅有部分决策变量要求取整数,称为混合整数线性规划;若J={1,2,…n},即全部的决策变量都取整数,称为纯整数线性规划;http://202.204.115.67:8080/files/files_upload/content/material_227/chapter_HVj/33605.ppt

关系如下：第一、对线性整数规划决策变量放松取整约束,就能得到对应的一般线性规划问题;反之,对一般线性规划增加决策变量取整要求,就能得到线性整数规划问题。因此,线性整数规划的约束比一般第二、线性整数规划问题的可行解集是其对应的一般线性规划问题可行解集的子集。第三、线性整数规划的目标值,不可能优于它对应

整数规划 integer programming 一类要求问题中的全部或一部分变量为整数的数学规划。 一般认为非线性的整数规划可分成线性部分和整数部分，因此常常把整数规划作为线性规划的特殊部分。在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求解答必须是整数。例如，所求解是机器的台数，工作的人数或装货的车数等。为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是01规划，它的变数仅限于0或1。 整数规划与组合最优化从广泛的意义上说，两者的领域是一致的，都是在有限个可供选择的方案中，寻找满足一定标准的最好方案。有许多典型的问题反映整数规划的广泛背景。例如，背袋（或装载）问题、固定费用问题、和睦探险队问题（组合学的对集问题）、有效探险队问题（组合学的覆盖问题）、送货问题等。因此整数规划的应用范围也是极其广泛的。它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。 整数规划是从1958年由R.E.戈莫里提出割平面法之后形成独立分支的 ，30多年来发展出很多方法解决各种问题。解整数规划最典型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题（衍生问题称为松弛问题的源问题）。通过松弛问题的解来确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。随即 ，再选择一个尚未被舍弃的或替代的原问题的衍生问题，重复以上步骤直至不再剩有未解决的衍生问题为止。目前比较成功又流行的方法是分枝定界法和割平面法，它们都是在上述框架下形成的。 0—1规划在整数规划中占有重要地位，一方面因为许多实际问题，例如指派问题、选地问题、送货问题都可归结为此类规划，另一方面任何有界变量的整数规划都与0—1规划等价，用0—1规划方法还可以把多种非线性规划问题表示成整数规划问题，所以不少人致力于这个方向的研究。求解0—1规划的常用方法是分枝定界法，对各种特殊问题还有一些特殊方法，例如求解指派问题用匈牙利方法就比较方便。

线性规划是所有约束条件和目标函数都是线性的，即未知数的次数均为一次。整数规划是线性规划中未知数只能取整数的那种特例。非线性规划是约束条件或目标函数中含有非线性的规划问题。

如果整数规划是求最小问题,那么对应的线性规划的最优值比原问题的最优值要小；如果整数规划是求最大问题,那么对应的线性规划的最优值比原问题的最优值要大.但从目标值上,松弛线性规划的更优,但它不是整数规划问题的可行解.

规划中的变量（全部或部分）限制为整数，称为整数规划。若在线性模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法往往只适用于整数线性规划。