อัลกอริทึมไขว้

Q: ประวัติศาสตร์

อัลกอริทึมไขว้ได้รับการเผยแพร่โดยอิสระโดย Tamas Terlaky [ 9 ] และโดย Zhe-Min Wang; [ 10 ] อัลกอริทึมที่เกี่ยวข้องปรากฏในรายงานที่ยังไม่ได้เผยแพร่โดยผู้เขียนอื่น [ 3 ]

ลูกบาศก์สามมิติ — อัลกอริทึมแบบไขว้จะเยี่ยมชมมุมทั้ง 8 มุมของลูกบาศก์ Klee–Mintyในกรณีที่เลวร้ายที่สุด โดยเฉลี่ยแล้วจะเยี่ยมชมมุมเพิ่มอีก 3 มุม ลูกบาศก์ Klee–Minty เป็นลูกบาศก์ที่มีการรบกวนจากลูกบาศก์ที่แสดงไว้ในที่นี้

ในการเพิ่มประสิทธิภาพทางคณิตศาสตร์อัลกอริทึมไขว้เป็นตระกูลของอัลกอริทึมสำหรับการเขียนโปรแกรมเชิงเส้นตัวแปรของอัลกอริทึมไขว้ยังสามารถแก้ปัญหาทั่วไปที่มีข้อจำกัดอสมการเชิงเส้นและฟังก์ชันวัตถุประสงค์ที่ไม่เป็นเชิงเส้น ได้ อีกด้วย มีอัลกอริทึมไขว้สำหรับปัญหาการเขียนโปรแกรมเชิงเส้นเศษส่วน^[¹^]^[²^] ปัญหา การเขียนโปรแกรมกำลังสองและปัญหาความสมบูรณ์เชิงเส้น^[³^]

เช่นเดียวกับอัลกอริทึมซิมเพล็กซ์ของGeorge B. Dantzigอัลกอริทึมครอสไม่ใช่อัลกอริทึมเวลาพหุนามสำหรับการเขียนโปรแกรมเชิงเส้น อัลกอริทึมทั้งสองเยี่ยมชมมุมทั้ง 2 ^มิติ ของลูกบาศก์ (ที่ถูกรบกวน) ในมิติ Dซึ่งก็คือลูกบาศก์Klee–Minty (ตั้งชื่อตามVictor KleeและGeorge J. Minty ) ในกรณี ที่เลว ร้ายที่สุด^{[ 4 ]}^{[ 5 ]}อย่างไรก็ตาม เมื่อเริ่มต้นที่มุมแบบสุ่ม อัลกอริทึมครอส จะเยี่ยมชม มุมเพิ่มเติมโดยเฉลี่ยเพียง D มุมเท่านั้น ^{[ 6 ]}^{[ 7 ]}^{[ 8 ]}ดังนั้น สำหรับลูกบาศก์สามมิติ อัลกอริทึมจะเยี่ยมชมมุมทั้ง 8 มุมในกรณีที่เลวร้ายที่สุด และเยี่ยมชมมุมเพิ่มเติมโดยเฉลี่ยเพียง 3 มุมเท่านั้น

ประวัติศาสตร์

อัลกอริทึมไขว้ได้รับการเผยแพร่โดยอิสระโดยTamas Terlaky ^{[ 9 ]}และโดย Zhe-Min Wang; ^{[ 10 ]}อัลกอริทึมที่เกี่ยวข้องปรากฏในรายงานที่ยังไม่ได้เผยแพร่โดยผู้เขียนอื่น^{[ 3 ]}

การเปรียบเทียบกับอัลกอริธึมซิมเพล็กซ์สำหรับการเพิ่มประสิทธิภาพเชิงเส้น

