อัลกอริทึมวิธีการ Simplex วิธีการแก้ปัญหา Simplex ZLP งานการเขียนโปรแกรมเชิงเส้นมาตรฐานตามเงื่อนไข

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

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

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

ตารางที่ 1.

ตัวแปรพื้นฐาน	สมาชิกฟรีในข้อ จำกัด	ตัวแปร Nebase
ตัวแปรพื้นฐาน	สมาชิกฟรีในข้อ จำกัด	x 1	x 2	...	x ลิตร	...	x N
x n + 1	b 1.	11.	12.	...	1L	...	1n
x n + 2	b 2.	21.	22	...	2L	...	2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n + r	b2	r1	r2	...	rl	...	rn
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n + m	b M.	m1	m2	...	ml	...	mn
f (x) สูงสุด	f 0	-c 1.	-c 2.	...	-c 1.	...	-c n

ขั้นตอนที่สาม ในขั้นตอนที่สามเราแปลตาราง Simplex ทั้งหมดในสูตรพิเศษสูตรเหล่านี้สามารถมองเห็นได้โดยใช้

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

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

ที่นี่คู่มือ (ไม่ใช่แอปเพล็ต) จะได้รับการแก้ปัญหาของสองงานด้วยวิธีการ Simplex (โซลูชันแอปเพล็ตที่คล้ายกัน) พร้อมคำอธิบายโดยละเอียดเพื่อให้เข้าใจวิธีการแก้ปัญหาวิธีการแก้ปัญหา Simplex-Method งานแรกที่มีสัญญาณความไม่เท่าเทียมนี้ "≤" (งานที่มีพื้นฐานเริ่มต้น) ที่สองอาจมีสัญญาณ "≥", "≤" หรือ "\u003d" (งานที่มีพื้นฐานเทียม) พวกเขาจะได้รับการแก้ไขในรูปแบบที่แตกต่างกัน

Simplex-Method แก้ปัญหาด้วยพื้นฐานเริ่มต้น

1)วิธี Simplexสำหรับงานที่มีพื้นฐานเริ่มต้น (สัญญาณทั้งหมดของความไม่เท่าเทียมกัน - ข้อ จำกัด "≤")

เราเขียนงาน B ตามบัญญัติ แบบฟอร์ม I.E ข้อ จำกัด ของความไม่เท่าเทียมจะเขียนใหม่ในรูปแบบของความเท่าเทียมกันโดยการเพิ่ม สมดุล ตัวแปร:

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

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

การทำซ้ำแบบง่าย ๆ 0

							ทัศนคติ

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

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

อนุญาตให้องค์ประกอบ มันอยู่ในจุดตัดของคอลัมน์ความละเอียดและความละเอียดเซลล์ของมันแยกต่างหากเป็น 1. ดังนั้นในการวนซ้ำครั้งต่อไปของวิธีการ Simplex ตัวแปร X 2 จะถูกแทนที่ในฐาน S 1 โปรดทราบว่าใน z-row ทัศนคติไม่ได้ค้นหามีเส้นประ "-" ในกรณีที่มีอัตราส่วนขั้นต่ำเช่นเดียวกับที่เลือกใด ๆ หากค่าสัมประสิทธิ์ทั้งหมดน้อยกว่าหรือเท่ากับคอลัมน์ความละเอียดการแก้ปัญหานั้นไม่มีที่สิ้นสุด

กรอกข้อมูลในตารางต่อไปนี้ "การทำซ้ำ 1" เราจะได้รับจากตาราง "ทำซ้ำ 0" จุดประสงค์ของการเปลี่ยนแปลงเพิ่มเติมคือการแปลงคอลัมน์ความละเอียด x 2 เป็นหนึ่ง (มีหน่วยแทนองค์ประกอบความละเอียดและศูนย์แทนที่จะเป็นองค์ประกอบอื่น ๆ )

1) การคำนวณสตริง x 2 ตาราง "การทำซ้ำ 1" ครั้งแรกเราแบ่งสมาชิกทั้งหมดของความละเอียด S 3 ตาราง "การทำซ้ำ 0" ไปยังองค์ประกอบความละเอียด (เป็น 1 ในกรณีนี้) ของตารางนี้เราได้รับสตริง x 2 ในตาราง "การวนซ้ำ 1" เพราะ องค์ประกอบการแก้ไขในกรณีนี้คือ 1 จากนั้นบรรทัด S 3 ของตาราง "การวนซ้ำ 0" จะตรงกับบรรทัด x 2 ของตาราง "การวนซ้ำ 1" บรรทัด x 2 ตาราง "การทำซ้ำ 1" เราได้รับ 0 1 0 0 1 20 แถวที่เหลืออยู่ของตาราง "การทำซ้ำ 1" จะได้รับจากบรรทัดนี้และสตริงของตาราง "การวนซ้ำ 0" ดังต่อไปนี้:

2) การคำนวณตาราง z-row "การทำซ้ำ 1" ในสถานที่ -6 ในบรรทัดแรก (z-roun) ในคอลัมน์ x 2 ของตาราง "การวนซ้ำ 0" ต้องเป็น 0 ในบรรทัดแรกของตาราง "การวนซ้ำ 1" ในการทำเช่นนี้องค์ประกอบทั้งหมดของสตริง x 2 ตาราง "การวนซ้ำ 1" 0 1 0 0 1 20 คูณด้วย 6 เราได้รับ 0 0 0 0 6 120 และวางสตริงนี้ด้วยตารางบรรทัดแรก (z - บรรทัด) ตาราง " 0 "-4 -6 0 0 0 0, เราได้รับ -4 0 0 0 6 120. ในคอลัมน์ x 2 ศูนย์ 0 ปรากฏเป้าหมายบรรลุเป้าหมาย องค์ประกอบของคอลัมน์ความละเอียด x 2 ถูกเน้นด้วยสีแดง

