การแก้สมการเชิงเดี่ยวโดยใช้วิธีตัวอย่าง การแก้ปัญหาการผลิตโดยใช้วิธีตารางซิมเพล็กซ์ การแปลงสตริงความละเอียด

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

เพื่อแก้ปัญหา ZLP วิธีเริมมันถูกนำมาสู่รูปแบบบัญญัติเช่น จากข้อจำกัด-ความไม่เท่าเทียม จำเป็นต้องสร้างข้อจำกัด-ความเท่าเทียมกัน เมื่อต้องการทำเช่นนี้ จะมีการใส่ปัจจัยที่ไม่เป็นลบเพิ่มเติมเข้าไปในข้อจำกัดแต่ละข้อ ตัวแปรงบดุลโดยมีเครื่องหมาย “+” หากเครื่องหมายอสมการคือ “£” และมีเครื่องหมาย “–” หากเครื่องหมายอสมการคือ “³”

ในฟังก์ชันวัตถุประสงค์ ตัวแปรเพิ่มเติมเหล่านี้รวมอยู่ในค่าสัมประสิทธิ์เป็นศูนย์ เช่น รายการของฟังก์ชันวัตถุประสงค์จะไม่เปลี่ยนแปลง ตัวแปรแต่ละตัวที่ไม่อยู่ภายใต้เงื่อนไขที่ไม่เป็นลบสามารถแสดงเป็นผลต่างของตัวแปรที่ไม่เป็นลบสองตัวได้:

หากข้อจำกัดของงานสะท้อนถึงความพร้อมใช้งานและการใช้ทรัพยากร ค่าตัวเลขของตัวแปรเพิ่มเติมในแผนงานที่เขียนในรูปแบบมาตรฐานจะเท่ากับจำนวนทรัพยากรที่ไม่ได้ใช้

เราจะใช้วิธี simplex เพื่อแก้ปัญหา ตารางซิมเพล็กซ์ของระบบสมการเชิงเส้นแบบสั้นและวิธีการกำจัดจอร์แดนแบบดัดแปลง.

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 ตั้งค่าที่แตกต่างกัน จากนั้นเมื่อแก้ระบบด้วยความเคารพต่อตัวแปรพื้นฐาน เราจะได้คำตอบบางส่วนจำนวนอนันต์ หากตัวแปรอิสระให้ค่าเป็นศูนย์เท่านั้น ก็สามารถเลือกโซลูชันเฉพาะจากชุดอนันต์ได้ โซลูชั่นพื้นฐาน- แผนพื้นฐาน

หากต้องการทราบว่าตัวแปรสามารถเป็นตัวแปรพื้นฐานได้หรือไม่ จำเป็นต้องคำนวณดีเทอร์มิแนนต์ที่ประกอบด้วยค่าสัมประสิทธิ์ของตัวแปรเหล่านี้ หากดีเทอร์มิแนนต์นี้ไม่เท่ากับศูนย์ ตัวแปรเหล่านี้อาจเป็นตัวแปรพื้นฐานได้

จำนวนวิธีแก้ปัญหาพื้นฐานและจำนวนกลุ่มของตัวแปรพื้นฐานที่สอดคล้องกันต้องไม่เกิน , โดยที่ n– จำนวนตัวแปรทั้งหมด ร– จำนวนตัวแปรพื้นฐาน ร≤ ม≤ n.

สำหรับภารกิจของเรา ร = 4; n= 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โดยพื้นฐานแล้วเราต้องใช้ตัวแปรอื่นจากตัวแปรอิสระ x 1 หรือ x 2 .

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

ตารางที่ 1

เอฟ-สายนี้เรียกว่า ดัชนี. เต็มไปด้วยค่าสัมประสิทธิ์ของฟังก์ชันวัตถุประสงค์ที่มีเครื่องหมายตรงกันข้ามเนื่องจากสมการของฟังก์ชันสามารถแสดงได้ในรูปแบบ เอฟ = 0 – (– 4x 1 – 3x 2).

ในคอลัมน์สมาชิกฟรี ข ฉันมีองค์ประกอบเชิงลบ ข 4 = –10 เช่น วิธีแก้ปัญหาระบบไม่ถูกต้อง เพื่อให้ได้แนวทางแก้ไขที่เป็นไปได้ (แผนอ้างอิง) องค์ประกอบ ข 4 จะต้องทำให้ไม่เป็นลบ

เลือก x 6 -สตริงที่มีเทอมอิสระเป็นลบ บรรทัดนี้มีองค์ประกอบเชิงลบ เลือกรายการใดรายการหนึ่ง เช่น “–1” ใน x 1 -คอลัมน์และ xคอลัมน์ 1 ถือเป็น คอลัมน์ความละเอียด(มันจะกำหนดว่าตัวแปร x 1 จะย้ายจากอิสระไปเป็นพื้นฐาน)

เราแบ่งสมาชิกฟรี ข ฉันไปยังองค์ประกอบที่สอดคล้องกัน เป็นคอลัมน์ความละเอียด เราได้ ความสัมพันธ์เชิงประเมินΘ ฉัน= = (24, 15, 12, 10) ในจำนวนนี้ เราเลือกค่าบวกที่น้อยที่สุด (minΘ ฉัน=10) ซึ่งจะสอดคล้องกัน เส้นอนุญาต. สตริงการเปิดใช้งานจะกำหนดตัวแปร เอ็กซ์เจซึ่งในขั้นตอนต่อไปจะยื่นออกมาจากฐานและเป็นอิสระ นั่นเป็นเหตุผล xบรรทัดที่ 6 คือบรรทัดที่เปิดใช้งาน และองค์ประกอบ “–1” คือ องค์ประกอบที่อนุญาต. เรามาวงกลมกันเถอะ ตัวแปร x 1 และ x 6 สลับกัน.

