GitHub Repository: DataScienceUWL/DS775
Path: blob/main/Lessons/Lesson 01 - LP 1/Self_Assess_Solns_01.ipynb
⁸⁷¹ views

Kernel: Python 3 (system-wide)

Lesson 01 - Self-Assessment Solutions

Self Assessment: LP Assumptions

(a) Additivity is violated by the term $x_1 x_2$ in the objective function and proportionality is violated by the term $x^2_2$ in the third constraint.

(b) The $+3$ in the objective function violates the proportionality assumption and the constraints of $x_1 = 1,2,3, \ldots, x_2 = 1,2,3, \ldots$ violate the divisibility assumption.

(c) $0.25 x + 1$ as the RHS of constraint 2 violated the proportionality assumption and the certainty assumption is violated because the exact value of $a_2$ is not known.

Self Assessment: Paper and Pencil Method

The maximum value is $Z^* = 210$ and occurs when $x_1^* = 3$ and $x_2^* = 9$ .

Self Assessment: Graphical Method #1

From the graphical method observe that the two binding contraints are $3 x_1 + 2 x_2 \leq 2400$ and $2x_1 \leq 1200.$ Since the constraints are binding we know that $3 x_1 + 2x_2 = 2400$ and $2x_1 = 1200.$ From the second equation we know $x_1 = 600$ . Substitute $x_1 = 600$ into the first equation to get $1800 + 2x_2 = 2400$ which yields $x_2 = 300.$ So the optimal value is $Z^* = 3600$ and it occurs at $x_1^* = 600, x_2^*=300.$

Hover over the CPF solutions in Desmos to get the coordinates:

In [3]:

# execute this cell for Desmos Graph
from IPython.display import IFrame
IFrame('https://www.desmos.com/calculator/mldmglotw3', width=1000, height = 600)

Out[3]:

Self Assessment: Graphical Method #2

(a) As in the Wyndor Glass Co. problem, we want to find the optimal levels of two activities that compete for limited resources. Let $x_1$ and $x_2$ be the fraction purchased of the partnership in the first and second friends venture respectively.

(b) Maximize $P = 9000 x_1 + 9000 x_2$

subject to

$x_1 \leq 1$

$x_2 \leq 1$

$10000 x_1 + 8000 x_2 \leq 12000$

$400 x_1 + 500 x_2 \leq 600$

$x_1, x_2 \geq 0$

In [4]:

# execute this cell for Desmos Graph
from IPython.display import IFrame
IFrame('https://www.desmos.com/calculator/s4llmtb8jw', width=1000, height = 600)

Out[4]:

Self Assessment: Graphical Method #3

There are infinitely many optimal solutions to this problem. $(x_1^*, x_2^*) = (15,15), (2.5,35.8\bar{3})$ and all the points on the line connecting these two points, $Z^* = 12000$ .

In [5]:

# execute this cell for Desmos Graph
from IPython.display import IFrame
IFrame('https://www.desmos.com/calculator/givnk8crtg', width=1000, height = 600)

Out[5]:

Self Assessment: Graphical Method #4

After setting up in Desmos check the value of Z at the CPFs which are the vertices of the unbounded, U-shaped region at the top of the graph.

In [6]:

# execute this cell for Desmos Graph
from IPython.display import IFrame
IFrame('https://www.desmos.com/calculator/cd4vcedr8z', width=1000, height = 600)

Out[6]:

Self-Assessment: Unbounded Region

There is no maximum value since we can increase the value of $x_1$ to make it as large as we want so that the value of $Z$ grows unboundedly. There is a minimum value of $Z^* = 4$ at $(x_1^*, x_2^*) = (0,2)$ .
There are multiple ways to do this. For example change to $c_1 = -2, c_2 = 3$ . Now we get a maximum value of $Z^* = 15$ at $(x_1^*, x_2^*) = (0,5)$ but there is no minimum value.
Any pair of $c_1,c_2$ that satisfy $c_1 < 0, c_2 < 0,$ and $c_1 = c_2,$ e.g. $c_1 = c_2 = -2,$ will make it so that $Z$ has infinitely many maxima (with negative values) along the line $x_1 + x_2 = 2$ at the left edge of the feasible region.

Self-Assessment: Specifying Bounds

In [7]:

from pyomo.environ import *

# Concrete Model
model = ConcreteModel(name="Wyndor")

# Decision Variables
model.doors = Var(domain=Reals, bounds=(0,4))
model.windows = Var(domain=Reals, bounds = (0,6))

# Objective
model.profit = Objective(expr=3.0 * model.doors + 5.0 * model.windows,
                         sense=maximize)

