1936-4b.sagews

4b

Finding the equation that forms between two lines: Insert x values in the X list and their associated y values at the same index in the Y list. They must be in either clockwise or counterclockwise order.

X = [1,2,4,6,5,1]
Y = [1,5,6,3,2,1]
for i in range(5):
    m = (Y[i+1]-Y[i])/(X[i+1]-X[i])
    b = Y[i]-m*X[i]
    print "Equation",i+1,": For (",X[i],",",Y[i],") and (",X[i+1],",",Y[i+1],"): ","y -",m,"x =",b

Equation 1 : For ( 1 , 1 ) and ( 2 , 5 ): y - 4 x = -3 Equation 2 : For ( 2 , 5 ) and ( 4 , 6 ): y - 1/2 x = 4 Equation 3 : For ( 4 , 6 ) and ( 6 , 3 ): y - -3/2 x = 12 Equation 4 : For ( 6 , 3 ) and ( 5 , 2 ): y - 1 x = -3 Equation 5 : For ( 5 , 2 ) and ( 1 , 1 ): y - 1/4 x = 3/4

Finding Inequalities: Since the origin is not in conv(P) we can use it to find the correct direction of the inequality sign for each equation creating conv(P). Equations 2,3 and 4 must include (0,0) in their inequality and equations 1 and 5 must exclude it. So we will use the opposite sign that appears in the algorithm below for equations 1 and 5, and the same sign for equations 2,3 and 4.

For example with equation 1: (0)-4(0) ? -3 → 0 ? -3. Equation 1 must exlude (0,0) so we want the ? to make that statement incorrect (this would imply "the shading" would be on the opposite side that (0,0) is on. So we see 0 > -3  which means the sign we will use in this equation is ≤. See Problem 4 written sheet for final linear equalities that define conv(P).

bValues = [-3,4,12,-3,3/4]
for i in range(5):
    if (0 < bValues[i]):
        print "Equation",i+1,": 0 <",bValues[i]
    else:
        print "Equation",i+1,": 0 >",bValues[i]

Equation 1 : 0 > -3 Equation 2 : 0 < 4 Equation 3 : 0 < 12 Equation 4 : 0 > -3 Equation 5 : 0 < 3/4

4c

Finding an objective function for each extreme point which makes it the unique optimal solution of some linear program.

We can find a line that goes through a point vj with a normal vector of vj as well. Below is using the general method for the points of our bounded polyhedron. See the written sheet for the general form for 4d.

x = [1,2,4,6,5,1,2,4,6]
y = [1,5,6,3,2,1,5,6,3]
#for i in range(5):        
for i in range(5):
    print "At point: (",x[i],",",y[i],")"
    for j in range(5):
        if not (x[i]-x[i+j] == 0):        
             c =  (y[i]-y[i+j])/(x[i]-x[i+j])
             if (c <0):    
                print "For point (",x[i+j],",",y[i+j],"): ",c,"< m/d"
             else:
                print "For point (",x[i+j],",",y[i+j],"): ",c,"> m/d"

At point: ( 1 , 1 ) For point ( 2 , 5 ): 4 > m/d For point ( 4 , 6 ): 5/3 > m/d For point ( 6 , 3 ): 2/5 > m/d For point ( 5 , 2 ): 1/4 > m/d At point: ( 2 , 5 ) For point ( 4 , 6 ): 1/2 > m/d For point ( 6 , 3 ): -1/2 < m/d For point ( 5 , 2 ): -1 < m/d For point ( 1 , 1 ): 4 > m/d At point: ( 4 , 6 ) For point ( 6 , 3 ): -3/2 < m/d For point ( 5 , 2 ): -4 < m/d For point ( 1 , 1 ): 5/3 > m/d For point ( 2 , 5 ): 1/2 > m/d At point: ( 6 , 3 ) For point ( 5 , 2 ): 1 > m/d For point ( 1 , 1 ): 2/5 > m/d For point ( 2 , 5 ): -1/2 < m/d For point ( 4 , 6 ): -3/2 < m/d At point: ( 5 , 2 ) For point ( 1 , 1 ): 1/4 > m/d For point ( 2 , 5 ): -1 < m/d For point ( 4 , 6 ): -4 < m/d For point ( 6 , 3 ): 1 > m/d

So:

For point (1,1): m < 1/4

For point (2,5): -1/2 < m/d < 1/2

For point (4,6): -3/2 < m/d< 1/2

For point (6,3): -1/2 < m /d< 2/5

For point (5,2): -1 < m /d< 1/4

# For (1,1)
A = Matrix([[-4,1],[1/4,-1]])
b = vector([1,1])
print "For (1,1):", A*b

# For (2,5)
A = Matrix([[-4,1],[(-1/2),1]])
b = vector([2,5])
print "For (2,5):", A*b

# For (4,6)
A = Matrix([[-1/2,1],[3/2,1]])
b = vector([4,6])
print "For (4,6):", A*b

# For (6,3)
A = Matrix([[3/2,1],[1,-1]])
b = vector([6,3])
print "For (6,3):", A*b

# For (5,2)
A = Matrix([[1,-1],[1/4,-1]])
b = vector([5,2])
print "For (5,2):", A*b

For (1,1): (-3, -3/4) For (2,5): (-3, 4) For (4,6): (4, 12) For (6,3): (12, 3) For (5,2): (3, -3/4)

x = [1,2,4,6,5]
y = [1,5,6,3,2]

# For (1,1)
print "At (1,1). Values for (-3)x-(3/4)y:"
for i in range(5):    
 print "     (",x[i],",",y[i],"): ",(-3/4)*y[i]-(3)*x[i]

# For (2,5)
print "At (2,5). Values for 3x+4y:"
for i in range(5):    
 print "     (",x[i],",",y[i],"): ",4*y[i]-(3)*x[i]

# For (4,6)
print "At (4,6). Values for 4x+12y:"
for i in range(5):    
 print "     (",x[i],",",y[i],"): ",12*y[i]+4*x[i]

# For (6,3)
print "At (6,3). Values for 12x+3y:"
for i in range(5):    
 print "     (",x[i],",",y[i],"): ",3*y[i]+12*x[i]

# For (5,2)
print "At (5,2). Values for 3x-(3/4)y" 
for i in range(5):    
 print "     (",x[i],",",y[i],"): ",(-3/4)*y[i]+(3)*x[i]

At (1,1). Values for (-3)x-(3/4)y: ( 1 , 1 ): -15/4 ( 2 , 5 ): -39/4 ( 4 , 6 ): -33/2 ( 6 , 3 ): -81/4 ( 5 , 2 ): -33/2 At (2,5). Values for 3x+4y: ( 1 , 1 ): 1 ( 2 , 5 ): 14 ( 4 , 6 ): 12 ( 6 , 3 ): -6 ( 5 , 2 ): -7 At (4,6). Values for 4x+12y: ( 1 , 1 ): 16 ( 2 , 5 ): 68 ( 4 , 6 ): 88 ( 6 , 3 ): 60 ( 5 , 2 ): 44 At (6,3). Values for 12x+3y: ( 1 , 1 ): 15 ( 2 , 5 ): 39 ( 4 , 6 ): 66 ( 6 , 3 ): 81 ( 5 , 2 ): 66 At (5,2). Values for 3x-(3/4)y ( 1 , 1 ): 9/4 ( 2 , 5 ): 9/4 ( 4 , 6 ): 15/2 ( 6 , 3 ): 63/4 ( 5 , 2 ): 27/2