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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(ย้อน)
 
(ไม่แสดง 42 รุ่นระหว่างกลางโดยผู้ใช้ 5 คน)
แถว 1: แถว 1:
บันทึกโดย : นายณัฐพล หล่อศิริ 50653781 , ...
+
จดบันทึกคำบรรยายโดย:
 +
::นายณัฐพล หล่อศิริ 50653781 และ<br>
 +
::นายวรวุทธ นัมคนิสรณ์ 50653898
  
  
แถว 16: แถว 18:
 
----
 
----
 
=== <u>Linear Programming Problem</u> ===
 
=== <u>Linear Programming Problem</u> ===
Instant ของ linear programming คือ จำนวนเต็มบวก n, m, c ∈ R^n, b ∈ R^m และเมตริกซ์ A ของจำนวนจริงขนาด m x n จะได้ว่า
+
Instant ของ linear programming คือ จำนวนเต็มบวก n, m เวกเตอร์  c ∈ R<sup>n</sup>, b ∈ R<sup>m</sup> และเมตริกซ์ A ของจำนวนจริงขนาด m x n จะได้ว่า
:F = { x R^n :Ax = b ,  x ≥0 }
+
:F = { x R<sup>n</sup> :Ax = b ,  x ≥0 }
:Cost : x → c^Tx
+
:Cost : x → c'x
  
  
แถว 27: แถว 29:
 
:หา x ที่ Ax = b  ;  x ≥ 0    แทนค่าจะได้<br>
 
:หา x ที่ Ax = b  ;  x ≥ 0    แทนค่าจะได้<br>
 
:[[ภาพ:Image011.png]]<br>
 
:[[ภาพ:Image011.png]]<br>
:หา x ที่ทำให้ c1x1 + c2x2 + c3x3 น้อยที่สุด
+
:หา x ที่ทำให้ <math>c_1x_1</math> + <math>c_2x_2</math> + <math>c_3x_3</math> น้อยที่สุด
  
  
แถว 33: แถว 35:
 
*การเขียนในรูปแบบ ''สมการ''<br>
 
*การเขียนในรูปแบบ ''สมการ''<br>
 
:- การระบุเซต F (เป็น constraint ของปัญหา)
 
:- การระบุเซต F (เป็น constraint ของปัญหา)
::x1 + x2 = 5
+
::<math>x_1</math> + <math>x_2</math> = 5
::x3 + x4 x2 = 1
+
::<math>x_3</math> + <math>x_4</math> <math>x_2</math> = 1
::x1 - x2 + x3 = 8
+
::<math>x_1</math> - <math>x_2</math> + <math>x_3</math> = 8
::x5 x3 = 7
+
::<math>x_5</math> <math>x_3</math> = 7
::xi ≥ 0  ทุกๆ  1 ≤ i ≤5
+
::<math>x_i</math> ≥ 0  ทุกๆ  1 ≤ i ≤5
 
:- การระบุ c (เป็น objective ของปัญหา)
 
:- การระบุ c (เป็น objective ของปัญหา)
::minimize:  x1 + x2 x3 + 2x4 2x5
+
::minimize:  <math>x_1</math> + <math>x_2</math> <math>x_3</math> + <math>x_4</math> <math>x_5</math>
  
 
*การเขียนในรูปแบบ ''เมตริกซ์''<br>
 
*การเขียนในรูปแบบ ''เมตริกซ์''<br>
แถว 45: แถว 47:
  
 
----
 
----
 +
 
=== <u>Form ของ Linear Programming</u> ===
 
=== <u>Form ของ Linear Programming</u> ===
 
==== Standard form ====
 
==== Standard form ====
แถว 70: แถว 73:
  
 
ถ้าให้
 
ถ้าให้
::x1 = เวลาอ่าน Architect
+
::<math>x_1</math> = เวลาอ่าน Architect
::x2 = เวลาอ่าน Algo
+
::<math>x_2</math> = เวลาอ่าน Algo
::x3 = เวลาอ่าน Soft Com.
+
::<math>x_3</math> = เวลาอ่าน Soft Com.
ให้ความเหนื่อยในการอ่านเป็น x1 + 5x2 + 2x3<br>
+
ให้ความเหนื่อยในการอ่านเป็น <math>x_1</math> + 5<math>x_2</math> + 2<math>x_3</math><br>
 