อัตราส่วนโดยประมาณΘ ฉันในแต่ละบรรทัดจะถูกกำหนดตามกฎ:

1) Θ ฉัน= ถ้า ข ฉันและ เป็นมีสัญญาณที่แตกต่างกัน

2) Θ ฉัน= ∞ ถ้า ข ฉัน= 0 และ เป็น < 0;

3) Θ ฉัน= ∞ ถ้า เป็น = 0;

4) Θ ฉัน= 0 ถ้า ข ฉัน= 0 และ เป็น > 0;

5)Θ ฉัน= ถ้า ข ฉันและ เป็นมีสัญญาณเหมือนกัน

เราทำขั้นตอนการแก้ไข Jordan elimination (JEME) ด้วยองค์ประกอบการแก้ปัญหา และเขียนตารางใหม่ (ตารางที่ 2) ตามกฎต่อไปนี้:

1) แทนที่องค์ประกอบการแก้ไข (RE) ค่าจะถูกตั้งค่าซึ่งเป็นค่าผกผันนั่นคือ ;

2) องค์ประกอบของสตริงการเปิดใช้งานแบ่งออกเป็น RE;

3) องค์ประกอบของคอลัมน์ความละเอียดแบ่งออกเป็น RE และเครื่องหมายเปลี่ยนไป

4) พบองค์ประกอบที่เหลือตามกฎสี่เหลี่ยม:

จากโต๊ะ 2 เป็นที่ชัดเจนว่าข้อกำหนดเสรีใน ข ฉัน-คอลัมน์ไม่เป็นลบ ดังนั้น จะได้วิธีแก้ปัญหาที่เป็นไปได้เบื้องต้น - แผนอ้างอิงครั้งแรก= (10; 0; 182; 5; 4; 0) ในกรณีนี้คือค่าของฟังก์ชัน เอฟ() = 40 ในเชิงเรขาคณิต ค่านี้จะสอดคล้องกับด้านบน เอฟ(10; 0) รูปหลายเหลี่ยมของสารละลาย (รูปที่ 1)

ตารางที่ 2

2. เราตรวจสอบแผนเพื่อความเหมาะสมที่สุดแผนอ้างอิงไม่เหมาะสมเนื่องจากมา เอฟ-line มีค่าสัมประสิทธิ์ลบ “–4” เราปรับปรุงแผน

3. ค้นหาแผนอ้างอิงใหม่

เราเลือกองค์ประกอบที่อนุญาตตามกฎ:

เราเลือกค่าสัมประสิทธิ์ลบที่เล็กที่สุดมา เอฟ-line “–4” ซึ่งกำหนดคอลัมน์ที่เปิดใช้งาน – x 6; ตัวแปร x 6 ถูกแปลงเป็นพื้นฐาน

ค้นหาความสัมพันธ์Θ ฉันในหมู่พวกเขาเราเลือกค่าบวกที่เล็กที่สุดซึ่งสอดคล้องกับเส้นความละเอียด:

นาที Θ ฉัน = นาที(14, 5, 2, ∞) = 2 ดังนั้น x 5 บรรทัด – เปิดใช้งาน, ตัวแปร x 5 ถูกแปลงเป็นฟรี (ตัวแปร x 5 และ x 6 สลับกัน)

ที่จุดตัดของแถวและคอลัมน์การแก้ไขจะมีองค์ประกอบการแก้ไข "2"

เราดำเนินการขั้นตอน SMGI และสร้างตาราง 3 ตามกฎข้างต้นและเราได้แผนอ้างอิงใหม่ = (12; 0; 156; 3; 0; 2)

ตารางที่ 3

4. การตรวจสอบแผนอ้างอิงใหม่เพื่อความเหมาะสมที่สุด

แผนอ้างอิงก็ไม่เหมาะสมเช่นกัน เนื่องจากมา เอฟ-line มีค่าสัมประสิทธิ์ลบ “–1” ค่าฟังก์ชัน เอฟ() = 48 ซึ่งสอดคล้องกับด้านบนทางเรขาคณิต อี(12; 0) รูปหลายเหลี่ยมของสารละลาย (รูปที่ 1) เราปรับปรุงแผน

5. ค้นหาแผนอ้างอิงใหม่

xคอลัมน์ 2 ได้รับอนุญาต เนื่องจากใน เอฟ-line ค่าสัมประสิทธิ์ลบที่เล็กที่สุด “–1” อยู่ใน x 2 คอลัมน์ (Δ 2 = –1) เราพบΘที่เล็กที่สุด ฉัน: นาที Θ ฉัน = นาที(หยาบคาย 9, 6, ∞, 24) = 6 ดังนั้น x 4 บรรทัด – อนุญาต องค์ประกอบความละเอียด "1/2" สลับตัวแปร x 2 และ x 4. เราดำเนินการขั้นตอน SMGI และสร้างตาราง 4 เราได้แผนอ้างอิงใหม่ = (9; 6; 51; 0; 0; 5)

6. การตรวจสอบแผนอ้างอิงเพื่อความเหมาะสมที่สุด

ใน เอฟ-line ค่าสัมประสิทธิ์ทั้งหมดไม่เป็นลบ ดังนั้นแผนอ้างอิงจึงเหมาะสมที่สุด เรขาคณิตสอดคล้องกับจุด ดี(9;6) (ดูรูปที่ 1) แผนที่เหมาะสมที่สุดจะให้ค่าสูงสุดของฟังก์ชันวัตถุประสงค์ c.u.

วิธีซิมเพล็กซ์สำหรับการแก้ปัญหาการโปรแกรมเชิงเส้น

1. บทนำ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3หน้า

2. วิธี Simplex สำหรับการแก้ปัญหาการเขียนโปรแกรมเชิงเส้น . . 4-10 หน้า