3) การคำนวณของสตริง S 1 ตาราง "การทำซ้ำ 1" ในสถานที่ 1 ใน 1 บรรทัดของตาราง "การวนซ้ำ 0" จะต้องเป็น 0 ในตาราง "การวนซ้ำ 1" สำหรับสิ่งนี้องค์ประกอบทั้งหมดของสตริง x 2 ตาราง "การวนซ้ำ 1" 0 1 0 0 1 20 คูณบน -1 เราได้รับ 0 -1 0 -1 -1 -20 และวางสตริงนี้ด้วย S 1 - บรรทัดของตาราง "การวนซ้ำ 0" 2 1 1 0 0 64 เราได้รับสตริง 2 0 1 0 -1 44. ในคอลัมน์ x 2 ที่ได้รับ 0 จะได้รับ

4) การคำนวณของสตริง S 2 ตาราง "การทำซ้ำ 1" ในตำแหน่ง 3 ในแถว S 2 ของตาราง "การวนซ้ำ 0" ควรเป็น 0 ในตาราง "ทำซ้ำ 1" ในการทำเช่นนี้องค์ประกอบทั้งหมดของสตริง x 2 ตาราง "การวนซ้ำ 1" 0 1 0 0 1 20 คูณโดย -3 เราได้รับ 0 -3 0 0 -3 -60 และวางสตริงนี้ด้วย S 1 - บรรทัดของตาราง "การวนซ้ำ 0" 1 3 0 1 0 72 เราได้รับสาย 1 0 0 1 -3 12. ในคอลัมน์ x 2 ที่ต้องการ 0 จะได้รับคอลัมน์ x 2 ในตาราง "การทำซ้ำ 1" กลายเป็นโสด มันมีหนึ่ง 1 และที่เหลือ 0

แถวของตาราง "การวนซ้ำ 1" จะได้รับตามกฎต่อไปนี้:

บรรทัดใหม่ \u003d สตริงเก่า - (ค่าสัมประสิทธิ์ของคอลัมน์ที่อนุญาตของบรรทัดเก่า) * (สตริงที่อนุญาตใหม่)

ตัวอย่างเช่นสำหรับ z-row เรามี:

z-row z-row (-4 -6 0 0 0 0) - (- 6) * ใหม่ที่อนุญาตสตริง - (0 -6 0 0 -6 -120) \u003d ใหม่ z-line (-4 0 0 0 6 120)

สำหรับตารางต่อไปนี้การคำนวณองค์ประกอบของตารางจะเกิดขึ้นในทำนองเดียวกันดังนั้นเราจึงละเว้น

การทำซ้ำวิธีการง่ายๆ 1

							ทัศนคติ

คอลัมน์ความละเอียด x 1 การแก้ไขสตริง S 2, S 2 ออกจากฐาน X 1 เข้าสู่พื้นฐาน คล้ายกับตาราง Simplex อื่น ๆ จนกระทั่งตารางที่ได้รับกับค่าสัมประสิทธิ์บวกทั้งหมดใน Z-ROW นี่เป็นสัญญาณของตารางที่เหมาะสมที่สุด

simplex- วิธีการทำซ้ำ 2

							ทัศนคติ

คอลัมน์ความละเอียด S 3 การแก้ไขสตริง S 1, S 1 ออกจากฐาน S 3 เข้าสู่พื้นฐาน

การทำซ้ำแบบง่าย ๆ 3

							ทัศนคติ

ใน z-row ค่าสัมประสิทธิ์ทั้งหมดไม่เป็นลบดังนั้นโซลูชันที่ดีที่สุด x 1 \u003d 24, x 2 \u003d 16, z max \u003d 192 ได้รับ

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

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

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

ที่ไหน x \u003d (x 1 , X. 2 ... , x น. ) ; ว. - พื้นที่ของค่าที่อนุญาตของตัวแปร เอ็กซ์ 1 , X. 2 ... , x น. ;f (x) - คุณสมบัติเป้าหมาย

เพื่อที่จะแก้ปัญหาการเพิ่มประสิทธิภาพก็เพียงพอที่จะหาทางออกที่ดีที่สุด I.e. ระบุเช่นนั้น ด้วยใด ๆ

ภารกิจการเพิ่มประสิทธิภาพนั้นยากถ้าไม่มีทางออกที่ดีที่สุด โดยเฉพาะอย่างยิ่งงานการสูงสุดจะต้องดื้อรั้นหากฟังก์ชั่นเป้าหมาย f (x) ไม่ จำกัด อยู่ด้านบนบนชุดที่อนุญาต ว..

วิธีการในการแก้ปัญหาการปรับให้เหมาะสมขึ้นอยู่กับประเภทของฟังก์ชั่นเป้าหมาย f (x)และจากโครงสร้างของชุดที่อนุญาต ว.. หากฟังก์ชั่นเป้าหมายในงานเป็นฟังก์ชั่น น. ตัวแปรจากนั้นวิธีการแก้ปัญหาเรียกว่าวิธีการเขียนโปรแกรมทางคณิตศาสตร์

คุณสมบัติลักษณะของงานการเขียนโปรแกรมเชิงเส้นมีดังนี้:

ตัวบ่งชี้การมองเห็น f (x) แสดงถึงฟังก์ชั่นเชิงเส้นจากองค์ประกอบของโซลูชัน x \u003d (x 1 , X. 2 ... , x น. ) ;

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

ภารกิจการเขียนโปรแกรมเชิงเส้น งานของการศึกษาการดำเนินการแบบจำลองทางคณิตศาสตร์ที่มีรูปแบบของ:

