การประยุกต์ใช้โปรแกรมเชิงเส้น (พร้อมไดอะแกรม)

บทความที่กล่าวถึงด้านล่างให้ภาพรวมเกี่ยวกับการประยุกต์ใช้การเขียนโปรแกรมเชิงเส้นกับทฤษฎีของ บริษัท

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

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

ข้อสมมติฐาน :

การวิเคราะห์การเขียนโปรแกรมเชิงเส้นของ บริษัท จะขึ้นอยู่กับสมมติฐานดังต่อไปนี้

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

(2) ถือว่ากระบวนการผลิตทางเลือกมีจำนวน จำกัด

(3) ถือว่าความสัมพันธ์เชิงเส้นตรงระหว่างตัวแปรที่แตกต่างกันซึ่งแสดงถึงสัดส่วนคงที่ระหว่างอินพุตและเอาต์พุตภายในกระบวนการ

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

(5) ข้อสันนิษฐานของการเพิ่มเติมยังรองรับเทคนิคการเขียนโปรแกรมเชิงเส้นซึ่งหมายความว่าทรัพยากรทั้งหมดที่ใช้โดย บริษัท ทั้งหมดจะต้องเท่ากับผลรวมของแหล่งที่มาที่ใช้โดยแต่ละ บริษัท

(6) การเขียนโปรแกรมเชิงเส้นเทคนิคต่อไปถือว่าต่อเนื่องและการหารในผลิตภัณฑ์และปัจจัย

(7) ปัจจัยด้านสถาบันยังคงที่เช่นกัน

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

ให้สมมติฐานเหล่านี้การเขียนโปรแกรมเชิงเส้นจะใช้ในทฤษฎีของ บริษัท สำหรับการแก้ปัญหาดังต่อไปนี้:

1. ผลผลิตสูงสุด:

ให้เราสมมติว่า บริษัท วางแผนที่จะผลิตสินค้า Z โดยใช้ X และ Y อินพุต วัตถุประสงค์คือเพื่อเพิ่มผลผลิต มันมีกระบวนการผลิตทางเลือกสองทางคือС (ทุนสูง) และ L (แรงงานเข้มข้น) ข้อ จำกัด เป็นค่าใช้จ่าย MP ที่กำหนดตามที่แสดงในรูปที่ 1 ข้อสมมติฐานอื่น ๆ ทั้งหมด (ที่ระบุไว้ด้านบน) ที่เกี่ยวข้องกับเทคนิคการเขียนโปรแกรมเชิงเส้นมีผลบังคับใช้

ในรูปหน่วยของอินพุต Y ต่อจุดจะถูกวัดตามแกนตั้งและหน่วยของอินพุต X ต่อจุดจะแสดงบนแกนนอน หากกระบวนการСต้องการอินพุต Y 2 ชุดสำหรับทุกหน่วยของอินพุต X มันจะผลิตสินค้าโภคภัณฑ์ 50 หน่วย Z หากอินพุทของ X และ Y เป็นสองเท่าเป็น 4 หน่วยของ Y และ 2 หน่วยของ X ก็เอาท์พุทเป็นสองเท่าเช่นกัน หน่วยของ Z

การรวมกันของ X และ Y ซึ่งเป็นตัวแทนของ a และ b, สร้างขนาดผลผลิตตามเรย์ทุนเข้มข้น ในทางกลับกันหน่วยที่ดี (50) ของ Z ที่ดีสามารถผลิตได้โดยกระบวนการ L โดยรวม 3 หน่วยของ X กับหนึ่งหน่วยของ Y และ 100 หน่วยของ Z สามารถผลิตได้โดยเพิ่มอินพุต A และ Y เป็น 6 เท่า ของ X และ 2 หน่วยของ Y

สเกลเอาท์พุทเหล่านี้สร้างขึ้นตามเรย์ประมวลผลที่ใช้แรงงานมาก OL ซึ่งเป็นตัวแทนจากชุดค่าผสมของอินพุตและเอาต์พุต หากคะแนน a และсที่ระดับเอาท์พุท 50 ยูนิตของรังสีเชิงเส้นОСและ OL เข้าร่วมพวกเขาจะสร้าง isoquant (แสดงจุด) IacS 1 ที่ระดับเอาต์พุต 100 หน่วย isoquant ที่เกี่ยวข้องคือ l 1 bdS