3. อัลกอริธึมของวิธีซิมเพล็กซ์สำหรับการแก้ปัญหาการโปรแกรมเชิงเส้น . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11หน้า

4. ตัวอย่างการแก้ปัญหาโดยใช้วิธีซิมเพล็กซ์ . . . . . . . . . . . . . . . . . 11-15 หน้า

5. สรุป. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16หน้า

6.รายการข้อมูลอ้างอิงที่ใช้ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17หน้า

1. บทนำ

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

อัลกอริธึมสำหรับการแก้ปัญหาได้รับการกำหนดและแสดงพร้อมตัวอย่าง

1. ระบุวิธีการค้นหาโซลูชันอ้างอิงที่เหมาะสมที่สุด

2. ระบุวิธีการเปลี่ยนจากโซลูชันอ้างอิงหนึ่งไปยังอีกโซลูชันหนึ่ง โดยที่ค่าของฟังก์ชันวัตถุประสงค์จะเข้าใกล้ค่าที่เหมาะสมที่สุดมากขึ้น เช่น ระบุวิธีการปรับปรุงโซลูชันอ้างอิง

3. กำหนดเกณฑ์ที่ช่วยให้คุณสามารถหยุดค้นหาโซลูชันสนับสนุนในโซลูชันที่เหมาะสมที่สุดได้ทันที หรือสรุปข้อสรุปเกี่ยวกับการไม่มีโซลูชันที่ดีที่สุด

2. วิธี Simplex สำหรับการแก้ปัญหาการเขียนโปรแกรมเชิงเส้นฉัน

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

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

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

วิธีนี้เป็นสากล ใช้ได้กับปัญหาการโปรแกรมเชิงเส้นใดๆ ในรูปแบบมาตรฐาน ระบบข้อจำกัดในที่นี้คือระบบสมการเชิงเส้นซึ่งจำนวนสิ่งที่ไม่ทราบมากกว่าจำนวนสมการ ถ้าอันดับของระบบเป็น r เราก็สามารถเลือก r ไม่ทราบ ซึ่งเราแสดงในรูปของไม่ทราบที่เหลือ เพื่อความแน่นอน เราถือว่ามีการเลือกค่าไม่ทราบค่า X1, X2, ..., Xr ลำดับแรกติดต่อกัน จากนั้นระบบสมการของเราสามารถเขียนได้เป็น

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

ด้วยการกำหนดค่าบางอย่างให้กับตัวแปรอิสระและการคำนวณค่าของค่าพื้นฐาน (แสดงในรูปของค่าอิสระ) เราจะได้รับวิธีแก้ปัญหาที่แตกต่างกันสำหรับระบบข้อ จำกัด ของเรา ดังนั้นจึงสามารถหาวิธีแก้ปัญหาได้ เราจะสนใจวิธีแก้ปัญหาพิเศษที่ได้รับในกรณีที่ตัวแปรอิสระมีค่าเท่ากับศูนย์ วิธีแก้ปัญหาดังกล่าวเรียกว่าพื้นฐาน ซึ่งมีมากพอ ๆ กับระบบข้อจำกัดที่กำหนดประเภทพื้นฐานที่แตกต่างกัน โซลูชันพื้นฐานเรียกว่าโซลูชันพื้นฐานที่ยอมรับได้หรือโซลูชันสนับสนุนหากค่าของตัวแปรไม่เป็นลบ ถ้าตัวแปร X1, X2, ..., Xr ถูกใช้เป็นค่าพื้นฐาน ดังนั้นผลเฉลย (b1, b2,..., br, 0, ..., 0) จะเป็นค่าอ้างอิง โดยมีเงื่อนไขว่า b1, b2,... , br ≥ 0

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

ดังนั้น วิธีซิมเพล็กซ์จะแนะนำลำดับที่แน่นอนทั้งเมื่อค้นหาโซลูชันพื้นฐานแรก (เริ่มต้น) และเมื่อย้ายไปยังโซลูชันพื้นฐานอื่นๆ

การดำเนินการแก้ไขปัญหาโดยใช้วิธีซิมเพล็กซ์จะแสดงอย่างชัดเจนในแผนภาพบล็อก (รูปที่ 1)

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

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

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

ในที่นี้ สำหรับความแน่นอนของสัญกรณ์ จะถือว่าตัวแปร X1, X2, ..., Xr สามารถถือเป็นตัวแปรพื้นฐานได้ และ b1, b2,..., br ≥ 0 (ผลเฉลยพื้นฐานที่สอดคล้องกันคือ อ้างอิงหนึ่ง)

ในการรวบรวมตารางซิมเพล็กซ์ในความเท่าเทียมกันทั้งหมดในคำสั่งปัญหา คำศัพท์ที่มีตัวแปรจะถูกโอนไปทางด้านซ้าย ส่วนว่างจะถูกทิ้งไว้ทางด้านขวา เช่น ปัญหาถูกเขียนในรูปแบบของระบบความเสมอภาค:

บันทึก. ชื่อของตัวแปรพื้นฐานถูกนำมาใช้เพื่อความชัดเจนเท่านั้น และอาจปรากฏแตกต่างออกไปในตารางจริง

ขั้นตอนการทำงานกับตารางซิมเพล็กซ์ ตารางซิมเพล็กซ์แรกได้รับการเปลี่ยนแปลง สาระสำคัญคือการเปลี่ยนไปใช้โซลูชันอ้างอิงใหม่

อัลกอริทึมสำหรับการย้ายไปยังตารางถัดไปมีดังนี้:

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

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

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

x1

+x2

+x3

x1

+x2

+x3

x1

+x2

+x3

≤ = ≥

≤ = ≥

≤ = ≥

×

คำเตือน

ล้างเซลล์ทั้งหมดใช่ไหม

ปิด ล้าง

