'ไม่มีขอบเขต' (Unbounded) ในโปรแกรมเชิงเส้นหมายถึงอะไร?

LP จะไม่มีขอบเขตเมื่อพื้นที่ที่เป็นไปได้ขยายออกไปอย่างไม่สิ้นสุดในทิศทางที่ฟังก์ชันเป้าหมายดีขึ้นเรื่อยๆ เช่น Maximize x โดยมีข้อจำกัดเพียง x >= 0 จะไม่มีค่าสูงสุดที่แน่นอน ปัญหา LP ในโลกจริงที่ลืมใส่ข้อจำกัดมักจะแสดงอาการนี้ ตัวแก้ปัญหาจะระบุสิ่งนี้ในระหว่างการทดสอบอัตราส่วนซิมเพล็กซ์เมื่อไม่มีตัวแปรที่จะออกจากฐาน

'คำตอบที่เหมาะสมหลายค่า' (Alternate optima) หมายถึงอะไร?

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

ตัวแก้ปัญหาโปรแกรมเชิงเส้น

แก้ปัญหาโปรแกรมเชิงเส้นออนไลน์โดยใช้วิธี Simplex รองรับวัตถุประสงค์แบบหาค่าสูงสุด (Maximize) หรือค่าต่ำสุด (Minimize) เงื่อนไขบังคับแบบผสม ≤/≥/= รองรับตัวแปรตัดสินใจสูงสุด 8 ตัว และสำหรับปัญหา LP แบบ 2 ตัวแปร จะแสดงแผนภาพอาณาบริเวณที่เป็นไปได้แบบโต้ตอบพร้อมจุดยอดทุกจุดและจุดที่เหมาะสมที่สุด

ตัวอย่างด่วน:

กำไรสูงสุด (2 ตัวแปร) ต้นทุนต่ำสุด (ปัญหาโภชนาการ) การผสมผลิตภัณฑ์ LP แบบ 3 ตัวแปร พร้อมข้อจำกัดแบบสมการ

โจทย์ปัญหาโปรแกรมเชิงเส้น

บรรทัดแรกคือฟังก์ชันเป้าหมาย (Maximize หรือ Minimize …) แต่ละบรรทัดถัดไปคือข้อจำกัดเชิงเส้น ใช้ <=, >=, หรือ = ตัวย่อ: x, y >= 0 ใช้กำหนดค่าไม่เป็นลบสำหรับหลายตัวแปรพร้อมกัน สูงสุด 8 ตัวแปร และ 20 ข้อจำกัด

Embed ตัวแก้ปัญหาโปรแกรมเชิงเส้น Widget

เกี่ยวกับ ตัวแก้ปัญหาโปรแกรมเชิงเส้น

ตัวแก้ปัญหาโปรแกรมเชิงเส้น คือเครื่องคำนวณออนไลน์ที่หาค่าสูงสุดหรือต่ำสุดของฟังก์ชันเป้าหมายเชิงเส้นภายใต้ระบบของอสมการหรือสมการเชิงเส้น โดยใช้วิธี วิธีซิมเพล็กซ์ (ตัวแปร Big-M) เพื่อให้สามารถผสมข้อจำกัดแบบ <=, >=, และ = ได้อย่างอิสระ และสำหรับปัญหาแบบ 2 ตัวแปร จะมีการวาดแผนภาพพื้นที่ที่เป็นไปได้แบบโต้ตอบพร้อมไฮไลต์ทุกจุดยอดและจุดที่เหมาะสมที่สุด

โปรแกรมเชิงเส้นคืออะไร?

ปัญหาโปรแกรมเชิงเส้น (LP) ถามว่า:

Maximize (หรือ minimize): Z = c₁ x₁ + c₂ x₂ + … + c_n x_n ภายใต้เงื่อนไข: a₁₁ x₁ + … + a_1n x_n (≤, ≥, หรือ =) b₁ a₂₁ x₁ + … + a_2n x_n (≤, ≥, หรือ =) b₂ … a_m1 x₁ + … + a_mn x_n (≤, ≥, หรือ =) b_m x₁, x₂, …, x_n ≥ 0

