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

ความคิดเห็น

7

ติดตามกระทู้

2

แชร์กระทู้นี้
จำนวนแชร์
4

กระทู้ที่เปิดอ่านล่าสุด

บทความที่ถูกแชร์เยอะที่สุด

  • โอ้โหเด็ด

  • น่ารักสุดๆ

  • หรูเริด

  • ตลกอ่ะ

  • เครียด

  • สู้ๆ สู้ตาย

  • ช็อค

  • โกรธ

  • ล้มโต๊ะ


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

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

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

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

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

2. มีสมการแสดงขอบข่าย (constraints) ซึ่งแสดงข้อจำกัดต่างๆของปัจจัยหรือทรัพยากรในรูปสมการหรืออสมการ
โดยที่สมการต่างๆ ทั้งหมดเป็นสมการเชิงเส้น เมื่อเทียบกับตัวแปร

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

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

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

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

1. จัดรูปแบบแทนระบบของปัญหา (Model Formulation)
ก่อนอื่นต้องศึกษาข้อมูลองค์ประกอบของปัญหาให้เข้าใจ โดยเลือกเฉพาะองค์ประกอบที่สำคัญและมีอิทธิพลมาก แล้วจัดตั้งตัวแปรแทนส่วนประกอบของปัญหานั้นๆ ให้ถูกต้อง

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

การจัดตั้งรูปแบบแทนระบบของปัญหา (Model Formulation)
ในการจัดตั้งรูปแบบแทนระบบของปัญหาโดยใช้โปรแกรมเชิงเส้น เราต้องทำความเข้าใจและศึกษาปัญหาอย่างชัดเจน นอกจากนี้ยังต้องสามารถระบุสิ่งต่อไปนี้ในปัญหา
1. ตัวแปรตัดสินใจ หรือเรียกสั้นๆ ว่า ตัวแปร (decision variables) ซึ่งคือตัวแปรที่สำหรับใส่เข้าไปในระบบ และเป็นตัวแปรที่เราสามารถจะควบคุมได้ ตัวแปรนี้เป็นสิ่งสำคัญที่เราจะป้อนเข้าไปในระบบเพื่อให้เกิดประโยชน์สูงสุด ตัวอย่างเช่น จำนวนสินค้าที่จะผลิตซึ่งเป็นตัวแปรที่เราควบคุมได้
2. พารามิเตอร์เป็นค่าในระบบที่เราไม่สามารถควบคุมได้ ตัวอย่างเช่นราคาสินค้าซึ่งขึ้นอยู่กับกลไกตลาด
3. สมการกำหนดเป้าหมาย (objective function) คือสมการแสดงความสัมพันธ์ของต้นทุน กำไร เพื่อให้กำหนดเป้าหมายสูงสุดหรือต่ำสุด
4. สมการแสดงขอบข่าย (constraints) ซึ่งแสดงข้อจำกัดต่างๆของปัจจัยหรือทรัพยากรในรูปสมการหรืออสมการ

เมื่อจัดตั้งรูปแบบแทนระบบของปัญหาโดยเขียนให้อยู่รูปแบบทางคณิตศาสตร์ รูปแบบที่ได้จะเป็นรูปแบบของโปรแกรมเชิงเส้นก็ต่อเมื่อมีคุณสมบัติต่อไปนี้
1. สมการกำหนดเป้าหมายจะต้องเป็นเชิงเส้น นั่นคือ ตัวแปรทุกตัวจะต้องมีกำลังเป็น 1 เท่านั้น นอกจากนี้จะต้องเขียนอยู่ในรูปของ การบวกและการลบของตัวแปรต่างๆ เท่านั้น ตัวอย่างเช่น 2x+3y เป็นเชิงเส้น เพราะตัวแปร x และ y มีกำลังเท่ากับ 1 และตัวแปรอยู่ในรูปของผลบวก แต่ 2xy ไม่เป็นเชิงเส้นเนื่องจากตัวแปรอยู่ในรูปของผลคูณของตัวแปร x และ y
2. สมการกำหนดเป้าหมายจะต้องระบุว่าต้องการหาค่าต่ำสุดหรือสูดสุด สมการกำหนดเป้าหมายจะต้องแสดงถึงจุดประสงค์ในการตัดสินใจ เช่น การหากำไรสูงสุด ค่าใช้จ่ายต่ำสุด
3. สมการแสดงขอบเขตเป็นเชิงเส้น นอกจากนี้จะต้องเขียนให้อยู่ในรูปของ \geq , \leq ,หรือ = เท่านั้น (ถ้าสมการอยู่ในรูปของ < หรือ > รูปแบบนี้จะไม่ใช้ปัญหาของโปรแกรมเชิงเส้น)

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