คำแนะนำในการป้อนข้อมูลตัวเลขจะป้อนเป็นจำนวนเต็ม (เช่น 487, 5, -7623 เป็นต้น) ทศนิยม (เช่น 67., 102.54 เป็นต้น) หรือเศษส่วน ต้องป้อนเศษส่วนในรูปแบบ a/b โดยที่ a และ b (b>0) เป็นจำนวนเต็มหรือเลขทศนิยม ตัวอย่าง 45/5, 6.6/76.4, -7/6.7 เป็นต้น

วิธีเริม

ตัวอย่างการแก้ ZLP โดยใช้วิธี simplex

ตัวอย่างที่ 1 แก้ปัญหาการโปรแกรมเชิงเส้นต่อไปนี้:

ด้านขวาของข้อจำกัดของระบบสมการมีรูปแบบดังนี้

มาเขียนแผนอ้างอิงปัจจุบันกัน:

แผนอ้างอิงนี้ไม่เหมาะสมเนื่องจากมีองค์ประกอบเชิงลบในแถวสุดท้าย องค์ประกอบเชิงลบที่ใหญ่ที่สุดในโมดูลัสคือ (-3) ดังนั้นเวกเตอร์จึงรวมอยู่ในฐาน x ที่ . นาที(40:6, 28:2)=20/3 สอดคล้องกับเส้นที่ 1 เวกเตอร์โผล่ออกมาจากฐาน x 3. ลองทำการกำจัดแบบเกาส์เซียนสำหรับคอลัมน์กัน x 2 โดยพิจารณาว่าองค์ประกอบนำหน้าตรงกับแถวที่ 1 มารีเซ็ตองค์ประกอบทั้งหมดของคอลัมน์นี้ยกเว้นองค์ประกอบนำหน้ากัน เมื่อต้องการทำเช่นนี้ ให้เพิ่มบรรทัดของบรรทัดที่ 2, 3, 4 ด้วยบรรทัดที่ 1 คูณด้วย -1/3, 1/6, 1/2 ตามลำดับ ต่อไปเราจะแบ่งเส้นที่มีองค์ประกอบนำด้วยองค์ประกอบนำ

แผนการอ้างอิงนี้ไม่เหมาะสมที่สุด เนื่องจากแถวสุดท้ายมีองค์ประกอบที่เป็นลบ (-3) ดังนั้นพื้นฐานจึงรวมเวกเตอร์ด้วย x 1. เรากำหนดว่าเวกเตอร์ใดออกมาจากฐาน เมื่อต้องการทำเช่นนี้ เราคำนวณ ที่ . min(44/3:11/3, 62/3:5/3)=4 สอดคล้องกับบรรทัดที่ 2 เวกเตอร์โผล่ออกมาจากฐาน x 4. ลองทำการกำจัดแบบเกาส์เซียนสำหรับคอลัมน์กัน x 1 โดยพิจารณาว่าองค์ประกอบนำหน้าสอดคล้องกับแถวที่ 2 มารีเซ็ตองค์ประกอบทั้งหมดของคอลัมน์นี้ยกเว้นองค์ประกอบนำหน้ากัน เมื่อต้องการทำเช่นนี้ ให้เพิ่มบรรทัด 1, 3, 4 โดยบรรทัดที่ 2 คูณด้วย 1/11, -5/11, 9/11 ตามลำดับ ต่อไปเราจะแบ่งเส้นที่มีองค์ประกอบนำด้วยองค์ประกอบนำ

ตาราง Simplex จะอยู่ในรูปแบบต่อไปนี้:

แผนอ้างอิงปัจจุบันเหมาะสมที่สุด เนื่องจากอยู่ในบรรทัดที่ 4 ใต้ตัวแปร ไม่มีองค์ประกอบเชิงลบ

วิธีแก้ปัญหาสามารถเขียนได้ดังนี้: .

ค่าของฟังก์ชันวัตถุประสงค์ ณ จุดนี้: เอฟ(เอ็กซ์)=.

ตัวอย่างที่ 2 ค้นหาค่าสูงสุดของฟังก์ชัน

สารละลาย.

เวกเตอร์พื้นฐาน x 4 , x 3 ดังนั้นองค์ประกอบทั้งหมดในคอลัมน์ x 4 , x 3 ใต้เส้นแนวนอนควรเป็นศูนย์

รีเซ็ตองค์ประกอบคอลัมน์ทั้งหมดให้เป็นศูนย์ x 4 ยกเว้นองค์ประกอบนำ เมื่อต้องการทำเช่นนี้ ให้เพิ่มแถวที่ 3 โดยแถวที่ 1 คูณด้วย 4 รีเซ็ตองค์ประกอบทั้งหมดของคอลัมน์ให้เป็นศูนย์ x 3 ยกเว้นองค์ประกอบนำ เมื่อต้องการทำเช่นนี้ ให้เพิ่มบรรทัดที่ 3 โดยบรรทัดที่ 2 คูณด้วย 1

ตาราง Simplex จะอยู่ในรูปแบบ:

แผนอ้างอิงนี้ไม่เหมาะสมที่สุด เนื่องจากแถวสุดท้ายมีองค์ประกอบที่เป็นลบ (-11) ดังนั้นพื้นฐานจึงรวมเวกเตอร์ด้วย x 2. เรากำหนดว่าเวกเตอร์ใดออกมาจากฐาน เมื่อต้องการทำเช่นนี้ เราคำนวณ ที่ . ดังนั้นฟังก์ชันวัตถุประสงค์จึงไม่มีขอบเขตจากด้านบน เหล่านั้น. ปัญหาการเขียนโปรแกรมเชิงเส้นไม่สามารถแก้ไขได้

ตัวอย่างการแก้ ZLP โดยใช้วิธีพื้นฐานประดิษฐ์

ตัวอย่างที่ 1 ค้นหาค่าสูงสุดของฟังก์ชัน

