Linear Programming (LP): บันทึกการศึกษา

ในบทความนี้เราจะหารือเกี่ยวกับการเขียนโปรแกรมเชิงเส้น (LP): - 1. แนวคิดของการเขียนโปรแกรมเชิงเส้น 2. การ ประยุกต์ใช้การเขียนโปรแกรมเชิงเส้น 3. ข้อสันนิษฐานของการเขียนโปรแกรมเชิงเส้นแบบ 4. สูตร

แนวคิดของการเขียนโปรแกรมเชิงเส้น:

การเขียนโปรแกรมเชิงเส้น (LP) เป็นเทคนิคการเพิ่มประสิทธิภาพทางคณิตศาสตร์ที่ใช้กันอย่างแพร่หลายซึ่งได้รับการพัฒนาในปี 1947 โดย George B. Dantzig สำหรับการแก้ปัญหาการวางแผนของกองทัพอากาศสหรัฐ แม้ว่าคอมพิวเตอร์ 'การเขียนโปรแกรม' ไม่เกี่ยวข้องกับ LP แต่การพัฒนาคอมพิวเตอร์มีส่วนสำคัญอย่างยิ่งต่อความสำเร็จของ LP

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

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

การแสดงออกเชิงพีชคณิตของวัตถุประสงค์เรียกว่าฟังก์ชันวัตถุประสงค์ซึ่งจะต้องเป็นเส้นตรง

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

ปัญหาที่เกิดขึ้นเมื่อสูตรสามารถแก้ไขได้โดยใช้เทคนิคที่แตกต่างกันจำนวนหนึ่งซึ่ง 'Graphical Solution' และ 'Simplex Method' เป็นที่นิยมมาก

การประยุกต์ใช้โปรแกรมเชิงเส้น :

การตัดสินใจทางเศรษฐกิจและธุรกิจมักเกี่ยวข้องกับการจัดสรรทรัพยากรที่หายากเช่นวัตถุดิบเงินเวลาพื้นที่ผู้คนและอื่น ๆ ในโครงการที่แข่งขันกันเพื่อให้บรรลุวัตถุประสงค์สูงสุดเช่นผลผลิตผลลัพธ์ผลตอบแทนจากการลงทุนส่วนแบ่งการตลาด ฯลฯ หรือลดวัตถุประสงค์บางอย่างเช่นต้นทุนขยะมลพิษ ฯลฯ สามารถใช้ LP เพื่อแก้ไขปัญหาการปฏิบัติของอุตสาหกรรมต่อไปนี้:

ผม. ปัญหาส่วนผสมของผลิตภัณฑ์ :

ส่วนผสมผลิตภัณฑ์ที่เหมาะสมที่จะผลิตด้วยกำลังคนที่ขาดแคลนของ บริษัท กำลังการผลิตวัตถุดิบวัตถุดิบการเงิน ฯลฯ สามารถวิเคราะห์และแก้ไขได้โดย LP ให้เรานำโรงงานแปรรูปอาหารที่ผลิตผลิตภัณฑ์มะเขือเทศเช่นมะเขือเทศตุ๋นมะเขือเทศวาง ซุปมะเขือเทศซอสมะเขือเทศน้ำมะเขือเทศมะเขือเทศกระป๋อง ฯลฯ

มันสามารถผลิตผลิตภัณฑ์ใด ๆ หรือทั้งหมดพร้อมกัน แต่มีการ จำกัด ของมะเขือเทศเวลา / แรงงานน้ำตาลและอื่น ๆ

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

ii ปัญหาอาหาร :

อาหารสัตว์นั้นผลิตขึ้นจากการผสมส่วนผสมหลายอย่างซึ่งแต่ละอย่างมีสัดส่วนโปรตีนวิตามินแร่ธาตุต่าง ๆ ฯลฯ อาหารสัตว์ที่ผลิตต้องมีระดับโภชนาการที่แน่นอนตามที่รัฐบาลกำหนดในราคาต่ำสุด

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

สาม. การจัดสรรงบประมาณโฆษณา :

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

iv การเลือกกระบวนการ :

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

v. ปัญหาการกระจาย :

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

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

vi ปัญหาการแปรรูปน้ำมันและการขนส่ง :

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

ปกเกล้าเจ้าอยู่หัว ปัญหาการกำหนดบุคลากร :

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