\displaystyle \begin{array}{rcl}\textrm{Min/Max}&z=\sum_{j=1}^n c_jx_j&\textrm{Subject to}&{\begin{array}{rc}\sum_{j=1}^n a_{ij}x_j(\geq,\leq,=)b_i&\textrm{for}\ i=1,\ldots,m\x_j\geq0&\textrm{for}\ j=1,2,\ldots,n\end{array}}\end{array}

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

ตัวอย่าง Diet Problem

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

อาหาร (ประเภท)
1234ปริมาณสารอาหารที่ต้องการ
โปรตีน8012060100700
วิตามิน3001010250
เหล็ก1510205300
ราคา (ต่อหน่วย)40652050


ตารางข้างต้นแสดงพารามิเตอร์ต่างๆ สำหรับปัญหาข้างต้น เราจะเห็นได้ว่าอาหารประเภทที่ 1 มีโปรตีนอยู่ 80 กรัม วิตามิน 30 กรัม และ เหล็ก 20 กรัม โดยที่อาหารประเภทนี้มีราคา 40 บาท ในทำนองเดียวกัน อาหารประเภทที่ 2 มีราคา 65 บาทมีสารอาหารโปรตีน 120 กรัม วิตามิน 0 กรัม และ เหล็ก 10 กรัม ปริมาณสารอาหารแต่ละชนิดที่ร่างกายเราต้องการมีดังนี้ โปรตีนเราต้องการอย่างน้อย 700 กรัม วิตามิน 250 กรัม และ เหล็ก 300 กรัม ตัวแปรตัดสินใจ คือปริมาณสารอาหารในแต่ละประเภทที่ควรจะบริโภค กำหนดให้ตัวแปรเหล่านี้คือ x_1,x_2,x_3,x_4 แทนปริมาณอาหารในแต่ละประเภท จุดมุ่งหมายคือต้องการหาค่าตัวแปร x_1,x_2,x_3,x_4 โดยที่ร่างกายจะต้องได้ปริมาณสารอาหารแต่ละชนิดครบตามความต้องการ โดยที่เสียค่าใช้จ่ายน้อยที่สุด

เมื่อเราได้ตัวแปรและค่าพารามิเตอร์ต่างๆแล้วขั้นตอนไปก็คือหาสมการกำหนดเป้าหมาย ซึ่งคือผลรวมทั้งหมดราคาของอาหารทุกประเภท จากตารางข้างต้น ราคาของอาหารประเภทที่ 1 มีค่าเท่ากับ 40x1 40x_1ราคาของอาหารประเภทที่ 2 มีค่าเท่ากับ 65x_2เราสามารถหาราคาของอาหารประเภทที่ 3 และ 4 ได้ เราจะได้ว่าค่าใช้จ่ายทั้งหมดคือ 40x_1+65x_2+20x_3+50x_4 จุดประสงค์ของสมการกำหนดเป้าหมายคือลดค่าใช้จ่ายให้น้อยที่สุด นั่นคือเราต้องการหาค่า x_1,x_2,x_3,x_4 ที่ทำให้ 40x_1+65x_2+20x_3+50x_4 มีค่าต่ำสุด สมการเป้าหมายคือ

\displaystyle{\textrm{Min}\quad 40x_1+65x_2+20x_3+40x_4}

เมื่อเราได้สมการกำหนดเป้าหมายแล้วขั้นตอนไปคือหาสมการแสดงขอบข่าย ซึ่งแสดงเงื่อนไขและข้อจำกัดต่างๆ ในปัญหานี้เงื่อนไขคือ ร่างกายต้องได้รับสารอาหารแต่ละชนิดครบถ้วน เมื่อพิจารณาสารอาหารประเภทโปรตีน ถ้าเราทานอาหารประเภทที่ 1 จำนวน x_1 หน่วย เราจะได้โปรตีนเป็นจำนวน 80x_1กรัม ในขณะเดียวกัน ถ้าเราทานอาหารประเภทที่ 2 จำนวน x_2หน่วย เราจะได้โปรตีนเป็นจำนวน 120x_2กรัม ดังนั้นโปรตีนทั้งหมดที่เราจะได้รับคือ 80x_1+120x_2+60x_3+100x_4 เนื่องจากร่างกายต้องการโปรตีนอย่างน้อย 700 กรัม สมการแสดงขอบข่ายของโปรตีน คือ

80x_1+120x_2+60x_3+100x_4 \geq 700

สำหรับสมการแสดงขอบข่ายของวิตามินและธาตุเหล็กสามารถเขียนได้ดังนี้

30x_1+0x_2+10x_3+10x_4 \geq 250

15x_1+10x_2+20x_3+5x_4 \geq 300

