วิธีกราฟิกสำหรับการแก้สมการโปรแกรมเชิงเส้น วิธีการแบบกราฟิกสำหรับการแก้ปัญหา

ทฤษฎีสั้น ๆ

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

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

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

ตัวอย่างการแก้ปัญหา

งาน

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

ที่จำเป็น:

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

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

การแก้ปัญหา

การสร้างแบบจำลอง

อนุญาตและแสดงจำนวนผลิตภัณฑ์ที่ผลิตในประเภทที่ 1 และ 2

จากนั้นข้อ จำกัด ของทรัพยากร:

นอกจากนี้ตามความหมายของงาน

ฟังก์ชันเป้าหมายของแบบจำลองเศรษฐศาสตร์-คณิตศาสตร์ซึ่งแสดงรายได้ที่ได้รับจากการขาย:

เราได้รับแบบจำลองทางเศรษฐศาสตร์และคณิตศาสตร์ดังต่อไปนี้:

การสร้างขอบเขตของโซลูชันที่เป็นไปได้

มาแก้ปัญหาการเขียนโปรแกรมเชิงเส้นที่เกิดขึ้นแบบกราฟิก:

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

มาหาจุดที่เส้นผ่านกัน:

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

ในการกำหนดครึ่งระนาบ ให้ใช้จุดใดก็ได้ เช่น ซึ่งไม่อยู่ในเส้น (1) และแทนที่พิกัด (0;0) ลงในอสมการที่สอดคล้องกัน เพราะ ความไม่เท่าเทียมกันเป็นจริง:

ขอบเขตการแก้ปัญหาของอสมการที่ 1 สอดคล้องกันกับครึ่งระนาบด้านซ้าย

ลองพิจารณาจุดใดๆ ที่ไม่อยู่ในเส้น (2) และแทนที่พิกัด (0;0) ลงในอสมการที่สอดคล้องกัน เพราะ ความไม่เท่าเทียมกันเป็นจริง:

ลองพิจารณาจุดใดๆ ที่ไม่อยู่ในเส้น (3) และแทนที่พิกัด (0;0) ลงในอสมการที่สอดคล้องกัน เพราะ ความไม่เท่าเทียมกันเป็นจริง:

ขอบเขตการแก้ปัญหาของอสมการที่ 2 สอดคล้องกันกับครึ่งระนาบด้านซ้าย

ขอบเขตของแนวทางแก้ไขที่เป็นไปได้คือตัวเลข

การค้นหาวิธีแก้ไขปัญหา LP

เราสร้างเวกเตอร์ซึ่งมีพิกัดเป็นสัดส่วนกับสัมประสิทธิ์ของฟังก์ชันวัตถุประสงค์ นี่คือค่าสัมประสิทธิ์สัดส่วน

วาดเส้นระดับตั้งฉากกับเวกเตอร์ที่สร้างขึ้น

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

คำตอบ

ดังนั้นจึงจำเป็นต้องผลิตผลิตภัณฑ์ประเภทที่ 1 จำนวน 56 รายการและผลิตภัณฑ์ประเภทที่ 2 จำนวน 64 รายการ ในกรณีนี้รายได้จากการขายผลิตภัณฑ์จะสูงสุดและเท่ากับ 5104 หน่วยการเงิน

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

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

การเขียนโปรแกรมนูน - วิธีกราฟิก
ให้ตัวอย่างการแก้ปัญหาการเขียนโปรแกรมนูนกำลังสองโดยใช้วิธีกราฟิกมาให้

ตัวอย่างที่ 6.1

สารละลาย:

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

สามารถแก้ไขได้โดยใช้วิธีทางเรขาคณิต

ขั้นที่ 1: ( โอดีอาร์ ).

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

.

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

ขั้นที่ 2: .

ให้เรานิยามฮาล์ฟเพลน - คำตอบของอสมการแต่ละอย่าง

ให้เราพิจารณาความไม่เท่าเทียมกันประการแรกของระบบข้อจำกัดของปัญหา ลองพิจารณาจุดหนึ่ง (จุดควบคุม) ที่ไม่อยู่ในเส้นที่สอดคล้องกับความไม่เท่าเทียมกันนี้ เช่น จุด (0; 0) ลองแทนที่มันเป็นอสมการที่กำลังพิจารณา:

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

ในทำนองเดียวกัน เราก็หาวิธีแก้ปัญหาของความไม่เท่าเทียมกันอื่นๆ และทำเครื่องหมายไว้บนกราฟตามลำดับ ดังนั้นกราฟจะมีลักษณะดังนี้:

ขั้นที่ 3: .

ระนาบครึ่งที่พบ (คำตอบของความไม่เท่าเทียมกันของระบบข้อจำกัด) จะก่อตัวเป็นรูปหลายเหลี่ยมเมื่อตัดกัน เอบีดีโอซึ่งเป็น ODD ของปัญหาที่กำลังพิจารณา