viii การวางแผนความจุระยะยาวสำหรับอุปกรณ์ไฟฟ้า :

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

โมเดลนี้ใช้งานง่ายผู้ใช้สามารถใช้เพื่อแก้ไขปัญหาได้อย่างรวดเร็ว นอกจาก LP เหล่านี้สามารถนำไปใช้กับด้านอื่น ๆ ของการตัดสินใจ

สมมติฐานของโมเดลการเขียนโปรแกรมเชิงเส้น :

แบบจำลอง LP ยึดตามสมมติฐานดังต่อไปนี้

1. จะต้องมีวัตถุประสงค์ที่ บริษัท ต้องการเพิ่มหรือย่อเล็กสุด ฟังก์ชันวัตถุประสงค์ (พีชคณิต) จะต้องเป็นเส้นตรง หลายวัตถุประสงค์อาจรวมอยู่ในการวิเคราะห์

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

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

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

การกำหนดปัญหาการโปรแกรมเชิงเส้น :

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

ต้องสร้างกล่อง A และ B กี่กล่องเพื่อให้ได้ผลงานสูงสุด

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

ปัญหาที่ 1:

ให้ x 1 = จำนวนของประเภทกล่อง, x 2 = จำนวนของประเภทกล่อง B ฟังก์ชันวัตถุประสงค์เพิ่มสูงสุด Z = 30x 1 + 20x 2 โดยที่ Z แทนกำไรและ 30 และ 20 คือการสนับสนุนกล่องประเภท A และ Type B ตามลำดับ

ขั้นตอนต่อไปในการกำหนดปัญหาคือการระบุข้อ จำกัด เมื่อ x 1 และ x 2 ใช้เวลา 3 นาที สำหรับการเชื่อมและจำนวนนาทีที่มีทั้งหมด ในแผนกการเชื่อมคือ 60 นาที. สมการที่ขัดแย้งจะเป็นดังนี้:

3x 1 + 3x 2 ≤ 60 (แผนกเชื่อม)

เช่นจำนวนนาทีทั้งหมด จำเป็นสำหรับการผลิต x 1 และ

x 2 boxes ควรน้อยกว่าหรือเท่ากับ 60 นาที

ในทำนองเดียวกันสมการข้อ จำกัด อื่น ๆ คือ:

หากมีเพียงสองตัวแปรปัญหาสามารถแก้ไขได้ด้วยวิธีกราฟิกอย่างง่าย ในกรณีที่เกี่ยวข้องกับตัวแปรมากกว่าสองตัวเราจะใช้ 'วิธี Simplex'

โซลูชันกราฟิก (การขยายให้ใหญ่สุด) :

ให้เราแก้ปัญหาแบบกราฟิก ตัวแปรการตัดสินใจมีเพียงสองตัวเท่านั้นนั่นคือ x 1 และ x 2 เกี่ยวข้อง ตัวแปรเหล่านี้ถูกพล็อตตามแกน x (แนวนอน) และแกน y (แนวตั้ง)

ในการพล็อตข้อ จำกัด บนกราฟสิ่งเหล่านี้จะแสดงในรูปของสมการต่อไปนี้:

3x 1 + 3x 2 = 60 (1)

6x 1 + 2x 2 = 60 (2)

8x 1 = 60 (3)

ตอนนี้ OABCD ในรูปที่ 5.1 เป็นพื้นที่นูนและจุดใน O, A, B, C, D เรียกว่าทางออกที่เป็นไปได้สำหรับปัญหา LP มีทฤษฎีบทพื้นฐานของ LP ซึ่งระบุว่าฟังก์ชันวัตถุประสงค์ได้รับการปรับให้เหมาะสมที่จุดใดมุมหนึ่งเช่น O, A, B, C, D ดังนั้นเพื่อผลกำไรสูงสุดเฉพาะจุดมุมเหล่านี้หรือที่เรียกว่าการแก้ปัญหาที่เป็นไปได้ขั้นพื้นฐานเท่านั้นที่จะได้รับการประเมิน

คะแนนยังสามารถได้รับโดยตรงจากกราฟ

ที่นี่ Z = Rs 450 (สูงสุดที่ B เมื่อ x 1 = 5 และ x 2 = 15)

