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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 155: แถว 155:
 
::[[ภาพ:Image029.png]] (เขียนแบบ integer programming)
 
::[[ภาพ:Image029.png]] (เขียนแบบ integer programming)
 
::[[ภาพ:Image030.png]] (เขียนแบบ linear programming)
 
::[[ภาพ:Image030.png]] (เขียนแบบ linear programming)
 +
 +
----
 +
== Duality ==

รุ่นแก้ไขเมื่อ 09:38, 2 กันยายน 2550

บันทึกโดย : นายณัฐพล หล่อศิริ 50653781 , ...


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^Tx


ตัวอย่าง

กำหนดให้ 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