ข้าว. 1. ขอบเขตของแนวทางแก้ไขปัญหาที่เป็นไปได้

ขั้นที่ 4:
เวกเตอร์การไล่ระดับสีแสดงทิศทางของการขยายฟังก์ชันวัตถุประสงค์ให้สูงสุด มากำหนดพิกัดกัน: พิกัดของจุดเริ่มต้น (จุดแอปพลิเคชัน) – (0; 0) พิกัดของจุดที่สอง:

ลองพล็อตเวกเตอร์นี้บนกราฟ (รูปที่ 2)

ขั้นที่ 5: .

ลองพิจารณาฟังก์ชันวัตถุประสงค์ของปัญหานี้:

.

ลองให้ค่ามันดูบ้าง เช่น . เรามาแสดงตัวแปรกัน x2ผ่าน x1:

.

ในการสร้างเส้นตรงโดยใช้สมการนี้ เราจะระบุจุดที่ต้องการ 2 จุด เช่น

เรามาสร้างเส้นตรงที่สอดคล้องกับฟังก์ชันวัตถุประสงค์ (รูปที่ 2)

ข้าว. 2. การสร้างฟังก์ชันเป้าหมาย F(X) และเวกเตอร์เกรเดียนต์ C

ขั้นที่ 6: การกำหนดฟังก์ชันเป้าหมายสูงสุด.

การเคลื่อนตัวเป็นเส้นตรง เอฟ(เอ็กซ์) ขนานกับตัวมันเองในทิศทางของเวกเตอร์ไล่ระดับสี เราจะหาจุดสุดขั้ว (จุด) ของ ODR ตามกราฟ (รูปที่ 3) จุดดังกล่าวคือจุด C - จุดตัดของเส้น ฉัน และ ครั้งที่สอง .

ข้าว. 3. การกำหนดจุดสูงสุดของฟังก์ชันวัตถุประสงค์ F(X)

มากำหนดพิกัดของจุด C เพื่อจุดประสงค์นี้ แก้ระบบสมการเชิงเส้นต่อไปนี้:

ลองแทนที่พิกัดที่พบเป็นฟังก์ชันวัตถุประสงค์แล้วค้นหาค่าที่เหมาะสม (สูงสุด) ของมัน:

คำตอบ:ภายใต้ข้อจำกัดที่กำหนด ค่าสูงสุดของฟังก์ชันวัตถุประสงค์ เอฟ(เอ็กซ์)=24 ซึ่งทำได้ที่จุด C ซึ่งเป็นพิกัดนั้น x1=6, x2=4.

ตัวอย่างที่ 6.2แก้ปัญหาการโปรแกรมเชิงเส้นโดยใช้วิธีเรขาคณิต:

สารละลาย:

ด่าน 1-3 คล้ายกับด่านที่เกี่ยวข้องของงานก่อนหน้า
ขั้นที่ 4: การสร้างเวกเตอร์เกรเดียนต์
การสร้างเวกเตอร์ไล่ระดับสีนั้นดำเนินการในลักษณะเดียวกับปัญหาก่อนหน้า ลองพล็อตเวกเตอร์นี้บนกราฟ (รูปที่ 4) เรายังทราบด้วย แผนภูมินี้ลูกศรคือทิศทางตรงข้ามกับเวกเตอร์ไล่ระดับสี – ทิศทางของการย่อเล็กสุดของฟังก์ชันวัตถุประสงค์ เอฟ (เอ็กซ์).

ขั้นที่ 5: การสร้างฟังก์ชันเป้าหมายโดยตรง.

การสร้างฟังก์ชันวัตถุประสงค์โดยตรง เอฟ(เอ็กซ์) ดำเนินการในลักษณะเดียวกับปัญหาก่อนหน้า (ผลการก่อสร้างแสดงในรูปที่ 4)

ข้าว. 4. การสร้างฟังก์ชันวัตถุประสงค์ F(x) และเวกเตอร์เกรเดียนต์ C

ขั้นที่ 6: การกำหนดฟังก์ชันเป้าหมายที่เหมาะสมที่สุด.

การเคลื่อนตัวเป็นเส้นตรง เอฟ(x) ขนานกับตัวมันเองในทิศทางตรงข้ามกับเวกเตอร์ไล่ระดับสี เราจะหาจุดสุดขั้ว (จุด) ของ ODR จากกราฟ (รูปที่ 5) จุดดังกล่าวคือจุด O ที่มีพิกัด (0; 0)

ข้าว. 5. การกำหนดจุดต่ำสุดของฟังก์ชันวัตถุประสงค์

