-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathQuestion No. 1
144 lines (136 loc) · 7.83 KB
/
Question No. 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
def frange(a,b):
temp=a
while(temp<b):
yield(temp)
temp+=0.01
class LPsolver:
def __init__(self): # Initialising instance variables
self.objective=None
self.constraints=None
self.table=None
self.result=None
def solve(self,L,M,option):
return (self.Simplex(L,M))
def Simplex(self,L,M): # Simplex function takes two lists as arguments
# List L contains co-efficients of variables in the objective
# e.g.- If objective is (2x+5y+7z) then L=[2,5,7]
# List M contains co-efficients of variables in the constraints and the last element is the constant
# List M is a nested list
# e.g. - If the constraints are x<=200 , y<=10 , z<=200 and x+2y+3z<=700 then --
# M=[[1,0,0,200],[0,1,0,10],[0,0,1,200],[1,2,3,700]], i.e.,
# 1.x+0.y+0.z<=200 , 0.x+1.y+0.z<=10 , 0.x+0.y+1.z<=200 and 1.x+2.y+3.z<=700
from numpy import array
self.objective=array(L,float)
self.constraints=array(M,float)
no_of_variables=len(self.objective) # variable to store total number of variables
no_of_equations=len(self.constraints) # variable to store total number of equations(constraints)
self.table=array([[0 for i in range(no_of_variables+no_of_equations+2)] for j in range(no_of_equations+1)],float) # initialising the augmented matrix
for i in range(no_of_equations):
for j in range(no_of_variables):
self.table[i][j]=self.constraints[i][j] # filling up the matrix
for i in range(no_of_variables):
self.table[-1][i]=(-1)*self.objective[i] # filling up the matrix
for i in range(no_of_equations+1):
self.table[i][no_of_variables+i]=1 # filling up the matrix
for i in range(no_of_equations):
self.table[i][-1]=self.constraints[i][-1] # filling up the matrix
self.table[-1][-1]=0 # matrix ready
for i in range(no_of_equations+1):
self.table[i][no_of_variables+i]=self.table[i][-1]/self.table[i][no_of_variables+i]
flag=0
if(min(self.table[-1])>=0): # testing terminal condition
flag=1
while(flag==0): # loop
pivot_col=self.table[-1].tolist().index(min(self.table[-1])) # finding column of pivot
pivot_row,temp,flag2=-1,0,0
for i in range(no_of_equations):
if(self.table[i][pivot_col]>0 and (pivot_row==-1 or self.table[i][-1]/self.table[i][pivot_col]<temp)): # finding row of pivot
pivot_row=i
temp=self.table[i][-1]/self.table[i][pivot_col]
flag2=1
if(flag2==0):
return ("Unbound") # terminal condition
pivot=self.table[pivot_row][pivot_col]
for i in range(no_of_equations+1): # loop to set all other elements of pivot's column to 0 by row operations
if(i==pivot_row):
continue
scale=self.table[i][pivot_col]/pivot
self.table[i]=self.table[i]-(scale*self.table[pivot_row])
if(min(self.table[-1])>=0):
flag=1 # terminal condition
x_pos,y_pos,count_1,count_2=0,0,0,0 # variables to store boundary points
for i in range(no_of_equations+1):
if(self.table[i][0]!=0):
count_1+=1
x_pos=self.table[i][-1]/self.table[i][0]
if(self.table[i][1]!=0):
count_2+=1
y_pos=self.table[i][-1]/self.table[i][1]
if(count_1>1):
x_pos=0
if(count_2>1):
y_pos=0
plt.plot(x_pos,y_pos,"o",color="c") # plotting boundary points
self.result="" # string to store final answer
for i in range(no_of_variables): # building up the string
count,temp,flag=0,0,1
for j in range(no_of_equations+1):
if(self.table[j][i]!=0):
count+=1
if(count>1):
flag=0
break
temp=self.table[j][-1]/self.table[j][i]
if(flag==1):
self.result+="x_"+str(i+1)+" = "+str(temp)+" ; "
else:
self.result+="x_"+str(i+1)+"=0 ; "
self.result+="Maximum value of objective = "+str(self.table[-1][-1])
self.plot()
return (self.result) # return result
def plot(self):
Color=["b","g","r","y","m"] # list of colors to be used
j=0 # counter variable
plt.xlabel("x axis")
plt.ylabel("y axis")
Legend=[] # initialising legend
x_max,y_max=0,0
for i in self.constraints:
if(i[0]!=0):
temp=i[2]/i[0]
if(temp>x_max):
x_max=temp
if(i[1]!=0):
temp=i[2]/i[1]
if(temp>y_max):
y_max=temp
for i in self.constraints: # plotting constraint lines
if(i[0]!=0 and i[1]!=0):
plt.plot([0,i[2]/i[0]],[i[2]/i[1],0],color=Color[j%5])
x=list(frange(0,i[2]/i[0]))
y1=list(map(lambda X:(i[2]-i[0]*X)/i[1],x))
y2=list(map(lambda X:0,x))
plt.fill_between(x,y1,y2,color=Color[j%5],alpha=0.7) # filling color
elif(i[0]!=0):
plt.axvline(i[2],color=Color[j%5])
x=list(frange(0,i[2]/i[0]))
y1=list(map(lambda X:y_max,x))
y2=list(map(lambda X:0,x))
plt.fill_between(x,y1,y2,color=Color[j%5],alpha=0.7) # filling color
else:
plt.axhline(i[2],color=Color[j%5])
x=list(frange(0,x_max))
y1=list(map(lambda X:i[2]/i[1],x))
y2=list(map(lambda X:0,x))
plt.fill_between(x,y1,y2,color=Color[j%5],alpha=0.7) # filling color
Legend.append(mpatches.Patch(color=Color[j%5],label="Constraint "+str(j+1))) # updating legend
j+=1
Legend.append(mpatches.Patch(color="w",label="The innermost region is the feasible region"))
Legend.append(mpatches.Patch(color="w",label="and its boundary points are the critical points"))
plt.legend(handles=Legend) # putting legend on graph
plt.show() # displaying graph
lps=LPsolver() # object creation
solution=lps.solve([3,2],[[2,1,18],[2,3,42],[3,1,24]],option="Simplex") # calling Simplex method
print(solution)