เป้าหมายคือ ต้องการอ่านหนังสือให้ได้ตามเงื่อนไข + ความเหนื่อยน้อยสุด<br>
 
เป้าหมายคือ ต้องการอ่านหนังสือให้ได้ตามเงื่อนไข + ความเหนื่อยน้อยสุด<br>
 
<u>วิธีทำ</u>
 
<u>วิธีทำ</u>
:minimize: x1 + 5x2 + 2x3
+
:minimize: <math>x_1</math> + 5<math>x_2</math> + 2<math>x_3</math>
 
:subject to:
 
:subject to:
::x1 + x2 + x3 ≤ 12
+
::<math>x_1</math> + <math>x_2</math> + <math>x_3</math> ≤ 12
::x1 ≥ 1
+
::<math>x_1</math> ≥ 1
::x2 ≥ 1
+
::<math>x_2</math> ≥ 1
::x3 ≥ 1
+
::<math>x_3</math> ≥ 1
::x1 + x2 ≥ 5
+
::<math>x_1</math> + <math>x_2</math> ≥ 5
::x1 , x2 , x3 ≥ 0<br>
+
::<math>x_3</math> ≤ 8
 +
::<math>x_1</math> , <math>x_2</math> , <math>x_3</math> ≥ 0<br>
 
แปลงให้อยู่ในรูป canonical form การทำให้สมการที่เป็น ≤ ให้เป็น ≥ ให้หมดจะได้ว่า<br>
 
แปลงให้อยู่ในรูป canonical form การทำให้สมการที่เป็น ≤ ให้เป็น ≥ ให้หมดจะได้ว่า<br>
:minimize: x1 + 5x2 + 2x3
+
:minimize: <math>x_1</math> + 5<math>x_2</math> + 2<math>x_3</math>
:subject to:
+
:subject to:
::-x1 - x2 - x3 ≥ -12
+
::จาก <math>x_1</math> + <math>x_2</math> + <math>x_3</math> ≤ 12 เอา -1 คูณตลอดจะได้
::x1 ≥ 1
+
::<math>-x_1</math> + <math>-x_2</math> + <math>-x_3</math> ≥ -12
::x2 ≥ 1
+
::จาก<math>x_3</math> ≤ 8 เอา -1 คูณตลอดจะได้
::x3 ≥ 1
+
::<math>-x_3</math> ≥ -8
::x1 + x2 ≥ 5
+
::<math>x_1</math> ≥ 1
::x1 , x2 , x3 ≥ 0<br>
+
::<math>x_2</math> ≥ 1
 +
::<math>x_3</math> ≥ 1
 +
::<math>x_1</math> + <math>x_2</math> ≥ 5
 +
::<math>x_1</math> , <math>x_2</math> , <math>x_3</math> ≥ 0<br>
 
เขียนเป็น matrix ได้<br>
 
เขียนเป็น matrix ได้<br>
 
::[[ภาพ:Image018.png]]
 
::[[ภาพ:Image018.png]]
แถว 98: แถว 105:
  
 
;<u>'''ตัวอย่าง'''</u>:
 
;<u>'''ตัวอย่าง'''</u>:
:บริษัทเช่าเต๊นท์มหาสนุกจำกัด<br>
+
:บริษัทเช่าเต๊นท์มหาสนุกจำกัด รับจัดหาเต็นท์ในเดือนๆหนึ่งมีเต็นท์ใช้ได้ไม่น้อยกว่าจำนวนที่ใช้ โดยมีเงื่อนไขว่าเต็นท์ซื้อขายได้ เก็บเต็นท์ในโกดังคิดค่าเช่าโกดัง จะซื้อขายหรือเก็บเต็นท์ยังไงให้ได้กำไรมากที่สุด<br>
 
:กำหนด<br>
 
