ำไพะไำะ

กำหนดการเชิงเส้น

( Linear  Programming)

 

1. อสมการและกราฟ

                ทฤษฎี    ให้ f  เป็นฟังก์ชันในเชต  R x R

                                1)  กราฟของอสมการ y > f(x)  คือ  บริเวณที่อยู่เหนือกราฟของ y = f(x)

                               2)  กราฟของอสมการ y < f(x)  คือ  บริเวณที่อยู่ใต้กราฟของ y = f(x)

                                3)  กราฟของอสมการ x > f(x)  คือ  บริเวณที่อยู่เหนือกราฟของ x = f(y)

                               4)  กราฟของอสมการ x < f(x)  คือ  บริเวณที่อยู่ใต้กราฟของ x = f(y)

 

2. ระบบอสมการ

                ถ้าอสมการประกอบด้วย  อสมการย่อยๆ  n  อสมการ  คือ

                P₁(x,y) , P₂(x,y) ,…, P_n(x,y) ซึ่งแต่ละอสมการเหล่านี้มีกราฟเป็น G₁,G₂,….,G_n 

ตามลำดับ  แล้วกราฟของอสมการดังกล่าว  คือ  G = เป็น G₁ÇG₂Ç,….,ÇG_n

 

3.  ระบบอสมการเชิงเส้น

                นิยาม  อสมการเชิงเส้น ( Linear  Programming)  ที่ประกอบด้วย

                                ตัวแปร x และ y  คือ อสมการที่เขียนได้ในรูปใดรูปหนึ่งต่อไปนี้

                                                                                ax + by + c  > 0

                                                                                ax + by + c  < 0

                                                                                ax + by + c  ³ 0

                                                                                ax + by + c  £ 0

                                เมื่อ a,b,c เป็นค่าคงที่ และ a,b  ไม่เป็นศูนย์พร้อมกัน

                นิยาม    ระบบอสมการเชิงเส้น  คือ  ระบบขอบของกราฟของระบบอสมการย่อยเป็น

            อสมการเชิงเส้น

 

นิยาม     เรียกจุดที่เกิดขึ้นจากการตัดกันของเส้นขอบของกราฟของระบบอสมการว่า จุดมุม

 ( corner  point)ของกราฟ

4.  กำหนดการเชิงเส้น

                ตัวแบบ (model)  ของปัญหากำหนดการเชิงเส้น  ประกอบด้วย 2  ส่วน  คือ

                (1)  ฟังก์ชันจุดประสงค์ (objective function) อยูในรูป

 

                                                P = ax + by

 

                (2) ข้อจำกัดหรือเงื่อนไขบังคับ (constration)  อยู่ในรูปของระบบอสมการเชิงเส้น

                ทฤษฎี   กำหนด เส้นตรง l เป็นกราฟของสมการเชิงเส้น ax + by = P เมื่อ P เป็นตัวแปร

 เสริม(Parameter)  จะได้ว่า

1)  ถ้า b > 0   แล้ว  l  ตัดแกน y ในตำแหน่งสูงขึ้น  เมื่อ P เพิ่มขึ้น และ l 

      ตัดแกน y ในตำแหน่งต่ำลง  เมื่อ P  ลดลง

2)  ถ้า b < 0   แล้ว  l  ตัดแกน y ในตำแหน่งสูงขึ้น  เมื่อ P ลดลง  และ l 

      ตัดแกน y ในตำแหน่งต่ำลง  เมื่อ P  เพิ่มขึ้น

 

                ทฤษฎี   ฟังก์ชันจุดประสงค์มีเงื่อนไข  บังคับเป็นเซตที่มีขอบเขต (บริเวณที่มีพื้นที่จำกัด)

                                จะมีทั้งค่าสูงสุดและค่าต่ำสุด  ซึ่งค่าทั้งสองจะเกิดขึ้นที่จุดมุมของกราฟ

 

                หมายเหตุ  ในกรณีที่เงื่อนไขบังคับเขตไม่มีขอบเขต (บริเวณที่มีพื้นไม่จำกัด)  ฟังก์ชัน

     จุดประสงค์จะมีค่าสูงสุด (ค่าต่ำสุด)  หรือไม่ก็ได้  แต่ถ้ามี  ค่านั้นจะเกิดขึ้นที่

     จุดมุมของกราฟเช่นกัน

 

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

                1.  เขียนกราฟของเซตคำตอบที่เป็นไปได้

                2.  หาจุดยอดมุม

                3.  หาค่าของฟังก์ชันจุดประสงค์  ที่จุดยอดมุมแต่ละจุด

                4.  ค่าน้อยที่สุดในชั้นที่ 3  คือ  ค่าต่ำสุดของฟังก์ชันจุดประสงค์

                     ค่ามากที่สุดในชั้นที่ 3  คือ ค่าสูงสุดของฟังก์ชันจุดประสงค์

 

