Python & Linear
Programming Basics
IEDA 3010 Tutorial 01
Chen Yang
Software Installation
• Anaconda (Python)
• [Link]
• Programming: Jupyter, Spyder, Pycharm, vscode.
Anaconda
Create and management the Python environment using
Anaconda Navigator or Anaconda Prompt.
Learn Python 3
• Google is the best
teacher for
programming.
• Tutorials on Anaconda
about Python, Pandas,
Numpy, Matplotlib and
so on.
• Tutorials on Youtube.
• Read and implement
examples.
Try Python as a scientific calculator
• Python arithmetic operators and function print
• Assignment operator “=”
• Variable(s): name(s) on the left, Value(s): expression(s) on the right
• Variables can be assigned to new values
• Other assignment operations
• +=, -=,
• Basic Built-in Data Types
• type()
• int, float, long ------ Numeric types (+, -, * , /, ** )
• True, False ----- Bool types
• str ------ string (+, len(), index, slice, f-string)
• list, tuple, dict, set
• Function
• abs, max, print, range,…
• Define a function, set parameters and return results.
• Module: import numpy as np
String
• Index and slice • f-string (python 3.6 or above)
Combine variable and string
• Sum of string
Format control ([Link])
• Length of string
• Add and remove element
List
• Create a list
• Index and slice
• Copy
• Keys, values and items
Dictionary
• Create a dict (key + value)
• Manipulation
Python Control Flow
• The Boolean Type Expressions
• Status: True or False
➢ Comparison operators (==, !=, >=, <=, >, <)
➢ Identity operators (is, is not)
➢ Membership operators (in, not in)
➢ Logic operators (and, or, not)
• Conditional Statements
• if-elif-else
• Coding style
• Flat is better than nested
• Readability counts
• Nested
Python Control Flow
• Iterations and loops
• The while loop
• The for loop
• Repeat the task a fixed number of times
• Comparison
Define a function
Output
Summary
• Software Installation
• Variables, Simple Data Types, Functions and Modules
• Assignment Statements
• Basic types and type conversion
• Function and modules
• Python Control Flow
• Boolean type expression
• Conditional statements
• Iterations and loops
Linear Optimization Review
• Formulation
• Standard form and other forms
• Geometry
Formulation
max 𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛
𝑠. 𝑡. 𝑎𝑖1 𝑥1 + 𝑎𝑖2 𝑥2 + ⋯ + 𝑎𝑖𝑛 𝑥𝑛 ≤ 𝑏𝑖 , 𝑖 = 1, … , 𝑚
𝑥1 , 𝑥2 , … , 𝑥𝑛 ≥ 0
• Decision variables: 𝑥1 , 𝑥2 , ⋯
• Objective function: 𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛
i.e. max or min 𝑓(𝑥)
• Constraints: 𝑎𝑖1 𝑥1 + 𝑎𝑖2 𝑥2 + ⋯ + 𝑎𝑖𝑛 𝑥𝑛 ≤ 𝑏𝑖 , 𝑥𝑖 ≥ 0
max 𝑐 𝑇 𝑥
Standard Form s.t. 𝐴𝑥 ≤ 𝑏
x≥0
Other Forms
1. Minimize to Maximize [Objective Function]
min 𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛
m𝑎𝑥 −𝑍 = −𝑐1 𝑥1 − 𝑐2 𝑥2 − ⋯ − 𝑐𝑛 𝑥𝑛
2. Larger than or equal to (≥) to Smaller than or equal to (≤)
[Constraints]
𝑎𝑖1 𝑥1 + 𝑎𝑖2 𝑥2 + ⋯ + 𝑎𝑖𝑛 𝑥𝑛 ≥ 𝑏𝑖
−𝑎𝑖1 𝑥1 − 𝑎𝑖2 𝑥2 − ⋯ − 𝑎𝑖𝑛 𝑥𝑛 ≤ −𝑏𝑖
Other Forms
3. Equal to (=) to Smaller than or equal to (≤) [Constraints]
𝑎𝑖1 𝑥1 + 𝑎𝑖2 𝑥2 + ⋯ + 𝑎𝑖𝑛 𝑥𝑛 = 𝑏𝑖
𝑎𝑖1 𝑥1 + 𝑎𝑖2 𝑥2 + ⋯ + 𝑎𝑖𝑛 𝑥𝑛 ≤ 𝑏𝑖
−𝑎𝑖1 𝑥1 − 𝑎𝑖2 𝑥2 − ⋯ − 𝑎𝑖𝑛 𝑥𝑛 ≤ −𝑏𝑖
4. Unrestricted sign [Constraints]
𝑥𝑗 unrestricted in sign for some values of j
𝑥𝑗 = 𝑥𝑗+ − 𝑥𝑗− Replace 𝑥𝑗 with 𝑥𝑗+ − 𝑥𝑗−
𝑥𝑗+ , 𝑥𝑗− ≥ 0 everywhere
Geometry of LP Review
• Constraints
▪ Example: inequality constraint
x1 + 2x2 ≤ 3 define a half space
• Feasible Region
▪ Intersection of all constraints
• Extreme Points
▪ Corner points inside the feasible region
Geometry of LP Review
• Objective function
▪ Isoquant
• Optimal solution
▪ Best feasible solution
▪ Unique, not unique, not finite optimal solution
• Binding and non-binding constraints
• *Theorem: For any feasible LP with a finite number of optimal solution, there
exists an optimal solution that is an extreme point.
▪ From infinite number of feasible solution to finite number of extreme points
Example 1
Example 1 (Solution)
Available Investment Return of Investment
Invest\ Invest\
1 2 3 4 5 1 2 3 4 5
Year Year
1.4
A ✓ ✓ ✓ ✓ A 1.4 A1 1.4 A2
A3
B ✓ ✓ ✓
B 1.7B1 1.7B2
C ✓
C
D ✓
D
Example 2
Use the graphical method to solve this problem
min 𝑍 = 15𝑥1 + 20𝑥2
s.t. 𝑥1 + 2𝑥2 ≥ 10 (1)
2𝑥1 − 3𝑥2 ≤ 6 (2)
𝑥1 + 𝑥2 ≥ 6 (3)
𝑥1, 𝑥2 ≥ 0
Example 2
min 𝑍 = 15𝑥1 + 20𝑥2
x2
s.t. 𝑥1 + 2𝑥2 ≥ 10 (1)
2𝑥1 − 3𝑥2 ≤ 6 (2)
𝑥1 + 𝑥2 ≥ 6 (3)
𝑥1, 𝑥2 ≥ 0
(2) (3) (1) x1
Optimal Solution:
(x1, x2) = (x1*, x2*) = (2, 4)
Z* = 110