ชุดของจุดที่เป็นไปตามทุกข้อจำกัดเรียกว่า พื้นที่ที่เป็นไปได้ (Feasible Region) ซึ่งมีลักษณะเป็นรูปทรงหลายเหลี่ยมนูน ทฤษฎีบทพื้นฐานของโปรแกรมเชิงเส้น ระบุว่าหาก LP มีคำตอบที่เหมาะสมที่สุดที่จำกัด คำตอบนั้นจะอยู่ที่จุดยอด (Extreme point) ของรูปทรงหลายเหลี่ยมนี้เสมอ นี่คือเหตุผลที่วิธีซิมเพล็กซ์ — ซึ่งเดินจากจุดยอดหนึ่งไปยังอีกจุดยอดหนึ่ง — จึงมีประสิทธิภาพมาก

วิธีซิมเพล็กซ์ทำงานอย่างไร

เริ่มจากจุดยอดที่เป็นไปได้ วิธีซิมเพล็กซ์จะปรับปรุงค่าเป้าหมายซ้ำๆ โดยการ Pivot ไปยังจุดยอดข้างเคียงที่มีค่าดีกว่า กลไกประกอบด้วย:

รูปแบบมาตรฐาน: แปลง LP เป็น max c^Tx ภายใต้ Ax = b, x ≥ 0 สำหรับข้อจำกัด <= ให้เพิ่มตัวแปร ช่วย (slack); สำหรับ >= ให้ลบตัวแปร ส่วนเกิน (surplus) และเพิ่มตัวแปร เทียม (artificial) พร้อมค่าปรับ −M ขนาดใหญ่; สำหรับสมการ ให้เพิ่มตัวแปรเทียม
ตารางเริ่มต้น: ฐานจะประกอบด้วยตัวแปรช่วยและตัวแปรเทียม ซึ่งให้จุดยอดเริ่มต้นที่เห็นได้ชัดเจน
ตัวแปรเข้า: เลือกตัวแปรที่ไม่ได้อยู่ในฐานที่มีต้นทุนลดลงเป็นบวกมากที่สุด $ c_j - z_j $ หากไม่มีตัวแปรดังกล่าว แสดงว่าคำตอบปัจจุบันเหมาะสมที่สุดแล้ว
ตัวแปรออก: จากคอลัมน์ตัวแปรเข้า ให้ทำ การทดสอบอัตราส่วนขั้นต่ำ — หาร RHS ของแต่ละแถวด้วยค่าบวกในคอลัมน์ตัวแปรเข้า และเลือกแถวที่มีอัตราส่วนน้อยที่สุด หากไม่มีค่าบวกอยู่เลย แสดงว่า LP นั้น ไม่มีขอบเขต
Pivot: ใช้การกำจัดแบบเกาส์เซียนเพื่อให้คอลัมน์ตัวแปรเข้ากลายเป็นเวกเตอร์หน่วย โดยมีค่าเป็น 1 ในแถวตัวแปรออก
ทำซ้ำจนกว่าจะตรงตามเกณฑ์การหยุด

หากมีตัวแปรเทียมหลงเหลืออยู่ในฐานที่มีค่าเป็นบวกเมื่อสิ้นสุดการทำงาน แสดงว่า LP เดิมนั้น เป็นไปไม่ได้ (infeasible)

วิธีเชิงกราฟิก (สำหรับ 2 ตัวแปร)

สำหรับปัญหาที่มีสองตัวแปร พื้นที่ที่เป็นไปได้คือรูปหลายเหลี่ยมนูน 2 มิติ เนื่องจากคำตอบที่เหมาะสมที่สุดจะอยู่ที่จุดยอดเสมอ การไล่เรียงทุกจุดยอดและประเมินค่าฟังก์ชันเป้าหมายที่จุดนั้นจึงเพียงพอต่อการแก้ปัญหา เครื่องคำนวณนี้ทำการไล่เรียงโดยหาจุดตัดของคู่ขอบเขตข้อจำกัดทุกคู่ เก็บเฉพาะจุดตัดที่สอดคล้องกับข้อจำกัดอื่นๆ ทั้งหมด และจัดเรียงตามเข็มนาฬิกาเพื่อการแสดงภาพ

