2024-08-28-124823.ipynb

Kernel: Python 3 (system-wide)

# EXECUTE FIRST

# computational imports
from pyomo.environ import *

# plotting imports
import matplotlib.pyplot as plt
import seaborn as sns
sns.set_style("darkgrid")

# display imports# computational imports
from pyomo.environ import *
from IPython.display import display, IFrame
from IPython.core.display import HTML

# for playing videos, customize height and width if desired
# keep a 16:9 ratio, e.g. 960 by 540, or 1280 by 720
def play_video(vid_name, w=640, h=360):
    vid_path = "https://media.uwex.edu/content/ds/ds775_r19/" + vid_name + "/index.html"
    print(vid_path)
    hlink = '<a href = ' + vid_path + ' target = """_blank""">Open video in new tab</a>'
    display(IFrame(vid_path, width=w, height=h))
    display(HTML(hlink))

Lesson 01: Linear Programming and Pyomo

Introduction and Set-Up

Course Overview and some Optimization Basics

In the video below we'll preview some of the course content, explain why we chose this textbook, discuss why we're using Python, and introduce some optimization terminology.

# Execute to play video
play_video("ds775_course-overview")

https://media.uwex.edu/content/ds/ds775_r19/ds775_course-overview/index.html

Introduction to CoCalc

The video below demonstrates how we will use CoCalc in this class. If you got this notebook without signing up for CoCalc (possible through github) then visit Canvas to find and follow the "CoCalc and Jupyter Instructions" handout before viewing the video. Even if you setup your own Jupyter environment at home, you'll still need to submit your assignments via CoCalc.

In CoCalc you can use this notebook in either the CoCalc interface, the Jupyter Classic View, or in Jupyter Lab. Jupyter Lab is our personal favorite, but the CoCalc interface has automatic backups and other features. In the CoCalc interface always be sure to explicitly save your file(s) before exiting - press the green "Save" button if it isn't light green.

# Execute to play video
play_video("ds775_cocalc-overview")

https://media.uwex.edu/content/ds/ds775_r19/ds775_cocalc-overview/index.html

Contents of each Lesson Directory

The lesson structure and folder contents is pretty similar for all the lessons. We'll show this one as an example, so you can know what to expect.

Here is a partial tree view of the lesson directory contents:,

├── Lesson_01.ipynb
├── Overview_01.ipynb
├── Self_Assess_Solns_01.ipynb
├── extras
│   ├── Python Refresher - Functions.ipynb
│   └── Python Refresher - Loops.ipynb
├── images
└── scripts

Descriptions of the files:

• Lesson_01.ipynb - the main lesson file with presentations and self-assessment exercises.

• Overview_01.ipynb - contains a list of lesson topics, objectives, and supplemental materials if any are available.

• Self_Assess_Solns_01.ipynb - solutions to the self-assessment exercises in the Lesson notebook.

• extras - if there are supplemental materials for the week they are contained in this directory.

• images - directory containing image files used in the notebook.

• scripts - directory contains code files that aren't important for the course content, but may be used to produce animations or other tools.

Our view of the provided materials