วิธีแก้ปัญหา เนื่องจากจำนวนเวกเตอร์พื้นฐานต้องเป็น 3 เราจึงเพิ่มตัวแปรเทียมและฟังก์ชันวัตถุประสงค์เราจึงเพิ่มตัวแปรนี้คูณด้วย −M โดยที่ M เป็นจำนวนที่มาก:

เมทริกซ์สัมประสิทธิ์ของระบบสมการมีรูปแบบ:

เวกเตอร์พื้นฐาน ดังนั้น องค์ประกอบทั้งหมดในคอลัมน์ใต้เส้นแนวนอนจะต้องเป็นศูนย์

มารีเซ็ตองค์ประกอบทั้งหมดของคอลัมน์ยกเว้นองค์ประกอบนำหน้ากัน เมื่อต้องการทำเช่นนี้ ให้เพิ่มบรรทัด 5 โดยบรรทัด 3 คูณด้วย -1

ตาราง Simplex จะอยู่ในรูปแบบ:

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

ตาราง Simplex จะอยู่ในรูปแบบต่อไปนี้:

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

ตาราง Simplex จะอยู่ในรูปแบบต่อไปนี้:

แผนอ้างอิงนี้ไม่เหมาะสมเนื่องจากมีองค์ประกอบเชิงลบในแถวสุดท้าย องค์ประกอบลบที่ใหญ่ที่สุดในโมดูลัส (-13/2) ดังนั้นพื้นฐานจึงรวมเวกเตอร์ด้วย x 3. เรากำหนดว่าเวกเตอร์ใดออกมาจากฐาน เมื่อต้องการทำเช่นนี้ เราคำนวณ ที่ สอดคล้องกับเส้นที่ 3 เวกเตอร์โผล่ออกมาจากฐาน x 5. ลองทำการกำจัดแบบเกาส์เซียนสำหรับคอลัมน์กัน x 3 โดยพิจารณาว่าองค์ประกอบนำหน้าตรงกับแถวที่ 3 มารีเซ็ตองค์ประกอบทั้งหมดของคอลัมน์นี้ยกเว้นองค์ประกอบนำหน้ากัน เมื่อต้องการทำเช่นนี้ ให้เพิ่มบรรทัดของบรรทัดที่ 1, 2, 4 กับบรรทัดที่ 3 คูณด้วย 5/3, 25/9, 65/9 ตามลำดับ ต่อไปเราจะแบ่งเส้นที่มีองค์ประกอบนำด้วยองค์ประกอบนำ

ตาราง Simplex จะอยู่ในรูปแบบต่อไปนี้:

แผนอ้างอิงปัจจุบันเหมาะสมที่สุด เนื่องจากไม่มีองค์ประกอบเชิงลบภายใต้ตัวแปรในบรรทัดที่ 4−5

วิธีแก้ไขปัญหาเดิมสามารถเขียนได้ดังนี้:

ตัวอย่างที่ 2 ค้นหาแผนการที่เหมาะสมที่สุดสำหรับปัญหาการโปรแกรมเชิงเส้นตรง:

เมทริกซ์สัมประสิทธิ์ของระบบสมการมีรูปแบบ:

เวกเตอร์พื้นฐาน x 4 , x 5 , x 6 ดังนั้น องค์ประกอบทั้งหมดในคอลัมน์ x 4 , x 5 , x 6 ใต้เส้นแนวนอนควรเป็นศูนย์

รีเซ็ตองค์ประกอบคอลัมน์ทั้งหมดให้เป็นศูนย์ x 4 ยกเว้นองค์ประกอบนำ เมื่อต้องการทำเช่นนี้ ให้เพิ่มบรรทัดที่ 4 โดยบรรทัดที่ 1 คูณด้วย -1 รีเซ็ตองค์ประกอบคอลัมน์ทั้งหมดให้เป็นศูนย์ x 5 ยกเว้นองค์ประกอบนำ เมื่อต้องการทำเช่นนี้ ให้เพิ่มบรรทัดที่ 5 โดยบรรทัดที่ 2 คูณด้วย -1 รีเซ็ตองค์ประกอบคอลัมน์ทั้งหมดให้เป็นศูนย์ x 6 ยกเว้นองค์ประกอบนำหน้า เมื่อต้องการทำเช่นนี้ ให้เพิ่มบรรทัด 5 โดยบรรทัด 3 คูณด้วย -1

ตาราง Simplex จะอยู่ในรูปแบบ:

ในบรรทัดที่ 5 องค์ประกอบที่สอดคล้องกับตัวแปร x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ไม่เป็นลบ และเป็นตัวเลขที่จุดตัดของแถวและคอลัมน์ที่กำหนด x 0 เป็นลบ แล้วปัญหาเดิมไม่มีแผนอ้างอิง ดังนั้นจึงไม่สามารถตัดสินใจได้

พิจารณาตัวอย่างของการแก้ปัญหาโดยใช้วิธีซิมเพล็กซ์รวมถึงตัวอย่างของการแก้ปัญหาแบบคู่

เนื้อหา

งาน