เมตริกซ์ (Matrix)

 

ในเรื่องนี้  จะมีส่วนสำคัญ 4  ส่วนคือ

                1.  เรื่องทั่วๆ ไปของเมตริกซ์

                2.  ดิเทอร์มิเนนต์ (Deteminant)

                3.  อินเวอร์ส ( Inverse)

                4.  ระบบสมการเชิงเส้น (Linear  Equation System)

 

สรุปเนื้อหาสำคัญ  : เมตริกซ์

                1.  นิยาม  เมตริกซ์เป็นกลุ่มของเลขจำนวนซึ่งเรียงกันในลักษณะของสี่เหลี่ยมมุมฉากล้อมรอบด้วยเครื่องหมาย [ ]

               

                2.  การบอกตำแหน่งของสมาชิก

                               

แถวที่หนึ่ง

แถวที่หนึ่ง

แถวที่หนึ่ง

                               

                                    หลัก    หนึ่ง  สอง สาม สี่

 

                3. มิติของเมตริกซ์ (Order of  matrix)

                                เราจะเรียกเมตริกซ์ที่มี  m แถว และ n  หลัก (Column) ว่ามีมติ m x n  โดยทั่วไป

    นิยมใช้อักษรตัวพิมพ์ใหญ่ (A , B , C …)  แทนเมตริกซ์  และใช้อักษร a_ij ,b_ij , c_ij …

     แทนสมาชิกแถวที่ I  ของเมตริกซ์  ในบางครั้ง อาจเขียน   [a_ij ] _mxn แทนเมตริกซ์ A

 

1. เมตริกจัตุรัส (Square matrix)  คือ เมตริกซ์ที่มี มิติ n x n

5. เมตริกศูนย์ (Zero  matrix )  คือ เมตริกซ์ที่มีสมาชิกทุกตัวเป็นศูนย์ และใช้สัญลักษณ์ 

    0  หรือ  [0] mxn

 

6.  เมตริกซ์เอกลักษณ์ (Identity  matrix  or Unit matrix) 

     คือเมตริกซ์จัตุรัสที่มีคุณสมบัติว่า

                                1  เมื่อ  i =  j

                aij  =

                                0  เมื่อ  i ¹  j

                จะใช้สัญลักษณ์ I  หรือ  I_n  แทนเมตริกซ์เอกลักษณ์ดังกล่าว

7.  การเท่ากันของเมตริกซ์

                กำหนดให้  A = [a_ij ] _mxn  เมื่อ  B = [b_ij ] _{p x q}

                        A = B  ก็ต่อเมื่อ A และ B  มีมิติเดียวกันและมีสมาชิกที่มีค่าเท่ากัน  ตำแหน่งต่อตำแหน่ง  นั่นคือ  เมตริกซ์ A เท่ากับเมตริกซ์ B  เมื่อ

                1)  m = p   และ  n = q

                2) a_ij = b_ij  ทุกค่า i  และ j

 

8.  การบวกเมตริกซ์ (Matrix Addltion)

                กำหนดให้ A = [a_ij ] _mxn , B = [b_ij ] _mxn  และ c = [c_ij ] _mxn

                ถ้า  C = A + B  แล้วจะได้ว่า c_ij = a_ij + b_ij  สำหรับทุกค่า i  และ j