แทนที่พิกัดของจุดต่ำสุดลงในฟังก์ชันเป้าหมาย เราจะกำหนดค่าที่เหมาะสมที่สุด (ขั้นต่ำ) ซึ่งเท่ากับ 0
คำตอบ:ภายใต้ข้อจำกัดที่กำหนด ค่าต่ำสุดของฟังก์ชันวัตถุประสงค์ เอฟ(เอ็กซ์)=0 ซึ่งไปถึงจุด O (0; 0)

ตัวอย่างที่ 6.3แก้ไขปัญหาการเขียนโปรแกรมเชิงเส้นต่อไปนี้โดยใช้วิธีทางเรขาคณิต:

สารละลาย:

ปัญหาการโปรแกรมเชิงเส้นที่กำลังพิจารณามีระบุไว้ใน รูปแบบบัญญัติเราเลือกเป็นตัวแปรพื้นฐาน x 1 และ x2 .

มาสร้างเมทริกซ์แบบขยายแล้วเลือกโดยใช้วิธีการ จอร์แดน-เกาส์ตัวแปรพื้นฐาน x1 และ x 2 .

คูณ (องค์ประกอบต่อองค์ประกอบ) บรรทัดแรกด้วย –3 และเพิ่มเข้าไปในบรรทัดที่สอง:
.

คูณบรรทัดที่สองด้วย:

.

เพิ่มบรรทัดที่สองลงในบรรทัดแรก:

.

เป็นผลให้ระบบข้อจำกัดจะอยู่ในรูปแบบต่อไปนี้:

เรามาแสดงตัวแปรพื้นฐานในรูปของตัวแปรอิสระกัน:

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

ให้เราเขียนปัญหาการเขียนโปรแกรมเชิงเส้นผลลัพธ์:

เนื่องจากตัวแปรต่างๆ x1 และ x2 ไม่เป็นลบดังนั้นระบบข้อ จำกัด ที่เกิดขึ้นสามารถเขียนได้ในรูปแบบต่อไปนี้:

จากนั้นปัญหาเดิมสามารถเขียนได้เทียบเท่ากันดังต่อไปนี้ งานมาตรฐานการเขียนโปรแกรมเชิงเส้น:

ปัญหานี้มีสองพารามิเตอร์การออกแบบ ดังนั้นจึงสามารถแก้ไขได้โดยใช้วิธีทางเรขาคณิต

ขั้นที่ 1: การสร้างเส้นตรงซึ่งจำกัดพื้นที่ของการแก้ปัญหาที่เป็นไปได้ ( โอดีอาร์ ).

ให้เราพิจารณาระบบข้อจำกัดของปัญหาการโปรแกรมเชิงเส้น (เพื่อความสะดวก เราจะนับจำนวนอสมการ):

มาสร้างเส้นตรงที่สัมพันธ์กับความไม่เท่าเทียมกันแต่ละอย่างกัน (รูปที่ 6) เรากำหนดหมายเลขเส้นตรงตามรูปแบบที่นำมาใช้ก่อนหน้านี้

ขั้นที่ 2: การกำหนดวิธีแก้ปัญหาความไม่เท่าเทียมกันของระบบข้อจำกัดต่างๆ.

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

ขั้นที่ 3: การกำหนด ODD ของปัญหาการโปรแกรมเชิงเส้น.

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

ข้าว. 6. ส่วนของเอกสาร MathCAD:

การสร้างขอบเขตของการแก้ปัญหาที่เป็นไปได้

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

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

ทิศทางตรงข้ามกับเวกเตอร์ไล่ระดับสีสอดคล้องกับทิศทางของการลดฟังก์ชันวัตถุประสงค์ให้เหลือน้อยที่สุด

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