ในการเขียนโปรแกรมเชิงเส้น อัลกอริทึมไขว้จะเปลี่ยนตำแหน่งระหว่างลำดับของฐาน แต่แตกต่างจากอัลกอริทึมซิมเพล็กซ์อัลกอริทึมซิมเพล็กซ์จะค้นหาฐานที่เป็นไปได้ (แบบดั้งเดิม) ก่อนโดยการแก้ " ปัญหา เฟสหนึ่ง " ใน "เฟสสอง" อัลกอริทึมซิมเพล็กซ์จะเปลี่ยนตำแหน่งระหว่างลำดับของ โซลูชัน ที่เป็นไปได้ พื้นฐาน เพื่อให้ฟังก์ชันวัตถุประสงค์ไม่ลดลงเมื่อเปลี่ยนตำแหน่งแต่ละครั้ง และสิ้นสุดด้วยโซลูชันที่เหมาะสมที่สุด (และในที่สุดก็พบโซลูชันที่เป็นไปได้แบบ "คู่" ด้วย) ^{[ 3 ]}^{[ 11 ]}

อัลกอริทึมแบบไขว้ (criss - cross algorithm) นั้นง่ายกว่าอัลกอริทึมแบบซิมเพล็กซ์ (simplex algorithm) เพราะอัลกอริทึมแบบไขว้มีเพียงเฟสเดียว กฎการเลือกแกนหมุนของมันคล้ายกับกฎการเลือกแกนหมุนดัชนีน้อยที่สุดของ Bland ^{[ 12 ]}กฎของ Bland เลือกตัวแปรขาเข้าโดยการเปรียบเทียบค่าต้นทุนที่ลดลง โดยใช้ลำดับจำนวนจริงของแกนหมุนที่เหมาะสม^{[ 12 ]}^{[ 13 ]}แตกต่างจากกฎของ Bland อัลกอริทึมแบบไขว้เป็น "เชิงการจัดเรียงอย่างแท้จริง" โดยเลือกตัวแปรขาเข้าและตัวแปรขาออกโดยพิจารณาเฉพาะเครื่องหมายของสัมประสิทธิ์แทนที่จะเป็นลำดับจำนวนจริง^{[ 3 ]}^{[ 11 ]}อัลกอริทึมแบบไขว้ถูกนำไปใช้เพื่อพิสูจน์ผลลัพธ์พื้นฐานในพีชคณิตเชิงเส้นเช่นบทพิสูจน์ของ Farkas ^{[ 14 ]}

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

คำอธิบาย

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

ความซับซ้อนในการคำนวณ: กรณีที่เลวร้ายที่สุดและกรณีเฉลี่ย

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

อัลกอริทึมหลายตัวสำหรับการเขียนโปรแกรมเชิงเส้น— อัลกอริทึมทรงรีของKhachiyan , อัลกอริทึมเชิงฉายของKarmarkarและอัลกอริทึมเส้นทางศูนย์กลาง —มีความซับซ้อนของเวลาในระดับพหุนาม (ในกรณีที่เลวร้ายที่สุดและโดยเฉลี่ย ) อัลกอริทึมทรงรีและอัลกอริทึมเชิงฉายได้รับการตีพิมพ์ก่อนอัลกอริทึมแบบไขว้

อย่างไรก็ตาม เช่นเดียวกับอัลกอริทึมซิมเพล็กซ์ของ Dantzig อัลกอริทึมครอสไม่ใช่อัลกอริทึมเวลาพหุนามสำหรับการเขียนโปรแกรมเชิงเส้น อัลกอริทึมครอสของ Terlaky เยี่ยมชมมุมทั้ง 2 ^มิติ ของลูกบาศก์ (ที่ถูกรบกวน) ในมิติ Dตามเอกสารของ Roos เอกสารของ Roos ปรับเปลี่ยน การสร้าง ลูกบาศก์ ของ Klee -Minty ซึ่งอัลกอริทึมซิมเพล็กซ์ใช้ ขั้นตอน 2 ^มิติ^[³^]^[⁴^]^[⁵^]เช่นเดียวกับอัลกอริทึมซิมเพล็กซ์ อัลกอริทึมครอสเยี่ยมชมมุมทั้ง 8 มุมของลูกบาศก์สามมิติในกรณีที่เลวร้ายที่สุด

