ผลต่างระหว่างรุ่นของ "204512/บรรยาย 11"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
 
(ไม่แสดง 28 รุ่นระหว่างกลางโดยผู้ใช้ 4 คน)
แถว 1: แถว 1:
 +
----
 +
จดบันทึกคำบรรยายโดย:
 +
:นางสาว สุกัลยา เลิศวิวัฒน์สกุล   รหัส : 50653955
 +
:นางสาว กมลวรรณ โพธิ์แก้ว       รหัส : 50653724
 +
<br />
 +
----
 
== ทบทวน ==
 
== ทบทวน ==
 
<u>Primal Linear Programming</u>
 
<u>Primal Linear Programming</u>
:minimize :
+
:minimize &nbsp;: <math>\sum_{j=1}^nc_j x_j</math>
::<math>\sum_{j=1}^n</math>c<sub>j</sub>x<sub>j</sub>
+
:subject to : <math>\sum_{j=1}^n a_{ij} x_j \ge b_i \qquad ; i = 1,...,m</math>
:subject to :
+
:::::: <math>x_i \ge 0 \qquad ; j = 1,...,n</math>
::<math>\sum_{j=1}^n</math>a<sub>ij</sub>x<sub>j</sub> ≥ b<sub>i</sub> &nbsp;&nbsp;; i = 1,,m
 
::: &nbsp; &nbsp; x<sub>i</sub> ≥ 0&nbsp;&nbsp;; j = 1,,n
 
  
 +
<br><br>
 +
หรือเขียนเป็น matrix form ได้
 +
:minimize &nbsp; : C&prime;x
 +
:subject to : Ax ≥ b &nbsp;&nbsp;; x เป็นเมตริกซ์ขนาด n-dimension
 +
:::: x ≥ 0
  
 
<u>Dual Linear Programming</u>
 
<u>Dual Linear Programming</u>
:maximize :
+
:maximize : <math>\sum_{i=1}^m b_i y_i</math>
::<math>\sum_{i=1}^m</math>b<sub>i</sub>y<sub>i</sub>
+
:subject to : <math>\sum_{i=1}^m a_{ij} y_i \le c_j \qquad ; j = 1,...,n</math>
:subject to :
+
:::::: <math>y_i \ge 0 \qquad ; i = 1,...,m</math>
::<math>\sum_{i=1}^m</math>a<sub>ij</sub>y<sub>i</sub> ≥ c<sub>j</sub> &nbsp;&nbsp;; j = 1,…,n
+
<br><br>
::: &nbsp; &nbsp; y<sub>i</sub> ≥ 0&nbsp;&nbsp;; i = 1,…,m
+
หรือเขียนเป็น matrix form ได้
 +
:maximize : y&prime;b
 +
:subject to : A<sup>T</sup>y ≤ c &nbsp;&nbsp;; y เป็นเมตริกซ์ขนาด m-dimension
 +
:::: &nbsp; y ≥ 0
 +
 
  
----
+
<u>'''ตัวอย่าง 1''' - Assigment</u><br>
<u>ตัวอย่าง - Assigment</u><br>
 
 
<u>โจทย์</u> - มีงาน n งาน
 
<u>โจทย์</u> - มีงาน n งาน
 
::มีพนักงาน n คน
 
::มีพนักงาน n คน
::assogn งาน j ให้กับพนักงาน i ใช้ cost C<sub>ij</sub>
+
::assign งาน j ให้กับพนักงาน i ใช้ cost C<sub>ij</sub>
 
::ต้องการ assign งานให้กับพนักงาน โดยที่งาน 1 งานให้พนักงาน 1 คน
 
::ต้องการ assign งานให้กับพนักงาน โดยที่งาน 1 งานให้พนักงาน 1 คน
 
::::::::: &nbsp; &nbsp;และพนักงาน 1 คนได้งาน 1 งาน
 
::::::::: &nbsp; &nbsp;และพนักงาน 1 คนได้งาน 1 งาน
 
+
<br>
<u>วิธีทำ</u>
+
'''วิธีทำ'''
 
:ให้ x<sub>ij</sub> เป็น 1 ถ้า assign งาน j ให้กับ i
 
:ให้ x<sub>ij</sub> เป็น 1 ถ้า assign งาน j ให้กับ i
 
:: &nbsp;&nbsp;เป็น 0 ถ้าเป็นอื่นๆ
 
:: &nbsp;&nbsp;เป็น 0 ถ้าเป็นอื่นๆ
 
<br>
 
<br>
 +
จากโจทย์เราเขียนเป็นสมการได้ว่า
 
<u>Primal</u>
 
<u>Primal</u>
 
:minimize :  
 