# Constraints
model.Plant3 = Constraint(expr=3.0 * model.doors + 2.0 * model.windows <= 18)

# Solve
solver = SolverFactory('glpk')
solver.solve(model)

#display(model)

#  display solution
print(f"Maximum Profit = ${1000*model.profit():,.2f}")
print(f"Batches of Doors = {model.doors():.1f}")
print(f"Batches of Windows = {model.windows():.1f}")

Out[7]:

Maximum Profit = $36,000.00
Batches of Doors = 2.0
Batches of Windows = 6.0

Self-Assessment: Formulate and Solve #1

(a) Minimize $C = 8S + 4P$

subject to

$\begin{darray}{rcl} 5S + 15P &\geq& 50 \\ 20S + 5P &\geq& 40 \\ 15S + 2P &\leq& 60 \\ S,P &\geq& 0 \end{darray}$

In [8]:

# Unfold to see the Pyomo solution with individual decision variables
from pyomo.environ import *

# Concrete Model
model = ConcreteModel(name="Ralph")

# Decision Variables
model.steak = Var(domain=Reals)
model.potatoes = Var(domain=Reals)

# Objective
model.cost = Objective(expr=8.0 * model.steak + 4.0 * model.potatoes,
                       sense=minimize)

# Constraints
model.carbs = Constraint(expr=5.0 * model.steak + 15.0 * model.potatoes >= 50)
model.protein = Constraint(
    expr=20.0 * model.steak + 5.0 * model.potatoes >= 40)
model.fat = Constraint(expr=15 * model.steak + 2.0 * model.potatoes <= 60)
model.sgeq0 = Constraint(expr=model.steak >= 0)
model.pgeq0 = Constraint(expr=model.potatoes >= 0)

# Solve
solver = SolverFactory('glpk')
solver.solve(model)

# display solution
print(f"Minimum Cost = ${model.cost():,.2f}")
print(f"Servings of Steak = {model.steak():.1f}")
print(f"Servings of Potatoes = {model.potatoes():.1f}")

Out[8]:

Minimum Cost = $21.82
Servings of Steak = 1.3
Servings of Potatoes = 2.9

Self-Assessment: Formulate and Solve #2

(a) The LP model:

The hard part of this model, for most students, seems to be the constraint that the number of full time workers has to be at least twice the number of part time workers:

full time $\geq$ 2 * part time

full time - 2 * part time $\geq$ 0

(b) The Pyomo solution is in the cell below this one.

The objective function minimum cost is $4,106.67 if it were possible to have a fractional number of workers per shift. Of course you can't have a fractional number of workers per shift, but you can either round these values to integers for an approximate solution or you can tell the solver to use only integer values which actually makes the problem into a harder problem called an integer programming problem. If you round the numbers of consultants to the nearest integer you should find a total cost of $4280.

