ผลต่างระหว่างรุ่นของ "204512/บรรยาย 10"
Nut t02 (คุย | มีส่วนร่วม) |
Nut t02 (คุย | มีส่วนร่วม) |
||
| แถว 17: | แถว 17: | ||
=== <u>Linear Programming Problem</u> === | === <u>Linear Programming Problem</u> === | ||
Instant ของ linear programming คือ จำนวนเต็มบวก n, m, c ∈ R^n, b ∈ R^m และเมตริกซ์ A ของจำนวนจริงขนาด m x n จะได้ว่า | Instant ของ linear programming คือ จำนวนเต็มบวก n, m, c ∈ R^n, b ∈ R^m และเมตริกซ์ A ของจำนวนจริงขนาด m x n จะได้ว่า | ||
| − | :F = { x ← R | + | :F = { x ← R<sup>n</sup> :Ax = b , x ≥0 } |
| − | :Cost : x → c | + | :Cost : x → c<sup>Tx</sup> |
| แถว 27: | แถว 27: | ||
:หา x ที่ Ax = b ; x ≥ 0 แทนค่าจะได้<br> | :หา x ที่ Ax = b ; x ≥ 0 แทนค่าจะได้<br> | ||
:[[ภาพ:Image011.png]]<br> | :[[ภาพ:Image011.png]]<br> | ||
| − | :หา x ที่ทำให้ | + | :หา x ที่ทำให้ c<sub>1</sub>x<sub>1</sub> + c<sub>2</sub>x<sub>2</sub> + c<sub>3</sub>x<sub>3</sub> น้อยที่สุด |
| แถว 33: | แถว 33: | ||
*การเขียนในรูปแบบ ''สมการ''<br> | *การเขียนในรูปแบบ ''สมการ''<br> | ||
:- การระบุเซต F (เป็น constraint ของปัญหา) | :- การระบุเซต F (เป็น constraint ของปัญหา) | ||
| − | :: | + | ::x<sub>1</sub> + x<sub>2</sub> = 5 |
| − | :: | + | ::x<sub>3</sub> + x<sub>4</sub> – x<sub>2</sub> = 1 |
| − | :: | + | ::x<sub>1</sub> - x<sub>2</sub> + x<sub>3</sub> = 8 |
| − | :: | + | ::x<sub>5</sub> – x<sub>3</sub> = 7 |
| − | :: | + | ::x<sub>i</sub> ≥ 0 ทุกๆ 1 ≤ i ≤5 |
:- การระบุ c (เป็น objective ของปัญหา) | :- การระบุ c (เป็น objective ของปัญหา) | ||
| − | ::minimize: | + | ::minimize: x<sub>1</sub> + x<sub>2</sub> – x<sub>3</sub> + 2x<sub>4</sub> – 2x<sub>5</sub> |
*การเขียนในรูปแบบ ''เมตริกซ์''<br> | *การเขียนในรูปแบบ ''เมตริกซ์''<br> | ||
| แถว 45: | แถว 45: | ||
---- | ---- | ||
| + | |||
=== <u>Form ของ Linear Programming</u> === | === <u>Form ของ Linear Programming</u> === | ||
==== Standard form ==== | ==== Standard form ==== | ||
รุ่นแก้ไขเมื่อ 09:45, 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 ← Rn :Ax = b , x ≥0 }
- Cost : x → cTx
- ตัวอย่าง
กำหนดให้ 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
- minimize:
Canonical form
- เมตริกซ์
- minimize: cx
- subject to: Ax ≥ b ; x ≥ 0
- สมการ
- minimize:
- subject to:
เมื่อ j = 1,…,n
- minimize:
- ตัวอย่าง
- เตรียมสอบมีเวลาอ่านหนังสือ 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
- minimize:
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)