นอกจากนี้เพื่อให้ได้ค่าตัวแปรที่สมเหตุสมผล ค่า x_1,x_2,x_3,x_4 ไม่ควรเป็นลบ นั่นคือ

x_1 \geq 0,x_2 \geq 0,x_3 \geq 0,x_4\geq 0

ซึ่งเราจะเรียกว่า non-negativity constraints

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

\displaystyle{\begin{array}{rcl}\textrm{Min}&40x_1+65x_2+20x_3+50x_4&\textrm(Objective function)\textrm{Subject to}&{\left\{\begin{array}{rcl}80x_1+120x_2+60x_3+100x_4\geq 700&x_1+0x_2+10x_3+10x_4\geq 250&x_1+10x_2+20x_3+5x_4\geq 300&\x_1\geq0, x_2\geq0,x_3\geq0, x_4\geq0\end{array}\right\}}&\textrm(Constraints)\end{array}}

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

จากปัญหาสารอาหารทางโภชนาการข้างต้น เราสามารถพิจารณาอาหารประเภทต่างๆ มากขึ้นหรือพิจารณาสารอาหารเพิ่มเติม เช่น พิจารณาอาหาร 150 ประเภท และ สารอาหาร 15 ชนิด ในกรณีนี้เราต้องการตัวแปร 150 ตัวแปร และ สมการแสดงขอบข่าย 15 อสมการ นอกเหนือจาก non-negativity constraints.
รูปแบบแทนระบบของปัญหานี้เราสามารถเขียนให้อยู่ในรูปแบบอย่างย่อได้ดังนี้
กำหนดให้ m แทนจำนวนชนิดของสารอาหาร และ n แทนจำนวนประเภทของอาหาร

a_{ij}แทนจำนวนของสารอาหาร i ที่อยู่ในอาหารประเภท j
b_iแทนปริมาณขั้นต่ำของสารอาหารชนิด i ที่ร่างกายต้องการ
c_jแทนราคาของอาหารประเภท j
x_jแทนปริมาณของอาหารประเภท j ที่ร่างกายบริโภค

โดยมี z เป็นสมการกำหนดเป้าหมาย
ปัญหาสารอาหารทางโภชนาการสามารถเขียนให้อยู่ในรูปของปัญหาทางคณิตศาสตร์ในรูปแบบของโปรแกรมเชิงเส้นได้ดังนี้

 \displaystyle{\begin{array}{rcl}\textrm{Min}&z=\sum_{j=1}^n c_jx_j&\textrm{Subject to}&{\begin{array}{rc}\sum_{j=1}^n a_{ij}x_j(\geq)b_i&\textrm{for}\ i=1,\ldots,m\x_j\geq0&\textrm{for}\ j=1,2,\ldots,n\end{array}}\end{array}}

ตัวอย่าง Cutting stock problem

ตัวอย่างนี้พบได้ทั่วๆไปในทางอุตสาหกรรมในการสั่งซื้อสิ่งค้าแล้วนำมาตัดแบ่ง เช่นในการสั่งซื้อไม้หรือม้วนกระดาษซึ่งอาจจะซื้อมาเป็นขนาดใหญ่แล้วนำมาตัดแบ่งเป็นขนาดต่างๆ ตามความต้องการ แล้วแต่การใช้งาน เป้าหมายคือต้องตัดกระดาษอย่างไร จึงจะประหยัดทรัพยากรมากที่สุด นั่นคือใช้กระดาษน้อยที่สุดในการตัด โดยกระดาษที่ตัดเป็นขนาดต่างๆ จะต้องมีเพียงพอต่อความต้องการของลูกค้า เช่นเราสั่งซื้อกระดาษที่มีขนาดความกว้าง 100 นิ้ว ในแบบที่ 1 เราจะตัดกระดาษให้มีขนาดความกว้าง 25 นิ้วเป็นจำนวน 2 ม้วน ขนาดความกว้าง 15 นิ้วเป็นจำนวน 3 ม้วน และขนาด 5 นิ้วเป็นจำนวน 1 ม้วน ในแบบที่ 2 เราจะตัดกระดาษให้มีความกว้าง 35 นิ้วจำนวน 2 ม้วนและ ขนาด 15 นิ้วจำนวน 3 ม้วน