(2) (3) (4) (5)

ในกรณีนี้ระบบของสมการเชิงเส้น (3) และความไม่เท่าเทียม (4), (5) ซึ่งกำหนดชุดโซลูชันที่อนุญาตของปัญหา ว.เรียกว่า ข้อ จำกัด ของระบบ งานการเขียนโปรแกรมเชิงเส้นและฟังก์ชั่นเชิงเส้น f (x) เรียกว่า ฟังก์ชั่นเป้าหมาย หรือ เกณฑ์การมองโลก .

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

หากแบบจำลองทางคณิตศาสตร์ของปัญหาการเขียนโปรแกรมเชิงเส้นคือ:

พวกเขาบอกว่างานถูกนำเสนอใน รูปแบบบัญญัติ .

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

กฎของภารกิจการเขียนโปรแกรมเชิงเส้นสำหรับลักษณะที่ปรากฏเป็นดังนี้:

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

หากอยู่ในข้อ จำกัด ส่วนที่ถูกต้องเป็นลบดังนั้นจึงจะเพิ่มขีด จำกัด นี้ใน -1;

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

หากตัวแปรบางอย่าง เอ็กซ์ เจ. ไม่มีข้อ จำกัด ในการลงชื่อมันจะถูกแทนที่ (ในฟังก์ชั่นเป้าหมายและในข้อ จำกัด ทั้งหมด) ความแตกต่างระหว่างตัวแปรที่ไม่ใช่ลบใหม่สองตัว: เอ็กซ์ 3 \u003d X. 3 + - X. 3 - ที่ไหน เอ็กซ์ 3 + , X. 3 - ≥ 0 .

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

ขั้นต่ำ l \u003d 2x 1 + x. 2 - X. 3 ; 2x 2 - X. 3 ≤ 5; เอ็กซ์ 1 + x. 2 - X. 3 ≥ -1; 2x 1 - X. 2 ≤ -3; เอ็กซ์ 1 ≤ 0; เอ็กซ์ 2 ≥ 0; เอ็กซ์ 3 ≥ 0.

เราแนะนำในแต่ละสมการของระบบของข้อ จำกัด การปรับระดับตัวแปร เอ็กซ์ 4 , X. 5 , X. 6 . ระบบจะถูกบันทึกในรูปแบบของความเท่าเทียมกันและในสมการแรกและสามของระบบขีด จำกัด ของตัวแปร เอ็กซ์ 4 , X. 6 แนะนำให้รู้จักกับส่วนซ้ายด้วยเครื่องหมาย "+" และในสมการสมการที่สอง เอ็กซ์ 5 ป้อนด้วยเครื่องหมาย "-"

2x 2 - X. 3 + x. 4 \u003d 5; เอ็กซ์ 1 + x. 2 - X. 3 - X. 5 \u003d -1; 2x 1 - X. 2 + x. 6 \u003d -3; เอ็กซ์ 4 ≥ 0; เอ็กซ์ 5 ≥ 0; เอ็กซ์ 6 ≥ 0.

สมาชิกฟรีในรูปแบบบัญญัติควรเป็นบวกสำหรับสิ่งนี้สมการสองตัวสุดท้ายจะทวีคูณใน -1:

2x 2 - X. 3 + x. 4 \u003d 5; -x 1 - X. 2 + x. 3 + x. 5 \u003d 1; -2X 1 + x. 2 - X. 6 = 3.

วิธีการ Simplex ในการแก้ปัญหาการเขียนโปรแกรมเชิงเส้น

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

กฎสองข้อสำหรับการเลือกที่ป้อนและไม่รวมตัวแปรในวิธีการง่ายๆที่เราเรียกว่า สภาพของการมองโลก และ เงื่อนไขการอนุญาต . เรากำหนดกฎเหล่านี้รวมถึงพิจารณาลำดับของการกระทำที่ดำเนินการเมื่อใช้วิธีการ Simplex

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

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

ให้เราให้อัลกอริทึมในการแก้ปัญหาการเขียนโปรแกรมเชิงเส้นเพื่อค้นหาสูงสุดโดยใช้ตาราง Simplex Simplex

f \u003d c 1 x 1 + c 2 x 2 + ... + กับ n x n 

x 1 0, x 2 0, ... , x n 0

ขั้นตอนที่ 1. เราแนะนำตัวแปรเพิ่มเติมและเขียนระบบสมการที่เกิดขึ้นและฟังก์ชั่นเชิงเส้นเป็นระบบขยาย

F-C 1 x 1 -c 2 x 2 - ... -c n x n \u003d 0 \u003d c p

ขั้นตอนที่ 2 เรารวบรวมตาราง Simplex เริ่มต้น

ตัวแปร	ตัวแปรพื้นฐานและสารเติมแต่ง	สมาชิกฟรี (การตัดสินใจ)	ที่ประมาณ ทัศนคติ
ตัวแปร		สมาชิกฟรี (การตัดสินใจ)	ที่ประมาณ ทัศนคติ

ขั้นตอนที่ 3 เราตรวจสอบประสิทธิภาพของเกณฑ์การมองเห็น - การปรากฏตัวในแถวสุดท้ายของสัมประสิทธิ์เชิงลบ หากไม่มีเช่นนี้โซลูชันนั้นดีที่สุดและ f * \u003d co ตัวแปรพื้นฐานเท่ากับค่าสัมประสิทธิ์ที่สอดคล้องกัน B J ตัวแปรที่ไม่มี Neur นั้นเป็นศูนย์นั่นคือ X * \u003d (B 1, B 2, ... , BM, 0, ... , 0)

ขั้นตอนที่ 4. หากไม่ปฏิบัติตามเกณฑ์ในแง่ดีค่าสัมประสิทธิ์เชิงลบสูงสุดในสตริงสุดท้าย (โดยประมาณ) จะถูกกำหนดโดยคอลัมน์ที่อนุญาต

