การแปลงปัญหาที่ไม่เป็นเชิงเส้น

การหาค่าที่เหมาะสมที่สุดใน Python เบื้องต้น

Jasmin Ludolf

Content Developer

หาค่าสูงสุดของฟังก์ชันที่ไม่เป็นเชิงเส้น

ศิลปินผลิตภาพวาดได้สูงสุด 16 ชิ้น โดยมีต้นทุน $C(q) = \sqrt q$ เมื่อ $q$ คือปริมาณ
อุปสงค์ผกผันคือ $p=\frac{3}{\sqrt q}$ เมื่อ $p$ คือราคา
$\max \Pi = pq - C=\frac{3}{\sqrt q}q-\sqrt q = 2\sqrt q$

$$\max 2\sqrt q$$

$$s.t. \ \ \ \ q\leq 16 $$

หญิงกำลังวาดภาพบนผืนผ้าใบ

SciPy หรือ PuLP?

SciPy: milp รองรับเฉพาะฟังก์ชันวัตถุประสงค์เชิงเส้น
PuLP:

model = LpProblem('Artist', LpMaximize)
q = LpVariable('q', lowBound=0, upBound=16)
model += 2 * q**(1/2)

--> 3 model += 2 * q**(1/2)

TypeError: unsupported operand type(s) for ** or pow(): 'LpVariable' and 'float'

แทนค่าตัวแปรเพื่อทำให้เป็นเชิงเส้น

แทนค่า $z = \sqrt q$
$\rightarrow$ $\Pi=2\sqrt q =2z$
$\rightarrow$ ข้อจำกัดกำลังการผลิต $z^2\leq 16\Leftrightarrow z\leq 4$

model = LpProblem('Artist', LpMaximize)
z = LpVariable('z', lowBound=0, upBound=4, cat='Integer')
model += 2 * z

model.solve() 
print(f"Solution is {LpStatus[model.status]}.")
print(f"The optimal number of paintings is {round(z.varValue**2)}.")

Solution is Optimal. 
The optimal number of paintings is 16.

การจัดสรรงบประมาณเมื่อโครงการมีความสัมพันธ์กัน

โจทย์

โครงการ $A$, $B$, $C$; $A$ เป็นเงื่อนไขเบื้องต้นของ $B$
กำไรตามลำดับคือ $V$ = [250, 200, 300]
เงินลงทุนที่ต้องการคือ $I$ = [2000, 1900, 2500] และมีงบประมาณเพียง $4600

การสร้างโมเดล

$o_A$, $o_B$, $o_C$ เป็นตัวแปรไบนารี แสดงการเลือกโครงการ

$\max\ \ o_AV_A + o_Ao_BV_B + o_CV_C$

$s.t.\ \ \ \ o_AI_A + o_Ao_BI_B + o_CI_C\leq 4600$

ไอคอนการบริหารงบประมาณ

การทำให้เป็นเชิงเส้น: ผลคูณของตัวแปรไบนารี

แทน $o_Ao_B=o_{AB}$
เพิ่มข้อจำกัด
- $o_{AB}\leq o_{A}$
- $o_{AB}\leq o_{B}$
- $o_{AB}\geq o_{A} + o_{B} -1$
ปัญหาลดรูปเป็น

$$\max\ \ o_AV_A + o_{AB}V_B + o_CV_C$$

$$s.t.\ \ \ \ o_AI_A + o_{AB}I_B + o_CI_C\leq 4600$$

$$ o_{A} + o_{B} -1 \leq o_{AB}\leq o_{A}, o_{B}$$

การจัดสรรทรัพยากรเมื่อมีต้นทุนการฝึกอบรม

จัดสรร 120 งานเพื่อให้ต้นทุนต่ำที่สุด
พนักงานอาวุโส ($S$) พนักงานทั่วไป ($J$) และนักศึกษาฝึกงาน ($I$)
ค่าฝึกอบรมนักศึกษาฝึกงาน $500
ต้นทุนต่องาน $c$ = [30, 40, 5]
เวกเตอร์ $x$: จำนวนงานที่จัดสรรอย่างเหมาะสม
ไบนารี $o$: ระบุว่านักศึกษาฝึกงานได้รับการฝึกอบรมหรือไม่
$TC = 30x_S+40x_J+(5x_I+500)o$

บุคคลถือดินสอยืนอยู่ข้างรายการสิ่งที่ต้องทำขนาดใหญ่

การทำให้เป็นเชิงเส้น: ผลคูณของไบนารีและตัวแปรต่อเนื่อง

วิธี BigM นำค่าจำนวนมาก M มาใช้
แทนผลคูณด้วย $z = (5x_I+500)o$
กำหนดข้อจำกัด
- $-oM\leq z \leq oM$
- $-(1-o)M \leq z- (5x_I+500)o \leq (1-o)M$

มาฝึกกันเถอะ!

การหาค่าที่เหมาะสมที่สุดใน Python เบื้องต้น