ปัญหาการตัดกระดาษสามารถเขียนให้อยู่ในรูปแบบโปรแกรมเชิงเส้นในรูปทั่วๆไปได้ดังนี้
กำหนดให้ m แทนจำนวนขนาดที่ต่างๆ กันทั้งหมดที่มีความกว้างตามที่ลูกค้าต้องการ
n แทนจำนวนทั้งหมดของแพทเทริน์ที่เราต้องการตัด
a_{ij}แทนจำนวนม้วนกระดาษที่มีความกว้างของขนาดที่ i จากการตัดแบบที่ j
b_iแทนจำนวนม้วนกระดาษทั้งหมดของขนาดที่ i ที่ลูกค้าต้องการ
xj x_jแทนจำนวนม้วนกระดาษที่ใช้ในการตัดแบบที่ j
โดยมี z เป็นสมการกำหนดเป้าหมาย
เราจะเห็นได้ว่าปัญหาการตัดกระดาษสามารถเขียนให้อยู่ในรูปของโปรแกรมเชิงเส้นได้ดังนี้

 \displaystyle{\begin{array}{rcl}\textrm{Min}&z=\sum_{j=1}^n x_j&\\textrm{Subject to}&{\begin{array}{rc}\sum_{j=1}^n a_{ij}x_j(\geq)b_i&\textrm{for}\ i=1,\ldots,m\x_j\geq0&\textrm{for}\ j=1,2,\ldots,n\end{array}}\end{array}}

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

ตัวอย่าง ปัญหาการตัดสินใจในการผลิตสินค้า

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

อย่างเช่นโรงงานแห่งหนึ่งมีเครื่องจักรอยู่ 3 ประเภท เครื่องกลึง เครื่องตัดและ เครื่องเจาะ ซึ่งใช้ในการผลิตสินค้า 4 ชนิด ในตารางแสดงจำนวนชั่วโมงที่ต้องใช้เครื่องจักรต่างๆ ผลิตสินคัาแต่ละชนิด ขีดจำกัดของการทำงานของเครื่องจักรในแต่ละวัน โรงงานควรผลิตสินค้าแต่ละชนิดเป็นจำนวนเท่าใดจึงจะมีรายได้สูงสุด
เครื่องกลึงเครื่องตัดเครื่องเจาะราคาที่ขายได้
สินค้าชนิดที่ 12316500
สินค้าชนิดที่ 21134000
สินค้าชนิดที่ 31213000
ขีดจำกัดการทำงานของเครื่องจักร152018


กำหนดให้ x_iแทนจำนวนของสินค้าของชนิด i ที่ควรผลิต

\displaystyle{\begin{array}{rc}\textrm{Mix}&6500x_1+4000x_2+3000x_3\\textrm{Subject to}&{\begin{array}{rcl}2x_1+x_2+x_3&\leq&15\3x_1+x_2+2x_3&\leq&20\x_1+3x_2+x+3&\leq&18\x_1,x_2,x_3&\geq&0\end{array}}\end{array}}

ในกรณีที่มีเครื่องจักรทั้งหมด m ชนิด และต้องการผลิตสินค้าทั้งหมด n ประเภท
ถ้า x_j แทนจำนวนของสินค้าประเภท j ควรจะผลิต
[/tex]แทนจำนวนชั่วโมงของเครื่องจักรที่ i ที่ใช้ในการผลิตสินค้าประเภท j
b_iแทนจำนวนชั่วโมงที่เป็นขีดจำกัดของเครื่องจักร i
c_jแทนราคาต่อหน่วยในการผลิตสินค้าประเภท j

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

เราจะเห็นว่า c_jx_jคือรายได้ที่ได้จากการผลิตสินค้าประเภท j a_{ij}x_jคือจำนวนชั่วโมงที่ใช้ในการผลิตสินค้าประเภท j ของเครื่องจักร i

 \displaystyle{\begin{array}{rcl}\textrm{Max}&z=\sum_{j=1}^nc_j x_j&\\textrm{Subject to}&{\begin{array}{rc}\sum_{j=1}^n a_{ij}x_j(\leq)b_i&\textrm{for}\ i=1,\ldots,m\x_j\geq0&\textrm{for}\ j=1,2,\ldots,n\end{array}}\end{array}}

ตัวอย่าง ปัญหาการขนส่ง (transportation problem)

กำหนดให้มีโรงงาน 2 โรงงานที่มีกำลังการผลิต 230 หน่วย และ 150 หน่วย ต้องการที่จะส่งสินค้าไปยังร้านค้าย่อย 4 กลุ่ม โดยร้านค้าแต่ละร้านมีความต้องการสินค้า 80, 100, 60, และ 130 ตามลำดับ โรงงานแห่งนี้ควรจะจัดส่งสินค้าอย่างไรโดยให้เสียค่าใช้จ่ายน้อยที่สุด โดยที่สามารถส่งของให้ร้านค้าย่อยทุกๆร้านได้ตามความต้องการ ค่าขนส่งจากโรงงานไปยังร้านค้าต่างๆ ได้แสดงในตารางข้างล่างนี้
ถึงร้านค้า
1234
จาก โรงงาน165403015
210354060