9.  การคูณเมตริกซ์ด้วยสเกลาร์ (Scalra Multiplication)

                กำหนดให้ A = [a_ij ] _mxn  และให้ K Î R

                จะได้ KA = K [a_ij ] _mxn   =  [Ka_ij ] _mxn

10. การคูณเมตริกซ์ (Matrix Multiplication)

                กำหนดให้ A = [a_ij ] _mxn , B = [b_ij ] _mxp  และ c = AB

                C จะมีมิติ mxp  คือ C = [c_ij ] _{m xp}  และ

                Cij = a_i1b_1j+ a_i2b_2j + a_i3b_3j + … + a_ijb_ij

                11.  ทฤษฎีบทสำหรับการคูณเมตริกซ์

                                ถ้า A ,B และC เป็นเมตริกช์ที่สามารถคูณกันจะได้ว่า

                                1. (AB)C = A(BC)  (การเปลี่ยนกลุ่มสำหรับการคูณ)

                                2. ถ้า A = [a_ij ] _nxn จะได้ว่า I_n.A = A  =  A.I_n

                                3. A(B + C)  = AB+ AC

                                4. ถ้า AB = AC  และ

                                                ถ้า A เป็น nonsingular  matrix  แล้วสรุปได้ว่า B = C

                                                ถ้า A เป็น singular  matrix แล้ว B และ C ไม่จำเป็นต้องเท่ากัน

 

                                5. ถ้า AB = 0

                                                ถ้า A เป็น nonsingular  matrix  แล้วสรุปได้ว่า B = 0

                                                ถ้า A เป็น singular  matrix แล้ว B  ไม่ใช่  0

                               

ข้อสังเกต               

1.  โดยทั่วไป AB  ¹  BA

2.  สูตรต่างๆ ในเรื่องจำนวนจริงอาจจะใช้กับเมตริกซ์ไม่ได้ เช่น

                (A+B)² = A²+ AB + BA + B²  ¹ A²+ 2AB + B²

                (A+B) (A+B) = A²+ AB - BA - B²  ¹ A² – B²

                12.  การทรานสโพสเมตริกซ์ ( Transpostlion of  matrix)

                                กำหนดให้ A = [a_ij ] _mxn , B = [b_ij ] _nxm  โดยที่ b_ij = a_ji   ทุกค่า i , j

                                แล้วจะเรียกเมตริกซ์ B ว่าเป็นการทรานสโพสของเมทริกซ์ A ซึ่งเขียนแทนด้วย

                                B = A^t

               

                13. ทฤษฎีบทสำหรับการทรานสโพสเมตริกซ์    ให้ A , B เป็นเมตริกซ์ใดๆ

                                1. (A^t) ^t  = A

                                2. (A+B)^t  = A ^t + B ^t

                                3. (AB) ^t  = B ^t A ^t

                                4. (A^-1) ^t  = (A ^t) ^–1  โดยที่ A เป็น nonsingular  matrix

                                5. (Aⁿ)^t  =  (A^t)ⁿ , n Î I⁺ 

6.  (KA)^t  = KA^t , K ÎR

 

 

 

 

 

