โปรแกรมเชิงเส้น โปรแกรมเชิงเส้น - บทคัดย่อ การรวบรวมโปรแกรมอย่างง่าย

1.2 สั้น ๆ เกี่ยวกับโปรแกรมเชิงเส้นตรง

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

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

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

การเขียนโปรแกรมเชิงเส้นเป็นเทคนิคการเพิ่มประสิทธิภาพที่ใช้บ่อยที่สุด ปัญหาการเขียนโปรแกรมเชิงเส้นรวมถึง:

การใช้วัตถุดิบและวัสดุอย่างมีเหตุผล ตัดงานเพิ่มประสิทธิภาพ

· การเพิ่มประสิทธิภาพของโปรแกรมการผลิตขององค์กร

ตำแหน่งที่เหมาะสมและความเข้มข้นของการผลิต

จัดทำแผนที่เหมาะสมที่สุดสำหรับการขนส่ง การดำเนินการขนส่ง

การจัดการสต็อคการผลิต

และอื่น ๆ อีกมากมายที่อยู่ในสาขาการวางแผนที่เหมาะสมที่สุด

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

ข้อความแรกของปัญหาการเขียนโปรแกรมเชิงเส้นถูกกำหนดโดย L.V. Kantorovich นักคณิตศาสตร์ชาวโซเวียตที่มีชื่อเสียง ผู้ได้รับรางวัลโนเบลสาขาเศรษฐศาสตร์สำหรับผลงานเหล่านี้

ปัจจุบัน โปรแกรมเชิงเส้นตรงเป็นหนึ่งในเครื่องมือที่ใช้กันมากที่สุดของทฤษฎีทางคณิตศาสตร์ของการตัดสินใจที่เหมาะสมที่สุด

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

1.3 งานหลักของการเขียนโปรแกรมเชิงเส้น

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

{1.1}

และนอกจากนี้จะลดฟังก์ชันวัตถุประสงค์เชิงเส้น (TF)

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

คำตอบที่ยอมรับได้ของ OLP คือชุดของตัวแปรใดๆ ที่เป็นไปตามสมการ (1.1)

ทางออกที่ดีที่สุดคือโซลูชันที่เป็นไปได้ ซึ่งตัวกรองดิจิทัลจะกลายเป็นขั้นต่ำ

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

พิจารณาปัญหาการโปรแกรมเชิงเส้นที่มีข้อจำกัดความไม่เท่าเทียมกันที่มีรูปแบบ

{1.2}

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

มาแนะนำสมการกัน:

{1.3}

โดยที่ตัวแปรเพิ่มเติมซึ่งไม่เป็นค่าลบด้วย

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

สัมประสิทธิ์ในสูตร (1.3) ก่อนหน้ามีค่าเท่ากับศูนย์

1.3. การสร้างข้อจำกัดและการไล่ระดับของฟังก์ชันวัตถุประสงค์: 1.4 พื้นที่ของการแก้ปัญหาที่เป็นไปได้คือส่วน AB 1.5. จุด A เหมาะสมที่สุด พิกัด A: ; ; . 2. การแก้ปัญหาการโปรแกรมเชิงเส้นโดยวิธีซิมเพล็กซ์ งานโดยตรง ปัญหาการเขียนโปรแกรมเชิงเส้นสำหรับจุดยอดในรูปแบบกะทัดรัดสามารถแสดงเป็น: เพื่อให้ได้มาเราใช้อัลกอริธึมที่ให้ไว้ใน ...

รังสีที่เปล่งออกมาจากจุดหนึ่งเรียกว่ากรวยนูนหลายหน้าที่มีจุดยอดอยู่ที่จุดนี้ 1.4 พื้นฐานทางคณิตศาสตร์สำหรับการแก้ปัญหาการโปรแกรมเชิงเส้นแบบกราฟิก 1.4.1 เครื่องมือทางคณิตศาสตร์ เพื่อให้เข้าใจทุกอย่างมากขึ้น การรู้และจินตนาการถึงการตีความทางเรขาคณิตของปัญหาโปรแกรมเชิงเส้นตรงที่สามารถกำหนดได้สำหรับกรณี n = 2 และ n = ...

งาน f1(x)=max=g1(x) – สำหรับองค์กรแรก; - สำหรับสถานประกอบการอื่นๆ การแก้ปัญหาการกระจายเงินที่เหมาะสมที่สุดระหว่างองค์กรโดยวิธีการเขียนโปรแกรมแบบไดนามิก ตารางที่ 12 กองทุนที่มีพันกรัม โรงงาน 1 2 3 4 G1(x) G2(x) G3(x) G4(x) 20 11 13 12 10 40 21 20 22 27 60 40 42 34 33 80 54 45 55 57 100 62 62 ...

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

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

งาน 1.1. การคำนวณสูตร

เขียนโปรแกรมที่แปลงอุณหภูมิในฟาเรนไฮต์เป็นเซลเซียสโดยใช้สูตร:

โดยที่ C คืออุณหภูมิในเซลเซียสและ F คืออุณหภูมิในฟาเรนไฮต์

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

ในกรณีนี้:

ข้อมูลเริ่มต้นคือจำนวนจริงหนึ่งจำนวนที่แสดงอุณหภูมิเป็นเซลเซียส

ผลที่ได้คือจำนวนจริงอีกจำนวนหนึ่ง

ก่อนเขียนโปรแกรม เรามาเปิด Visual C++ IDE กันก่อน:

เริ่ม/โปรแกรม/Microsoft Visual Studio/ Microsoft Visual C++ 6.00

1) ไฟล์ > ใหม่...

2) ในหน้าต่างที่เปิดอยู่:

เลือกประเภทแอปพลิเคชันคอนโซล Win32

ป้อนชื่อโครงการในกล่องข้อความชื่อโครงการ

ป้อน (เลือกโดยใช้ปุ่ม ...) ชื่อของไดเร็กทอรีที่ไฟล์โครงการอยู่ในฟิลด์ข้อความ Location เช่น G: / ASOIZ /

คลิกปุ่มซ้ายของเมาส์ที่ปุ่มตกลง

3) แอปพลิเคชันคอนโซล Win32 - กล่องโต้ตอบ Stepl of 1 จะเปิดขึ้นและในนั้น:

เลือกประเภท โครงการที่ว่างเปล่า

คลิกปุ่มเสร็จสิ้น

4) หลังจากคลิกแล้ว หน้าต่าง New Project จะปรากฏขึ้น โดยคลิกที่ปุ่ม OK

1) ไฟล์ > ใหม่.... ซึ่งจะเปิดกล่องโต้ตอบใหม่

2) บนแท็บไฟล์:

เลือกประเภทไฟล์ (ในกรณีนี้: C++ Source File);

ในช่องข้อความชื่อไฟล์ ให้ป้อนชื่อไฟล์ที่ต้องการ

ต้องเปิดใช้งานช่องกาเครื่องหมายเพิ่มในโครงการ

คลิกปุ่มตกลง

เราพิมพ์ข้อความโปรแกรมต่อไปนี้:

ลองพิจารณาแต่ละบรรทัดของโปรแกรมแยกกัน

ที่จุดเริ่มต้นของโปรแกรมมีการเขียนคำสั่งตัวประมวลผลล่วงหน้าตามที่ไฟล์ส่วนหัวเชื่อมต่อกับซอร์สโค้ดของโปรแกรม . นี่คือไฟล์ที่มีคำอธิบายของคำสั่ง cin และ cout I/O

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

ช่องว่างใด ๆ เมื่อเขียนโปรแกรมมีรูปแบบ:

#รวม<…>

#รวม<…>

การประกาศตัวแปร

การป้อนข้อมูลเริ่มต้น

การคำนวณผลลัพธ์

ผลลัพธ์ผลลัพธ์;

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

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

ประเภทหลัก:

int (สั้น, ไม่ได้ลงนาม) - จำนวนเต็ม,

float (ดับเบิ้ล, ดับเบิ้ลยาว) – จริง

ถ่าน - ตัวอักษร

บูล - บูลีน

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

ในคำสั่ง 4 ป้อนตัวเลขเดียวจากแป้นพิมพ์ลงในตัวแปร fahr. สำหรับสิ่งนี้จะใช้วัตถุมาตรฐาน ซินและการแยก (อ่าน) การดำเนินการ >> หากคุณต้องการป้อนค่าหลายค่า ให้ใช้ chain of operation >>

ในตัวดำเนินการ 5 นิพจน์ที่เขียนทางด้านขวาของ การดำเนินงานที่ได้รับมอบหมาย(แสดงด้วยเครื่องหมาย =) และผลลัพธ์ถูกกำหนดให้กับเซลล์ของตัวแปร กล่าวคือ มันถูกป้อนลงในหน่วยความจำที่จัดสรรให้กับตัวแปรนี้ ตั้งแต่แรก ทั้งหมด ค่าคงที่ 5 จะถูกหารด้วย จูบ ค่าคงที่ 9 จากนั้นผลลัพธ์ของการดำเนินการนี้จะถูกคูณด้วยผลลัพธ์ของการลบตัวเลข 32 ออกจากตัวแปร fahr

เพื่อแสดงผลลัพธ์ในคำสั่ง 6 วัตถุจะใช้ ศาลสตริงที่ประกอบด้วยห้าองค์ประกอบจะปรากฏขึ้น นี่คือสตริง "ฟาเรนไฮต์:", ค่าตัวแปร fahr, ไลน์ ", หน่วยเป็นองศาเซลเซียส:", ค่าตัวแปร เซลล์และตัวดำเนินการกระโดด บรรทัดใหม่ ปลาย

คำสั่งสุดท้าย (คำสั่ง 7) ของโปรแกรมนี้ออกแบบมาเพื่อส่งคืนและโอนค่าไปยังสภาพแวดล้อมภายนอก

ต่อไปเราจะคอมไพล์โปรแกรม ในการดำเนินการนี้ ให้กดปุ่มบนแถบเครื่องมือหรือคีย์ผสม Ctrl + F7 หน้าต่างแสดงผล (ด้านล่างของหน้าจอ) ควรแสดงข้อความ ข้อผิดพลาด 0 รายการ คำเตือน 0 รายการ (0 ข้อผิดพลาด 0 คำเตือน) หากมีข้อผิดพลาดให้ตรวจสอบกับต้นฉบับ

หากต้องการเริ่มโปรแกรม ให้กดปุ่มบนแถบเครื่องมือหรือกดคีย์ผสม Ctrl + F5

เวลารันโปรแกรมแทนอักษรรัสเซียเราจะเห็น ??? ซึ่งเกิดจากมาตรฐานการเข้ารหัสอักขระซิริลลิกใน ระบบปฏิบัติการ MS DOS และ Windows หากต้องการแก้ไข ให้เพิ่มฟังก์ชัน CharToOem ลงในโปรแกรม (ส่วนเสริมจะไฮไลต์ด้วยสีแดงเพื่อความชัดเจน)

#รวม

#รวม

ถ่าน* RUS(const ถ่าน* ข้อความ)

CharToOem(ข้อความ, บัฟ);

ค่าโดยสารลอยตัว, เซล;

ศาล<

เซลล์=5/9 * (fahr - 32);

ศาล<

ศาล<

การทำงาน มาตุภูมิ()ไม่สามารถใช้งานได้มากกว่าหนึ่งครั้งในห่วงโซ่การดำเนินงาน<< для одного объекта ศาลดังนั้นเราจึงแยกออกเป็นสองส่วน