ข้อ จำกัด ด้านค่าใช้จ่ายในการใช้จ่ายจะแสดงโดยเส้นโค้ง iso-cost MP และวางข้อ จำกัด เกี่ยวกับกำลังการผลิตของ บริษัท บริษัท สามารถผลิตโดยใช้ทั้งสองเทคนิคที่มีอยู่Сและ L ภายในพื้นที่ที่แสดงโดย Obd รูปสามเหลี่ยม มันเป็นไปไม่ได้ที่จะสร้างมันขึ้นมาเพื่อผลิตนอก 'การแก้ปัญหาที่เป็นไปได้'

ทางออกที่ดีที่สุดซึ่งเพิ่มผลผลิตสูงสุดของ บริษัท จะเกิดขึ้น ณ จุดที่เส้นโค้งต้นทุน iso สัมผัสกับ isoquant กับเอาต์พุตสูงสุด ในรูป, เส้นโค้ง iso-cost MP แตะ isoquant i 1 bdS ที่จุด b บนโพรเซสเรย์ แสดงให้เห็นว่า บริษัท จะใช้เทคนิคที่เน้นการลงทุนโดยใช้ 4 หน่วยของอินพุต Y และ X 2 หน่วยและผลิตสินค้าโภคภัณฑ์ Z 100 หน่วย

2. การเพิ่มรายได้สูงสุด:

ใช้ บริษัท อื่นที่มีวัตถุประสงค์เพื่อเพิ่มรายได้ภายใต้ข้อ จำกัด บางประการของความสามารถที่ จำกัด สมมติว่า บริษัท ผลิตผลิตภัณฑ์สองรายการคือ X และ Y มีแผนกสี่แผนกที่มีกำลังการผลิตคงที่ ให้แผนกเหล่านี้เกี่ยวข้องกับการผลิตการประกอบการขัดเงาและการบรรจุผลิตภัณฑ์ที่กำหนดเป็นА, В, Сและ D ปัญหาจะแสดงในรูปกราฟิกในรูปที่ 2

การผลิต X และ Y ขึ้นอยู่กับข้อ จำกัด A, B, C และ D ข้อ จำกัด A จำกัด การผลิต X ถึง OA ข้อ จำกัด การ จำกัด การผลิตของ Y เป็น OB ข้อ จำกัด С จำกัด การผลิตทั้ง X และУถึงОС 1 และОСตามลำดับในขณะที่ข้อ จำกัด D จำกัด การผลิตไว้ที่ OD 1 และ OD OATSRB พื้นที่แสดงการรวมกันของ X และ Y ที่สามารถผลิตได้โดยไม่ละเมิดข้อ จำกัด ใด ๆ

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

เส้น iso-profit แสดงถึงการรวมกันของ X และ Y ซึ่งให้ผลกำไรเหมือนกันกับ บริษัท ทางออกที่ดีที่สุดตั้งอยู่บนบรรทัดกำไร ISO ที่สูงที่สุดในรูปหลายเหลี่ยม OATSRB ที่จุด S จุดใด ๆ ที่ไม่ใช่ S อยู่นอกเขตของการผลิตที่เป็นไปได้

3. การลดต้นทุน :

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

Bread (x 1 ) วัดตามแนวแกนนอนและเนย (x 2 ) ถูกวัดบนแกนตั้ง บรรทัด AB แสดงให้เห็นถึงการรวมกันของเนยมากขึ้นและขนมปังน้อยลงและซีดีหมายถึงการรวมกันของเนยน้อยลงและขนมปังมากขึ้น โซลูชั่นที่เป็นไปได้อยู่บนหรือสูงกว่าเส้นหนา AZD ทางออกที่ดีที่สุดคือที่จุด Z ซึ่งเส้นประ iso ต้นทุน RK ผ่านจุดตัดของ AB และ CD วิธีแก้ปัญหาที่เป็นไปได้อาจอยู่ที่จุด A ถ้าขนมปังเป็นที่รักหรือที่ D ถ้าเนยเป็นคนรัก แต่การแก้ปัญหาที่ดีที่สุดจะเกิดขึ้นที่จุด Z ในปัญหานี้

โซลูชั่นกราฟิคโน้ตคณิตศาสตร์ :

