Pengaturcaraan Linear, Contoh Kerja (sederhana)

(a) Rantau ini disempadani oleh empat garis: paksi $x=0$ dan $y=0$, garis $x+y=8$, dan garis $y=3x$. Cari bucu dengan menyelesaikan sempadan ini secara berpasangan, kekalkan hanya persilangan yang memenuhi setiap ketaksamaan.

$$y=3x,\; y=0 \;\Rightarrow\; (0,0)$$

$$x+y=8,\; y=0 \;\Rightarrow\; (8,0)$$

$$y=3x,\; x+y=8 \;\Rightarrow\; x+3x=8,\; 4x=8,\; x=2,\; y=6$$

Maka rantau itu ialah segi tiga dengan bucu $O(0,0)$, $B(8,0)$ dan $C(2,6)$.

(b) Nilaikan $k=5x+4y$ pada setiap bucu:

$$\text{Di } O(0,0):\quad k=5(0)+4(0)=0$$

$$\text{Di } B(8,0):\quad k=5(8)+4(0)=40$$

$$\text{Di } C(2,6):\quad k=5(2)+4(6)=10+24=34$$

(a) Terjemah setiap syarat. 'Paling banyak 12 keseluruhan' mengehadkan jumlah; 'pai paling banyak dua kali kek' mengehadkan $y$ kepada $2x$; 'sekurang-kurangnya 2 kek' menetapkan had bawah pada $x$.

$$x+y\le 12,\qquad y\le 2x,\qquad x\ge 2$$

(b) Bucu rantau ini ialah tempat garis sempadan $x=2$, $y=0$, $y=2x$ dan $x+y=12$ bertemu secara berpasangan. Selesaikan setiap pasangan dan kekalkan titik yang mematuhi setiap kekangan:

$$x=2,\; y=0 \;\Rightarrow\; (2,0)$$

$$x=2,\; y=2x \;\Rightarrow\; y=4,\quad (2,4)$$

$$y=2x,\; x+y=12 \;\Rightarrow\; 3x=12,\; x=4,\; y=8,\quad (4,8)$$

$$x+y=12,\; y=0 \;\Rightarrow\; (12,0)$$

Sekarang nilaikan untung $P=5x+9y$ pada setiap bucu:

$$\text{Di }(2,0):\; P=5(2)+9(0)=10$$

$$\text{Di }(2,4):\; P=5(2)+9(4)=10+36=46$$

$$\text{Di }(4,8):\; P=5(4)+9(8)=20+72=92$$

$$\text{Di }(12,0):\; P=5(12)+9(0)=60$$

Dua kekangan $\ge$ menolak rantau menjauhi asalan, jadi ia terbentang ke atas-kanan tanpa had atas, tiada maksimum, tetapi minimum wujud pada suatu bucu. Cari bucu dengan memasangkan sempadan dan kekalkan yang memenuhi kedua-dua ketaksamaan.

$$x+2y=8,\; y=0 \;\Rightarrow\; (8,0)$$

$$2x+y=10,\; x=0 \;\Rightarrow\; (0,10)$$

Dua garis condong itu juga bersilang. Ambil $x=8-2y$ daripada yang pertama dan gantikan ke dalam yang kedua:

$$2(8-2y)+y=10 \;\Rightarrow\; 16-3y=10 \;\Rightarrow\; y=2,\; x=4$$

Maka bucu rantau itu ialah $(8,0)$, $(4,2)$ dan $(0,10)$. Persilangan paksi yang lain masing-masing melanggar kekangan yang bukan asalnya: $(5,0)$ memberi $x+2y=5<8$, dan $(0,4)$ memberi $2x+y=4<10$, jadi kedua-duanya bukan bucu.

Sekarang nilaikan $C=3x+2y$:

$$\text{Di }(8,0):\; C=3(8)+2(0)=24$$

$$\text{Di }(4,2):\; C=3(4)+2(2)=12+4=16$$

$$\text{Di }(0,10):\; C=3(0)+2(10)=20$$

