最优化方法线性规划求解实现

1.概念原理：

如果线性规划问题有可行解，那么该解必须满足 所有不等式要求。

2.利用图解法求解最优值

所有不等式要求：

$$x1+x2<=6$$

$$-x1+2x2<=8$$

$$x1,x2>=0$$

求解最大值：

$$max（z= x1+3*x2）$$

话不多说直接上python咱们画出来：

import numpy as np
import matplotlib.pylab as plt
x2 = np.arange(-10,10.0,0.1)
x22 = np.arange(-10,10,0.1)
x_mark2=np.arange(-10,10,0.1)
x1 = 6-x2
x11=2*x22-8
plt.xlabel("x2")
plt.ylabel("x1")
x_mark1=46/3-3*x_mark2
plt.plot(x2,x1 ,label="x1+x2=6")
plt.plot(x22,x11,label="-x1+2x2=8")
plt.plot(x_mark2,x_mark1,label="x1=46/3-3x2( assume z=46/3)")
plt.title("xk_solve")
plt.ylim(0,10) # 指定y轴的范围，画出来的效果不一样
plt.xlim(0,10) # 指定y轴的范围，画出来的效果不一样
plt.legend()
plt.show()

结论：一目了然，咱们Z的最大值就是46/3，三线交点为（4/3,14/3）

3.求解规划问题

要做一些香肠，现有以下原料可供选择:

原料 成本 可供数量
猪肉 23.32 30
小麦 2.46 20
淀粉 1.86 17
打算做两种香肠：
经济型：（猪肉 > 40%）
优质型：（猪肉> 60%）
一根香肠50克(0.05公斤)。
根据政府规定，我们在香肠中最多可以使用25%的淀粉，现在和屠夫已经签定了购买23公斤猪肉的合同，如果猪肉不使用就会变质。 目前市场有350根经济香肠和500根高级香肠的需求。那么我们如何最有效地生产香肠。

问题分析

直接假设使用猪肉，小麦，和淀粉的kg数分别为x猪，x小，x淀，
则有：

$$（ min） 钱= 23.32*x猪+2.46*x小+1.86*x淀$$

$$x猪<=30 且 x猪>=23$$

$$x小<=20 且 x小>=0$$

$$x淀<=17 且 x淀>=0$$

我们继续假设经济型和优质型香肠有n经,n优，经济型里含猪肉占比p猪经，优质型里含猪肉占比p猪优,经济型里含淀粉占比p淀经，优质型里含淀粉占比p淀优，
则有：

$$n经>=350 且 n优>=500$$

$$p猪经>0.4 且p猪经<=1$$

$$p猪优>0.6 且p猪优<=1$$

$$p淀优<=0.25 且p淀优>=0$$

$$p淀经<=0.25 且p淀经>=0$$

$$0<=(1-p淀优-p猪优)<=1$$

$$0<=(1-p淀经-p猪经)<=1$$

$$x猪=（n经*p猪经+n优*p猪优）*0.05$$

$$x小=（n经*(1-p淀经-p猪经)+n优*(1-p淀优-p猪优)）*0.05$$

$$x淀=（n经*p淀经+n优*p淀优）*0.05$$

所以带入上式： 最低花费公式就为：

$$（ min） 钱= 23.32*(n经*p猪经+n优*p猪优)*0.05$$

$$+2.46*(n经*(1-p淀经-p猪经)+n优*(1-p淀优-p猪优))*0.05$$

$$+1.86*(n经*p淀经+n优*p淀优)*0.05$$

由于n是我们自己设的变量，p也是我们自己设的变量，所以此模型不能用python的线性规划scipy求解。白给！

不过小康必须得给它解出来，咱们可以先用贪心算法，将此题强制转化为一道线性规划问题，我们根据题干我们直接玩贪的，因为淀粉最便宜，我们直接设淀粉直接占0.25,猪肉最贵，那么假设猪肉直接占0.4和0.6.这样，对应的小麦就是0.35和0.15:

import numpy as np
from scipy.optimize import linprog
c = np.array([23.32, 2.46,1.86])
print(linprog(c,bounds=([22, 30], [9.875, 9.875],[10.625,10.625])))#贪心算法10.625<17

我们发现居然全部戳戳有余，甚至猪肉还少用了1kg。那么如果不改变猪肉占比的话，我们还必须把23-22=1（kg）的猪肉给用了，不然臭了。于是我们还要做出超标的香肠。不过可以得出一个线性规划问题，就是这么用1kg猪肉和相应的占比，做出最便宜的预算：

假设n1,n2 为1kg猪肉能制作的经济型，优质型数量，则有：

$$min(z)=23.32*（0.4*0.05*n1+0.05*0.6*n2）$$

$$+2.46*(0.35*0.05*n1+0.15*0.05*n2)$$

$$+1.86*(0.25*0.05*n1+0.25*0.05*n2)$$

$$0.4*0.05*n1+0.05*0.6*n2>=1$$

$$0.35*0.05*n1+0.15*0.05*n2<=20-9.875$$

$$0.25*0.05*n1+0.25*0.05*n2<=17-10.625$$

$$n1,n2>=0$$

所以我们直接利用python求出结果：

import numpy as np
from scipy.optimize import linprog
c = np.array([0.5327, 0.7413])
a_ub = np.array([[-0.4*0.05, -0.6*0.05], [0.35*0.05, 0.15*0.05],[0.25*0.05, 0.25*0.05]])
b_ub = np.array([-1, 20-9.875,17-10.625])
print( linprog(c, a_ub, b_ub,  bounds=([0, None], [0, None])))

也就是说我们要用0个经济，33.3循环个优质来消耗完最后1kg最划算。需要向上取整，则为0个经济，34个优质。

最后我们做出了350根经济香肠，534根优质香肠，经济香肠肉，小麦，淀粉占比分别为0.4,0.35,0.25.优质香肠肉，小麦，淀粉占比分别为0.6,0.15,0.25.一共需要花费557.095+约24.71=581.805（元）

附

将其不看做线性规划问题解法：

如果不把其看做线性规划，那么我们利用贪心发现他还少用了1kg猪肉，那我们必须适当加大猪肉占比，同时保证价格最低，所以，我们在不减少淀粉的条件下，减少小麦的用量即可，从宏观上看1kg猪肉随机加入到850个香肠中，则一定要有1kg的小麦被移除，所以最后的最低预算是：

$$min(z)=(22+1)*23.32+2.46*(9.875-1)+1.86*10.625= 577.955(元)$$

可以看出577.955<581.805

这1kg猪肉完全可以随机的加入到850根香肠中的任何一根里面，因为都满足要求，最后生产出来的刚好是预算最低，刚好符合数量要求，并且也用完了23kg猪肉的方案。但这并不是用所学线性规划解决。因为这不是一个线性规划问题。