6

 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
import numpy as np
def f(x):
c = np.matrix('4.; 1.; -7.; 0.')
return np.dot(c[0:x.shape[0],0:].T, x)
c = np.matrix('4.; 1.; -7.; 0.')
n = c.shape[0]
A = np.matrix('2 1 3 0; 3 1 0 1')
b = np.matrix('24; 12')
m = b.shape[0]
min_el = 100000
def simplex():
B = A[0:m, 0:m]
p = np.dot(c[0:m, 0:1].T, B.I)
d = np.array([])
for i in range (m, n):
ai = A[0:, i:i+1]
d = np.append(d, np.dot(p, ai) - c[i:i+1, 0:1])
min_d = np.argmin(d)
if d[min_d] > 0:
return np.dot(B.I, b)
alpha = np.dot(B.I, A[0:, min_d:min_d +1])
betha = np.dot(B.I, b)
p = -1
for i in range(0, alpha.shape[0]):
if alpha[i][0] > 0 :
if betha[i][0]/alpha[i][0] < min_el:
min_el = betha[i][0]/alpha[i][0]
p = i
if p == -1:
return
x = np.zeros((n, 1))
addx = np.dot(B.I, b)
for i in range (0, addx.shape[0]):
x[i][0] = addx[i][0]
x[m + min_d][0] = min_el
x[min_d][0] = 0
ep = np.zeros(B.shape)
ep[p][p] = 1
return simplex()
x = simplex()
print 'x: ',x
print 'f(x): ',f(x)