:กำหนด<br>
::di ; i = 1, … ,12  เป็นจำนวนเต๊นท์ที่ต้องการในเดือนที่ i
+
::<math>d_i</math> ; i = 1, … ,12  เป็นจำนวนเต๊นท์ที่ต้องการในเดือนที่ i
::t0 ; เป็นจำนวนเต๊นท์ที่เหลือจากปีที่แล้ว
+
::<math>t_0</math> ; เป็นจำนวนเต๊นท์ที่เหลือจากปีที่แล้ว
::cb ; ราคาซื้อเต๊นท์ / เต๊นท์
+
::<math>c_b</math> ; ราคาซื้อเต๊นท์ / เต๊นท์
::cs ; ราคาขายเต๊นท์ / เต๊นท์
+
::<math>c_s</math> ; ราคาขายเต๊นท์ / เต๊นท์
::ck ; ราคาเก็บเต๊นท์ที่ไม่ได้ใช้ / เดือน<br>
+
::<math>c_k</math> ; ราคาเก็บเต๊นท์ที่ไม่ได้ใช้ / เดือน<br>
 
:ตัวแปร
 
:ตัวแปร
::t1 , … , t12 จำนวนเต๊นท์ที่เราครอบครองในเดือนที่ i
+
::<math>t_1</math> , … , <math>t_12</math> จำนวนเต๊นท์ที่เราครอบครองในเดือนที่ i
::b1 , … , b12 จำนวนเต๊นท์ที่ซื้อในเดือนที่ i
+
::<math>b_1</math> , … , <math>b_12</math> จำนวนเต๊นท์ที่ซื้อในเดือนที่ i
::s1 , … , s12 จำนวนเต๊นท์ที่ขายในเดือนที่ i
+
::<math>s_1</math> , … , <math>s_12</math> จำนวนเต๊นท์ที่ขายในเดือนที่ i
::k1 , … , k12 จำนวนเต๊นท์ในโกดังในเดือนที่ i<br>
+
::<math>k_1</math> , … , <math>k_12</math> จำนวนเต๊นท์ในโกดังในเดือนที่ i<br>
 
:จะได้ว่า <br>
 
:จะได้ว่า <br>
 
::minimize:    [[ภาพ:Image019.png]]<br>
 
::minimize:    [[ภาพ:Image019.png]]<br>
 
::subject to:
 
::subject to:
:::ti ≥  di ; i = 1, … ,12   
+
:::<math>t_i</math> ≥  <math>d_i</math> ; i = 1, … ,12   
:::ki ti - di ; i = 1, … ,12   
+
:::<math>k_i</math> <math>t_i</math> - <math>d_i</math> ; i = 1, … ,12   
:::ti ti-1  ≤  bi
+
:::<math>t_i</math> <math>t_i</math>-1  ≤  <math>b_i</math>
:::bi ≥  0 ; i = 1, … ,12   
+
:::<math>b_i</math> ≥  0 ; i = 1, … ,12   
:::ti-1 – ti ≤  si
+
:::<math>t_i</math>-1 – <math>t_i</math> ≤  <math>s_i</math>
:::si ≥  0
+
:::<math>s_i</math> ≥  0
:::ti ≥  0
+
:::<math>t_i</math> ≥  0
'''''Note'''''  maximize เป็นส่วนกลับของ minimize สามารถแปลงกลับไปมาได้โดยเอา -1 คูณ
+
'''''Note'''''  maximize เป็นส่วนกลับของ minimize สามารถแปลงกลับไปมาได้โดยเอา -1 คูณเงื่อนไข
  
 
----
 
----
=== <u>Shortest path in linear programming</u> ===
+
 
 +
=== <u>Shortest path in Linear Programming</u> ===
  
  
แถว 136: แถว 144:
 
::ds = 0
 
::ds = 0
 
::dv ≥ 0 สำหรับทุกๆ v∈V
 
::dv ≥ 0 สำหรับทุกๆ v∈V
 +
 +
 +
----
 +
 +
== Integer Programming ==
 +
:คือการบอกว่า constraint (subject to) มีการกำหนดให้เป็นจำนวนเต็มค่าใดค่าหนึ่ง
 +
----
 +
 +
=== <u>Assignment Problem</u> ===
 +
;<u>'''ตัวอย่าง'''</u>
 +
:มีคน n คน มีงาน n งาน
 +
