- ۲۴ آذر ۹۴ ، ۲۳:۵۰
- ۰با نظرات خود کمکمون کنید
کد پایتون برای مسئله p-median و الگوریتم لاگرانژین
g=[[0,210,360,240,60],[350,0,80,420,100],[450,60,0,360,140],[200,210,240,0,40],[150,150,280,120,0]]
f=[200,100,100,100,100]
ub=2000000
lb=0
import copy
m=5
n=5
p=2
y=[0,0,0,0,0]
while ub!=lb :
you=[]
s=copy.deepcopy(g)
for j in range(0,m):
for i in range(0,n):
if s[j][i]-f[i]<0 :
s[j][i]=s[j][i]-f[i]
else :
s[j][i]=0
v=[]
for j in range(0,m):
num=0
for i in range(0,n):
num=num+s[j][i]
v.append(num)
for j in range(0,m):
y[j]=0
v1=copy.deepcopy(v)
for j in range(0,p):
r=v1.index(min(v1))
you.append(r)
y[r]=1
v1[r]=1000000000000000000000000000000
x=copy.deepcopy(g)
for j in range(0,m):
if y[j]==1:
for i in range(0,n):
if s[j][i]<0 :
x[j][i]=1
else :
x[j][i]=0
else :
for i in range(0,n):
x[j][i]=0
z1=0
z11=0
z12=0
for j in range(0,m):
z11=z11+(v[j]*y[j])
for i in range(0,n):
z12=z12+f[i]
z1=z12+z11
z2=0
lb=max(lb,z1)
e=copy.deepcopy(x)
for i in range(0,n):
for j in range(0,m):
e[j][i]=0
for i in range(0,n):
ver=copy.deepcopy(g[you[0]][i])
per=i
cer=you[0]
for j in range(0,p):
if g[you[j]][i] < ver :
ver=g[you[j]][i]
per=i
cer=you[j]
e[cer][per] = 1
for i in range(0,n):
for j in range(0,m):
z2=z2+(e[j][i]*g[j][i])
ub=min(z2,ub)
print(f,ub,lb)
t1=0
for i in range(0,n):
t2=0
for j in range(0,m):
t2=t2+x[j][i]
t1=t1+((t2-1)**2)
t=(1*(ub-lb))/t1
for i in range(0,n):
w=0
for j in range(0,m):
w=w+x[j][i]
f[i]=max(0,f[i]-t*(w-1))