เพื่อกำหนดสตริงความละเอียดคำนวณความสัมพันธ์โดยประมาณ และเติมคอลัมน์สุดท้ายของตาราง

อัตราส่วนโดยประมาณของแถว i-th เท่ากัน

ถ้า B I และ A มีสัญญาณที่แตกต่างกัน

ถ้า B I \u003d 0 และ A คือ<0;

ถ้า A คือ \u003d 0;

0, ถ้า b i \u003d 0 และ a คือ\u003e 0;

ในคอลัมน์ความสัมพันธ์การประเมินเราพบองค์ประกอบขั้นต่ำขั้นต่ำ ซึ่งกำหนดความละเอียดของสตริง G

หากไม่มีขั้นต่ำงานจะไม่มีขั้นสุดท้ายที่เหมาะสมที่สุดและเป็นเรื่องยาก

ที่จุดตัดของแถวและคอลัมน์ความละเอียดคือการอนุญาตให้ใช้องค์ประกอบ GS

ขั้นตอนที่ 5. สร้างตารางต่อไปนี้ สำหรับสิ่งนี้

ไปที่ขั้นตอนที่สาม

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

วิธีการแก้ปัญหาสากลของ LP เรียกว่าวิธี Simplex การใช้วิธีนี้และการปรับเปลี่ยนที่พบบ่อยที่สุดคือวิธี Simplex สองเฟส

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

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

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

พิจารณาวิธีการง่ายๆในตัวอย่างเฉพาะของภารกิจในการวาดแผน

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

พิจารณาภารกิจของแผนการผลิตการสร้างแบบจำลองล่วงหน้าและนำไปสู่รูปแบบพิเศษ

งาน.

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

เราจะสร้างแบบจำลองทางคณิตศาสตร์แสดงให้เห็นถึง เอช. 1 จำนวนผลิตภัณฑ์และในแง่ของ เอช. 2 - จำนวนผลิตภัณฑ์ ใน. จากนั้นระบบ จำกัด จะมีลักษณะเช่นนี้:

x 1 ≤50
x 2 ≤40
2x1 + x 2 ≤80
x 1 ≥0, x 2 ≥0
5x1 + 3x 2 →สูงสุด

เราให้งานกับแบบฟอร์ม Canonical โดยป้อนตัวแปรเพิ่มเติม:

x 1 + x 3 \u003d 50
x 2 + x 4 \u003d 40
2x 1 + x 2 + x 5 \u003d 80
x 1 ≥0, x 2 ≥0
5x1 + 3x 2 →สูงสุด
-f \u003d -5X 1 - 3x 2 →นาที

ภารกิจนี้มีลักษณะพิเศษ (มีพื้นฐานชิ้นส่วนที่เหมาะสมไม่เป็นลบ) มันสามารถแก้ไขได้โดยวิธี Simplex

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

ตารางที่ 3.4

เกณฑ์			ฟรี

ครั้งที่สอง เวที. ตรวจสอบแผนการสนับสนุนสำหรับการเพิ่มขึ้น

ตารางนี้ 3.4 สอดคล้องกับแผนการอ้างอิงต่อไปนี้:

(เอช. 1 , เอช. 2 , เอช. 3 , เอช. 4 , เอช. 5) = (0, 0, 50, 40, 80).

ตัวแปรฟรี เอช. 1 , เอช. 2 เท่ากับ 0; เอช. 1 = 0, เอช. 2 \u003d 0 และตัวแปรพื้นฐาน เอช. 3 , เอช. 4 , เอช. 5 ค่าใช้จ่าย เอช. 3 = 50, เอช. 4 = 40, เอช. 5 \u003d 80 - จากคอลัมน์ของสมาชิกฟรี ค่าของฟังก์ชั่นเป้าหมาย:

-F. = - 5เอช. 1 - 3เอช. 2 \u003d -5 · 0 - 3 · 0 \u003d 0

งานของเราคือการตรวจสอบว่าแผนอ้างอิงนี้ดีที่สุดหรือไม่ เมื่อต้องการทำเช่นนี้ดูสตริงดัชนี - แถวของฟังก์ชั่นเป้าหมาย F..

สถานการณ์ต่าง ๆ เป็นไปได้

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

2. ในบรรทัดดัชนีมีองค์ประกอบเชิงลบอย่างน้อยหนึ่งองค์ประกอบที่ไม่มีคอลัมน์เชิงบวก จากนั้นเราสรุปได้ว่าฟังก์ชั่นเป้าหมาย F.→∞ลดลงไม่ จำกัด

3. ในบรรทัดดัชนีมีองค์ประกอบเชิงลบในคอลัมน์ที่มีอย่างน้อยหนึ่งบวก จากนั้นไปที่ขั้นตอนต่อไป III ระลึกถึงตารางโดยปรับปรุงแผนอ้างอิง

สาม เวที. ปรับปรุงแผนการอ้างอิง

จากดัชนีองค์ประกอบเชิงลบ F.- ลองเลือกโมดูลที่ใหญ่ที่สุดโดยโมดูลให้เราเรียกคอลัมน์ที่สอดคล้องกับการอนุญาตและสังเกต ""

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

ในตัวอย่างของเราองค์ประกอบที่ 2 อนุญาต สตริงที่สอดคล้องกับองค์ประกอบนี้เรียกอีกอย่างว่าความละเอียด (ตารางที่ 3.5)

ตารางที่ 3.5

โดยการเลือกรายการที่อนุญาตเราทำรายการตารางตามกฎ:

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

ตารางที่ 3.6