:คนที่ i ทำงาน j ใช้เวลา w_ij หน่วย
 +
<u>วิธีทำ</u>
 +
:ให้ตัวแปร [[ภาพ:Image025.png]]
 +
:minimize: [[ภาพ:Image026.png]]<br>
 +
:subject to:<br>
 +
::[[ภาพ:Image027.png]]
 +
::[[ภาพ:Image028.png]]
 +
::[[ภาพ:Image029.png]] (เขียนแบบ integer programming)
 +
::[[ภาพ:Image030.png]] (เขียนแบบ linear programming)
 +
 +
----
 +
== Duality ==
 +
;<u>'''ตัวอย่าง'''</u>:
 +
 +
:minimize: 7x<sub>1</sub> + x<sub>2</sub> + 5x<sub>3</sub>
 +
:subject to:
 +
::x<sub>1</sub> – x<sub>2</sub> + 3x<sub>3</sub> ≥ 10 …(1)
 +
::5x<sub>1</sub> + 2x<sub>2</sub> – x<sub>3</sub> ≥ 6 …(2)
 +
::x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub> ≥ 0
 +
:ค่า objective ของคำตอบที่ดีที่สุด = Z<sup>*</sup>
 +
 +
 +
:สมมติ&nbsp;&nbsp;[[ภาพ:Image031.png]]&nbsp;แล้วบอกได้ว่า Z* ≤ 30
 +
:(1)x 2 + (2);&nbsp;&nbsp;&nbsp;7x<sub>1</sub> + 5x<sub>3</sub> ≥ 26<br>
 +
:สังเกตว่าคล้ายๆ minimize เพราะฉะนั้นบอกได้ว่า lower bound เป็น 26
 +
 +
:(1)x y<sub>1</sub> →&nbsp;&nbsp;&nbsp;y<sub>1</sub>x<sub>1</sub> – y<sub>1</sub>x<sub>2</sub> + 3y<sub>1</sub>x<sub>3</sub> ≥ 10y<sub>1</sub><br>
 +
:(2)x y<sub>2</sub> →&nbsp;&nbsp;&nbsp;5y<sub>2</sub>x<sub>1</sub> + 2y<sub>2</sub>x<sub>2</sub> – y<sub>2</sub>x<sub>3</sub> ≥ 6y<sub>2</sub>
 +
 +
:ต้องการ สัมประสิทธิ์ของ x<sub>1</sub> = 7, สัมประสิทธิ์ของ x<sub>2</sub> = 1, สัมประสิทธิ์ของ x<sub>3</sub> = 5<br>
 +
:เพราะฉะนั้นจะสร้าง linear program ได้อีกอันว่า
 +
 +
 +
:maximize: 10y<sub>1</sub> + 6y<sub>2</sub>
 +
:subject to:
 +
::y<sub>1</sub> + 5y<sub>2</sub> ≤ 7 …(3)
 +
::-y<sub>1</sub> + 2y<sub>2</sub> ≤ 1 …(4)
 +
::3y<sub>1</sub> - y<sub>2</sub> ≤ 5 …(5)
 +
::y<sub>1</sub>, y<sub>2</sub> ≥ 0
 +
:ค่า objective ของคำตอบที่ดีที่สุด = A<sup>*</sup>
 +
 +
 +
:เพราะฉะนั้น A<sup>*</sup> = Z<sup>*</sup> จะเรียกว่า strong duality
 +
:โดย
 +
::สมการที่ (1), (2) จะเรียกว่า ''Primal''
 +
::สมการที่ (3), (4), (5) จะเรียกว่า ''Dual''
 +
 +
----
 +
=== <u>Primal Linear Programming</u> ===
 +
:minimize:
 +
::[[ภาพ:Image015.png]]
 +
:subject to:
 +
::[[ภาพ:Image034.png]]&nbsp;&nbsp;; i = 1,…,m
 +
::x<sub>i</sub> ≥ 0&nbsp;&nbsp;; j = 1,…,n
 +
 +
----
 +
 +
=== <u>Dual Linear Programming</u> ===
 +
:maximize:
 +
::[[ภาพ:Image035.png]]
 +
:subject to:
 +