เราพยายามที่จะอธิบายรายละเอียดที่สมบูรณ์และการทำงานของปัญหาการเขียนโปรแกรมเชิงเส้นทางคณิตศาสตร์และกราฟิก

1. การเพิ่มรายได้สูงสุด :

ใช้ บริษัท ที่ผลิตผลิตภัณฑ์ X และ Y สองตัวในราคาที่กำหนดไว้ที่ Rs.12 และ Rs.15 ตามลำดับสำหรับแต่ละหน่วย ในการผลิตผลิตภัณฑ์ X บริษัท จำเป็นต้องใช้อินพุต A 12 หน่วย, อินพุต 6 หน่วยและอินพุต 14 ยูนิต C. ผลิตภัณฑ์ Y ต้องการอินพุต 4 หน่วย A, 12 ยูนิตของ 12 และ 12 ยูนิตอินพุต C

อินพุตที่มีอยู่ทั้งหมดในแต่ละกรณีคือ 48 หน่วยของ A, 72 ยูนิตของВและ 84 หน่วยของ C ข้อมูลอินพุต - เอาต์พุตสำหรับปัญหานี้แสดงอยู่ในตารางที่ 1

ปัญหาการเขียนโปรแกรมเชิงเส้นทุกปัญหามีสามส่วนด้วยกัน พวกเขามีดังต่อไปนี้ในแง่ของปัญหาของเราระบุไว้ข้างต้น

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

ฟังก์ชันวัตถุประสงค์ระบุว่าหากทั้งสองผลิตภัณฑ์ X และ Y นำรายได้ของ Rs 12 และ Rs.15 ต่อหน่วยสินค้าเหล่านี้มีการผลิตเท่าใดเพื่อให้ บริษัท มีรายได้สูงสุด

สามารถเขียนเป็น:

Мах: R = 12Х + 15Y

ข้อ จำกัด :

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

อันดับแรกเรารับอินพุต A ปริมาณอินพุตสูงสุดที่สามารถใช้ได้คือ 48 หน่วย แต่ผลิตภัณฑ์ของปริมาณ X และ Y ของทั้งสองผลิตภัณฑ์จะต้องไม่เกิน 48 หน่วย ทางคณิตศาสตร์เนื่องจาก 12X + 4Y ไม่สามารถมากกว่า 48 หน่วยข้อ จำกัด ที่กำหนดโดยอินพุต A จะเป็น 12X + 4Y ≤ 48 ด้วยเหตุผลเดียวกับที่เราสามารถมีข้อ จำกัด ในแง่ของความไม่เท่าเทียมกันสำหรับอินพุตและ C

ดังนั้นข้อ จำกัด เชิงโครงสร้างสามข้อในปัญหาของเราจึงสามารถเขียนเป็น:

12 X + 4 Y ≤ 4Y … (1)

6X + 12 Y ≤ 72 …. (2)

14X + 12 Y ≤ 84 … (3)

โดยที่ X และ Y เป็นตัวแปรทางเลือกของเรา ได้แก่ หน่วยของอินพุต

ข้อ จำกัด ที่ไม่ใช่การปฏิเสธ:

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

โซลูชันกราฟิค :

สำหรับวิธีแก้ไขปัญหากราฟิกเราแก้ไขปัญหาของเรา:

เพิ่ม R = 12X + 15Y

ขึ้นอยู่กับ (i) 12X + 4Y £ 48

6X + 12Y £ 72

14X + 12Y £ 84

(ii) X3 ≥ 0 และ Y3 ≥ 0

เพื่อเป็นตัวแทนของความไม่เท่าเทียมกันแต่ละกราฟิกเราละเว้นสัญญาณความไม่เท่าเทียมกัน (≤) ในสมการของเราและแทนที่ด้วยเครื่องหมายเท่าเทียมกัน (=) เราเขียนสมการ (1) เป็น 12 X + 4 Y = 48

โดยสมมติว่าผลิตภัณฑ์ X ผลิตโดยใช้จำนวนทั้งหมด 48 หน่วยของอินพุต A เท่านั้นเราจึงได้รับ

12X + 4Y = 48 (สูงสุด)

หรือ X = 4 (เมื่อ Y = 0)

ในทำนองเดียวกันสมมติว่าผลิตภัณฑ์ Y นั้นผลิตโดยใช้จำนวน 48 หน่วยของอินพุต A ทั้งหมด