2. แทนที่องค์ประกอบความละเอียด 2 เขียนหมายเลขตรงกันข้าม½

3. องค์ประกอบของสตริงที่อนุญาตจะแบ่งออกเป็นองค์ประกอบที่อนุญาต

4. องค์ประกอบของคอลัมน์ความละเอียดแบ่งเป็นรายการที่อนุญาตและเขียนด้วยเครื่องหมายตรงข้าม

5. เติมองค์ประกอบที่เหลือของตารางที่ 3.6 เราจะคำนวณใหม่ตามกฎสี่เหลี่ยมผืนผ้า ให้เราต้องการคำนวณองค์ประกอบที่ยืนอยู่ในที่ 50

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

ดังนั้น. เราเขียน 10 ไปยังสถานที่ที่มี 50 ในทำนองเดียวกัน:
, , , .

ตารางที่ 3.7

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

เราจะแก้ปัญหาในตอนท้าย เมื่อต้องการทำเช่นนี้ให้ตรวจสอบสตริงดัชนีและการดูองค์ประกอบเชิงลบ -1 ในนั้นเราเรียกคอลัมน์ที่เหมาะสมกับมันอนุญาตและตามขั้นตอนที่ III คำนวณตารางใหม่ โดยการวาดความสัมพันธ์และการเลือกขั้นต่ำ \u003d 40 ในหมู่พวกเขากำหนดองค์ประกอบที่อนุญาต 1. ตอนนี้คำนวณใหม่เราดำเนินการตามกฎ 2-5

ตารางที่ 3.8

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

ivเวที. การกำจัดโซลูชันที่ดีที่สุด

หากวิธีการ Simplex หยุดตามขั้นตอนที่ 1 ขั้นตอนที่ 1 จากนั้นวิธีการแก้ปัญหาจะถูกเขียนดังนี้ ตัวแปรพื้นฐานใช้ค่าของคอลัมน์ของสมาชิกฟรีตามลำดับ ในตัวอย่างของเรา เอช. 3 = 30, เอช. 2 = 40, เอช. 1 \u003d 20. ตัวแปรฟรีคือ 0, เอช. 5 = 0, เอช. 4 \u003d 0. ฟังก์ชั่นเป้าหมายใช้ค่าขององค์ประกอบสุดท้ายของคอลัมน์ของสมาชิกฟรีที่มีเครื่องหมายตรงข้าม: - F. = -220 → F.\u003d 220 ในตัวอย่างของเราฟังก์ชั่นถูกศึกษาในขั้นต่ำและในขั้นต้น F. →สูงสุดดังนั้นในความเป็นจริงเครื่องหมายมีการเปลี่ยนแปลงสองครั้ง ดังนั้น, เอช.* = (20, 40, 30, 0, 0), F.* \u003d 220. การตอบสนองต่องาน:

จำเป็นต้องมีผลิตภัณฑ์ประเภท 20 ประเภท แต่40 ผลิตภัณฑ์ชนิด B และกำไรจะสูงสุดและจะเท่ากับ 220 รูเบิล

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

อ้างอิงด้านบนสี่เหลี่ยมในผังงานแสดงให้เห็นว่ากลุ่มการแปลงที่เกี่ยวข้องเกี่ยวข้องกับเวทีหรือประโยคย่อย กฎการค้นหาแผนอ้างอิงเริ่มต้นจะถูกกำหนดในวรรค 3.7

ตัวอย่าง. แก้ไขภารกิจของ LP ต่อไปนี้ในวิธีการ Canonical Form Simplex
f (x) \u003d x 1 + 9x 2 + 5x3 + 3x 4 + 4x5 + 14x6 →นาที
x 1 + x 4 \u003d 20
x 2 + x 5 \u003d 50
x 3 + x 6 \u003d 30
x 4 + x 5 + x 6 \u003d 60
x i ≥ 0, i \u003d 1, ... , 6
ว่ากันว่าภารกิจของ LP มีรูปแบบบัญญัติหากข้อ จำกัด ทั้งหมด (ยกเว้นตัวแปรที่ไม่ลบล้าง) มีรูปแบบของความเท่าเทียมกันและสมาชิกฟรีทั้งหมดไม่เป็นลบ ดังนั้นเราจึงมีงานในรูปแบบบัญญัติ
แนวคิดของวิธีการ Simplex มีดังนี้ ก่อนอื่นคุณต้องหาจุดสุดยอด (เริ่มต้น) ของโซลูชั่นที่อนุญาต polyhedron (โซลูชันพื้นฐานที่อนุญาต) จากนั้นคุณต้องตรวจสอบโซลูชันนี้เพื่อเพิ่มความเหมาะสม หากเหมาะสมกว่านั้นพบวิธีแก้ปัญหา ถ้าไม่เช่นนั้นไปที่ด้านบนของ polyhedron อื่น ๆ และตรวจสอบอีกครั้งเพื่อเพิ่มความเหมาะสม เนื่องจากแขนขาของจุดยอดของ polyhedron (ผลของแขนขาของข้อ จำกัด ของงานของ LP) สำหรับจำนวนสุดท้ายของ "ขั้นตอน" เราจะพบจุดที่ต้องการของขั้นต่ำหรือสูงสุด ควรสังเกตว่าเมื่อย้ายจากจุดยอดหนึ่งไปยังอีกจุดหนึ่งค่าของฟังก์ชั่นเป้าหมายจะลดลง (ในปัญหาขั้นต่ำ) หรือเพิ่มขึ้น (ในงานสูงสุด)
ดังนั้นความคิดของวิธีการ Simplex จึงขึ้นอยู่กับคุณสมบัติสามของงาน LP
การตัดสินใจ เพื่อค้นหาโซลูชันพื้นฐานที่อนุญาตเริ่มต้น I.e. ในการกำหนดตัวแปรพื้นฐานระบบ (5.6) จะต้องนำไปสู่ความคิด "เส้นทแยงมุม" การใช้วิธี Gauss (วิธีการยกเว้นที่ไม่รู้จักที่สอดคล้องกัน) เราได้รับจาก (5.6):
x 2 + x 1 + x 3 \u003d 40
x 4 + x 1 \u003d 20
x 5 -x 1 -x 3 \u003d 10
x 6 + x 3 \u003d 30
ดังนั้นพื้นฐานคือตัวแปร x 2, x 4, x 5, x 6,พวกเขาแนบค่าเท่ากับสมาชิกฟรีของบรรทัดที่เกี่ยวข้อง: x 2 \u003d 40, x 4 \u003d 20, x 5 \u003d 10, x 6 \u003d 30,. ตัวแปร x 1 และ x 3 เป็น unbasic: x 1 \u003d 0, x 3 \u003d 0.
สร้างโซลูชันพื้นฐานที่อนุญาตเริ่มต้น
x 0 \u003d (0.40,0,20,10,30) (5.9)
เพื่อตรวจสอบการมองเห็นการแก้ปัญหาที่พบ x 0 มีความจำเป็นต้องยกเว้นตัวแปรพื้นฐานจากฟังก์ชั่นเป้าหมาย (ใช้ระบบ (5.8)) และสร้างตาราง Simplex พิเศษ
หลังจากไม่รวมตัวแปรคุณสมบัติเป้าหมายนั้นสะดวกในการเขียนในแบบฟอร์ม:
f (x) \u003d -7x 1 - 14x 3 +880 (5.10)
ขณะนี้มี (5.8) - (5.10) เราทำตาราง Simplex เริ่มต้น:

