怎么理解线性规划问题的基可行解对应可行域的顶点？
运筹学课本里只有这样一个结论，我不明白为什么。求大神解答，请解释得通俗易懂一些
我们讨论标准化了的线性规划问题，也就是有m个“《=”方程约束（矩阵形式就是非退化的A，functional constraints，扩展形式中的松弛变量）和n个非负约束（non-negativity constraints）。可以直接看加粗部分，不过不建议。首先，基本可行解（basic feasible solution）是扩展后的角点可行解（Corner Point Feasible solution），也就是说n个原始变量（decision variables）取值后加入对应的m个松弛变量（不等式转化出的变量，slack variables）取值后形成的。当我们谈起可行域(n维)的顶点，指的就是角点可行解（Corner Point Feasible Solution）对应的点。所以我觉得从几何对应上，最好说，线性规划问题（Linear Programming）的角点可行解对应可行域的顶点，因为可行域的顶点的坐标就是角点可行解。而从对可行域顶点的理解上，你的说法更好。接下来看回答你就会明白。正式来回答你这个问题。角点是m个方程约束和n个非负约束定义的超平面（就是方程取“=”后画的一个n-1维平面，所以每个约束对应一个超平面，hyper plane）的交点，它的坐标。每一个角点都有n个（因为是n维空间嘛）定义方程（它是哪几个方程形成的超平面的交点，哪几个方程就是它的定义方程，defining equations）。这n个定义方程对应的变量（非负约束自然对应原始变量，方程约束对应的就是松弛变量）就是n个取值为0的非基变量，另外m个和这个角点无关的超平面对应的变量就是基变量（basic variables）。基变量和非基变量的取值一结合就是基本解（basic solutions）了，所以线性规划问题的基本解对应顶点。如果这个基本解满足所有的约束，那它就是可行的。对应几何上，角点处于可行域内，那就是角点可行解了。简单来说，可行域顶点是可行的角点，角点的定义方程对应取值为0的非基变量，剩下的超平面对应基变量。有时角点的定义方程多于n个，那么自选n个作为定义方程，没选到的就是退化（取值为0，称为退化）的基变量。所以角点对应基本解。可行的基本解就对应可行的角点，也就是可行域顶点。为了说明白，回答得有点长，希望对你有帮助。因为自己也是上学期刚学，理解尚浅，可能有谬误之处，或者有没说清楚的地方，评论给我就好。
case 1case 1不同基求出来的不同的基可行解有可能对应同一个值.(一个基代表一套坐标系，同一值的基可行解是否等同，就看每个人的定义了.我也不知道官方定义是怎样)Case 2老师说还有一种情况是可能的，不过没证明。没有退化的的情形是一对一，有退化时有可能是一个顶点对多个基可行解。修改写的比较简单。欢迎提问。修改写的比较简单。欢迎提问。这个我还没学到。等学到了，有时间了，我再回来尝试解法。不知道这两点能不能给各位前辈提示，解决这位知友和我的困惑
已有帐号？
无法登录？
社交帐号登录当前位置： >>
线性整数规划 excel求解
1100SpreadsheetTJCJ, 2010 3 ?2100 or
integer linear programming IPear programming ear programmingall-integer linmixed-integer lin-3100: 0-1 ear programming 1 0-1 1 00-1 integer lin0 1 0 1 0-41005.1.1 A B 5.1.1 2000 A 140 55.1.1设备名称 原材料（千克/台） 劳动力 （千小时/台） 利润（千元/台） 仪器 A 282 4 10 仪器 B 400 40 15 可提供量 5 100A YBXo.b. max 10X + 15Y s.t. 282X + 400Y 4X + 40Y X X, Y 20006 100140 5 05.1.1(a) X = 2.48 Y = 3.25Y73.575 4 3 2 1 0 可行域7 100Y最优 LP 解: ( X = 2.48, Y = 3.25 )10 X + 15Y = 73.57123456X5.1.1(a)(LP)5.1.1(b)Y5 4 3 可行域 2 1 0 Y 最优 IP 解: ( X = 4, Y = 2 )10 X + 15Y = 708 100123456X5.1.1(b)(IP)X=4 Y =2702SpreadsheetSpreadsheetExcel int 5.2.19 1005.2.15.1.1Spreadsheet5.2.15.2.1Spreadsheet101005.1.1 5.2.1.15.2.1.1Spreadsheet111005.2.25.2.2121005.2.130-10-1 0 1 Excel 0 1 5.3.1 bin131005.3.10-13.1.5.3.15.3.1 5.3.1141005.3.1项目 第一年投资（净现值） 第二年投资（净现值） 第三年投资（净现值） 第四年投资（净现值） 利润（净现值） 引进设备 25 0 20 0 40 研制新产品 20 15 20 10 80 培训人才 10 10 10 10 40 增加广告数量 8 8 8 8 20 资金预算 60 50 50 350-1 X1, X2, X3, X4 1 0 0-1151000-1 o.b. max 40X1 + 80X2 + 40X3 + 20X4 s.t. 25X1 + 20X2 + 10X3 + 8X4 15X2 + 10X3 + 8X4 20X1 + 20X2 + 10X3 + 8X4 10X2 + 10X3 + 8X4 X1, X2, X3, X4 0 1 60 50 50 35 0-116 100Spreadsheet5.3.25.3.2Spreadsheet17100Spreadsheet 5.3.2.15.3.2.1181005.3.25.3.25.3.2 5.3.2 1, X3 = 1, X3 = 0 X1 = 1, X2 = 160191001603.2.5.3.2 700 5.3.3 5.3.3 5.3.4城镇 1 700 吨1200201001000 吨焚烧填海500 吨掩埋1300 吨城镇 21200 吨5.3.35.3.3处理场所 1. 焚烧 2. 填海 3. 掩埋5.3.4处理场所固定成本（元/周）
1920变动成本（元/吨） 12 16 6焚烧 城镇 运费（元/吨） 城镇 1 城镇 2 处理能力（吨/周） 7.5 5.0 1000填海 5.0 7.5 500掩埋 15.0 12.5 1300应处理量（吨） 700 1200211000-1 Xij (i = 1, 2; j = 1, 2, 3) i i22 100Yi(i = 1, 2, 3) jXij Yi 0-1o.b. min 12 × (X11 + X21) + 16 × (X12 + X22)+ 6 × (X13 + X23) + 7.5X11 + 5.0X12 + 15.0X13+ 5.0X21 + 7.5X22 + 12.5X23 + 3850Y1 + 1150Y2 + 1920Y3 s.t. X11 + X12 + X13 = 700 X21 + X22 + X23 = 1200 X11 + X21 X12 + X22 X13 + X23 Y2
1 2 1 2 323 100Yi = 0 1(i = 1, 2, 3) Xij (i = 1, 2; j = 1, 2, 3)Spreadsheet5.3.35.3.524100Spreadsheet 5.3.5.15.3.3.1251005.3.4261005.3.45.3.55.3.65.3.6处理场所 焚烧 城镇 废物量（吨） 城镇 1 城镇 2 700 300 0 0 0 900 填海 掩埋Y1 = 1, Y2 = 0, Y3 = 127 1001 2 900 700 3003.3.5.3.35.3.7 5.3.828 1005.3.7单位 工厂 1 工厂 2 45000 工厂 3 40000 工厂 4 42000 工厂 5 40000 分配中心 1 分配中心 2 分配中心 3
60000 年固定成本 （元） 350005.3.8终点 起点 工厂 1 工厂 2 工厂 3 工厂 4 工厂 5 分配中心 1 800 700 800 500 700 运输成本（元/箱） 生产能力（箱） 分配中心 2
600 600 分配中心 3
700 500 300 200 300 200 4005.3.9终点 起点 工厂 1 工厂 2 工厂 3 工厂 4 工厂 5 分配中心 1 800 700 800 500 700 运输成本（元/箱） 生产能力（箱） 分配中心 2
600 600 分配中心 3
700 500 300 200 300 200 400291005.3.5生产能力 分店 1 需求量 200300工厂 1 1200800
中心 140 80 90 40 30200工厂 2200工厂 3500 700 800 600 500 500 700 700 60050 70 600 中心 2分店 230060 80 80 5030100300工厂 4 中心 3分店 3150400工厂 550060 800 分店 4 2505.3.50-1 Xij (i = 1, ? ? ? , 5; j = 1, 2, 3) Fi(i j i j i Di = 1, ? ? ? , 5) Yij (i Xij Fi Yij 0-1 0-1 i = 1, 2, 3; j i31 100=1, ? ? ? , 4) Di(i = 1, 2, 3)0-1 o.b. min 800X11 + 1000X12 + 1200X13 + 700X21 + 500X22+ 700X23 + 800X31 + 600X32 + 500X33 + 500X41 + 600X42+ 700X43 + 700X51 + 600X52 + 40Y11 + 80Y12 + 90Y13+ 50Y14 + 70Y21 + 40Y22 + 60Y23 + 80Y24 + 80Y31 + 30Y32+32 10050Y33 + 60Y34 + 35000F1 + 45000F2 + 40000F3 + 000F5 + 40000D1 + 20000D2 + 60000D3 s.t. X11 + X12 + X13 X21 + X22 + X23 X31 + X32 + X33 300F1 200F2 200F3 1 2 3X41 + X42 + X43 X51 + X52 + X53200F4 200F5 14 5X11 + X12 + X13 + X14 + X15 = Y11 + Y12 + Y13 + Y14 X12 + X22 + X32 + X42 + X52 = Y21 + Y22 + Y23 + Y24 2 X13 + X23 + X33 + X43 + X53 = Y31 + Y32 + Y33 + Y34 3 Y11 + Y12 + Y13 + Y14 Y21 + Y22 + Y23 + Y24 Y31 + Y32 + Y33 + Y34 900D1 900D2 900D3 1 2 333 100Y11 + Y21 + Y31 Y12 + Y22 + Y32 Y13 + Y23 + Y33 Y14 + Y24 + Y34 Yij200 300 150 2501 2 3 434 100Fi = 0 1(i = 1, ? ? ? , 5), Di = 0 1(i = 1, 2, 3) 0-1 0(i = 1, 2; j = 1, ? ? ? , 4)Spreadsheet5.3.105.3.10351005.3.105.3.636 1005.3.65.3.115.3.11工厂 工厂 1 工厂 2 工厂 3 工厂 4 工厂 5 分配中心 1 300 0 0 0 05.3.12分配中心 3 0 0 300 0 300分配中心 2 0 0 0 0 05.3.12分配中心 分配中心 1 分配中心 2 分配中心 3分销店 1 200 0 0分销店 2 0 0 250分销店 3 0 0 200分销店 4 100 0 150371000-1F1 = 1, F2 = 0, F3 =1, F4 = 0, F5 = 1 D1 = 1, D2 = 0, D3 = 15.3.11 6995005.3.12381003.4.A AB B39 1005.3.411 4 5.3.7 A, B, C, D 1, 2, 3, 4, ? ? ? , 1140100?9 1 B 82 A 3 6 11 4 5 C41 100D 7 105.3.7A 1 2 A11 AB4 BBB SpreadsheetA 5.3.13 5.3.1342100Spreadsheet 5.3.145.3.13.1431005.3.8 5.3.13 5.3.13 .3.145.3.14消防站 A 决策变量 1 消防站 B 0 消防站 C 1 消防站 D 1441003.5.451004610047100
用Excel解决简单线性规划问题_理学_高等教育_教育专区。用Excel解决简单线性规划问题...Z时,我们只须在上 面的求解中添加约束条件: “$B$8=整数;$B$9=整数”...Excel求解线性规划问题实验教程_计算机软件及应用_IT/计算机_专业资料。挺好 ...线性和整数规划问题取自 Frontline Systems 公司的 John Watson 和 Dan Fylstra ...Excel求解运筹学问题简介_金融/投资_经管营销_专业资料...其中,单元格 B2、C2 为决策变量初值,对于线性规划...1.4 整数规划求解 例 1-3 求解下列整数规划问题 ?...下列关于用 Excel 求解整数规划的说法正确的是() A. 基本步骤与求解一般线性规划问题相同 B. 需在约束条件中添加一个“整数”约束 C. 在 Excel 规划求解的“...Excel 四、实验内容 (一)整数规划 1、0-1 整数规划 其中,D11=F2;D12=F3;...在 【选项】菜单中选择“采用线性模型” “假定非负” 。即可进行求解得结果,...一、实验目的 1、 掌握如何建立整数线性规划模型,特别是0～1逻辑变量在模型中的应用。 2、 掌握用Excel求解整数线性规划模型的方法。 3、 掌握如何借助于Excel对...利用Excel软件进行非线性拟合的非编程方法_IT/计算机_专业资料。摘要:一种在Excel...束条件);或者指定某参数为整数(利用规划求解中的整数规划或者混合规划求 解器)...EXcel文件输入; enddata calc: @text('a_out.txt') = !列向量形式...(解线性整数规划); @divert('intModel_out.txt'); @write(@newline(2),'...使用Excel 规划求解 2000 年 10 月 Excel 规划求解的选项可以用来解决线性规划与非线性规划优化问题。可以设置决策变 量为整数约束。规划求解可以用来解决最多有 ...Excel 软件、管理运筹学软件,掌握线性规划的 Excel 求解和管理运筹学 软件求解。...本节实验要求完成以下内容: 1、整数规划问题模型的建立; 2、Excel 界面内数据...
All rights reserved Powered by
copyright &copyright 。文档资料库内容来自网络，如有侵犯请联系客服。查看: 2460|回复: 0
用EXCEL2003解决线性规划问题时如何做出可行域？
阅读权限20
在线时间 小时
大家好，我是一名高中数学教师，我知道Excel2003可以解决线性规划问题，但不知可否使用Excel做出可行域，做到图文并茂，数形结合？（顺便问一下，当我看到别人的Excel作品后，想模仿一下，但又不知如何下手，可否请朋友们指点迷津！）
玩命加载中，请稍候
玩命加载中，请稍候
Powered by
本论坛言论纯属发表者个人意见，任何违反国家相关法律的言论，本站将协助国家相关部门追究发言者责任！ & & 本站特聘法律顾问：徐怀玉律师 李志群律师您的访问出错了(404错误)
很抱歉，您要访问的页面不存在。
1、请检查您输入的地址是否正确。
进行查找。
3、感谢您使用本站，两秒后自动跳转至网站首页