204512/บรรยาย 11

---

จดบันทึกคำบรรยายโดย:

นางสาว สุกัลยา เลิศวิวัฒน์สกุล   รหัส : 50653955

นางสาว กมลวรรณ โพธิ์แก้ว       รหัส : 50653724

---

ทบทวน

Primal Linear Programming

minimize  : $\sum _{j=1}^{n}c_{j}x_{j}$

subject to : $\sum _{j=1}^{n}a_{ij}x_{j}\geq b_{i}\qquad ;i=1,...,m$

$x_{i}\geq 0\qquad ;j=1,...,n$

หรือเขียนเป็น matrix form ได้

minimize   : C′x

subject to : Ax ≥ b   ; x เป็นเมตริกซ์ขนาด n-dimension

x ≥ 0

Dual Linear Programming

maximize : $\sum _{i=1}^{m}b_{i}y_{i}$

subject to : $\sum _{i=1}^{m}a_{ij}y_{i}\leq c_{j}\qquad ;j=1,...,n$

$y_{i}\geq 0\qquad ;i=1,...,m$

หรือเขียนเป็น matrix form ได้

maximize : y′b

subject to : A^Ty ≤ c   ; y เป็นเมตริกซ์ขนาด m-dimension

  y ≥ 0

ตัวอย่าง 1 - Assigment
โจทย์ - มีงาน n งาน

มีพนักงาน n คน

assign งาน j ให้กับพนักงาน i ใช้ cost C_ij

ต้องการ assign งานให้กับพนักงาน โดยที่งาน 1 งานให้พนักงาน 1 คน

   และพนักงาน 1 คนได้งาน 1 งาน

วิธีทำ

ให้ x_ij เป็น 1 ถ้า assign งาน j ให้กับ i

  เป็น 0 ถ้าเป็นอื่นๆ

จากโจทย์เราเขียนเป็นสมการได้ว่า Primal

minimize :

$\sum _{i=1}^{n}\sum _{j=1}^{m}c_{ij}x_{ij}$

subject to :

$\forall j;\qquad \sum _{i=1}^{n}x_{ij}=1$

$\forall i;\qquad \sum _{j=1}^{n}x_{ij}=1$

$\forall i,j;\quad \quad x_{ij}\in {0,1}$

จะเห็นว่าสมการข้างบนเป็น integer program ซึ่งต้องใช้เวลาในการแก้นาน ฉะนั้นเราจะทำให้เป็น linear program แทน
ฉะนั้นเราจะแก้ subject to เป็น

$\forall j;\qquad \sum _{i=1}^{n}x_{ij}\geq 1\qquad \longrightarrow (\beta _{j})$

$\forall i;\qquad \sum _{j=1}^{n}x_{ij}\geq 1\qquad \longrightarrow (\alpha _{i})$

$\forall i,j;\qquad x_{ij}\geq 0$

จะได้ว่าเป็น relaxed linear program

เขียนเป็น Dual

maximize :

$\sum _{i=1}^{n}\alpha _{i}+\sum _{j=1}^{m}\beta _{j}$

subject to :

$\forall i,j;\qquad \alpha _{i}+\beta _{j}\leq c_{ij}$

$\forall i;\qquad \qquad \quad \alpha _{i}\geq 0$

$\forall j;\qquad \qquad \quad \beta _{j}\geq 0$

เมื่อเราแปลง Primal → Dual ; ค่า Max ของค่าที่นำมาแปลง จะไม่เกินค่า Min ของค่าที่ถูกแปลง

---

ตัวอย่าง 2
โจทย์ จากตัวอย่างที่ 1 ต้องการหา optimal maching?
วิธีทำ

สามารถทำให้ค่า objective = 15 ได้หรือไม่ ?

Solution คือ สร้าง Dual ที่มี objective = 15 แล้วสร้าง Primal ที่มี objective = 15 เช่นเดียวกัน

กำหนดให้

     เราจะทำการปรับค่า Dual(feasible แล้ว) ใหม่ แล้วแก้ Primal(infeasible) เก่า ให้เหมาะสมกับ Dual ใหม่ ทำจนกว่าค่าของ Dual และ Primal(feasible ทั้งคู่) จะมีค่าเท่ากัน

---

Duality

จาก Prob. priallity

นิยาม 

Primal

maximize : c′x

subject to : Ax ≥ b

  x ≥ 0

Dual

maximize : y′b

subject to : A^Ty ≤ c

  y ≥ 0

Weak duality

Thm:

ถ้า x และ y เป็น feasible solution

y′b ≤ c′x

Proof:

y′b ≤ y′Ax ≤ c′x

---

Storng duality

Thm:

ถ้า x* และ y* เป็น 2optimal solution ของ PLP, DLP

c′x* = b′y*

---

Complementary Slackness

Dual:

maximize : y′b

A^Ty + s = c       ; s เป็น matrix ขนาด n มิติเท่า y

         y ≥ 0

         s ≥ 0

Proof:

(A^Ty*′ + s)x* = y*′b

  y*′Ax + sx* = y*′b

    y*′b + sx*′ = y*′b

  sx* = 0

---

---

ตัวอย่าง 3 : Shortest path
โจทย์ หา shortest path จาก s
วิธีทำ

ให้กราฟ G = (V,E), l(u,v) แทนความยาวเส้นเชื่อม (u,v)

  ตัวแปร D_v แทนระยะทาง s ไปยัง v

Primal

maximize :

D_t - D_s

subject to :

$\forall e=(u,v);\qquad \ D_{v}\leq D_{u}+l(u,v)$

${\mathit {D_{s}=0}}$

$\forall u;\qquad \qquad \qquad D_{u}\geq 0$

จะเห็นว่าสมการข้างบนดูยาก เราจะเขียนใหม่ได้

maximize :

D_t - D_s

subject to :

$\forall e=(u,v);\qquad D_{v}-D_{u}\leq l(u,v)\qquad \longrightarrow x(u,v)$

$\forall u;\qquad \qquad \qquad \qquad D_{u}\geq 0$

เขียนเป็น Dual ได้

minimize :

$\sum _{(u,v)\in E}l(u,v)x(u,v)\qquad \longrightarrow$ เป็น cost ของ flow

subject to :

$\sum _{(w,u)\in E}x(w,u)=\sum _{(u,w)\in E}x(u,w)$

$\sum _{(w,u)\in E}x(w,u)=\sum _{(u,w)\in E}x(u,w)\qquad \longrightarrow$ flow เข้ามา t 1 หน่วย

$\sum _{(w,s)\in E}x(w,s)=\sum _{(s,w)\in E}x(s,w)\qquad \longrightarrow$ flow ออกจาก s 1 หน่วย

นี่คือ Dual Program ของ Shortest Path และเป็น form หนึ่งของปัญหา min cost flow

---

Min-cost Maximun flow

min-cost flow คือการหา flow ที่มี cost ต่ำที่สุด

ให้กราฟ G = (V,E)

capacity u(x,y) บน edge (x,y)

cost c(x,y) บน edge (x,y)

    ที่มี cost = ค่าต่ำสุด (route มากสุด = max flow)

min-cost circulation คือ flow = 0 โดยหมุนวนใน flow. จากรูป

minimize :

$\sum _{(u,v)\in E}c(x,y)f(x,y)$

subject to :

$\forall u\in V;\qquad \sum _{(w,x)\in E}f(w,x)=\sum _{(x,w)\in E}f(x,w)$      (flow เข้า = flow ออก)

$f(x,y)\leq u(x,y)$

---