:minimize :  
::<math>\sum_{i=1}^n\sum_{j=1}^m</math>c<sub>ij</sub>x<sub>ij</sub>
+
::<math>\sum_{i=1}^n\sum_{j=1}^m c_{ij} x_{ij}</math>
 
:subject to :  
 
:subject to :  
::<math>\forall j</math>; &nbsp; &nbsp; &nbsp; <math>\sum_{i=1}^n</math>x<sub>ij</sub> = 1
+
::<math>\forall j; \qquad \sum_{i=1}^n x_{ij} = 1</math>
::<math>\forall i</math>; &nbsp; &nbsp; &nbsp; <math>\sum_{j=1}^n</math>x<sub>ij</sub> = 1
+
::<math>\forall i; \qquad \sum_{j=1}^n x_{ij} = 1</math>
::<math>\forall i,j</math>; &nbsp; x<sub>ij</sub> &isin; {0,1}
+
::<math>\forall i,j; \quad \quad x_{ij} \in {0,1}</math>
 
<br>
 
<br>
//--------------------------------------------------------------------------------------------------------------------//
+
จะเห็นว่าสมการข้างบนเป็น integer program ซึ่งต้องใช้เวลาในการแก้นาน ฉะนั้นเราจะทำให้เป็น linear program แทน
 
<br>
 
<br>
<u>note</u>
+
ฉะนั้นเราจะแก้ subject to เป็น
จาก x<sub>ij</sub> &isin; {0,1} ไม่สามารถใชกัน linear progame ได้ ฉะนั้นเราจะแก้ subject to เป็น
+
::<math>\forall j; \qquad \sum_{i=1}^n x_{ij} \ge 1 \qquad \longrightarrow (\beta_j)</math>
::<math>\forall j</math>; &nbsp; &nbsp; &nbsp; <math>\sum_{i=1}^n</math>x<sub>ij</sub> ≥ 1 &nbsp; &nbsp; ----(&beta;<sub>j</sub>)
+
::<math>\forall i; \qquad \sum_{j=1}^n x_{ij} \ge 1 \qquad \longrightarrow (\alpha_i)</math>
::<math>\forall i</math>; &nbsp; &nbsp; &nbsp; <math>\sum_{j=1}^n</math>x<sub>ij</sub> ≥ 1 &nbsp; &nbsp; ----(&alpha;<sub>i</sub>)
+
::<math>\forall i,j; \qquad x_{ij} \ge 0</math>
::<math>\forall i,j</math>; &nbsp; x<sub>ij</sub> ≥ 0
+
:จะได้ว่าเป็น <u>relaxed</u> linear program
:จะได้ว่า relaxed linear program
+
 
//--------------------------------------------------------------------------------------------------------------------//
 
 
<br>
 
<br>
 
<u>เขียนเป็น Dual</u>
 
<u>เขียนเป็น Dual</u>
 
:maximize :
 
:maximize :
::<math>\sum_{i=1}^n</math>&alpha;<sub>i</sub> + <math>\sum_{j=1}^m</math>&beta;<sub>j</sub>
+
::<math>\sum_{i=1}^n \alpha_i + \sum_{j=1}^m \beta_j</math>
 
:subject to :  
 
:subject to :  
::<math>\forall i,j</math>; &nbsp; &alpha;<sub>i</sub> + &beta;<sub>j</sub> = 1
+
::<math>\forall i,j; \qquad \alpha_i + \beta_j \le c_{ij}</math>
::<math>\forall i</math>; &nbsp; &nbsp; &nbsp; &alpha;<sub>i</sub> ≥ 0
+
::<math>\forall i; \qquad \qquad \quad \alpha_i \ge 0</math>
::<math>\forall j</math>; &nbsp; &nbsp; &nbsp; &beta;<sub>j</sub> ≥ 0
+
::<math>\forall j; \qquad \qquad \quad \beta_j \ge 0</math>
 +
 
 +
<pre><nowiki>
 +
เมื่อเราแปลง Primal → Dual ; ค่า Max ของค่าที่นำมาแปลง จะไม่เกินค่า Min ของค่าที่ถูกแปลง
 +
</nowiki></pre>
 +
{{จบบทพิสูจน์}}
 +
 
 +
<u>'''ตัวอย่าง 2'''</u><br>
 +
<u>โจทย์</u> จากตัวอย่างที่ 1 ต้องการหา optimal maching?
 +
<br>
 +
'''วิธีทำ'''<br>
 +
: สามารถทำให้ค่า objective = 15 ได้หรือไม่ ?<br>
 +
[[ภาพ:Image_example2.jpg|200px]]
 +
<pre><nowiki>
 +