::[[ภาพ:Image036.png]]&nbsp;&nbsp;; j = 1,…,n
 +
::y<sub>i</sub> ≥ 0&nbsp;&nbsp;; i = 1,…,m
 +
 +
----
 +
 +
=== <u>Max flow & Min Cut</u> ===
 +
ให้ P แทนเซตของ simple path ทั้งหมดจาก s ไป t สำหรับ path p∈P มี
 +
ตัวแปร f<sub>p</sub> แทนปริมาณ flow ใน path นั้น
 +
 +
:''primal''
 +
::maximize:&nbsp;&nbsp;[[ภาพ:Image038.png]]
 +
::subject to:
 +
:::[[ภาพ:Image0392.png]]&nbsp;&nbsp;[[ภาพ:Image040.png]]
 +
:::[[ภาพ:Image041.png]]&nbsp;&nbsp;f<sub>p</sub> ≥ 0
 +
 +
:''dual''
 +
::กำหนดตัวแปร d<sub>e</sub> สำหรับ edge e
 +
::minimize:&nbsp;&nbsp;[[ภาพ:Image042.png]]
 +
::subject to:
 +
:::[[ภาพ:Image043.png]]&nbsp;&nbsp;[[ภาพ:Image044.png]]
 +
:::[[ภาพ:Image045.png]]&nbsp;&nbsp;d<sub>e</sub> ≥ 0
 +
 +
:ดังนั้นสรุปได้ว่า ''Min Cut'' เป็น '''Dual''' ของ ''Max Flow''
 +
 +
 +
;<u>'''ตัวอย่าง'''</u>:
 +
:''primal''
 +
::minimize: 2x<sub>1</sub> + 5x<sub>2</sub>
 +
::subject to:
 +
:::x<sub>1</sub> + x<sub>2</sub> ≥ 5 …y1
 +
:::-x<sub>1</sub> + x<sub>2</sub> ≥ -1 …y2
 +
:::x<sub>1</sub> + 2x<sub>2</sub> ≥ 4 …y3
 +
:::x<sub>1</sub>, x<sub>2</sub> ≥ 0
 +
 +
:แปลงเป็น dual ได้ว่า
 +
 +
:''dual''
 +
::maximize: 5y<sub>1</sub> – y<sub>2</sub> + 4y<sub>3</sub>
 +
::subject to:
 +
:::y<sub>1</sub> – y<sub>2</sub> + y<sub>3</sub> ≤ 2
 +
:::y<sub>1</sub> + y<sub>2</sub> + 2y<sub>3</sub> ≤ 5
 +
:::y<sub>1</sub>, y<sub>2</sub>, y<sub>3</sub> ≥ 0

รุ่นแก้ไขปัจจุบันเมื่อ 11:10, 23 กันยายน 2553

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

นายณัฐพล หล่อศิริ 50653781 และ
นายวรวุทธ นัมคนิสรณ์ 50653898


Linear Programming

Note Problem ต่างจาก Instant ของ Problem กล่าวคือ Problem จะเท่ากับ เซตของ Instant ของ Problem
Note ตัวแปรทั้งหมดเป็นตัวแปรแบบเวกเตอร์ เพราะฉะนั้นจะขอละ ไม่ใส่เครื่องหมายเวกเตอร์


Optimization Problem

Instant ของปัญหา Optimization Problem จะประกอบด้วย

  • set F (เซตของคำตอบที่เป็นไปได้)
  • function cost F→R (จำนวนจริง)

ต้องการหา f∈F และ cost (f) ≤ cost (y) , สำหรับทุกๆ y∈F


Linear Programming Problem

Instant ของ linear programming คือ จำนวนเต็มบวก n, m เวกเตอร์ c ∈ Rn, b ∈ Rm และเมตริกซ์ A ของจำนวนจริงขนาด m x n จะได้ว่า

F = { x ∈ Rn :Ax = b , x ≥0 }
Cost : x → c'x


ตัวอย่าง

กำหนดให้ n = 3, m = 1 เขียนเป็นเมตริกซ์ ได้เป็น

Image010.png
หา x ที่ Ax = b ; x ≥ 0 แทนค่าจะได้
Image011.png
หา x ที่ทำให้ + + น้อยที่สุด