กำหนดให้ x_{ij} แทนจำนวนสินค้าที่ส่งจากโรงงาน i ถึงร้านค้า j ตัวอย่างเช่น x_{11} แทนจำนวนสินค้าที่ส่งจากโรงงาน 1 ไปยังร้านค้า 1
สมการเป้าหมายซึ่งคือค่าใช้จ่ายทั้งหมดที่ใช้ในการขนส่ง สามารถเขียนได้ดังนี้

\textrm{Min}\,65x_{11}+40x_{12}+30x_{13}+15x_{14}+10x_{21}+35x_{22}+40x_{23}+60x_{24}

ในการจัดส่งสินค้าจากโรงงานไปยังร้านค้าต่างๆ ปริมาณการขนส่งสินค้าจากโรงงานแต่ละแห่งไม่ควรเกินกำลังการผลิต เราจะเห็นได้ว่า x_{11}+x_{12}+x_{13}+x_{14}
คือจำนวนสินค้าที่โรงงานที่ 1 ส่งไปยังร้านค้าต่างๆ เนื่องจากกำลังการผลิตของโรงงานนี้เท่ากับ 230 หน่วย ดังนั้น สมการแสดงขอบข่ายของโรงงาน 1 คือ

x_{11}+x_{12}+x_{13}+x_{14}\leq 230

สมการแสดงขอบข่ายของโรงงานที่ 2 คือ

x_{21}+x_{22}+x_{23}+x_{24}\leq 150

นอกจากนี้ข้อกำหนดในการจัดส่งสินค้าคือร้านค้าแต่ละร้านต้องได้รับสินค้าครบตามความต้องการ สำหรับร้านค้าที่ 1 ร้านค้าต้องการสินค้า 80 หน่วย ดังนั้นจำนวนที่ได้รับต้องไม่น้อยกว่า 80 หน่วย นั่นคือ
x_{11}+x_{21}\geq 80

นอกจากนี้จำนวนสินค้าที่ส่งจากโรงงานไปยังร้านค้าต่างๆ ต้องไม่เป็นลบ ดังนั้น

x_{ij}\geq 0\quad \textrm(non-negativity\quad constaints)

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

[Unparseable or potentially dangerous latex formula. Error 6 ]

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

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

วิธีกราฟ (Graphical Method)
วิธีกราฟนี้เป็นวิธีที่เข้าใจได้ง่ายสำหรับปัญหาที่มี 1 หรือ 2 ตัวแปร

ตัวอย่าง พิจารณาโปรแกรมเชิงเส้นต่อไปนี้

\displaystyle{\begin{array}{rc}\textrm{Max}&z=x_1+4x_2\ \textrm{Subject to}&{\begin{array}{rcl}x_1+x_2&\leq&3\x_1+2x_2&\leq&4\-x_1+x_2&\geq&1\x_1\geq0,x_2&\geq&0\end{array}}\end{array}}

การแก้ปัญหาโปรแกรมเชิงเส้นโดยวิธีกราฟมีขั้นตอนต่อไปนี้
1. วาดกราฟของสมการแสดงขอบข่ายทั้งหมด (สมการข้อจำกัด และ non-negativity constraints)
2. ระบุพื้นที่ที่เป็นสอดคล้องกับข้อจำกัดทั้งหมด นั่นคือคำตอบของสมการแสดงขอบข่ายทั้งหมดอยู่บนพื้นที่นี้พื้นที่นี้เรียกว่า (feasible region)

45307



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

3. วาดกราฟของสมการกำหนดเป้าหมายโดยการกำหนดให้สมการกำหนดเป้าหมายมีค่าต่างๆ พร้อมทั้งหาทิศทางการเปลี่ยนค่าของสมการกำหนดเป้าหมาย

45308



สมการ z=x_1+4x_2เป็นเส้นตรงโดยที่จุดต่างๆ บนเส้นตรงจะให้ค่า z เดียวกัน เมื่อกำหนดค่า z ค่าใหม่สมการที่ได้จะเป็นเส้นตรงที่ขนานกับเส้นเดิม จากกราฟข้างต้นจุด (x_1,x_2) ทุกๆจุดที่อยู่บนเส้นตรง x_1+4x_2=2 จะมีค่าของสมการกำหนดเป้าหมายเท่ากับ 2 ในขณะเดียวกันสำหรับจุด (x_1,x_2)ที่อยู่บนเส้นตรง x_1+4x_2=5จะมีค่าของสมการกำหนดเป้าหมายเท่ากับ 5 เราจะเห็นได้ว่าเมื่อค่าของสมการกำหนดเป้าหมายเพิ่มขึ้นเรื่อยๆ เส้นตรงจะเลื่อนขึ้นไปทางขวามือ ดังแสดงในกราฟ