เมื่อเริ่มต้นที่มุมสุ่มของลูกบาศก์ อัลกอริทึมไขว้จะเยี่ยมชมมุมเพิ่มเติมเพียง D มุมเท่านั้น อย่างไรก็ตาม ตามเอกสารปี 1994 โดยFukudaและ Namiki ^{[ 6 ]}^{[ 7 ]}โดยทั่วไป อัลกอริทึมซิมเพล็กซ์ใช้เวลาเฉลี่ย Dขั้นตอนสำหรับลูกบาศก์^{[ 8 ]}^{[ 15 ]}เช่นเดียวกับอัลกอริทึมซิมเพล็กซ์ อัลกอริทึมไขว้จะเยี่ยมชมมุมเพิ่มเติมของลูกบาศก์สามมิติโดยเฉลี่ย 3 มุมพอดี

ตัวแปร

อัลกอริทึมแบบไขว้ได้รับการขยายเพื่อแก้ปัญหาทั่วไปได้มากกว่าปัญหาการเขียนโปรแกรมเชิงเส้น

ปัญหาการหาค่าเหมาะสมที่สุดอื่นๆ ที่มีข้อจำกัดเชิงเส้น

มีอัลกอริธึมแบบไขว้หลายรูปแบบสำหรับการเขียนโปรแกรมเชิงเส้นการเขียนโปรแกรมกำลังสองและปัญหาความสมบูรณ์เชิงเส้นด้วย "เมทริกซ์ที่เพียงพอ" ^{[ 3 ]}^{[ 6 ]}^{[ 16 ]}^{[ 17 ]}^{[ 18 ]}^{[ 19 ]}ในทางกลับกัน สำหรับปัญหาความสมบูรณ์เชิงเส้น อัลกอริธึมแบบไขว้จะสิ้นสุดอย่างจำกัดก็ต่อเมื่อเมทริกซ์เป็นเมทริกซ์ที่เพียงพอ^{[ 18 ]}^{[ 19 ]}เมทริกซ์ที่เพียงพอเป็นการวางนัยทั่วไปของทั้งเมทริกซ์บวกกำหนดและเมทริกซ์ Pซึ่งไมเนอร์หลักแต่ละตัวเป็นบวก^{[ 18 ]}^{[ 19 ]}^{[ 20 ]}อัลกอริธึมแบบไขว้ยังได้รับการปรับให้เข้ากับการเขียนโปรแกรมเชิงเส้นเศษส่วนด้วย^{[ 1 ]}^{[ 2 ]}

การแจงนับจุดยอด

อัลกอริทึมไขว้ถูกใช้ในอัลกอริทึมสำหรับการแจงนับจุดยอดทั้งหมดของโพลีโทปซึ่งได้รับการตีพิมพ์โดยDavid AvisและKomei Fukudaในปี 1992 ^{[ 21 ]} Avis และ Fukuda ได้นำเสนออัลกอริทึมที่ค้นหา จุดยอด vจุดของโพลีเฮดรอนที่กำหนดโดยระบบ อสมการเชิงเส้นn ตัวที่ไม่เสื่อม ^สภาพใน มิติD (หรือในทางกลับกัน ด้าน v ด้านของส่วนนูนของ จุด nจุดใน มิติ Dโดยที่แต่ละด้านมี จุดที่กำหนด D จุดพอดี ) ในเวลา O ( nDv ) และพื้นที่ O( nD ) ^[ 22 ^]

เมทริกซ์เชิงทิศทาง

