งานวิจัย

การวิจัยดำเนินงาน

  Operations research

โปรแกรมเชิงเส้น   (Linear Programming)

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

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

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

            1.  ขนาดขีดความสามารถในการผลิตของเครื่องจักรและแรงงาน

            2.  ปริมาณความต้องการของตลาด

            3.  ปริมาณวัตถุดิบและพลังงานอื่นๆ ในการผลิตเช่น น้ำ น้ำมัน ไฟฟ้า มีอยู่ในจำนวนจำกัด

            4.  เงินทุนจำกัด    5.  อื่นๆ

            เทคนิคทางการโปรแกรมเชิงเส้นตรง ในการวิจัยดำเนินงานนี้พัฒนามาจากผลความก้าวหน้าทางวิทยาศาสตร์ ซึ่งมีนักคิดชาวคณิตศาสตร์และนักวิทยาศาสตร์หลายๆ ท่าน เช่น

            ฟอน นิวแมน เริ่มใช้ทฤษฏี สูงสุด - ต่ำสุด ในทฤษฏีของเกมในปี 1928 และถูกพัฒนานำไปใช้ในปัญหาทางการขนส่งในปี 1941

            ในปี 1945 โดยจอร์ช สติคเลอร์ ได้นำเทคนิคดังกล่าวนำไปใช้ในการแก้ปัญหาทางการโภชนาการ

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

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

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

1.  การวางแผนการผลิต และการลงทุน

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

2.  การผสมส่วนวัตถุดิบ

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

3.  การจัดลำดับและการกระจายงาน

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

4.  เกมและกลวิธี

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

5.  ปัญหาอื่นๆ

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

รูปแบบแทนระบบของการโปรแกรมเชิงเส้นตรง

            1.  มีสมการกำหนดเป้าหมาย (Objective function) คือสมการแสดงความสัมพันธ์ของต้นทุน กำไร เพื่อให้กำหนดเป้าหมายสูงสุดหรือต่ำสุด

            2.  มีสมการแสดงของข่าย (Constraints) ซึ่งแสดงความจำกัดของปัจจัยหรือทรัพยากรในรูปสมการหรืออสมการ

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

            4.  ตัวแปรทุกตัวต้องมีค่ามากกว่าหรือเท่ากับศูนย์ (All positive value)

            จากรูปแบบของโปรแกรมเชิงเส้นตรงนี้ จะเห็นได้ว่าตัวค่าวัดผลการดำเนินงานจะได้จากสมการกำหนดเป้าหมายซึ่งเราจะต้องพยายามหาค่าเป็นไปตามเป้าหมายโดยเทคนิคที่มีอยู่ ตัวแปรต่างๆ จะเป็นตัวแทนจำนวนปริมาณหรือค่าของปัจจัยที่มีอยู่จำกัดโดยการกำหนดของสมการหรืออสมการ ในขอบข่ายของปัญหา  ผลการวิเคราะห์จะได้เป็นค่าตัวแปรที่จะนำไปตัดสินใจเพื่อดำเนินการให้ได้ตามเป้าหมาย เช่น กำหนดให้สินค้าต้องใช้วัตถุดิบชนิดหนึ่ง ปริมาณที่มีอยู่จำกัดในจำนวน 10 ตัน จะได้สมการขอบข่ายเป็น “น้อยกว่าหรือเท่ากับ 10 ตัน สำหรับปริมาณวัตถุที่ใช้นั้นๆ หรือกำหนดว่าปริมาณการขายสำหรับสินค้าชนิดนั้นต่ำสุดเป็น 20,000 ชิ้น ทำให้เกิดอสมการ “มากกว่าหรือเท่ากับ 20,000 ชิ้น” สำหรับปริมาณการขายเป็นต้น

            ตัวอย่างรูปแบบแทนระบบของการโปรแกรมเชิงเส้นตรง เพื่อให้หาค่าของตัวแปร เช่น X1, X2,……,Xn ที่ทำให้ผลการดำเนินงานที่มีค่าสูงสุดตามสมการเป้าหมายดังนี้

สมการเป้าหมาย      Max.Z  =             C1X1+C2X2+…….+CnXn

สมการหรืออสมการขอบข่าย              a11X1+a12X2+…+a1nXn  <= b1

                                                            a21X1+a22X2+…+a2nXn  <= b2

                                                            am1X2+am2X2+…+amnXn  <= bm

Xi >= 0 ; I = 1,2,…,n

โดยมี               Z = F(Xi)  เป็นสมการเป้าหมาย

                                    Xi         เป็นค่าตัวแปรที่แทนค่าของปัจจัย

                                    aij, Cj   เป็นค่าสัมประสิทธิ์ของตัวแปรที่มีค่าคงที่

                                    bj         เป็นปริมาณทรัพยากรที่จะนำมาใช้ในแต่ละกิจการซึ่งมีค่าคงที่

ขั้นตอนการดำเนินการของโปรแกรมเชิงเส้นตรง

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

1.  การจัดตั้งรูปแบบแทนระบบของปัญหา

     ก. สมการกำหนดเป้าหมาย

     ข. สมการหรืออสมการที่แสดงความสัมพันธ์ของตัวแปรภายใต้ขอบข่ายต่างๆที่มีอยู่

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

2.  การหาผลลัพธ์ของรูปแบบแทนระบบของปัญหา

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

ก. ในกรณีที่เป็นปัญหาที่มีตัวแปรเป็น 2 ตัวเราอาจใช้วิธี

            1.  วิธีกำจัดขอบข่ายของคำตอบ

            2.  วิธีอนุมานทางคณิตศาสตร์

            3.  วิธีกราฟ

ข. ในกรณีที่เป็นปัญหาที่มีตัวแปรมากกว่า 2 ตัว เราอาจใช้
            1.  วิธีทางพีชคณิตทั่วๆ ไป
            2.  วิธี Simplex method           

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

การพิจารณาปัญหา โปรแกรมเชิงเส้นตรงแบบธรรมดา

            1. ในกรณีที่เป็นปัญหาที่มีตัวแปรเป็น 2 ตัวเราอาจใช้วิธี   วิธีกำจัดขอบข่ายของคำตอบ  โดยวิธีอนุมานทางคณิตศาสตร์   วิธีกราฟ

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

ลักษณะของปัญหาการโปรแกรมเชิงเส้น

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

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