当前位置：文档之家 › 线性规划

线性规划

  • 格式：doc
  • 大小：268.00 KB
  • 文档页数：11

数学软件作业0-1整数规划分班模型学校：济宁学院班级：数学与应用数学二班姓名：闫玺萍、张敏、尹城日期：2013-12-220-1整数规划分班模型摘要第一问中对数据进行正太性检验，利用SPSS中Q-Q、P-P图观察，并利用K-S法（峰度-偏度检验法）进行计算检验；第二问中对52名同学进行分班，只考虑前年级前30名即可，考虑到每名同学只能在一个班级中，故利用0-1整数规划模型解决问题。

关键词正态分布，峰度-偏度检验，0-1整数规划问题重述下表是某学校学生的总成绩，年级名次以及数学等其它六门课的成绩和名次。

请考虑下面的两个问题：1、所有学生的总分是否符合正态分布？2、将这52名学生分成5个班。

分班要求为：每个班年级前30名的学生个数最多相差一个；每个班的年级前30学生的总成绩平均分相差尽量少。

本题的目标函数可以根据你的分班想法自行给出，也可以没有目标函数给出满足上述两个条件的可行解即可。

分班后得到的每个班的学生名单以excel的形式给出。

注：作业一律用word2003版，A4纸打印。

本题可以用lingo，spss来考虑符号说明g偏度；1g峰度；2σg偏度标准误；1σg峰度标准误；2x ij决策变量；S i第i名学生成绩；前言对数据进行分析、优化、筛选一般应用到SPSS、Lingo、Matlab等软件，本文将利用软件对数据进行处理，以达到题目要求。

1 第一问1.1图示法以样本的分位数作为横坐标，以按照正态分布计算的相应分位点作为纵坐标，把样本表现为指教坐标系的散点。

如果资料服从正态分布，则样本点应该呈一条围绕第一象限对角线的直线。

通过观察P-P图、Q-Q图，学生成绩数据围绕第一象限对角线，并且亲和度较高，初步判断学生成绩符合正态分布。

直观看出学生成绩符合正太分布。

1.2计算法K-S 检验法：计算公式：偏度系数（Skewness ）计算公式：gu g 101-= 峰度系数（Kurtosis ）计算公式： gu g 102-= g 1表示偏度，g 2表示峰度，通过计算g 1和g 2及其标准误σg 1及σg 2然后作U检验。

两种检验同时得出96.105.0=<U U U ，即p>0.05的结论时，则可认为所给数据符合服从正态分布。

通过数据描述u 值分别为-0.846和 1.373均小于1.96U 0.05=，因此学生总成绩符合正态分布。

2 问题二2.1模型概述将问题分成两部分完成：前30名分班；其余学生分班。