อัลกอริทึมไขว้มักได้รับการศึกษาโดยใช้ทฤษฎีเมทริกซ์เชิงทิศทาง (OMs) ซึ่งเป็น นามธรรมเชิงการจัด เรียงของทฤษฎีการหาค่าเหมาะสมที่สุดเชิงเส้น^{[ 17 ]}^{[ 23 ]}อันที่จริง กฎการหมุนของ Bland นั้นอิงตามเอกสารก่อนหน้าของเขาเกี่ยวกับทฤษฎีเมทริกซ์เชิงทิศทาง อย่างไรก็ตาม กฎของ Bland แสดงให้เห็นถึงการวนซ้ำในปัญหาการเขียนโปรแกรมเชิงเส้นเมทริกซ์เชิงทิศทางบางปัญหา^{[ 17 ]}อัลกอริทึมเชิงการจัดเรียงบริสุทธิ์ตัวแรกสำหรับการเขียนโปรแกรมเชิงเส้นได้รับการคิดค้นโดยMichael J. Todd [ ^{17 ] [}^{24 ] อั}ลกอริทึมของ Todd ได้รับการพัฒนาไม่เพียงแต่สำหรับการเขียนโปรแกรมเชิงเส้นในบริบทของเมทริกซ์เชิงทิศทางเท่านั้น แต่ยังรวมถึง ปัญหาการเขียนโปรแกรมกำลังสองและปัญหาความสมบูรณ์เชิงเส้นด้วย [ ^{17 ] [}^{24 ] น่า}เสียดายที่อัลกอริทึมของ Todd นั้นซับซ้อนแม้กระทั่งการกล่าวถึง และการพิสูจน์การลู่เข้าแบบจำกัดของมันก็ค่อนข้างซับซ้อน^{[ 17 ]}

อัลกอริทึมแบบไขว้และการพิสูจน์การสิ้นสุดแบบจำกัดสามารถระบุได้อย่างง่ายดายและขยายการตั้งค่าของเมทริกซ์แบบมีทิศทาง อัลกอริทึมสามารถทำให้ง่ายขึ้นได้อีกสำหรับปัญหาความเป็นไปได้เชิงเส้นนั่นคือสำหรับระบบเชิงเส้นที่มี ตัวแปรที่ไม่เป็นลบ ปัญหาเหล่านี้สามารถกำหนดได้สำหรับเมทริกซ์แบบมีทิศทาง^[¹⁴^] อัลกอริทึมแบบไขว้ได้รับการปรับให้เข้ากับปัญหาที่ซับซ้อนกว่าการเขียนโปรแกรมเชิงเส้น: มีตัวแปรเมทริกซ์แบบมีทิศทางสำหรับปัญหาการเขียนโปรแกรมกำลังสองและสำหรับปัญหาความสมบูรณ์เชิงเส้นด้วย^[³^]^[¹⁶^]^[¹⁷^]

สรุป

อัลกอริทึมไขว้ (Criss-cross algorithm) เป็นอัลกอริทึมที่อธิบายง่ายๆ สำหรับการเขียนโปรแกรมเชิงเส้น เป็นอัลกอริทึมเชิงการจัดเรียงแบบสมบูรณ์ตัวที่สองสำหรับการเขียนโปรแกรมเชิงเส้น แตกต่างจากอัลกอริทึมซิมเพล็กซ์เชิงการจัดเรียงบางส่วนของวัฏจักรแบลนด์ (Bland cycles) บนเมทริกซ์เชิงทิศทาง (oriented matroids) บางตัว (ที่ไม่สามารถสร้างได้จริง) อัลกอริทึมเชิงการจัดเรียงแบบสมบูรณ์ตัวแรกได้รับการตีพิมพ์โดยท็อดด์ (Todd) และมีความคล้ายคลึงกับอัลกอริทึมซิมเพล็กซ์ตรงที่รักษาความสามารถในการหาคำตอบได้หลังจากสร้างฐานที่เป็นไปได้ฐานแรกแล้ว อย่างไรก็ตาม กฎของท็อดด์มีความซับซ้อน อัลกอริทึมไขว้ไม่ใช่แบบอัลกอริทึมซิมเพล็กซ์ เพราะไม่จำเป็นต้องรักษาความสามารถในการหาคำตอบได้ อย่างไรก็ตาม อัลกอริทึมไขว้ไม่ได้มีความซับซ้อนของเวลาแบบพหุนาม

นักวิจัยได้ขยายอัลกอริทึมแบบไขว้ (criss-cross algorithm) ไปใช้กับปัญหาการหาค่าเหมาะสมที่สุดหลายประเภท รวมถึงการเขียนโปรแกรมเชิงเส้นเศษส่วน (linear-fractional programming) อัลกอริทึมแบบไขว้สามารถแก้ปัญหาการเขียนโปรแกรมเชิงกำลังสอง (quadratic programming problems) และปัญหาความสมบูรณ์เชิงเส้น (linear complementarity problems) ได้ แม้กระทั่งในบริบทของเมทริกซ์เชิงทิศทาง (oriented matroids) ก็ตาม แม้ว่าจะมีการขยายความทั่วไปแล้ว อัลกอริทึมแบบไขว้ก็ยังคงเขียนได้ง่ายอยู่

