ลองพิจารณาดู วิธีการสากลแนวทางแก้ไขปัญหา Canonical การเขียนโปรแกรมเชิงเส้น
กับ nตัวแปรและ มข้อจำกัดความเท่าเทียมกันหรือที่เรียกว่าวิธีซิมเพล็กซ์
ชุดแผนสำหรับปัญหาตามรูปแบบบัญญัติคือชุดรูปทรงหลายเหลี่ยมนูนที่มีจุดมุมจำนวนจำกัด และหากปัญหานี้มีทางออกที่ดีที่สุด ก็แสดงว่าบรรลุผลสำเร็จที่มุมหนึ่งเป็นอย่างน้อย
แผนพื้นฐานของปัญหาที่เกี่ยวข้องกับจุดมุมใดๆ ซึ่งตัวแปรมีค่าเท่ากับศูนย์ และตัวแปรที่เหลือสอดคล้องกับคอลัมน์อิสระเชิงเส้นของเมทริกซ์เงื่อนไข คอลัมน์อิสระเชิงเส้นเหล่านี้สร้างเมทริกซ์พื้นฐานที่ไม่เป็นเอกพจน์
การวนซ้ำจุดมุมทั้งหมดมีราคาแพงในการคำนวณ ดังนั้นจึงไม่ได้ผล ในปี 1947 J. Dantzig ได้เสนอขั้นตอนที่เป็นระเบียบในการแจกแจงจุดมุม ซึ่งเพียงพอที่จะตรวจสอบเพียงส่วนเล็กๆ เพื่อหาวิธีแก้ปัญหาที่ดีที่สุด ขั้นตอนนี้เรียกว่า วิธีเริม.
J. Danzig เสนอให้แทนที่เวกเตอร์เพียงตัวเดียวในเมทริกซ์พื้นฐานเมื่อเคลื่อนที่จากจุดสุดขั้วหนึ่งไปยังอีกจุดหนึ่ง ซึ่งหมายความว่าในระหว่างการเปลี่ยนแปลงดังกล่าว เราต้องแยกตัวแปรพื้นฐานตัวใดตัวหนึ่งออก - ทำให้ตัวแปรนั้นไม่ใช่ตัวแปรพื้นฐาน ( เท่ากับศูนย์) และแทนที่ตัวแปรใหม่จากตัวแปรที่ไม่ใช่พื้นฐาน (ศูนย์) - ทำให้เป็นตัวแปรพื้นฐาน (บวก)
ปรากฎว่าการแทนที่ทางเรขาคณิตดังกล่าวนำไปสู่การเปลี่ยนจากจุดมุมหนึ่งไปยังจุดที่อยู่ติดกัน (ใกล้เคียง) ที่เกี่ยวข้องกับ จุดก่อนหน้าขอบทั่วไป
จากจุดใกล้เคียงทั้งหมด จะมีการเลือกจุดที่ฟังก์ชันวัตถุประสงค์เพิ่มขึ้นมากที่สุด เนื่องจากจำนวนจุดมุมมีจำกัด ผ่านการเปลี่ยนจุดยอดด้วยจำนวนจำกัด มูลค่าสูงสุดฟังก์ชั่นวัตถุประสงค์หรือความไม่มีขอบเขตของฟังก์ชั่นวัตถุประสงค์จะถูกสร้างขึ้นบนชุดแผนไม่จำกัด
รูปแบบทั่วไปของวิธีซิมเพล็กซ์ประกอบด้วยขั้นตอนหลักดังต่อไปนี้
· ขั้นตอนที่ 0- การกำหนดพื้นฐานเริ่มต้นและจุดมุมเริ่มต้นที่สอดคล้องกัน (เส้นพื้นฐาน)
· ขั้นตอนที่ 1- การตรวจสอบพื้นฐานปัจจุบันเพื่อความเหมาะสมที่สุด . หากเป็นไปตามเกณฑ์การเพิ่มประสิทธิภาพ ที่ แผนนี้เหมาะสมที่สุดและการแก้ปัญหาก็เสร็จสมบูรณ์ มิฉะนั้นไปที่ขั้นตอนที่ 2
· ขั้นตอนที่ 2- การค้นหาตัวแปรที่นำมาใช้กับตัวแปรพื้นฐาน (จากเงื่อนไขการเพิ่มฟังก์ชันวัตถุประสงค์)
· ขั้นตอนที่ 3- การค้นหาตัวแปรที่แยกออกจากตัวแปรพื้นฐาน (จากเงื่อนไขการรักษาข้อจำกัดของปัญหา)
· ขั้นตอน 4 - ค้นหาพิกัดของเส้นฐานใหม่ (จุดมุมที่อยู่ติดกัน) ไปที่ขั้นตอนที่ 1
ทำซ้ำขั้นตอนที่ 1-4 ในรูปแบบการวนซ้ำของวิธีซิมเพล็กซ์
จากแผนภาพนี้เป็นไปตามนั้น ประการแรกในการเริ่มต้นวิธีซิมเพล็กซ์ คุณต้องมีจุดมุมบางประเภท - แผนพื้นฐานเริ่มต้น และประการที่สอง คุณต้องสามารถตรวจสอบจุดมุมปัจจุบันเพื่อความเหมาะสมที่สุดโดยไม่ต้องคำนวณจุดที่อยู่ติดกันทั้งหมด จุดยอด ปัญหาเหล่านี้จะแก้ไขได้อย่างง่ายดายหากปัญหา Canonical LP มีรูปแบบพิเศษบางอย่าง
คำนิยาม- เราจะบอกว่าปัญหา Canonical LP มี "รูปแบบที่ต้องการ" ถ้า
1. ด้านขวามือของสมการ .
2. เมทริกซ์เงื่อนไขประกอบด้วยเมทริกซ์ย่อยหน่วยที่มีขนาด
กล่าวอีกนัยหนึ่ง ในสมการใดๆ มีตัวแปรที่มีค่าสัมประสิทธิ์เท่ากับหนึ่ง ซึ่งไม่มีอยู่ในสมการอื่น เงื่อนไขแรกไม่เป็นภาระ เนื่องจากในกรณีของสมการทางขวามือที่เป็นลบ ก็เพียงพอที่จะคูณด้วย (-1) ในปัญหาประเภทสิทธิพิเศษ การค้นหาเส้นฐานเริ่มต้นนั้นง่ายมาก
ตัวอย่างที่ 2.1
เมทริกซ์เงื่อนไข กและเวกเตอร์ของด้านขวามือของข้อจำกัด ขดูเหมือน
และเวกเตอร์เป้าหมาย c = (1, -3, 0, 4, 2)
เมทริกซ์พื้นฐานหนึ่งนั้นชัดเจนทันที: ด้วยเวกเตอร์หน่วยของเงื่อนไข
ดังนั้นการเลือกเป็นตัวแปรพื้นฐาน x 1 , x 3 ,x 5 , และใส่ระบบสมการลงไป x 2 = x 4 = 0 (ตัวแปรที่ไม่ใช่พื้นฐาน) , เราพบมันทันที x 1 = 10,x 3 = 20,x 5 = 8 ดังนั้นเป็นพื้นฐานเริ่มต้น x 0 = (10, 0, 20, 0, 8). เราจะเห็นว่าค่าของตัวแปรพื้นฐานเท่ากับด้านขวามือของข้อจำกัด จากนี้ชัดเจนว่าฝั่งขวาจะต้องเป็นบวก ข ฉัน .
ในอนาคต เราจะรวมตัวแปรพื้นฐานให้เป็นเวกเตอร์ x บี.
ดังนั้นใน ปัญหามาตรฐานของรูปแบบที่ต้องการ เมทริกซ์ย่อยของหน่วยจะถูกใช้เป็นเมทริกซ์พื้นฐานเริ่มต้น ก บี = อีและตัวแปรพื้นฐานที่สอดคล้องกันจะเท่ากับทางด้านขวามือของข้อจำกัด:
x บี = ข.
สำหรับแผนพื้นฐานประเภทนี้ สามารถกำหนดเกณฑ์การเพิ่มประสิทธิภาพที่ง่ายพอที่จะทดสอบได้ เรามาแนะนำปริมาณกัน
? เจ = < с บี , ก เจ > - ค เจ , เจ = 1,...,n,(2.1)
ที่ไหน กับ บี- เวกเตอร์ของสัมประสิทธิ์ของฟังก์ชันวัตถุประสงค์สำหรับตัวแปรพื้นฐาน x บี , ก เจ -เจ-ไทย คอลัมน์เมทริกซ์เงื่อนไข ค เจ -เจ-ค่าสัมประสิทธิ์ของฟังก์ชันวัตถุประสงค์ ความแตกต่าง ? เจเรียกว่าผลต่างเชิงเริมหรือค่าประมาณเชิงเริม
เกณฑ์การเพิ่มประสิทธิภาพสำหรับแผนพื้นฐาน- ถ้าเป็นแผนพื้นฐานแบบมียูนิต เมทริกซ์พื้นฐานการประมาณการด้านซิมเพล็กซ์ทั้งหมดไม่เป็นลบ ดังนั้นแผนนี้จึงเหมาะสมที่สุด
ให้เราใช้เกณฑ์นี้เพื่อตรวจสอบความเหมาะสมของแผนพื้นฐาน x 0 = (10, 0, 20, 0, 8) จากตัวอย่างที่ 2.1
เนื่องจากในเรื่องนี้เวกเตอร์ของตัวแปรพื้นฐาน x บี =(x 1 , x 3 ,x 5 ), ที่ กับ บี = (ค 1 , ค 3 ,ค 5 ) = (1, 0, 2).
เพราะฉะนั้น,
? 1 = < с บี , ก 1 > - ค 1 = 1 1 + 0 0 + 2 0 - 1= 0,
2 = < сБ, A2 >- c2 = 1 3 + 0 1 + 2 2 - (-3) = 10,
? 3 = < с บี , ก 3 > - ค 3 = 1 0 + 0 1 + 2 0 - 0= 0,
? 4 = < с บี , ก 4 > - ค 4 = 1 (-1) + 0 5 + 2 1 - 4= -3,
? 5 = < с บี , ก 5 > - ค 5 = 1 0 + 0 0 + 2 1 - 2= 0.
นับตั้งแต่มีการประเมิน ? 4 < 0, то базисный план x 0 ไม่เหมาะที่สุด โปรดทราบว่าค่าประมาณด้านซิมเพล็กซ์ที่สอดคล้องกับตัวแปรพื้นฐานจะเท่ากับศูนย์เสมอ ดังนั้นจึงเพียงพอแล้วที่จะตรวจสอบเฉพาะค่าประมาณที่ไม่ใช่ค่าพื้นฐานเท่านั้น
วิธีซิมเพล็กซ์ประกอบด้วยการค้นหาและทดสอบจุดยอด (มุม) ที่เป็นวิธีแก้ปัญหา LP ในแต่ละขั้นตอน วิธีการจะเลือกจุดยอดและตัวแปรที่เกี่ยวข้อง ซึ่งรับประกันการเคลื่อนที่ไปยังจุดต่ำสุด (สูงสุด) ด้วย ความเร็วสูงสุด- ตัวแปรที่เลือกจะแทนที่ตัวแปรอื่นที่มีข้อจำกัดมากที่สุด วิธีซิมเพล็กซ์ยังช่วยให้คุณระบุได้ว่ามีวิธีแก้ปัญหาอยู่หรือไม่ อัลกอริทึมที่ใช้วิธีซิมเพล็กซ์สามารถเขียนได้เป็น:
ขั้นตอนที่ 1มีการกำหนดจุดยอดที่แน่นอนใน ODR ซึ่งสอดคล้องกับสารละลายพื้นฐานที่ยอมรับได้ (ตัวแปร) ที่พบโดยการดึงข้อมูลจากเมทริกซ์ ต- เชิงเส้น คอลัมน์อิสระและตั้งค่าตัวแปรอื่นๆ ทั้งหมดที่สอดคล้องกับคอลัมน์อื่นๆ ของเมทริกซ์ให้เป็นศูนย์
ขั้นตอนที่ 2เลือกจากจำนวนที่เหลือที่เป็นไปได้ทั้งหมด พี - ทีขอบที่สอดคล้องกับตัวแปรที่ไม่ใช่พื้นฐาน ขอบ (ตัวแปร) ที่เมื่อเคลื่อนที่ไปตามนั้น จะนำไปสู่การลดลงเร็วที่สุดในฟังก์ชันวัตถุประสงค์
ขั้นตอนที่ 3เหมือนกับว่ามีการเคลื่อนไหวจากจุดยอดเริ่มต้นไปตามขอบที่เลือกไปยังจุดยอดอื่น ซึ่งให้โซลูชันใหม่ที่มีค่า CF ต่ำกว่า จุดยอดใหม่ถูกสร้างขึ้นโดยการแทนที่ตัวแปรพื้นฐาน (ขอบ) ด้วยตัวแปรพื้นฐานใหม่ (ขอบ)
คอลัมน์และองค์ประกอบของเวกเตอร์มักจะเรียงลำดับและเขียนในรูปแบบของตารางซิมเพล็กซ์ ซึ่งจะแสดงไว้ด้านล่าง
วิธีซิมเพล็กซ์แก้ปัญหา LP ใน แบบฟอร์มมาตรฐาน.
ย่อเล็กสุด (ขยายใหญ่สุด) ฟังก์ชันภายใต้เงื่อนไข x > 0; ขวาน = ข.
เมทริกซ์ A เป็นของจริงและมีมิติ ต x "และอันดับ ต.
ปัญหา LP ที่กำหนดสามารถเขียนได้ในรูปแบบ
จากการบันทึกปัญหา LP ในรูปแบบ (8L) เราสามารถพูดได้ว่าเมทริกซ์แบบขยาย
ขนาด (ที + 1) (น + 2) สอดคล้องกับวิธีแก้ปัญหา[x/] เสื้อ
ลองแทนเมทริกซ์ A เป็นเซตของคอลัมน์กัน
เนื่องจากเมทริกซ์ A มีอันดับ ที,แล้วจะมี ตคอลัมน์อิสระเชิงเส้นของเมทริกซ์ A ตัวอย่างเช่น (a U1 ,...,a U/u พิจารณาเวกเตอร์ x° > 0 เพื่อให้ทั้งหมดนั้น พี - ทีองค์ประกอบคือ 0 และ Ax° = b ให้สิ่งเหล่านี้เป็นองค์ประกอบที่มีตัวเลข..., ฉัน n_mให้เราสมมติด้วยว่าตำแหน่ง aw ของคอลัมน์อิสระเชิงเส้นของเมทริกซ์ A สอดคล้องกับตำแหน่งขององค์ประกอบที่ไม่เป็นศูนย์ในเวกเตอร์ 0 ในเชิงเรขาคณิต ตามข้อความที่ 3 ของมาตรา 7.6 หมายความว่า x° คือจุดยอด (มุม) ของ ODR และยังเป็นไปตามเงื่อนไขที่กำหนดอีกด้วย วิธีแก้ปัญหานี้เรียกว่า วิธีแก้ปัญหาพื้นฐานที่ยอมรับได้มุมของชุดที่ยอมรับได้คือ วิธีแก้ปัญหาพื้นฐานที่ยอมรับได้
โปรดจำไว้ว่าชุดวิธีแก้ปัญหาพื้นฐานประกอบด้วยข้อมูลทั้งหมดที่จำเป็นสำหรับการแก้ปัญหา LP อย่างเหมาะสมที่สุด สำหรับกรณีสองมิติที่พิจารณาใน § 7.6 คำตอบพื้นฐานคือทั้งหมด 6 คะแนน และคำตอบพื้นฐานที่ยอมรับได้คือคะแนน ล, วี,ศรี 0.
ดังนั้น เวกเตอร์ x ใดๆ ที่คล้ายกับ x° สามารถเขียนได้เป็น
ที่ไหน x เข้า- เวกเตอร์ที่มีองค์ประกอบสอดคล้องกับคอลัมน์อิสระเชิงเส้นของเมทริกซ์ A เอ็กซ์เอฟ -เวกเตอร์ที่มีองค์ประกอบเป็นศูนย์
ขอให้เรานิยามเวกเตอร์ในทำนองเดียวกัน
ตัวแปรที่เป็นองค์ประกอบของเวกเตอร์ x ในถูกเรียก ตัวแปรพื้นฐานและตัวแปรที่เป็นองค์ประกอบของเวกเตอร์ x เอฟถูกเรียก ฟรี (ไม่ใช่พื้นฐาน) ตัวแปร
เพราะ x° เอฟ=0 แล้วค่าของฟังก์ชันวัตถุประสงค์สำหรับเวกเตอร์เริ่มต้น x° จะเท่ากับ
โดยที่ /° คือค่าของ / ที่จุด x°
เรียกว่าสารละลาย (8.1) ในรูปแบบ [x°/°]t สำหรับ x > 0 วิธีแก้ปัญหาที่ชัดเจน (ชัดเจน)ดังนั้น หากเราตั้งค่าตัวแปรที่ไม่ใช่พื้นฐานให้เป็นศูนย์ เราจะได้คำตอบที่ชัดเจน
เพื่อความสะดวกขอจัดเรียงใหม่ครับ ตคอลัมน์อิสระเชิงเส้นของเมทริกซ์ A นิ้ว ด้านซ้ายและเขียนเมทริกซ์ในรูป
ที่นี่เมทริกซ์ B สอดคล้องกัน ตคอลัมน์อิสระเชิงเส้น 
มีมิติ tx เสื้อและอันดับ ที,และเมทริกซ์ F
เป็น เท็กซัส (พี - ที)เมทริกซ์ เนื่องจากเมทริกซ์ B ประกอบด้วยคอลัมน์อิสระเชิงเส้น จึงมีค่าผกผัน B -1 และ detB φ 0 โปรดทราบว่าในการสร้างเมทริกซ์ B คุณสามารถเลือกอะไรก็ได้ ตคอลัมน์อิสระเชิงเส้นของเมทริกซ์ A
ให้เรานำเสนอปัญหา (8.1) โดยคำนึงถึงสัญกรณ์ที่แนะนำ
การแสดงนี้สอดคล้องกับเมทริกซ์ขยาย ให้เราสมมติว่า
ตามมาที่ไหน
ถ้าเวกเตอร์ x วีจะเป็นคำตอบของระบบ Bx d = b จากนั้นจะเป็นคำตอบพื้นฐาน หากยังมีความไม่เท่าเทียมกันอยู่ วี= B -1 b > O แล้ว x เข้าจะเป็นทางออกที่ยอมรับได้
ดังนั้น, โซลูชั่นปัจจุบันเป็นไปตามสมการต่อไปนี้:
ลองพิจารณาเมทริกซ์ (8.4) ตัวแปรพื้นฐานจะนำเสนอใน อย่างชัดเจนถ้าเราแทนที่เมทริกซ์ B ด้วยเมทริกซ์เอกลักษณ์ I เมื่อคูณแถวแรกของเมทริกซ์ (8.4) ทางซ้ายด้วย B~ 1 เราจะได้
โดยที่ B_1 b > O เช่น ต องค์ประกอบด้านบนในคอลัมน์ด้านขวาไม่เป็นค่าลบและแสดงถึงค่าปัจจุบันของตัวแปร
ด้านซ้าย บรรทัดบนสุดผลลัพธ์คือเมทริกซ์หน่วย: B -1 B = I การนำเสนอครั้งนี้สะดวกมากตั้งแต่เมื่อคูณด้วยเวกเตอร์ x เข้าแต่ละตัวแปรจะอยู่ในบรรทัดที่แยกจากกัน
ดังนั้น วิธีแก้ปัญหาพื้นฐานซึ่งเราจะพิจารณาว่ายอมรับได้และสอดคล้องกับพื้นฐาน B คือ x m = [x ใน 0] โดยที่ x ใน == B_1 ข. การแก้ปัญหาเบื้องต้นเกิดจากการสันนิษฐานว่า x ฟ = 0. อย่างไรก็ตาม ถ้า xF* 0 ดังนั้น x^ สามารถคำนวณได้เป็น x 5 = = B~"b - B^"Fx/r การแทนที่นิพจน์นี้เป็น ฟังก์ชั่นเป้าหมาย(ฟังก์ชันต้นทุน) เราได้
เนื่องจากจำเป็นต้องกำหนดการพึ่งพาต้นทุนของตัวแปรที่ไม่ใช่พื้นฐาน ซึ่งหนึ่งในนั้นจะรวมอยู่ในตัวแปรพื้นฐาน บรรทัดล่างสุดภายใต้เมทริกซ์ I จึงควรเป็นศูนย์ เมื่อต้องการทำเช่นนี้ ใน (8.7) เราจะคูณแถวแรก (ของเมทริกซ์) ด้วย จากถึงและเพิ่มด้วยอันที่สอง
โดยที่ค่าของฟังก์ชันวัตถุประสงค์สำหรับศตวรรษเริ่มต้นคือ
พรู x 0 จาก (8.3)
เรียกว่าเมทริกซ์ (8.8) ตารางเริมจะพาเธอไป. สายพันธุ์นี้เป็น ระยะเริ่มแรกอัลกอริธึมซิมเพล็กซ์ ในระหว่างการดำเนินการอัลกอริธึม การเปลี่ยนแปลงจะทำจากตารางหนึ่งไปยังอีกตารางหนึ่งจนกระทั่งองค์ประกอบมุมขวาล่างของตารางกลายเป็นค่าสูงสุดหรือต่ำสุด
การใช้ตารางซิมเพล็กซ์ทำให้ง่ายต่อการดูวิธีแก้ปัญหาที่เป็นไปได้ ตัวแปร x F สอดคล้องกับเมทริกซ์ย่อยศูนย์ ตัวแปร x เข้า- เมทริกซ์หน่วย:
สมมติว่าปัญหา LP ลดลงเป็นรูปแบบมาตรฐาน ตารางซิมเพล็กซ์ได้รับการคำนวณแล้ว และเลือกวิธีแก้ปัญหาพื้นฐานเริ่มต้นที่สอดคล้องกับจุดยอดของรูปทรงหลายเหลี่ยมของโซลูชันแล้ว
แล้ว 
- การแก้ปัญหา (8.1) ดังนั้น
เช่น b > โอ้ นี่เป็นวิธีแก้ปัญหาพื้นฐานที่ยอมรับได้
ให้เรานำเสนอเมทริกซ์ (8.9) ในรูปแบบที่สะดวกยิ่งขึ้น โดยคงสัญกรณ์พื้นฐานไว้:
ให้เราพิจารณาปัญหาของการขยายใหญ่สุดและการย่อเล็กสุดแยกกัน
การค้นหาแผนการที่เหมาะสมที่สุด วิธีนี้เป็นสากล โดยช่วยให้สามารถแก้ปัญหาการโปรแกรมเชิงเส้นทุกมิติในสูตรทั่วไปได้ อย่างไรก็ตาม วิธีการนี้จำเป็นต้องลดปัญหาเดิมให้อยู่ในรูปแบบมาตรฐาน
แนวคิดหลักของวิธีซิมเพล็กซ์คือการย้ายจากจุดยอดหนึ่งของ ODR ไปยังอีกจุดหนึ่ง เพื่อให้ค่าของ CF ลดลงในแต่ละช่วงการเปลี่ยนภาพ นี่คือวิธีที่คุณจะได้รับจากจุดยอดใดๆ ไปยังจุดที่เหมาะสมที่สุด และรับแผนที่เหมาะสมที่สุด
ตัวอย่างเช่น: ให้แผนอ้างอิง X =(x1,x2,…,xm,0,0,…,0) และระบบที่เกี่ยวข้องของเวกเตอร์อิสระเชิงเส้น: A1,A2,…,ฉันเป็นที่รู้จัก ดังนั้นสำหรับแผนอ้างอิงนี้ คุณสามารถคำนวณค่า CF Z=(c1x1+c2x2+…+cmxm) และจดเงื่อนไขข้อจำกัดไว้ใน แบบฟอร์มต่อไปนี้ x1A1+x2A2+…+xmAm=b
เนื่องจากเวกเตอร์ A1, A2,…, Am มีความเป็นอิสระเชิงเส้น เวกเตอร์ Aj ใดๆ จึงสามารถขยายเป็นเวกเตอร์เหล่านี้ได้: Aj=x1jA1+x2jA2+…+xmjAm (*) ให้เราแนะนำค่า Zj Zj=x1jc1+x2jc2+…+ xmjcm โดยที่ xij คือสัมประสิทธิ์ที่สอดคล้องกับ Ai ในเวกเตอร์ส่วนขยาย Aj ด้วยเวกเตอร์พื้นฐาน
ทฤษฎีบทที่ 1: การปรับปรุงแผนอ้างอิง
หากดัชนี j บางตัวเป็นไปตามเงื่อนไข Zj-Cj>0 ค่าของ CF ก็สามารถลดลงได้ และ:
· ถ้า CF ถูกจำกัดจากด้านล่าง ก็สามารถสร้างแผนอ้างอิงที่มีค่า CF น้อยลงได้ เช่นเดียวกับค่า CF ก่อนหน้า
· หาก TF ไม่ได้ถูกจำกัดจากด้านล่าง ก็เป็นไปได้ที่จะสร้างแผนที่สอดคล้องกับค่า TF ที่น้อยตามอำเภอใจ
ทฤษฎีบทที่ 2: เกณฑ์การปรับให้เหมาะสมที่สุดสำหรับแผนอ้างอิง
ถ้าสำหรับดัชนี j บางตัวในแผนอ้างอิงความไม่เท่าเทียมกัน Zj-Cj0 ปล่อยให้เวกเตอร์ Ak บรรลุค่าต่ำสุดนี้ แล้วเวกเตอร์นี้จะต้องได้มาจากฐาน เส้นตรงที่สอดคล้องกับเวกเตอร์นี้เรียกว่าเส้นบอกแนวและเขียนว่า "à"
4. หลังจากกำหนดเส้นบอกแนวคอลัมน์และแถวแล้ว ให้กรอกตารางซิมเพล็กซ์ใหม่ ในตารางดังกล่าว Ai จะปรากฏแทนที่เส้นบอกแนว การกรอก ตารางใหม่เริ่มต้นด้วยเส้นแนะนำ เนื่องจากเป็นส่วนประกอบของแผนอ้างอิง ค่า gest0 X'l=og0=Xk/Xkl จะถูกเขียนไว้ที่นั่น องค์ประกอบที่เหลือของบรรทัดนี้จะถูกกำหนดโดยสูตร X'lj X'lj=Xkj/Xkl โดยที่ Xkl เป็นองค์ประกอบ ตั้งอยู่ที่จุดตัดของเส้นบอกแนวแถวและคอลัมน์ โดยเฉพาะองค์ประกอบเดิมทั้งหมดของเส้นบอกแนวจะถูกแบ่งออก และหน่วยจะปรากฏขึ้นโดยอัตโนมัติในตำแหน่งขององค์ประกอบ Xkl เดิม กฎทั่วไปหากต้องการคำนวณเส้นบอกแนวใหม่ให้เขียนได้ดังนี้ Ak (องค์ประกอบใหม่ของเส้นบอกแนว) = (องค์ประกอบเก่าของเส้นบอกแนว)/(องค์ประกอบยืนอยู่ที่จุดตัดของคอลัมน์และแถวนำ)
5. องค์ประกอบทั้งหมดของแถวที่เหลือของตารางจะถูกคำนวณใหม่ รวมถึงองค์ประกอบเพิ่มเติมด้วย บรรทัดล่าง- การคำนวณใหม่ดำเนินการตามสูตร
· สำหรับส่วนประกอบของแผนอ้างอิง X'i=Xi-̨0Xil=Xi-(Xk/Xkl)*Xil
· สำหรับส่วนประกอบที่ขยายตามพื้นฐาน X'ij=Xij-(Xkj/Xkl)*Xil
· สำหรับ บรรทัดเพิ่มเติม Z'j-Cj=(Zj-Cj)-(Xkj/Xkl)*(Zl-Cl)
สูตรทั้งหมดนี้สร้างขึ้นตามกฎข้อเดียว:
(อีเมลใหม่)=(อีเมลเก่า)-(อีเมลทิศทางของแถวใหม่)*(อีเมลทิศทางสำหรับคอลัมน์ในแถวที่เกี่ยวข้อง)
หลังจากกรอกตารางซิมเพล็กซ์ใหม่แล้ว การเปลี่ยนไปสู่ขั้นตอนที่สองของอัลกอริทึมจะเกิดขึ้น
วิธีธรรมชาติและ พื้นฐานเทียม- แนวคิดพื้นฐาน อัลกอริธึมของวิธีการ
สำหรับปัญหาการโปรแกรมเชิงเส้นส่วนใหญ่ ความยากลำบากเกิดขึ้นในการแก้ปัญหาที่เกี่ยวข้องกับการกำหนดแผนอ้างอิงเริ่มต้นและตารางซิมเพล็กซ์เริ่มต้นซึ่งเป็นจุดเริ่มต้นของการวนซ้ำทั้งหมด นี่เป็นเพราะความจริงที่ว่าในปัญหาจริงของเวกเตอร์ Ai นั้นไม่มีเวกเตอร์ที่มีองค์ประกอบที่ไม่เป็นศูนย์เพียงองค์ประกอบเดียว นั่นคือ เวกเตอร์ในรูปแบบ (0,0,0,…,0,1,0,…,0) หรือจำนวนไม่เพียงพอที่จะสร้างพื้นฐาน นั่นคือไม่สามารถสร้างพื้นฐานตามธรรมชาติได้
วิธีการพื้นฐานเทียมนั้นขึ้นอยู่กับ การแนะนำเทียมวี แบบจำลองทางคณิตศาสตร์ปัญหาของเวกเตอร์ดังกล่าว
ให้มันได้รับ ZLP ตามบัญญัติแบบฟอร์ม
F: C1X1=C2X2+…+CnXnàmin
a11x1+a21x2+…+an1xn=b1
a12x1+a22x2+…+an2xn=b2
…………………………
a1mx1+a2mx2+…+anmxn=bm
จากนั้นจึงแปลงเป็นแบบฟอร์ม
F: C1X1+C2X2+…+CnXn+MXn=1+MXn+2+…+MXn+มามิน
a11x1+a21x2+…+an1xn+xn+1=b1
a12x1+a22x2+…+an2xn+xn+2=b2
……………………………….
a1mx1+a2mx2+…+anmxn+xn+m=bm
โดยที่ M ไม่มีที่สิ้นสุด ตัวเลขใหญ่- ในปัญหาที่เกิดขึ้น พื้นฐานเริ่มต้นจะมองเห็นได้ทันที ควรพิจารณาเวกเตอร์ที่มีตัวแปรนำเข้า xn+1, xn+2,…, xn+m แทน เนื่องจากเวกเตอร์เหล่านี้จะมีรูปแบบ: (1,0,0,…,0),(0,1,0,…,0),(0,0,…,1) ปัญหาที่แปลงแล้วได้รับการแก้ไขโดยใช้อัลกอริธึมวิธีซิมเพล็กซ์ แผนอ้างอิงเบื้องต้นของปัญหาการแปลงมีรูปแบบ (0,0,…,0,xn+1,xn+2,…,xn+m)=(0,0,…,0,b1,b2,…, บีเอ็ม) ตาราง Simplex ดั้งเดิมมีลักษณะดังนี้:
| พื้นฐาน | ค่าสัมประสิทธิ์ ซีเอฟ | วางแผน | ค1 | ค2 | … | ซีเอ็น | ม | ม | … | ม |
| A1 | A2 | … | หนึ่ง | อัน+1 | อัน+2 | … | อัน+ม | |||
| อัน+1 | ม | ข1 | ก11 | ก21 | … | อัน1 | 1 | 0 | … | 0 |
| อัน+2 | ม | ข2 | ก12 | ก22 | … | อัน2 | 0 | 1 | … | 0 |
| … | … | … | … | … | … | … | … | … | … | … |
| อัน+ม | ม | บีเอ็ม | ก1ม | เอทูม | … | เช้า | 0 | 0 | … | 1 |
| Z0 | ||||||||||
เรากำหนดองค์ประกอบของบรรทัดเพิ่มเติมโดยใช้สูตร Z0=Mb1+Mb2+…+Mbm=∑mi=1Mbi=M∑ni=1bi
เพื่อกำหนดความแตกต่าง Zj=a11M+Ma12+…+Ma1m=M∑mj=1aij V i=1,n
Zj-Cj=M∑mj=1aij-Cj
หลังจากได้รับตารางซิมเพล็กซ์ดั้งเดิม ตารางนั้นจะถูกแปลง โดยพยายามหามาจากเวกเตอร์พื้นฐานที่สอดคล้องกับตัวแปรเพิ่มเติมที่แนะนำ
เนื่องจากเอ็มเป็นอย่างมาก จำนวนมากจากนั้นในบรรดาความแตกต่าง Zj-Cj จะมีจำนวนบวกมากมาย นั่นคือจะมีผู้สมัครจำนวนมากที่จะรวมไว้ในพื้นฐานระหว่างเวกเตอร์ A1,A2,…,An
หากเวกเตอร์บางตัวสอดคล้องกับตัวแปรที่แนะนำอย่างผิด ๆ xn+1,xn+2,…,xn+m ดังนั้นเวกเตอร์ที่สอดคล้องกันจะได้มาจากพื้นฐาน และคอลัมน์ซิมเพล็กซ์ของตารางที่มีเวกเตอร์นี้จะถูกขีดฆ่าออกและจะไม่ส่งคืน ไปที่มันอีกครั้ง ในตอนท้ายของการแปลงตารางด้านเดียว มีสองตัวเลือกที่เป็นไปได้:
· เวกเตอร์ทั้งหมดที่สอดคล้องกับตัวแปรเทียมได้มาจากพื้นฐาน ในกรณีนี้ คอลัมน์ทั้งหมดของตารางซิมเพล็กซ์ที่สอดคล้องกับตัวแปรเพิ่มเติมจะหายไป และวิธีการแก้ปัญหาจะเป็น ปัญหาเดิม
· แผนผลลัพธ์ที่เหมาะสมที่สุดจะยังคงประกอบด้วยตัวแปรเพิ่มเติม ซึ่งหมายความว่า ODD ของปัญหาเดิมว่างเปล่า กล่าวคือ ข้อจำกัดของมันขัดแย้งกัน ดังนั้นปัญหาเดิมจึงไม่มีวิธีแก้ปัญหาเลย
ปัญหาการเขียนโปรแกรมเชิงเส้นคู่ คำชี้แจงปัญหาคุณสมบัติของพวกเขา
ปัญหาคู่สมมาตร:
แบบฟอร์มมาตรฐานครั้งแรก
f(x)=c1x1+c2x2+…+cnxnàmin
a11x1+a21x2+…+an1xn>=b1
a12x1+a22x2+…+an2xn>=b2
…………………………………………..
a1mx1+a2mx2+…+anmxn>=bm
ปัญหาคู่
d(y)=b1y1+b2y2+…+บีมายมาแม็กซ์
a11y1+a12y2+…+a1mym=0, V เจ=1,ม
คู่ที่ไม่ใช่เซปเทนารีของปัญหาคู่
ปัญหาเดิมๆใน. รูปแบบบัญญัติ
f(x)=c1x1+c2x2+…+cnxnàmin
a11x1+a21x2+..+an1xn=b1
a12x1+a22x2+..+an2xn=b2
…………………………..
2. การแนะนำตัวแปรพื้นฐานทางธรรมชาติ การสร้างโต๊ะซิมเพล็กซ์ คำจำกัดความของแผนศูนย์
วิธีเริม อัลกอริทึมของวิธีซิมเพล็กซ์
วิธีเริม- อัลกอริทึมสำหรับการแก้ปัญหาการปรับให้เหมาะสมของการโปรแกรมเชิงเส้นโดยการแจกแจงจุดยอดของรูปทรงหลายเหลี่ยมนูนในพื้นที่หลายมิติ วิธีการนี้ได้รับการพัฒนาโดย George Danzig นักคณิตศาสตร์ชาวอเมริกันในปี 1947
แนวคิดของวิธีซิมเพล็กซ์คือปัญหาเชิงพรรณนาที่ถูกวางถูกแปลเป็นรูปแบบทางคณิตศาสตร์ การกำหนดทางคณิตศาสตร์ของปัญหาประกอบด้วยสมการของฟังก์ชันวัตถุประสงค์ซึ่งระบุผลลัพธ์ที่ต้องการ - กำหนดค่าต่ำสุดหรือสูงสุดของฟังก์ชันวัตถุประสงค์ ระบบ ข้อจำกัดเชิงเส้นกำหนดโดยความเท่าเทียมกันหรือความไม่เท่าเทียมกัน คำอธิบายทางคณิตศาสตร์ที่ได้จะนำไปสู่ รูปแบบเมทริกซ์- จากนั้นคำอธิบายเมทริกซ์ของปัญหาจะลดลงเป็นรูปแบบมาตรฐาน หลังจากที่ระบบ สมการเชิงเส้นลดเหลือรูปแบบ Canonical เราก็เริ่มแก้ปัญหาการเขียนโปรแกรมเชิงเส้น อัลกอริธึมสำหรับการแก้ปัญหานี้ประกอบด้วยลำดับการสร้างเมทริกซ์ แต่ละขั้นตอนของการแก้ปัญหาจะทำให้คุณเข้าใกล้ผลลัพธ์ที่ต้องการมากขึ้น
ในรูปแบบการคำนวณของวิธีซิมเพล็กซ์ กระบวนการสั่งจะถูกนำมาใช้โดยเริ่มต้นจากจุดมุมที่ยอมรับได้เริ่มต้น (โดยปกติคือจุดกำเนิด) การเปลี่ยนต่อเนื่องจากจุดสุดขั้วที่ยอมรับได้หนึ่งไปยังอีกจุดหนึ่งจะดำเนินการจนกระทั่งจุดที่สอดคล้องกับวิธีแก้ปัญหาที่ดีที่สุด พบแล้ว
อัลกอริธึมวิธี Simplex
1. เรานำระบบข้อจำกัดมาสู่รูปแบบมาตรฐาน (เมื่อระบบถูกจำกัด) นอกจากนี้ยังสามารถระบุพื้นฐานเดียวในระบบได้
2. ค้นหาต้นฉบับ แผนอ้างอิง(คำตอบพื้นฐานที่ไม่เป็นลบของระบบสมการ KZLP) แผนอ้างอิงแต่ละแผนถูกกำหนดโดยระบบของเวกเตอร์อิสระเชิงเส้น m ที่มีอยู่ในระบบที่กำหนดของ n เวกเตอร์ ก 1 , ก 2 ,…, หนึ่ง- ขีดจำกัดบนของจำนวนแผนอ้างอิงที่มีอยู่ในปัญหาที่กำหนดจะพิจารณาจากจำนวนชุดค่าผสม กับ นาโนเมตร);
3. เราสร้าง ตารางเริม (ตารางเริมเมทริกซ์ที่ทำหน้าที่เป็นวิธีการแจกแจงวิธีแก้ปัญหาพื้นฐานที่ยอมรับได้ของปัญหาการเขียนโปรแกรมเชิงเส้น (ไม่เสื่อมลง) เมื่อทำการแก้ไขโดยใช้วิธีซิมเพล็กซ์ มันถูกสร้างขึ้นจากเมทริกซ์ของค่าสัมประสิทธิ์ของระบบสมการการเขียนโปรแกรมเชิงเส้นที่ลดลงเป็นรูปแบบมาตรฐาน การแปลงตามลำดับตามที่เรียกว่าอัลกอริธึมซิมเพล็กซ์ช่วยให้ขั้นตอนจำนวน จำกัด (การวนซ้ำ) เพื่อให้ได้ผลลัพธ์ที่ต้องการ - แผนที่ให้ ค่าสุดขีดของฟังก์ชันวัตถุประสงค์)
4. บี ตารางเริมเราตรวจสอบเวกเตอร์เพื่อหาค่าลบ เช่น การประเมิน Zj – ชเขียนในบรรทัดจะต้องเป็น ≤ 0 (อย่างน้อยที่สุด) Zj – Сj ≥ 0(ให้สูงสุด) หากการประมาณการเป็นไปตามเงื่อนไขการปรับให้เหมาะสมที่สุด ปัญหาก็จะได้รับการแก้ไข
5. หากเงื่อนไขการปรับให้เหมาะสมที่สุดถูกละเมิดสำหรับเวกเตอร์บางตัว จำเป็นต้องแนะนำเวกเตอร์ที่สอดคล้องกับ:
สูงสุด[θ 0 เจ (Zj – Сj)] ; นาที[θ 0 เจ (Zj – Сj)] ; θ 0 เจ = นาที, ที่ไหน x ฉัน> 0
องค์ประกอบเวกเตอร์ θ เจซึ่งสอดคล้องกัน θ 0 เจเรียกว่าอนุญาต; แถวและคอลัมน์ที่อยู่นั้นเรียกว่าไกด์ เวกเตอร์ในแถวไกด์จะออกจากฐาน
6. จงหาค่าสัมประสิทธิ์การขยายตัวของเวกเตอร์ทั้งหมดโดยใช้พื้นฐานใหม่ ลองใช้วิธี Giordano Gauss กัน
เรามาตรวจสอบแผนอ้างอิงที่เหมาะสมที่สุดกัน หากการประมาณการเป็นไปตามเงื่อนไขการปรับให้เหมาะสมที่สุด ปัญหาก็จะได้รับการแก้ไข หากไม่เป็นเช่นนั้น ให้ดำเนินการตามขั้นตอนที่ 5-7
2. การแนะนำตัวแปรพื้นฐานทางธรรมชาติ การสร้างโต๊ะซิมเพล็กซ์ คำจำกัดความของแผนศูนย์
วิธีซิมเพล็กซ์มีประสิทธิภาพมากที่สุดในการแก้ปัญหาที่ซับซ้อน และแสดงถึงกระบวนการวนซ้ำ (ทีละขั้นตอน) โดยเริ่มจาก ศูนย์(อ้างอิง) โซลูชัน (จุดยอด n- รูปทรงหลายเหลี่ยมมิติ) ต่อไปในการค้นหา ตัวเลือกที่ดีที่สุดแผนจะถือว่าการเคลื่อนที่ไปตามจุดมุม (จุดยอดของรูปทรงหลายเหลี่ยม) จนกระทั่งค่าของฟังก์ชันวัตถุประสงค์ถึงค่าสูงสุด (ขั้นต่ำ) ให้เราพิจารณาอัลกอริทึมของวิธีซิมเพล็กซ์โดยใช้ตัวอย่างปัญหาการวางแผนการหมุนเวียน ทรัพยากรที่จำกัดวัตถุดิบ
บริษัทจำหน่าย nกลุ่มผลิตภัณฑ์มี มวัสดุและทรัพยากรทางการเงินมีจำกัด ขฉัน ≥0 (1 ≤ ฉัน≤ ม.) ทราบต้นทุนทรัพยากรของทุกคนแล้ว ฉัน- ประเภทการผลิตและการขายหน่วยสินค้าของแต่ละกลุ่มแสดงในรูปของเมทริกซ์ ( ก ij) และกำไรที่วิสาหกิจได้รับจากการขายสินค้าหนึ่งหน่วย เจ-group รวมอยู่ในฟังก์ชั่นวัตถุประสงค์ ซี(เอ็กซ์- วิธีการเขียนโปรแกรมเชิงเส้นไม่แตกต่างจากระบบ (1) - (2):
Z(X) = с 1 Р 1 + с 2 Р 2 + с 3 Р 3 + … +с n Р n →สูงสุด(นาที) (1)
ก 11 X 1 + ก 12 X 2 +…ก 1n X n ≤ ข 1
ก 21 X 1 + ก 22 X 2 +…ก 2n X n ≤ ข 2 (2)
a m1 X 1 + a m2 X 2 +…a mn X n ≤ b m,
X 1 ≥0 X 2 ≥0 X 3 ≥0 …Xn ≥0
ขั้นตอนการแก้ปัญหาโดยใช้วิธีซิมเพล็กซ์ ได้แก่ :
1) จัดทำแผนอ้างอิงเป็นศูนย์ เราแนะนำตัวแปรที่ไม่เป็นลบ (พื้นฐาน) ใหม่ ซึ่งทำให้ระบบอสมการ (2) กลายเป็นระบบสมการ:
a 11 X 1 + a 12 X 2 +…a 1n X n + X n+1 = b 1
a 21 X 1 + a 22 X 2 +…a 2n X n + X n+2 = b 2 (3)
……………………………………..
ก m1 X 1 + ก m2 X 2 +…a mn X n + X n+m = b ม.
หากเรารับตัวแปรอินพุตเป็นเวกเตอร์คอลัมน์ มันจะเป็นตัวแทน เดี่ยว (ขั้นพื้นฐาน) เวกเตอร์ โปรดทราบว่าตัวแปรพื้นฐานมีความเรียบง่าย ความหมายทางกายภาพ- นี้ ส่วนที่เหลือทรัพยากรเฉพาะในคลังสินค้าสำหรับแผนการผลิตที่กำหนด ดังนั้นจึงเรียกว่าพื้นฐานนี้ เป็นธรรมชาติ- เราแก้ระบบ (3) ด้วยความเคารพต่อตัวแปรพื้นฐาน:
X n+1 = b 1, -a 11 X 1 - a 12 X 2 -…a 1n X n
X n+2 = b 2 - a 21 X 1 - a 22 X 2 -…a 2n X n (4)
………………………………………..
X n+m = b m, - a m1 X 1 + a m2 X 2 +…a mn X n
เราเขียนฟังก์ชันวัตถุประสงค์ใหม่ในรูปแบบ
ซี(X) = 0-(-с 1 Р 1 -с 2 Р 2 -с 3 Р 3 -…-с n Р n) (5)
สมมติว่าตัวแปรหลักที่ต้องการ X 1 = X 2 = X 3 = ... = X n = 0 เราจะได้แผนอ้างอิงที่เป็นศูนย์ X = (0, 0, ...0, b 1, b 2, b 3 ... b m) โดยที่ Z(X) = 0 (ทรัพยากรทั้งหมดในสต็อก ไม่มีการผลิตเลย) เราใส่แผนลงในตารางซิมเพล็กซ์
| วางแผน | พื้นฐาน | ซี ฉัน /ซี เจ | ความหมาย เอ็กซ์ ฉัน | เอ็กซ์ 1 | เอ็กซ์ 2 | Xn | Xn+1 | Xn+2 | Xn+3 | คิวนาที |
| Xn+1 | ข 1 | 11 | 12 | 13 | ข 1/ก 12 | |||||
| Xn+2 | ข 2 | 21 | 22 | 23 | ข 2 / ก 22 | |||||
| Xn+3 | ข 3 | 31 | 32 | 33 | ข 3 / ก 32 | |||||
| ซี(X) = 0 | -ค 1 | - ค 2 | - ค 3 | ดัชนี. เส้น |
2) จากค่าสัมประสิทธิ์ลบของเส้นดัชนี ให้เลือกค่าที่ใหญ่ที่สุด ค่าสัมบูรณ์ซึ่งกำหนดคอลัมน์นำและแสดงว่าตัวแปรใดในการวนซ้ำครั้งถัดไป (ขั้นตอน) ที่จะย้ายจากคอลัมน์หลัก (อิสระ) ไปเป็นคอลัมน์พื้นฐาน (อันที่จริง กลุ่มผลิตภัณฑ์จะถูกเลือกซึ่งยอดขายนำมาซึ่ง รายได้สูงสุด- จากนั้นเราแบ่งปริมาณสำรองของวัตถุดิบ b i ด้วยค่าสัมประสิทธิ์ต้นทุนที่สอดคล้องกันป้อนผลลัพธ์ลงในตารางและกำหนดค่าขั้นต่ำ Q นาที (เลือกทรัพยากรที่มีการสำรองอย่างเข้มงวดที่สุดซึ่งจำกัดผลลัพธ์ของกลุ่มผลิตภัณฑ์ที่เลือก) ค่านี้จะเลือกเส้นนำและตัวแปร Xi ซึ่งในขั้นตอนถัดไป (การวนซ้ำ) จะออกจากพื้นฐานและกลายเป็นอิสระ
3) การเปลี่ยนไปใช้แผนใหม่ดำเนินการอันเป็นผลมาจากการคำนวณตารางซิมเพล็กซ์ใหม่โดยใช้วิธี Jordan-Gauss ขั้นแรก เราแทนที่ X j ในฐานด้วย X i ของคอลัมน์นำหน้า ให้เราแบ่งองค์ประกอบทั้งหมดของเส้นนำด้วยองค์ประกอบการแก้ไข (RE) ซึ่งเป็นผลมาจากการที่ตำแหน่งของ RE ในเส้นนำจะเป็น 1 เนื่องจาก X i กลายเป็นพื้นฐาน ค่าสัมประสิทธิ์ที่เหลือจะต้องเท่ากับ 0. พบองค์ประกอบใหม่ของแผนนี้ตามกฎรูปสี่เหลี่ยมผืนผ้า
NE=SE – (A*B)/RE (6)
แผนผลลัพธ์จะได้รับการประเมินโดยใช้ค่าสัมประสิทธิ์ของเส้นดัชนี: หากเป็นบวกทั้งหมด แสดงว่าแผนนั้นเหมาะสมที่สุด หากไม่ สามารถปรับปรุงแผนได้โดยดำเนินการวนซ้ำครั้งถัดไป (ขั้นตอน)
ตัวอย่าง.มีการจัดสรรเงิน 20,000 รูเบิลสำหรับการซื้ออุปกรณ์สำหรับสถานที่ผลิต สามารถวางอุปกรณ์ได้บนพื้นที่ไม่เกิน 72 ตร.ม. สามารถสั่งอุปกรณ์ได้ 2 แบบ คือ แบบ A ต้องการพื้นที่การผลิต 6 ตร.ม. และจำนวน 6 พันยูนิต สินค้าต่อกะ (ราคา 5,000 รูเบิล) และประเภท B ต้องการพื้นที่ 12 ตร.ม. และผลิตได้ 3,000 หน่วย (ราคา 2,000 รูเบิล) แผนการซื้ออุปกรณ์ที่เหมาะสมที่สุดเพื่อให้แน่ใจว่าคืออะไร ประสิทธิภาพสูงสุดพล็อต?
ให้เราแสดงปริมาณของอุปกรณ์ที่ซื้อประเภท A และ B ด้วย X 1 และ X 2 ตามลำดับ
ผลผลิตของไซต์งาน (ฟังก์ชันวัตถุประสงค์): Z(X) =6X 1 +3X 2
ข้อจำกัดหลักมีความเกี่ยวข้องกัน
ด้วยเงินสด: 5X 1 +2X 2 ≤ 20,
โดยมีพื้นที่ไซต์การผลิต: 6H 1 +12H 2 ≤ 72
เราแนะนำตัวแปรพื้นฐานใหม่ X 3 (ส่วนที่เหลือ เงินสดหลังจากซื้ออุปกรณ์) และ X 4 (พื้นที่คงเหลือหลังการจัดวางอุปกรณ์) และเขียนข้อจำกัดใหม่ในรูปแบบของระบบสมการ:
5X 1 +2X 2 +X 3 =20 (X 3 =20 – 5X 1 - 2X 2)
6X 1 +12X 2 +X 4 = 72 (X 4 =72 – 6X 1 – 12X 2)
ในกรณีนี้ ฟังก์ชันเป้าหมาย: Z(X) = 6X 1 +3X 2 +0X 3 +0X 4
เราจัดทำแผนอ้างอิง (ที่ 0): X = (0, 0, 20, 72) เช่น ยังไม่ได้ซื้ออะไรเลย (ยังไม่มีการใช้เงิน พื้นที่ว่างเปล่า) การทำตารางซิมเพล็กซ์
| วางแผน | พื้นฐาน | ซี ฉัน /ซี เจ | ความหมาย เอ็กซ์ ฉัน | เอ็กซ์ 1 | เอ็กซ์ 2 | เอ็กซ์ 3 | เอ็กซ์ 4 | คิวนาที | |||
| เอ็กซ์ 3 | 20/5=4 | ||||||||||
| เอ็กซ์ 4 | 72/6=12 | ||||||||||
| ซี(X) = 0 | - 6 | - 3 | เส้นดัชนี | ||||||||
| →เอ็กซ์ 1 | 0,4 | 0,2 | 4/0,4=10 | ||||||||
| เอ็กซ์ 4 | 9,6 | -1,2 | 48/9,6=5 | ||||||||
| Z(X) = 6*4=24 | -0,6 | 1,2 | เส้นดัชนี | ||||||||
| เอ็กซ์ 1 | 0,25 | -1/24 | - | ||||||||
| →เอ็กซ์ 2 | -1/8 | 5/48 | - | ||||||||
| Z(X) =6*2+3*5=27 | 9/8 | 1/16 | เส้นดัชนี | ||||||||
แน่นอนว่าคอลัมน์นำหน้าสอดคล้องกับ X 1 เนื่องจากมีดัชนีที่ใหญ่ที่สุด 6 เราค้นหาค่าต่ำสุดของ Q min = 4 (ข้อจำกัดด้านทรัพยากรที่รุนแรงที่สุด) โดยการกำหนดแถวนำที่แสดงว่า X 3 ได้มาจากตัวแปรพื้นฐาน และ X จะถูกป้อนแทน 1 เราคำนวณองค์ประกอบของเส้นนำหน้าใหม่โดยหารด้วย 5 และใช้สูตร (6) เพื่อกำหนดองค์ประกอบของเส้นที่สองและเส้นดัชนี ฟังก์ชันวัตถุประสงค์ของแผนที่ 1 เท่ากับ Z(X) = 6*4+3*0 = 24
อย่างไรก็ตาม ค่าสัมประสิทธิ์หนึ่งของแถวดัชนีสำหรับคอลัมน์ X 2 ยังคงเป็นลบ -0.6 ดังนั้น แผนนี้ไม่เหมาะสมและจำเป็นต้องทำซ้ำ (ขั้นตอน) อื่นเพื่อปรับปรุง เลือกคอลัมน์ที่ 2 เป็นผู้นำและ ค่าต่ำสุด Q min = 5 เรากำหนดเส้นนำด้วยตัวแปรพื้นฐาน X 4 เมื่อทำการแปลงแบบเดียวกันแล้วเราได้แผนที่ 2 ซึ่งจะเหมาะสมที่สุดเนื่องจากค่าสัมประสิทธิ์ดัชนีทั้งหมดเป็นค่าบวก
มาวิเคราะห์ผลลัพธ์ที่ได้รับ ที่ ทางออกที่ดีที่สุดฟังก์ชันวัตถุประสงค์มี ค่าสูงสุด 27,000 รูเบิล ในขณะที่ทรัพยากรทั้งสองถูกลบออกจากฐานดังนั้นจึงใช้ไปจนหมด
ตรวจสอบให้แน่ใจ: 5*2+2*5 = 20,000 รูเบิล 6*2+12*5=72 ตร.ม. วิธีแก้ไขที่ต้องการคือ X = (2; 5;0;0) สิ่งนี้ไม่ได้เกิดขึ้นเสมอไป
การบรรยายครั้งที่ 10
หัวข้อ: วิธี Simplex สำหรับปัญหาพื้นฐานเทียม
วิธีการแก้ปัญหาแบบซิมเพล็กซ์นั้นขึ้นอยู่กับการแนะนำตัวแปร (พื้นฐาน) เพิ่มเติมที่ทำให้สามารถสร้างเมทริกซ์หน่วยได้ หากข้อจำกัดของปัญหาแสดงอยู่ในรูปแบบของความไม่เท่าเทียมกัน:
i1 X 1 + i2 X 2 +…a ใน X n ≥ b i (1)
หรือสมการ:
i1 X 1 + i2 X 2 +…a ใน X n = b i (1*)
จึงไม่สามารถรับแผนอ้างอิงในรูปแบบที่ต้องการได้ ในกรณีนี้ เราขอแนะนำเพื่อให้สอดคล้องกับความเท่าเทียมกัน (1*) พื้นฐานเทียม ย i และตัวแปรประดิษฐ์ไม่เกี่ยวข้องโดยตรงกับเนื้อหาของงาน แต่ทำให้สามารถสร้างแผนอ้างอิง (เริ่มต้น):
i1 X 1 + i2 X 2 +…a ใน X n +Y i = b i (2)
ฟังก์ชันวัตถุประสงค์เมื่อแก้ไขปัญหาให้สูงสุดจะถูกเขียนในรูปแบบ:
Z(X) =∑C เจ X เจ +(-M)∑Y ผม (3)
เมื่อแก้ไขปัญหาที่คล้ายกันอย่างน้อยที่สุด:
Z(X)=∑C เจ X เจ +(M)∑Y ผม (3*)
โดยที่ M มีขนาดใหญ่มาก จำนวนบวกซึ่งเป็นบทลงโทษสำหรับการใช้ตัวแปรเทียม
ในกรณีของความไม่เท่าเทียมกัน (1) ในตอนแรกเราจะแนะนำตัวแปรเพิ่มเติม X n + i ด้วยเครื่องหมายลบ เมทริกซ์ของพวกมันจะไม่รวมกัน ดังนั้นในแต่ละความไม่เท่าเทียมกันของระบบ (1) เราจึงแนะนำตัวแปรเทียม У i:
i1 X 1 +a i2 X 2 +…a ใน X n –X n+i +Y i =b i (4)
ฟังก์ชันวัตถุประสงค์ในกรณีนี้คือ Z(X)=∑C j X j +0∑X n + i +(-M)∑Y i (เพื่อหาค่าสูงสุด) การใช้พื้นฐานเทียมทำให้วิธีซิมเพล็กซ์มีความยืดหยุ่นมากขึ้น และช่วยให้นำไปใช้กับปัญหาได้หลากหลาย
ตัวอย่าง . กำหนดค่ากำไรสูงสุดและต่ำสุดสำหรับการผลิตผลิตภัณฑ์ A และ B สองประเภทหากระบุต้นทุนการผลิตและความสามารถในการทำกำไรจากการขายหน่วยผลิตภัณฑ์ไว้ในตาราง เงื่อนไขหลักคือการจ้างคนงานในองค์กรอย่างเต็มรูปแบบ
ในทางคณิตศาสตร์ ข้อจำกัดผลผลิตจะถูกเขียนในรูปแบบของระบบผสม:
1X 1 + 1X 2 ≤ 6,
2X 1 + 1X 2 =8
ให้เราแนะนำตัวแปรพื้นฐาน X 3 สำหรับอสมการแรก และตัวแปรเทียม Y 1 สำหรับสมการที่สอง:
1X 1 + 1X 2 + X 3 = 6
2X 1 + 1X 2 +Y 1 =8
ให้เราแสดง X 3 และ Y 1 จากระบบสมการผลลัพธ์ และเพื่อกำหนดค่าสูงสุด ลองจินตนาการถึงฟังก์ชันวัตถุประสงค์:
Z(X)= 3X 1 + 2X 2 +0X 3 –MY 1 = 3X 1 + 2X 2 –M(8 -2X 1 –X 2)=
3X 1 + 2X 2 –8M +2MX 1 + MX 2 = (2M + 3)X 1 + (M + 2)X 2 -8M
สำหรับแผนอ้างอิง - X=(0,0,6,8) มาสร้างตาราง Simplex กันดีกว่า:
| วางแผน | พื้นฐาน | ซี ฉัน /ซี เจ | ความหมาย เอ็กซ์ ฉัน | เอ็กซ์ 1 | เอ็กซ์ 2 | เอ็กซ์ 3 | ใช่ 1 | คิวนาที |
| เอ็กซ์ 3 | 6/1=6 | |||||||
| ใช่ 1 | -ม | 8/2=4 | ||||||
| ซี(X) = -8M | -2M-3 | -เอ็ม-2 | เส้นดัชนี | |||||
| เอ็กซ์ 3 | 0,5 | -0,5 | 2/0,5=4 | |||||
| →เอ็กซ์ 1 | 0,5 | 0,5 | 4/0,5=8 | |||||
| Z(X) = 3*4=12 | - 0,5 | ม+1.5 | เส้นดัชนี | |||||
| →เอ็กซ์ 2 | -1 | - | ||||||
| เอ็กซ์ 1 | -1 | - | ||||||
| Z(X) =3*2+2*4=14 | ม+1 | เส้นดัชนี |
ตามกฎแล้ว การปรับปรุงแผนอ้างอิงเริ่มต้นด้วยการลบตัวแปรเทียม Y 1 ออกจากพื้นฐาน ได้รับแผนที่เหมาะสมที่สุด X = (2,4,0,0) ในการวนซ้ำครั้งที่สอง โดยมีรายได้สูงสุด 14 พัน. ถู. และค่าสัมประสิทธิ์ของแถวดัชนีไม่เป็นลบ เป็นเรื่องง่ายที่จะตรวจสอบว่าในงานนี้ ด้วยแผนที่เหมาะสมที่สุด ทรัพยากรจะถูกใช้อย่างเต็มที่ (2*1+4*1=6; 2*2+1*4=8)
เมื่อค้นหาความสามารถในการทำกำไรขั้นต่ำ เราจะกำหนดฟังก์ชันวัตถุประสงค์ให้แตกต่างออกไป (+MY 1 จะถูกป้อนเป็นคำ:
Z(X)= 3X 1 + 2X 2 +0X 3 +MY 1 = 3X 1 + 2X 2 +M(8 -2X 1 –X 2)=
3X 1 + 2X 2 +8M - 2MX 1 - MX 2 = (3 - 2M)X 1 + (2 - M)X 2 +8M
แผนพื้นฐานเหมือนกัน แต่ค่าสัมประสิทธิ์แถวดัชนีในตารางซิมเพล็กซ์จะแตกต่างกัน คอลัมน์นำหน้าเหมือนเมื่อก่อนถูกเลือกโดยคอลัมน์ที่ใหญ่ที่สุด ค่าสัมบูรณ์สัมประสิทธิ์เชิงบวกสำหรับ X 1 แถวนำถูกกำหนดโดยค่าต่ำสุดของ Q min = 4 ในการวนซ้ำครั้งแรก ตัวแปรเทียม Y 1 จะได้มาจากพื้นฐาน
| วางแผน | พื้นฐาน | ซี ฉัน /ซี เจ | ความหมาย เอ็กซ์ ฉัน | เอ็กซ์ 1 | เอ็กซ์ 2 | เอ็กซ์ 3 | ใช่ 1 | คิวนาที | ||
| เอ็กซ์ 3 | 6/1=6 | |||||||||
| ใช่ 1 | ม | 8/2=4 | ||||||||
| Z(X) = 8M | 2M-3 | เอ็ม-2 | เส้นดัชนี | |||||||
| เอ็กซ์ 3 | 0,5 | -0,5 | 2/0,5=4 | |||||||
| →เอ็กซ์ 1 | 0,5 | 0,5 | 4/0,5=8 | |||||||
| Z(X) = 3*4=12 | - 0,5 | -ม+1.5 | เส้นดัชนี | |||||||
ผลลัพธ์ที่เป็นลบของค่าสัมประสิทธิ์ในเส้นดัชนี X i บ่งบอกถึงความเหมาะสมของแผนที่ 1 โดยมีรายได้ขั้นต่ำ 12,000 รูเบิล
ได้มาจากผลผลิตของผลิตภัณฑ์ A เท่านั้น (ไม่ได้ผลิตผลิตภัณฑ์ B) วัตถุดิบไม่ได้ใช้อย่างเต็มที่ (ส่วนที่เหลือ X 3 = 2t) ในขณะที่ตรงตามเงื่อนไขหลัก - คนงานถูกใช้อย่างเต็มที่ในการผลิต
การบรรยายครั้งที่ 11
หัวข้อ: ปัญหาการขนส่งแบบปิด
1. สูตรทางคณิตศาสตร์ของปิด ปัญหาการขนส่ง- การกำหนดจำนวนสิ่งที่ไม่ทราบที่ต้องการ
2. ขั้นตอนการกำหนดแผนการแก้ไขปัญหาการขนส่ง