อย่างที่คุณเห็น ผลลัพธ์ของการรันโปรแกรมด้วยความเสถียรนั้นเป็นศูนย์! นี่เป็นเพราะวิธีการประเมินนิพจน์ ลองดูตัวดำเนินการ 4 อีกครั้ง ค่าคงที่ 5 และ 9 เป็นประเภทจำนวนเต็ม ดังนั้นผลลัพธ์ของการหารจึงเป็นจำนวนเต็มด้วย โดยธรรมชาติแล้ว ผลลัพธ์ของการคำนวณเพิ่มเติมไม่สามารถเป็นอย่างอื่นได้นอกจากศูนย์ การแก้ไขข้อผิดพลาดนี้ทำได้ง่าย เพียงเขียนค่าคงที่อย่างน้อยหนึ่งค่าเป็นจำนวนจริง เช่น

เซล = 5. / 9 * (fahr - 32);

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

ตัวแปร

ตัวแปรคือค่าที่ในขณะที่โปรแกรมกำลังทำงานอยู่ สามารถ -

เปลี่ยนค่าของมัน ตัวแปรทั้งหมดที่ใช้ในโปรแกรมจะต้องประกาศในส่วนการประกาศตัวแปรที่ขึ้นต้นด้วยคีย์เวิร์ด var

ตัวแปรแต่ละตัวจะได้รับชื่อและประเภท เช่น

หมายเลข var: จำนวนเต็ม; x, y: จริง; ตัวเลือก: ถ่าน;

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

ประเภทของตัวแปรจะถูกเลือกตามช่วงและความแม่นยำที่ต้องการของการแสดงข้อมูล

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

จำนวน const: จำนวนเต็ม = 100; x: จริง = 0.02; ตัวเลือก: ถ่าน = "u";

โดยค่าเริ่มต้น ตัวแปรทั้งหมดที่ประกาศในโปรแกรมหลักจะถูกตั้งค่าเป็นศูนย์

นิพจน์

นิพจน์คือกฎสำหรับการประเมินค่า ในการแสดงออกที่เกี่ยวข้อง -

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

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

• 1. Unary operation ไม่ unary ลบ - ใช้ที่อยู่ @
• 2. การดำเนินการเช่นการคูณ: * / div mod และ shl shr
• 3. การดำเนินการประเภทเพิ่มเติม: + - หรือ xor
• 4. การดำเนินการเชิงสัมพันธ์: = o = นิ้ว

ฟังก์ชันที่ใช้ในนิพจน์จะได้รับการประเมินก่อน

ตัวอย่างนิพจน์:

t + sin (x) / 2 * x - ผลลัพธ์เป็นประเภทจริง เอ

