11.4. วิธีดูอัลซิมเพล็กซ์
จากผลลัพธ์ของส่วนก่อนหน้านั้น เพื่อให้ได้วิธีแก้ปัญหาสำหรับปัญหาเดิม เราสามารถส่งต่อไปยังส่วนคู่ และใช้ค่าประมาณของการออกแบบที่เหมาะสมที่สุด กำหนดวิธีแก้ปัญหาที่เหมาะสมที่สุดสำหรับปัญหาเดิม
ไม่จำเป็นต้องเปลี่ยนไปใช้ปัญหาคู่เนื่องจากถ้าเราพิจารณาฉากซิมเพล็กซ์แรกด้วยพื้นฐานเพิ่มเติมของหน่วย จะเห็นได้ง่ายว่าคอลัมน์มีปัญหาเดิม และปัญหาคู่เขียนในแถว
ดังที่แสดงไว้ เมื่อแก้ปัญหาตรงที่การวนซ้ำใด ๆ ความแตกต่าง, เช่น. ขนาด -สัมประสิทธิ์กับตัวแปรเท่ากับความแตกต่างระหว่างด้านขวาและด้านซ้ายของข้อจำกัดที่สอดคล้องกันของปัญหาคู่ หากเมื่อแก้ปัญหาโดยตรงด้วยฟังก์ชันวัตถุประสงค์สูงสุด การวนซ้ำไม่ได้นำไปสู่วิธีแก้ปัญหาที่เหมาะสม อย่างน้อยก็สำหรับตัวแปรหนึ่งตัวและเฉพาะในค่าที่เหมาะสมที่สุดสำหรับทั้งหมดเท่านั้นความแตกต่าง .
พิจารณาเงื่อนไขนี้โดยคำนึงถึงความเป็นคู่เราสามารถเขียน
.
ดังนั้น ถ้า, แล้ว . ซึ่งหมายความว่าเมื่อวิธีแก้ไขปัญหาปฐมภูมิไม่เหมาะสม วิธีแก้ไขปัญหาสองปัญหานั้นไม่ถูกต้อง ในทางกลับกัน 
ที่ . นี่หมายความว่าทางออกที่ดีที่สุดของปัญหาปฐมภูมิสอดคล้องกับวิธีแก้ไขปัญหาที่ยอมรับได้ของปัญหาคู่
สิ่งนี้ทำให้สามารถพัฒนาวิธีการใหม่ในการแก้ปัญหาการโปรแกรมเชิงเส้นเมื่อใช้งานซึ่งในตอนแรกอาจได้รับวิธีแก้ปัญหาที่ "ดีกว่าที่เหมาะสมที่สุด" (ในวิธีซิมเพล็กซ์ปกติก่อน ยอมรับได้, แต่ ไม่เหมาะสมวิธีการแก้). วิธีการใหม่ที่เรียกว่า วิธีดูอัลซิมเพล็กซ์, รับรองการปฏิบัติตามเงื่อนไขที่เหมาะสมที่สุดของโซลูชันและ "การประมาณ" อย่างเป็นระบบไปยังพื้นที่ของโซลูชันที่เป็นไปได้ เมื่อโซลูชันที่ได้รับกลายเป็นสิ่งที่ยอมรับได้ กระบวนการคำนวณแบบวนซ้ำจะสิ้นสุดลง เนื่องจากโซลูชันนี้ก็เหมาะสมที่สุดเช่นกัน
วิธีดูอัลซิมเพล็กซ์ช่วยให้สามารถแก้ปัญหาการโปรแกรมเชิงเส้นได้ ซึ่งระบบข้อจำกัดที่มีพื้นฐานเชิงบวกมีเงื่อนไขอิสระของเครื่องหมายใดๆ วิธีนี้ทำให้สามารถลดจำนวนการแปลงระบบข้อจำกัด ตลอดจนขนาดของตารางซิมเพล็กซ์ พิจารณาการประยุกต์ใช้วิธีดูอัลซิมเพล็กซ์โดยใช้ตัวอย่าง
ตัวอย่าง. หาค่าต่ำสุดของฟังก์ชัน 
ภายใต้ข้อจำกัด
.
ไปที่รูปแบบบัญญัติ:
ภายใต้ข้อจำกัด
ฉากซิมเพล็กซ์เริ่มต้นมีรูปแบบ
|
ขั้นพื้นฐาน ตัวแปร |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
วิธีการแก้ |
|
x 3 x 4 x 5 |
–3 –4 |
–1 –3 |
–3 –6 |
|||
|
–2 |
–1 |
วิธีแก้ปัญหาเบื้องต้นเบื้องต้นเหมาะสมที่สุดแต่ไม่เป็นที่ยอมรับ
เช่นเดียวกับวิธีซิมเพล็กซ์ทั่วไป วิธีการแก้ปัญหาภายใต้การพิจารณาจะขึ้นอยู่กับการใช้เงื่อนไขที่ยอมรับได้และเหมาะสมที่สุด
เงื่อนไขการรับเข้าเรียน. ตัวแปรพื้นฐานเชิงลบที่ใหญ่ที่สุดในค่าสัมบูรณ์จะถูกเลือกเป็นตัวแปรที่แยกออก (หากมีทางเลือกอื่น ทางเลือกจะถูกกำหนดโดยพลการ) หากตัวแปรพื้นฐานทั้งหมดไม่เป็นค่าลบ กระบวนการคำนวณจะสิ้นสุดลง เนื่องจากผลลัพธ์ที่ได้จะเป็นไปได้และเหมาะสมที่สุด
สภาพ ความเหมาะสม. ตัวแปรที่รวมอยู่ในค่าพื้นฐานจะถูกเลือกจากตัวแปรที่ไม่ใช่ตัวแปรพื้นฐานดังต่อไปนี้ คำนวณอัตราส่วนของสัมประสิทธิ์ทางด้านซ้าย-equations กับสัมประสิทธิ์ที่สอดคล้องกันของสมการที่เกี่ยวข้องกับตัวแปรที่แยกออก ความสัมพันธ์กับตัวส่วนบวกหรือศูนย์จะไม่ถูกนำมาพิจารณา ในปัญหาการลดขนาดตัวแปรอินพุต อัตราส่วนที่น้อยที่สุดจะต้องสอดคล้องกัน และในปัญหาการขยายให้ใหญ่สุด อัตราส่วนที่มีค่าสัมบูรณ์ที่น้อยที่สุด (หากมีทางเลือกอื่น ให้เลือกตามอำเภอใจ) ถ้าตัวส่วนของอัตราส่วนทั้งหมดเป็นศูนย์หรือบวก แสดงว่าปัญหาไม่มีวิธีแก้ปัญหาที่เป็นไปได้
หลังจากเลือกตัวแปรที่จะรวมอยู่ในค่าพื้นฐานและจะถูกแยกออก การดำเนินการตามปกติของการแปลงแถวของตารางซิมเพล็กซ์จะดำเนินการเพื่อให้ได้แนวทางแก้ไขถัดไป
ในตัวอย่างนี้ ตัวแปรที่ยกเว้นคือ. อัตราส่วนที่คำนวณเพื่อกำหนดตัวแปรฐานใหม่จะแสดงในตารางต่อไปนี้:
|
ตัวแปร |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
สมการ x 4 - สมการ |
–2 –4 |
–1 –3 |
|||
|
ทัศนคติ |
ตัวแปรที่จะรวมคือ x 2. การแปลงสตริงที่ตามมาส่งผลให้เกิดตารางซิมเพล็กซ์ใหม่:
|
ขั้นพื้นฐาน ตัวแปร |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
วิธีการแก้ |
|
x 3 x 2 x 5 |
–1 –1 |
|||||
โซลูชั่นใหม่ ยังเหมาะสมที่สุด แต่ก็ยังไม่ถูกต้อง ในฐานะตัวแปรใหม่ที่ถูกแยกออก เราเลือก (ตามอำเภอใจ) x 3 . มากำหนดตัวแปรรวมกัน
|
ตัวแปร |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
สมการ x 4 - สมการ |
|||||
|
ทัศนคติ |
วิธีซิมเพล็กซ์ - นี่เป็นวิธีการเปลี่ยนจากโซลูชันพื้นฐานแบบต่อเนื่อง (จุดยอดของรูปทรงหลายเหลี่ยมของโซลูชัน) ของระบบข้อจำกัดของปัญหาการโปรแกรมเชิงเส้นไปเป็นโซลูชันพื้นฐานอื่น จนกว่าฟังก์ชันเป้าหมายจะใช้ค่าที่เหมาะสมที่สุด (สูงสุดหรือต่ำสุด)
วิธีซิมเพล็กซ์เป็นวิธีการสากลที่สามารถแก้ปัญหาใด ๆ ได้ ปัญหาการเขียนโปรแกรมเชิงเส้นในขณะที่วิธีการแบบกราฟิกเหมาะสำหรับระบบข้อจำกัดสองตัวแปรเท่านั้น
นักคณิตศาสตร์ชาวอเมริกัน R. Danzig เสนอวิธีการแบบซิมเพล็กซ์ในปี 1947 ตั้งแต่นั้นมา สำหรับความต้องการของอุตสาหกรรม วิธีนี้มักจะแก้ปัญหาการเขียนโปรแกรมเชิงเส้นด้วยตัวแปรและข้อจำกัดหลายพันตัว
ก่อนจะไปต่อกันที่อัลกอริธึมวิธีซิมเพล็กซ์ ให้คำจำกัดความก่อน.
วิธีแก้ปัญหาใด ๆ ที่ไม่เป็นลบต่อระบบข้อ จำกัด เรียกว่า ทางออกที่ยอมรับได้ .
ให้มีระบบ มข้อจำกัดจาก นตัวแปร ( มน)
โซลูชันพื้นฐานที่ยอมรับได้ เป็นสารละลายที่ประกอบด้วย มไม่เป็นลบ วิชาเอก (ขั้นพื้นฐาน ) ตัวแปรและ น - ม ไม่ใช่คอร์ . (ไม่ใช่พื้นฐานหรือ ฟรี ) ตัวแปร ตัวแปรที่ไม่เป็นพื้นฐานในโซลูชันพื้นฐานมีค่าเท่ากับศูนย์ในขณะที่ตัวแปรหลักตามกฎแล้วไม่เป็นศูนย์นั่นคือเป็นตัวเลขบวก
ใดๆ มตัวแปรระบบ มสมการเชิงเส้นด้วย นตัวแปรเรียกว่า หลัก หากดีเทอร์มีแนนต์ของสัมประสิทธิ์ที่พวกมันแตกต่างจากศูนย์ แล้วที่เหลือ น - มตัวแปรเรียกว่า ไม่ใช่คอร์ (หรือ ฟรี ).
อัลกอริธึมเมธอด Simplex
- ขั้นตอนที่ 1. นำปัญหาการเขียนโปรแกรมเชิงเส้นมาสู่รูปแบบบัญญัติ เมื่อต้องการทำเช่นนี้ ให้ย้ายเงื่อนไขอิสระไปทางด้านขวามือ (หากในบรรดาคำศัพท์อิสระเหล่านี้เป็นค่าลบ ให้คูณสมการที่สอดคล้องกันหรืออสมการด้วย - 1) และใส่ตัวแปรเพิ่มเติมเข้าไปในแต่ละข้อจำกัด (ด้วยเครื่องหมายบวก หากอยู่ใน ความไม่เท่าเทียมกันดั้งเดิม เครื่องหมายจะน้อยกว่าหรือเท่ากับ " และด้วยเครื่องหมายลบ ถ้า "มากกว่าหรือเท่ากับ")
- ขั้นตอนที่ 2. หากอยู่ในระบบผลลัพธ์ มสมการแล้ว มใช้ตัวแปรเป็นตัวหลัก แสดงตัวแปรหลักในรูปของตัวแปรที่ไม่ใช่เบส และหาคำตอบพื้นฐานที่สอดคล้องกัน หากวิธีแก้ปัญหาพื้นฐานที่พบกลายเป็นว่ายอมรับได้ ให้ไปที่โซลูชันพื้นฐานที่ยอมรับได้
- ขั้นตอนที่ 3. แสดงฟังก์ชันเป้าหมายในแง่ของตัวแปรรองของโซลูชันพื้นฐานที่เป็นไปได้ หากพบค่าสูงสุด (ต่ำสุด) ของรูปแบบเชิงเส้นและไม่มีตัวแปรที่ไม่เป็นพื้นฐานที่มีค่าสัมประสิทธิ์เชิงลบ (บวก) ในนิพจน์ แสดงว่าเป็นไปตามเกณฑ์ที่เหมาะสมที่สุดและผลลัพธ์ที่ได้คือโซลูชันพื้นฐานที่เหมาะสมที่สุด - การแก้ปัญหาสิ้นสุดลง หากเมื่อหาค่าสูงสุด (ต่ำสุด) ของรูปแบบเชิงเส้น นิพจน์ประกอบด้วยตัวแปรที่ไม่เป็นพื้นฐานอย่างน้อยหนึ่งตัวที่มีค่าสัมประสิทธิ์เชิงลบ (บวก) ให้ไปที่โซลูชันพื้นฐานใหม่
- ขั้นตอนที่ 4. จากตัวแปรที่ไม่ใช่พื้นฐานที่รวมอยู่ในรูปแบบเชิงเส้นที่มีค่าสัมประสิทธิ์เชิงลบ (บวก) ให้เลือกตัวแปรที่สอดคล้องกับสัมประสิทธิ์ที่ใหญ่ที่สุด (โมดูโล) และโอนไปยังตัวแปรหลัก ไปที่ขั้นตอนที่ 2
เงื่อนไขสำคัญ
บางกรณีพิเศษจะกล่าวถึงในบทความแยกต่างหาก: เมื่อ ฟังก์ชันวัตถุประสงค์สูงสุด - อินฟินิตี้, เมื่อไร ระบบไม่มีวิธีแก้ปัญหา, และเมื่อ ทางออกที่ดีที่สุดไม่ใช่ทางออกเดียว .
ต่อไป เราจะวิเคราะห์ตัวอย่างทั่วไป เมื่อระบบของข้อจำกัดมีความสอดคล้องกันและมีขอบเขตที่เหมาะสมที่สุดและมีเพียงอันเดียวเท่านั้น รูปแบบของวิธีการซิมเพล็กซ์คือ วิธีการกระจายสินค้าเพื่อแก้ไขปัญหาการขนส่ง .
วิธี Simplex กับตาราง Simplex
โดยการสร้างตารางแบบซิมเพล็กซ์ จะแก้ปัญหาการเขียนโปรแกรมเชิงเส้นได้ง่ายกว่าการแปลงพีชคณิตซึ่งแสดงในย่อหน้าถัดไป ตาราง Simplex เป็นภาพที่มองเห็นได้ชัดเจน มีกฎหลายประเภทสำหรับการทำงานกับตารางซิมเพล็กซ์ เราจะวิเคราะห์กฎซึ่งส่วนใหญ่มักเรียกว่าคอลัมน์นำและกฎแถวนำ
มันจะมีประโยชน์ในการเปิดการดำเนินการด้วยตนเองที่มีเศษส่วนในหน้าต่างใหม่: มีเศษส่วนในปัญหาของวิธีซิมเพล็กซ์เพียงพอแล้ว
ตัวอย่าง.
เราแนะนำตัวแปรที่ไม่เป็นลบเพิ่มเติมและลดระบบอสมการนี้ให้เป็นระบบสมการที่เท่ากัน
.
สิ่งนี้ทำตามกฎต่อไปนี้: หากเครื่องหมายในข้อจำกัดเดิมคือ "น้อยกว่าหรือเท่ากับ" จะต้องเพิ่มตัวแปรเพิ่มเติม และหาก "มากกว่าหรือเท่ากับ" ตัวแปรเพิ่มเติมจะต้องเป็น หักออก
ตัวแปรเพิ่มเติมที่แนะนำถือเป็นตัวแปรหลัก (พื้นฐาน) จากนั้นและเป็นตัวแปรที่ไม่ใช่พื้นฐาน (ฟรี)
แสดงตัวแปรหลัก (พื้นฐาน) ในแง่ของไม่ใช่พื้นฐาน (ฟรี) เราได้รับ
นอกจากนี้เรายังแสดงฟังก์ชันเป้าหมายในแง่ของตัวแปรที่ไม่ใช่พื้นฐาน (ฟรี):
จากสัมประสิทธิ์ของตัวแปร (ไม่ทราบ) เราสร้างฉากซิมเพล็กซ์แรก
| ตารางที่ 1 | ||||
| ไม่ทราบพื้นฐาน | สมาชิกฟรี | ไม่ทราบที่หลวม | สัมประสิทธิ์เสริม | |
| X1 | X2 | |||
| X3 | -2 | 1 | -2 | |
| X4 | -4 | -1 | -1 | |
| X5 | 2 | 1 | -1 | |
| X6 | 6 | 0 | 1 | |
| F | 0 | -1 | -2 | |
แถวสุดท้ายของตารางซึ่งมีฟังก์ชันวัตถุประสงค์และสัมประสิทธิ์ของตัวแปรอิสระในนั้นจะถูกเรียกว่าแถวดัชนี
ผลลัพธ์ที่ได้นั้นไม่เหมาะสม เนื่องจากสัมประสิทธิ์ของตัวแปรอิสระในแถวดัชนีเป็นค่าลบ นั่นคือ ทางออกที่ดีที่สุดจะเป็นแบบที่สัมประสิทธิ์ของตัวแปรอิสระในแถวดัชนีจะมากกว่าหรือเท่ากับศูนย์
หากต้องการไปยังตารางถัดไป ให้ค้นหาตัวเลขที่ใหญ่ที่สุด (โมดูโล) และ . ตัวเลขนี้คือ 2 ดังนั้นคอลัมน์นำหน้าคือคอลัมน์ที่เขียน
ในการกำหนดแถวนำ เราจะหาอัตราส่วนขั้นต่ำของสมาชิกอิสระต่อองค์ประกอบของคอลัมน์นำ และหากตัวเศษมีจำนวนบวกและตัวส่วนเป็นลบ อัตราส่วนจะถือว่าเท่ากับอนันต์
.
ดังนั้นเส้นนำคือเส้นที่เขียน
องค์ประกอบนำคือ -2
เราเขียนตารางซิมเพล็กซ์ที่สอง
เราป้อนองค์ประกอบพื้นฐานใหม่ในบรรทัดแรก และเราเข้าสู่คอลัมน์ที่มันอยู่ เราป้อนตัวแปรอิสระใหม่
กรอกบรรทัดแรก ในการทำเช่นนี้ เราแบ่งตัวเลขทั้งหมดในแถวนำหน้าของตารางที่ 1 ด้วยองค์ประกอบนำและเขียนลงในคอลัมน์ที่สอดคล้องกันของแถวแรกของตารางที่ 2 ยกเว้นตัวเลขในคอลัมน์นำหน้าซึ่งส่วนกลับของส่วนนำ องค์ประกอบถูกเขียนขึ้น (นั่นคือหนึ่งหารด้วยองค์ประกอบนำหน้า)
กรอกข้อมูลในคอลัมน์ของสัมประสิทธิ์เสริม สำหรับจำนวนคอลัมน์นำหน้าของตารางที่ 1 นี้ นอกเหนือจากองค์ประกอบนำหน้าแล้ว เราเขียนด้วยเครื่องหมายตรงข้ามในคอลัมน์ของสัมประสิทธิ์เสริมของตารางที่ 2
| ตารางที่ 2 | ||||
| ไม่ทราบพื้นฐาน | สมาชิกฟรี | ไม่ทราบที่หลวม | สัมประสิทธิ์เสริม | |
| X1 | X3 | |||
| X2 | 1 | -1/2 | -1/2 | |
| X4 | -3 | -3/2 | -1/2 | 1 |
| X5 | 3 | 1/2 | -1/2 | 1 |
| X6 | 5 | 1/2 | 1/2 | -1 |
| F | 2 | -2 | -1 | 2 |
ใครยังไม่ได้เปิดในหน้าต่างใหม่ การดำเนินการด้วยตนเองกับเศษส่วน สามารถทำได้ในขณะนี้ เพราะถึงเวลาแล้ว
เพื่อให้ได้แถวที่เหลือของตารางที่ 2 ตัวเลขที่อยู่ในแถวแรกของตารางนี้จะถูกคูณด้วยค่าสัมประสิทธิ์เสริมในแถวที่เติม และผลลัพธ์เราจะเพิ่มตัวเลขจากตารางที่ 1 ซึ่งอยู่ในแถวเดียวกันกับ ตัวแปรที่สอดคล้องกัน
ตัวอย่างเช่น เพื่อให้ได้สมาชิกอิสระของแถวที่สอง เราคูณตัวเลข 1 ด้วย 1 แล้วบวกตัวเลข -4 จากตารางที่ 1 เราได้ -3 เราพบสัมประสิทธิ์สำหรับในบรรทัดที่สองในลักษณะเดียวกัน: 
. เนื่องจากไม่มีคอลัมน์ที่มีตัวแปรอิสระใหม่ในตารางก่อนหน้านี้ สัมประสิทธิ์ของแถวที่สองในคอลัมน์ของตัวแปรอิสระใหม่จะเป็น 
(นั่นคือจากตารางที่ 1 เราเพิ่ม 0 เนื่องจากไม่มีคอลัมน์ c ในตารางที่ 1)
บรรทัดดัชนีถูกกรอกในลักษณะเดียวกัน:
การแก้ปัญหาที่ได้รับจึงไม่เหมาะสมอีกครั้ง เนื่องจากสัมประสิทธิ์ของตัวแปรอิสระในแถวดัชนีเป็นค่าลบอีกครั้ง
ในการไปที่ตารางซิมเพล็กซ์ถัดไป ให้หาค่าที่ใหญ่ที่สุด (โมดูโล) ของตัวเลข และ นั่นคือ โมดูลของสัมประสิทธิ์ในบรรทัดดัชนี ตัวเลขนี้คือ 2 ดังนั้น คอลัมน์นำหน้าคือคอลัมน์ที่ประกอบด้วย
ในการค้นหาแถวนำ ให้หาอัตราส่วนขั้นต่ำของสมาชิกอิสระต่อองค์ประกอบของแถวนำหน้า เราได้รับ:
.
ดังนั้น เส้นนำหน้าคือเส้นที่เขียน และองค์ประกอบนำหน้าคือ -3/2
รวบรวมตารางซิมเพล็กซ์ที่สาม
เราเขียนตัวแปรพื้นฐานใหม่ในบรรทัดแรก ในคอลัมน์ที่เป็นอยู่ เราป้อนตัวแปรอิสระใหม่
เส้นแรก:
ค่าสัมประสิทธิ์เสริม:
| ตารางที่ 3 | ||||
| ไม่ทราบพื้นฐาน | สมาชิกฟรี | ไม่ทราบที่หลวม | สัมประสิทธิ์เสริม | |
| X4 | X3 | |||
| X1 | 2 | -2/3 | 1/3 | |
| X2 | 2 | -1/3 | -1/3 | 1/2 |
| X5 | 2 | 1/3 | -2/3 | -1/2 |
| X6 | 4 | 1/3 | 1/3 | -1/2 |
| F | 6 | -4/3 | -1/3 | 2 |
ผลลัพธ์ที่ได้กลับไม่เหมาะสมอีกครั้ง เนื่องจากค่าสัมประสิทธิ์ของค่าที่ไม่ทราบค่าว่างในแถวดัชนีเป็นค่าลบอีกครั้ง
ในการไปที่ตารางซิมเพล็กซ์ที่สี่ ให้หาจำนวนที่มากที่สุดและ . นี่คือตัวเลข
ดังนั้น คอลัมน์นำคือคอลัมน์ที่มี .
โมดูลัสขั้นต่ำของความสัมพันธ์ของสมาชิกอิสระกับองค์ประกอบของคอลัมน์นำ:
.
ดังนั้นเส้นนำคือเส้นที่เขียนและองค์ประกอบนำหน้าคือ 1/3
ในตารางซิมเพล็กซ์ที่สี่ เราเขียนตัวแปรพื้นฐานใหม่ในบรรทัดแรก ในคอลัมน์ที่เป็นอยู่ เราเขียนตัวแปรอิสระใหม่
เส้นแรก:
ค่าสัมประสิทธิ์เสริม:
| ตารางที่ 4 | ||||
| ไม่ทราบพื้นฐาน | สมาชิกฟรี | ไม่ทราบที่หลวม | สัมประสิทธิ์เสริม | |
| X5 | X3 | |||
| X4 | 6 | 3 | -2 | |
| X1 | 6 | 2 | -1 | 2/3 |
| X2 | 4 | 1 | -1 | 1/3 |
| X6 | 2 | -1 | 1 | -1/3 |
| F | 14 | 4 | -3 | 4/3 |
การคำนวณแถวที่เหลือโดยใช้ตัวอย่างของแถวที่สอง:
ผลลัพธ์ที่ได้ก็ไม่เหมาะสมเช่นกัน แต่ก็ดีกว่าวิธีก่อนหน้านี้แล้ว เนื่องจากหนึ่งในค่าสัมประสิทธิ์สำหรับตัวแปรอิสระในแถวดัชนีนั้นไม่เป็นค่าลบ
เพื่อปรับปรุงแผน ไปที่ฉากซิมเพล็กซ์ถัดไป
หาจำนวนที่ใหญ่ที่สุดของตัวเลข 4 และ . ตัวเลขนี้คือ 4 ดังนั้น คอลัมน์นำหน้าคือ
ในการหาแถวนำ ให้หา
.
ดังนั้น เส้นนำคือเส้นที่มี . แต่พวกมันอยู่ด้วยกันแล้วท่ามกลางตัวแปรอิสระ ดังนั้น ในการถ่ายโอนตัวแปรถัดไปจากแบบฟรีไปเป็นแบบพื้นฐาน เราจึงเลือกคอลัมน์นำหน้าอีกคอลัมน์หนึ่ง ซึ่งเป็นคอลัมน์ที่เขียนขึ้น
ในการหาแถวนำ ให้หา
.
ดังนั้นบรรทัดสำคัญคือบรรทัดที่เขียนและองค์ประกอบนำคือ 1
ในตารางซิมเพล็กซ์ที่ห้า ตัวแปรพื้นฐานใหม่จะถูกเขียนในบรรทัดแรก ในคอลัมน์ที่เป็นอยู่ เราเขียนตัวแปรอิสระใหม่
เส้นแรก:
ค่าสัมประสิทธิ์เสริม:
| ตารางที่ 5 | ||||
| ไม่ทราบพื้นฐาน | สมาชิกฟรี | ไม่ทราบที่หลวม | สัมประสิทธิ์เสริม | |
| X5 | X6 | |||
| X3 | 2 | -1 | 1 | |
| X4 | 10 | 2 | ||
| X1 | 8 | 1 | ||
| X2 | 6 | 1 | ||
| F | 20 | 1 | 3 | 3 |
ลองค้นหาทันทีว่าวิธีแก้ปัญหานั้นไม่เหมาะสมหรือไม่ ดังนั้น สำหรับแถวที่เหลือ เราคำนวณเฉพาะเงื่อนไขว่าง (เพื่อค้นหาค่าของตัวแปรพื้นฐานเมื่อตัวแปรอิสระเท่ากับศูนย์) และค่าสัมประสิทธิ์ของตัวแปรอิสระในแถวดัชนี
สมาชิกฟรี:
ในบรรทัดที่สอง ;
ในบรรทัดที่สาม ;
บนบรรทัดที่สี่
เส้นดัชนี:
เราดูที่ตารางซิมเพล็กซ์ 5 เราเห็นว่าได้คำตอบที่ดีที่สุดแล้ว เนื่องจากค่าสัมประสิทธิ์ของค่าไม่ทราบค่าอิสระในแถวดัชนีนั้นไม่เป็นค่าลบ
วิธีซิมเพล็กซ์พร้อมการแปลงเชิงพีชคณิต
ลองแก้ด้วยการแปลงพีชคณิตในตัวอย่างเดียวกับในย่อหน้าก่อน ควรสังเกตว่าเมื่อแก้วิธีซิมเพล็กซ์ประเภทนี้ จะดีกว่าที่จะไม่เขียนฟังก์ชันเป้าหมายในแบบฟอร์ม เนื่องจากเป็นเรื่องง่ายที่จะสับสนในสัญญาณ แต่ในกรณีนี้ จุดอัลกอริธึมที่กำหนดเกณฑ์ความเหมาะสมจะได้รับการแก้ไขดังนี้
หากพบค่าสูงสุด (ต่ำสุด) ของรูปแบบเชิงเส้นและไม่มีตัวแปรที่ไม่เป็นพื้นฐานที่มีค่าสัมประสิทธิ์บวก (ลบ) ในนิพจน์ แสดงว่าเป็นไปตามเกณฑ์ความเหมาะสมและผลลัพธ์พื้นฐานที่ได้คือค่าที่เหมาะสมที่สุด - การแก้ปัญหาสิ้นสุดลง หากเมื่อค้นหาค่าสูงสุด (ต่ำสุด) ของรูปแบบเชิงเส้น นิพจน์ประกอบด้วยตัวแปรที่ไม่เป็นพื้นฐานอย่างน้อยหนึ่งตัวที่มีค่าสัมประสิทธิ์เชิงบวก (เชิงลบ) ให้ไปที่โซลูชันพื้นฐานใหม่
ตัวอย่าง.หาค่าสูงสุดของฟังก์ชันภายใต้ข้อจำกัด
ขั้นตอนที่ 1 เราแนะนำตัวแปรที่ไม่เป็นลบเพิ่มเติมและลดระบบอสมการนี้ให้เป็นระบบสมการที่เท่ากัน
.
ตัวแปรเพิ่มเติมที่นำมาใช้เป็นตัวแปรหลักเนื่องจากในกรณีนี้จะพบวิธีแก้ปัญหาพื้นฐานของระบบได้ง่าย แล้วและเป็นตัวแปรรอง
เราได้แสดงตัวแปรหลักในแง่ของตัวแปรที่ไม่ใช่พื้นฐาน
ดังนั้น การแบ่งตัวแปรออกเป็นระดับพื้นฐานและไม่ใช่พื้นฐาน จึงสอดคล้องกับวิธีแก้ปัญหาพื้นฐาน 
ซึ่งไม่ถูกต้อง (ตัวแปรสองตัวเป็นค่าลบ) ดังนั้นจึงไม่เหมาะสม มาเริ่มกันต่อจากโซลูชันพื้นฐานนี้ไปเป็นโซลูชันที่ปรับปรุงแล้วกัน
ในการตัดสินใจว่าควรย้ายตัวแปรใดจากตัวแปรที่ไม่ใช่ตัวหลักไปยังตัวการ ให้พิจารณาสมการใดสมการหนึ่งที่มีอยู่ของระบบสุดท้ายที่มีพจน์ว่างเชิงลบ ตัวอย่างเช่น สมการที่สอง มันแสดงให้เห็นและสามารถแปลเป็นตัวแปรหลักได้ เนื่องจากในสมการนี้พวกมันมีค่าสัมประสิทธิ์บวก (ดังนั้น เมื่อมันเพิ่มขึ้น และสิ่งนี้จะเกิดขึ้นถ้าเราแปลพวกมันเป็นตัวแปรหลัก ตัวแปรจะเพิ่มขึ้น)
ลองแปลเป็นตัวแปรหลักกัน ในการพิจารณาว่าตัวแปรใดควรถูกถ่ายโอนจากตัวแปรหลักไปยังตัวแปรพื้นฐาน เราจะหาค่าสัมบูรณ์ของอัตราส่วนที่น้อยที่สุดของสมาชิกอิสระของระบบต่อสัมประสิทธิ์ที่ เรามี . ได้มาจากสมการที่สาม ซึ่งแสดงว่าตัวแปรนั้นต้องถูกแปลงเป็นตัวแปรที่ไม่ใช่พื้นฐาน ซึ่งเป็นค่าบวกในคำตอบพื้นฐานดั้งเดิม ดังนั้น โซลูชันพื้นฐานที่ได้รับ เช่นเดียวกับโซลูชันดั้งเดิม มีองค์ประกอบเชิงลบสองส่วน กล่าวคือ จะไม่มีการปรับปรุงในการเปลี่ยนไปใช้โซลูชันพื้นฐานดังกล่าว
วิธีซิมเพล็กซ์− เป็นวิธีการแจงนับแบบสั่งของแผนอ้างอิง (การสั่งซื้อได้รับการประกันโดยการเปลี่ยนแปลงที่ซ้ำซากจำเจในมูลค่าของฟังก์ชันวัตถุประสงค์ในระหว่างการเปลี่ยนไปใช้แผนถัดไป) ในกรณีนี้ จำเป็นต้องปฏิบัติตามหลักการ: ขั้นตอนต่อไปแต่ละขั้นควรปรับปรุง หรือในกรณีที่ร้ายแรง ไม่ทำให้ค่าของฟังก์ชันวัตถุประสงค์แย่ลง
เพื่อแก้ปัญหา LLP วิธีซิมเพล็กซ์มันถูกลดขนาดเป็นรูปแบบบัญญัติเช่น จากข้อ จำกัด - ความไม่เท่าเทียมกันจำเป็นต้องสร้างข้อ จำกัด - ความเท่าเทียมกัน เมื่อต้องการทำเช่นนี้ ข้อจำกัดแต่ละข้อจะถูกเสริมด้วยเพิ่มเติมที่ไม่เป็นลบ ตัวแปรงบดุลด้วยเครื่องหมาย “+” หากเครื่องหมายอสมการคือ “£” และใช้เครื่องหมาย “–” หากเครื่องหมายอสมการคือ “³”
ในฟังก์ชันวัตถุประสงค์ ตัวแปรเพิ่มเติมเหล่านี้ป้อนค่าสัมประสิทธิ์เป็นศูนย์ เช่น รายการฟังก์ชันเป้าหมายจะไม่เปลี่ยนแปลง ตัวแปรแต่ละตัวที่ไม่อยู่ภายใต้เงื่อนไขที่ไม่เป็นลบสามารถแสดงเป็นความแตกต่างของตัวแปรที่ไม่เป็นลบสองตัว:
หากข้อจำกัดของงานสะท้อนถึงการมีอยู่และการใช้ทรัพยากร ค่าตัวเลขของตัวแปรเพิ่มเติมในแผนงานซึ่งเขียนในรูปแบบบัญญัติจะเท่ากับจำนวนทรัพยากรที่ไม่ได้ใช้
ในการแก้ปัญหาด้วยวิธีซิมเพล็กซ์ เราจะใช้ ตารางซิมเพล็กซ์ที่สั้นลงของระบบสมการเชิงเส้นและวิธีกำจัดจอร์แดนที่แก้ไขแล้ว.
1. เราจัดทำแผนพื้นฐานแผนแรก
ภารกิจยังคงเหมือนเดิม ให้เรานำรูปแบบมาตรฐานของระบบอสมการ (1) มาอยู่ในรูปแบบบัญญัติของระบบสมการโดยการเพิ่มตัวแปรสมดุลเพิ่มเติม x 3 , x 4 , x 5 ,x 6 .
ในแง่เศรษฐศาสตร์ ค่าของตัวแปรเพิ่มเติม x 3 , x 4 , x 5 กำหนดความสมดุลของวัตถุดิบหลังการขายผลิตภัณฑ์
เมทริกซ์ของระบบผลลัพธ์ของสมการมีรูปแบบดังนี้
จะเห็นได้ว่าในเมทริกซ์ อาฐานรองของลำดับที่ 4 คือดีเทอร์มีแนนต์ ประกอบด้วยสัมประสิทธิ์หน่วยสำหรับตัวแปรเพิ่มเติม x 3 , x 4 , x 5 ,x 6 เนื่องจากไม่เป็นศูนย์และเท่ากับ 1 ซึ่งหมายความว่าเวกเตอร์คอลัมน์สำหรับตัวแปรเหล่านี้มีความเป็นอิสระเชิงเส้น กล่าวคือ รูปร่าง พื้นฐานและตัวแปรที่เกี่ยวข้อง x 3 , x 4 , x 5 ,x 6 คือ ขั้นพื้นฐาน(ขั้นพื้นฐาน). ตัวแปร x 1 , x 2 จะถูกเรียกว่า ฟรี(ส่วนน้อย).
ถ้าตัวแปรอิสระ x 1 และ x 2 เพื่อตั้งค่าที่แตกต่างกัน จากนั้น แก้ระบบด้วยความเคารพต่อตัวแปรพื้นฐาน เราได้รับชุดโซลูชันเฉพาะจำนวนไม่จำกัด หากตั้งค่าเพียงศูนย์สำหรับตัวแปรอิสระจากนั้นจากชุดโซลูชันเฉพาะที่ไม่มีที่สิ้นสุด โซลูชั่นพื้นฐาน- แผนพื้นฐาน
เพื่อหาว่าตัวแปรสามารถเป็นตัวแปรพื้นฐานได้หรือไม่ จำเป็นต้องคำนวณดีเทอร์มีแนนต์ที่ประกอบด้วยสัมประสิทธิ์ของตัวแปรเหล่านี้ หากดีเทอร์มีแนนต์นี้ไม่เท่ากับศูนย์ ตัวแปรเหล่านี้เป็นตัวแปรพื้นฐานได้
จำนวนคำตอบพื้นฐานและจำนวนกลุ่มของตัวแปรพื้นฐานที่สอดคล้องกันต้องไม่เกิน โดยที่ นคือจำนวนตัวแปรทั้งหมด rคือจำนวนตัวแปรพื้นฐาน r≤ ม≤ น.
สำหรับงานของเรา r = 4; น= 6. จากนั้น กล่าวคือ ตัวแปรพื้นฐานได้ 15 กลุ่มจาก 4 ตัวแปร (หรือ 15 คำตอบพื้นฐาน)
ให้เราแก้ระบบสมการเทียบกับตัวแปรพื้นฐาน x 3 , x 4 , x 5 ,x 6:
สมมติว่าตัวแปรอิสระ x 1 = 0, x 2 = 0 เราได้รับค่าของตัวแปรพื้นฐาน: x 3 = 312; x 4 = 15; x 5 = 24;x 6 = -10 นั่นคือ คำตอบพื้นฐานจะเป็น = (0; 0; 312; 15; 24; -10)
วิธีแก้ปัญหาพื้นฐานนี้คือ รับไม่ได้, เพราะ x 6 = –10 ≤ 0 และโดยเงื่อนไขข้อจำกัด x 6 ≥ 0 ดังนั้น แทนที่จะเป็นตัวแปร x 6 เป็นพื้นฐาน คุณต้องใช้ตัวแปรอื่นจากตัวแปรอิสระ x 1 หรือ x 2 .
เราจะดำเนินการแก้ไขเพิ่มเติมโดยใช้ตารางซิมเพล็กซ์แบบย่อ เติมแถวของตารางแรกด้วยค่าสัมประสิทธิ์ของระบบดังนี้ (ตารางที่ 1):
ตารางที่ 1
F- สตริงเรียกว่า ดัชนี. เต็มไปด้วยค่าสัมประสิทธิ์ฟังก์ชันวัตถุประสงค์ที่มีเครื่องหมายตรงข้าม เนื่องจากสมการของฟังก์ชันสามารถแสดงเป็น F = 0 – (– 4x 1 – 3x 2).
ในคอลัมน์สมาชิกอิสระ ข ฉันมีองค์ประกอบเชิงลบ ข 4 = -10 นั่นคือ การแก้ปัญหาของระบบไม่ถูกต้อง เพื่อให้ได้โซลูชันที่ถูกต้อง (แผนพื้นฐาน) องค์ประกอบ ข 4 ต้องทำให้ไม่เป็นลบ
เลือก x 6 - บรรทัดที่มีสมาชิกติดลบฟรี บรรทัดนี้มีองค์ประกอบเชิงลบ เลือกอย่างใดอย่างหนึ่ง เช่น "-1" ใน x 1 -คอลัมน์ และ x 1 - คอลัมน์ยอมรับเป็น คอลัมน์อนุญาต(มันจะกำหนดว่าตัวแปร x 1 จะเปลี่ยนจากฟรีเป็นพื้นฐาน)
เราแบ่งปันสมาชิกฟรี ข ฉันในองค์ประกอบที่เกี่ยวข้อง เป็นกำลังแก้ไขคอลัมน์ เราจะได้ การประเมินความสัมพันธ์Θ ผม==(24, 15, 12, 10) ของเหล่านี้ เราเลือกค่าบวกที่น้อยที่สุด (minΘ ผม=10) ซึ่งจะตรงกับ สายการอนุญาต. สตริงการอนุญาตกำหนดตัวแปร x jซึ่งในขั้นตอนต่อไปจะยื่นออกมาจากพื้นฐานและกลายเป็นอิสระ นั่นเป็นเหตุผลที่ x 6 -line เป็นบรรทัดที่อนุญาต และองค์ประกอบ "-1" คือ องค์ประกอบที่เปิดใช้งาน. เราวงกลมมัน ตัวแปร x 1 และ x 6 ถูกเปลี่ยน
อัตราส่วนโดยประมาณ Θ ผมในแต่ละบรรทัดถูกกำหนดโดยกฎ:
1) Θ ผม= ถ้า ข ฉันและ เป็นมีสัญญาณต่างกัน
2) Θ ผม= ∞ ถ้า ข ฉัน= 0 และ เป็น < 0;
3) Θ ผม= ∞ ถ้า เป็น = 0;
4) Θ ผม= 0 ถ้า ข ฉัน= 0 และ เป็น > 0;
5) Θ ผม= ถ้า ข ฉันและ เป็นมีสัญญาณเดียวกัน
เราใช้ขั้นตอนของการกำจัด Jordanian elimination (MJJI) ที่แก้ไขด้วยองค์ประกอบที่อนุญาตและรวบรวมตารางใหม่ (ตารางที่ 2) ตามกฎต่อไปนี้:
1) แทนที่องค์ประกอบการแก้ไข (RE) ค่าจะถูกตั้งค่าผกผันเช่น ;
2) องค์ประกอบของเส้นอนุญาตแบ่งออกเป็น RE;
3) องค์ประกอบของคอลัมน์แก้ไขแบ่งออกเป็น RE และเครื่องหมายเปลี่ยนไป
4) พบองค์ประกอบที่เหลือตามกฎสี่เหลี่ยมผืนผ้า:
จากตาราง. 2 แสดงว่าสมาชิกฟรีใน ข ฉัน-คอลัมน์ไม่เป็นค่าลบ ดังนั้นจึงได้วิธีแก้ปัญหาเบื้องต้นที่ยอมรับได้ - แผนฐานแรก= (10; 0; 182; 5; 4; 0). ในกรณีนี้ ค่าของฟังก์ชัน F() = 40. ในทางเรขาคณิต ตรงกับยอด F(10; 0) สารละลายรูปหลายเหลี่ยม (รูปที่ 1)
ตารางที่ 2
2. เราตรวจสอบแผนเพื่อความเหมาะสมแผนฐานไม่เหมาะสมเพราะใน F-line มีค่าสัมประสิทธิ์เป็นลบ "-4" เราปรับปรุงแผน
3. หาเส้นฐานใหม่
เราเลือกองค์ประกอบการอนุญาตตามกฎ:
เราเลือกค่าสัมประสิทธิ์เชิงลบที่น้อยที่สุดใน F-line "-4" ซึ่งกำหนดคอลัมน์ที่เปิดใช้งาน - x 6; ตัวแปร x 6 แปลเป็นพื้นฐาน;
เราหาอัตราส่วน Θ ผมในหมู่พวกเขาเราเลือกค่าบวกที่เล็กที่สุดซึ่งสอดคล้องกับสตริงที่อนุญาต:
นาที Θ ผม = นาที(14, 5, 2, ∞) = 2 ดังนั้น x 5 - บรรทัด - อนุญาต, ตัวแปร x 5 เราแปลเป็นฟรี (ตัวแปร x 5 และ xสลับกัน 6 ตัว)
ที่จุดตัดของแถวและคอลัมน์ที่อนุญาตคือองค์ประกอบที่อนุญาต "2";
เราทำตามขั้นตอน SHMZhI เราสร้างตาราง 3 ตามกฎข้างต้นและรับแผนอ้างอิงใหม่ = (12; 0; 156; 3; 0; 2)
ตารางที่ 3
4. ตรวจสอบแผนพื้นฐานใหม่เพื่อความเหมาะสม
แผนฐานยังไม่เหมาะสมเนื่องจากใน F-line มีค่าสัมประสิทธิ์เป็นลบ "-1" ค่าฟังก์ชัน F() = 48 ซึ่งสอดคล้องกับยอดทางเรขาคณิต อี(12; 0) สารละลายรูปหลายเหลี่ยม (รูปที่ 1) เราปรับปรุงแผน
5. หาเส้นฐานใหม่
x 2 คอลัมน์ได้รับอนุญาตเนื่องจากใน F-line ค่าสัมประสิทธิ์เชิงลบที่เล็กที่สุด "-1" อยู่ใน x 2 คอลัมน์ (Δ 2 = -1) หาที่เล็กที่สุด Θ ผม: นาที Θ ผม = นาที(≈ 9, 6, ∞, 24) = 6 ดังนั้น xบรรทัดที่ 4 - อนุญาต องค์ประกอบอนุญาต "1/2" การสลับตัวแปร x 2 และ xสี่. เราทำตามขั้นตอน SHMZhI เราสร้างตาราง 4 เราได้รับแผนอ้างอิงใหม่ = (9; 6; 51; 0; 0; 5)
6. การตรวจสอบแผนพื้นฐานเพื่อความเหมาะสม
ที่ F-line สัมประสิทธิ์ทั้งหมดไม่เป็นค่าลบ ดังนั้น แผนอ้างอิงจึงเหมาะสมที่สุด ทางเรขาคณิตสอดคล้องกับจุด ดี(9;6) (ดูรูปที่ 1) แผนที่เหมาะสมจะให้ค่าสูงสุดของฟังก์ชันวัตถุประสงค์ c.u.
หลัก แนวคิดของวิธีการแบบซิมเพล็กซ์ในการแก้ปัญหา LLPประกอบด้วยการปรับปรุงโซลูชั่นการสนับสนุน LLP อย่างสม่ำเสมอ
มีหลายวิธีในการเขียนวิธีซิมเพล็กซ์
- รูปแบบพื้นฐานของวิธีซิมเพล็กซ์
- วิธี Simplex ในรูปแบบของตาราง Simplex
- แก้ไขวิธีซิมเพล็กซ์;
- วิธี Simplex ในรูปแบบคอลัมน์
- วิธี Simplex ในรูปแบบแถว
มากำหนดค่าสูงสุดของฟังก์ชันวัตถุประสงค์ F(X) = 3x 1 +5x 2 +4x 3 ภายใต้เงื่อนไขข้อจำกัดต่อไปนี้
0.1x 1 +0.2x 2 +0.4x 3 ≤1100
0.05x 1 +0.02x 2 +0.02x 3 ≤120
3x1 +x2 +2x3 ≤8000
ในการสร้างแผนอ้างอิงแรก เราลดระบบความไม่เท่าเทียมกันให้เป็นระบบสมการโดยการแนะนำตัวแปรเพิ่มเติม (การเปลี่ยนผ่านเป็นรูปแบบบัญญัติ)
0.1x1 + 0.2x2 + 0.4x3 + 1x4 + 0x5 + 0x6 = 1100
0.05x1 + 0.02x2 + 0.02x3 + 0x4 + 1x5 + 0x6 = 120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 8000
สัญกรณ์พื้นฐานของวิธีซิมเพล็กซ์
| การแก้ปัญหาดำเนินการโดยการแสดงตัวแปรพื้นฐานผ่านตัวแปรที่ไม่ใช่พื้นฐาน: x0 = 3x1 +5x2 +4x3 x 4 = 1100-0.1x 1 -0.2x 2 -0.4x 3 x 5 = 120-0.05x 1 -0.02x 2 -0.02x 3 x 6 = 8000-3x 1 -x 2 -2x 3 |
วิธีซิมเพล็กซ์ในรูปแบบของตารางซิมเพล็กซ์
การแก้ปัญหาจะดำเนินการในรูปแบบของตารางซิมเพล็กซ์ แบบฟอร์มนี้ออกแบบมาสำหรับการคำนวณบนคอมพิวเตอร์ เมื่อใช้พื้นฐานเทียม จะใช้หมายเลขพิเศษ M (ปกติคือ 10,000)| วางแผน | พื้นฐาน | ที่ | x 1 | x2 | x 3 | x4 | x5 | x6 | นาที |
| 1 | x4 | 1100 | 0.1 | 0.2 | 0.4 | 1 | 0 | 0 | 5500 |
| x5 | 120 | 0.05 | 0.02 | 0.02 | 0 | 1 | 0 | 6000 | |
| x6 | 8000 | 3 | 1 | 2 | 0 | 0 | 1 | 8000 | |
| เส้นดัชนี | เอฟ(X1) | 0 | -3 | -5 | -4 | 0 | 0 | 0 | 0 |
| 2 | x2 | 5500 | 0.5 | 1 | 2 | 5 | 0 | 0 | 11000 |
| x5 | 10 | 0.04 | 0 | -0.02 | -0.1 | 1 | 0 | 250 | |
| x6 | 2500 | 2.5 | 0 | 0 | -5 | 0 | 1 | 1000 | |
| เส้นดัชนี | เอฟ(X2) | 27500 | -0.5 | 0 | 6 | 25 | 0 | 0 | 0 |
| 3 | x2 | 5375 | 0 | 1 | 2.25 | 6.25 | -12.5 | 0 | 11000 |
| x1 | 250 | 1 | 0 | -0.5 | -2.5 | 25 | 0 | 250 | |
| x6 | 1875 | 0 | 0 | 1.25 | 1.25 | -62.5 | 1 | 1000 | |
| เส้นดัชนี | เอฟ(X3) | 27625 | 0 | 0 | 5.75 | 23.75 | 12.5 | 0 | 0 |
แก้ไขวิธีซิมเพล็กซ์
| เมทริกซ์สัมประสิทธิ์ A = a ij เมทริกซ์ข. |
วิธี Simplex ในรูปแบบคอลัมน์
| เราส่งผ่านไปยังรูปแบบคอลัมน์ของวิธีซิมเพล็กซ์ เราแสดงตัวแปรแต่ละตัวในรูปของตัวแปรที่ไม่ใช่เบส x 0 = 0-3(-x 1)-5(-x 2)-4(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 1 = 0-1(-x 1)+0(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 2 = 0+0(-x 1)-1(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 3 = 0+0(-x 1)+0(-x 2)-1(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 4 = 1100+0.1(-x 1)+0.2(-x 2)+0.4(-x 3)+1(-x 4)+0(-x 5)+0(-x 6) x 5 = 120+0.05(-x 1)+0.02(-x 2)+0.02(-x 3)+0(-x 4)+1(-x 5)+0(-x 6) x 6 = 8000+3(-x 1)+1(-x 2)+2(-x 3)+0(-x 4)+0(-x 5)+1(-x 6) ระบบนี้สอดคล้องกับตาราง T 0 .
|
เมธอด Simplex ในรูปแบบสตริง
เป็นฐานที่ยอมรับได้เบื้องต้น เราสามารถหา B 0 = . ได้<4, 5, 6>. มันจะสอดคล้องกับตารางต่อไปนี้
|
เมทริกซ์ Q ประกอบด้วยสัมประสิทธิ์ของระบบเรียกว่า ตารางซิมเพล็กซ์สอดคล้องกับฐาน B. ฉากซิมเพล็กซ์เรียกว่า ยอมรับได้, หรือ ยอมรับได้โดยตรงถ้า q i0 ≥ 0 องค์ประกอบ q i0 ของแถวสุดท้ายของตารางซิมเพล็กซ์ Q ถูกเรียก ประมาณการสัมพัทธ์.
รูปแบบของการแก้ปัญหาโดยวิธีการพื้นฐานเทียม
สำหรับการใช้ตัวแปรเทียมที่นำมาใช้ในฟังก์ชันวัตถุประสงค์ จะมีการกำหนดโทษที่เรียกว่า M ซึ่งเป็นจำนวนบวกที่มาก ซึ่งมักจะไม่ได้ระบุผลลัพธ์ที่ได้เรียกว่าเทียม และวิธีการแก้ปัญหาเรียกว่าวิธีการพื้นฐานเทียม
นอกจากนี้ ตัวแปรเทียมไม่เกี่ยวข้องกับเนื้อหาของงาน แต่อนุญาตให้คุณสร้างจุดเริ่มต้น และกระบวนการปรับให้เหมาะสมจะบังคับให้ตัวแปรเหล่านี้ใช้ค่าศูนย์และรับรองการยอมรับของโซลูชันที่เหมาะสมที่สุด
รูปแบบของการแก้ปัญหาโดยวิธีการพื้นฐานเทียม:
- M-method (ตารางแบบง่าย);
- วิธีซิมเพล็กซ์แบบสองขั้นตอนหรือสองเฟส (สัญกรณ์พื้นฐาน วิธีโมดิฟายซิมเพล็กซ์ วิธีซิมเพล็กซ์ในรูปแบบคอลัมน์ วิธีซิมเพล็กซ์ในรูปแบบเส้น)
หากมีข้อ จำกัด เกี่ยวกับเครื่องหมาย ≥ ในเงื่อนไขของปัญหา พวกเขาสามารถลดลงเป็นรูปแบบ ∑a ji b j โดยคูณความไม่เท่าเทียมกันทั้งสองส่วนด้วย -1 เราแนะนำตัวแปรเพิ่มเติม m ตัว x n+j ≥0(j =1,m ) และแปลงข้อจำกัดให้อยู่ในรูปของความเท่าเทียมกัน
(2)
สมมุติว่าตัวแปรเริ่มต้นทั้งหมดของปัญหา x 1 , x 2 ,..., x n นั้นไม่ใช่เบสิก จากนั้นตัวแปรเพิ่มเติมจะเป็นพื้นฐานและโซลูชันเฉพาะสำหรับระบบข้อ จำกัด มีรูปแบบ
x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m . (3)
เนื่องจากในกรณีนี้ค่าของฟังก์ชันเป้าหมาย F 0 = 0 เราสามารถแทน F(x) ได้ดังนี้:
F(x)=∑c ผม x ผม + F 0 =0 (4)
ตารางซิมเพล็กซ์เริ่มต้น (ตารางซิมเพล็กซ์ 1) ถูกคอมไพล์ตามสมการ (2) และ (4) หากตัวแปรเพิ่มเติม x n+j นำหน้าด้วยเครื่องหมาย "+" เช่นใน (2) สัมประสิทธิ์ทั้งหมดก่อนตัวแปร x i และพจน์ว่าง b j จะถูกป้อนลงในตารางซิมเพล็กซ์โดยไม่มีการเปลี่ยนแปลง ค่าสัมประสิทธิ์ของฟังก์ชันเป้าหมายในระหว่างการขยายให้ใหญ่สุดจะถูกป้อนในบรรทัดล่างสุดของตารางซิมเพล็กซ์ที่มีเครื่องหมายตรงข้ามกัน สมาชิกอิสระในตารางซิมเพล็กซ์กำหนดวิธีแก้ปัญหา
อัลกอริทึมสำหรับการแก้ปัญหามีดังนี้:
ขั้นตอนที่ 1 องค์ประกอบของคอลัมน์สมาชิกอิสระจะถูกค้นหา หากทั้งหมดเป็นบวก แสดงว่าพบโซลูชันพื้นฐานที่ยอมรับได้ และควรดำเนินการในขั้นตอนที่ 5 ของอัลกอริทึม ซึ่งสอดคล้องกับการค้นหาโซลูชันที่เหมาะสมที่สุด หากมีเงื่อนไขเชิงลบใน simplex tableau เริ่มต้น แสดงว่าวิธีแก้ปัญหานั้นไม่ถูกต้อง และคุณควรไปที่ขั้นตอนที่ 2
ขั้นตอนที่ 2 เพื่อหาแนวทางแก้ไขที่เป็นไปได้ ให้ดำเนินการ ในขณะที่จำเป็นต้องตัดสินใจว่าจะรวมตัวแปรที่ไม่ใช่พื้นฐานตัวใดในเกณฑ์พื้นฐาน และตัวแปรใดที่จะถอนออกจากเกณฑ์
ตารางที่ 1.
| ตัวแปรพื้นฐาน | สมาชิกฟรีในข้อจำกัด | ตัวแปรที่ไม่ใช่พื้นฐาน | |||||
| x 1 | x2 | ... | x l | ... | x น|||
| xn+1 | ข 1 | 11 | 12 | ... | 1l | ... | 1n |
| xn+2 | ข2 | 21 | 22 | ... | 2l | ... | 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+r | b2 | r1 | r2 | ... | rl | ... | rn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+m | ข m | m1 | m2 | ... | aml | ... | amn |
| F(x)แม็กซ์ | F0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
ในการทำเช่นนี้ เลือกองค์ประกอบเชิงลบใดๆ ของคอลัมน์ของสมาชิกอิสระ (ปล่อยให้เป็น b 2 นำหรืออนุญาต หากไม่มีองค์ประกอบเชิงลบในแถวที่มีสมาชิกอิสระเชิงลบ ระบบข้อจำกัดจะไม่สอดคล้องกันและ ปัญหาไม่มีวิธีแก้ไข
ในเวลาเดียวกัน ตัวแปรที่เป็นคนแรกที่เปลี่ยนเครื่องหมายด้วยการเพิ่มขึ้นของ NP x l ที่เลือกจะไม่รวมอยู่ใน BP นี่จะเป็น x n+r ซึ่งดัชนี r ถูกกำหนดจากเงื่อนไข
เหล่านั้น. ตัวแปรที่สอดคล้องกับอัตราส่วนที่เล็กที่สุดของเทอมว่างกับองค์ประกอบของคอลัมน์นำหน้าที่เลือก ความสัมพันธ์นี้เรียกว่า ความสัมพันธ์แบบซิมเพล็กซ์ ควรพิจารณาความสัมพันธ์เชิงบวกเท่านั้น
สตริงที่สอดคล้องกับตัวแปร x n+r เรียกว่า เป็นผู้นำหรืออนุญาต องค์ประกอบของตาราง simplex a rl ซึ่งอยู่ที่จุดตัดของแถวนำและคอลัมน์นำหน้าเรียกว่าองค์ประกอบนำหน้าหรือองค์ประกอบการแก้ไขการค้นหาองค์ประกอบนำสิ้นสุดการทำงานด้วยฉากซิมเพล็กซ์ถัดไป
ขั้นตอนที่ 3 มีการคำนวณตารางแบบซิมเพล็กซ์ใหม่ ซึ่งองค์ประกอบจะคำนวณใหม่จากองค์ประกอบของตารางแบบซิมเพล็กซ์ของขั้นตอนก่อนหน้าและทำเครื่องหมายด้วยจำนวนเฉพาะ เช่น b" j, a" ji, c" i, F" 0. องค์ประกอบจะถูกคำนวณใหม่ตามสูตรต่อไปนี้:
ขั้นแรก แถวและคอลัมน์ที่นำหน้าในตารางซิมเพล็กซ์ก่อนหน้าจะถูกเติมในตารางซิมเพล็กซ์ใหม่ นิพจน์ (5) หมายความว่าองค์ประกอบ a "rl แทนที่องค์ประกอบชั้นนำเท่ากับส่วนกลับขององค์ประกอบของตาราง simplex ก่อนหน้า องค์ประกอบของแถว a ri ถูกหารด้วยองค์ประกอบนำและองค์ประกอบของ คอลัมน์ a jl จะถูกหารด้วยองค์ประกอบนำหน้าเช่นกันแต่จะมีเครื่องหมายตรงข้าม องค์ประกอบ b" r และ c" l ถูกคำนวณตามหลักการเดียวกัน
สูตรที่เหลือสามารถเขียนได้ง่ายๆ โดยใช้ .
สี่เหลี่ยมผืนผ้าถูกสร้างขึ้นตามตารางซิมเพล็กซ์แบบเก่าในลักษณะที่หนึ่งในแนวทแยงของมันถูกสร้างขึ้นโดยองค์ประกอบที่คำนวณใหม่ (a ji) และองค์ประกอบนำ (a rl) (รูปที่ 1) เส้นทแยงมุมที่สองถูกกำหนดอย่างเฉพาะเจาะจง ในการค้นหาองค์ประกอบใหม่ a "ji ผลิตภัณฑ์ขององค์ประกอบของเส้นทแยงมุมตรงข้ามหารด้วยองค์ประกอบนำหน้าจะถูกลบออกจากองค์ประกอบ a ji (ซึ่งแสดงด้วยเครื่องหมาย" - "ที่เซลล์) ในทำนองเดียวกันองค์ประกอบ b" j, (j≠r) และ c" i ถูกคำนวณใหม่ (i≠l)
ขั้นตอนที่ 4 การวิเคราะห์ตารางซิมเพล็กซ์ใหม่เริ่มจากขั้นตอนที่ 1 ของอัลกอริทึม การดำเนินการจะดำเนินต่อไปจนกว่าจะพบวิธีแก้ปัญหาพื้นฐานที่เป็นไปได้ กล่าวคือ องค์ประกอบทั้งหมดของคอลัมน์สมาชิกอิสระต้องเป็นค่าบวก
ขั้นตอนที่ 5 เราเชื่อว่าพบวิธีแก้ปัญหาพื้นฐานที่ยอมรับได้ เราดูที่สัมประสิทธิ์ของเส้นของฟังก์ชันเป้าหมาย F(x) สัญญาณของความเหมาะสมของตารางแบบซิมเพล็กซ์คือค่าที่ไม่ใช่ค่าลบของสัมประสิทธิ์สำหรับตัวแปรที่ไม่เป็นพื้นฐานในแถว F
ข้าว. 1. กฎสี่เหลี่ยมผืนผ้า
หากในสัมประสิทธิ์ของแถว F มีค่าลบ (ยกเว้นระยะว่าง) คุณต้องไปที่โซลูชันพื้นฐานอื่น เมื่อเพิ่มฟังก์ชันเป้าหมายสูงสุด พื้นฐานจะรวมตัวแปรที่ไม่ใช่พื้นฐาน (เช่น x l) ซึ่งคอลัมน์จะสอดคล้องกับค่าสัมบูรณ์สูงสุดของสัมประสิทธิ์เชิงลบ c l ในแถวล่างสุดของตารางซิมเพล็กซ์ วิธีนี้ช่วยให้คุณเลือกตัวแปรที่การเพิ่มขึ้นนำไปสู่การปรับปรุงฟังก์ชันเป้าหมายได้ คอลัมน์ที่สอดคล้องกับตัวแปร x l เรียกว่าคอลัมน์นำหน้า ในเวลาเดียวกัน ตัวแปร x n+r นั้นถูกแยกออกจากฐาน ดัชนี r ซึ่งถูกกำหนดโดยอัตราส่วนซิมเพล็กซ์ขั้นต่ำ:
แถวที่สอดคล้องกับ x n+r เรียกว่า แถวนำหน้า และองค์ประกอบของตารางซิมเพล็กซ์ a rl ซึ่งอยู่ที่จุดตัดของแถวนำและคอลัมน์นำหน้า เรียกว่า องค์ประกอบชั้นนำ
ขั้นตอนที่ 6 ตามกฎที่กำหนดไว้ในขั้นตอนที่ 3 ขั้นตอนจะดำเนินต่อไปจนกว่าจะพบวิธีแก้ปัญหาที่เหมาะสมหรือสรุปได้ว่าไม่มีอยู่จริง
หากในกระบวนการเพิ่มประสิทธิภาพโซลูชันในคอลัมน์นำหน้า องค์ประกอบทั้งหมดไม่เป็นค่าบวก จะไม่สามารถเลือกแถวนำหน้าได้ ในกรณีนี้ ฟังก์ชันในโดเมนของการแก้ปัญหาที่ยอมรับได้จะไม่ถูกจำกัดจากด้านบนและ F max ->&∞
หากในขั้นตอนต่อไปของการค้นหาตัวแปรพื้นฐานตัวใดตัวหนึ่งมีค่าเท่ากับศูนย์ โซลูชันพื้นฐานที่เกี่ยวข้องจะเรียกว่าเสื่อมสภาพ ในกรณีนี้การวนซ้ำที่เรียกว่าเกิดขึ้นซึ่งมีลักษณะของความจริงที่ว่าการรวมกันของ BP แบบเดียวกันเริ่มทำซ้ำด้วยความถี่ที่แน่นอน (ในกรณีนี้ค่าของฟังก์ชัน F จะถูกรักษาไว้) และไม่สามารถเปลี่ยนเป็น โซลูชันพื้นฐานใหม่ที่ยอมรับได้ การวนรอบเป็นข้อเสียเปรียบหลักของวิธีซิมเพล็กซ์ แต่ก็ค่อนข้างหายาก ในทางปฏิบัติ ในกรณีเช่นนี้ เรามักจะปฏิเสธที่จะป้อนตัวแปรพื้นฐานซึ่งคอลัมน์นั้นสอดคล้องกับค่าสัมบูรณ์สูงสุดของสัมประสิทธิ์เชิงลบในฟังก์ชันเป้าหมาย และสุ่มเลือกวิธีแก้ปัญหาพื้นฐานใหม่
ตัวอย่างที่ 1 แก้ปัญหา
สูงสุด (F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1.2 ≥0)
วิธี Simplex และให้การตีความทางเรขาคณิตของกระบวนการแก้ปัญหา
การตีความแบบกราฟิกของการแก้ปัญหาแสดงในรูปที่ 2. ถึงค่าสูงสุดของฟังก์ชันเป้าหมายที่ด้านบนของ ODZP พร้อมพิกัด มาแก้ปัญหาโดยใช้ตารางซิมเพล็กซ์ เราคูณข้อ จำกัด ที่สองด้วย (-1) และแนะนำตัวแปรเพิ่มเติมเพื่อนำความไม่เท่าเทียมกันมาสู่รูปแบบของความเท่าเทียมกัน
ตัวแปรเริ่มต้น x 1 และ x 2 ถือเป็นตัวแปรพื้นฐาน และตัวแปรเพิ่มเติม x 3 , x 4 และ x 5 ถือเป็นพื้นฐาน และเรารวบรวมตารางแบบซิมเพล็กซ์ (ตารางแบบซิมเพล็กซ์ 2) โซลูชันที่สอดคล้องกับตารางซิมเพล็กซ์ 2 ไม่ถูกต้อง; องค์ประกอบชั้นนำถูกร่างและเลือกตามขั้นตอนที่ 2 ของอัลกอริทึมด้านบน แท็บซิมเพล็กซ์ถัดไป 3 กำหนดโซลูชันพื้นฐานที่ยอมรับได้ 2 องค์ประกอบชั้นนำถูกร่างและเลือกตามขั้นตอนที่ 5 ของอัลกอริทึมสำหรับการแก้ปัญหา แท็บ 4 สอดคล้องกับวิธีแก้ปัญหาที่ดีที่สุดของปัญหา ดังนั้น: x 1 = x 5 = 0; x 2 \u003d 4; x 3 \u003d 3; x 4 = 8; F สูงสุด = 20
ข้าว. 2. การแก้ปัญหาแบบกราฟิก
