204512/บรรยาย 11

---

จดบันทึกคำบรรยายโดย:

นางสาว สุกัลยา เลิศวิวัฒน์สกุล   รหัส : 50653955

นางสาว กมลวรรณ โพธิ์แก้ว       รหัส : 50653724

---

ทบทวน

Primal Linear Programming

minimize :

$\sum _{j=1}^{n}$c_jx_j

subject to :

$\sum _{j=1}^{n}$a_ijx_j ≥ b_i   ; i = 1,…,m

    x_i ≥ 0  ; j = 1,…,n

Dual Linear Programming

maximize :

$\sum _{i=1}^{m}$b_iy_i

subject to :

$\sum _{i=1}^{m}$a_ijy_i ≥ c_j   ; j = 1,…,n

    y_i ≥ 0  ; i = 1,…,m

---

ตัวอย่าง 1 - Assigment
โจทย์ - มีงาน n งาน

มีพนักงาน n คน

assogn งาน j ให้กับพนักงาน i ใช้ cost C_ij

ต้องการ assign งานให้กับพนักงาน โดยที่งาน 1 งานให้พนักงาน 1 คน

   และพนักงาน 1 คนได้งาน 1 งาน

วิธีทำ

ให้ x_ij เป็น 1 ถ้า assign งาน j ให้กับ i

  เป็น 0 ถ้าเป็นอื่นๆ

Primal

minimize :

$\sum _{i=1}^{n}\sum _{j=1}^{m}$c_ijx_ij

subject to :

$\forall j$;       $\sum _{i=1}^{n}$x_ij = 1

$\forall i$;       $\sum _{j=1}^{n}$x_ij = 1

$\forall i,j$;   x_ij ∈ {0,1}

//--------------------------------------------------------------------------------------------------------------------//
note จาก x_ij ∈ {0,1} ไม่สามารถใชกัน linear progame ได้ ฉะนั้นเราจะแก้ subject to เป็น

$\forall j$;       $\sum _{i=1}^{n}$x_ij ≥ 1     ----(β_j)

$\forall i$;       $\sum _{j=1}^{n}$x_ij ≥ 1     ----(α_i)

$\forall i,j$;   x_ij ≥ 0

จะได้ว่า relaxed linear program

//--------------------------------------------------------------------------------------------------------------------//
เขียนเป็น Dual

maximize :

$\sum _{i=1}^{n}$α_i + $\sum _{j=1}^{m}$β_j

subject to :

$\forall i,j$;   α_i + β_j = 1

$\forall i$;       α_i ≥ 0

$\forall j$;       β_j ≥ 0

---

ตัวอย่าง 2
โจทย์ จากตัวอย่างที่ 1 ต้องการหา optimal maching?

วิธีทำ รูป

---

Duality

จาก Prob. priallity

นิยาม 

Primal

min cx

s.t. Ax ≥ b

  x ≥ 0

Dual

max y^'b

s.t. A^Ty ≤ c

  y ≥ 0

Thm: Weak duality

ถ้า x และ y เป็น feasible solution

y^'b ≤ c^'x

---

Proof:

y^'b ≤ y^'Ax ≤ c^'x

---

Thm: Storng duality

ถ้า x^* และ y^* เป็น 2optimal solution ของ PLP, DLP

c^'x^* = b^'y^*

---

---