ไวยากรณ์การป้อนข้อมูล

เขียน ฟังก์ชันเป้าหมาย ในบรรทัดแรก จากนั้นใส่ หนึ่งข้อจำกัดต่อหนึ่งบรรทัด ชื่อตัวแปรสามารถเป็นตัวระบุใดก็ได้ (x, y, x1, profit…) ตัวดำเนินการคือ <=, >=, และ = ค่าไม่เป็นลบสามารถเขียนเป็น x, y >= 0 เป็นตัวย่อได้

Maximize 3x + 5y x + y <= 10 2x + y <= 16 x + 3y <= 18 x, y >= 0

บรรทัดว่างและคอมเมนต์ที่ขึ้นต้นด้วย # จะถูกละเว้น ตัวแก้ปัญหารองรับตัวแปรตัดสินใจสูงสุด 8 ตัว และข้อจำกัด 20 ข้อ

ตัวอย่างโจทย์

พิจารณาโรงงานเฟอร์นิเจอร์ที่ผลิตโต๊ะและเก้าอี้ โต๊ะแต่ละตัวได้กำไร \$3 และต้องการไม้ 1 หน่วย แรงงาน 2 หน่วย เก้าอี้แต่ละตัวได้กำไร \$5 และต้องการไม้ 1 หน่วย แรงงาน 1 หน่วย และน้ำมันวานิช 3 หน่วย ทรัพยากรที่มี: ไม้ 10 หน่วย, แรงงาน 16 หน่วย, วานิช 18 หน่วย กำหนดให้ x = โต๊ะ และ y = เก้าอี้ โจทย์ LP คือ:

Maximize Z = 3x + 5y x + y <= 10 (ไม้) 2x + y <= 16 (แรงงาน) x + 3y <= 18 (วานิช) x, y >= 0

พื้นที่ที่เป็นไปได้คือรูปห้าเหลี่ยม ประเมินค่า Z ที่แต่ละจุดยอด:

จุดยอด (x, y)	Z = 3x + 5y	เป็นไปได้หรือไม่?
(0, 0)	0	ใช่
(8, 0)	24	ใช่
(6, 4)	38 ← เหมาะสมที่สุด	ใช่
(0, 6)	30	ใช่

ดังนั้นโรงงานควรผลิต โต๊ะ 6 ตัว และเก้าอี้ 4 ตัว เพื่อกำไรสูงสุด \$38 ข้อจำกัดเรื่องไม้และแรงงานนั้น มีผล (binding) (มีค่าเท่ากับ RHS ที่จุดเหมาะสมที่สุด); วานิชมีส่วนช่วยเป็น 0 (ในกรณีนี้ก็มีผลเช่นกัน) หมายความว่าทรัพยากรทั้งสามอย่างถูกใช้จนหมด

ข้อผิดพลาดที่พบบ่อยและสิ่งที่ตัวแก้ปัญหาตรวจพบ