It's our intention that you should lightly read the corresponding sections in the textbook (focus on applications and big picture, don't pay attention to details of algorithms or Excel instructions). After reading the textbook work your way through the lesson notebook. If you have time, go through each example and make sure you understand the implementation and solution. Work Self-Assessment problems to solidify your understanding (we don't collect these). Finally, start the homework and return to the lesson as needed.

What to do for homework

Each Lesson has an accompanying homework notebook. You should use the notebook to work out the solutions after which you'll enter the solutions in a Canvas quiz. You get two attempts at each quiz (but you'll have to re-enter all the answers for the second attempt - that's a Canvas issue). You should submit:

• Your lesson notebook in CoCalc. You don't have to do anything to submit, just make sure the completed notebook (.ipynb file) is in the original folder in CoCalc by the due date. Make sure the notebook is clearly named, especially if there are multiple notebooks in the folder.

• Complete the Canvas quiz by using your answers in the notebook. You're allowed two attempts at the quiz prior to the due date.

We've seen students mostly use two different approaches to homework:

1. Work completely and carefully through the lesson and Self-Assessment problems before beginning the homework. Your goal is to have a solid understanding of the concepts and code before beginning the homework. This approach may be too time-consuming for some students.

2. Loosely work through the lesson notebook before beginning the homework. Your goal is developing awareness of the content and code before beginning the homework. After developing a loose understanding of the lesson then start the homework and refer to the lesson to fill in details as needed. This approach may be more time efficient for some students, but it's easy to fall into the trap of trying to copy and tweak code from the lesson without really understanding the code in the first place. Tweaking code without really understanding it is inefficient and frustrating.

What is a Linear Program?

The material in this chapter assumes that you're familiar with graphing lines, graphing inequalities, and solving linear equations. If you need to refresh your memory of these topics there are many sources on the internet. All of these topics may be found in this free Algebra course at Khan Academy.

Before progressing through the remainder of this notebook, you really should have read Chapter 3 so that you know the basics of a linear program.

# execute this cell for video
play_video("ds775_lesson1_what-is-linear-programming")

https://media.uwex.edu/content/ds/ds775_r19/ds775_lesson1_what-is-linear-programming/index.html

IMPORTANT Correction to Video

In the video we say that constant terms do not violate the proportionality assumption, but the book disagrees with us. According to the book $Z = 3x + 2y$ is OK, but $Z = 3x + 2y + 5$ is not OK. This is a subtle, and unimportant, difference. For the purposes of the homework we will say that **constants violate the proportionality assumption.**

Self Assessment: LP Assumptions

Read Hillier 3.3 and answer the questions below. Solutions are found in the Self_Assessment_Solutions notebook.

For parts (a) - (c) below, state which, if any, linear programming model assumptions are violated and why.

(a) Maximize $Z = 2x_1 + 7x_2 + x_1 x_2,$

subject to

$\begin{array}{rcrcr} 5 x_1 & + & 3 x_2 & \leq & 30 \\ x_1 & + & 3 x_2 & \leq & 40 \\ 12 x_1 & + & x^2_2 & \leq & 50 \end{array}$

and $x_1 \geq 0, x_2 \geq 0.$

(b) Minimize $Z = x_1 + 2x_2 + 3,$

subject to

$\begin{array}{rcrcr} & + & 5 x_2 & \geq & 8 \\ x_1 & + & & \geq & 4 \\ x_1 & + & x_2 & \geq & 10 \end{array}$

and $x_1 = 1,2,3, \ldots, x_2 = 1,2,3, \ldots$

(c) Maximize $Z = 0.5 x + 0.3 y$

subject to

$\begin{array}{rcrcr} 2x & - & 0.1 y & \leq & 2.5 \\ 0.25 x & + & 1 & \leq & 5.5 \\ 3 x & + & a_2 y & \leq & 7.9 \end{array}$

$x \geq 0, y \geq 0,$

$2 \leq a_2 \leq 3$

Note: We don't collect or grade the Self-Assessment questions (even though some of them have language that suggest you should submit something). Do not submit the self-assessments. The Self-Assessment solutions are included with each lesson in a separate Jupyter notebook.

Graphical Solutions

The next video explains some basic ideas like feasible region and corner feasible point. It's also pretty easy to get same information from reading the textbook, but watch the video below if you think it might be useful for you. The video immediately following this one also mentions some of the same ideas.

# execute this cell for video
play_video("ds775_lesson1_linear-programming-basics")

https://media.uwex.edu/content/ds/ds775_r19/ds775_lesson1_linear-programming-basics/index.html

Paper Example (video)

Get "old school" and solve a graphical example with paper and pencil along with some graphing and algebra. This video talks you through an example. Doing this yourself will help your understanding (and appreciation) of how optimal solutions are found graphically using various software applications.

# execute this cell for video
play_video("ds775_lesson1-graphical-by-hand")

https://media.uwex.edu/content/ds/ds775_r19/ds775_lesson1-graphical-by-hand/index.html

Self Assessment: Paper and Pencil Method

Textbook Problem 3.1-6. Use paper and pencil to solve this problem using the graphical method.

Maximize $Z = 10x_1 + 20x_2,$

subject to

$\begin{array}{rcrcr} -x_1 & + & 2x_2 & \leq & 15 \\ x_1 & + & x_2 & \leq & 12 \\ 5x_1 & + & 3x_2 & \leq & 45 \end{array}$

and $x_1 \geq 0, x_2 \geq 0.$

Software for Graphical Solutions

Desmos is a step up from "paper and pencil", but is still pretty hands-on. While there are easier tools to use (e.g. PHPSimplex), we prefer using Desmos because it helps to understand the relationship between the equations, the feasible solutions, and the optimal solution.

# execute this cell for video
play_video("ds775_lesson1-graphical-example-desmos")

https://media.uwex.edu/content/ds/ds775_r19/ds775_lesson1-graphical-example-desmos/index.html

Self Assessment: Graphical Method #1

Textbook Problem 3.1-9. The Primo Insurance Company is introducing two new product lines: special risk insurance and mortgages. The expected profit is $5 per unit on special risk insurance and $2 per unit on mortgages. Management wishes to establish sales quotas for the new product lines to maximize total expected profit. The work requirements are as follows:

(a) Formulate a linear programming model for this problem.

(b) Use Desmos to solve this model using the graphical method. Paste screenshots of your solution into your homework file.

(c) Verify the exact value of your optimal solution from (b) by solving algebraically for the simultaneous solution of the relevant two equations

Self Assessment: Graphical Method #2

Textbook Problem 3.2-3. This is your lucky day. You have just won a $20,000 prize. You are setting aside $8,000 for taxes and partying expenses, but you have decided to invest the other $12,000. Upon hearing this news, two different friends have offered you an opportunity to become a partner in two different entrepreneurial ventures, one planned by each friend. In both cases, this investment would involve expending some of your time next summer as well as putting up cash. Becoming a full partner in the first friend’s venture would require an investment of $10,000 and 400 hours, and your estimated profit (ignoring the value of your time) would be $9,000. The corresponding figures for the second friend’s venture are $8,000 and 500 hours, with an estimated profit to you of $9,000. However, both friends are flexible and would allow you to come in at any fraction of a full partnership you would like. If you choose a fraction of a full partnership, all the above figures given for a full partnership (money investment, time investment, and your profit) would be multiplied by this same fraction. Because you were looking for an interesting summer job anyway (maximum of 600 hours), you have decided to participate in one or both friends’ ventures in whichever combination would maximize your total estimated profit. You now need to solve the problem of finding the best combination.

(a) Describe the analogy between this problem and the Wyndor Glass Co. problem discussed in Sec. 3.1. Then construct and fill in a table like Table 3.1 for this problem, identifying both the activities and the resources.

(b) Formulate a linear programming model for this problem.

(c) Use Desmos to solve this model by the graphical method. What are the values of the decision variables at the optimal solution? What is the estimated profit?

Self Assessment: Graphical Method #3

Textbook Problem 3.2-4. Use the graphical method to find all optimal soutions for the following model:

Maximize $Z = 500x_1 + 300x_2,$

subject to

$\begin{array}{rcrcr} 15 x_1 & + & 5 x_2 & \leq & 300 \\ 10 x_1 & + & 6 x_2 & \leq & 240 \\ 8x_1 & + & 12x_2 & \leq & 450 \end{array}$

and $x_1 \geq 0, x_2 \geq 0.$

Self Assessment: Graphical Method #4

Textbook Problem 3.4-4. Use the graphical method to solve the problem:

Minimize $Z = 15x_1 + 20x_2,$

subject to

$\begin{array}{rcrcr} x_1 & + & 2x_2 & \geq & 10 \\ 2 x_1 & - & 3x_2 & \leq & 6 \\ x_1 & + & x_2 & \geq & 6 \end{array}$

and $x_1 \geq 0, x_2 \geq 0.$

Unbounded Regions

Self Assessment: Unbounded Region

Explore the linear program below using Desmos. The goal here is to understand that a linear program is not guaranteed to have a maximum value or a minimum value on an unbounded region. It depends on how the objective function is "oriented" with respect to the feasible region.

Optimize $Z = c_1 x_1 + c_2 x_2,$

subject to

$\begin{array}{rcrcr} & & x_2 & \leq & 5 \\ x_1 & + & x_2 & \geq & 2 \end{array}$

and $x_1 \geq 0, x_2 \geq 0.$

In this problem there is no upper bound on $x_1$ so the feasible region is a strip that extends to infinity in the horizontal direction.

Try and answer the questions below using the Desmos graph in the next cell.

1. Using values of $c_1 = 3, c_2 = 2$ so that $Z = 3 x_1 + 2 x_2$ Is there a minimum value? Is there a maximum value?

2. Now change the coefficients c1 and c2 ($Z = c_1 x + c_2 y$). Can you find an objective function that has maximum value but no minimum value?

3. Find coefficients c1 and c2 so that there are infinitely many maxima.

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

Solving Linear Programs with Pyomo

What is Pyomo?

• A Python framework for formulating optimization models

• Similar to other mathematical programming languages such as AMPL and LINDO (see page 72 in the textbook)

• Uses natural math syntax for models (we'll get into examples below)

• Allows separation of the model from the data to formulate large models concisely

• Works with many solvers including GLPK, CPLEX, Gurobi, etc.

Pyomo is an example of a declarative programming language. Instead of specifying exactly how to get the solution (imperative programming) we declare the problem mathematically. Pyomo then translates the mathematical problem into a computer problem that can be solved by one of many available solvers.

Pyomo Resources

Some resources to help you learn more about Pyomo:

• The Official Pyomo Documentation.

• The Pyomo Tutorial is a large set of slides from the Pyomo developers at Sandia National Labs

• Professor Jeffrey Cantor's ND Pyomo Cookbook gives many examples

• The Pyomo Gallery also has several examples.

Installing Pyomo and GLPK

If you're working in CoCalc these are already installed. If you want to install them at home we suggest using the Anocanda distribution, then in a terminal window:

install Pyomo with: conda install -c conda-forge pyomo

install GLPK with: conda install -c conda-forge glpk

Solution Algorithms behind Pyomo

Pyomo works with a wide variety of solvers, but the Pyomo code remains the same. There are two main types of solvers:

• those based on the simplex method

• interior point methods

Both of these are discussed in some detail in the textbook in Chapter 4. We won't go into the details behind these methods, but for most problems they behave similarly in terms of performance. Linear programs with thousands of variables are now fairly routine for most solvers. GLPK is based on the simplex method.

Two kinds of Pyomo models

Concrete Models: data first, then model:

• 1-pass construction: numerical constants supplied as model is built

• easier to script

• harder to reuse model

Abstract Models: model first, then data:

• 2-pass construction

• Pass 1: Model is constructed with unknown numerical constants

• Pass 2: Numerical constants added from separate file at runtime

• harder to script

• easier for large problems and model reuse

We'll stick to concrete models in this course, but we'll take steps toward making them abstract by separating the data and the model.

Pyomo Example

Wyndor Glass Company

Here is the Wyndor model as described in the textbook. $Z$ is the profit in thousands of dollars. $d$ and $w$ are the batches of doors and windows, respectively. The constraints, in order, represent the production capacities of Plants 1, 2, and 3.

Maximize $Z = 3 d + 5 w$

Subject to:

$\begin{array}{ccccc} d & & & \leq & 4 \\ & & 2w & \leq & 12 \\ 3d & + & 2w & \leq & 18 \end{array}$

$d \geq 0$, $w \geq 0$

First Pyomo Solution

Video: Code Walkthrough

# execute this cell for video
play_video("ds775_lesson1-wyndor1")

https://media.uwex.edu/content/ds/ds775_r19/ds775_lesson1-wyndor1/index.html

Pyomo Solution

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

# Decision Variables
model.doors = Var(domain=Reals)
model.windows = Var(domain=Reals)

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

# Constraints
model.Plant1 = Constraint(expr=model.doors <= 4)
model.Plant2 = Constraint(expr=2.0 * model.windows <= 12)
model.Plant3 = Constraint(expr=3.0 * model.doors + 2.0 * model.windows <= 18)
model.dgeq0 = Constraint(expr=model.doors >= 0)
model.wgeq0 = Constraint(expr=model.windows >= 0)

# 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}")
print(model.Plant3())

# NOTE:  the string formatting was updated from the video, we're now using f-strings, short for formatted string literals, for cleaner and more "pythonic" formatting
# Learn more here:  https://realpython.com/python-f-strings/ and http://zetcode.com/python/fstring/

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

Self-Assessment: Specifying Bounds

Non-negativity constraints like $d\geq0$ can be included in the variable declarations by changing domain=Reals to domain=NonNegativeReals.

We can also include lower and upper bounds in the variable declarations like this: model.doors = Var(domain=Reals, bounds = (0,4) ).

Try this: Copy the Pyomo Wyndor solution into a new code block, add appropriate bounds to the doors and windows variables and delete all constraints except the constraint for Plant 3. Run the code. Do you get the same answer?

Pyomo solution using a vector of decision variables

Video: Code Walkthrough

# execute this cell for video
play_video("ds775_lesson1-wyndor2")

https://media.uwex.edu/content/ds/ds775_r19/ds775_lesson1-wyndor2/index.html

Pyomo Solutions

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

products = ['drs', 'wdw']

bounds_dict = {'drs': (0, 4), 'wdw': (0, 6)}
def bounds_rule(model, product):
    return (bounds_dict[product])

model.x = Var(products, domain=Reals, bounds=bounds_rule)

# Objective
model.profit = Objective(expr=3.0 * model.x['drs'] + 5.0 * model.x['wdw'],
                         sense=maximize)

# Constraints
model.Constraint3 = Constraint(
    expr=3.0 * model.x['drs'] + 2.0 * model.x['wdw'] <= 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.x['drs']():.1f}")
print(f"Batches of Windows = {model.x['wdw']():.1f}")

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

Self-Assessment: Formulate and Solve #1

Textbook Problem 3.4-8 (a,c) Ralph Edmund loves steak and potatoes. Therefore, he has decided to go on a steady diet of only these two foods (plus some liquids and vitamin supplements) for all his meals. Ralph realizes that this isn’t the healthiest diet, so he wants to make sure that he eats the right quantities of the two foods to satisfy some key nutritional requirements. He has obtained the nutritional and cost information shown below. Ralph wishes to determine the number of daily servings (can be fractional) of steak and potatoes that will meet these requirements at a minimum cost.

(a) Formulate a mathematical model (the linear program) for this problem.

(c) Use Pyomo to solve the model. Report the minimum cost as well as the number of servings each of steak and potatoes at the minimum.

Start to Finish: Formulate a Model and Code it in Pyomo

Problem Description (video)

This is problem 3.4-9, page 85, from the textbook.

Web Mercantile sells many household products through an online catalog. The company needs substantial warehouse space for storing its goods. Plans now are being made for leasing warehouse storage space over the next 5 months. Just how much space will be required in each of these months is known. However, since these space requirements are quite different, it may be most economical to lease only the amount needed each month on a month-by-month basis. On the other hand, the additional cost for leasing space for additional months is much less than for the first month, so it may be less expensive to lease the maximum amount required for the entire 5 months. Another option is the intermediate approach of changing the total amount of space leased (by adding a new lease and/or having an old lease expire) at least once but not every month.

The space requirement and the leasing costs for the various leasing periods are as follows:

# execute this cell for video
play_video("ds775_lesson1-ex-3-4-9-model-requirements")

<IPython.lib.display.IFrame at 0x7f4f8ee3d9d0>

Mathematical Formulation (video)

# execute this cell for video
play_video("ds775_lesson1-ex-3-4-9-model-formulation")

<IPython.lib.display.IFrame at 0x7f4f8ee3de80>

Using design variables $x_{ij}$ that represent the square feet leased for $j$ months beginning in the $i^{th}$ month, the model is

Minimize $Z =65(x_{11} +x_{21} +x_{31} +x_{41} +x_{51})+100(x_{12} +x_{22} +x_{32} +x_{42}) +135(x_{13} + x_{23} + x_{33}) + 160(x_{14} + x_{24}) + 190x_{15}$

Subject to:

$\begin{array}{lcl} x_{11} + x_{12} + x_{13} + x_{14} + x_{15} & \geq & 30,000 \\ x_{12} + x_{13} + x_{14} + x_{15} + x_{21} + x_{22} + x_{23} + x_{24} & \geq & 20,000 \\ x_{13} + x_{14} + x_{15} + x_{22} + x_{23} + x_{24} + x_{31} + x_{32} + x_{33} & \geq & 40,000 \\ x_{14} + x_{15} + x_{23} + x_{24} + x_{32} + x_{33} + x_{41} + x_{42} & \geq & 10,000 \\ x_{15} + x_{24} + x_{33} + x_{42} + x_{51} & \geq & 50,000 \\ \end{array}$

and all $x_{ij} \geq 0$.

To learn about typesetting mathematics like this go to the section below labeled "Typesetting mathematical notation with LaTeX code."

Solving the model in Pyomo

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

# Decision Variables
model.x = Var( ['x11','x12','x13','x14','x15','x21','x22','x23','x24',
                'x31','x32','x33','x41','x42','x51'], 
              domain = NonNegativeReals )

# Objective 
model.obj = Objective( expr = 65 * (model.x['x11'] + model.x['x21'] + model.x['x31'] + 
                                   model.x['x41'] + model.x['x51']) + 
                      100 * (model.x['x12'] + model.x['x22'] + model.x['x32'] + 
                            model.x['x42']) + 
                      135 * (model.x['x13'] + model.x['x23'] + model.x['x33']) + 
                      160 * (model.x['x14'] + model.x['x24']) + 
                      190 * model.x['x15'], sense = minimize)

# Constraints
model.Constraint1 = Constraint( expr = model.x['x11'] + model.x['x12'] + model.x['x13'] +
                               model.x['x14'] + model.x['x15'] >= 30000 )
model.Constraint2 = Constraint( expr = model.x['x12'] + model.x['x13'] + model.x['x14'] +
                               model.x['x15'] + model.x['x21'] + model.x['x22'] + 
                               model.x['x23'] + model.x['x24'] >= 20000 )
model.Constraint3 = Constraint( expr = model.x['x13'] + model.x['x14'] + model.x['x15'] +
                               model.x['x22'] + model.x['x23'] + model.x['x24'] +
                               model.x['x31'] + model.x['x32'] + model.x['x33'] >= 40000 )
model.Constraint4 = Constraint( expr = model.x['x14'] + model.x['x15'] + model.x['x23'] + 
                               model.x['x24'] + model.x['x32'] + model.x['x33'] + 
                               model.x['x41'] + model.x['x42'] >= 10000 )
model.Constraint5 = Constraint( expr = model.x['x15'] + model.x['x24'] + model.x['x33'] + 
                               model.x['x42'] + model.x['x51'] >= 50000 )

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

# display(model)

# print a shorter summary of relevant results (we inspected the results to figure out what to print)
print(f"Total Cost = ${model.obj():,.2f}")
print(f"Lease {model.x['x15']():.0f} sq. ft. in month 1 for 5 months")
print(f"Lease {model.x['x31']():.0f} sq. ft. in month 3 for 1 month")
print(f"Lease {model.x['x51']():.0f} sq. ft. in month 5 for 1 month")

Total Cost = $7,650,000.00
Lease 30000 sq. ft. in month 1 for 5 months
Lease 10000 sq. ft. in month 3 for 1 month
Lease 20000 sq. ft. in month 5 for 1 month

Typesetting mathematical notation with LaTeX code (video)

# execute this cell for video
play_video("ds775_lesson1-latex-demo")

<IPython.lib.display.IFrame at 0x7f4f6a09a130>

Self-Assessment: Formulate and Solve #2

Textbook Problem 3.4-10 Larry Edison is the director of the Computer Center for Buckly College. He now needs to schedule the staffing of the center. It is open from 8 A.M. until midnight. Larry has monitored the usage of the center at various times of the day, and determined that the following number of computer consultants are required:

Two types of computer consultants can be hired: full-time and part-time. The full-time consultants work for 8 consecutive hours in any of the following shifts: morning (8 A.M.–4 P.M.), afternoon (noon–8 P.M.), and evening (4 P.M.–midnight). Full-time consultants are paid $40 per hour. Part-time consultants can be hired to work any of the four shifts listed in the above table. Part-time consultants are paid $30 per hour. An additional requirement is that during every time period, there must be at least 2 full-time consultants on duty for every part-time consultant on duty. Larry would like to determine how many full-time and how many part-time workers should work each shift to meet the above requirements at the minimum possible cost.

(a) Formulate a linear programming model for this problem. (Hint: you could have 7 design variables - 3 for the number of full-time workers on each shift and 4 for the number of part-time workers on each shift.)

(b) Solve this model using Pyomo. You may find fractional numbers of consultants per shift so round the answers to get an approximate solution. Report the total cost with both fractional and rounded numbers of consultants.

(c) (not in book) Using Pyomo in Python, require the decision variables to be integers (specify domain=NonNegativeIntegers rather than NonNegativeReals for the decision variables), and compute the solution. How does it compare to the solution in (b)? This is now an integer programming problem and is not solved by the simplex method. We'll learn more about integer programming soon. Be aware that integer programming problems are generally more computationally intense than those using real valued variables.

Self-Assessment: Formulate and Solve #3

Textbook Problem 3.5-6 (a,e). Maureen Laird is the chief financial officer for the Alva Electric Co., a major public utility in the Midwest. The company has scheduled the construction of new hydroelectric plants 5, 10, and 20 years from now to meet the needs of the growing population in the region served by the company. To cover at least the construction costs, Maureen needs to invest some of the company’s money now to meet these future cash-flow needs. Maureen may purchase only three kinds of financial assets, each of which costs $1 million per unit. Fractional units may be purchased. The assets produce income 5, 10, and 20 years from now, and that income is needed to cover at least minimum cash-flow requirements in those years. (Any excess income above the minimum requirement for each time period will be used to increase dividend payments to shareholders rather than saving it to help meet the minimum cash-flow requirement in the next time period.) The following table shows both the amount of income generated by each unit of each asset and the minimum amount of income needed for each of the future time periods when a new hydroelectric plant will be constructed.

Maureen wishes to determine the mix of investments in these assets that will cover the cash-flow requirements while minimizing the total amount invested.

(a) Formulate a linear programming model for this problem.

(e) Use Pyomo to solve the model.

Sausages Blending Problem

Here is an extra example, with no videos, of a blending problem. We'll revisit this example in the next lesson.

This example adapted from here: http://benalexkeen.com/linear-programming-with-python-and-pulp-part-4/.

Problem Description

We're going to make sausages by blending pork, wheat, and starch. Our objective is to minimize the cost of making the sausages. The table below shows the ingredients available, the cost, and the amount of each ingredient available from our supplier:

Ingredient	Cost ($/kg)	Amount (kg)
Pork	4.32	7
Wheat	2.46	20.0
Starch	1.86	17

Additionally, we have 23 kg of pork on hand that we must use in the sausages.

We want to make 2 types of sausage:

• Economy ( > 40% pork)

• Premium ( > 60% pork)

Each sausage is 50 grams (0.05 kg).

According to government regulations, the most starch we can use in our sausages is 25% by weight.

We have a demand for 350 economy sausages and 500 premium sausages.

The linear program

The decision variables are the kg of each ingredient to use:

Variable	Description
$p_e$	kg pork in the economy sausages
$w_e$	kg wheat in the economy sausages
$s_e$	kg starch in the economy sausages
$p_p$	kg pork in the premium sausages
$w_p$	kg wheat in the premium sausages
$s_p$	kg starch in the premium sausages

We want to minimize the cost: $$\mbox{Cost} = 4.32 ( p_e + p_p) + 2.46( w_e + w_p) + 1.86 (s_e + s_p)$$

Subject to the following constraints:

Constraint	Description
$p_e + w_e + s_e = 350 \times 0.05$	total kg of economy sausages
$p_p + w_p + s_p = 500 \times 0.05$	total kg of premium sausages
$p_e \geq 0.4 (p_e + w_e + s_e)$	ecomony sausage must be at least 40% pork
$p_p \geq 0.6 (p_p + w_p + s_p)$	premium sausage must be at least 60% pork
$s_e \leq 0.25 (p_e + w_e + s_e)$	no more than 25% starch
$s_p \leq 0.25 (p_p + w_p + s_p)$	no more than 25% starch
$p_e + p_p \leq 30$	30 kg of pork available
$w_e + w_p \leq 20$	20 kg of wheat available
$s_e + s_p \leq 17$	17 kg of starch avaialble
$p_e + p_p \geq 23$	must use the 23 kg of pork we already purchased

Pyomo Solution

x = 5

# Concrete Model
M = ConcreteModel(name = "Sausages1")

# Decision Variables
M.pe = Var(domain = NonNegativeReals)
M.we = Var(domain = NonNegativeReals)
M.se = Var(domain = NonNegativeReals)
M.pp = Var(domain = NonNegativeReals)
M.wp = Var(domain = NonNegativeReals)
M.sp = Var(domain = NonNegativeReals)

# Objective 
M.cost = Objective( expr = 4.32*(M.pe+M.pp)+2.46*(M.we+M.wp)+1.86*(M.se+M.sp),
                      sense = minimize )

# Constraints
M.tot_econ_ct = Constraint( expr = M.pe + M.we + M.se == 17.5 )
M.tot_prem_ct = Constraint( expr = M.pp + M.wp + M.sp == 25 )
M.p_prp_econ_ct = Constraint( expr = M.pe >= 0.4*(M.pe + M.we + M.se) )
M.p_prp_prem_ct = Constraint( expr = M.pp >= 0.6*(M.pp + M.wp + M.sp) )
M.s_prp_econ_ct = Constraint( expr = M.se <= 0.25*(M.pe + M.we + M.se) )
M.s_prp_prem_ct = Constraint( expr = M.sp <= 0.25*(M.pp + M.wp + M.sp) )
M.p_tot_mx_ct = Constraint( expr = M.pe + M.pp <= 30 )
M.w_tot_mx_ct = Constraint( expr = M.we + M.wp <= 20 )
M.s_tot_mx_ct = Constraint( expr = M.se + M.sp <= 17 )
M.p_tot_mn_ct = Constraint( expr = M.pe + M.pp >= 23 )

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

# display(M)

# display solution
print(f"Minimum Cost = ${M.cost():,.2f}")

import pandas as pd
dvars = pd.DataFrame( [[M.pe(),M.pp()],
                       [M.we(),M.wp()],
                       [M.se(),M.sp()]],
                    index = ['Pork','Wheat','Starch'],
                    columns = ['Economy','Premium'])
print("Kilograms of each ingredient in each type of sausage:")
dvars

Minimum Cost = $140.96
Kilograms of each ingredient in each type of sausage: