ประวัติ Optimization Problem และ Models

บังเอิญได้พบ Web site ของคุณสุรีพร .. http://sureeporn.blogth.com/9356/%A1%D2%C3%B9%D3%A7%D2%B9%E4%BB%E3%AA%E9%BB%C3%D0%E2%C2%AA%B9%EC.html .. จึงอยากบันทึกไว้น่าจะเป็นประโยชน์แก่หลายๆท่าน , อีกทั้งกลัวว่าข้อมูลจะสูญหายในอนาคต จึงได้ขอทำการ Qoute บันทึกไว้ณ.ที่นี้ ด้วยครับ

อนึ่ง เนื่องจากบันทึกได้กล่าวถึง Models .. อย่าง Linear Programming และ Dynamic Programming .. ว่าคือ Models หรือ Algorithm (Mechanism) .. หรืออะไรกันแน่ .. จึงขอทิ้ง Link ที่น่าสนใจดังนี้

http://en.wikipedia.org/wiki/Operations_research

http://www.me.utexas.edu/~jensen/ORMM/models/index.html

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

ดังนั้นในบทนี้หัวข้อ 2.1 และหัวข้อ 2.2 กล่าวถึงประวัติความเป็นมาของ Optimization ว่ามีการพัฒนาอย่างไรบ้าง หัวข้อ 2.3 กล่าวถึงประโยชน์ของ Optimization กับงานด้านต่าง ๆหัวข้อ 2.4 กล่าวถึงการวิจัยการดำเนินงาน ตัวแบบทางคณิตศาสตร์ หัวข้อ 2.5 กล่าวถึงรายละเอียดของตัวแบบกำหนดการเชิงเส้น (Linear Programming Model) หัวข้อ 2.6 กล่าวถึงรายละเอียดของตัวแบบกำหนดการไม่เป็นเชิงเส้น (Non-linear Programming Model) และหัวข้อ 2.7 กล่าวถึงคำนิยามและทฤษฎีพื้นฐานที่ใช้ในการจัดทำโครงงาน

2.1 การสำรวจวรรณกรรมที่เกี่ยวข้อง

Newton, Lagrange และ Cauchy ได้พัฒนาวิธีหาค่าเชิงอนุพันธ์และทฤษฎีของแคลคูลัส ซึ่งเป็นพื้นฐานของเทคนิค Optimization และ Bernoulli, Euler, Lagrange และ Weirstrass ได้พัฒนาแนวคิดทางแคลคูลัส เพื่อเป็นการพัฒนาเทคนิค Optimization

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

2.2 การพัฒนาของ Optimization

เทคนิค Optimization ได้มีการนำมาประยุกต์ใช้เป็นครั้งแรกโดย Cauchy ในเรื่องการหาค่าต่ำสุด และเทคนิค Optimization ยุคใหม่เกิดขึ้นเพราะมีทฤษฎีใหม่ๆ เกิดขึ้นคือ

  • penalty functions (Courant[1943])
  • simplex method สำหรับ linear programming (Dantzig[1947])
  • การหาค่าที่เหมาะสมแบบ KKT สำหรับ Constrained (Karush, Kuhn และ Tucker[1951])
  • และ ได้มีการประกาศกฎของ optimal policy สำหรับปัญหาแบบ dynamic programming (Bellman[1952]) ซึ่งเป็นพื้นฐานสำหรับการพัฒนาวิธีการแก้ปัญหาสำหรับ constrained optimization

ในช่วงปีทศวรรษที่ 1960 ได้มีการพัฒนาวิธีการเกี่ยวกับตัวเลขของ Unconstrained Optimization ที่เกิดขึ้นในประเทศอังกฤษเท่านั้น mixed integer programming ได้รับการพัฒนาโดย Land และ Doig[1960] และวิธีการ cutting plane โดย Gomory ซึ่งเป็นผู้บุกเบิกงานทางด้าน integer programming[1960] วิธีการเปลี่ยนแปลง metric ของ Davidon-Fletcher-Powell ที่เรียกว่า DFP [1959] มีการพัฒนา gradient-based methods เป็นการพัฒนา non-gradient หรือ direct methods ด้วยวิธี Rosenbrock ในการทำ orthogonal direction[1960] ได้มีรูปแบบวิธีการค้นหาของ Hooke และ Jeeves[1961] วิธีของ Powell สำหรับการทำ conjugate direction[1964] วิธี simplex method ของ N
elder และ Meade[1965] และวิธีของ Box[1965] genetic algorithm เป็น direct methods (Holland[1975], Goldberg[1989]) ผู้ที่บุกเบิกเรื่อง Constrained Optimization คือ Rosen ด้วยวิธีการ gradient projection ในปี 1960 วิธีการของ Zoutendijk สำหรับ feasible directions[1960] ซึ่งผลงานของ Rosen และ Zoutendijk เป็นงานทางด้าน non-linear programming ซึ่งเป็นสัญญาณของการพัฒนาที่ดี และมีการใช้เทคนิคของ non-linear optimization ในการออกแบบโครงสร้าง (Schmit[1960]) ได้มีการสรุปเรื่อง gradient method โดย Abadie, Carpentier และ Hensgen[1966] และมีการคิด geometric programming จากการทำงานของ Duffin, Zener และ Peterson[1967]

ในช่วงทศวรรษปีที่ 1970 ได้มีการพัฒนาวิธี sequential quadratic programming (SQP) สำหรับ constrained minimization และวิธี hybird polynomial-interval ที่ใช้ในการค้นหาเกิดขึ้น (Brent[1971])