ตัวอย่าง
  • การเขียนในรูปแบบ สมการ
- การระบุเซต F (เป็น constraint ของปัญหา)
+ = 5
+ = 1
- + = 8
= 7
≥ 0 ทุกๆ 1 ≤ i ≤5
- การระบุ c (เป็น objective ของปัญหา)
minimize: + +
  • การเขียนในรูปแบบ เมตริกซ์
Image013.png , Image014.png , Image0142.png

Form ของ Linear Programming

Standard form

เมตริกซ์
minimize: cx
subject to: Ax = b ; x ≥ 0
สมการ
minimize: Image015.png
subject to: Image016.png เมื่อ j = 1,…,n


Canonical form

เมตริกซ์
minimize: cx
subject to: Ax ≥ b ; x ≥ 0
สมการ
minimize: Image015.png
subject to: Image017.png เมื่อ j = 1,…,n


ตัวอย่าง
เตรียมสอบมีเวลาอ่านหนังสือ 12 ชม. มี 3 วิชา Architect, Algo, Soft Com. อ่านอย่างน้อยวิชาละ 1 ชม., อ่าน architect & algo รวมกันไม่น้อยกว่า 5 ชม., อ่าน Soft Com. ไม่เกิน 8 ชม.

ถ้าให้

= เวลาอ่าน Architect
= เวลาอ่าน Algo
= เวลาอ่าน Soft Com.

ให้ความเหนื่อยในการอ่านเป็น + 5 + 2
เป้าหมายคือ ต้องการอ่านหนังสือให้ได้ตามเงื่อนไข + ความเหนื่อยน้อยสุด
วิธีทำ

minimize: + 5 + 2
subject to:
+ + ≤ 12
≥ 1
≥ 1
≥ 1
+ ≥ 5
≤ 8
, , ≥ 0

แปลงให้อยู่ในรูป canonical form การทำให้สมการที่เป็น ≤ ให้เป็น ≥ ให้หมดจะได้ว่า

minimize: + 5 + 2
subject to:
จาก + + ≤ 12 เอา -1 คูณตลอดจะได้
+ + ≥ -12
จาก ≤ 8 เอา -1 คูณตลอดจะได้
≥ -8
≥ 1
≥ 1
≥ 1
+ ≥ 5
, , ≥ 0

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

Image018.png


ตัวอย่าง
บริษัทเช่าเต๊นท์มหาสนุกจำกัด รับจัดหาเต็นท์ในเดือนๆหนึ่งมีเต็นท์ใช้ได้ไม่น้อยกว่าจำนวนที่ใช้ โดยมีเงื่อนไขว่าเต็นท์ซื้อขายได้ เก็บเต็นท์ในโกดังคิดค่าเช่าโกดัง จะซื้อขายหรือเก็บเต็นท์ยังไงให้ได้กำไรมากที่สุด
กำหนด
; i = 1, … ,12 เป็นจำนวนเต๊นท์ที่ต้องการในเดือนที่ i
; เป็นจำนวนเต๊นท์ที่เหลือจากปีที่แล้ว
; ราคาซื้อเต๊นท์ / เต๊นท์
; ราคาขายเต๊นท์ / เต๊นท์
; ราคาเก็บเต๊นท์ที่ไม่ได้ใช้ / เดือน
ตัวแปร
, … , จำนวนเต๊นท์ที่เราครอบครองในเดือนที่ i
, … , จำนวนเต๊นท์ที่ซื้อในเดือนที่ i
, … , จำนวนเต๊นท์ที่ขายในเดือนที่ i
, … , จำนวนเต๊นท์ในโกดังในเดือนที่ i
จะได้ว่า
minimize: Image019.png
subject to:
; i = 1, … ,12
= - ; i = 1, … ,12
-1 ≤
≥ 0 ; i = 1, … ,12
-1 –
≥ 0
≥ 0

Note maximize เป็นส่วนกลับของ minimize สามารถแปลงกลับไปมาได้โดยเอา -1 คูณเงื่อนไข


Shortest path in Linear Programming

ตัวอย่าง