0 + 4Y = 48 หรือ Y = 12 (เมื่อ X = 0)

สมการ 12X + 4Y + 48 แสดงในรูปที่ 4 โดยเส้น AB โดยที่ OA = 12 Y และ OB = 4X จุดใด ๆ บน AB เช่น T เป็นไปตามสมการ 12X + 4Y = 48 ในขณะที่พื้นที่ด้านล่างและด้านซ้ายของเส้น AB ตรงตามความไม่เท่าเทียมกัน 12X + 4Y≤48

ด้วยการแก้สมการ 6X + 12Y = 72 ในวิธีที่คล้ายกันเราจะได้ X = 12 และ Y = 6 นี่คือพล็อตในรูปที่ 45.4 เป็นซีดีเส้นที่ตรงกับสมการนี้โดยที่ОС = 6Y และ OD = 12Y

และโดยการแก้สมการ 14X + 12Y = 84 เราจะได้ X = 6 และ Y = 7 Line EF ในรูปที่ 4 เป็นไปตามสมการนี้โดยที่ OE = 7Y และ OF = 6X

ภูมิภาคที่เป็นไปได้ :

รูปที่ 4 แสดงว่าจุดทั้งหมดในพื้นที่แรเงาที่ล้อมรอบด้วยเส้นสามเส้นที่ตัดกันจะน่าพอใจกับความไม่เท่าเทียมกันสามประการ ที่จุด S เส้น EF ตัดกันเส้นซีดีและที่ T เส้นซีดีตัดกัน AB ดังนั้นพื้นที่แรเงา OBTSC ซึ่งอยู่ด้านล่างและด้านซ้ายของสามบรรทัดตัดกันที่จุด S และ T เป็นไปตามความไม่เท่าเทียมกันของสมการทั้งสาม

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

ทางออกที่ดีที่สุด :

จากจุดต่างๆ B, T, S, C ซึ่งแสดงถึงทางออกที่เป็นไปได้เราต้องหาจุดที่เหมาะสมที่จะเพิ่มรายได้ของ บริษัท ให้ได้มากที่สุด

วิธีรับจุดนี้พีชคณิต? เรารู้พิกัดของจุดที่และСจากสมการ (1) และ (2) โดย OB = 4X และОС = 67 เพื่อกำหนดพิกัดของจุด T เราปฏิบัติกับสมการ (1) และ (3) เป็น สมการที่เกิดขึ้นพร้อมกันเพราะเส้น AB และ EF เป็นตัวแทนของพวกมันตัดกันที่ T แล้วแก้มันด้วย

12X + 4Y = 48 … (1)

14X + 12Y = 84 … (3)

โดยการคูณสมการ (1) ด้วย 3 และลบหลังจากนั้นเรามี

ดังนั้นพิกัดของจุด T คือ X = 2.73 และУ = 3.81 ในทำนองเดียวกันเราสามารถแก้ไขพิกัดของจุด S ด้วยสมการ (3) และ (2) ซึ่งมาถึงที่ Z = 1.5 และ Y = 5.25

เพื่อหาชุดค่าผสมที่เหมาะสมที่สุดของ X และ Y เราจะแทนที่ค่าของ X (Rs. 12) และУ (Rs 15) เป็นค่าของพิกัดของจุด comerer ต่างๆที่มาในปรสิตข้างต้น

ที่ B เรามี X = 4 และ Y = 0 และแทนที่สิ่งเหล่านี้ในฟังก์ชันวัตถุประสงค์ (Rs) R = 12X + 15 Y เรามี

(Rs 12) (4) + (Rs 15) (0) = Rs 48 … (4)

ที่ T เรามี X = 2.73 และУ = 3.81 และได้มาในทำนองเดียวกัน

(Rs 12) (2.73) + (Rs. 15) (3.81) = Rs 89.91 ... (5)

ที่ S เรามี X = 1.5 และ Y = 5.25 และเราได้รับ

(Rs 12) (1.5) + (Rs 15) (5.25) = Rs 96.75 … (6)

ที่ C เรามี Y = 6 และ X = 0 และเราได้

(Rs. 12) (0) + (Rs 15) (6) Rs 90 …. (7)

