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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 19: แถว 19:
 
=== <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^n, b ∈ R^m และเมตริกซ์ A ของจำนวนจริงขนาด m x n จะได้ว่า
:F = { x R^n :Ax = b ,  x ≥0 }
+
:F = { x R^n :Ax = b ,  x ≥0 }
 
:Cost : x → c'x
 
:Cost : x → c'x
  

รุ่นแก้ไขเมื่อ 06:04, 3 กันยายน 2550

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

นายณัฐพล หล่อศิริ 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 ∈ R^n, b ∈ R^m และเมตริกซ์ A ของจำนวนจริงขนาด m x n จะได้ว่า

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


ตัวอย่าง

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

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


ตัวอย่าง
  • การเขียนในรูปแบบ สมการ
- การระบุเซต F (เป็น constraint ของปัญหา)
x1 + x2 = 5
x3 + x4 – x2 = 1
x1 - x2 + x3 = 8
x5 – x3 = 7
xi ≥ 0 ทุกๆ 1 ≤ i ≤5
- การระบุ c (เป็น objective ของปัญหา)
minimize: x1 + x2 – x3 + 2x4 – 2x5
  • การเขียนในรูปแบบ เมตริกซ์
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 ชม.

ถ้าให้

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

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

minimize: x1 + 5x2 + 2x3
subject to:
x1 + x2 + x3 ≤ 12
x1 ≥ 1
x2 ≥ 1
x3 ≥ 1
x1 + x2 ≥ 5
x1 , x2 , x3 ≥ 0

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

minimize: x1 + 5x2 + 2x3
subject to:
-x1 - x2 - x3 ≥ -12
x1 ≥ 1
x2 ≥ 1
x3 ≥ 1
x1 + x2 ≥ 5
x1 , x2 , x3 ≥ 0

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

Image018.png


ตัวอย่าง
บริษัทเช่าเต๊นท์มหาสนุกจำกัด
กำหนด
di ; i = 1, … ,12 เป็นจำนวนเต๊นท์ที่ต้องการในเดือนที่ i
t0 ; เป็นจำนวนเต๊นท์ที่เหลือจากปีที่แล้ว
cb ; ราคาซื้อเต๊นท์ / เต๊นท์
cs ; ราคาขายเต๊นท์ / เต๊นท์
ck ; ราคาเก็บเต๊นท์ที่ไม่ได้ใช้ / เดือน
ตัวแปร
t1 , … , t12 จำนวนเต๊นท์ที่เราครอบครองในเดือนที่ i
b1 , … , b12 จำนวนเต๊นท์ที่ซื้อในเดือนที่ i
s1 , … , s12 จำนวนเต๊นท์ที่ขายในเดือนที่ i
k1 , … , k12 จำนวนเต๊นท์ในโกดังในเดือนที่ i
จะได้ว่า
minimize: Image019.png
subject to:
ti ≥ di ; i = 1, … ,12
ki = ti - di ; i = 1, … ,12
ti – ti-1 ≤ bi
bi ≥ 0 ; i = 1, … ,12
ti-1 – ti ≤ si
si ≥ 0
ti ≥ 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