204512/บรรยาย 10

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

นายณัฐพล หล่อศิริ 50653781 และ

นายวรวุทธ นัมคนิสรณ์ 50653898

เนื้อหา

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