จากสมการข้างต้น (4), (5), (6) และ (7) เราพบว่าสมการ (6) ให้รายได้สูงสุดของ Rs 96.75 นี่แสดงให้เห็นว่าเนื่องจากราคาของทั้งสองผลิตภัณฑ์ X และУและด้วยจำนวนของปัจจัยการผลิตรายได้รวมของ บริษัท จะเพิ่มสูงสุดที่จุด S ซึ่งเป็นจุดที่ดีที่สุดภายใต้ข้อ จำกัด ที่กำหนด

การพิสูจน์โซลูชันที่เหมาะสมที่สุด :

เพื่อให้การแก้ปัญหาที่เหมาะสมที่สุดถูกต้องผลผลิตทั้งหมดที่ผลิตต้องเท่ากับอินพุตทั้งหมดที่มีอยู่สำหรับ บริษัท เราเห็นว่าจุดที่เหมาะสมที่สุดคือ S ในรูปที่ 45.4 ซึ่ง บริษัท จะเพิ่มรายได้รวมสูงสุดด้วยการผลิต X 1.5 หน่วยและ 5.25 หน่วยของУ เพื่อที่จะกำหนดจำนวนรวมของแต่ละอินพุตที่ บริษัท ใช้เพื่อสร้างหน่วยข้างต้นของ X และУเราจะอ้างถึงคอลัมน์ (2) และ (3) ของตาราง 45.1

ในการผลิตหนึ่งหน่วยของ X บริษัท ใช้อินพุต 12A + 6В + 14С และเพื่อสร้างหนึ่งหน่วยของУมันใช้อินพุต 4A + 125 + 12C เนื่องจาก บริษัท ผลิต X 1.5 หน่วยและ 5.25 หน่วยของ Y อินพุตต่างๆที่ใช้ในการผลิตหน่วยเหล่านี้จะถูกนำเสนอในรูปแบบตารางด้านล่าง

การเพิ่มผลรวมของอินพุตที่เกี่ยวข้องเราพบว่าจำนวนทั้งหมดของอินพุต A ที่ใช้คือ 18A + 21A = 39A ของอินพุตเป็น 9B + 63B = 72B และอินพุตСคือ 21C + 63С = 84С คอลัมน์สุดท้ายของตาราง 45.1 แสดงจำนวนสูงสุดของอินพุต A ที่ บริษัท มีให้คือ 48 หน่วย, 72 หน่วยของอินพุต 5 และ 84 หน่วยของอินพุต C เราพบว่าอินพุตและเอสซีถูกใช้โดย บริษัท อย่างเต็มที่เมื่อสร้าง ผลิตภัณฑ์ X และ Y ณ จุดที่เหมาะสม S

ตราบใดที่อินพุต A เกี่ยวข้องกันมันก็ไม่ได้ใช้อย่างเต็มที่เพราะมีเพียง 39 ยูนิตเท่านั้นที่ใช้โดย บริษัท และ 9 ยูนิต (48-39) ยังคงไม่ใช้งาน นั่นคือเหตุผลที่จุด T บนขอบเขตที่เป็นไปได้ไม่ได้เป็นตัวแทนของการแก้ปัญหาที่ดีที่สุดเพราะมันเป็นพิกัดของสมการ (1) และ (3)

ปัญหาสองประการ:

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

เพื่อให้ได้มาซึ่งปัญหาสองครั้งแรกจำเป็นต้องมีขั้นตอนต่อไปนี้:

1. คอลัมน์และแถวสลับกัน

2. ทิศทางของความไม่เท่าเทียมกันในข้อ จำกัด กลับด้าน หากครั้งแรกมีสัญญาณ dual ทั้งคู่มีสัญญาณ≥

3. จำนวนตัวแปรถูกกลับรายการ

ปัญหาแรกที่กำหนดไว้ในตารางที่ 45.1 ถูกตั้งค่าในรูปแบบของคู่ตาม:

2. ปัญหาเรื่องอาหาร - ลดต้นทุน:

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

ให้ x 1 และ x 2 เป็นตัวแทนของขนมปังและเนยตามลำดับแต่ละอันมีเนื้อหาของแคลอรี่และไวยากรณ์ของโปรตีนดังต่อไปนี้ ปริมาณสารอาหารของขนมปังคือ 1, 000 แคลอรี่และโปรตีน 50 กรัมต่อครึ่งกิโลกรัม เนย 2000 แคลอรี่และ 200 กรัมของโปรตีนต่อครึ่งกิโลกรัม