วิธีการทางเลือกอื่นสำหรับการได้รับโซลูชันที่เป็นไปได้ขั้นพื้นฐานจะแสดงในรูปที่ (5.2) ซึ่งเหมือนกับมะเดื่อ (5.1) ที่มีจุด iso-profit หลายจุดเช่น L 1 L 1, L 2 L 2, L 3 L 3, ฯลฯ บรรทัด iso-profit เป็นการนำเสนอแบบกราฟิกของชุดค่าผสมที่เป็นไปได้ทั้งหมดของผลิตภัณฑ์สองชนิดที่ให้เหมือนกัน กำไร. นี่คือเส้นขนานที่มีความชันเท่ากัน อาจมีจำนวนบรรทัดดังกล่าวไม่ จำกัด ยิ่งบรรทัด iso-profit จากจุดเริ่มต้นมากเท่าไหร่ก็ยิ่งได้กำไรมากขึ้นเท่านั้น

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

Z = 30x 1 + 20x 2 (ฟังก์ชันวัตถุประสงค์) คือสมการเชิงเส้นของระดับแรก หากเราใช้ค่าต่าง ๆ ของ Z เช่น 150, 300, 600 เป็นต้นและพล็อตพวกมันบนกราฟเส้นจะขนานกัน

L 1 L 1, L 2 L 2, L 3 L 3, เป็นเส้น iso-profit L 3 L 3 สัมผัสกับพื้นที่โซลูชัน 0ABCD ณ จุดใดจุดหนึ่งเช่น B (5, 15)

. . . Z = อาร์เอส 450 (กำไรที่เหมาะสมที่สุด) และ x 1 = 5 และ x 2 = 15 (ส่วนผสมที่เหมาะสม)

โซลูชันกราฟิค: การย่อขนาด :

ให้เราคุยเกี่ยวกับปัญหาการย่อเล็กสุด

ปัญหาที่ 2

คนต้องการสารเคมี A, B และ C 10, 12 และ 12 หน่วยตามลำดับสำหรับสวนของเขา ผลิตภัณฑ์ที่เป็นของเหลวประกอบด้วย 5, 2 และ 1 ของ A, B และ C ตามลำดับต่อขวด ผลิตภัณฑ์แบบแห้งประกอบด้วย 1, 2 และ 4 หน่วยของ A, B และ C ต่อกล่อง ถ้าผลิตภัณฑ์ของเหลวขายสำหรับ Rs 3 ต่อขวดและผลิตภัณฑ์แห้งขายสำหรับ Rs 2 ต่อกล่องควรซื้อกี่กล่องเพื่อลดต้นทุนและตอบสนองความต้องการ?

วิธีการแก้:

ให้ x 1 = หน่วยของผลิตภัณฑ์ของเหลวที่ซื้อและ x 2 = หน่วยของผลิตภัณฑ์แห้งที่ซื้อ

ฟังก์ชั่นวัตถุประสงค์จะกลายเป็น:

ย่อ Z = 3x 1 + 2x 2 (1)

ภายใต้ข้อ จำกัด ดังต่อไปนี้

ในการพล็อตข้อ จำกัด บนกราฟสิ่งเหล่านี้จะแสดงในรูปของสมการต่อไปนี้:

ที่นี่พื้นที่การแก้ปัญหาอยู่เหนือเส้น (2) ', (3)' และ (4) 'ดังที่แสดงโดยพื้นที่แรเงาในรูปที่ (5.3)

ต่อไปเราย้ายบรรทัด iso-profit ไปยังจุดกำเนิดจนถึงจุดสุดท้ายบนขอบเขตของพื้นที่การแก้ปัญหาคือ B (ที่นี่)

พิกัดของ B สามารถหาได้โดยการแก้สมการ (2) 'และ (3)' ดังต่อไปนี้:

ตอนนี้ Z ต่ำสุดที่ B = 3 X 1 + 2 X 5 = Rs 13. พิกัดของ B สามารถรับได้จากกราฟโดยตรง

วิธี Simplex :

ปัญหา LP ที่ซับซ้อนไม่สามารถแก้ไขได้ด้วยโซลูชั่นกราฟิก สำหรับปัญหาดังกล่าวเราใช้วิธี simplex ให้เราคุยเกี่ยวกับปัญหาการขยายให้ง่ายที่สุด

ปัญหาที่ 1

บริษัท ผู้ผลิต ABC สามารถสร้างผลิตภัณฑ์สองตัว P 1 และ P 2 แต่ละผลิตภัณฑ์ต้องใช้เวลากับ 'เครื่องตัดและเครื่องตกแต่ง

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