ดูเพิ่มเติม

แจ็ค เอ็ดมอนด์ส (ผู้บุกเบิกการหาค่าเหมาะสมที่สุดเชิงการจัดเรียงและนักทฤษฎีเมทริกซ์เชิงทิศทาง; อาจารย์ที่ปรึกษาปริญญาเอกของโคเมอิ ฟุกุดะ)

หมายเหตุ

↑ ^อิ ^ลเลส, เซอร์ไม และเทอร์ลากี (1999)
^ ^a ^b Stancu-Minasian, I. M. (สิงหาคม 2549). "บรรณานุกรมการเขียนโปรแกรมเศษส่วนฉบับที่หก" การเพิ่มประสิทธิภาพ55 (4): 405– 428. doi : 10.1080/02331930600819613 . MR 2258634 . S2CID 62199788 .
↑ ^a ^b ^c ^d ^e ^f ^gฟูกูดะ และเทอร์ลากี (1997)
^ ^a ^b Roos (1990)
^ ^a ^b Klee, Victor ; Minty, George J. (1972). "อัลกอริทึมซิมเพล็กซ์ดีแค่ไหน?" ใน Shisha, Oved (บรรณาธิการ). อสมการ III (รายงานการประชุมสัมมนาครั้งที่ 3 ว่าด้วยอสมการ ณ มหาวิทยาลัยแคลิฟอร์เนีย ลอสแอนเจลิส รัฐแคลิฟอร์เนีย วันที่ 1-9 กันยายน 1969 อุทิศแด่ความทรงจำของ Theodore S. Motzkin)นิวยอร์ก-ลอนดอน: Academic Press. หน้า 159–175 . MR 0332165 .
↑ ^a ^b ^cฟูกูดะ และ เทอร์ลากี (1997 , หน้า 385)
↑ ^ฟุ ^กุดะ และ นามิกิ (1994 , หน้า 367)
^ ^a ^bอัลกอริทึมซิมเพล็กซ์ใช้เวลาโดยเฉลี่ย Dขั้นตอนสำหรับลูกบาศก์Borgwardt (1987) : Borgwardt, Karl-Heinz (1987). วิธีซิมเพล็กซ์: การวิเคราะห์เชิงความน่าจะเป็นอัลกอริทึมและคณิตศาสตร์เชิงการจัดเรียง (ตำราเรียนและการวิจัย) เล่ม 1 เบอร์ลิน: Springer-Verlag หน้า xii+268 ISBN 978-3-540-17096-9MR 0868467
↑เทอร์ลากี (1985)และเทอร์ลากี (1987)
^หวัง (1987)
^ ^a ^b Terlaky & Zhang (1993)
^ ^a ^b Bland, Robert G. (พฤษภาคม 1977). "กฎการหมุนเวียนแบบจำกัดใหม่สำหรับวิธีซิมเพล็กซ์". คณิตศาสตร์ของการวิจัยการดำเนินงาน 2 ( 2): 103– 107. doi : 10.1287/moor.2.2.103 . JSTOR 3689647 . MR 0459599 .
^กฎของ Bland ยังเกี่ยวข้องกับกฎดัชนีน้อยที่สุดก่อนหน้านี้ ซึ่งเสนอโดย Katta G. Murty สำหรับปัญหาความสมบูรณ์เชิงเส้นตามที่ Fukuda & Namiki (1994) กล่าว ไว้
อรรถ เป็น^ข ^คลา ฟสกี้ และ เทอร์ลากี (1991)
^โดยทั่วไปแล้ว สำหรับอัลกอริธึมซิมเพล็กซ์ จำนวนขั้นตอนที่คาดหวังจะเป็นสัดส่วนกับ Dสำหรับปัญหาการเขียนโปรแกรมเชิงเส้นที่สุ่มเลือกจากทรงกลมหน่วยยุค ลิด ดังที่พิสูจน์โดยบอ ร์กวาร์ดและสเมล
อรรถ เป็น^{ข ฟุกุ}^ดะและนามิกิ (1994)
↑ ^a ^b ^c ^d ^e ^f ^gบียอร์เนอร์, แอนเดอร์ส; Las Vergnas, มิเชล ; Sturmfels, แบร์นด์ ; ไวท์, นีล; ซีกเลอร์, กึนเตอร์ (1999) "10 การเขียนโปรแกรมเชิงเส้น" เมทริกซ์เชิง สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. หน้า 417– 479. ดอย : 10.1017/CBO9780511586507 . ไอเอสบีเอ็น 978-0-521-77750-6MR 1744046
^ ^a ^b ^c den Hertog, D.; Roos, C.; Terlaky, T. (1 กรกฎาคม 1993). "ปัญหาความสมบูรณ์เชิงเส้น เมทริกซ์เพียงพอ และวิธีการไขว้" (PDF) . พีชคณิตเชิงเส้นและการประยุกต์ใช้ . 187 : 1– 14. doi : 10.1016/0024-3795(93)90124-7 .
^ ^a ^b ^c Csizmadia, Zsolt; Illés, Tibor (2006). "อัลกอริทึมแบบไขว้ใหม่สำหรับปัญหาความสมบูรณ์เชิงเส้นด้วยเมทริกซ์เพียงพอ" (PDF)วิธีการเพิ่มประสิทธิภาพและซอฟต์แวร์ 21 ( 2): 247– 266. doi : 10.1080/10556780500095009 . MR 2195759 . S2CID 24418835 . เก็บถาวรจากต้นฉบับ(pdf)เมื่อวันที่ 23 กันยายน 2015 . สืบค้นเมื่อ30 สิงหาคม 2011 .
^ Cottle, RW ; Pang, J.-S.; Venkateswaran, V. (มีนาคม–เมษายน 1989). "เมทริกซ์เพียงพอและปัญหาความสมบูรณ์เชิงเส้น" . พีชคณิตเชิงเส้นและการประยุกต์ใช้ . 114– 115: 231– 249. doi : 10.1016/0024-3795(89)90463-1 . MR 0986877 .
↑เอวิส และ ฟูกูดะ (1992 , หน้า 297)
^การ หา จุดยอด vจุดในระนาบ ไฮเปอร์เพล น n ระนาบแบบง่าย ใน มิติ Dสามารถทำได้ด้วยความซับซ้อนของเวลา O( n ²Dv ) และ พื้นที่ O( nD )
^ทฤษฎีของเมทริกซ์เชิงทิศทางริเริ่มโดย R. Tyrrell Rockafellar ( Rockafellar 1969 ):
Rockafellar, RT (1969). "เวกเตอร์พื้นฐานของปริภูมิย่อยของ(1967)" $R^{N}$ (PDF)ในRC Boseและ TA Dowling (บรรณาธิการ). คณิตศาสตร์เชิงการจัดเรียงและการประยุกต์ใช้ชุดเอกสารทางวิชาการด้านความน่าจะเป็นและสถิติของมหาวิทยาลัยนอร์ทแคโรไลนา แชปเพิลฮิลล์ นอร์ทแคโรไลนา: สำนักพิมพ์มหาวิทยาลัยนอร์ทแคโรไลนา หน้า 104–127 . MR 0278972พิมพ์ซ้ำในรูปแบบ PDF
ร็อกกาเฟลลาร์ได้รับอิทธิพลจากการศึกษาในอดีตของอัลเบิร์ต ดับเบิลยู. ทักเกอร์และจอร์จ เจ . มินตี โดยทักเกอร์และมินตีได้ศึกษาแบบแผนของเครื่องหมายในเมทริกซ์ที่เกิดขึ้นจากการดำเนินการหมุนแกนของอัลกอริทึมซิมเพล็กซ์ของแดนท์ซิก
^ ^a ^b Todd, Michael J. (1985). "การเขียนโปรแกรมเชิงเส้นและเชิงกำลังสองในเมทริกซ์เชิงทิศทาง"วารสารทฤษฎีเชิงการจัดเรียงซีรี่ส์ B. 39 (2): 105– 133. doi : 10.1016/0095-8956(85)90042-5 . MR 0811116 .

