กลับไปหน้าบทความ

อ่าน 1 นาที

ความเป็นคู่ที่แข็งแกร่ง

ภาวะ ทวิลักษณ์ที่แข็งแกร่ง (Strong duality) เป็นเงื่อนไขใน การหาค่าเหมาะสมที่สุดทางคณิตศาสตร์ ซึ่งค่าเป้าหมายที่เหมาะสมที่สุดในปัญหาหลักและ ค่าเป้าหมายที่เหมาะสมที่สุดในปัญหา คู่...

ความเป็นคู่ที่แข็งแกร่ง

ภาวะ ทวิลักษณ์ที่แข็งแกร่ง (Strong duality)เป็นเงื่อนไขในการหาค่าเหมาะสมที่สุดทางคณิตศาสตร์ซึ่งค่าเป้าหมายที่เหมาะสมที่สุดในปัญหาหลักและ ค่าเป้าหมายที่เหมาะสมที่สุดในปัญหา คู่ ขนานนั้น เท่ากัน ตามคำนิยาม ภาวะทวิลักษณ์ที่แข็งแกร่งจะเป็นจริงก็ต่อเมื่อช่องว่างทวิลักษณ์ (Duality gap ) เท่ากับ 0 เท่านั้น ซึ่งตรงข้ามกับภาวะทวิลักษณ์ที่อ่อนแอ (Weak duality ) (ปัญหาหลักมีค่าเหมาะสมที่สุดมากกว่าหรือเท่ากับปัญหาคู่ขนาน กล่าวอีกนัยหนึ่ง คือ ช่องว่างทวิลักษณ์มากกว่าหรือเท่ากับศูนย์)

เงื่อนไขที่เพียงพอ

เงื่อนไขแต่ละข้อต่อไปนี้เพียงพอที่จะทำให้ทฤษฎีทวิภาวะแบบเข้มแข็ง (strong duality) เป็นจริงได้:

ความเป็นคู่ที่แข็งแกร่งและความซับซ้อนในการคำนวณ

ภายใต้เงื่อนไขบางประการ (เรียกว่า "คุณสมบัติข้อจำกัด") หากปัญหาสามารถแก้ไขได้ในเวลาพหุนาม ปัญหานั้นก็จะมีภาวะคู่ที่แข็งแกร่ง (ในความหมายของภาวะคู่แบบลากรางจ์ ) ยังคงเป็นคำถามที่เปิดกว้างว่าทิศทางตรงกันข้ามก็เป็นจริงด้วยหรือไม่ กล่าวคือ ภาวะคู่ที่แข็งแกร่งจะหมายถึงการแก้ไขได้ในเวลาพหุนามหรือไม่[ 3 ]

ดูเพิ่มเติม

ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Strong_duality&oldid=1322739391 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ ความเป็นคู่ที่แข็งแกร่ง

ภาวะ ทวิลักษณ์ที่แข็งแกร่ง (Strong duality) เป็นเงื่อนไขใน การหาค่าเหมาะสมที่สุดทางคณิตศาสตร์ ซึ่งค่าเป้าหมายที่เหมาะสมที่สุดในปัญหาหลักและ ค่าเป้าหมายที่เหมาะสมที่สุดในปัญหา คู่...

เงื่อนไขที่เพียงพอ

เงื่อนไขแต่ละข้อต่อไปนี้เพียงพอที่จะทำให้ทฤษฎีทวิภาวะแบบเข้มแข็ง (strong duality) เป็นจริงได้:

ความเป็นคู่ที่แข็งแกร่งและความซับซ้อนในการคำนวณ

ภายใต้เงื่อนไขบางประการ (เรียกว่า "คุณสมบัติข้อจำกัด") หากปัญหาสามารถแก้ไขได้ในเวลาพหุนาม ปัญหานั้นก็จะมีภาวะคู่ที่แข็งแกร่ง (ในความหมายของ ภาวะคู่แบบลากรางจ์ ) ยังคงเป็นคำถามที่เปิดกว้างว่าทิศทางตรงกันข้ามก็เป็นจริงด้วยหรือไม่ กล่าวคือ...

ดูเพิ่มเติม

การเพิ่มประสิทธิภาพแบบนูน การเขียนโปรแกรมเชิงเส้น #ความเป็นคู่ โปรแกรมเชิงเส้นคู่ ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Strong_duality&oldid=1322739391 "