วิธีการแก้:

ปล่อย

x 1 = ผลลัพธ์ของผลิตภัณฑ์ P 1 ;

x 2 = ผลผลิตของผลิตภัณฑ์ P 2 ;

x 3 = ตัวแปรหย่อนคือเวลาตัดที่ไม่ได้ใช้

x 4 = ตัวแปร Slack คือชั่วโมงการตกแต่งที่ไม่ได้ใช้

และ

Z = กำไรที่เหมาะสมที่สุด

ตอนนี้ฟังก์ชั่นวัตถุประสงค์จะกลายเป็น: ขยายใหญ่สุด Z = 6x 1 + 4x 2 + 0x 3 + 0x 4 ภายใต้ข้อ จำกัด :

เนื่องจากค่าทั้งหมดของ (C j - Z j ) เช่นแถวดัชนีของ Pass II เป็นศูนย์หรือเชิงลบจึงได้คำตอบที่เหมาะสม

ผู้ผลิตจะต้องผลิตสินค้า 120 หน่วยต่อสัปดาห์และ 150 หน่วยต่อสัปดาห์ของ P 1 และ P 2 ตามลำดับเพื่อให้ได้ผลงานสูงสุดเช่น Rs 1320

การคำนวณ :

กระบวนการคำนวณดังต่อไปนี้ไม่กี่ขั้นตอน เหล่านี้อธิบายไว้ด้านล่าง

ตารางเริ่มต้น :

ใส่ rhs ของสมการ (2) และ (3) ใน CC 'และ DC' กำลังสองตามลำดับ ใส่สัมประสิทธิ์ x 1, x 2, x 3 และ x 4 ในสมการ (2) ใน CD ', CE', CF 'และ CG' กำลังสองตามลำดับ ในทำนองเดียวกันให้ใส่สัมประสิทธิ์ x 1, x 2, x 3 และ x 4 ในสมการ (3) ใน DD ', DE', DF 'และ DG' สแควร์ตามลำดับ ใส่ตัวแปร slack, x 3 และ x 4, และการมีส่วนร่วมของพวกเขา 0 และ 0 ตามที่แสดงในสมการ (1) ใน CB ', DB', CA 'และ DA' กำลังสองตามลำดับ

การคำนวณแถว Z j

EC 'square = 390 x 0 + 810 x = 0

ED 'square = 2 x 0 + 3 x 0 = 0 และต่อไปเรื่อย ๆ

การคำนวณแถว C j - Z j

FD 'square = 6 - 0 = 6 (เช่น AD' - FD ')

FE 'square = 4 - 0 = 4 เป็นต้น

ผ่านการคำนวณ:

การคำนวณผ่านครั้งที่สอง:

คล้ายกับ Pass I

แถวดัชนี (เช่น C j - Z j ) ใน Pass II สำหรับตัวแปรหย่อนคือ X 3 และ X 4 มีการตีความทางเศรษฐกิจที่สำคัญ ค่าสัมบูรณ์ของพวกเขาคือ 2 และ 2/3 ที่นี่แสดงจำนวนการเปลี่ยนแปลงในมูลค่าที่เหมาะสมของฟังก์ชันวัตถุประสงค์ซึ่งจะเกิดขึ้นจากการผ่อนคลายข้อ จำกัด ที่เกี่ยวข้องโดยหนึ่งหน่วย

ค่านี้เรียกว่า 'ราคาเงา' ดังนั้นเราสามารถพูดได้ว่าถ้ามีเวลาตัดอีกหนึ่งชั่วโมง บริษัท ผู้ผลิต ABC สามารถเพิ่มผลกำไรด้วย Rs 2 คือราคาเงาสำหรับเวลาตัดคือ Rs 2. ในทำนองเดียวกันราคาเงาสำหรับเวลาจบคือ Rs 2/3

ลักษณะเพิ่มเติมของวิธีการ Simplex :

วิธี Big-M :

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

ปัญหาที่ 1:

เพิ่มฟังก์ชั่นกำไรสูงสุดและแสดงความคิดเห็นของคุณ:

วิธีแก้ปัญหา :

ขอแนะนำตัวแปรสแล็ก x 4 และ x 5 และตัวแปรประดิษฐ์ x 6 เรามีฟังก์ชั่นวัตถุประสงค์:

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

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

