204512/บรรยาย 10

จาก Theory Wiki
รุ่นแก้ไขเมื่อ 11:10, 23 กันยายน 2553 โดย Jittat (คุย | มีส่วนร่วม) (ย้อน)
(ต่าง) ←รุ่นแก้ไขก่อนหน้า | รุ่นแก้ไขล่าสุด (ต่าง) | รุ่นแก้ไขถัดไป→ (ต่าง)
ไปยังการนำทาง ไปยังการค้นหา

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

นายณัฐพล หล่อศิริ 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