Sesuatu titik terletak dalam rantau tersaur hanya jika ia memenuhi setiap ketaksamaan serentak, bukan hanya satu sahaja. Uji setiap titik terhadap $2x+y\le 10$ dan $x+3y\le 12$, ketiga-tiga titik sudah mempunyai $x\ge 0$ dan $y\ge 0$.

$$A(3,2):\quad 2(3)+2=8\le 10, \qquad 3+3(2)=9\le 12$$

Kedua-dua had dipenuhi untuk $A$, jadi ia memenuhi setiap kekangan dan terletak di dalam rantau.

$$B(5,3):\quad 2(5)+3=13>10 \qquad C(1,4):\quad 1+3(4)=13>12$$

$B$ sudah melanggar kekangan pertama, manakala $C$ memenuhi yang pertama ($2(1)+4=6\le 10$) tetapi melanggar yang kedua, jadi kedua-duanya bukan titik tersaur.

(a) Gunakan kedua-dua pintasan untuk membentuk persamaan: garis itu memotong paksi-$x$ pada $4$ dan paksi-$y$ pada $6$, jadi tulis dalam bentuk pintasan dan padamkan pecahan.

$$\frac{x}{4}+\frac{y}{6}=1 \;\Rightarrow\; 3x+2y=12$$

(b) Oleh sebab titik asalan terletak di dalam rantau, gantikan $(0,0)$ ke dalam ungkapan di sebelah kiri dan bandingkan dengan $12$.

$$3(0)+2(0)=0, \quad 0<12$$

Gantikan bucu itu dan nilai maksimum yang diberi ke dalam fungsi objektif; ini memberi satu persamaan dalam $q$.

$$3(6)+q(4)=38$$

$$18+4q=38 \;\Rightarrow\; 4q=20 \;\Rightarrow\; q=5$$

(a) Rantau ini disempadani oleh paksi, garis $x=8$ dan garis $x+2y=12$. Pasangkan sempadan-sempadan itu untuk mencari setiap bucu.

$$x=0,\;y=0 \;\Rightarrow\;(0,0) \qquad x=8,\;y=0 \;\Rightarrow\;(8,0)$$

$$x=8,\;x+2y=12 \;\Rightarrow\; y=2,\;(8,2) \qquad x=0,\;x+2y=12 \;\Rightarrow\; y=6,\;(0,6)$$

(b) Nilaikan $K=x+2y$ pada setiap bucu.

$$K(0,0)=0,\quad K(8,0)=8,\quad K(8,2)=8+4=12,\quad K(0,6)=0+12=12$$

$K$ mencapai $12$ pada kedua-dua $(8,2)$ dan $(0,6)$, dan ini bukan kebetulan. $K=x+2y$ mempunyai kecerunan yang sama tepat dengan garis sempadan $x+2y=12$, jadi setiap titik di sepanjang tepi itu sudah memenuhi $x+2y=12$, bermakna $K=12$ sepanjang tepi itu, bukan hanya pada kedua-dua hujungnya.

(a) Terjemah setiap syarat. 'Sekurang-kurangnya 12 keseluruhan' menetapkan had bawah pada jumlah; 'kotak kebersihan sekurang-kurangnya separuh kotak makanan' mengehadkan $y$ daripada bawah oleh $\frac{x}{2}$; 'paling banyak 16 kotak makanan' mengehadkan $x$.

$$x+y\ge 12,\qquad x\le 2y,\qquad x\le 16$$

(b) Bucu rantau ini terletak di tempat $x+y=12$, $x=2y$ dan $x=16$ bertemu secara berpasangan, bersama paksi $x=0$. Selesaikan setiap pasangan yang relevan:

$$x=0,\;x+y=12 \;\Rightarrow\;(0,12) \qquad x+y=12,\;x=2y \;\Rightarrow\; 2y+y=12,\;y=4,\;x=8,\;(8,4)$$

$$x=2y,\;x=16 \;\Rightarrow\; y=8,\;(16,8)$$

Sekarang nilaikan kos $C=8x+5y$ pada setiap bucu:

$$C(0,12)=8(0)+5(12)=60,\quad C(8,4)=64+20=84,\quad C(16,8)=128+40=168$$