ลิงก์ภายนอก

Komei Fukuda (ETH Zentrum, ซูริก)พร้อมสิ่งพิมพ์
Tamás Terlaky (มหาวิทยาลัย Lehigh)พร้อมผลงานตีพิมพ์เก็บถาวรเมื่อวันที่ 28 กันยายน 2011 ที่Wayback Machine

[LF99Hyperbolic-1] อิ ^ลเลส, เซอร์ไม และเทอร์ลากี (1999)

[Bibl-2] Stancu-Minasian, I. M. (สิงหาคม 2549). "บรรณานุกรมการเขียนโปรแกรมเศษส่วนฉบับที่หก" การเพิ่มประสิทธิภาพ55 (4): 405– 428. doi : 10.1080/02331930600819613 . MR 2258634 . S2CID 62199788 .

[FukudaTerlaky-3] ↑ ^a ^b ^c ^d ^e ^f ^gฟูกูดะ และเทอร์ลากี (1997)

[Roos-4] Roos (1990)

[KleeMinty-5] Klee, Victor ; Minty, George J. (1972). "อัลกอริทึมซิมเพล็กซ์ดีแค่ไหน?" ใน Shisha, Oved (บรรณาธิการ). อสมการ III (รายงานการประชุมสัมมนาครั้งที่ 3 ว่าด้วยอสมการ ณ มหาวิทยาลัยแคลิฟอร์เนีย ลอสแอนเจลิส รัฐแคลิฟอร์เนีย วันที่ 1-9 กันยายน 1969 อุทิศแด่ความทรงจำของ Theodore S. Motzkin)นิวยอร์ก-ลอนดอน: Academic Press. หน้า 159–175 . MR 0332165 .

