Python：每日一题 105

jerryxjr1220

每日一题似乎好久不更新了，我来贡献一题吧。

首先我们的玩法做了一下改变：
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位即可）

bush牛

我觉得最大值为1，x = 1, y = 0

jerryxjr1220

bush牛 发表于 2017-9-28 21:48
我觉得最大值为1，x = 1, y = 0

对的，程序呢？

鱼油9527

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)

bush牛

jerryxjr1220 发表于 2017-9-28 22:11
对的，程序呢？

程序不知道从什么地方开始写~完全没有写过这样的。这个起始变量不知道怎么定义。

jerryxjr1220

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[0]+2*n[1]))

(1.0, 0.0)
先把范围内所有符合条件的点都获取到，然后求最大值。
当然，这种计算法效率很低，差不多要13s才能计算这么简单的题。

jerryxjr1220

另外一种高效的方法，就是利用一个非常牛逼的线性规划库--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以内就出答案了。

这个牛逼的线性规划库功能十分强大，还可以用来求“数独”，“八皇后”等等这种难度比较大的线性规划问题，关键是效率非常高！

solomonxian

这类题都是直线，基本上就是求所有交点代入的最大值
用矩阵求解线性方程组，结果应该很精确

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[0]+j[0]).reshape(2,2)
        b = np.array([i[1],j[1]]).reshape(-1,1)
        result.append(*np.linalg.solve(a,b).T)
    # 去掉不符合项
    result = filter(lambda x: 2*x[0]-x[1] <= 2 and 3*x[0]-2*x[1] >= 3 and x[0]+x[1] <= 2, result)
    d = max(result, key=lambda x: x[0] + 2*x[1])
    return "最大值是：%s，当前(x,y)为：%s" % (d[0] + d[1] *2, d)

solomonxian

我记得读中学时好像是画图解决的吧，
暂时不知道用python画出来之后要怎么解

import pylab

def fun():
    x = pylab.arange(-5,6)
    y = ("2 * (x-1)", "3 * (x-1)/2", "2 - x") # 3个方程用y表示
    [pylab.plot(x, eval(i), label="y = %s"%i) for i in y]
    pylab.legend() 
    pylab.show()

bush牛

jerryxjr1220 发表于 2017-9-29 09:53
另外一种高效的方法，就是利用一个非常牛逼的线性规划库--pymprog，详细的使用说明点链接查看。

程序基 ...

学习了。
您提供的第一种方法，我运行了下，是很慢。基本上思路就是暴力枚举。
第二种方法【线性规划库】我是第一次听说，我要主要学习一下。

jerryxjr1220

solomonxian 发表于 2017-9-29 19:05
我记得读中学时好像是画图解决的吧，
暂时不知道用python画出来之后要怎么解

是的，画图可以解决，不等式在图像上其实就是表示为直线的某一方（上方或下方），当你把3个不等式画出来的话，其实就是表示为其所组成的范围。然后你再把要求的那条直线画上，最大值就是求直线与所围部分交点的最高点，最小值就是最低点。

小贤啊哦

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[0]+2*x[1]))