4. ในการหาคำตอบของโปรแกรมเชิงเส้นสามารถทำได้โดยการเปลี่ยนค่าของสมการกำหนดเป้าหมาย ถ้าสมการกำหนดเป้าหมายต้องการหาค่าสูงสุด คำตอบของโปรแกรมเชิงเส้นข้างต้นคือค่าของตัวแปร x_1และ x2 x_2ที่ทำให้ค่าของสมการกำหนดเป้าหมายมีค่าสูงสุดโดยที่ค่าของตัวแปรนั้นจะต้องอยู่ในพื้นที่ที่แรงเงาด้วย

45309



จากกราฟข้างต้น ในการหาค่าสูงสุดของสมการกำหนดเป้าหมายทำได้โดยเลื่อนเส้นตรงไปทางขวาจนสุดเขตพื้นที่ที่แรงเงา จะเห็นได้ว่า ค่าของ x_1 และ x_2ที่ทำให้ค่าของสมการกำหนดเป้าหมายมีค่าสูงสุดคือ x_1=2/3,x_2=5/3โดยที่ค่าของสมการกำหนดเป้าหมายมีค่าเท่ากับ 22/3 ถ้าเราต้องการหาค่าต่ำสุดของสมการกำหนดเป้าหมายทำได้โดยเลื่อนเส้นตรงไปทางซ้ายจนสุดพื้นที่แรงเงา ค่าของ x_1และ x_2ที่ทำให้ค่าของสมการกำหนดเป้าหมายมีค่าต่ำสุดคือ x_1=0,x_2=0

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

45312


จุดยอดค่าของสมการกำหนดเป้าหมาย
x_1+4x_2
(0,0)0
(0,1)4
(2/3, 5/3)22/3*
(2,1)6
(3,0)3


จะเห็นได้ว่าในกรณีนี้ค่าของสมการกำหนดเป้าหมายมีค่าสูงสุดเท่ากับ 8 เมื่อ x_1=2/3 และ x_2=5/3 หรือ x_1=2และ x_2=1 จากกราฟเราจะเห็นได้ว่าคำตอบทั้งหมดคือจุดทุกๆจุดของ x1 x_1และ x2 x_2ที่อยู่บนเส้นตรง 2x_1+4x_2=8โดยที่ x_1มีค่าอยู่ระหว่าง 2/3 และ 2

ตัวอย่าง พิจารณาโปรแกรมเชิงเส้นต่อไปนี้

\displaystyle{\begin{array}{rc}\textrm{Max}&z=x_1+4x_2\ \textrm{Subject to}&{\begin{array}{rcl}-3x_1+x_2&\leq&3\-x_1+x_2&\geq&-2\-2x_1+x_2&\leq&5\x_1\geq0,x_2&\geq&0\end{array}}\end{array}}

45313



จากกราฟจะเห็นได้ว่าพื้นที่ของอยู่สอดคล้องกับข้อจำกัดทั้งหมดมีขอบเขตไม่จำกัด (unbounded region) นอกจากนี้ค่าของสมการกำหนดเป้าหมายซึ่งเป็นเส้นตรงที่มีค่าเพิ่มขึ้น เส้นตรงจะเลื่อนไปทางขวามือ เราจะเห็นว่าค่าของสมการกำหนดเป้าหมายเพิ่มขึ้นไปเรื่อยๆไม่มีขีดจำกัด นั่นคือ ผลลัพธ์ไม่มีขอบเขตจำกัด ถ้าต้องการหาค่าสมการกำหนดเป้าหมายที่มีค่าต่ำสุด ค่าของสมการกำหนดเป้าหมายมีค่าต่ำลงเมื่อเส้นตรงเลื่อนไปทางซ้ายมือ เมื่อเลื่อนเส้นตรงไปทางซ้ายมือสุดขอบพื้นที่ ค่าของสมการกำหนดเป้าหมายมีค่าเท่ากับ 0 ที่จุดยอด (x_1,x_2)=(0,0)

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

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

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

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

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

ขั้นตอนเริ่มต้น

ในแก้ปัญหาโปรแกรมเชิงเส้นสำหรับ simplex method ก่อนอื่นเราต้องจัดรูปแบบของปัญหาให้อยู่ในรูปแบบมาตราฐานของโปรแกรมเชิงเส้น ซึ่งมีลักษณะดังต่อไปนี้

\displaystyle{\begin{array}{rc}\textrm{Min}&z=c_1x_1+c_2x_2+\ldots+c_nx_n\ \textrm{Subject to}&{\begin{array}{rcl}a_{11}x_1+a_{12}x_2+\ldots+a_{1n}x_n&=&b_1\a_{21}x_1+a_{22}x_2+\ldots+a_{2n}x_n&=&b_2\ \vdots \qquad\qquad\qquad& & \vdots \a_{m1}x_1+a_{m2}x_2+\ldots+a_{mn}x_n&=&b_m\x_1\geq0,x_2\geq0,\ldots,x_n&\geq&0 \end{array}}\end{array}}