Image020.jpg
สมมติ path ดังรูป d1 = 0, ตัวแปร d1, … , d5 แทนระยะสั้นสุดจาก node 1 ไปยัง node ต่างๆ
ให้กราฟแบบมีทิศทาง G = (V,E) ความยาว l บนเส้นเชื่อม, จุดเริ่มต้น s∈V
ให้ dv แทนระยะสั้นสุดจาก s ไป v สำหรับ v∈V
จะได้ว่า

maximize: Image023.png
subject to:
dv – du ≤ l(u,v) สำหรับทุกๆ (u,v)∈E
ds = 0
dv ≥ 0 สำหรับทุกๆ v∈V



Integer Programming

คือการบอกว่า constraint (subject to) มีการกำหนดให้เป็นจำนวนเต็มค่าใดค่าหนึ่ง

Assignment Problem

ตัวอย่าง
มีคน n คน มีงาน n งาน
คนที่ i ทำงาน j ใช้เวลา w_ij หน่วย

วิธีทำ

ให้ตัวแปร Image025.png
minimize: Image026.png
subject to:
Image027.png
Image028.png
Image029.png (เขียนแบบ integer programming)
Image030.png (เขียนแบบ linear programming)

Duality

ตัวอย่าง
minimize: 7x1 + x2 + 5x3
subject to:
x1 – x2 + 3x3 ≥ 10 …(1)
5x1 + 2x2 – x3 ≥ 6 …(2)
x1, x2, x3 ≥ 0
ค่า objective ของคำตอบที่ดีที่สุด = Z*


สมมติ  Image031.png แล้วบอกได้ว่า Z* ≤ 30
(1)x 2 + (2);   7x1 + 5x3 ≥ 26
สังเกตว่าคล้ายๆ minimize เพราะฉะนั้นบอกได้ว่า lower bound เป็น 26
(1)x y1 →   y1x1 – y1x2 + 3y1x3 ≥ 10y1
(2)x y2 →   5y2x1 + 2y2x2 – y2x3 ≥ 6y2
ต้องการ สัมประสิทธิ์ของ x1 = 7, สัมประสิทธิ์ของ x2 = 1, สัมประสิทธิ์ของ x3 = 5
เพราะฉะนั้นจะสร้าง linear program ได้อีกอันว่า


maximize: 10y1 + 6y2
subject to:
y1 + 5y2 ≤ 7 …(3)
-y1 + 2y2 ≤ 1 …(4)
3y1 - y2 ≤ 5 …(5)
y1, y2 ≥ 0
ค่า objective ของคำตอบที่ดีที่สุด = A*


เพราะฉะนั้น A* = Z* จะเรียกว่า strong duality
โดย
สมการที่ (1), (2) จะเรียกว่า Primal
สมการที่ (3), (4), (5) จะเรียกว่า Dual

Primal Linear Programming

minimize:
Image015.png
subject to:
Image034.png  ; i = 1,…,m
xi ≥ 0  ; j = 1,…,n

Dual Linear Programming

maximize:
Image035.png
subject to:
Image036.png  ; j = 1,…,n
yi ≥ 0  ; i = 1,…,m

Max flow & Min Cut

ให้ P แทนเซตของ simple path ทั้งหมดจาก s ไป t สำหรับ path p∈P มี ตัวแปร fp แทนปริมาณ flow ใน path นั้น

primal
maximize:  Image038.png
subject to:
Image0392.png  Image040.png
Image041.png  fp ≥ 0
dual
กำหนดตัวแปร de สำหรับ edge e
minimize:  Image042.png
subject to:
Image043.png  Image044.png
Image045.png  de ≥ 0
ดังนั้นสรุปได้ว่า Min Cut เป็น Dual ของ Max Flow


ตัวอย่าง
primal
minimize: 2x1 + 5x2
subject to:
x1 + x2 ≥ 5 …y1
-x1 + x2 ≥ -1 …y2
x1 + 2x2 ≥ 4 …y3
x1, x2 ≥ 0
แปลงเป็น dual ได้ว่า
dual
maximize: 5y1 – y2 + 4y3
subject to:
y1 – y2 + y3 ≤ 2
y1 + y2 + 2y3 ≤ 5
y1, y2, y3 ≥ 0