เราจะพิจารณาวิธีแก้ปัญหานี้บนเครื่องบิน อสมการของระบบข้อจำกัดด้านฟังก์ชันแต่ละอย่างจะกำหนดเส้นแบ่งเขตครึ่งระนาบในเชิงเรขาคณิต พี x, + + j2 x 2 = bn i = 1, ต.เงื่อนไขที่ไม่เป็นลบจะกำหนดครึ่งระนาบที่มีเส้นแบ่งเขต เอ็กซ์ (= 0, x2= 0 ตามนั้น ถ้าระบบมีความสอดคล้องกัน ระนาบครึ่งหนึ่งที่ตัดกันจะก่อตัวเป็นส่วนร่วมซึ่งเป็นเซตนูนและแสดงถึงกลุ่มของจุด พิกัดของแต่ละจุดเหล่านี้เป็นคำตอบของระบบนี้ เซตของจุดเหล่านี้เรียกว่า รูปหลายเหลี่ยมสารละลายอาจเป็นจุด ส่วน รังสี รูปหลายเหลี่ยมที่มีขอบเขตหรือไม่มีขอบเขตก็ได้

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

สมการเชิงเส้นอธิบายชุดของจุดที่อยู่ในเส้นเดียวกัน อสมการเชิงเส้นอธิบายบางพื้นที่บนเครื่องบิน

ให้เราพิจารณาว่าส่วนใดของเครื่องบินที่อธิบายความไม่เท่าเทียมกัน 2x ( + 3x 2 12.

ก่อนอื่น เรามาสร้างเส้นตรง 2x กันก่อน + Zx 2 = 12. มันผ่านจุด (6; 0) และ (0; 4) ประการที่สอง เราพิจารณาว่าฮาล์ฟเพลนใดที่ตรงกับความไม่เท่าเทียมกัน เมื่อต้องการทำสิ่งนี้ ให้เลือกจุดใดก็ได้บนกราฟที่ไม่อยู่ในเส้นและแทนที่พิกัดของจุดนั้นลงในอสมการ หากความไม่เท่าเทียมกันเกิดขึ้นแล้ว จุดที่กำหนดให้เป็นวิธีแก้ปัญหาที่ยอมรับได้ และครึ่งระนาบที่มีจุดจะตอบสนองความไม่เท่าเทียมกัน สะดวกในการใช้ต้นทางของพิกัดมาทดแทนความไม่เท่าเทียมกัน มาทดแทนกันเถอะ x ( = x 2 = 0 ถึงอสมการ 2x, + 3x 2 12. เราได้ 2 0 + 3 0

ในทำนองเดียวกัน คุณสามารถอธิบายข้อจำกัดทั้งหมดของปัญหาการเขียนโปรแกรมเชิงเส้นเป็นกราฟิกได้

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

ต้องจำไว้ว่าขอบเขตของการแก้ปัญหาที่เป็นไปได้นั้นเป็นไปตามเงื่อนไขของการไม่ปฏิเสธ (เอ็กซ์จ > 0เจ = 1, ป)พิกัดของจุดใดๆ ที่เป็นของโดเมนคำจำกัดความเป็นวิธีแก้ไขปัญหาที่ถูกต้อง

หากต้องการค้นหาค่าสุดขีดของฟังก์ชันวัตถุประสงค์เมื่อแก้ ZLP แบบกราฟิก ให้ใช้ เวกเตอร์ไล่ระดับสี,ซึ่งพิกัดเป็นอนุพันธ์บางส่วนของฟังก์ชันวัตถุประสงค์:

เวกเตอร์นี้แสดงทิศทางของการเปลี่ยนแปลงที่เร็วที่สุดในฟังก์ชันวัตถุประสงค์ ตรง ค [ x ลิตร + ค 2 x 2 = ฉ(x 0)ตั้งฉากกับเวกเตอร์เกรเดียนต์คือ เส้นระดับฟังก์ชั่นเป้าหมาย (รูปที่ 2.2.2) ณ จุดใดๆ บนเส้นระดับ ฟังก์ชันวัตถุประสงค์จะใช้ค่าเดียวกัน ให้เราถือเอาฟังก์ชันเป้าหมายเป็นค่าคงที่ ก.การเปลี่ยนความหมาย เอ,เราได้ตระกูลเส้นขนาน ซึ่งแต่ละเส้นเป็นเส้นระดับของฟังก์ชันวัตถุประสงค์

ข้าว. 2.2.2.

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

วิธีการแบบกราฟิกสำหรับการแก้ปัญหา PLP ประกอบด้วยสี่ขั้นตอน:

• 1. มีการสร้างขอบเขตของโซลูชันที่ยอมรับได้ (ADA) ของ PLP
• 2. เวกเตอร์เกรเดียนต์ของฟังก์ชันวัตถุประสงค์ (TF) ถูกสร้างขึ้นโดยมีจุดเริ่มต้นที่จุด x 0(0; 0): V = (s, จาก 2)
• 3. เส้นระดับ CjXj + ค 2 x 2 = ก (ก -ค่าคงที่) - เส้นตรงตั้งฉากกับเวกเตอร์ไล่ระดับสี V - เคลื่อนที่ไปในทิศทางของเวกเตอร์ไล่ระดับสีในกรณีของการเพิ่มฟังก์ชันวัตถุประสงค์ให้สูงสุด ฉ(x v x 2)จนกว่าจะออกจาก ODR เมื่อย่อเล็กสุด /(*, x2)เส้นระดับเคลื่อนที่ไปในทิศทางตรงข้ามกับเวกเตอร์ไล่ระดับสี จุดสูงสุด (หรือจุด) ของ ODR ในระหว่างการเคลื่อนไหวนี้คือจุดสูงสุด (ต่ำสุด) ฉ(xหน้า เจซี 2)

หากเส้นตรงที่สอดคล้องกับเส้นระดับไม่ทิ้ง ODR ในระหว่างการเคลื่อนไหว ดังนั้นค่าต่ำสุด (สูงสุด) ของฟังก์ชัน ฉ(xหน้า x 2) ไม่มีอยู่

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

4. กำหนดพิกัดของจุดสูงสุด (ต่ำสุด) เมื่อต้องการทำเช่นนี้ ก็เพียงพอที่จะแก้ระบบสมการของเส้นที่ให้คะแนนสูงสุด (ต่ำสุด) ที่จุดตัด ความหมาย ฉ(x ( , x 2),ที่พบที่จุดผลลัพธ์คือค่าสูงสุด (ขั้นต่ำ) ของฟังก์ชันวัตถุประสงค์

สถานการณ์ที่เป็นไปได้ของโซลูชันกราฟิกของ ZLP แสดงไว้ในตารางที่ 1 2.2.1.

ตารางที่ 2.2.1

ประเภทของ ODR	ประเภทของโซลูชันที่เหมาะสมที่สุด
ถูก จำกัด	การตัดสินใจเท่านั้น
	โซลูชั่นที่ไม่มีที่สิ้นสุด
ไม่ จำกัด	CF ไม่จำกัดจากด้านล่าง
	CF ไม่ได้จำกัดจากด้านบน
	การตัดสินใจเท่านั้น
	โซลูชั่นที่ไม่มีที่สิ้นสุด
	การตัดสินใจเท่านั้น
	โซลูชั่นที่ไม่มีที่สิ้นสุด

ตัวอย่างที่ 2.2.1 การวางแผนการผลิตของสถานประกอบการตัดเย็บ (ปัญหาเรื่องชุดสูท)

มีการวางแผนที่จะเปิดตัวชุดสูทสองประเภท - ชายและหญิง ชุดสูทของผู้หญิงต้องใช้ขนแกะ 1 ม. ลาฟซาน 2 ม. และแรงงาน 1 วัน สำหรับผู้ชาย - ขนแกะ 3.5 ม., ลาฟซาน 0.5 ม. และแรงงาน 1 วัน โดยรวมแล้วมีขนแกะ 350 ม. ลาฟซาน 240 ม. และแรงงาน 150 วัน

จำเป็นต้องกำหนดจำนวนชุดที่ต้องทำแต่ละประเภทเพื่อให้ได้กำไรสูงสุดหากกำไรจากการขายชุดสูทผู้หญิงคือ 10 หน่วย หน่วยและจากชาย - 20 ถ้ำ หน่วย โปรดทราบว่าจำเป็นต้องเย็บชุดสูทผู้ชายอย่างน้อย 60 ชุด

ทางเศรษฐกิจ แบบจำลองทางคณิตศาสตร์งาน

ตัวแปร: เอ็กซ์, - จำนวนชุดสูทผู้หญิง x 2 -จำนวนชุดสูทผู้ชาย

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

ข้อ จำกัด:

ข้อจำกัดแรก (บนขนแกะ) มีรูปแบบ x ( + 3.5x 2 x ( + 3.5x 2 = 350 ผ่านจุด (350; 0) และ (0; 100) ข้อ จำกัด ที่สอง (ตาม lavsan) มีรูปแบบ 2x (+ 0.5x 2 2x x + 0.5x 2 = 240 ผ่านจุด (120; 0) และ (0; 480) ข้อจำกัดที่สาม (เรื่องแรงงาน) มีรูปแบบ xy + x 2 150. ทางตรง x ( + x 2 = 150 ผ่านจุด (150; 0) และ (0; 150) ข้อจำกัดที่สี่ (เกี่ยวกับจำนวนชุดสูทผู้ชาย) มีรูปแบบ x2> 60. วิธีแก้อสมการนี้คือระนาบครึ่งระนาบที่อยู่เหนือเส้นตรง x 2 = 60.

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

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

ในการสร้างเวกเตอร์ดังกล่าว คุณต้องเชื่อมต่อจุด (10; 20) กับจุดกำเนิด เพื่อความสะดวก คุณสามารถสร้างเวกเตอร์ตามสัดส่วนของเวกเตอร์ V ได้ ดังนั้น ในรูป 2.2.3 แสดงเวกเตอร์ (30; 60)

จากนั้นเราจะสร้างเส้นระดับ 10xj + 20x 2 = ก.ให้เราถือเอาฟังก์ชันเป้าหมายเป็นค่าคงที่ ก.การเปลี่ยนความหมาย กเราจะได้ตระกูลเส้นขนาน ซึ่งแต่ละเส้นเป็นเส้นระดับของฟังก์ชันวัตถุประสงค์

งาน. แก้ไขปัญหาการเขียนโปรแกรมเชิงเส้นแบบกราฟิกโดยกำหนดค่าสุดขีดของฟังก์ชันวัตถุประสงค์:

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

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

มาสร้างสมการ 3x 1 +x 2 = 9 กัน ที่สองจุด.
ในการค้นหาจุดแรก เราเท่ากับ x 1 = 0 เราพบ x 2 = 9 ในการค้นหาจุดที่สอง เราเท่ากับ x 2 = 0 เราพบ x 1 = 3 เราเชื่อมโยงจุด (0;9) กับ (3;0) โดยมีเส้นตรง. ให้เรานิยามระนาบครึ่งที่กำหนดโดยอสมการ เมื่อเลือกจุด (0; 0) แล้ว เราจะกำหนดเครื่องหมายอสมการในครึ่งระนาบ: 3 0 + 1 . 0 - 9 ≤ 0 เช่น 3x 1 +x 2 - 9≥ 0 ในระนาบครึ่งเหนือเส้นตรง
ลองสร้างสมการ x 1 +2x 2 = 8 กัน ที่สองจุด.
ในการค้นหาจุดแรก เราเท่ากับ x 1 = 0 เราพบ x 2 = 4 ในการค้นหาจุดที่สอง เราเท่ากับ x 2 = 0 เราพบ x 1 = 8 เราเชื่อมโยงจุด (0;4) กับ (8;0) โดยมีเส้นตรง. ให้เรานิยามระนาบครึ่งที่กำหนดโดยอสมการ เมื่อเลือกจุด (0; 0) แล้วเราจะกำหนดเครื่องหมายอสมการในครึ่งระนาบ: 1 0 + 2 . 0 - 8 ≤ 0 เช่น x 1 +2x 2 - 8≥ 0 ในระนาบครึ่งเหนือเส้นตรง
มาสร้างสมการ x 1 + x 2 = 8 กัน ที่สองจุด.
ในการค้นหาจุดแรก เราเท่ากับ x 1 = 0 เราพบ x 2 = 8 ในการค้นหาจุดที่สอง เราเท่ากับ x 2 = 0 เราพบ x 1 = 8 เราเชื่อมโยงจุด (0;8) กับ (8;0) โดยมีเส้นตรง. ให้เรานิยามระนาบครึ่งที่กำหนดโดยอสมการ เมื่อเลือกจุด (0; 0) แล้วเราจะกำหนดเครื่องหมายอสมการในครึ่งระนาบ: 1 0 + 1 . 0 - 8 ≤ 0 เช่น x 1 +x 2 - 8≤ 0 ในระนาบครึ่งระนาบใต้เส้นตรง

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

คุณสามารถตรวจสอบความถูกต้องของการสร้างกราฟฟังก์ชันได้โดยใช้เครื่องคิดเลข

พิจารณาฟังก์ชันวัตถุประสงค์ของโจทย์ F = 4x 1 +6x 2 → min
ลองสร้างเส้นตรงที่สอดคล้องกับค่าของฟังก์ชัน F = 0: F = 4x 1 +6x 2 = 0 เวกเตอร์เกรเดียนต์ที่ประกอบด้วยสัมประสิทธิ์ของฟังก์ชันวัตถุประสงค์ ระบุทิศทางของการย่อ F(X) จุดเริ่มต้นของเวกเตอร์คือจุด (0; 0) จุดสิ้นสุดคือจุด (4; 6) เราจะเคลื่อนเส้นตรงนี้ไปในลักษณะขนานกัน เนื่องจากเราสนใจวิธีแก้ปัญหาแบบขั้นต่ำสุด เราจึงเลื่อนเส้นตรงไปจนแตะพื้นที่ที่กำหนดก่อน บนกราฟ เส้นตรงนี้แสดงด้วยเส้นประ

ตรง ฉ(x) = 4x 1 +6x 2 ตัดกันพื้นที่ที่จุด B เนื่องจากจุด B ได้มาจากผลการตัดกันของเส้นตรง (1) และ (2) จากนั้นพิกัดของมันจะเป็นไปตามสมการของเส้นเหล่านี้:
3x 1 +x 2 =9
x 1 +2x 2 =8

เมื่อแก้ระบบสมการแล้วเราจะได้: x 1 = 2, x 2 = 3
เราจะหาค่าต่ำสุดของฟังก์ชันวัตถุประสงค์ได้อย่างไร:
ฉ(X) = 4*2 + 6*3 = 26

การแก้ปัญหาการเขียนโปรแกรมเชิงเส้น (LPP) โดยใช้วิธีการแบบกราฟิก

การกำหนดทั่วไปของโครงเรื่อง

ค้นหาค่าของตัวแปร n x 1 , x 2 , …, xn ที่ให้ค่าสุดขีด (ต่ำสุดหรือสูงสุด) ของฟังก์ชันเชิงเส้น Z=C 1 x 1 ,+ C 2 x 2+…+ C n x n

และปฏิบัติตามข้อจำกัดของแบบฟอร์มไปพร้อมๆ กัน

ก 1.1 x 1 +ก 1.2 x 2 +…+ก 1.n x nปอนด์ =≥b 1 ,

ก 2.1 x 1 +ก 2.2 x 2 +…+ก 2.n x n£ = ≥b 2 ,

. . . . . . . . . . . . . . . . . . . . . . .,

ม.,1 x 1 +ม.,2 x 2 +…+ม.,n x n£ = ≥b ม. ,

สำหรับให้ i,j , b i, C j (i=1,2,…,m; j=1,2,…,n) เครื่องหมายความสัมพันธ์สามารถรับค่าใดค่าหนึ่งในสามค่าที่กำหนดได้

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

ลองพิจารณาปัญหาต่อไปนี้ ผู้จัดการของบริษัทที่ผลิตสีสองประเภทได้อธิบายให้นักวิจัยปฏิบัติการทราบถึงสถานการณ์ในการผลิตและการตลาดของสี ปรากฎว่าโรงงานผลิตสีสองประเภท: สำหรับทาภายในและ งานภายนอก- เข้ามาทั้ง 2 สีครับ ขายส่ง- สำหรับการผลิตสีทั้งสอง สินค้าเดิม– A และ B ปริมาณสำรองรายวันสูงสุดที่เป็นไปได้ของผลิตภัณฑ์เหล่านี้คือ 6 และ 8 ตัน ตามลำดับ ประสบการณ์แสดงให้เห็นว่าความต้องการสีทาภายนอกในแต่ละวันไม่เกินความต้องการสีทาภายในมากกว่า 1 ตัน นอกจากนี้ยังพบว่าความต้องการสีทาภายนอกไม่เกิน 2 ตันต่อวัน ราคาขายส่งสำหรับสีหนึ่งตันมีดังนี้: 3,000 รูเบิลสำหรับสีภายนอกและ 2,000 รูเบิลสำหรับสีภายใน โรงงานควรผลิตสีแต่ละประเภทเท่าไรเพื่อเพิ่มยอดขายสูงสุด?

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

เมื่อสร้างแบบจำลองทางคณิตศาสตร์ ผู้วิจัยปฏิบัติการจะถามตัวเองสามคำถาม

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

เรามาแนะนำตัวแปรกัน:

x 1 – ปริมาณการผลิตสีภายนอกรายวัน (หน่วยเป็นตัน)

x 2 – ปริมาณการผลิตสีทาภายในรายวัน (หน่วยเป็นตัน)

กำลังพิจารณา ราคาขายส่งต่อตันของสีแต่ละประเภท รายได้รายวันจากการขายผลิตภัณฑ์ที่ผลิตจะได้รับจากฟังก์ชันวัตถุประสงค์เชิงเส้น Z = 3x 1 + 2x 2

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

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

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

2x 1 + x 2 £ 6 (สินค้า A 6 ตันในสต็อก)

x 1 + 2x 2 £ 8 (มีสินค้า B อยู่ในสต็อก 8 ตัน)

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

สถานการณ์การขายสีในตลาดนำไปสู่ข้อ จำกัด ดังต่อไปนี้: x 1 – x 2 £ 1 (สีภายนอกขายได้ไม่เกินหนึ่งตันมากกว่าสีภายใน), x 1 £ 2 (สีภายนอกขายไม่เกินหนึ่งตัน) เกินสองตันต่อวัน)

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

หา® สูงสุด( Z=2× x 1 + 3× x 2 ) โดยมีข้อจำกัดต่อไปนี้เกี่ยวกับค่าของตัวแปร x 1 และ x 2

2 × x 1 + x 2 £ 6 ข้อจำกัด (1),

X 1 + 2 × x 2 ปอนด์ 8 ข้อจำกัด (2),

X 1 - x 2 ปอนด์ 1 ข้อจำกัด (3)

X 1 £ 2 ข้อจำกัด (4)

และข้อกำหนดที่ว่าตัวแปร x 1 ³ 0 (5), x 2 ³ 0 (6) ต้องไม่เป็นลบ

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

วิธีการแบบกราฟิกสำหรับการแก้ปัญหา

วิธีการแก้ปัญหาแบบกราฟิกสามารถทำได้ในกรณีสองมิติเท่านั้น

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

ขั้นที่ 1 การสร้างขอบเขตของโซลูชันที่เป็นไปได้

เป้าหมายคือการสร้างพื้นที่ซึ่งทุกจุดเป็นไปตามข้อจำกัดทั้งหมด

ข้อจำกัดทั้งหกแต่ละข้อกำหนดครึ่งระนาบทางเรขาคณิต เพื่อสร้างมันขึ้นมา คุณต้องมี:

• · แทนที่เครื่องหมายอสมการในข้อจำกัดด้วยความเท่าเทียมกัน (เราได้สมการของเส้นตรง)

• · สร้างเส้นตรงโดยใช้จุดสองจุด

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

เราดำเนินการเหล่านี้สำหรับข้อจำกัดทั้งหมด เราแสดงแต่ละบรรทัดด้วยตัวเลขที่ใช้เมื่อกำหนดหมายเลขข้อจำกัด (ดูรูป)

พื้นที่ของการแก้ปัญหาที่เป็นไปได้ (เป็นไปตามข้อจำกัดทั้งหมด) คือเซตของจุดของจตุภาคแรกของระนาบพิกัด (x 1, x 2) ซึ่งเป็นจุดตัดของระนาบครึ่งทั้งหมดที่กำหนดโดยความไม่เท่ากันของข้อจำกัด

เซตของจุดที่เป็นไปตามข้อจำกัดทั้งหกประการของปัญหาคือ AFEDCB รูปหลายเหลี่ยม

ขั้นที่ 2: การสร้างเส้นระดับฟังก์ชันเป้าหมายและการกำหนดจุดสูงสุด

เป้าหมายคือการค้นหาในรูปหลายเหลี่ยม A ที่สร้างขึ้นFEDCB คือจุดที่ฟังก์ชันวัตถุประสงค์ Z=2x 1 + 3x 2 รับค่าสูงสุด

ลองวาดเส้นตรง 2x 1 + 3x 2 = Const (เส้นระดับ) เพื่อให้มันตัดกับรูปหลายเหลี่ยม AFEDCB (เช่น Const = 10) เส้นระดับนี้แสดงเป็นเส้นประในรูป

หากเราพิจารณาค่าของฟังก์ชันวัตถุประสงค์เชิงเส้น Z บนเซตของจุด (x 1 , x 2) ที่เป็นของส่วนของเส้นประที่อยู่ภายในรูปหกเหลี่ยม ค่าเหล่านั้นทั้งหมดจะเท่ากับค่าเดียวกัน (Const = 10)

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

การเปลี่ยนแปลงสามารถดำเนินต่อไปได้ตราบใดที่เส้นตรงที่กำลังเคลื่อนที่ตัดกับรูปหลายเหลี่ยมของคำตอบที่เป็นไปได้ ตำแหน่งสุดท้ายของเส้นเมื่อมีจุดร่วมหนึ่งจุดกับรูปหลายเหลี่ยม AFEDCB (จุด C) จะสอดคล้องกับ ค่าสูงสุดฟังก์ชั่นวัตถุประสงค์ Z และบรรลุที่จุด C ด้วยพิกัด x 1 = 4/3 (» 1.333), x 2 = 10/3 (» 3.333) ในกรณีนี้ Z = 38/3 (» 12.667)

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

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

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

ภารกิจที่ 1 (ทำในชั้นเรียนให้ครูดู)

แก้แบบกราฟิก

A) F =2 x 1 +3 x 2 และสูงสุด โดยมีข้อจำกัด x 1 +3 x 2 ≤ 18 2 x 1 + x 2 ≤ 16 x 2 ≤ 5 3 x 1 ≤ 21 x 1 ≥ 0 x 2 ≥ 0	B ) F =4 x 1 +6 x 2 และนาที โดยมีข้อจำกัด 3 x 1 + x 2 ≥ 9 x 1 +2 x 2 ≥ 8 x 1 +6x 2 ≥ 12 x 1 ≥ 0 x 2 ≥ 0
C ) F =3 x 1 +3 x 2 และสูงสุด โดยมีข้อจำกัด x 1 + x 2 ≤ 8 2x 1 -x 2 ≥ 1 x 1 -2x 2 ≤ 2 x 1 ≥ 0 x 2 ≥ 0	D ) F =2 x 1 -3 x 2 และนาที โดยมีข้อจำกัด x 1 + x 2 ≥ 4 2x 1 -x 2 ≥ 1 x 1 -2x 2 ≤ 1 x 1 ≥ 0 x 2 ≥ 0

ก) x1=6 x2=4 F=24

ข) x1=2 x2=3 F=26

ค) x1О x2=8-x1 F=24

ภารกิจที่ 2 (ทำในชั้นเรียนให้ครูดู)

ตอบคำถามเป็นตัวเอียง

ภารกิจที่ 3 (การบ้าน)

เขียนโปรแกรม.

แดน ไฟล์ข้อความใจดี

2 3 (สัมประสิทธิ์ฟังก์ชันวัตถุประสงค์)

4 (จำนวนข้อจำกัด)

2 2 12 (ข้อจำกัด)

1 2 8

4 0 16

0 4 12

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

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