204512-53/lecture12

Linear Programming

กำหนดการเชิงเส้น จะอยู่ในรูปแบบทางคณิตศาสตร์ของสมการเชิงเส้นและอสมการเชิงเส้น แล้วหาค่าสูงสุด ต่ำสุดของฟังก์ชันที่สอดคล้องกับสมการ (และอสมการ) ที่กำหนด ตัวแบบคณิตศาสตร์

การหาค่าสูงสุด : Maximize $\sum _{i}{c_{i}x_{i}}$

โดยที่มีตัวแปร 2 แบบคือ

และเงื่อนไข อยู่ในรูป General Form

แปลงเป็น Minimum โดยการแปลงค่า $\sum _{i}{c_{i}x_{i}}$ โดยการคูณเครื่องหมายลบเข้าไปจะทำให้เปลี่ยนเครื่องหมายของอสมการเปลี่ยนไปในทางตรงข้าม

การคิดคำนวณด้วยวิธีการ Simplex ต้องเปลี่ยนระบบอสมการในโมเดลคณิตศาสตร์เชิงเส้นให้อยู่ในรูปของสมการเพื่อความง่ายต่อการคำนวณ โดยเพิ่มตัวแปรสมมติขึ้น รูปแบบของสมการจะขยายเพิ่มเติมขึ้นเราเรียกรูปแบบนี้ว่า “Slack Form”

หลักการเพิ่มตัวแปรใน Slack Form 1. ในอสมการเดิมที่อยู่ในรูปเครื่องหมายน้อยกว่าหรือเท่ากับ เราจะเปลี่ยนเป็นเครื่องหมายเท่ากับ ดังนั้น จึงต้องเพิ่มส่วนที่เหลือโดยการเพิ่มค่าเข้าไปอีก โดยตัวแปรที่เพิ่มค่าจึงมีเครื่องหมาย + นำหน้า เพื่อให้เหมือนกับว่าเพิ่มค่าให้ได้เท่ากับ 2. ในกรณีของอสมการในโมเดลคณิตศาสตร์เดิมอยู่ในรูปเครื่องหมายมากกว่าหรือเท่ากับ เปรียบว่าฝั่งซ้ายมากกว่าฝั่งขวา ดังนั้นการเปลี่ยนอสมการให้เป็นสมการจึงต้องลดลง ในที่นี้ต้องเติมตัวแปร Slack โดยมีเครื่องหมายลบนำหน้า แต่จากหลักการคำนวณทางแมทริกซ์ ตัวแปรที่ให้ผลลัพธ์แต่ละครั้งที่คำนวณหา จะมีสัมประสิทธิ์เท่ากับ + 1 ซึ่งเกิดเป็นแมทริกซ์ของสัมประสิทธิ์ของตัวแปรที่เป็นตัวแปรพื้นฐาน (basic variable) ตามข้อกำหนดของวิธีซิมเพล็กซ์ กำหนดว่า ผลลัพธ์เบื้องต้นที่เป็นไปได้จะมีค่าตัวแปรที่เป็นตัวแปรพื้นฐานมากกว่าหรือเท่ากับศูนย์ ดังนั้น จึงต้องเติมตัวแปรอีกตัวหนึ่งที่มีสัมประสิทธิ์เป็นบวก 3. ในกรณีที่เป็นสมการที่มีเครื่องหมาย เท่ากับ = อยู่แล้ว ให้เพิ่มตัวแปรได้เลย

ปัญหา เทพวิตามิน คนต้องการ $v_{A}$ 100 มก. $v_{B}70$ มก. $v_{C}$ 500 มก.

แปลงให้อยู่ในรูป Matrix

ใน Case นี้ให้ $x_{4}=0$

$x_{1}=235/36,x_{2}=96/72,x_{3}=5/42$

สังเกตุที่ $x_{3}$ เพิ่ม$x_{4}$ ไปแล้ว $x_{3}$ มีค่าเพิ่มขึ้นเรื่อยๆ ซึ่งไม่มีผลอะไรเพราะมีค่ามากกว่าเท่ากับ 0 อยู่แล้ว

จากโจทย์ถ้าเพิ่ม $x_{4}$ จะมีผลกับ ส$_{2}$ (-1) และ ส$_{3}$ (-100)

แก้สมการเมตริกซ์จะได้ $d_{1}=(-131)/72,d_{2}=(-7)/144,d_{3}=83/144$

เพิ่ม $x_{4}$ ไป ซึ่งจะทำให้ค่า $x_{1}$ เป็น 0 เพิ่ม $x_{4}$ ไป ซึ่งจะทำให้ค่า $x_{2}$ เป็น 0

กำหนด x1, x2, x3 ซึ่งเรียกว่า Basic Solution ที่เป็น matrix Max C’x Subject to Ax = b x ≥ 0 เลือก B = {1,2,3}

โดยที่ C’ = เวกเตอร์แนวนอน, X = เวกเตอร์แนวตั้ง, A = คือ matrix มี ‘ เป็นแถวเวกเตอร์ ไม่มี ‘ เป็นหลักเวกเตอร์ , $A_{B}$ = Matrix A ที่หยิบมาเฉพาะหลักในเซต B , $X_{B}$ = เอาเฉพาะตัวแปรใน index B

เริ่มจาก basic feasible solution XB มี B เป็นเซตของ basis $A_{B}X_{B}=b$

ถ้า แสดงว่าปรับแล้วค่าไม่ดีขึ้น หยิบ field ไหนก็ได้ < 0 พิจารณา x ใดๆ ที่เป็น Basis Feasible Solution

Ax = b x ≥ 0

พิจารณา x’b ใดๆ ที่เป็น Basis Physical Solution Ax = b x ≥ 0

เกมส์วิตามิน (ต่อ) : ในกรณีที่ต้องการกินวิตามินให้ได้ครบ

มองในแง่คนขาย ถ้าต้องการขายวิตามินให้ได้ราคาดีที่สุด

เป็นการแปลงจากแถวเป็นหลักและทำให้ Objective เปลี่ยนไปซึ่งคุณสมบัตินี้เราเรียกว่า Dual Linear Programing

นฤดล ขจรวุฒิตระกูล 5214550154 รัตนพงษ์ ชัยรักษ์วัฒนา 5214550243 ศักดา เอื้อจิรกาล 5214550286 สยาม ชุณห์วิจิตรา 5214550294 สุเกติองค์ ภู่พัฒน์ 5214550316