复习到了SA,正好做了一道利用SA解决LP问题,是非常基础的一道题目。
求x1-3x2的最小值?
其中满足的条件是:2x1+3x2<=6,-x1+x2<=1,x1>=0,x2>=0,一看可能会有点熟悉的题目吧,是啊,这个是高中最普遍的解决线性规划的问题,我们当时的变量不多,如果变量好多的话,解决就要需要电脑了,现在我用SA的想法来解决问题。
首先要加入衬垫变数x3,x4,使得2x1+3x2+x3=6,-x1+x2+x4=1,其中x1>=0,x2>=0,x3>=0,x4>=0.然后利用SA算法,下面有表格做说明
0 | -1 | -3 | 0 | 0 |
| x1 | x2 | x3 | x4 |
6 | 2 | 3 | 1 | 0 |
1 | -1 | 1 | 0 | 1 |
做法首先确定了其中的基底x3和x4(两个是线性无关的),然后找到第一行中的是负数的最小的那个,然后纵向找到一个正数即3,接着就是线性代数的知识,使得基底进行变动,并且使得第一行中的负数变为0
3 | -4 | 0 | 0 | 3 |
| x1 | x2 | x3 | x4 |
3 | 5 | 0 | 1 | -3 |
1 | -1 | 1 | 0 | 1 |
下面的操作和上面的类似,最终得到
27/5 | 0 | 0 | 4/5 | 3/5 |
| x1 | x2 | x3 | x4 |
3/5 | 1 | 0 | 1/5 | -3/5 |
8/5 | 0 | 1 | 1/5 | 2/5 |
对应表格中的左上角的数正是我们所求数的相反数,所以最小的值因为-27/5,而此时我们可以得到x1=3/5,x2=8/5
分享到:
相关推荐
2010年ACM/ICPC暑期集训的时候自己做的组合数学讲稿,希望能多大家的授课有所帮助~~ 目录 1 引言 组合数学 1 1.1 组合数学研究的基本问题 1 1.2 两个基本计数原理 1 1.2.1 加法原理 1 1.2.2 乘法原理 1 1.3 排列...
本书是系统阐述组合数学基础、理论、方法和实例的优秀教材,出版30多年来多次改版,被MIT、哥伦比亚大学、UIUC、威斯康星大学等众多国外高校采用,对国内外组合数学教学产生了较大影响,也是相关学科的主要参考文献...
组合数学 清华大学计算机 黄连生 组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。...但是,要学好组合数学并非易事,既需要一定的数学修养,也要进行相当的训练。
组合数学 卢开澄 清华大学出版社 第四版第一章习题答案 可惜只找到第一章~
组合数学训练 材料 acm 训练的部分资料
组合优化问题,组合数学的重要部分 组合数学 重要部分
本书是系统阐述组合数学基础、理论、方法和实例的优秀教材,出版近30年来多次改版,被MIT、哥伦比亚大学、UIUC、威斯康星大学等众多国外高校采用,对国内外组合数学教学产生了较大影n向,也是相关学科的主要参考文献...
卢开澄组合数学第五版第四章讲义 Burnside引理和Polya定理
兴趣教学法在《组合数学》课程中的应用,李雪珊,,结合笔者近几年的组合数学研究及授课经验,探讨了如何通过多讲数学故事、整合零散知识、训练一题多解、介绍知识应用等途径,激发
本书是系统阐述组合数学基础、理论、方法和实例的优秀教材,出版近30年来多次改版,被MIT、哥伦比亚大学、UIUC、威斯康星大学等众多国外高校采用,对国内外组合数学教学产生了较大影n向,也是相关学科的主要参考文献...
计算机的数学基础,组合数学,(原书第四版) 本书是系统阐述组合数学基础、理论、方法和实例的优秀教材,出版近30年来多次改版,被MIT、哥伦比亚大学、UIUC、威斯康星大学等众多国外高校采用,对国内外组合数学教学...
同等学力 计算机综合 离散数学 组合数学 习题练习
同等学力 计算机综合 组合数学 练习习题
卢开澄的组合数学第四版的参考答案,通过这些习题的练习和参考答案,便于理解组合数学的概念、方法、应用技巧,对理解组合数学的原理、算法、应用具有参考价值
1.1 组合数学的研究对象 1.2 组合问题的基本解题方法 1.3 回溯法的讨论 习题一 第二章 从鸽笼原理到Ramsey理论 2.1 鸽笼原理 2.2 Ramsey问题和数 习题二 第三章 排列组合信其计数问题 3.1 两个基本计数原理 3.2 排列...
本书是系统阐述组合数学基础、理论、方法和实例的优秀教材,出版近30年来多次改版,被MIT、哥伦比亚大学、UIUC、威斯康星大学等众多国外高校采用,对国内外组合数学教学产生了较大影n向,也是相关学科的主要参考文献...
五年级数学思维训练组合图形的面积.pdf
数学排列和组合练习题 加详细解释.rar
六年级上册数学组合图形面积练习 .ppt