[FTNamiki-6] ฟูกูดะ และ เทอร์ลากี (1997 , หน้า 385)

[FukudaNamiki-7] ฟุ ^กุดะ และ นามิกิ (1994 , หน้า 367)

[Borgwardt-8] อัลกอริทึมซิมเพล็กซ์ใช้เวลาโดยเฉลี่ย Dขั้นตอนสำหรับลูกบาศก์Borgwardt (1987) : Borgwardt, Karl-Heinz (1987). วิธีซิมเพล็กซ์: การวิเคราะห์เชิงความน่าจะเป็นอัลกอริทึมและคณิตศาสตร์เชิงการจัดเรียง (ตำราเรียนและการวิจัย) เล่ม 1 เบอร์ลิน: Springer-Verlag หน้า xii+268 ISBN 978-3-540-17096-9MR 0868467

[9] เทอร์ลากี (1985)และเทอร์ลากี (1987)

[Wang-10] หวัง (1987)

[TerlakyZhang-11] Terlaky & Zhang (1993)

[Bland-12] Bland, Robert G. (พฤษภาคม 1977). "กฎการหมุนเวียนแบบจำกัดใหม่สำหรับวิธีซิมเพล็กซ์". คณิตศาสตร์ของการวิจัยการดำเนินงาน 2 ( 2): 103– 107. doi : 10.1287/moor.2.2.103 . JSTOR 3689647 . MR 0459599 .

[13] กฎของ Bland ยังเกี่ยวข้องกับกฎดัชนีน้อยที่สุดก่อนหน้านี้ ซึ่งเสนอโดย Katta G. Murty สำหรับปัญหาความสมบูรณ์เชิงเส้นตามที่ Fukuda & Namiki (1994) กล่าว ไว้

[KT91-14] อรรถ เป็น^ข ^คลา ฟสกี้ และ เทอร์ลากี (1991)

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

[FukudaNamikiLCP-16] อรรถ เป็น^{ข ฟุกุ}^ดะและนามิกิ (1994)