สรุปเนื้อหาสำคัญ : ดีเทอร์มิเนนต์ (Determinant)

 

                1. ดิเทอร์มิเนนต์ เป็นฟังก์ชันที่มีโดเมนเป็นเซตของเมตริกซ์จัตุรัส  และมีเรนจ์เป็นเซตของ

              จำนวนจริง  ดีเทอร์มิเนนต์ของเมตริกซ์ A เขียนแทนด้วย | A | หรือ  det A หรือ det (A)

 

                2.  ความเป็นเอกฐานของเมตริกซ์ (Singularity of Matrix)

                                ให้ A เป็นเมตริกซ์จัตุรัส

                                ถ้า det (A) = 0  จะเรียกเมตริกซ์เอกฐาน (Singular Matrix)

                                ถ้า det (A) ¹ 0  จะเรียกเมตริกซ์ไม่เอกฐาน (nonSingular Matrix)

               

                3. การหาดีเทอร์มิเนนต์ของเตริกซ์จัตุรัสที่มีมิติไม่เกิน  3x3

                                1. เมตริกซ์  | x |

                                ให้ A  = [ a ]      จะได้ det (A) = a

                                2. เมตริกซ์  2x2

                                ให้ A  =    จะได้ det (A) = ad – bc

                                2. เมตริกซ์  3x3  ใช้วิธีต่อ 2 หลัก

                                ให้ A  = 

                                จะได้ det (A) = (aci + bfg + cdh) – (gec + hfa + idb)

 

 

                4. ไมเนอร์ , โคแฟกเตอร์ และเมตริกผูกพัน ( Minor , Cofactor and Adjonint)

                                กำหนดเมตริกซ์ A = [a_ij ] _mxn  โดยที่  n > 1

                                4.1 ไมเนอร์ของ a_ij  คือ ดีเทอร์มิเนนต์ของเมตริกซ์ที่ได้จากการคัดแถวที่ i และ

      หลักที่ j ของเมตริกซ์ A  ออก เขียนแทนไมเนอร์  a_ij  ด้วย M_ij

4.2 โคแฟกเตอร์ของ a_ij  คือ ผลคูณของ (-1) ^i+j  และ M_ij

      เขียนแทนด้วย C_ij  = (-1) ^i+j M_ij

 

                                4.3 เมตริกผูกพัน (Adjonint Matrix)  ของ A  คือ ทรานสโพสของเมตริกที่ได้มา

      จากการแทนที่สมาชิกทุกตัวด้วย โคแฟกเตอร์ของสมาชิกนั้น  เขียนแทนด้วย

       adj(A) = [C_ij] ^t

 

5.  คุณสมบัติที่น่าสนใจในการหาDeterminant

                                ให้ A และ B เป็นเมตริกซ์จัตุรัส

                                1. det (AB) = det (A) det (B)

                                2. det (A)    = det (A^t)

                                3. det (A). det (A^-1) = 1 เมื่อ A เป็น nonsingular Matrix

                                4. det (Aⁿ)   = det (A) ⁿ  โดยที่ n Î I⁺

5. ถ้า A มีสมาชิกทุกตัวในแถวใดแถวหนึ่งหรือหลักใดหลักหนึ่งเป็น 0 ตลอด

    แล้ว det (A) = 0

6. ถ้า A มีสมาชิกใน 2 แถวใดๆ หรือ 2 หลักใดๆ เหมือนกันทุกประการ 

    แล้ว det (A) = 0

7. ถ้า A มีสมาชิกแถวใดแถวหนึ่ง ( หรือหลักใดหลักหนึ่ง) เป็น K เท่าของแถวหนึ่ง

    (หรืออีกหลักหนึ่ง) แล้ว det (A) = 0

8. ถ้า B มีสมาชิกที่ได้จากการเอาค่าคงที่ K ซึ่ง k¹ 0  คูณสมาชิกในแถวใดแถวหนึ่ง

    หรือหลักใดหลักหนึ่งของ A จะได้ det (B) = Kdet (A)

9. ถ้า A เป็นสมาชิกจัตุรัสมิติ n x n และ B = KA  จะได้ว่า det (B) = Kⁿdet (A)

    ในกรณี K = -1  จะได้

                                                                                det (A) เมื่อ n เป็นเลขคี่

                det (-A) = (-1)ⁿ det (A)  =

                                                                                -det (A) เมื่อ n เป็นเลขคู่

และ

 

สำหรับเมตริกซ์จัตุรัสมิติอื่นๆ  สูตรก็จะเป็นไปในทำนองเดียวกัน

 

11. ถ้าเมตริกซ์ B ได้จากการสลับสองแถว ( หรือสองหลักใดๆ) ของ A

      แล้วจะได้ det (B) = -det (A) 

12. จาก A ซึ่งเป็นเมตริกซ์ขนาด n x n ถ้ามีการเปลี่ยนสมาชิกในแถวที่ i (หรือ

      หลักที่ j ) โดยเอา K คูณสมาชิกในหลักที่ j โดยที่ i ¹ j แล้วสมารถบวกกับ

      สมาชิกของแถวที่ i จะได้ ดีเทอร์มิเนนต์ เท่าเดิมเสมอ  คุณสมบัติข้อนี้มี

      ประโยชน์ในการหาดิเทอร์มิเนนต์ของเมตริกซ์ชนิดต่างๆ

13. ดิเทอร์มิเนนต์ของเมตริกซ์ A มิติ n x n  หาได้จากการกระจายโคแฟกเตอร์

                1. กระจายโคแฟกเตอร์ในแถวที่ i

                                det (A) = a_{ij1 .}C_ij1 + a_{ij2 .}C_ij2 + a_ij3.C_ij3+…+ a_ni.C_ni

                        2. กระจายโคแฟกเตอร์ในหลักที่ j

                                det (A) = a_{ij1 .}C_ij1 + a_{ij2 .}C_ij2 + a_ij3.C_ij3+…+ a_{nj .}C_nj

14. Aadj(A) = adj(A).A  = det(A).I_n

 

อินเวอร์สของเมตริกซ์

                1. เงื่อนไขที่จะมีอินเวอร์สการคูณ

                                สำหรับจัตุรัส A ใด ๆ จะสามารถหาอินเวอรส์การคูณของ A ได้ก็ต่อเมื่อ

                                det(A) ¹ 0

                2.  การหาอินเวอร์สของเมตริกซ์

                                1.  เมตริกซ์ | x |

                                                ถ้า A = [a]  และ a ¹ 0  จะได้ A^–1 =  

                                2. เมตริกซ์  2x2

                                                ถ้า A =   โดยที่ ad –bc ¹ 0  จะได้ A^–1 = 

                                3. สำหรับเมตริกซ์จัตุรัสใดๆ ที่เป็น nonsingular Matrix สามารถหาอินเวอร์สได้

   จากสูตร

A^–1  =  adj(A)

 

                3.  คุณสมบัติของอินเวอร์สเมตริกซ์

                                กำหนด A และ B เป็น nonsingular Matrix มิติเดียวกัน

                                1. det (A^-1) ^-1   = A

                                2. det (AB) ^–1   =  B^–1  A^–1

                                3. det (A^-1) ^t    = (A ^t) ^–1

                                4. (Aⁿ)^-1         = (A ^-1) ⁿ   เมื่อ n Î I⁺

                                5. (KA)^-1        =  A ^–1  โดยที่  K ¹ 0

ตรรกศาสตร์

 

สรุปเนื้อหาสำคัญ

                1.  ประพจน์  คือ  ประโยคบอกเล่าหรือปฏิเสธที่มีค่าความจริงเป็นจริงหรือเป็นเท็จเพียงอย่างใดอย่างหนึ่ง

                2.  หลักการจำค่าความจริงของประพจน์มีตัวเชื่อม

                                1) ตัวเชื่อม และ (Ù)                         T Ù T ได้  T ที่เหลือ F  หมด

                                2) ตัวเชื่อม หรือ (Ú)                         F Ú F    ได้  F ที่เหลือ T  หมด

                                3) ตัวเชื่อม ถ้า…แล้ว (®)              T®F ได้  F  ที่เหลือ T  หมด

                                4) ตัวเชื่อม ก็ต่อเมื่อ («)               ค่าความจริงตรงกันได้ T ถ้าต่างกันได้ F

                3.  ประพจน์ที่สมมูลกัน คือ ประพจน์ที่มีค่าความจริงตรงกันทุกกรณี

                4.  สัจนิรันดร์ (Tautology) คือ ประพจน์ที่มีค่าความจริงเป็นจริงเสมอ

                5.  ประพจน์ที่สมมูลกันที่สำคัญ

                                p Ù (q Ú r)   º  ( p Ù q ) Ú (p Ù r)

                                p Ú  (q Ù r)  º  ( p Ú q ) Ù (p Ú r)

                                       p ® q        º  ~p Ú q

                                       p ® q        º  ~q ® ~p

                                       p « q   º  (p ® q) Ù (q ® p)

                                       p « q   º  ~p «~q

                6. นิเสธ

                                      ~ ( p Ù q )    º ~p Ú ~q

                                      ~ ( p Ú q )    º ~p Ù ~q

                                       ~ ( p ® q ) º  p Ú ~q

                                       ~"x [p(x)]  º $x [~p(x)]

                                       ~$x [p(x)]  º "x [~p(x)]

                7. การหาความจริงของประโยคที่มีตัวบ่งปริมาณ

                                "x [P(x)]                          จะเป็น T เมื่อเซตคำตอบเป็นm ไม่เช่นนั้นจะเป็น F

                                $x [P(x)]                           จะเป็น F เมื่อเซตคำตอบเป็นf ไม่เช่นนั้นจะเป็น T

                                "x,"y [P(x,y)]              จะเป็น T เมื่อสำหรับ x และ y ทุกค่า P(x,y) เป็นจริง

 

                                "x,$y [P(x,y)]               จะเป็น T เมื่อสำหรับ x แต่ละตัว จะต้องมี y ที่ทำให้

 P(x,y) เป็นจริง

                                $ x,"y [P(x,y)]              จะเป็น T เมื่อมี x ที่ทำให้ P(x,y) เป็นจริงสำหรับ y ทุกค่า

                                $x, $y [P(x,y)]               จะเป็น T เมื่อมี x และ y ที่ทำให้ P(x,y) เป็นจริง

 