ตอนนี้ดูตาราง 5.2 เนื่องจากค่าทั้งหมดของดัชนีแถวสุดท้าย (C j - Z j ) เป็นลบหรือเป็นศูนย์จึงได้คำตอบที่เหมาะสม

. . . x 1 = 900, x 2 = 1, 000, x 3 = 0 และ Z (สูงสุด = 62, 400

การคำนวณคล้ายกับปัญหาก่อนหน้า

ปัญหาที่ 2

ใช้วิธี Big-M เพื่อขยาย Z = 6x 1 + 4x2 ให้อยู่ภายใต้ข้อ จำกัด

ให้โซลูชันที่แตกต่างกันสองวิธีถ้าโซลูชันไม่ซ้ำกัน

วิธีการแก้:

แนะนำตัวแปรสแล็ก x 3 และ x 4, ตัวแปรส่วนเกิน x 5 และตัวแปรประดิษฐ์ x 6 เราได้รับข้อ จำกัด ดังนี้

และฟังก์ชั่นวัตถุประสงค์คือ: ขยาย Z = 6x 1 + 4x 2 + 0x 3 + 0x 4 + 0x 5 - Mx 6

รับวิธีแก้ปัญหาโดยกำจัด big-M

ปัญหาการลดขนาด :

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

ย่อเล็กสุด Z = - ย่อเล็กสุด (-Z)

ต่อไปเราจะเพิ่ม (-Z) เหมือนก่อนและรับค่าลบของการเพิ่ม (-Z)

ปัญหาที่ 3

ใช้วิธี Big-M เพื่อย่อขนาด Z = 15x 1 + 12x 2 ภายใต้ข้อ จำกัด :

วิธีการแก้:

ขอแนะนำตัวแปรส่วนเกิน x 3 และ x 4 และตัวแปรประดิษฐ์ x 5 และ x 6 เราได้รับ

ย่อ Z = 15x 1 + 12x 2 + 0x 3 + 0x 4 + Mx 5 + Mx 6

ภายใต้ข้อ จำกัด

ตอนนี้ย่อขนาดเล็กสุด Z = - ย่อเล็กสุด (-Z) ที่นี่สูงสุด (-Z) = -15x 1 - 12x 2 - 0x 3 - 0x 4 - Mx 5 - Mx 6

จากนั้นใช้วิธี Big-M เพื่อแก้ปัญหาการขยายสูงสุด (-Z) ค่าที่เหมาะสมของการย่อขนาด Z = ค่าลบของการเพิ่ม (-Z)

แบบจำลองทางคณิตศาสตร์ทั่วไปของแบบจำลอง LP :

คู่ :

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

ความสัมพันธ์ระหว่าง Primal และ Dual :

ปัญหาที่ 1

ปัญหาปฐม:

สูงสุด z = 60x 1 + 80x 2

ในทั้งสองกรณี z (สูงสุด) = α (ขั้นต่ำ) y 1 และ y 2 เป็นตัวแปร 'คู่' เราสามารถแก้ปัญหา 'คู่' โดยใช้วิธีกราฟิคหรือซิมเพล็กซ์

การวิเคราะห์ความไว :

หลังจากได้รับการแก้ปัญหาที่ดีที่สุดของปัญหา LP เราอาจศึกษาการเปลี่ยนแปลงในการแก้ปัญหาที่เหมาะสมกับการเปลี่ยนแปลงในพารามิเตอร์ของปัญหา

การเปลี่ยนแปลงต่อไปนี้สามารถทำได้:

(1) เปลี่ยนค่าสัมประสิทธิ์ของฟังก์ชันวัตถุประสงค์

(2) เปลี่ยน co-efficient ของตัวแปรใน lhs ของข้อ จำกัด

(3) เปลี่ยนตัวเลขบน rhs ของข้อ จำกัด

(4) เพิ่ม / ลบตัวแปรใหม่และ

(5) เพิ่ม / ลบข้อ จำกัด ฯลฯ

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

การศึกษาปัญหา LP นี้เรียกว่า "การวิเคราะห์ความไว" การวิเคราะห์ส่วนใหญ่กระทำโดยใช้รหัสคอมพิวเตอร์ เราควรจะสามารถตีความผลลัพธ์จากรหัสดังกล่าวเช่นรหัส LPGOGO เป็นต้น

 

แสดงความคิดเห็นของคุณ