[OMBook-17] ↑ ^a ^b ^c ^d ^e ^f ^gบียอร์เนอร์, แอนเดอร์ส; Las Vergnas, มิเชล ; Sturmfels, แบร์นด์ ; ไวท์, นีล; ซีกเลอร์, กึนเตอร์ (1999) "10 การเขียนโปรแกรมเชิงเส้น" เมทริกซ์เชิง สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. หน้า 417– 479. ดอย : 10.1017/CBO9780511586507 . ไอเอสบีเอ็น 978-0-521-77750-6MR 1744046

[HRT-18] Hertog, D.; Roos, C.; Terlaky, T. (1 กรกฎาคม 1993). "ปัญหาความสมบูรณ์เชิงเส้น เมทริกซ์เพียงพอ และวิธีการไขว้" (PDF) . พีชคณิตเชิงเส้นและการประยุกต์ใช้ . 187 : 1– 14. doi : 10.1016/0024-3795(93)90124-7 .

[CIsufficient-19] Csizmadia, Zsolt; Illés, Tibor (2006). "อัลกอริทึมแบบไขว้ใหม่สำหรับปัญหาความสมบูรณ์เชิงเส้นด้วยเมทริกซ์เพียงพอ" (PDF)วิธีการเพิ่มประสิทธิภาพและซอฟต์แวร์ 21 ( 2): 247– 266. doi : 10.1080/10556780500095009 . MR 2195759 . S2CID 24418835 . เก็บถาวรจากต้นฉบับ(pdf)เมื่อวันที่ 23 กันยายน 2015 . สืบค้นเมื่อ30 สิงหาคม 2011 .

[20] Cottle, RW ; Pang, J.-S.; Venkateswaran, V. (มีนาคม–เมษายน 1989). "เมทริกซ์เพียงพอและปัญหาความสมบูรณ์เชิงเส้น" . พีชคณิตเชิงเส้นและการประยุกต์ใช้ . 114– 115: 231– 249. doi : 10.1016/0024-3795(89)90463-1 . MR 0986877 .

[21] เอวิส และ ฟูกูดะ (1992 , หน้า 297)

[22] การ หา จุดยอด vจุดในระนาบ ไฮเปอร์เพล น n ระนาบแบบง่าย ใน มิติ Dสามารถทำได้ด้วยความซับซ้อนของเวลา O( n ²Dv ) และ พื้นที่ O( nD )

[23] ทฤษฎีของเมทริกซ์เชิงทิศทางริเริ่มโดย R. Tyrrell Rockafellar ( Rockafellar 1969 ):
Rockafellar, RT (1969). "เวกเตอร์พื้นฐานของปริภูมิย่อยของ(1967)" $R^{N}$ (PDF)ในRC Boseและ TA Dowling (บรรณาธิการ). คณิตศาสตร์เชิงการจัดเรียงและการประยุกต์ใช้ชุดเอกสารทางวิชาการด้านความน่าจะเป็นและสถิติของมหาวิทยาลัยนอร์ทแคโรไลนา แชปเพิลฮิลล์ นอร์ทแคโรไลนา: สำนักพิมพ์มหาวิทยาลัยนอร์ทแคโรไลนา หน้า 104–127 . MR 0278972พิมพ์ซ้ำในรูปแบบ PDF
ร็อกกาเฟลลาร์ได้รับอิทธิพลจากการศึกษาในอดีตของอัลเบิร์ต ดับเบิลยู. ทักเกอร์และจอร์จ เจ . มินตี โดยทักเกอร์และมินตีได้ศึกษาแบบแผนของเครื่องหมายในเมทริกซ์ที่เกิดขึ้นจากการดำเนินการหมุนแกนของอัลกอริทึมซิมเพล็กซ์ของแดนท์ซิก

[Todd-24] Todd, Michael J. (1985). "การเขียนโปรแกรมเชิงเส้นและเชิงกำลังสองในเมทริกซ์เชิงทิศทาง"วารสารทฤษฎีเชิงการจัดเรียงซีรี่ส์ B. 39 (2): 105– 133. doi : 10.1016/0095-8956(85)90042-5 . MR 0811116 .

[

[

[

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

สภาพ

[ 23 ]

24 ] อั