อาหารมาตรฐานควรมี 3000 แคลอรี่และ 200 กรัมของโปรตีนต่อวัน ราคาตลาด 500 กรัม ขนมปังคือ Rs 2 และเนย Rs 6 ต่อ 500 กรัม ข้อมูลนี้ถูกสรุปไว้ในตารางที่ 2

ปัญหาคือการหาอาหารที่ดีที่สุดตามมาตรฐานโภชนาการขั้นต่ำตามที่วางไว้ในคอลัมน์สุดท้ายของตารางข้างต้นและค่าใช้จ่ายน้อยที่สุดที่ระบุโดย (?) ค่าใช้จ่ายทั้งหมดของการรับประทานอาหารคือ

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

การแก้ปัญหาสามารถทำได้โดยเงื่อนไขสามข้อใด ๆ ตัวอย่างเช่นค่าใช้จ่ายСสามารถลดลงได้โดยขึ้นอยู่กับความสัมพันธ์ด้านเดียว: x 1 2x2 = 3 ด้วยการแก้ปัญหาเรามี x 1 = 3 และ x 2 = 3/2 = 1.5 ในรูปที่ 5 นี้แสดงโดยบรรทัด AB โดยที่ OA = 1.5x 2 และ OB = 3x 1

ความสัมพันธ์ด้านที่สองคือ 2x 1 + 8x 2 = 8 และโดยการแก้มันทำให้เราได้ x 1 = 4 และ x 2 = 1 นี่คือพล็อตในรูปที่ 5 เป็นซีดีสายที่ตรงกับสมการนี้โดยที่ОС = 1x2 และ OD = 4x 1 ดังนั้นในรูปที่ 5, x 1 (ขนมปัง) จะถูกวัดตามแนวแกนนอนและ x 2 (เนย) จะถูกวัดตามแนวแกน

บรรทัด AB แสดงการรวมกัน x 1 + 2x 2 = 3 และ CD หมายถึงการรวมกัน 2x 1 + 8x 2 = 8 คำตอบที่เป็นไปได้อยู่บนหรือสูงกว่าเส้นหนา AZD ทางออกที่ดีที่สุดคือที่จุด Z ซึ่งจุดตัดกัน AB และ CD สองเส้น

ในการค้นหาว่า Z หรือจุดอื่นใด (A หรือ D) ภายในขอบเขตที่เป็นไปได้ AZD แสดงถึงวิธีแก้ปัญหาที่เป็นไปได้หรือไม่เราปฏิบัติกับสมการทั้งสองของปัญหาเป็นสมการพร้อมกันและแก้ปัญหาดังนี้

X 1 + 2x 2 = 3 …… .. (1)

2x 1 + 8x 2 = 8 ………… .. (2)

โดยการคูณสมการ (1) ด้วย 4 และลบหลังจากนั้นเรามี

4x 1 + 8x 2 = 12

2x 1 + 8x 2 = 8

2x1 = 4

X 1 = 2

แทนค่า x 1 = 2 ใน (2) เราจะได้รับ

2 x 2 + 8x 2 = 8

4 + 8x 2 = 4

8x2 = 8-4

X 2 = 1/2

ดังนั้นพิกัดของจุด Z คือ x 1 = 2 และ x 2 = 1/2 เรารู้พิกัดของจุด A เป็น x 2 = 1.5 และх 1 = 0 และจากจุด D เป็น x 1 = 4 และ x 2 = 0

เพื่อหาการรวมกันที่ดีที่สุดของ x 1 (เนย) และ x 2 (ขนมปัง) เราจะแทนที่ค่าของ x 1 (Rs 2) และ x 2 (Rs 6) เป็นค่าของพิกัดสามจุด A Z และ D

ณ จุด A เรามี x 2 = 1.5 และ x 1 -0 และแทนสิ่งเหล่านี้ในฟังก์ชันวัตถุประสงค์ C = 2x t + 6x 2 เรามี

(Rs 2) (0) + (Rs 6) (1.5) = Rs 9 …… .. (3)

ในทำนองเดียวกันที่ Z เรามี (Rs2) (2) + (Rs6) (1/2) = Rs 7 …… .. (4)

