P1
Express the following problem as a linear program. Given an m×nmatrix A and a vector b of length m, find a vector x such that |┤|Ax-b|┤|_1 is minimized. In other words, find x_1…x_nsuch that ∑_(i=1)^m|b_(i )-∑_(j=1)^n a_ij x_j | is minimized.

# Use linear programming to accomplish the following task.
# Given an mxn matrix A and a vector b of length m,
# find a vector x such that |Ax-b|_1 is minimized.
# In other words, find x such that
# sum( abs(b[i] - (Ax)[i]) for i in range(m)) is minimized
# (Hint: you will want to introduce new variables for both
# the positive and negative differences between b[i] (Ax)[i]).
#
# For this exercise, we will use pymprog.
#
# Please read the documentation before attempting the exercise.
# Some key points to note are
#
# 1. When declare a set of variable for your linear program as in
# x = var([0,1,2])
# you get back a dictionary with [0,1,2] as the keys (they don't
# even have to be integers)
# and
# unique pymprog.variable as the values.
# 2. Thus, when you specify the objective function as in
#
# maximize( 1.0 * x[0] - 2.0 * x[1] )
#
# or specify a set of constraints as in
#
# st( [ x[0] <= 1, x[2] <= 3])
#
# the expressions are interpretted as a computer algebra system
# would (think Mathematica) and added to the model.
#3. By default variables are constrained to be nonnegative.
# You can remove this restriction by the statment
# None <= x[0]
#
#4. Pymprog doesn't like numpy's types, so you have to cast them
# back to floats via
#
# float(c[1])
#
# for example.
#
# Here is a super-simple example of a program that uses pymprog
#
# c = numpy.array([1.0, -2.0], dtype=float)
# b = numpy.array([1.0, 3.0], dtype=float)
#
# beginModel('basic')
# verbose(False)

# x = var([0,1,2])

# maximize( float(c[0]) * x[0] + float(c[1]) * x[1] )

# st( [ x[0] <= float(b[0]), x[2] <= float(b[1]) ])

# solve()

# endModel() #Good habit: do away with the problem

# print numpy.array([x[i].primal for i in [0,1,2]])

from pymprog import *
import numpy as np

def labsdev(A,b):
"""Input: A numpy array A with shape = (m,n) and a numpy array b.
   Output: A numpy array x that minimizes |b - Ax|_1.
"""

(m,n) = A.shape

def main():
A = np.array([[1,0],
            [0,1],
            [0,1]],dtype=float)
b = np.array([1, 2, 1],dtype=float)

x = labsdev(A,b)

Ax = np.dot(A,x)

r = b - Ax

assert (sum(abs(r[i]) for i in range(3)) == 1.0)

if __name__ == '__main__':
main()

P2
Let A=(a_ij)for 1≤i≤mand 1≤j≤n be a matrix with m rows and n columns. Such a matrix defines a two-person game as follows. Two players, Row and Column play a game where Row selects a row i and Column selects a column j. If a_ij>0 Row receives a payoff amount of a_ij from Column. If a_(ij )<0, Row pays an amount of -a_ij to Column. The payoff matrix A is known to both players.

Suppose Row picks the i-th row with probability p_iand announces this vector p. Knowing this vector, Column will choose column j that minimizes Row’s expected payout. Thus, the expected payout is z = (min)┬j ∑_(i=1)^m p_i a_ij. Naturally, Row then will want to choose the vector (p_1,…,p_m) so as to maximize this quantity. Express Row’s problem as a linear program. (Of course p_1,…p_m≥0 and ∑_(i=1)^m p_i = 1.)

#Let A be a matrix with m rows and n columns. Such a matrix defines
#a two-person game as follows. Two players, Row and Column play a
#game where Row selects a row i and Column selects a column j.
#If A[i][j] >0 Row receives a payoff amount of A[i][j] . If A[i][j] <0,
#Row pays an amount of -A[i][j] to Column. The payoff matrix A is
#known to both players.
#
#Suppose Row picks the ith row with probability p[i] and announces this
#vector p. Knowing this vector, Column will choose column j that
#minimizes Row's expected payout. Thus, the expected payout is
#z = min_j \sum p[i]*A[i][j]. Naturally, Row then will want to
#choose the vector (p1,,pm) so as to maximize this quantity.
#Express Row's problem as a linear program. Of course, p[i] >=0
#and \sum_i p[i] = 1.
#
#
# For this exercise, we will use pymprog. Documentation
# can be found here
# http://pymprog.sourceforge.net/tutorial.html#a-dive-in-example
#
# Please read the documentation before attempting the exercise.
# Some key points to note are
#
# 1. When declare a set of variable for your linear program as in
# x = var([0,1,2])
# you get back a dictionary with [0,1,2] as the keys (they don't
# even have to be integers)
# and
# unique pymprog.variable as the values.
# 2. Thus, when you specify the objective function as in
#
# maximize( 1.0 * x[0] - 2.0 * x[1] )
#
# or specify a set of constraints as in
#
# st( [ x[0] <= 1, x[2] <= 3])
#
# the expressions are interpretted as a computer algebra system
# would (think Mathematica) and added to the model.
#3. By default variables are constrained to be nonnegative.
# You can remove this restriction by the statment
# None <= x[0]
#
#4. Pymprog doesn't like numpy's types, so you have to cast them
# back to floats via
#
# float(c[1])
#
# for example.
#
# Here is a super-simple example
#
# c = numpy.array([1.0, -2.0], dtype=float)
# b = numpy.array([1.0, 3.0], dtype=float)
#
# beginModel('basic')
# verbose(False)

# x = var([0,1,2])

# maximize( float(c[0]) * x[0] + float(c[1]) * x[1] )

# st( [ x[0] <= float(b[0]), x[2] <= float(b[1]) ])

# solve()

# endModel() #Good habit: do away with the problem

# print numpy.array([x[i].primal for i in [0,1,2]])

from pymprog import *
import numpy as np

def rowStrategy(A):
(m,n) = A.shape

def main():
A = np.array([[1,0],
            [0,1]],dtype=float)

x = rowStrategy(A)
ans = np.array([0.5,0.5], dtype=float)
assert(np.allclose(x,ans))

assert ( min(x.dot(A)) + 1.0e-8 > 0.5)

if __name__ == '__main__':
main()

P1 Express the following problem as a linear program. Given an m×...