ค่าสัมประสิทธิ์จะถูกบันทึกในบรรทัดศูนย์ด้วยสัญญาณย้อนกลับของตัวแปรที่สอดคล้องกันที่ฟังก์ชั่นเป้าหมาย เกณฑ์การมองเห็น (สำหรับงานค้นหาขั้นต่ำ): โซลูชันพื้นฐานที่อนุญาต ( x 0) อย่างดีที่สุดหากไม่มีจำนวนบวกอย่างเคร่งครัดในบรรทัดศูนย์ (ไม่นับค่าของฟังก์ชั่นเป้าหมาย (880)) กฎนี้ใช้กับการวนซ้ำต่อไปนี้ (ตาราง) องค์ประกอบของแถวศูนย์จะเรียกว่าการประมาณการคอลัมน์
ดังนั้นโซลูชันพื้นฐานที่อนุญาตเริ่มต้น (5.9) ไม่ดีที่สุด: 7>0, 14>0 .
ในคอลัมน์ศูนย์ค่าของตัวแปรพื้นฐานจะถูกบันทึกไว้ พวกเขาต้องไม่เป็นลบ (ดูสมการ (5.7)) จากบรรทัดแรกถึงสี่ค่าสัมประสิทธิ์ของตัวแปรจากระบบ (5.8) ถูกเขียนขึ้น
เช่น x 0 ไม่ดีที่สุดแล้วคุณต้องไปที่จุดสุดยอดอื่น ๆ เป็นรูปหลายเหลี่ยมของโซลูชั่นที่อนุญาต (สร้าง D. B.r.R ใหม่) ในการทำเช่นนี้ค้นหาองค์ประกอบชั้นนำและทำการแปลงเฉพาะ (การแปลงแบบง่าย ๆ )
อันดับแรกเราพบองค์ประกอบชั้นนำของตารางซึ่งอยู่ในจุดตัดของคอลัมน์ชั้นนำ (คอลัมน์ที่มีการประเมินผลบวกที่ยิ่งใหญ่ที่สุด) และสตริงโฮสต์ (สตริงที่สอดคล้องกับอัตราส่วนขั้นต่ำขององค์ประกอบคอลัมน์ศูนย์ไปยังองค์ประกอบที่สอดคล้องกัน (อย่างเคร่งครัด บวก) คอลัมน์ชั้นนำ)
ในตารางที่ 1 คอลัมน์ชั้นนำเป็นคอลัมน์ที่สามและบรรทัดชั้นนำคือบรรทัดที่สี่ (ขั้นต่ำ (40 / 1.30 / 1) \u003d 30/1) ทำเครื่องหมายด้วยลูกศรและองค์ประกอบชั้นนำเป็นวงกลม องค์ประกอบตะกั่วแสดงให้เห็นว่าตัวแปรพื้นฐาน x 6 จำเป็นต้องเปลี่ยนด้วยการไม่ใช้การละเมิด x 3. จากนั้นตัวแปรพื้นฐานใหม่จะเป็น x 2, x 3, x 4, x 5,และไม่ตัดการเชื่อมต่อ - x 1, x 6,. ซึ่งหมายความว่าการเปลี่ยนไปใช้จุดสุดยอดใหม่ของโซลูชันที่อนุญาต polyhedron เพื่อค้นหาพิกัดของโซลูชันพื้นฐานที่อนุญาตใหม่ x 00 คุณต้องสร้างตาราง Simplex ใหม่และดำเนินการแปลงระดับประถมศึกษา:
แต่) องค์ประกอบทั้งหมดของสตริงโฮสต์จะถูกแบ่งออกเป็นองค์ประกอบชั้นนำโดยการเปลี่ยนองค์ประกอบชั้นนำนี้ใน 1 (เพื่อความสะดวกในการคำนวณ);
b) การใช้องค์ประกอบไดรฟ์ (เท่ากับ 1) องค์ประกอบทั้งหมดของคอลัมน์ชั้นนำเปลี่ยนเป็นศูนย์ (คล้ายกับวิธีการยกเว้นที่ไม่รู้จัก);
เป็นผลให้ในคอลัมน์ศูนย์ค่าของตัวแปรพื้นฐานใหม่ได้รับ x 2, x 3, x 4, x 5, (ดูตารางที่ 2) - ส่วนประกอบพื้นฐานของจุดสุดยอดใหม่ x 00 (ส่วนประกอบของ Nebase x 1 \u003d 0, x 6 \u003d 0,).