ในการขายสินค้าสามกลุ่ม องค์กรการค้ามีวัสดุและทรัพยากรทางการเงินที่จำกัดสามประเภทในจำนวน b 1 = 240, b 2 = 200, b 3 = 160 หน่วย ในเวลาเดียวกันสำหรับการขายสินค้า 1 กลุ่มในราคา 1,000 รูเบิล การหมุนเวียนสินค้าโภคภัณฑ์ ทรัพยากรประเภทแรกถูกใช้ไปในจำนวน 11 = 2 หน่วย ทรัพยากรประเภทที่สองมีจำนวน 21 = 4 หน่วย ทรัพยากรประเภทที่สามมีจำนวน 31 = 4 ยูนิต. สำหรับการขายสินค้า 2 และ 3 กลุ่มในราคา 1,000 รูเบิล มูลค่าการซื้อขายจะถูกใช้ตามทรัพยากรประเภทแรกในจำนวน 12 = 3, 13 = 6 หน่วย, ทรัพยากรประเภทที่สองในจำนวน 22 = 2, 23 = 4 หน่วย, ทรัพยากรของ ประเภทที่สามจำนวน 32 = 6, 33 = 8 หน่วย กำไรจากการขายสินค้าสามกลุ่มในราคา 1,000 รูเบิล มูลค่าการซื้อขายตามลำดับ c 1 = 4, c 2 = 5, c 3 = 4 (พันรูเบิล) กำหนดปริมาณและโครงสร้างตามแผนของมูลค่าการซื้อขายเพื่อเพิ่มผลกำไรขององค์กรการค้าให้สูงสุด

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

การแก้ปัญหาโดยใช้วิธีซิมเพล็กซ์

ให้ x 1, x 2, x 3 เป็นจำนวนสินค้าที่ขายในหน่วยพันรูเบิล 1, 2, 3 กลุ่มตามลำดับ จากนั้นแบบจำลองทางคณิตศาสตร์ของปัญหาจะมีรูปแบบ:

F = 4 x 1 + 5 x 2 + 4 x 3 ->สูงสุด

0)))(~)" title="delim(lbrace)(matrix(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

เราแก้วิธีซิมเพล็กซ์

เราแนะนำตัวแปรเพิ่มเติม x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 เพื่อแปลงความไม่เท่าเทียมกันให้กลายเป็นความเท่าเทียมกัน

สมมุติว่า x 4 = 240 เป็นพื้นฐาน x 5 = 200; x 6 = 160.

เราป้อนข้อมูลลงไป ตารางเริม

ตาราง Simplex หมายเลข 1

ฟังก์ชั่นวัตถุประสงค์:

0 240 + 0 200 + 0 160 = 0

เราคำนวณค่าประมาณโดยใช้สูตร:

Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0

เนื่องจากมีประมาณการเชิงลบ แผนจึงไม่เหมาะสม คะแนนต่ำสุด:

เราแนะนำตัวแปร x 2 ให้เป็นฐาน

เรากำหนดตัวแปรที่เกิดจากพื้นฐาน เมื่อต้องการทำเช่นนี้ เราจะหาอัตราส่วนที่ไม่เป็นลบที่น้อยที่สุดสำหรับคอลัมน์ x2

= 26.667

ไม่เป็นลบน้อยที่สุด: Q 3 = 26.667 เราได้ตัวแปร x 6 จากฐาน

หารบรรทัดที่ 3 ด้วย 6
จากบรรทัดที่ 1 ให้ลบบรรทัดที่ 3 คูณด้วย 3
จากบรรทัดที่ 2 ให้ลบบรรทัดที่ 3 คูณด้วย 2

เราคำนวณ:

เราได้รับตารางใหม่:

ตาราง Simplex หมายเลข 2

ฟังก์ชั่นวัตถุประสงค์:

0 160 + 0 440/3 + 5 80/3 = 400/3

เราคำนวณค่าประมาณโดยใช้สูตร:

Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6

เนื่องจากมีการประมาณการเชิงลบ Δ 1 = - 2/3 แผนจึงไม่เหมาะสม

เราแนะนำตัวแปร x 1 เข้าไปในฐาน

เรากำหนดตัวแปรที่เกิดจากพื้นฐาน เมื่อต้องการทำเช่นนี้ เราจะหาอัตราส่วนที่ไม่เป็นลบที่น้อยที่สุดสำหรับคอลัมน์ x 1

ค่าน้อยที่สุดที่ไม่เป็นลบ: Q 3 = 40 เราหาตัวแปร x 2 จากฐาน

หารบรรทัดที่ 3 ด้วย 2/3
จากบรรทัดที่ 2 ให้ลบบรรทัดที่ 3 คูณด้วย 8/3

เราคำนวณ:

เราได้รับตารางใหม่:

ตาราง Simplex หมายเลข 3

ฟังก์ชั่นวัตถุประสงค์:

0 160 + 0 40 + 4 40 = 160

เราคำนวณค่าประมาณโดยใช้สูตร:

Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1

เนื่องจากไม่มีการให้คะแนนติดลบ แผนนี้จึงเหมาะสมที่สุด

การแก้ปัญหา:

x 1 = 40; x2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x6 = 0; F สูงสุด = 160

นั่นคือจำเป็นต้องขายสินค้าประเภทแรกจำนวน 40,000 รูเบิล ไม่จำเป็นต้องขายสินค้าประเภทที่ 2 และ 3 ในกรณีนี้กำไรสูงสุดจะเป็น F max = 160,000 รูเบิล

การแก้ปัญหาแบบคู่

ปัญหาคู่มีรูปแบบ:

Z = 240 ปี 1 + 200 ปี 2 + 160 ปี 3 ->นาที

Title="delim(lbrace)(matrix(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}

เราแนะนำตัวแปรเพิ่มเติม y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 เพื่อแปลงความไม่เท่าเทียมกันให้มีความเท่าเทียมกัน

คู่ตัวแปรผันของปัญหาโดยตรงและปัญหาคู่มีรูปแบบ:

จากตารางซิมเพล็กซ์หมายเลข 3 สุดท้ายของปัญหาโดยตรง เราจะพบวิธีแก้ไขปัญหาแบบคู่:

Z นาที = F สูงสุด = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;

ใช่ 1 = 0; y2 = 0; ย 3 = 1; Z นาที = 160;

วิธีซิมเพล็กซ์เป็นหนึ่งในวิธีที่มีประสิทธิภาพมากที่สุดในการแก้ปัญหา LP เชิงตัวเลข สาระสำคัญของแนวคิด “ซิมเพล็กซ์” มีดังนี้ สำหรับวัตถุในปริภูมิ k มิติ ซิมเพล็กซ์คือเซตที่ประกอบด้วยจุดยอด k + 1 ของวัตถุนี้ดังนั้น สำหรับ k = 2 นั่นคือ บนระนาบ เริมคือจุดยอดของรูปสามเหลี่ยม สำหรับ k = 3 ค่าซิมเพล็กซ์คือจุดยอดของจัตุรมุข เช่น จัตุรมุข เป็นต้น ชื่อนี้ถูกกำหนดให้กับวิธีการด้วยเหตุผลที่ว่าขึ้นอยู่กับการค้นหาจุดยอดของ ODZP ตามลำดับเพื่อกำหนดพิกัดของจุดยอดที่ฟังก์ชันเป้าหมายมีค่าสูงสุด

แบ่งออกเป็นสองขั้นตอนหลัก ในระยะแรก พบว่ามีวิธีแก้ปัญหาอย่างหนึ่งที่สอดคล้องกับระบบข้อจำกัด. ระบบที่มีตัวแปรมากกว่าข้อจำกัด N > m เรียกว่าความไม่แน่นอน พวกมันจะลดลงเหลือเพียงระบบบางระบบ (N = m) โดยให้ตัวแปร N-m เท่ากับศูนย์ ซึ่งจะทำให้ระบบสมการ m มีค่าไม่ทราบค่า m ซึ่งมีคำตอบหากดีเทอร์มิแนนต์ของระบบแตกต่างจากศูนย์ วิธีซิมเพล็กซ์แนะนำแนวคิดของตัวแปรพื้นฐานหรือพื้นฐาน พื้นฐานคือชุดของตัวแปร m ใดๆ โดยดีเทอร์มิแนนต์ที่ประกอบด้วยสัมประสิทธิ์ของตัวแปรเหล่านี้ในข้อจำกัด m ไม่ใช่ศูนย์ ตัวแปร N-m ที่เหลือเรียกว่าตัวแปรที่ไม่ใช่พื้นฐานหรือตัวแปรอิสระ ถ้าเราถือว่าตัวแปรที่ไม่ใช่พื้นฐานทั้งหมดมีค่าเท่ากับศูนย์และแก้ระบบข้อจำกัดเกี่ยวกับตัวแปรพื้นฐาน เราจะได้คำตอบพื้นฐาน

ในระบบสมการ m ที่ไม่ทราบค่า N จำนวนคำตอบพื้นฐานทั้งหมดสำหรับ N > m จะถูกกำหนดโดยจำนวนชุดค่าผสม

คำตอบพื้นฐานที่เรียก x i 0, i = 1,m ทั้งหมด วิธีแก้ปัญหาพื้นฐานที่ยอมรับได้ดังนั้นขั้นตอนแรกของการแก้ปัญหาโดยใช้วิธีซิมเพล็กซ์จึงจบลงด้วยการค้นหาวิธีแก้ปัญหาพื้นฐานที่ยอมรับได้แม้ว่าจะไม่ประสบผลสำเร็จก็ตาม

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

1) ตัวแปรพื้นฐานและฟังก์ชันเป้าหมายแสดงผ่านตัวแปรที่ไม่ใช่พื้นฐาน

2) ตามกฎบางข้อจะมีการเลือกตัวแปรที่ไม่ใช่พื้นฐานตัวใดตัวหนึ่งซึ่งการเปลี่ยนค่าที่สามารถปรับปรุงค่าของ F(x) และจะถูกนำเข้าสู่พื้นฐาน

