Python：每日一题 105
本帖最后由 jerryxjr1220 于 2017-9-28 15:19 编辑每日一题似乎好久不更新了，我来贡献一题吧。
首先我们的玩法做了一下改变：
1. 楼主不再提供答案。24小时后，会贴出参考解答。
2. 大家独立思考。
3. 鼓励大家积极答题，奖励的期限为出题后24小时内。
4. 根据答案的质量给予1~5鱼币的奖励。
题目：求最值
已知：
2 * x - y <= 2
3 * x - 2 * y >= 3
x + y <= 2
求：
x + 2 * y 的最大值是多少？当x与y分别是多少时取得？
相信解题是非常容易的，那么用python程序你会怎么写？（如果有小数，答案请保留小数点后3位即可） 我觉得最大值为1，x = 1, y = 0 bush牛 发表于 2017-9-28 21:48
我觉得最大值为1，x = 1, y = 0
对的，程序呢？ x_list = []
y_list = []
for x in range(10):
for y in range(10):
if 2*x - y <= 2:
if 3*x - 2*y >= 3 and x + y <= 2:
x_list.append(x)
y_list.append(y)
a = max(x_list)
b = max(y_list)
print('x+2*y的最大值为：',a+b)
print('x为：',a)
print('y为：',b)
jerryxjr1220 发表于 2017-9-28 22:11
对的，程序呢？
{:5_100:}程序不知道从什么地方开始写~完全没有写过这样的。这个起始变量不知道怎么定义。 bush牛 发表于 2017-9-28 23:15
程序不知道从什么地方开始写~完全没有写过这样的。这个起始变量不知道怎么定义。
起始值的设置一种可以通过条件（不等式）计算出范围，另外一种就是完全靠猜（但是有可能不在猜测范围内）。
先贴一种边界范围靠猜测（-3到3范围之内），按照精度要求保留小数点3位。
lists=[]
for I in range(-3000,3000):
i = I/1000.0
for J in range(-3000,3000):
j = J/1000.0
if 2*i-j<=2 and 3*i-2*j>=3 and i+j<=2:
lists.append((i,j))
print(max(lists,key=lambda n:n+2*n))
(1.0, 0.0)
先把范围内所有符合条件的点都获取到，然后求最大值。
当然，这种计算法效率很低，差不多要13s才能计算这么简单的题。 另外一种高效的方法，就是利用一个非常牛逼的线性规划库--pymprog，详细的使用说明点链接查看。
from pymprog import *
begin('test')
x=var('x', bounds=(None,None))
y=var('y', bounds=(None,None))
2*x-y<=2
3*x-2*y>=3
x+y<=2
maximize(x+2*y)
solve()
print(x.primal, y.primal)
程序基本上就是把已知条件直接原封不动的复制上去，然后稍微设定一下，程序就自动计算了。
下面是结果：
GLPK Simplex Optimizer, v4.60
3 rows, 2 columns, 6 non-zeros
0: obj =-0.000000000e+00 inf = 3.000e+00 (1)
1: obj = 1.000000000e+00 inf = 0.000e+00 (0)
* 2: obj = 1.000000000e+00 inf = 0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
1.0 0.0
0.1s以内就出答案了。
这个牛逼的线性规划库功能十分强大，还可以用来求“数独”，“八皇后”等等这种难度比较大的线性规划问题，关键是效率非常高！ 这类题都是直线，基本上就是求所有交点代入的最大值
用矩阵求解线性方程组，结果应该很精确
import itertools as it
import numpy as np
def fun():
result = []
for i,j in it.combinations([((2,-1),2),((3,-2),3),((1,1),2)], 2):
a = np.array(i+j).reshape(2,2)
b = np.array(,j]).reshape(-1,1)
result.append(*np.linalg.solve(a,b).T)
# 去掉不符合项
result = filter(lambda x: 2*x-x <= 2 and 3*x-2*x >= 3 and x+x <= 2, result)
d = max(result, key=lambda x: x + 2*x)
return "最大值是：%s，当前(x,y)为：%s" % (d + d *2, d) 我记得读中学时好像是画图解决的吧，
暂时不知道用python画出来之后要怎么解{:10_269:}
import pylab
def fun():
x = pylab.arange(-5,6)
y = ("2 * (x-1)", "3 * (x-1)/2", "2 - x") # 3个方程用y表示
pylab.legend()
pylab.show()
jerryxjr1220 发表于 2017-9-29 09:53
另外一种高效的方法，就是利用一个非常牛逼的线性规划库--pymprog，详细的使用说明点链接查看。
程序基 ...
学习了。
您提供的第一种方法，我运行了下，是很慢。基本上思路就是暴力枚举。
第二种方法【线性规划库】我是第一次听说，我要主要学习一下。
solomonxian 发表于 2017-9-29 19:05
我记得读中学时好像是画图解决的吧，
暂时不知道用python画出来之后要怎么解
是的，画图可以解决，不等式在图像上其实就是表示为直线的某一方（上方或下方），当你把3个不等式画出来的话，其实就是表示为其所组成的范围。然后你再把要求的那条直线画上，最大值就是求直线与所围部分交点的最高点，最小值就是最低点。{:10_256:} a=[]
for x in range(10):
for y in range(10):
if 2 * x - y <= 2 and 3 * x - 2 * y >= 3 and x + y <= 2:
a.append((x,y))
print(max(a,key=lambda x : x+2*x))
页:
[1]