Solution คือ สร้าง Dual ที่มี objective = 15 แล้วสร้าง Primal ที่มี objective = 15 เช่นเดียวกัน
 +
</nowiki></pre>
 +
: กำหนดให้<br><br>
 +
[[ภาพ:Image_feasible_infeasible.jpg]]<br><br>
 +
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;เราจะทำการปรับค่า Dual(feasible แล้ว) ใหม่ แล้วแก้ Primal(infeasible) เก่า ให้เหมาะสมกับ Dual ใหม่ ทำจนกว่าค่าของ Dual และ Primal(feasible ทั้งคู่) จะมีค่าเท่ากัน<br><br>
 +
[[ภาพ:Image_solution.jpg|750px]]
 +
<br>
 +
{{จบบทพิสูจน์}}
  
 +
== Duality ==
 +
จาก Prob. priallity<br>
 +
;นิยาม :
 +
<u>Primal</u>
 +
:maximize : c&prime;x
 +
:subject to : Ax ≥ b
 +
::::&nbsp; x ≥ 0
 +
<br>
 +
<u>Dual</u>
 +
:maximize : y&prime;b
 +
:subject to : A<sup>T</sup>y ≤ c
 +
::::&nbsp; y ≥ 0
 +
<br>
 +
=== Weak duality ===
 +
{{กล่องทฤษฎีบท|
 +
'''Thm''':
 +
:ถ้า x และ y เป็น feasible solution
 +
:y&prime;b ≤ c&prime;x}}
 +
 +
'''Proof:'''
 +
:y&prime;b ≤ y&prime;Ax ≤ c&prime;x
 +
{{จบบทพิสูจน์}}
 +
<br>
 +
 +
=== Storng duality ===
 +
{{กล่องทฤษฎีบท|
 +
'''Thm''':
 +
:ถ้า x* และ y* เป็น 2optimal solution ของ PLP, DLP
 +
:c&prime;x* <nowiki>=</nowiki> b&prime;y*}}
 +
 +
----
 +
 +
== Complementary Slackness ==
 +
{{กล่องทฤษฎีบท|
 +
'''Dual''':
 +
:maximize : y&prime;b
 +
::A<sup>T</sup>y + s <nowiki>=</nowiki> c &nbsp; &nbsp; &nbsp; ; s เป็น matrix ขนาด n มิติเท่า y
 +
:: &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; y ≥ 0
 +
:: &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; s ≥ 0}}
 +
 +
'''Proof:'''
 +
:(A<sup>T</sup>y*&prime; + s)x* = y*&prime;b
 +
: &nbsp; y*&prime;Ax + sx* = y*&prime;b
 +
: &nbsp; &nbsp; y*&prime;b + sx*&prime; = y*&prime;b
 +
::: &nbsp; sx* = 0
 +
{{จบบทพิสูจน์}}
 +
 +
 +
{{เริ่มบทพิสูจน์ }}
 +
'''<u>ตัวอย่าง 3 : Shortest path</u>'''<br>
 +
<u>โจทย์</u> หา shortest path จาก s<br>
 +
'''วิธีทำ'''
 +
:ให้กราฟ G = (V,E), l(u,v) แทนความยาวเส้นเชื่อม (u,v)
 +
: &nbsp; ตัวแปร D<sub>v</sub> แทนระยะทาง s ไปยัง v<br>
 +
: [[ภาพ:Image_line_distance.jpg]]<br>
 +
<u>Primal</u>
 +
:maximize :
 +
::D<sub>t</sub> - D<sub>s</sub>
 +
:subject to :
 +
::<math>\forall e = (u,v); \qquad \ D_v \le D_u + l(u,v)</math>
 +
::::::::<font size='4'><math>\mathit{ D_s = 0 } </math></font><br><br>
 +
::<math>\forall u; \qquad \qquad \qquad D_u \ge 0</math>
 +
<br>
 +
จะเห็นว่าสมการข้างบนดูยาก เราจะเขียนใหม่ได้
 +
:maximize :
 +
::D<sub>t</sub> - D<sub>s</sub>
 +
:subject to :
 +
::<math>\forall e = (u,v); \qquad D_v - D_u \le l(u,v) \qquad \longrightarrow x(u,v)</math>
 +
::<math>\forall u; \qquad \qquad \qquad \qquad D_u \ge 0</math>
 +
 +
<br>
 +
<u>เขียนเป็น Dual</u> ได้
 +
:minimize :
 +
::<math>\sum_{(u,v) \in E} l(u,v) x(u,v) \qquad \longrightarrow </math> <font size='3'>เป็น cost ของ flow</font>
 +
:subject to :
 +
<!-- ::<math>\forall u_{u \in {s,t}} \in V; \qquad \alpha_i + \beta_j \le c_{ij}</math>
 +