วิธีการวิเคราะห์ระบบข่ายงาน (network analysis method) เป็นเทคนิคการควบคุมการจัดการที่เป็นหัวใจหลักของระบบข่ายงาน ได้พัฒนาขึ้นในช่วงปี 1957 และ 1958 game theory คิดค้นโดย Von Neumann[1928] และมีการนำไปประยุกต์ใช้ในการแก้ปัญหาทางเศรษฐศาสตร์ และปัญหาต่างๆ อีกมากมาย ในช่วงหลายปีหลังจากนั้น game theory มีการนำไปใช้ในการแก้ปัญหาการออกแบบของวิศวกรรมศาสตร์

การแต่งหนังสือเกี่ยวกับวิศวกรรม Optimization แต่งโดย Johnson[1961], Wilde [1967], Fox[1971], Siddall[1972], Haug และ Arora[1979], Reklaitis, Ravindran และ Ragsdell [1983], Vanderplaats[1984], Haflka[1984] และ Rao[1996] เป็นส่วนสำคัญในการศึกษาวิศวกรรมการประยุกต์ของเทคนิค Optimization

2.3 การนำ Optimization ไปใช้ประโยชน์

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

2.4 การวิจัยการดำเนินงาน (Operation Research)

2.4.1 การสำรวจวรรณกรรมเกี่ยวข้อง

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

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

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

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

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

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

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

2.4.2 ความหมายของ การวิจัยการดำเนินงาน

คำว่า การวิจัยการดำเนินงาน (Operation Research) สามารถสรุปความหมายและนิยามต่างๆ ไว้ดังนี้

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

ส่วน สมาคมการวิจัยการดำเนินงานของสหรัฐอเมริกา ได้ให้นิยามว่า การวิจัยการดำเนินงาน คือหลักเกณฑ์การตัดสินใจที่จะวางแผนระบบคน และเครื่องจักรภายใต้เงื่อนไขที่มีทรัพยากรจำกัด

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

ลักษณะสำคัญของการวิจัยการดำเนินงานสามารถสรุปได้ดังนี้

1. ใช้วิธีการทางวิทยาศาสตร์มาแก้ปัญหาอย่างมีประสิทธิภาพ

2. เป็นการทำงานร่วมกันเป็นทีม คือผู้ที่มีความรู้ความเชี่ยวชาญในสาขาวิชาการต่างๆ มาทำ งานร่วมกันเพื่อให้เกิดประสิทธิภาพที่สุด

3. มีการสร้างตัวแบบ (Model) แทนระบบปัญหาจริงๆ ที่ต้องการศึกษาและวิเคราะห์

2.4.3 ตัวแบบทางคณิตศาสตร์ (Models in Operation Research)

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

Real System

Model

Real Conclusions

Model Conclusions

Formulation

Interpretation

Deduction

รูปที่ 2-1 ความสัมพันธ์ของตัวแบบทางคณิตศาสตร์ต่างๆ

ตัวแบบทางคณิตศาสตร์ที่ใช้กันแพร่หลายคือ ตัวแบบกำหนดการเชิงเส้น (Linear Programming Model) เทคนิคทางคณิตศาสตร์ที่นิยมใช้หาผลลัพธ์ของตัวแบบนี้คือ วิธีซิมเพลกซ์ (Simplex Method)

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

1. ตัวแบบกำหนดการเชิงเส้น (Linear Programming Model) เป็นตัวแบบแทนระบบปัญหาเกี่ยวกับการใช้ทรัพยากรที่มีอยู่อย่างจำกัดให้มี ประสิทธิภาพที่สุด และความสัมพันธ์ของตัวแปรต่างๆ เป็นแบบเชิงเส้นทั้งสิ้น การหาผลลัพธ์ของตัวแปรนี้มีหลายวิธี แต่ที่นิยมคือ วิธีซิมเพลกซ์ (Simplex Method)

2. ตัวแบบกำหนดการไม่เป็นเชิงเส้น (Non-linear Programming Model) เป็นตัวแบบแทน

ระ บบปัญหาที่ความสัมพันธ์ของตัวแปรไม่เป็นแบบเชิงเส้น

3. ตัวแบบกำหนดการพลวัต (Dynamic Programming Model) เป็นตัวแบบแทนระบบปัญหาที่มีการตัดสินใจติดต่อกันเป็นขั้นตอนหลายๆ ขั้นตอน สำหรับปัญหาขนาดใหญ่ที่มีความยุ่งยากซับซ้อน การแตกปัญหาออกเป็นขั้นตอนย่อยๆ แล้วแก้ปัญหาแต่ละขั้นตอนย่อยๆ นั้นง่ายกว่าการแก้ปัญหาขนาดใหญ่

4. ตัวแบบปัญหาการขนส่ง (Transportation Model) เป็นตัวแบบแทนปัญหาการขนส่งทรัพยากรระหว่างแหล่งต่างๆ

5
. ตัวแบบแถวคอย (Queuing Model) เป็นตัวแบบแทนระบบปัญหาเกี่ยวกับการให้บริการที่ไม่ต้องการให้ลูกค้าเสียเวลารอคอยนานเกินไป โดยคำนึงถึงการประหยัดค่าใช้จ่ายต่างๆ

6. ตัวแบบสินค้าคงคลัง (Inventory Model) เป็นตัวแบบแทนระบบปัญหาที่เกี่ยวกับการหาจำ นวนสินค้าที่สั่งซื้อหรือผลิตในแต่ละครั้ง

7. ตัวแบบการแข่งขัน (Competitive Model) เป็นตัวแบบแทนระบบปัญหาที่ต้องมีการตัดสินใจในการประกอบธุรกิจ เพราะว่าในการทำธุรกิจย่อมต้องมีการแข่งขันกัน

8. ตัวแบบการจำลอง (Simulation Model)

Del.icio.us : , , , ,
Technorati : , , , ,

Advertisements

One thought on “ประวัติ Optimization Problem และ Models

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s