程序代做 COMP3530 Discrete Optimization – cscodehelp代写
COMP3530 Discrete Optimization
Week 3: Modeling
Julian of Computer Science University of and Refresher
Goal for Today
Show power of Linear Programming by modeling several optimization problems as a Linear Programs.
Give a demo of Gurobi (www.gurobi.com).
1
Recall
A Linear Program is optimization problem of the form
minimize c · x subject to Ax b x2Rn
whereA2Rm⇥n,b2Rm,andc2Rn.
Any general Linear Program can be reduced to an equivalent
program in standard form.
Simplex algorithm solves Linear Programs in standard form.
standard form A-✗= 6
✗ 20 rank(A) = m
2
Modeling
Three Steps of Modeling
To model a given optimization problem as a Linear Program we need to:
1. Define our variables: How many are there, of what type, and what do they represent?
2. Define our constraints: What are the inequalities and what do they enforce?
3. Objective function: What is it and what does it represent?
For each of the components we need to define them and, to make sense of it, state the semantic that we are trying to capture.
3
Production Planning
Given demand forecast data d1, d2, . . . , dn for n time periods, we need to decide how many units to produce in each period so that:
1. We always have enough stock to meet demand.
2. Each time period we produce at least m at most M units. 3. Storage costs f per unit per time period.
1 Variables
✗i.amount producedattimei
see
50–10
left
over stock
at time i
✗= 5
10 5 9
f – 1 – 1 – 1 – 1
5. = 9 6 d,=6
4
Production Planning
Given demand forecast data d1, d2, . . . , dn for n time periods, we need to decide how many units to produce in each period so that:
1. We always have enough stock to meet demand.
2. Each time period we produce at least m at most M units. 3. Storage costs f per unit per time period.
2
Constraints
I
dis
Si 3 si =
So –0
M
✗sM i
ti=1.–,n ,
=i ti,
sin + Xi ,
n i=0,- . ,n
0
Si.,+Xi- di
4
—
Production Planning
Given demand forecast data d1, d2, . . . , dn for n time periods, we need to decide how many units to produce in each period so that:
1. We always have enough stock to meet demand.
2. Each time period we produce at least m at most M units. 3. Storage costs f per unit per time period.
What if w e cannot shore ^ t” “” “” °”*”°”
3 Objective m in
[( I
t.si
di
+
e-= e
,
n
?|¥¥⇒ 4
e-= ‘
s in ,
E. ¥+2 e-=
“”¥ F.
r
Fit a line through a point set
Given (x ,yP),(x ,y ),…,(x ,y ) want to find scalars a and b 1122nn
a x t b
m i n i m i z i n g ni = 1 | y i ( a x i + b ) | . ” e . 1 a.6 free
|^
ei > 0
tier,
..
,n
2
Caxitb) Sei
✗ ti- 1, . . . ,n
3
Eei
–
) Sei [-]
Yi –
Yi ( axitb
m in
i. = L
n
5
Fit a line through a point set
Given (x ,yP),(x ,y ),…,(x ,y ) want to find scalars a and b 1122nn
minimizing ni=1 |yi (axi + b)|. convex
↳ 2- z
↳ objective
o
objective
to
is minimize
concave
is to maximize
5
Flow Problems
1
Variables
V-cu.net
V-cu.net
a-
8
Given a directed graph G = (V,E) with capacities c : E ! R, and s, t 2 V . Find an s-t flow with maximum value.
fun > o 2 fur
scar
Ét u ⇐ V l { S t }
+
Efe
e e s i c n )
Efe
e e s o e t l u)
?f
–
[
eesoutcsy
capacities ?
e.c- 5cm Ewefe
3
max
te
2 vertex
)
3 Mox flow min cost 6
Integer Programming
Integer Linear Programs are special Linear Programs that have additional integrality constraints on the variables.
minimize c · x subject to Ax b
x 2 Zn
7
Gurobi Demo
To Install Gurobi on your computer
Follow the instructions to install Gurobi for Academics and Researchers.
There will be some applied components to our future assignments where you will have solve Linear Programs.
You are not required to, but I strongly recommend that you use Gurobi. Other popular solvers are CPLEX, Matlab, and GLPK. Even Excel has an add-in solver!
8
Administratrivia
Announcements
• Install Gurobi on your computer, apply for an academic license, and run the Jupyter notebook from the demo.
• How are the tutorials going? • Assignment 2:
• available in Ed (resource tab)
• due on August 27 (11:59pm)
• -submission is via Gradescope (up and running) • any questions?
9
10
