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

F = { x ∈ Rⁿ :Ax = b , x ≥0 }

Cost : x → c'x

ตัวอย่าง

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

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

หา x ที่ทำให้ $c_{1}x_{1}$ + $c_{2}x_{2}$ + $c_{3}x_{3}$ น้อยที่สุด

ตัวอย่าง

• การเขียนในรูปแบบ สมการ
  

- การระบุเซต F (เป็น constraint ของปัญหา)

$x_{1}$ + $x_{2}$ = 5

$x_{3}$ + $x_{4}$ – $x_{2}$ = 1

$x_{1}$ - $x_{2}$ + $x_{3}$ = 8

$x_{5}$ – $x_{3}$ = 7

$x_{i}$ ≥ 0 ทุกๆ 1 ≤ i ≤5

- การระบุ c (เป็น objective ของปัญหา)

minimize: $x_{1}$ + $x_{2}$ – $x_{3}$ + $x_{4}$ – $x_{5}$

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

, ,

---

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 ชม.

ถ้าให้

$x_{1}$ = เวลาอ่าน Architect

$x_{2}$ = เวลาอ่าน Algo

$x_{3}$ = เวลาอ่าน Soft Com.

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

minimize: $x_{1}$ + 5$x_{2}$ + 2$x_{3}$

subject to:

$x_{1}$ + $x_{2}$ + $x_{3}$ ≤ 12

$x_{1}$ ≥ 1

$x_{2}$ ≥ 1

$x_{3}$ ≥ 1

$x_{1}$ + $x_{2}$ ≥ 5

$x_{3}$ ≤ 8

$x_{1}$ , $x_{2}$ , $x_{3}$ ≥ 0

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

minimize: $x_{1}$ + 5$x_{2}$ + 2$x_{3}$

subject to:

จาก $x_{1}$ + $x_{2}$ + $x_{3}$ ≤ 12 เอา -1 คูณตลอดจะได้

$-x_{1}$ + $-x_{2}$ + $-x_{3}$ ≥ -12

จาก$x_{3}$ ≤ 8 เอา -1 คูณตลอดจะได้

$-x_{3}$ ≥ -8

$x_{1}$ ≥ 1

$x_{2}$ ≥ 1

$x_{3}$ ≥ 1

$x_{1}$ + $x_{2}$ ≥ 5

$x_{1}$ , $x_{2}$ , $x_{3}$ ≥ 0

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

ตัวอย่าง

บริษัทเช่าเต๊นท์มหาสนุกจำกัด รับจัดหาเต็นท์ในเดือนๆหนึ่งมีเต็นท์ใช้ได้ไม่น้อยกว่าจำนวนที่ใช้ โดยมีเงื่อนไขว่าเต็นท์ซื้อขายได้ เก็บเต็นท์ในโกดังคิดค่าเช่าโกดัง จะซื้อขายหรือเก็บเต็นท์ยังไงให้ได้กำไรมากที่สุด

กำหนด

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

$t_{0}$ ; เป็นจำนวนเต๊นท์ที่เหลือจากปีที่แล้ว

$c_{b}$ ; ราคาซื้อเต๊นท์ / เต๊นท์

$c_{s}$ ; ราคาขายเต๊นท์ / เต๊นท์

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

ตัวแปร

$t_{1}$ , … , $t_{1}2$ จำนวนเต๊นท์ที่เราครอบครองในเดือนที่ i

$b_{1}$ , … , $b_{1}2$ จำนวนเต๊นท์ที่ซื้อในเดือนที่ i

$s_{1}$ , … , $s_{1}2$ จำนวนเต๊นท์ที่ขายในเดือนที่ i

$k_{1}$ , … , $k_{1}2$ จำนวนเต๊นท์ในโกดังในเดือนที่ i

จะได้ว่า

minimize:

subject to:

$t_{i}$ ≥ $d_{i}$ ; i = 1, … ,12

$k_{i}$ = $t_{i}$ - $d_{i}$ ; i = 1, … ,12

$t_{i}$ – $t_{i}$-1 ≤ $b_{i}$

$b_{i}$ ≥ 0 ; i = 1, … ,12

$t_{i}$-1 – $t_{i}$ ≤ $s_{i}$

$s_{i}$ ≥ 0

$t_{i}$ ≥ 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