(c) Set an integer constraint (domain=NonNegativeIntegers) on the decision variable cells and solve using Pyomo to get a total cost of $4160. Rounding fractional solutions yielded a less optimal answer than using integer programming in this case. (In general don't use integer variables unless instructed to do so. We will see more about this in Lesson 6.)

In [9]:

# first, the Pyomo solution to 3.4-10 for real number decision variables

from pyomo.environ import *

# Concret Model
model = ConcreteModel(name = "Staffing")

# Decision Variables
model.x = Var( ['xf1','xf2','xf3','xp1','xp2','xp3','xp4'], 
              domain = NonNegativeReals)

# Objective 
model.obj = Objective( expr = 40 * 8 * (model.x['xf1'] + model.x['xf2'] + model.x['xf3']) +
                      30 * 4 * (model.x['xp1'] + model.x['xp2'] + model.x['xp3'] + 
                            model.x['xp4']), sense = minimize)

# Constraints
model.Constraint1 = Constraint( expr = model.x['xf1'] + model.x['xp1'] >= 4 )
model.Constraint2 = Constraint( expr = model.x['xf1'] + model.x['xf2'] + 
                               model.x['xp2'] >= 8 )
model.Constraint3 = Constraint( expr = model.x['xf2'] + model.x['xf3'] + 
                               model.x['xp3'] >= 10 )
model.Constraint4 = Constraint( expr = model.x['xf3'] + model.x['xp4'] >= 6 )
model.Constraint5 = Constraint( expr = model.x['xf1'] - 2*model.x['xp1'] >= 0 )
model.Constraint6 = Constraint( expr = model.x['xf1'] + model.x['xf2'] -
                               2*model.x['xp2'] >= 0 )
model.Constraint7 = Constraint( expr = model.x['xf2'] + model.x['xf3'] - 
                               2*model.x['xp3'] >= 0 )
model.Constraint8 = Constraint( expr = model.x['xf3'] - 2*model.x['xp4'] >= 0 )
                      
# Solve
solver = SolverFactory('glpk')
solver.solve(model)

# remove the comment symbol to see the pyomo display of results
# display(model)

# print a shorter summary of relevant results
print(f"Total Cost = ${model.obj():,.2f}")
print(f"Number of FT, 8 am - 4 pm: {model.x['xf1']():.2f}")
print(f"Number of FT, noon - 8 pm: {model.x['xf2']():.2f}")
print(f"Number of FT, 4 pm -12 am: {model.x['xf3']():.2f}")
print(f"Number of PT, 8 am -12 pm: {model.x['xp1']():.2f}")
print(f"Number of PT, noon - 4 pm: {model.x['xp2']():.2f}")
print(f"Number of PT, 4 pm - 8 pm: {model.x['xp3']():.2f}")
print(f"Number of PT, 8 pm -12 am: {model.x['xp4']():.2f}")

Out[9]:

Total Cost = $4,106.67
Number of FT, 8 am - 4 pm: 2.67
Number of FT, noon - 8 pm: 2.67
Number of FT, 4 pm -12 am: 4.00
Number of PT, 8 am -12 pm: 1.33
Number of PT, noon - 4 pm: 2.67
Number of PT, 4 pm - 8 pm: 3.33
Number of PT, 8 pm -12 am: 2.00

In [8]:

# now the solution to 3.4-10 for decison variables restricted to integers

from pyomo.environ import *

# Concret Model
model = ConcreteModel(name = "Staffing")

# Decision Variables
model.x = Var( ['xf1','xf2','xf3','xp1','xp2','xp3','xp4'], 
              domain = NonNegativeIntegers)

# Objective 
model.obj = Objective( expr = 40 * 8 * (model.x['xf1'] + model.x['xf2'] + model.x['xf3']) +
                      30 * 4 * (model.x['xp1'] + model.x['xp2'] + model.x['xp3'] + 
                            model.x['xp4']), sense = minimize)

# Constraints
model.Constraint1 = Constraint( expr = model.x['xf1'] + model.x['xp1'] >= 4 )
model.Constraint2 = Constraint( expr = model.x['xf1'] + model.x['xf2'] + 
                               model.x['xp2'] >= 8 )
model.Constraint3 = Constraint( expr = model.x['xf2'] + model.x['xf3'] + 
                               model.x['xp3'] >= 10 )
model.Constraint4 = Constraint( expr = model.x['xf3'] + model.x['xp4'] >= 6 )
model.Constraint5 = Constraint( expr = model.x['xf1'] - 2*model.x['xp1'] >= 0 )
model.Constraint6 = Constraint( expr = model.x['xf1'] + model.x['xf2'] -
                               2*model.x['xp2'] >= 0 )
model.Constraint7 = Constraint( expr = model.x['xf2'] + model.x['xf3'] - 
                               2*model.x['xp3'] >= 0 )
model.Constraint8 = Constraint( expr = model.x['xf3'] - 2*model.x['xp4'] >= 0 )
                      
# Solve
solver = SolverFactory('glpk')
solver.solve(model)

# remove the comment symbol to see the pyomo display of results
# display(model)

# print a shorter summary of relevant results
print(f"Total Cost = ${model.obj():,.2f}")
print(f"Number of FT, 8 am - 4 pm: {model.x['xf1']():.0f}")
print(f"Number of FT, noon - 8 pm: {model.x['xf2']():.0f}")
print(f"Number of FT, 4 pm -12 am: {model.x['xf3']():.0f}")
print(f"Number of PT, 8 am -12 pm: {model.x['xp1']():.0f}")
print(f"Number of PT, noon - 4 pm: {model.x['xp2']():.0f}")
print(f"Number of PT, 4 pm - 8 pm: {model.x['xp3']():.0f}")
print(f"Number of PT, 8 pm -12 am: {model.x['xp4']():.0f}")

Out[8]:

Total Cost = $4,160.00
Number of FT, 8 am - 4 pm: 3
Number of FT, noon - 8 pm: 3
Number of FT, 4 pm -12 am: 4
Number of PT, 8 am -12 pm: 1
Number of PT, noon - 4 pm: 2
Number of PT, 4 pm - 8 pm: 3
Number of PT, 8 pm -12 am: 2

Textbook Problem 3.5-6 (a,e) Solution

(a) Model formulation:

(e) Optimal solution using the simplex method in Pyomo is in the following cell.

Self-Assessment: Formulate and Solve #3