ในฐานะที่เป็นตารางที่ 2 การแสดงโซลูชันฐานใหม่ x 00 \u003d (0.10,30,20,40,0) ไม่ใช่อย่างดีที่สุด (ในบรรทัดศูนย์มีคะแนนที่ไม่ใช่ค่าลบ 7) ดังนั้นด้วยองค์ประกอบชั้นนำ 1 (ดูตารางที่ 2) เราสร้างตาราง Simplex ใหม่ I. สร้างโซลูชันพื้นฐานที่อนุญาตใหม่

ตารางที่ 3 ตรงกับโซลูชันพื้นฐานที่อนุญาต x 000 \u003d (10,0,30,10,50,0) และมันก็เหมาะสมที่สุดเพราะ ไม่มีการประมาณการเชิงบวกในเส้นศูนย์ ดังนั้น f (x 000) \u003d 390 มีค่าต่ำสุดของฟังก์ชั่นเป้าหมาย
ตอบ: x 000 \u003d (10, 0, 30, 10, 50, 0) - จุดต่ำสุด, f (x 000) \u003d 390.

งานการเขียนโปรแกรมเชิงเส้นมาตรฐานตามเงื่อนไข

คุณต้องดำเนินงานต่อไปนี้ในลำดับที่ระบุ

ค้นหาแผนที่ดีที่สุดสำหรับงานโดยตรง:
a) วิธีการกราฟิก
b) Simplex-Method (เพื่อสร้างแผนอ้างอิงแหล่งที่มาขอแนะนำให้ใช้วิธีการเทียมพื้นฐาน)
สร้างงานสองงาน
ค้นหาคุณสมบัติที่ดีที่สุดของงาน Dual จากโซลูชันกราฟิกโดยตรงโดยใช้เงื่อนไขของเรื่องไร้สาระเสริม
ค้นหาแผนที่ดีที่สุดของปัญหาคู่ในทฤษฎีบทคู่แรกโดยใช้ตาราง Simplex ขั้นสุดท้ายที่ได้รับเมื่อแก้ปัญหาโดยตรง (ดูย่อหน้า 1b) ตรวจสอบการอนุมัติ "ค่าของฟังก์ชั่นเป้าหมายของงานสองคู่ในโซลูชันที่ดีที่สุดของพวกเขาตรงกัน"
Dual Task คือการแก้ไขวิธีการ Simplex จากนั้นใช้ตาราง Simplex ขั้นสุดท้ายของงานคู่เพื่อค้นหาแผนที่ดีที่สุดสำหรับงานโดยตรงในทฤษฎีบทคู่แรก เปรียบเทียบผลลัพธ์กับผลลัพธ์ซึ่งได้รับจากวิธีการกราฟิก (ดูส่วนที่ 1a)
ค้นหาโซลูชันจำนวนเต็มที่ดีที่สุด:
a) วิธีการกราฟิก
b) วิธีการของ Homori
เปรียบเทียบค่าของฟังก์ชั่นของจำนวนเต็มและไม่ปฏิบัติตามโซลูชัน

คำถามสำหรับการควบคุมตนเอง

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

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

ในการเริ่มต้นแอปเพล็ตให้คลิกที่ปุ่ม "Simplex" หากมองไม่เห็นปุ่ม "Simplex" เหนือสตริงนี้ Java ไม่ได้ติดตั้งบนคอมพิวเตอร์

หลังจากกดปุ่ม "Simplex" หน้าต่างแรกจะปรากฏขึ้นเพื่อป้อนจำนวนตัวแปรและจำนวนข้อ จำกัด ของงานไปยังวิธี Simplex

หลังจากคลิกที่ปุ่ม "ตกลง" หน้าต่างจะปรากฏขึ้นเพื่อป้อนข้อมูลงานที่เหลืออยู่ในวิธีการ Simplex: โหมดการแสดงผล (เศษส่วนทศนิยมหรือสามัญ) ชนิดของเกณฑ์ของปัญหาขั้นต่ำหรือสูงสุดป้อนค่าสัมประสิทธิ์ฟังก์ชั่นเป้าหมาย และค่าสัมประสิทธิ์ระบบขีด จำกัด ที่มีสัญญาณของ "≤", "≥" หรือ "\u003d" ข้อ จำกัด ของสปีชีส์ x i ≥ 0 ไม่จำเป็นต้องป้อน พวกเขาถูกนำมาพิจารณาในอัลกอริทึมของพวกเขา

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

ข้อผิดพลาดที่เลือกและความคิดเห็นในแอปเพล็ตจะถูกส่งไปที่ [อีเมลได้รับการป้องกัน] หรือโทร 8 962 700 77 06 ซึ่งเราจะขอบคุณคุณมาก

โปรแกรม M-Method

โปรแกรมสำหรับการแก้ปัญหาการขนส่ง

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

Simplex-Method แก้ปัญหาด้วยพื้นฐานเริ่มต้น

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

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

ซ้ำ 0

BP	การตัดสินใจ	ทัศนคติ

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

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