การอ้างเหตุผล (Argument)

                การอ้างเหตุผลเป็นการอ้างว่าประพจน์  p₁ , p₂ , p₃ , . . . p_n  สามารถสรุประพจน์ Q

ซึ่งสมเหตุสมผล (Valid) หรือ   ไม่สมเหตุสมผล (Invalid)   การอ้างเหตุผลจะสมเหตุสมผล

ก็ต่อเมื่อ P₁A P₂ A P₃A… AP_n ® Q เป็นสัจนิรันดร์  และจะสรุปว่าไม่สมเหตุสมผล ก็ต่อเมื่อ

P₁A P₂ A P₃A… AP_n ® Q ไม่เป็นสัจนิรันดร์

 

รูปแบบการอ้างเหตุผล (Argument Form)

รูปแบบการอ้างเหตุผลที่สมเหตุสมผลและนิยมใช้

1. Modus ponens                                                5.  Dislunctlve Sylloglsm

    เหตุ       1. p ® q                                            เหตุ         1. p Ú q

                                    2. p                                                                          2. ~ p

                    ผล          q                                                          ผล               q

2. Modus Tallens                                               6.  เหตุ        1. p ® r

    เหตุ    1. p ® q                                                                 2. q ® s

                   2. ~ q                                                                     3. p Ú q

    ผล         ~ p                                        ผล          r Ú s

3. Law of  Sylloglsm                                        7. Law of Slmpllflcution

    เหตุ   1. p ® q                                                เหตุ          p Ù q

                  2. q ® r                                               ผล             p

    ผล        p ® r

 

 

4. Law of  Contrapasltive                                8. Law of  addition

    เหตุ p ® q                                                         เหตุ   p

    ผล   ~q ®  ~ p                             ผล   p Ú q

    หรือผล ~ p Ú q

ความสัมพันธ์และฟังก์ชัน

 

1. ผลคูณคาร์ทีเซียน

                ถ้า A และ B  เป็นเชต ผลคูณคาร์ทีเซียนของ A และ B คือเชตที่มีสมาชิกเป็นคู่อันดับ (x,y)  โดยที่ x e A และ  y e B  และเขียนแทนด้วยสัญลักษณ์ AxB

 

                นั่นคือ    AxB =  {(x,y) x e A และ y e B}

 

คุณสมบัติที่สำคัญ

                1.  ถ้า A มีสมาชิก m ตัวและ B มีสมาชิก n ตัว A x B จะมีสมาชิก m x n ตัว

                2.  A x B = f ก็ต่อเมื่อ A = f หรือ B = f

                3.  A x (B ÈC)  = (A x B) È (A x C)

                4.  A x (B &Ccedil