การเปลี่ยนรูปแบบดั้งเดิมให้เป็นรูปแบบมาตราฐานของโปรแกรมเชิงเส้นสามารถทำได้ดังนี้

1. ถ้าปัญหาต้องการที่จะสมการกำหนดเป้าหมายมีค่าสูงสุด

\displaystyle{\textrm{Max}\,z=\sum_jc_jx_j}
เราสามารถเปลี่ยนให้เป็นปัญหาที่มีสมการกำหนดเป้าหมายต่ำสุดได้โดย

\displaystyle{\textrm{Min}\,z’=-\textrm{Max}\,z=-\sum_jc_jx_j}

เช่น \textrm{Max}\,2x_1-3x_2+4x_3\Rightarrow \textrm{Min}\,-2x_1+3x_2-4x_3

2. ในกรณีที่สมการแสดงขอบข่ายอยู่ในรูปของเครื่องหมาย \leqเช่น
a_{i1}x_1+a_{i2}x_2+\ldots +a_{in}x_n\leq b_i
เราสามารถเปลี่ยนให้อยู่ในรูปของสมการได้โดย a_{i1}x_1+a_{i2}x_2+\ldots +a_{in}x_n+x_{n+1}=b_i
โดยที่ตัวแปรที่เพิ่มขึ้นเราเรียกว่าตัวแปรขาด หรือ slack variable
เช่น 2x_1-3x_2+4x_3\leq 3\rightarrow 2x_1-3x_2+4x_3+x_4=3

3. ในกรณีที่สมการแสดงขอบข่ายอยู่ในรูปของเครื่องหมาย \geqเช่น

a_{i1}x_1+a_{i2}x_2+\ldots +a_{in}x_n\geq b_i
เราสามารถเปลี่ยนให้อยู่ในรูปของสมการได้โดย

a_{i1}x_1+a_{i2}x_2+\ldots +a_{in}x_n-x_{n+1}+x_{n+2}=b_i
โดยที่ตัวแปร x_{n+1}เรียกว่าตัวแปรเกิน หรือ surplus variable และ x_{n+2}เรียกว่าตัวแปรเทียม artificial variable เช่น 2x_1-3x_2+4x_3\geq3\rightarrow 2x_1-3x_2+4x_3-x_4+x_5=3

4. ในกรณีที่ x_i\leq 0 เราสามารถเปลี่ยนให้อยู่ในรูปแบบเพิ่มเติมโดยกำหนดให้ \displaystyle{x_i^\prime =-x_i,x_i^\prime \geq 0}

5. ในกรณีที่ x_iไม่มีข้อจำกัด นั่นคือ x_i สามารถเป็นทั้งบวกและลบรวมทั้งศูนย์ เราสามารถเปลี่ยนโดยกำหนดให้ x_i=x_i^\prime - x_i^{\prime\prime} , x_i\geq 0 และ -x_i\geq 0

6. ในกรณีที่ทางซ้ายมือเป็นค่าสัมบูรณ์ |a_1x_1+a_2x_2|\leq b เราสามารถเปลี่ยนให้อยู่ในรูปของ a_1x_1+a_2x_2\leq b และ -a_1x_1-a_2x_2\leq b

ตัวอย่างเช่น

\displaystyle{\begin{array}{rcl}{\begin{array}{rc}\textrm{Max}&2x_1+3x_2-4x_3\textrm{Subject to}&2x_1+x_2\geq5\&x_1-x_2-x_3\leq3\&x_1+x_3=4\&x_1\geq0,x_2\leq0,x_3\end{array}}&\Rightarrow&{\begin{array}{rc}\textrm{Min}&-2x_1-3x_2+4(x^{\prime}_3-x^{\prime\prime}_3)\textrm{Subject to}&2x_1+x_2-x_4+x_5=5\&x_1-x_2-(x^\prime_3-x^{\prime\prime}_3)+x_6=3\&x_1\geq0,x_2\geq0,x^\prime_3\geq0,x^{\prime\prime}_3\geq0,\&x_4\geq0,x_5\geq0,x_6\geq0\end{array}}\end{array}}

โดยที่ x_4เป็นตัวแปรขาด x_5เป็นตัวแปรเกินและ x_6 เป็นตัวแปรเทียม

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

