204512/บรรยาย 10

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

เนื้อหา

1 Linear Programming
2 Integer Programming
- 2.1 Assignment Problem
3 Duality

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

ตัวอย่าง

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

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

หา x ที่ทำให้ c₁x₁ + c₂x₂ + c₃x₃ น้อยที่สุด

ตัวอย่าง

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

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

x₁ + x₂ = 5

x₃ + x₄ – x₂ = 1

x₁ - x₂ + x₃ = 8

x₅ – x₃ = 7

x_i ≥ 0 ทุกๆ 1 ≤ i ≤5

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

minimize: x₁ + x₂ – x₃ + 2x₄ – 2x₅

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

,

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
จะได้ว่า