204512-53/lecture12
Linear Programming
กำหนดการเชิงเส้น จะอยู่ในรูปแบบทางคณิตศาสตร์ของสมการเชิงเส้นและอสมการเชิงเส้น แล้วหาค่าสูงสุด ต่ำสุดของฟังก์ชันที่สอดคล้องกับสมการ (และอสมการ) ที่กำหนด ตัวแบบคณิตศาสตร์
การหาค่าสูงสุด : Maximize
โดยที่มีตัวแปร 2 แบบคือ
และเงื่อนไข อยู่ในรูป General Form
แปลงเป็น Minimum โดยการแปลงค่า โดยการคูณเครื่องหมายลบเข้าไปจะทำให้เปลี่ยนเครื่องหมายของอสมการเปลี่ยนไปในทางตรงข้าม
การคิดคำนวณด้วยวิธีการ Simplex ต้องเปลี่ยนระบบอสมการในโมเดลคณิตศาสตร์เชิงเส้นให้อยู่ในรูปของสมการเพื่อความง่ายต่อการคำนวณ โดยเพิ่มตัวแปรสมมติขึ้น รูปแบบของสมการจะขยายเพิ่มเติมขึ้นเราเรียกรูปแบบนี้ว่า “Slack Form”
หลักการเพิ่มตัวแปรใน Slack Form 1. ในอสมการเดิมที่อยู่ในรูปเครื่องหมายน้อยกว่าหรือเท่ากับ เราจะเปลี่ยนเป็นเครื่องหมายเท่ากับ ดังนั้น จึงต้องเพิ่มส่วนที่เหลือโดยการเพิ่มค่าเข้าไปอีก โดยตัวแปรที่เพิ่มค่าจึงมีเครื่องหมาย + นำหน้า เพื่อให้เหมือนกับว่าเพิ่มค่าให้ได้เท่ากับ 2. ในกรณีของอสมการในโมเดลคณิตศาสตร์เดิมอยู่ในรูปเครื่องหมายมากกว่าหรือเท่ากับ เปรียบว่าฝั่งซ้ายมากกว่าฝั่งขวา ดังนั้นการเปลี่ยนอสมการให้เป็นสมการจึงต้องลดลง ในที่นี้ต้องเติมตัวแปร Slack โดยมีเครื่องหมายลบนำหน้า แต่จากหลักการคำนวณทางแมทริกซ์ ตัวแปรที่ให้ผลลัพธ์แต่ละครั้งที่คำนวณหา จะมีสัมประสิทธิ์เท่ากับ + 1 ซึ่งเกิดเป็นแมทริกซ์ของสัมประสิทธิ์ของตัวแปรที่เป็นตัวแปรพื้นฐาน (basic variable) ตามข้อกำหนดของวิธีซิมเพล็กซ์ กำหนดว่า ผลลัพธ์เบื้องต้นที่เป็นไปได้จะมีค่าตัวแปรที่เป็นตัวแปรพื้นฐานมากกว่าหรือเท่ากับศูนย์ ดังนั้น จึงต้องเติมตัวแปรอีกตัวหนึ่งที่มีสัมประสิทธิ์เป็นบวก 3. ในกรณีที่เป็นสมการที่มีเครื่องหมาย เท่ากับ = อยู่แล้ว ให้เพิ่มตัวแปรได้เลย
ปัญหา เทพวิตามิน คนต้องการ 100 มก. มก. 500 มก.
แปลงให้อยู่ในรูป Matrix
ใน Case นี้ให้
สังเกตุที่ เพิ่ม ไปแล้ว มีค่าเพิ่มขึ้นเรื่อยๆ ซึ่งไม่มีผลอะไรเพราะมีค่ามากกว่าเท่ากับ 0 อยู่แล้ว
จากโจทย์ถ้าเพิ่ม จะมีผลกับ ส (-1) และ ส (-100)
แก้สมการเมตริกซ์จะได้
เพิ่ม ไป ซึ่งจะทำให้ค่า เป็น 0 เพิ่ม ไป ซึ่งจะทำให้ค่า เป็น 0
กำหนด x1, x2, x3 ซึ่งเรียกว่า Basic Solution ที่เป็น matrix Max C’x Subject to Ax = b x ≥ 0 เลือก B = {1,2,3}
โดยที่ C’ = เวกเตอร์แนวนอน, X = เวกเตอร์แนวตั้ง, A = คือ matrix มี ‘ เป็นแถวเวกเตอร์ ไม่มี ‘ เป็นหลักเวกเตอร์ , = Matrix A ที่หยิบมาเฉพาะหลักในเซต B , = เอาเฉพาะตัวแปรใน index B
เริ่มจาก basic feasible solution XB มี B เป็นเซตของ basis
ถ้า แสดงว่าปรับแล้วค่าไม่ดีขึ้น หยิบ 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
