运筹学 复习题(09.1)

1、线性规划和优化的初步研究，重复课程，1。填空：1除图解法外，解决线性规划问题的常用方法是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。2.用单纯形法求解线性规划问题时，不等式必须被约束成等式。如果不等式符号右侧的常数不是负的，那么当不等式符号小于或等于时，它应该是负的；当等号大于或等于时，你应该。3.用图解法求解利润最大的线性规划问题时，需要画一条_ _ _ _ _ _线，其最优解点必须位于这条线与可行解区域的交点处。原问题的第一个约束方程是“=”型，那么对偶问题的相应变量是_ _。5。整数规划_ _ _ _ _ _ _ _ _ _(是或否)线性规划。6.为了解决最小生成树问

2、题，常用的方法有：避圈法和_ _。在树形图中，任意两个顶点之间只有一条链。线性规划的图解法适用于决策变量为线性规划的模型。通常有两种方法可以找到运输问题的初始基本可行解。解决不平衡运输问题的基本思路是。11.没有圈的连通图叫做树。如果一个图的顶点数是n，那么它的边数是。2、下列线性规划转化为标准形式，线性规划模型转化为标准形式，变量，约束，右端项，形式，不变，不变，两端约束乘以 1 ，值是无约束的，目标函数数是极大的或极小的，不变，当添加松弛变量或剩余变量时，当添加人工变量时，3、使用图片，各产品的资源消耗、 单位产品销售后获得的利润值和这三种资源的储备量如下表所示：(1)建立生产计划的线性规

3、划模型，使工厂获得最大利润； 2)用单纯形法寻找该问题的最优解。4.建模与求解：1)建立线性规划数学模型：将产品A、B、C的生产量设为x1、x2、x3，然后设为x1、x2、x30，将产品售后总利润设为Z，则最大Z=10 x16 x23，2)用单纯形法寻找最优解：加入松弛变量x4、x5。最大z=10 x1 6x2 4x3 0 x4 0 x5 0 x6，缩写为，X*=(，0，0，0，100)，最大z=10 6=，解决整数规划问题：l0 :x1=2.25，x2=3.75，z=41.25，l03333。5.采用分支定界法，X1=1，X2=40/9，Z=365/9，X1=1，X2=4，Z=37，X1=0

4、，X2=5，Z=40，L03360，L13360一家农产品配送公司有三个棉花收购站A1、A2和A3，分别向四家纺织厂供应600吨、1000吨和700吨棉花。B1、B2、B3和B4四家纺织厂的需求分别为300吨、500吨、900吨和600吨。据了解，从各采购站到各纺织厂的单位运费如下(单位：1000元/吨)。我们应该如何调度运输以降低总运费？一家公司有三个分支机构A1、A2和A3，其产品销往B1、B2、B3和B4。三个分公司的生产能力和四个地区的单位运输成本如下表所示。尝试用表格运算法寻找运输方案及其最优解，使运输成本最小化。7.用匈牙利算法解决问题。8.最小树。1.请使用避圈法(或破圈法)找到

5、最小零件树。请使用Dijkstra算法找到从发送点到接收点的最短路径。1最小部分树是，并且从起点S到终点T的最短路径是，为了解决线性规划问题，1。列出线性规划问题的标准形式，2。请用单纯形法中的大M法寻找其最优解和目标函数值。1。线性规划问题的标准形式，2。使用单纯形法的大m法，(1)在上述公式的标准形式中加入人工变量，我们得到：(2)列单纯形表1:(3)列单纯形表2:(4)列单纯形表3:(5)列单纯形生产产品A所需的原料1和2分别为2吨和1吨，生产产品B所需的原料1和2分别为1吨和2吨。产品a和b的单位销售收入分别为3元和2元。公司分别拥有6吨和4吨两种原料1和2。如果生产的所有产品都可以销

6、售，我们应该如何制定生产计划来最大化总销售收入？2.一个企业的一个部门有三个人A1、A2和A3，这个部门有三个工作B1、B2和B3要做。每个人只被要求做一项工作，并且每项工作只能由一个人完成。据了解，B1、B2和B3的单位消费岗位按A1人群分布为：3、5和2；从事B1、B2和B3工作的A2人的单位消费分布是2、10和12。从事B1、B2和B3的A3人的单位消费分布是1、9和8。试着建立一个数学模型，说明如何分配工作以减少总消耗。3.一家钢管厂有一批11米长的钢管。现在一个客户计划订购60根3米长的钢管和90根4米长的钢管，试图建立一个数学模型，以尽量减少总浪费。家具厂生产衣柜、书柜、圆桌和凳子。每个衣柜的利润是15元，每个书架的利润是20元，每个圆桌的利润是10元，每个凳子的利润是8元。制作一个衣柜需要0.15立方米的杂木和0.3立方米的松木，制作一个书架需要0.2立方米的杂木和0.4立方米的松木，制作一个圆桌需要0.2立方米的杂木，制作一个凳子需要0.15立方米的松木。杂木和松木的月供应量分别为