สถานการณ์	อาการ	วิธีแก้ไข
LP ไม่มีขอบเขต	ตัวแก้ปัญหารายงาน "ไม่มีขอบเขต" (Unbounded)	เพิ่มข้อจำกัดขอบเขตบนที่ขาดหายไป ค่าเป้าหมายสามารถเติบโตได้โดยไม่มีที่สิ้นสุดเนื่องจากพื้นที่ที่เป็นไปได้ขยายออกไปไม่หยุดในทิศทางที่ค่าดีขึ้น
LP เป็นไปไม่ได้	ตัวแก้ปัญหารายงาน "เป็นไปไม่ได้" (Infeasible)	ข้อจำกัดขัดแย้งกันเอง (เช่น `x >= 10` ร่วมกับ `x <= 5`) โปรดตรวจสอบคู่ของขอบเขตทุกคู่
คำตอบที่เหมาะสมหลายค่า	ป้ายเตือน; จุดยอดที่เหมาะสมที่สุดมีมากกว่าหนึ่งจุด แต่ Z ที่ได้จะเท่ากันตลอดทั้งขอบ	เกิดขึ้นเมื่อเวกเตอร์ฟังก์ชันเป้าหมายขนานกับขอบของข้อจำกัดที่มีผล จุดผสมนูน (Convex combination) ใดๆ ของจุดยอดสองจุดบนขอบนั้นจะเหมาะสมที่สุดทั้งหมด
การเสื่อมถอย / การวนซ้ำไม่สิ้นสุด	ซิมเพล็กซ์วนซ้ำโดยไม่ปรับปรุงค่า Z	พบได้ยากในโจทย์ตำรา สามารถแก้ไขได้ด้วยกฎของ Bland หรือการรบกวน (Perturbation) ตัวแก้ปัญหานี้จำกัดจำนวนรอบการวนซ้ำเพื่อหลีกเลี่ยงการวนลูปไม่รู้จบ

การประยุกต์ใช้งาน

การผสมผลิตภัณฑ์และการวางแผนการผลิต — วิธีผลิตสินค้าแต่ละชนิดเพื่อให้ได้กำไรสูงสุดภายใต้ทรัพยากรที่จำกัด
ปัญหาโภชนาการและการผสม — ลดต้นทุนอาหารหรือวัตถุดิบให้น้อยที่สุดโดยที่ยังคงได้รับสารอาหารตามเกณฑ์ขั้นต่ำ
การขนส่งและการมอบหมายงาน — ลดต้นทุนการขนส่งเมื่ออุปทานและอุปสงค์ต้องสมดุลกัน
การเพิ่มประสิทธิภาพพอร์ตโฟลิโอ — เพิ่มผลตอบแทนที่คาดหวังสูงสุดภายใต้ข้อจำกัดด้านความเสี่ยง (ในรูปแบบเชิงเส้น)
การไหลในเครือข่าย — ปัญหาการไหลสูงสุด (Max-flow) และการไหลที่ต้นทุนต่ำสุด ซึ่งลดรูปเป็น LP ได้
การจัดตารางเวลา — การจัดตารางเวรคนงานตามความต้องการในแต่ละกะและขอบเขตชั่วโมงทำงานรวม

วิธีใช้งานเครื่องคำนวณนี้

พิมพ์โจทย์ LP ของคุณ ในช่องข้อความ บรรทัดแรกต้องขึ้นต้นด้วย Maximize หรือ Minimize บรรทัดถัดมาแต่ละบรรทัดคือหนึ่งข้อจำกัด
ใช้ตัวย่อ x, y >= 0 เพื่อประกาศค่าไม่เป็นลบสำหรับตัวแปรทั้งหมดที่ระบุพร้อมกัน
คลิก 'แก้ปัญหา LP' ตัวแก้ปัญหาจะรายงานค่าที่เหมาะสมที่สุด Z, ค่าที่เหมาะสมของแต่ละตัวแปรตัดสินใจ, รายการข้อจำกัดที่มีผล และแผนภาพพื้นที่ที่เป็นไปได้สำหรับ LP แบบ 2 ตัวแปร
วางเมาส์บนจุดยอด ในแผนภาพเพื่อดูพิกัดและค่า Z จุดที่เหมาะสมที่สุดจะถูกไฮไลต์ด้วยดาว
ตรวจสอบตารางซิมเพล็กซ์ เพื่อดูการ Pivot ในแต่ละขั้นตอนและติดตามว่าวิธีนี้ปรับปรุงค่า Z อย่างไร คอลัมน์เข้าจะถูกไฮไลต์ด้วยสีเหลืองอำพัน และแถวออกจะถูกไฮไลต์ด้วยสีแดง