3) กำหนดว่าตัวแปรพื้นฐานใดควรได้รับมาจากพื้นฐาน ในขณะที่ตัวแปรพื้นฐานชุดใหม่ที่เกิดขึ้นในแต่ละขั้นตอนแตกต่างจากตัวแปรก่อนหน้าในตัวแปรเดียวเท่านั้น

4) ตัวแปรพื้นฐานและฟังก์ชันเป้าหมายจะแสดงผ่านตัวแปรที่ไม่ใช่พื้นฐานใหม่และการดำเนินการ 2) และ 3) จะถูกทำซ้ำ

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

ลองพิจารณาตัวอย่างที่เกี่ยวข้องกับงานการจัดการองค์กรและเศรษฐกิจและการช่วยให้เข้าใจเนื้อหาของวิธีซิมเพล็กซ์

ตัวอย่างที่ 1 จัดสรรเงิน 20,000 ปีเพื่อซื้ออุปกรณ์สำหรับไซต์ใหม่ ต้องวางอุปกรณ์บนพื้นที่ไม่เกิน 72 ตร.ม. สามารถสั่งซื้ออุปกรณ์ได้สองประเภท: 1) อุปกรณ์ราคา 5,000 ปี ครอบครองพื้นที่ 6 ตารางเมตร และผลิตได้ 8,000 หน่วย สินค้าต่อกะ; 2) อุปกรณ์มูลค่า 2 พัน y.e. ครอบครองพื้นที่ 12 m2 และผลิตได้ 4 พันหน่วยต่อกะ สินค้า. ค้นหาตัวเลือกที่เหมาะสมที่สุดสำหรับการซื้ออุปกรณ์ที่รับรองประสิทธิภาพการผลิตโดยรวมของไซต์งานสูงสุดโดยใช้วิธีแบบซิมเพล็กซ์

ให้เราแสดงจำนวนอุปกรณ์ที่ไม่ทราบประเภทที่หนึ่งและที่สองตามลำดับ x 1 และ x 2 ฟังก์ชันวัตถุประสงค์สามารถเขียนได้ดังนี้: F(x) = 8x 1 + 4x 2 (สูงสุด) ข้อจำกัดพื้นที่: 6x 1 +12x 2 ≤72; ข้อจำกัดด้านต้นทุน: 5x 1 + 2x 2 ≤20 ; ข้อจำกัดเกี่ยวกับเครื่องหมายของตัวแปร x 1 ≥0 ; x 2 ≥0