ที่ D เรามี (Rs 2) (4) + (Rs 6) (0) = Rs 8 …… .. (5)

จากสมการข้างต้นเราพบว่าสมการ (4) ให้ค่าต่ำสุดของ Rs 7 ดังนั้นทางออกที่ดีที่สุดของปัญหาอาหารนี้คือ x 1 = 2, x 2 = 1/2, Z = 7 (ขั้นต่ำ) ซึ่งแสดงให้เห็นว่า ตรงตามข้อกำหนดทางโภชนาการขั้นต่ำรายวันของบุคคลนั้นหากพบว่าเขาซื้อ 2 ขนมปังและ 250 กรัมของเนยในราคาขั้นต่ำ 7 รูปีต่อวัน

มันคู่:

ทุกปัญหาการย่อเล็กสุดมีปัญหาการขยายใหญ่สุดที่เกี่ยวข้องหรือที่เรียกว่าคู่ ปัญหาแรกของอาหารของเราคือ C = 2x 1 + 6x 2 ซึ่งเป็นเรื่องขั้นต่ำ

ปัญหาอาหารนี้ประกอบด้วยการให้ 3000 แคลอรี่และโปรตีน 200 กรัมที่จะได้รับจากขนมปังและเนยปริมาณที่แน่นอนในราคาต่ำสุด ให้ y 1 และ y 2 เป็นราคาต่อหน่วยของสารอาหารทั้งสอง ปัญหาที่สองคือการเพิ่ม P ที่มูลค่ารวมของอาหาร

นี่แสดงให้เห็นว่าค่าใช้จ่ายสำหรับขนมปังคือ y 1 + 2уซึ่งไม่เกิน Rs 2 ต่อครึ่งกิโลกรัมและเนยเป็น2у 1 + 8y 2 ซึ่งไม่เกิน Rs 6 ต่อครึ่งกิโลกรัม

ในคู่แรกถูกย้ายในความสัมพันธ์ด้านกล่าวคือในปัญหาแรกราคา Rs 2 และ Rs 6 จะลดลงและมาตรฐานโภชนาการขั้นต่ำ 3 และ 8 เป็นความสัมพันธ์ด้านในขณะที่คู่ที่ปรากฏในสถานที่ตรงกันข้าม .

คำตอบของสมการ (2) ด้านบนคือ

Y 1 + 2у 2 = 2

2Y 1 + 8y 2 = 6

สมการการคูณ (i) คูณ 4 และลบสมการ (ii) จากนั้นเราจะได้

เพื่อหาการรวมกันที่เหมาะสมที่สุดของ y 1 และ y 2 เราจะแทนที่ค่าของ y 1 (Rs 3) และ y 2 (Rs 8) เป็นค่าของพิกัดของจุดมุม A และ D ในรูป 6

ด้วยการแก้สมการ y 1 + 2y 2 = 2 ค่าของ y 1 = 2 และของ y 2 = 1 ดังนั้น OA = 1y 2 และ OB = 2y 1 ในรูปที่ 6

ในทำนองเดียวกันค่าของ y 1 = 3 และของ y = 3/4 หรือ 0.75 จากสมการ 2y 1 + 8y 2 = 6 เพื่อให้ОС = 0.75y 2 และ OD = 3y 1 ในรูป

ดังนั้น ณ จุด A เรามี y 2 = 1 และ y 1 = Оและแทนที่สิ่งเหล่านี้ในฟังก์ชันวัตถุประสงค์

P = 3Y 1 + 8Y 2 เรามี

(Rs 3) (0) + (Rs 8) (1) = Rs 8 ……. (สาม)

ในทำนองเดียวกันที่จุด P เรามี (Rs 3) (1) + (Rs 8) (1/2) = Rs 7 …… (iv)

ณ จุด D เรามี (Rs 3) (3) + (Rs 8) (0) = Rs 9 …… (v)

ดังนั้นเราจึงพบว่าสมการ (iv) ให้ค่าต่ำสุดของ Rs 7

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

วิธีแก้ปัญหาแรกคือ

x 1 = 2, x 2 = 1/2, Z = 7 (ต้นทุนอาหารขั้นต่ำ)

วิธีการแก้ปัญหาของ dual (2) ทำงานได้ที่

Y 1 = 1, y 2 = 1/2, P = 1 (ค่าสูงสุดของอาหาร)

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