คำถามที่พบบ่อย

ปัญหาโปรแกรมเชิงเส้นคืออะไร?

ปัญหาโปรแกรมเชิงเส้น (LP) คือการหาค่าสูงสุดหรือต่ำสุดของฟังก์ชันเป้าหมายเชิงเส้นบนชุดของตัวแปรตัดสินใจที่เป็นไปตามระบบอสมการหรือสมการเชิงเส้น พื้นที่ที่เป็นไปได้คือรูปทรงหลายเหลี่ยมนูน และค่าที่เหมาะสมที่สุดจะอยู่ที่จุดยอดจุดใดจุดหนึ่งเสมอ — ซึ่งเป็นข้อเท็จจริงสำคัญที่วิธีซิมเพล็กซ์นำมาใช้

วิธีซิมเพล็กซ์ทำงานอย่างไร?

วิธีซิมเพล็กซ์จะเดินไปตามจุดยอดของรูปทรงหลายเหลี่ยมที่เป็นไปได้ แต่ละขั้นตอน (การ "Pivot") จะเปลี่ยนตัวแปรในฐานหนึ่งตัวกับตัวแปรอื่น เพื่อย้ายไปยังจุดยอดข้างเคียงที่มีค่าเป้าหมายดีกว่า อัลกอริทึมจะหยุดเมื่อไม่มีการ Pivot ใดที่สามารถปรับปรุง Z ได้อีก — จุดยอดนั้นจึงเป็นจุดที่เหมาะสมที่สุด เครื่องมือนี้ใช้ Big-M เพื่อให้ผสมข้อจำกัด <=, >=, และ = ได้

พื้นที่ที่เป็นไปได้คืออะไร?

พื้นที่ที่เป็นไปได้คือชุดของค่าตัวแปรทั้งหมดที่สอดคล้องกับทุกข้อจำกัดพร้อมกัน สำหรับ 2 ตัวแปรจะเป็นรูปหลายเหลี่ยมนูน 2 มิติ สำหรับ n ตัวแปรจะเป็นรูปทรงหลายเหลี่ยม n มิติ หากรูปทรงหลายเหลี่ยมว่างเปล่าหมายถึง LP เป็นไปไม่ได้; หากรูปทรงหลายเหลี่ยมขยายไปอย่างไม่มีที่สิ้นสุดในทิศทางที่ค่าดีขึ้นหมายถึง LP ไม่มีขอบเขต

"ไม่มีขอบเขต" ในโปรแกรมเชิงเส้นหมายถึงอะไร?

LP จะไม่มีขอบเขตเมื่อพื้นที่ที่เป็นไปได้ยืดออกไปถึงอินฟินิตี้ในทิศทางที่ค่าเป้าหมายดีขึ้นเรื่อยๆ เช่น Maximize x ภายใต้เงื่อนไข x ≥ 0 เพียงอย่างเดียว จะไม่มีค่าสูงสุดที่แน่นอน ปัญหา LP ในโลกจริงที่ไม่มีขอบเขตมักจะแสดงว่าลืมใส่ข้อจำกัดบางอย่าง — บ่อยครั้งคือขอบเขตบนของทรัพยากรหรือตัวแปร

"คำตอบที่เหมาะสมหลายค่า" หมายถึงอะไร?

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

ตัวแก้ปัญหานี้รับตัวแปรและข้อจำกัดได้เท่าไหร่?

สูงสุด 8 ตัวแปรตัดสินใจ และ 20 ข้อจำกัด แผนภาพพื้นที่ที่เป็นไปได้จะวาดสำหรับโจทย์ 2 ตัวแปรเท่านั้น สำหรับ 3 ตัวแปรขึ้นไป คุณจะยังได้รับผลลัพธ์เชิงตัวเลขของซิมเพล็กซ์ ตารางทีละขั้นตอน และรายงานข้อจำกัดที่มีผลอย่างครบถ้วน