ลองหารค่าสัมประสิทธิ์ของข้อ จำกัด แรกด้วย 6 และลดข้อ จำกัด เป็นรูปแบบความเท่าเทียมกันโดยแนะนำตัวแปรเพิ่มเติม x 3 และ x 4:

x 1 + 2x 2 + x 3 =12, (1)

5x 1 + 2x 2 + x 4 = 20 (2)

ดังนั้น ข้อจำกัดของปัญหาสำหรับ จะลดลงเหลือเพียงระบบสมการพีชคณิตสองตัวที่ไม่ทราบค่าสี่ตัว ขั้นตอนการแก้ปัญหามีดังนี้:

ขั้นตอนที่ 1 ในการแก้ปัญหาโดยใช้วิธีซิมเพล็กซ์ เราเลือก x 2 และ x 4 เป็นตัวแปรพื้นฐาน (BP) เนื่องจากดีเทอร์มิแนนต์ที่ประกอบด้วยค่าสัมประสิทธิ์ของตัวแปรเหล่านี้ในข้อจำกัดของปัญหาแตกต่างจากศูนย์

จากนั้น x 1 และ x 3 จะเป็นตัวแปรที่ไม่ใช่พื้นฐาน (NP) ให้เราแสดงตัวแปรพื้นฐานและ F(x) ในรูปของตัวแปรที่ไม่ใช่พื้นฐาน

(3)

จากข้อจำกัดที่สองเป็นไปตามนั้น

x 4 = 20 - 2x 2 - 5x 1 (4)

โดยคำนึงถึงการแสดงออกข้างต้นที่เราได้รับ

x 4 = 8 - 4x 1 + x 3 (5)

แล้ว

F(x) = 8x 1 + 4x 2 = 24 + 6x 1 - 2x 3 (6)

ในแต่ละขั้นตอน NP จะเท่ากับศูนย์ ดังนั้น BP และ F(x) จะเท่ากับพจน์อิสระในนิพจน์ที่เกี่ยวข้อง:

x 1 = 0, x 3 = 0, x 2 = 6, x 4 = 8, ฉ(x) = 24

วิธีนี้สอดคล้องกับพิกัดของจุดยอด A ของ ODZP ในรูปที่ 1 1. ตรวจสอบความเหมาะสมของโซลูชันโดยใช้นิพจน์ F(x) สำหรับฟังก์ชันเป้าหมาย ตัวแปร x 3 เข้าสู่นิพจน์นี้โดยมีค่าสัมประสิทธิ์ลบ หากคุณป้อน x 3 ลงในฐานในขั้นตอนถัดไปก็จะได้ค่าบวกและค่าหนึ่งจะถูกลบออกจากตัวเลข 24 เช่น ค่าของ F(x) จะลดลง หากคุณป้อน x 1 ลงในฐานในขั้นตอนถัดไป ค่าของฟังก์ชันเป้าหมายจะเพิ่มขึ้น เช่น จะปรับปรุง.

เมื่อใช้วิธีซิมเพล็กซ์ ตัวแปรที่จะไปที่ศูนย์ก่อนเมื่อใส่ลงในฐาน x 1 จะถูกแยกออกจากฐาน จากการวิเคราะห์ (3) และ (5) เราพิจารณาว่าควรแยก x 4 ออกจากฐาน ในขั้นตอนถัดไป ตัวแปร x 1 และ x 4 จะถูกสลับ

ขั้นตอนที่ 2 ของวิธีซิมเพล็กซ์ x 1 และ x 2 เป็นตัวแปรพื้นฐาน x 3 และ x 4 ไม่ใช่ตัวแปรพื้นฐาน ให้เราแสดงตัวแปรพื้นฐานและ F(x) ในรูปของตัวแปรที่ไม่ใช่พื้นฐาน จาก (5) ดังต่อไปนี้

x 1 =2+(1/4)x 3 -(1/4)x 4 (7)

ข้าว. 1. การตีความภาพตัวอย่างที่ 1 โดยใช้วิธีซิมเพล็กซ์

เมื่อแทน (7) ลงใน (3) เราจะได้

x 2 =5-(5/8)x 3 +(1/8)x 4

จากนั้น F(x) = 8x 1 + 4x 2 = 36 - (1/2)x 3 -(3/4)x 4 ผลลัพธ์ก็คือ x 3 = x 4 = 0 (แบบไม่มีพื้นฐาน), x 1 = 2, x 2 = 5, F = 36 วิธีนี้สอดคล้องกับพิกัดของจุดยอด B ในรูปที่ 1 1. ค่าที่พบจะเหมาะสมที่สุด ไม่สามารถปรับปรุงค่า F(x) ได้เนื่องจากตัวแปร x 3 และ x 4 รวมอยู่ในนิพจน์สำหรับฟังก์ชันเป้าหมายที่มีค่าสัมประสิทธิ์ลบ

ดังนั้นเราจึงพบว่าผลผลิตสูงสุดของไซต์คือ 36,000 หน่วยโดยใช้วิธีซิมเพล็กซ์ สินค้าต่อกะจะได้รับเมื่อซื้อ 2 หน่วย อุปกรณ์ประเภทที่ 1 จำนวน 5 เครื่อง อุปกรณ์ประเภทที่สอง ตัวแปรเพิ่มเติม x 3 และ x 4 มีความหมายถึงทรัพยากรที่ไม่ได้ใช้ ในตัวอย่างนี้ ทรัพยากรทั้งหมดในแง่ของพื้นที่และต้นทุนถูกใช้จนหมด (x 3 = x 4 = 0)