อนุญาตให้องค์ประกอบ ตั้งอยู่ที่จุดตัดของคอลัมน์ความละเอียดและความละเอียดเซลล์ของมันแยกต่างหากเป็น 1. ดังนั้นในการวนซ้ำครั้งต่อไปตัวแปร x 2 จะถูกแทนที่ในพื้นฐาน S 3 โปรดทราบว่าใน z-row ทัศนคติไม่ได้ค้นหามีเส้นประ "-" ในกรณีที่มีอัตราส่วนขั้นต่ำเช่นเดียวกับที่เลือกใด ๆ หากค่าสัมประสิทธิ์ทั้งหมดน้อยกว่าหรือเท่ากับคอลัมน์ความละเอียดการแก้ปัญหานั้นไม่มีที่สิ้นสุด

4) การคำนวณของสตริง S 2 ตาราง "การทำซ้ำ 1" ในตำแหน่ง 3 ในแถว S 2 ของตาราง "การวนซ้ำ 0" ควรเป็น 0 ในตาราง "ทำซ้ำ 1" ในการทำเช่นนี้องค์ประกอบทั้งหมดของสตริง x 2 ตาราง "การวนซ้ำ 1" 0 1 0 0 1 20 คูณบน -3 เราได้รับ 0 -3 0 0 -3 -60 และวางสตริงนี้ด้วย S 2 - บรรทัดนี้ด้วย S 2 - บรรทัดของ ตาราง "การทำซ้ำ 0" 1 3 0 1 0 72, เราได้รับสตริง 1 0 0 1 -3 12. ในคอลัมน์ x 2, ที่ต้องการ 0 จะได้รับคอลัมน์ x 2 ในตาราง "การวนซ้ำ 1" กลายเป็นโสด มันมี 1 1 และที่เหลือ 0

แถวของตาราง "การวนซ้ำ 1" จะได้รับตามกฎต่อไปนี้:

ตัวอย่างเช่นสำหรับ Z - เรามี:

z-row เก่า (-4 -6 0 0 0 0)
- (- 6) * ใหม่ที่อนุญาตให้สตริง - (0-6 0 0 -6 -120)
\u003d z-string ใหม่(-4 0 0 0 6 120) .

การวนซ้ำ 1.

						การตัดสินใจ	ทัศนคติ

การวนซ้ำ 2.

						การตัดสินใจ	ทัศนคติ

คอลัมน์ความละเอียด S 3 การแก้ไขสตริง S 1, S 1 ออกจากฐาน S 3 เข้าสู่พื้นฐาน

การทำซ้ำ 3.

						การตัดสินใจ	ทัศนคติ

Simplex-Method แก้ปัญหาด้วยพื้นฐานเทียม

2) ฉันจะแก้ปัญหาด้วยพื้นฐานเทียม (อย่างน้อยหนึ่งสัญญาณของการจำกัดความไม่เท่าเทียมกัน "≥" หรือ "\u003d")

เราเขียนงานในรูปแบบบัญญัติ (เป็นระบบสมการซึ่งต้องใช้วิธีการง่าย ๆ ) สำหรับสิ่งนี้เราแนะนำตัวแปรสองตัว x 3 ≥ 0 และ x 4 ≥ 0 เราได้รับ:

ระบบ จำกัด มีเพียงหนึ่งตัวแปรพื้นฐานที่อนุญาต x 4 เท่านั้นที่เข้าสู่สมการเพียงหนึ่งเดียวในสามด้วยค่าสัมประสิทธิ์ 1 ดังนั้นในสมการแรกและที่สองเพิ่มตัวแปรประดิษฐ์ r 1 ≥ 0 และ r 2 ≥ 0 และ r 2 ≥ 0 และ r 2 ≥ 0 และ r 2 ≥ 0 และ r 2 ≥ 0 และ r 2 ≥ 0 และ r 2 ≥ 0 และ r 2 ≥ 0 และ r 2 ≥ 0 และ r 2 ≥ 0 ใช้ระบบ Symplex-Method สมการข้อ จำกัด ต้องเป็นระบบที่มีพื้นฐาน I. ในแต่ละสมการจะต้องมีตัวแปรที่มีค่าสัมประสิทธิ์ 1 ซึ่งรวมอยู่ในสมการเดียวของระบบในกรณีของเราคือ R 1, R 2 และ X 4 ได้รับงานที่เรียกว่า m-task:

ระบบนี้เป็นระบบที่มีพื้นฐานซึ่ง r 1, r 2 และ x 4 เป็นตัวแปรพื้นฐานและ x 1, x 2 และ x 3 ตัวแปรฟรีสมาชิกของสมการทั้งหมดไม่เป็นลบ ดังนั้นเพื่อแก้ปัญหาคุณสามารถใช้วิธีการง่ายๆ เราเขียนตาราง Simplex เริ่มต้น:

ซ้ำ 0

	การตัดสินใจ	ทัศนคติ
-16

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

คอลัมน์ความละเอียด x 1 การแก้ไข R 1, R 1 ออกจากฐาน X 1 เข้าสู่พื้นฐาน หลังจากนั้นไม่มีตัวแปรเทียมในฐานดังนั้นจึงไม่มีแถว "การประเมินผล" ในตารางต่อไปนี้:

การวนซ้ำ 2.

							การตัดสินใจ	ทัศนคติ

ถัดไปคอลัมน์ที่อนุญาตจะถูกเลือกโดย z-row ใน z-row ค่าสัมประสิทธิ์ทั้งหมดไม่เป็นลบนอกเหนือจากค่าสัมประสิทธิ์กับตัวแปรเทียม r 1 ซึ่งไม่ส่งผลกระทบต่อการเพิ่มขึ้นเมื่อตัวแปรเทียมออกจากฐาน ดังนั้นจึงได้รับโซลูชันที่ดีที่สุด x 1 \u003d 6/5; x 2 \u003d 3/5; Z Max \u003d 72/5

กรณีพิเศษของการใช้วิธี Simplex

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

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

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