::<math>\forall i; \qquad \qquad \qquad \qquad \alpha_i \ge 0</math>
 +
::<math>\forall j; \qquad \qquad \qquad \qquad \beta_j \ge 0</math>-->
 +
 +
::<math>\sum_{(w,u) \in E} x(w,u) = \sum_{(u,w) \in E} x(u,w)</math>
 +
<br>
 +
:::::[[ภาพ:Image_arrow_in_out.jpg]]
 +
<br>
 +
::<math>\sum_{(w,u) \in E} x(w,u) = \sum_{(u,w) \in E} x(u,w) \qquad \longrightarrow </math> <font size='3'>flow เข้ามา t 1 หน่วย</font>
 +
::<math>\sum_{(w,s) \in E} x(w,s) = \sum_{(s,w) \in E} x(s,w) \qquad \longrightarrow </math> <font size='3'>flow ออกจาก s 1 หน่วย</font><br><br>
 +
นี่คือ 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)<br>
 +
: [[ภาพ:Image_multi.jpg|140 px]] &nbsp;&nbsp;&nbsp;&nbsp;ที่มี cost = ค่าต่ำสุด (route มากสุด = max flow)
 +
<br>
 +
: <u>min-cost circulation</u> คือ flow = 0 โดยหมุนวนใน flow. จากรูป<br>
 +
:: [[ภาพ:Image_circle.jpg]]
 +
:minimize :
 +
::<math>\sum_{(u,v) \in E} c(x,y) f(x,y)</math>
 +
:subject to :
 +
::<math>\forall u \in V; \qquad \sum_{(w,x) \in E} f(w,x) = \sum_{(x,w) \in E} f(x,w)</math>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(flow เข้า = flow ออก)
 +
:::::::::<math>f(x,y) \le u(x,y)</math>
 
----
 
----

รุ่นแก้ไขปัจจุบันเมื่อ 11:21, 16 กันยายน 2550


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

นางสาว สุกัลยา เลิศวิวัฒน์สกุล   รหัส : 50653955
นางสาว กมลวรรณ โพธิ์แก้ว       รหัส : 50653724



ทบทวน

Primal Linear Programming

minimize  :
subject to :



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

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

Dual Linear Programming

maximize :
subject to :



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

maximize : y′b
subject to : ATy ≤ c   ; y เป็นเมตริกซ์ขนาด m-dimension
  y ≥ 0


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

มีพนักงาน n คน
assign งาน j ให้กับพนักงาน i ใช้ cost Cij
ต้องการ assign งานให้กับพนักงาน โดยที่งาน 1 งานให้พนักงาน 1 คน
   และพนักงาน 1 คนได้งาน 1 งาน


วิธีทำ

ให้ xij เป็น 1 ถ้า assign งาน j ให้กับ i
  เป็น 0 ถ้าเป็นอื่นๆ


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

minimize :
subject to :


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

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


เขียนเป็น Dual

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

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

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

Image example2.jpg

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

Image feasible infeasible.jpg

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

Image solution.jpg

Littlebox.png

Duality

จาก Prob. priallity

นิยาม 

Primal

maximize : c′x
subject to : Ax ≥ b
  x ≥ 0


Dual

maximize : y′b
subject to : ATy ≤ c
  y ≥ 0


Weak duality

Thm:

ถ้า x และ y เป็น feasible solution
y′b ≤ c′x

Proof:

y′b ≤ y′Ax ≤ c′x
Littlebox.png


Storng duality

Thm:

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

Complementary Slackness

Dual:

maximize : y′b
ATy + s = c       ; s เป็น matrix ขนาด n มิติเท่า y
         y ≥ 0
         s ≥ 0

Proof:

(ATy*′ + s)x* = y*′b
  y*′Ax + sx* = y*′b
    y*′b + sx*′ = y*′b
  sx* = 0
Littlebox.png



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

ให้กราฟ G = (V,E), l(u,v) แทนความยาวเส้นเชื่อม (u,v)
  ตัวแปร Dv แทนระยะทาง s ไปยัง v
Image line distance.jpg

Primal

maximize :
Dt - Ds
subject to :



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

maximize :
Dt - Ds
subject to :


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

minimize :
เป็น cost ของ flow
subject to :


Image arrow in out.jpg


flow เข้ามา t 1 หน่วย
flow ออกจาก s 1 หน่วย

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

Littlebox.png

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)
Image multi.jpg     ที่มี cost = ค่าต่ำสุด (route มากสุด = max flow)


min-cost circulation คือ flow = 0 โดยหมุนวนใน flow. จากรูป
Image circle.jpg
minimize :
subject to :
      (flow เข้า = flow ออก)