Description
Here, we will maximize x and y where $f = x + 3y$ and x and y are restricted by the following system of linear inequalities with a MixedIntegerLinearProgram
object:
Sage Cell
We'll go over this line-by-line:
Line 1: We create a new MixedIntegerLinearProgram with the name LP. We then tell it to maximize the objective by setting maximization to true. If we wanted to minimize the objective, we would set it to false.
Line 2: We make a new variable named x in LP. x is actually an infinite array of variables, so all variables used in the program will just be different indices of x. An index must be an integer greater than or equal to 0, but the don't have to be consecutive. In the program we use x[1] and x[2] for simplicity's sake, but we could just as easily have used x[42] and x[9999999] and been fine.
Line 3: We set the objective we want to optimize. The objective is in normal Sage notation, except $x$ and $y$ have been replaced with x{1] and x[2], respectively. If the objective is unset, the program will automatically try to maximize the variable with the lowest index.
Lines 4-8: We set the constraints of the linear system of inequalities here. Again, we use normal Sage notation, but replace $x$ and $y$ with x[1] and x[2].
Lines 9-10: Here, we print the answer to our problem. LP.solve() gives us our optimized value of $f$ in $f = x + 3y$, while LP.get_values( x ) gives us all initialized values in the array x, from lowest to highest index. Since we only used two values, we are only returned two values.
Code
LP = MixedIntegerLinearProgram (maximization = true)
x = LP.new_variable()
LP.set_objective(x[1] + 3*x[2])
LP.add_constraint( 1.5 - 2*x[1] >= x[2] )
LP.add_constraint( 1 - x[1] >= x[2] )
LP.add_constraint( 1 - x[1] <= 2*x[2] )
LP.add_constraint( x[1] >= 0 )
LP.add_constraint( x[2] >= 0 )
print LP.solve()
print LP.get_values( x )Minimization
Here we will use the exact same objective and system of inequalities, except we wish to minimize $f = x + 3y$. This is accomplished simply by setting maximization to false when making a MixedIntegerLinearProgram object.
Code
LP = MixedIntegerLinearProgram (maximization = false)
x = LP.new_variable()
LP.set_objective(x[1] + 3*x[2])
LP.add_constraint( 1.5 - 2*x[1] >= x[2] )
LP.add_constraint( 1 - x[1] >= x[2] )
LP.add_constraint( 1 - x[1] <= 2*x[2] )
LP.add_constraint( x[1] >= 0 )
LP.add_constraint( x[2] >= 0 )
print LP.solve()
print LP.get_values( x )Options
Other Features of Linear Programming
Multiple Variable Letters
We can set different variable letters in the same object; this also means we'll have to call .get_values() multiple times, as it only works with one array of variables at a time.
Code
LP = MixedIntegerLinearProgram (maximization = true)
x = LP.new_variable()
y = LP.new_variable()
LP.set_objective(x[1] + 3*y[1])
LP.add_constraint( 1.5 - 2*x[1] >= y[1] )
LP.add_constraint( 1 - x[1] >= y[1] )
LP.add_constraint( 1 - x[1] <= 2*y[1] )
LP.add_constraint( x[1] >= 0 )
LP.add_constraint( y[1] >= 0 )
print LP.solve()
print LP.get_values( x )
print LP.get_values( y ).show()
Using .show will provide a human-readable summary of the object:
Code
LP = MixedIntegerLinearProgram (maximization = true)
x = LP.new_variable()
LP.set_objective(x[1] + 3*x[2])
LP.add_constraint( 1.5 - 2*x[1] >= x[2] )
LP.add_constraint( 1 - x[1] >= x[2] )
LP.add_constraint( 1 - x[1] <= 2*x[2] )
LP.add_constraint( x[1] >= 0 )
LP.add_constraint( x[2] >= 0 )
LP.show()
print LP.solve()
print LP.get_values( x )Setting Nonnegativity
If we set nonnegative = true when declaring a new array of variables, we don't need a >= 0 constraint for the set.
Code
LP = MixedIntegerLinearProgram (maximization = true)
x = LP.new_variable(nonnegative = true)
LP.set_objective(x[1] + 3*x[2])
LP.add_constraint( 1.5 - 2*x[1] >= x[2] )
LP.add_constraint( 1 - x[1] >= x[2] )
LP.add_constraint( 1 - x[1] <= 2*x[2] )
print LP.solve()
print LP.get_values( x )Integer-only Solutions
We can tell our program that specific variables may only be integers in the optimization, using integer=true when declaring a new variable:
Code
LP = MixedIntegerLinearProgram (maximization = true)
x = LP.new_variable(nonnegative = true, integer=true)
LP.set_objective(x[1] + 3*x[2])
LP.add_constraint( 1.5 - 2*x[1] >= x[2] )
LP.add_constraint( 1 - x[1] >= x[2] )
LP.add_constraint( 1 - x[1] <= 2*x[2] )
print LP.solve()
print LP.get_values( x )Tags
Primary Tags:
Secondary Tags:
A list of possible tags can be found at The WeBWorK Open Problem Library. For linear algebra tags see the Curated Courses Project.
Related Cells
Any related cells go here. Provide a link to the page containing the information about the cell.
Attribute
Permalink:
Author:
Date: 09 Mar 2019 15:21
Submitted by: Zane Corbiere