3. ปัญหาการเพิ่มกำไรสูงสุด :

ให้เรานำปัญหาการโปรแกรมเชิงเส้นอีกอันเกี่ยวกับการเพิ่มผลกำไรสูงสุด สมมติว่ามีผู้ผลิตรายย่อยที่ผลิตผลิตภัณฑ์ X และ Y สองเครื่องในสองเครื่อง A และ B ผลิตภัณฑ์ X ต้องใช้เวลา 3 ชั่วโมงในเครื่อง A และ 2 ชั่วโมงสำหรับเครื่อง B ในขณะที่ผลิตภัณฑ์ Y ต้องใช้เวลา 3 ชั่วโมงในเครื่อง A และ 4 ชั่วโมง เครื่อง B.

เครื่อง A สามารถทำงานได้ 18 ชั่วโมงต่อวันในขณะที่เครื่อง A สามารถทำงานได้ 16 ชั่วโมงต่อวัน ผู้ผลิตได้รับผลกำไร Rs 30 ในแต่ละหน่วยของผลิตภัณฑ์ X และ Rs 40 ในแต่ละหน่วยของผลิตภัณฑ์ 7 เขาควรผลิตสินค้าแต่ละหน่วยต่อวันเพื่อให้ได้กำไรสูงสุด เพื่อความเข้าใจที่ดีขึ้นปัญหาจะถูกนำเสนอในตารางที่ 3

สำหรับโซลูชันกราฟิกปัญหาการเขียนโปรแกรมเชิงเส้นนี้สามารถเรียกคืนเป็น:

ขยายใหญ่สุด P = 30X + 40 Y (Rs)

ภายใต้ (i) 3X + 3Y ≤ 18

หรือ X + Y ≤ 6 …. (1)

2X + 4Y ≤ 16

X + 2Y ≤ 8 …. (2)

(ii) X ≥ 0 และ 7 ≥ 0

ด้วยการแก้สมการ X + Y = 6 เรามี X = 6 และ Y = 6 ซึ่งแสดงเป็นบรรทัด AB ในรูปที่ 7 โดยที่ OA = 6Yand OB = 6X

ในทำนองเดียวกันโดยการแก้สมการ X + 2y = 8 เรามี X = 8 และ Y = 4 นี่แสดงเป็นซีดีบรรทัดในรูปที่ 7 โดยที่ОС = 4 Y และ OD = 8X

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

ในการค้นหาว่าจุดใดของจุดมุมО, В, P หรือСแสดงถึงวิธีการแก้ปัญหาที่เป็นไปได้ซึ่งกำไรได้รับการขยายให้มากที่สุดเราจะปฏิบัติต่อสมการทั้งสองเป็นสมการพร้อมกันและแก้ปัญหาดังต่อไปนี้

X + Y = 6 …. (ผม)

X + 2Y = 8 …. (ii)

โดยการคูณสมการ

(i) โดย 2 และลบสมการ

(ii) จากนั้นเราจะได้รับ

การแทนค่า X = 4 ในสมการ (i) เรามี

4 + Y = 6

หรือ Y = 2

ดังนั้นพิกัดของจุด P คือ X = 4 และ Y = 2 ตามที่คำนวณไว้ข้างต้นพิกัดของจุดคือ X = 6 และ 7 = 0 และพิกัดของจุดСคือ X = 0 และ X = 4

เพื่อให้ได้ผลกำไรสูงสุดเราคำนวณกำไรที่มุมของภูมิภาคความเป็นไปได้เช่น O, B, P และСด้วยความช่วยเหลือของค่าของพิกัดเหล่านี้

กำไรที่จุดОเป็นศูนย์

กำไรที่จุด = (Rs 30) (6) + (Rs 40) (0) = Rs 180

กำไร ณ จุด P = (Rs 30) (4) + (Rs 40) (2) = Rs 200

กำไรที่จุดС = (Rs 30) (0) + (Rs 40) (4) = Rs 160

ดังนั้นผู้ผลิตจะได้รับ Rs 200 เป็นกำไรสูงสุด (ที่จุด P) โดยผลิต X 4 หน่วยและ 2 หน่วยต่อ 7 วัน ดังนั้นทางออกที่ดีที่สุดคือ X = 4, Y = 2 และ P = Rs 200 (สูงสุด)

 

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