问题关键是前30名学生的分配问题，根据题目要求我们利用0-1整数规划进行计算：整数规划指的是决策变量为非负整数值的一类线性规划，在实际问题的应用中，整数规划模型对应着大量的生产计划或活动安排等决策问题, 在整数规划问题中，0—1型整数规划则是其中较为特殊的一类情况，它要求决策变量的取值仅为0或1，本问题中每名同学只能进入一个班级,例如:第i 个同学进入第j 个班级为1,反之为0,利用穷举法对决策变量（即前30名学生)30....1(=i S i ）的每一个0或1值，均比较其目标函数的值的大小，从中求得最优解，但本题目中数据量较大，通过增加过滤条件来得到一个较合理和范围内的优化解。

2.2模型分析与变量假设2.2.1 目标函数对于每一名同学而言，他要么属于班级j ，要么不属于班级j ，故决策变量可定义为：⎩⎨⎧=j i j i x ij 不在班级若学生在班级若学生01这种定义，我们能根据最优解中x ij 的值来很快确定学生i 与班级j 之间的隶属关系。

又因我们需要使5个班级中前30名同学的平均分相差尽量小，换言之，是各个班级的总分相差最小，我们取每个班级总分与前30名同学平均总分（3003.6）作差，并取平方来作为目标函数，即：∑-=∑==512)6.3003*(301min j S x i i ij z 2.2.2模型约束条件（1）每名同学只能进入一个班级：)5...1;30...1(151===∑=j i j ij x （2）每个班级前30名学生人数为6： )5..1;30...1(6301===∑=j i i ij x2.2.3模型优化为减少枚举法中数据处理量，我们添加过滤条件从而优化算法：5.0301512)6.3003*(<∑=∑-=j S x i i ij 2.3编程求解编写Lingo 程序，进行最优化求解（程序及运行结果见附录1）。

分班结果见附录2.具体详细结果见附录3.参考文献(1) 汪晓银，邹庭荣，周宝平.数学软件与数学实验.北京：科学出版社，2010(2) 姜启源，谢金星，叶俊.数学模型.北京：高等教育出版社，2010(3) （美）吉奥丹诺等著；叶其孝等译.数学建模（第四版）.北京：机械工业出版社，2009.8附录1含目标函数：sets:stu/1..30/:S;cla/1..5/:;link(cla,stu):x;endsetsdata:S=647603.5590580567555.5554.5539.5535.5532.5517.5512.5510.5509493488.5485.5477.5474.5468.5463461453.5443.5439.5435430.5418417.5414.5;enddatamin=@sum(cla(j):(@sum(stu(i):S(i)*x(j,i))-3003.6)^2);@for(link:@bin(x));@for(cla(j):@sum(stu(i):x(j,i))=6);@for(stu(i):@sum(cla(j):x(j,i))=1);@for(cla(j):@abs(@sum(stu(i):x(j,i)*S(i))-3003.6)<0.5); End不含目标函数：sets:stu/1..30/:S;cla/1..5/:;link(cla,stu):x;endsetsdata:S=647603.5590580567555.5554.5539.5535.5532.5517.5512.5510.5509493488.5485.5477.5474.5468.5463461453.5443.5439.5435430.5418417.5414.5;enddata@for(link:@bin(x));@for(cla(j):@sum(stu(i):x(j,i))=6);@for(stu(i):@sum(cla(j):x(j,i))=1);@for(cla(j):@abs(@sum(stu(i):x(j,i)*S(i))-3003.6)<0.5); End运行结果：Feasible solution found.Infeasibilities: 0.000000Extended solver steps: 5013Total solver iterations: 47694Variable Value S( 1) 647.0000 S( 2) 603.5000 S( 3) 590.0000 S( 4) 580.0000 S( 5) 567.0000 S( 6) 555.5000 S( 7) 554.5000 S( 8) 539.5000 S( 9) 535.5000 S( 10) 532.5000 S( 11) 517.5000 S( 12) 512.5000 S( 13) 510.5000S( 16) 488.5000 S( 17) 485.5000 S( 18) 477.5000 S( 19) 474.5000 S( 20) 468.5000 S( 21) 463.0000 S( 22) 461.0000 S( 23) 453.5000 S( 24) 443.5000 S( 25) 439.5000 S( 26) 435.0000 S( 27) 430.5000 S( 28) 418.0000 S( 29) 417.5000 S( 30) 414.5000 X( 1, 1) 0.000000 X( 1, 2) 0.000000 X( 1, 3) 0.000000 X( 1, 4) 0.000000 X( 1, 5) 0.000000 X( 1, 6) 0.000000 X( 1, 7) 0.000000 X( 1, 8) 1.000000 X( 1, 9) 0.000000 X( 1, 10) 0.000000 X( 1, 11) 1.000000 X( 1, 12) 1.000000 X( 1, 13) 1.000000 X( 1, 14) 0.000000 X( 1, 15) 1.000000 X( 1, 16) 0.000000 X( 1, 17) 0.000000 X( 1, 18) 0.000000 X( 1, 19) 0.000000 X( 1, 20) 0.000000 X( 1, 21) 0.000000 X( 1, 22) 0.000000 X( 1, 23) 0.000000 X( 1, 24) 0.000000 X( 1, 25) 0.000000 X( 1, 26) 0.000000 X( 1, 27) 1.000000 X( 1, 28) 0.000000 X( 1, 29) 0.000000 X( 1, 30) 0.000000 X( 2, 1) 0.000000 X( 2, 2) 0.000000 X( 2, 3) 0.000000 X( 2, 4) 0.000000 X( 2, 5) 0.000000 X( 2, 6) 1.000000 X( 2, 7) 1.000000 X( 2, 8) 0.000000 X( 2, 9) 1.000000 X( 2, 10) 0.000000 X( 2, 11) 0.000000 X( 2, 12) 0.000000 X( 2, 13) 0.000000 X( 2, 14) 0.000000X( 2, 17) 0.000000 X( 2, 18) 0.000000 X( 2, 19) 0.000000 X( 2, 20) 0.000000 X( 2, 21) 0.000000 X( 2, 22) 1.000000 X( 2, 23) 1.000000 X( 2, 24) 1.000000 X( 2, 25) 0.000000 X( 2, 26) 0.000000 X( 2, 27) 0.000000 X( 2, 28) 0.000000 X( 2, 29) 0.000000 X( 2, 30) 0.000000 X( 3, 1) 1.000000 X( 3, 2) 0.000000 X( 3, 3) 1.000000 X( 3, 4) 0.000000 X( 3, 5) 0.000000 X( 3, 6) 0.000000 X( 3, 7) 0.000000 X( 3, 8) 0.000000 X( 3, 9) 0.000000 X( 3, 10) 0.000000 X( 3, 11) 0.000000 X( 3, 12) 0.000000 X( 3, 13) 0.000000 X( 3, 14) 0.000000 X( 3, 15) 0.000000 X( 3, 16) 0.000000 X( 3, 17) 0.000000 X( 3, 18) 0.000000 X( 3, 19) 1.000000 X( 3, 20) 0.000000 X( 3, 21) 0.000000 X( 3, 22) 0.000000 X( 3, 23) 0.000000 X( 3, 24) 0.000000 X( 3, 25) 1.000000 X( 3, 26) 1.000000 X( 3, 27) 0.000000 X( 3, 28) 1.000000 X( 3, 29) 0.000000 X( 3, 30) 0.000000 X( 4, 1) 0.000000 X( 4, 2) 0.000000 X( 4, 3) 0.000000 X( 4, 4) 1.000000 X( 4, 5) 0.000000 X( 4, 6) 0.000000 X( 4, 7) 0.000000 X( 4, 8) 0.000000 X( 4, 9) 0.000000 X( 4, 10) 0.000000 X( 4, 11) 0.000000 X( 4, 12) 0.000000 X( 4, 13) 0.000000 X( 4, 14) 1.000000 X( 4, 15) 0.000000X( 4, 16) 1.000000X( 4, 17) 1.000000X( 4, 18) 1.000000X( 4, 19) 0.000000X( 4, 20) 0.000000X( 4, 21) 1.000000X( 4, 22) 0.000000X( 4, 23) 0.000000X( 4, 24) 0.000000X( 4, 25) 0.000000X( 4, 26) 0.000000X( 4, 27) 0.000000X( 4, 28) 0.000000X( 4, 29) 0.000000X( 4, 30) 0.000000X( 5, 1) 0.000000X( 5, 2) 1.000000X( 5, 3) 0.000000X( 5, 4) 0.000000X( 5, 5) 1.000000X( 5, 6) 0.000000X( 5, 7) 0.000000X( 5, 8) 0.000000X( 5, 9) 0.000000X( 5, 10) 1.000000X( 5, 11) 0.000000X( 5, 12) 0.000000X( 5, 13) 0.000000X( 5, 14) 0.000000X( 5, 15) 0.000000X( 5, 16) 0.000000X( 5, 17) 0.000000X( 5, 18) 0.000000X( 5, 19) 0.000000X( 5, 20) 1.000000X( 5, 21) 0.000000X( 5, 22) 0.000000X( 5, 23) 0.000000X( 5, 24) 0.000000X( 5, 25) 0.000000X( 5, 26) 0.000000X( 5, 27) 0.000000X( 5, 28) 0.000000X( 5, 29) 1.000000X( 5, 30) 1.000000附录2一班:于翔、苏杭、王文、曾建、靳道、张瑞、史寒、胡亚、李学、陈智、阮敬潘敏二班：狄晓、高松、寻亚、乔宁、张茂、王丽、张悦、胡楷、狄乾、陆洋三班：王元、韦胜、寻亚、杨梅、张东、岳洋、姜圆、张硕、张良、田展四班：王有、谢朝、陈瑞、郭亚、谢秋、张代、韩月、黄然、李彤、赵腾五班：蔡飞、李志、杨丽、袁森、苏杭、付通、胡萍、贾倩、刘成、孔俊（注：红色为前30名学生姓名）- 11 -。

合集下载

第二章线性规划

第二章线性规划




线性规划要研究的两类问题中都包含有约束条件和目 标函数。用数学的方式描述，规划的目的就是在给定 的限制条件（或称约束条件）下，求目标函数的极值 问题（包括极小值和极大值）。
2
线性规划的数学模型
3
解： 设产品 的产量为：1 , 产品 的产量为：x2 x
4
5
6
7

配料问题：由若干种不同价格、不同成分含量的原料，用 不同的配比混合调配出一些不同规格的产品，在原料的供 应量限制和保证产品成分含量的前提下，如何进行配料来 获取最大利润或使总成本最低。
15
2.2.3 线性规划求解的可能结局
1、有唯一的最优解
2、有无穷多个最优解 （将目标函数改为 z=4x1+3x2 ）
x2
max z 4 x1 3 x2 x1 2 x2 5 2 x x 4 1 2 s.t. 4 x1 3 x2 9 x1 , x2 0
3x1 2 x2 4 x3 3
3x1 2 x2 4 x3 xs 3
剩余变量
变量xs实际上是原式左端减去右端的差，即 ：
xs 3x1 2 x2 4 x3 3
当约束条件是“ ”型的不等式时，只要将该约 束条件左端减去一个非负的剩余变量即可化为等式。 无论是松弛变量还是剩余变量在决策中都不产生实际价 值，因此它们在目标函数中的系数都应该为零。有时也将松 29 弛变量和剩余变量统称为松弛变量。
2x1+x2=4 D C
x1+2x2=5 B 4x1+3x2=9 O A x1
16
3、无界解
指线性规划问题有可行解，但是 在可行域，目标函数值是无界的， 因而达不到有限最优值。因此线 性规划问题不存在最优解。
线性规划PPT课件

线性规划PPT课件


线性规划的基本定理
线性规划的解存在性
对于任何线性规划问题，都存在至少一个最优解。
最优解的唯一性
在某些情况下，线性规划问题的最优解是唯一的，这取决于目标函 数和约束条件的形状和位置。
解的稳定性
线性规划问题的最优解是稳定的，即使目标函数或约束条件略有变 化，最优解也不会发生大的变化。
03
线性规划的求解方法
优缺点：内点法具有全局收敛性和对初始点不敏 感的优点，但计算量较大，需要较高的计算资源 。
椭球法
01
总结词：几何方法
02
03
04
详细描述：椭球法是一种基 于几何方法的线性规划算法。 它将可行解的边界表示为椭 球，通过迭代移动椭球中心
来逼近最优解。
算法步骤：椭球法的基本步 骤包括初始化、构建椭球和 迭代更新。在每次迭代中， 根据当前椭球的位置和方向 来更新中心和半径，直到满
运输问题
总结词
运输问题是线性规划在物流和供应链管理中的重要应用，旨在优化运输成本、 运输时间和运输量等目标。
详细描述
运输问题通常需要考虑多个出发地、目的地、运输方式和运输成本等因素。通 过线性规划方法，可以找到最优的运输方案，使得总运输成本最低、运输时间 最短，同时满足运输量和运输路线的限制。
投资组合优化问题
03
单纯形法
单纯形法是线性规划的标 准算法，通过迭代和优化， 找到满足约束条件的最大 或最小目标函数值。
初始解
在应用单纯形法之前，需 要先找到一个初始解，这 可以通过手动计算或使用 软件工具来实现。
迭代过程
单纯形法通过不断迭代和 优化，逐步逼近最优解， 每次迭代都需要重新计算 目标函数值和最优解。
线性规划的几何意义
第一章 线性规划

第一章 线性规划

(1-8)
例 1.5 （汽油混合问题） 一种汽油的特性可用两个指标描述：其点火性用“辛烷数” 描述，其挥发性用“蒸汽压力”描述，某炼油厂有四种标准汽油，设其标号分别为 1，2， 3，4，其特性及库存量见表 1.5，将上述标准汽油适量混合，可得到两种飞机汽油，其标 号分别为 1，2，这两种飞机汽油的性能指标及产量需求见表 1.6，问应如何根据库存情况 适量混合各种标准汽油，使既满足飞机汽油的性能指标，而产量又为最高。
注：前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了 12 个变量，10 个约束条件。
表 1.2 资源 住宅体系 砖混住宅 壁板住宅 大模住宅 资源限量 造价 (元/m2) 105 135 120 110000 (千元 钢材 (公斤/m2) 12 30 25 20000 (吨) 例 1.2 的数据表 水泥 (公斤/m2) 110 190 180 150000 (吨) 砖 (块/m2) 210 —— —— 147000 (千块) 人工 (工日/m2) 4.5 3.0 3.5 4000 (千工日)
3．线性规划模型的一般形式 以 MAX 型、≤约束为例 决策变量： x1 ,
(1-4)
, xn
目标函数： Maxz = c1 x1 +
+ cn x n
⎧a11 x1 + + a1n x n ≤ b1 ⎪ ⎪ 约束条件： s.t.⎨ ⎪a m1 x1 + + a mn x n ≤ bm ⎪ ⎩ x1 , , x n ≥ 0
2
Maxz = x1 + x 2 + x3 ⎧0.105 x1 + 0.135 x 2 + 0.120 x3 ≤ 110000 ⎪0.012 x1 + 0.030 x 2 + 0.025 x3 ≤ 20000 数学模型为: ⎪0.110 x1 + 0.190 x 2 + 0.180 x 3 ≤ 150000 (1-3) s.t ⎨ 0.210 x ≤ 147000 ⎪0.00451 x + 0.003x 2 + 0.0035 x 3 ≤ 4000 ⎪x , x , x 1 ≥ 0 ⎩ 1 2 3
线性规划

线性规划

饲料 蛋白质（g） A1 0.3 A2 2 A3 1 A4 0.6 A5 1.8
矿物质（g）
维生素(mg）
0.1
0.05
0.05
0.1
0.02
0.02
0.2
0.2
0.05
0.08
希望建立数学模型，既能满足动物需要，又使总成 本最低的饲料配方
模型
饲料 符号 A1 x1 A2 x2 A3 x3 A4 x4 A5 x5
约 l2 : 12x1 8x2 480 束 12x1 8x2 480 l4 条 3x1 100 l3 : 3x1 100 件 c l4 : x1 0, l5 : x2 0 x1 , x2 0 目标 函数
l1 : x1 x2 50
x2 A
l1 B l2 C Z=3600 l3
线性规划问题的数学模型的一般形式
（ 1）列出约束条件及目标函数 （2）画出约束条件所表示的可行域 （3）在可行域内求目标函数的最优解及最优值
线性规划问题的标准形式
{
max y=cTx s.t. Ax=b x≥0
求解方法： （1）单纯形法 （2）软件求解:Lindo， Lingo, matlab，sas
RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 X2 ROW 72.000000 24.000000 8.000000
Max z 72x1 64x2
z=c (常数) ~等值线
0
l5
Z=0
x1 D Z=2400