\displaystyle{\begin{array}{rcl}{\begin{array}{rc}\textrm{Min}&-3x_1-x_2-3x_3\textrm{Subject to}&2x_1+x_2+x_3\geq2\&x_1+2x_2+x_3\leq5\&2x_1+2x_3+x_3\leq6\&x_1\geq0,x_2\leq0,x_3\leq0\end{array}}&\Rightarrow&{\begin{array}{rc}\textrm{Min}&z\textrm{Subject to}&{\begin{array}{rcl}z=3x_1+x_2+3x_3&=&0x_1+x_2+x_3+x_4&=&2\x_1+2x_2+x_3\qquad+x_5&=&5x_1+2x_2+x_3\qquad\qquad+x_6&=&6\x_1\geq0,x_2\geq0,x_3\geq0,&&\x_4\geq0,x_5\geq0,x_6\geq0&&\end{array}} \end{array}}\end{array}}

จากตัวอย่างข้างต้นเราจะเห็นได้ว่า x_4=2,x_5=5,x_6=6,x_1=x_2=x_3=0 เป็นผลลัพธ์เริ่มต้น ตัวแปรแบ่งได้ออกเป็นสองประเภทคือ ตัวแปรมูลฐาน หรือ basic variables ซึ่งเป็นตัวแปรที่ไม่ใช่ศูนย์ในผลลัพธ์เริ่มต้น (x_4,x_5,x_6) และตัวแปรที่ไม่เป็นมูลฐาน หรือ non-basic variables นั่นคือตัวแปรที่มีค่าเท่ากับศูนย์ในผลลัพธ์เริ่มต้น (x_1,x_2.x_3)

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


PS.  ช่วยเข้าปัยAddเปนเพิ่ลหน่อยดิ

แก้ไขครั้งล่าสุดเมื่อ : วันที่ 15 มีนาคม 2555 เวลา 22:44 น.

อยากเป็นคนแรกที่โหวตมั๊ยล่ะ... โหวตเลย!

  • โอ้โหเด็ด

  • น่ารักสุดๆ

  • หรูเริด

  • ตลกอ่ะ

  • เครียด

  • สู้ๆ สู้ตาย

  • ช็อค

  • โกรธ

  • ล้มโต๊ะ


0 โหวต จากทั้งหมด 0 โหวตเลือก

ความคิดเห็น

7

ติดตามกระทู้

2

แชร์กระทู้นี้
จำนวนแชร์
4
ซ่อน

ความคิดเห็นทั้งหมด

หน้า 1

ความคิดเห็นที่ 1 - ความคิดเห็นล่าสุด

  1. ขอบคุณ
    ความเห็นนี้

    ยากจังเลย
    PS.  ดีดี
  2. ขอบคุณ
    ความเห็นนี้

    กำลังเรียนอยู่พอดีเลยอะ จะสอบแล้วด้วย101
  3. ขอบคุณ
    ความเห็นนี้

    ยาวเป็นหางว่าว ขี้เกียจอ่านอ่ะ~ >____TT

    อีกอย่างยังไม่ได้เรียนด้วย~ >\\\\\^;;

    PS.  เงยหน้าขึ้นรับแสงตะวัน แล้วคุณจะไม่มีวันพบกับเงามืด
  4. ขอบคุณ
    ความเห็นนี้

    ยาก ๆเรียนแล้วไม่เข้าหัวเลยง่า
  5. ขอบคุณ
    ความเห็นนี้

    Thank you very much ^^
    PS.  ยอดนักสืบ ม.ปลายตะวันออก VS เทพเจ้าแห่งโลกตะวันออก Forever...D2B
  6. ขอบคุณ
    ความเห็นนี้

    ยากอะ
    เรียนแล้ว
  7. ขอบคุณ
    ความเห็นนี้

    มาเรียนที่มหาวิทยาลัยเกริก สาขาการจัดการโลจิสติกส์สิค่ะ ที่นี่อาจารย์และพี่ๆๆดูแลกันมากค่ะ กำลังเป็นที่ต้องการของตลาดมากค่ะ จบแล้วรับรองค่ะว่ามีงานทำแซงหน้าสาขาอื่นกันเลย และกำลังจะมีสาขาน้องใหม่เปิดค่ะคือสาขาการบิน ลองมาเรียนกันน่ะค่ะ รับลองค่ะว่าจะไม่ผิดหวัง พี่ๆโลจิสติกส์รออยู่ค่ะ
    โทรศัพท์: 02-552-3500-9, 02-970-5820 email :http://www.krirk.ac.th/
ซ่อน

แสดงความคิดเห็น

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

ร้องเรียนปัญหากระทู้ภายใน
เว็บไซต์ Dek-D.com

board@dek-d.com
( ทุกวัน 24 ชม )
02-860-1142 ต่อ 140
( จ-ศ 09.00-18.00 พักเที่ยง 12.00-13.00 )
refer: