Q1 Standard Form
CSC373 Fall’20 Tutorial 6
Oct 27, 2020
Convert the following linear program to the standard form.
min 4x+3y−6z s.t.
y − 3z ≥ 2x + 2 3x + 2y + 5z = 10 x, z ≥ 0
Q2 Simple Scheduling with Prerequisites (SSP)
You are given n jobs with a list of durations d1,d2,…,dn. For every pair of jobs (i,j), you are also given a boolean pi,j: if this is true, then job i must finish before job j can begin (i.e. job i is a prerequisite for job j).
Your goal is to find start times s1, s2, . . . , sn for the jobs (no job can start earlier than time 0) such that the total time to complete all jobs is minimized while ensuring that the prerequisite constraints are met. Write a linear program to solve this problem.
Q3 Exercises From Class
(a) Show that the following optimization problem can be solved by solving one or more LPs.
max 12A + 23B + 15C s.t.
5A+15B+10C ≤500 4A+4B+7C ≤300 35A+20B+25C ≤1000 ¬(A > 0 ∧ B > 0)
A, B, C ≥ 0
(b) Show that the following optimization problem can be solved by solving one or more LPs.
1
max 12A+23B·C2 s.t.
5A+15B+10C ≤500 4A+4B+7C ≤300 35A+20B+25C ≤1000 C ∈ 1,…,100
A, B ≥ 0 (c) LetF={x∈Rn:Ax≤b∧x≥0}.Let
• O1 = arg maxx∈F cT1 x
// This is a usual LP as we maximize a linear objective subject to linear constraints;
• O2 = arg maxx∈O1 cT2 x
// Among the optimal solutions from before, break ties by maximizing another objective;
• O3 = arg maxx∈O2 cT3 x
// Break ties further by maximizing yet another objective.
Show how to find some x ∈ O3 by solving one or more LPs.
2