(x > 0) และ (y

โครงสร้างโปรแกรม

โปรแกรม PASCAL ประกอบด้วยส่วนหัวที่เป็นทางเลือก ส่วนคำอธิบาย และส่วนคำสั่ง:

ชื่อโปรแกรม; (ส่วนหัว) ส่วนการประกาศเริ่มต้นส่วนคำสั่งสิ้นสุด (* โปรแกรมลงท้ายด้วยจุด *)

โปรแกรมอาจมี ความคิดเห็นอยู่ในวงเล็บปีกกา () หรือวงเล็บของแบบฟอร์ม (* *)

โครงสร้างทั่วไปของโปรแกรมแสดงในรูปที่ 2.1.

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

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

โมดูลคือไลบรารีของทรัพยากร (รูทีนย่อย ค่าคงที่ ฯลฯ) ที่เชื่อมต่อกับโปรแกรม

ข้าว. 2.1.

ส่วนคำอธิบายโมดูล หากมี จะต้องมาก่อน คำอธิบายเริ่มต้นด้วยการใช้คำสำคัญ ตามด้วยรายการที่คั่นด้วยเครื่องหมายจุลภาคของโมดูลทั้งหมดที่เชื่อมต่อกับโปรแกรม ทั้งแบบมาตรฐานและแบบกำหนดเอง เช่น ใช้ crt, กราฟ, my_module;

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

ในส่วนการประกาศตัวแปร คุณต้องกำหนดตัวแปรทั้งหมดที่จะใช้ในโปรแกรมหลัก

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

น้ำหนักสุทธิ: จริง = 61.5; n = 10;

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

ป้ายกำกับใช้เพื่อจัดระเบียบการเปลี่ยนไปยังผู้ปฏิบัติงานเฉพาะโดยใช้ โอเปอเรเตอร์กระโดดแบบไม่มีเงื่อนไขไปที่.

ขั้นตอนอินพุต-เอาต์พุต โปรแกรมใดๆ เมื่อป้อนข้อมูลเริ่มต้นและผลลัพธ์เอาต์พุต จะโต้ตอบกับอุปกรณ์ภายนอก ชุดอุปกรณ์อินพุตและเอาต์พุตมาตรฐาน เช่น แป้นพิมพ์และหน้าจอแสดงผลเรียกว่า คอนโซล

อินพุตคีย์บอร์ด ขั้นตอนต่อไปนี้ถูกกำหนดไว้สำหรับการป้อนข้อมูลด้วยแป้นพิมพ์: read และ readln: read(list); readln [(รายการ)];

วงเล็บประกอบด้วยรายชื่อตัวแปรที่คั่นด้วยเครื่องหมายจุลภาค วงเล็บเหลี่ยมระบุว่ารายการอาจขาดหายไป ตัวอย่างเช่น:

อ่าน (a, b, c); readln(y); อ่าน;

ความสนใจ

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

การป้อนค่าของตัวแปรแต่ละตัวทำได้ดังนี้:

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

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

คุณลักษณะการป้อนอักขระและสตริงคืออักขระช่องว่างในนั้นไม่ต่างจากอักขระอื่นทั้งหมด ดังนั้นจึงไม่สามารถเป็นตัวคั่นได้

เอาท์พุทบนจอแสดงผล ที่เอาต์พุต การแปลงแบบย้อนกลับจะดำเนินการ: จากการแสดงภายในไปจนถึงอักขระที่แสดงบนหน้าจอ ในการทำเช่นนี้ ภาษากำหนดขั้นตอนมาตรฐาน write และ writeln: write (list); writeln [(รายการ)];

ขั้นตอนการเขียนจะพิมพ์ค่าที่ระบุในรายการไปที่หน้าจอ และขั้นตอน writeln จะย้ายเคอร์เซอร์ไปที่บรรทัดถัดไปด้วย ขั้นตอน writeln ที่ไม่มีพารามิเตอร์จะเลื่อนเคอร์เซอร์ไปที่บรรทัดถัดไป

คุณสามารถส่งออกค่าของประเภทตรรกะ จำนวนเต็ม จำนวนจริง อักขระและสตริง รายการนี้ไม่เพียงแต่ประกอบด้วยชื่อตัวแปรเท่านั้น แต่ยังรวมถึงนิพจน์และค่าคงที่กรณีพิเศษของพวกมันด้วย นอกจากนี้ สำหรับแต่ละค่าเอาต์พุต คุณสามารถตั้งค่าได้ รูปแบบ,ตัวอย่างเช่น: writeln(a:4, b:6:2);

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

15. วิธีการวิเคราะห์ วิธีการโปรแกรมเชิงเส้น

15.1. วิธีการวิเคราะห์

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

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

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

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

ส่วนสำคัญของวิธีการปรับให้เหมาะสมคือการเขียนโปรแกรมเชิงเส้น

15.2. แนวคิดการเขียนโปรแกรมเชิงเส้นพื้นฐาน

วิธีการทางคณิตศาสตร์ที่กล่าวถึงครั้งแรก (1938) ในการจัดการการผลิตอย่างมีประสิทธิภาพเป็นของนักคณิตศาสตร์โซเวียต L. V. Kantorovich อีกหนึ่งปีต่อมาในปี พ.ศ. 2482 แอล. วี. คันโตโรวิช ตีพิมพ์ผลงาน "วิธีการทางคณิตศาสตร์สำหรับองค์กรและการวางแผนการผลิต" และนำผลที่ได้รับไปใช้จริง คำว่า "โปรแกรมเชิงเส้น" ถูกนำมาใช้โดยนักคณิตศาสตร์ชาวอเมริกัน J. Danzig และ T. Koopmans ในช่วงปลายยุค 40 J. Dantzig พัฒนาเครื่องมือทางคณิตศาสตร์ของวิธีซิมเพล็กซ์สำหรับการแก้ปัญหาโปรแกรมเชิงเส้นตรง (1951) วิธีแบบซิมเพล็กซ์จะค้นหาแอปพลิเคชันสำหรับแก้ปัญหาการเขียนโปรแกรมเชิงเส้นแบบต่างๆ และยังคงเป็นหนึ่งในวิธีการหลัก

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

มีเอกลักษณ์เฉพาะสำหรับงานที่กำหนด

วัดเป็นหน่วยปริมาณ

เชิงเส้นขึ้นอยู่กับพารามิเตอร์อินพุต

จากที่กล่าวมา เราสามารถกำหนดปัญหาการโปรแกรมเชิงเส้นในรูปแบบทั่วไป:

หาปลายสุดของฟังก์ชันวัตถุประสงค์

ภายใต้ข้อจำกัดในรูปแบบของความเท่าเทียมกัน:

(2.2)

ภายใต้ข้อจำกัดในรูปแบบของความไม่เท่าเทียมกัน:

(2.3)

และเงื่อนไขที่ไม่เป็นลบของพารามิเตอร์อินพุต:

ในรูปแบบสั้น ปัญหาการเขียนโปรแกรมเชิงเส้นสามารถเขียนได้ดังนี้:

(2.5)

เนื่องจาก

ที่ไหน
- ตัวแปรอินพุต;

ตัวเลขบวกลบและเท่ากับศูนย์

ในรูปแบบเมทริกซ์ ปัญหานี้สามารถเขียนได้ดังนี้:

ปัญหาการเขียนโปรแกรมเชิงเส้นสามารถแก้ไขได้ในเชิงวิเคราะห์และแบบกราฟิก

15.3. ปัญหาการเขียนโปรแกรมเชิงเส้นตรงที่เป็นที่ยอมรับ

, ผม=1,…,ม,

, j=1,…,น.

วิธีการคำนวณหลักสำหรับการแก้ปัญหาการโปรแกรมเชิงเส้นได้รับการพัฒนาโดยเฉพาะสำหรับปัญหาตามรูปแบบบัญญัติ

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

จำเป็นต้องเพิ่ม (ย่อเล็กสุด) ฟังก์ชันเชิงเส้นของ นตัวแปร

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

, ฉัน=1,…, k,

, ฉัน=1+ k,…, ม,

, …,

ที่นี่ k≤ ม, r≤ น. ปัญหามาตรฐานได้มาจากกรณีพิเศษของปัญหาทั่วไปสำหรับ k= ม, r= น; บัญญัติ - at k=0, r= น.

ตัวอย่าง.

โรงงานผลิตขนมผลิตขนมหลายชนิด เรียกพวกเขาว่า "A", "B" และ "C" เป็นที่ทราบกันว่าการขายขนม "A" สิบกิโลกรัมให้ผลกำไร 90 รูเบิล, "B" - 100 รูเบิลและ "C" - 160 รูเบิล แคนดี้สามารถผลิตได้ในปริมาณเท่าใดก็ได้ (รับประกันการขาย) แต่วัตถุดิบมีจำนวนจำกัด มีความจำเป็นต้องกำหนดว่าขนมใดและต้องผลิตกี่สิบกิโลกรัมเพื่อให้กำไรรวมจากการขายสูงสุด อัตราการใช้วัตถุดิบในการผลิตขนมแต่ละประเภท 10 กก. แสดงไว้ในตารางที่ 1

ตารางที่ 1 อัตราการใช้วัตถุดิบ

เพื่อการผลิต

สูตรทางเศรษฐศาสตร์และคณิตศาสตร์ของปัญหามีรูปแบบ

ค้นหาค่าตัวแปรดังกล่าว X=(x1, x2, x3), ถึง

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

ภายใต้เงื่อนไข-ข้อจำกัด: