204512/บรรยาย 10

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

นายณัฐพล หล่อศิริ 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 เขียนเป็นเมตริกซ์ ได้เป็น

หา x ที่ Ax = b ; x ≥ 0 แทนค่าจะได้

หา 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

• การเขียนในรูปแบบ เมตริกซ์
  

, ,

---

Form ของ Linear Programming

Standard form

เมตริกซ์

minimize: cx

subject to: Ax = b ; x ≥ 0

สมการ

minimize:

subject to: เมื่อ j = 1,…,n

Canonical form

เมตริกซ์

minimize: cx

subject to: Ax ≥ b ; x ≥ 0

สมการ

minimize:

subject to: เมื่อ 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 ได้

ตัวอย่าง

บริษัทเช่าเต๊นท์มหาสนุกจำกัด

กำหนด

di ; i = 1, … ,12 เป็นจำนวนเต๊นท์ที่ต้องการในเดือนที่ i

t0 ; เป็นจำนวนเต๊นท์ที่เหลือจากปีที่แล้ว

cb ; ราคาซื้อเต๊นท์ / เต๊นท์

cs ; ราคาขายเต๊นท์ / เต๊นท์

ck ; ราคาเก็บเต๊นท์ที่ไม่ได้ใช้ / เดือน

ตัวแปร

t1 , … , t12 จำนวนเต๊นท์ที่เราครอบครองในเดือนที่ i

b1 , … , b12 จำนวนเต๊นท์ที่ซื้อในเดือนที่ i

s1 , … , s12 จำนวนเต๊นท์ที่ขายในเดือนที่ i

k1 , … , k12 จำนวนเต๊นท์ในโกดังในเดือนที่ i

จะได้ว่า

minimize:

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

ตัวอย่าง

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

maximize:

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 หน่วย

วิธีทำ

ให้ตัวแปร

minimize:

subject to:

(เขียนแบบ integer programming)

(เขียนแบบ linear programming)

---

Duality

ตัวอย่าง

minimize: 7x₁ + x₂ + 5x₃

subject to:

x₁ – x₂ + 3x₃ ≥ 10 …(1)

5x₁ + 2x₂ – x₃ ≥ 6 …(2)

x₁, x₂, x₃ ≥ 0

ค่า objective ของคำตอบที่ดีที่สุด = Z^*

สมมติ   แล้วบอกได้ว่า Z* ≤ 30

(1)x 2 + (2);   7x₁ + 5x₃ ≥ 26

สังเกตว่าคล้ายๆ minimize เพราะฉะนั้นบอกได้ว่า lower bound เป็น 26

(1)x y₁ →   y₁x₁ – y₁x₂ + 3y₁x₃ ≥ 10y₁

(2)x y₂ →   5y₂x₁ + 2y₂x₂ – y₂x₃ ≥ 6y₂

ต้องการ สัมประสิทธิ์ของ x₁ = 7, สัมประสิทธิ์ของ x₂ = 1, สัมประสิทธิ์ของ x₃ = 5

เพราะฉะนั้นจะสร้าง linear program ได้อีกอันว่า

maximize: 10y₁ + 6y₂

subject to:

y₁ + 5y₂ ≤ 7 …(3)

-y₁ + 2y₂ ≤ 1 …(4)

3y₁ - y₂ ≤ 5 …(5)

y₁, y₂ ≥ 0

ค่า objective ของคำตอบที่ดีที่สุด = A^*

เพราะฉะนั้น A^* = Z^* จะเรียกว่า strong duality

โดย

สมการที่ (1), (2) จะเรียกว่า Primal

สมการที่ (3), (4), (5) จะเรียกว่า Dual

---

Primal Linear Programming

minimize:

subject to:

  ; i = 1,…,m

x_i ≥ 0  ; j = 1,…,n

---

Dual Linear Programming

maximize:

subject to:

  ; j = 1,…,n

y_i ≥ 0  ; i = 1,…,m

---

Max flow & Min Cut

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

primal

maximize:  

subject to:

  

  f_p ≥ 0

dual

กำหนดตัวแปร d_e สำหรับ edge e

minimize:  

subject to:

  

  d_e ≥ 0

ดังนั้นสรุปได้ว่า Min Cut เป็น Dual ของ Max Flow

ตัวอย่าง

primal

minimize: 2x₁ + 5x₂

subject to:

x₁ + x₂ ≥ 5 …y1

-x₁ + x₂ ≥ -1 …y2

x₁ + 2x₂ ≥ 4 …y3

x₁, x₂ ≥ 0

แปลงเป็น dual ได้ว่า

dual

maximize: 5y₁ – y₂ + 4y₃

subject to:

y₁ – y₂ + y₃ ≤ 2

y₁ + y₂ + 2y₃ ≤ 5

y₁, y₂, y₃ ≥ 0