线性规划（200分悬赏，回答的好最佳50分）

Question

刚学习了线性规划，我发现好烦了啊，我现在就是2元一次的线性规划问题，通常都是画图来解答！没写一题就要话这么都条直线，然后有要考虑公共部分是哪些，图有没有什么地方没画标准，平移时又要看清楚到底那个点最多，那个点最小！
要是就写一道题还好写，一连写这么多，每道题都要这样画图，而且至少要画的比较标准，真不少要我的命吗？
所以希望大家能提出点解题技巧和方法，难道除一个一条一条的直线老老实实的画出来以外，就没有其它方法了吗？
希望大家多多帮忙，能教在下些不要每题都去画图的方法，我再次谢谢给我了！

Answer 1

整数线性规划的解法总结

0-1整数线性规划是整数线性规划的特殊情况，在实际中有着广泛的应用。虽然变量的取值只有两个，但此类问题的求解却意外的困难，下面把有关的一些解法总结一下。

1.穷举法 把所有可能的解一一代入，然后比较满足约束的解，使目标函数最达到最优的解是最优解。这不失为一种方法，但不是一种好方法。如果问题规模大，则无法在可接受的时间内求得最优解。这也是求解整数规划的困难所在。

2.隐枚举法I 是穷举法的改进，其思路是先给出一个可行解，然后代入目标函数算出函数值得到一个上界（如果求最小值）或下界（如果是求最大值）。然后一一检验其它的解，如果该解大于上界或小于下界，则不用检验可行性，因为它不可能是最优解，否则的话就要检验可行性，如果是可行解，则修改上界或下界，继续检验其它的解，否则不用修改上界或下界，直接检验其它的解。这种方法通过上界或下界来控制是否需要进行可行性检验，提高了效率。但是，要找可行解也得花一定的时间，当约束和变量较多时，工作量异常的大，退一步来说，即使可行解比较容易找到，但其产生的上界太大，或是下界太小，则其过滤的效果也不明显。这是这种方法的缺陷。

3.隐枚举法II 这种方法先把问题转化成标准型，然后按照分枝定界法的思想，尽量少的检验可行解来寻找最优解。这种方法比较麻烦，我在这里也描述不清楚，过几天理解透了再来写这一部分。

4.隐枚举法III 这是在程冬时，张声年在江西电力职业技术学院学报上发表的一篇文章《关于0-1型整数规划的若干问题》中提出来的，大致的思路是：把所有可能的解都代入目标函数算出值，然后把这些目标函数值进行排序，如果是求最大值，则降序排列，如果是求最小值则升序排列。然后按这个顺序一个一个的检验对应的解的可行性，当碰到第一个可行解时即得到最优解，因为其它的解不会优于此解了。这种方法的缺陷也是明显的，如果变量为N个，则需求2的N次个目标函数值，然后还要进行排序，这又是项工作量很大的工作，再一个就是，如果排序结果是把可行解排在最后一个，那还是得进行2的N次方次检验。

4.启发式算法 遗传算法，蚁群算法等都可归于此类。这都是随机算法，说白了就是听天由命，即使算出了最优解你也不知道是不是最优解，因为此类算法的收敛性都只是依概率收敛的，真正在算的过程中是否已得到最优只有上帝知道。启发式算法是万不得已的情况下才使用的，我们用这种方法只能保证得到的解比其它方法得到的好，但不一定就说得到了最优了。

0-1规划的求解方法还在研究之中，也许你会发现一个有效的算法。

Answer 2

你可以把所有要画直线的斜率都求出来，从小到大或者从大到小排序。再把目标函数的斜率求出来。看看目标函数的斜率介于哪两个斜率之间。把它们两个的直线方程写出来，列成方程组。解出交点，一般这个交点就是最优解。这个方法适用于线性区域是封闭图形的 说实话，线性规划确实很麻烦，但要学好也只有这一条路！！
学好了对以后的很多题目的解答都大有益处，其实你只要弄懂方法，做三五道题就可以了！

实在没有什么捷径！！

Answer 3

你可以把所有要画直线的斜率都求出来，从小到大或者从大到小排序。再把目标函数的斜率求出来。看看目标函数的斜率介于哪两个斜率之间。把它们两个的直线方程写出来，列成方程组。解出交点，一般这个交点就是最优解。这个方法适用于线性区域是封闭图形的

Answer 4

1、其实画图是最直观、简明的方法，但是如果你的图都得手工去画就不是那个事了。用数学软件呀。

2、搞清楚ax+by+c>0是哪半边，你可以少画或者不画图。a>0时，ax+by+c>0表示直线的右半区域（因可化为x>…，大于符号表示右半），或者b>0时ax+by+c>0表示直线的上半区域。

Answer 5

我是运筹学专业博士生 就是研究线性规划方向的
画图法是最简单的 没有更简单的了 你以后会要用单纯型法来做多元一次 不用画图 但要麻烦得多
其实画图不用很标准，只需要知道交点的大致位置 然后解出交点 就可以对比了 一般直接就可以找出最大最小值的点 再带回目标方程即可
我就是学这个专业的研究生 说的到目前为止肯定是对的
如果一定要用简便方法 可以用excel 或编程 都可以解决