persamaan linear

PENGATURCARAAN LINEAR MTE 3104

1.0 Pengaturcaran Linear

Pengaturcaraan linear adalah proses mengambil pelbagai ketaksamaan linear

berhubungan dengan situasi tertentu, dan mencari yang "terbaik" nilai boleh

diperolehi di bawah syarat-syarat itu. Satu contoh yang tipikal akan mengambil had

bahan-bahan dan buruh, dan kemudian menentukan yang "terbaik" pengeluaran

peringkat bagi keuntungan maksimal di bawah syarat-syarat itu.

"Kehidupan sebenar", pengaturcaraan linear adalah bahagian yang amat

penting pada kawasan matematik yang dikenali sebagai "pengoptimuman teknik".

Bidang pengajian (atau sekurang-kurangnya keputusan yang dipohon itu) digunakan

setiap hari dalam organisasi dan peruntukan sumber. System ini "kehidupan

sebenar" boleh mempunyai berpuluh-puluh atau beratus-ratus pemboleh ubah, atau

lebih. Algebra, walaupun, anda hanya akan bekerja dengan mudah (dan graphable)

pada mana-mana dua pembolehubah linear.

Proses umum untuk menyelesaikan latihan linear-programming graf

ketidaksamaan (yang dipanggil "kekangan") untuk membentuk satu kawasan yang

berdinding-mati pada x, y –“plane” (Dipanggil "wilayah kemungkinan"). Kemudian

anda memikirkan koordinat sudut rantau kemungkinan ini (iaitu, anda mencari titik-

titik persilangan pelbagai pasangan garisan), dan ujian-mata sudut dalam formula

(dipanggil "persamaan pengoptimuman") untuk anda cuba untuk mencari nilai

tertinggi atau terendah.

Cari nilai yang maksimal dan minimal daripada = 3x + 4dan tertakluk kepada

yang berikut kekangan:

{x+2 y ≤143x− y≥0x− y≤2 }

Tiga ketaksamaan dalam penyokong “curly braces” adalah kekangan.

Formula " daripada = 3 x + 4 dan " adalah persamaan pengoptimuman. Saya perlu

mencari (x, dan) sudut mata rantau kemungkinan bahawa kembali nilai-nilai terbesar

dan terkecil daripada.

Langkah pertama saya adalah untuk menyelesaikan ketidaksamaan masing-

masing untuk lebih mudah graf bentuk bersamaan:

AMODD DEAL TINGADON 3


{x+2 y ≤143x− y≥0x− y≤2 }⇒ {y ≤−12 x+7y ≤3x

y≥ x−2}

Untuk mencari titik sudut yang tidak sentiasa jelas dari graf - Saya akan

memasangkan talian (sehingga membentuk sistem persamaan linear) dan

menyelesaikan:

dan=−( 12 ) x+7=3xdan=3 x

dan=−( 12 ) x+7dan=x−2

dan=3 x

dan=x−2

−( 12 )x+7=3x−x+14=6 x

14=7 x

2=x

dan=3 (2 )=6

−( 12 )x+7=x−2−x+14=2x−4

18=3x

6=x

dan (6 )−2=4

3 x=x−2

2 x=−2

x=−1

dan3 (−1 )=−3

Titik sudut pada (2, 6) Titik sudut pada (6, 4) Sudut pt. Pada(-1,-3)

Oleh itu titik sudut ialah (2,6), (6,4), dan (-1, -3).


http://www.purplemath.com/modules/systlin1.htm


Seseorang benar-benar pintar membuktikan bahawa, bagi sistem linear

seperti ini, maksimum dan nilai minimum persamaan pengoptimuman akan sentiasa

berada pada sudut-sudut rantau kemungkinan.

Jadi, untuk mencari penyelesaian untuk latihan ini, saya hanya perlu plug-tiga

mata kepada "daripada = 3x + 4dan".

(2, 6): daripada = 3(2) + 4(6) = 6 + 24 = 30

(6, 4): daripada = 3(6) + 4(4) = 18 + 16 = 34 (–1, –3): daripada = 3(–1) + 4(–3) = –3 – 12 = –15

Kemudian yang maksimum daripada = 34 berlaku pada (6, 4),

dan sekurang-kurangnya daripada = –15 berlaku pada (–1, –3).




Graf Ketaksamaan Linear

Untuk garisan lurus ax + by = c, dimana

b > 0, kawasan garisan diatas adalah

memenuhi ketaksamaan ax + by > c

sementara kawasan di garisan di bawah

memenuhi ketaksamaan ax + by < c

Persamaan bagi sempadan kawasan

yang boleh dikenalpasti iaitu;

Y =mx + c

y – y1 = m(x – x1)

xa+ yb=1


Kenyataan Matematik Ketaksamaan

y lebih banyak daripada x y > x

y lebih kecil daripada x y < x

y tidak lebih banyak daripada x y ≤ x

y tidak kurang daripada x y ≥ x

y lebih kurang k darab dengan x y ≥ kx

y adalah hampir kepada k darab dengan x y ≤ kx

Nilai maxima x ialah k x ≤ k

Nilai minima x ialah k x ≥ k

Hasil tambah x dan y adalah tidak lebih daripada k x + y ≤ k

y adalah lebih daripada x lebih kurang dengan k y – x ≥ k

y adalah lebih besar daripada k darap x y ≤ kx

y mesti melebihi x dengan lebih kurang k y – x ≥ k


ax + by > k

ax + by < k

ax + by = k


Konsep ketaksamaan linear


y

x

k adalah darap lazim a dan b.

Garisan padu (_________) merangkumi titik pada garisan.

Garisan putus - putus (_________) tidak merangkumi titik pada garisan.



Definisi pengaturacaraan merupakan masalah pengoptimum dengan beberapa perkara yang

mesti dipatuhi

Maksimumkan/minimumkan fungsi

linear pembolehubah keputusan

Nilai – nilai pembolehubah keputusan

mestilah memenuhi set kekangan

Sebarang pembolehubah x1 mestilah

bukan negatif.

Terdapat 3 langkah asas untuk membuat suatu model pengaturancaraan linear.

Kenalpasti pembolehubah keputusan. Pembolehubah keputusan ,menerangkan

keputusan yang perlu dibuat dan boleh diwakili oleh huruf seperti x , y, z dan

sebagainya.

Kenalpasti fungsi objektif iaitu fungsi yang hendak

dimaksimumkan atau diminimumkan

Kenalpasti kekangan yang terdapat dalam masalah dan wakilkan

kekangan dalam bentuk persaamaan/ ketaksamaan . kekangan mestilah

linear dalam sebutan pembolehubah-pembolehubah keputusan.



KAEDAH PENYELESAIAN

Graf

Simpleks

Kaedah M

Kaedah Dua Fasa

Dua pembolehubah keputusan sahaja

Dua/lebih pembolehubah keputusan dan

kekangan (≤) sahaja.

Kekangan (≤), (=) dan/ atau (≥)



PENYELESAIAN BERGRAF

Untuk penjelaskan kaedah graf bagi penyelesaian pengaturcaraan linear,

langkah-langkah yang perlu adalah melihat kepada kekangan terlebih

dahulu kemudian diikuti dengan fungsi objektif.

Tentukan nilai-nilai pembolehubah keputusan yang menyesuaikan semua

kekangan dengan meneliti satu persatu kekangan yang terlibat bagi model

Pengaturacaraan Linear tersebut.

Setiap kekangan akan mengizinkan nilai-nilai tertentu untuk pembolehubah

keputusan yang sesuai dengan kekangan berkenaan. Nilai-nilai ini

dinamakan nilai-nilai tersaur manakala nilai-nilai yang tidak menyesuaikan

kakangan dinamakan nilai-nilai tidak tersaur.

Jika masalah tersebut mempunyai penyelesaian, semua kekangan dalam

masalah itu akan membentuk satu kawasan sepunya yang dinamakan

sebagai kawasan tersaur dan penyelesaian yang terdapat dalam kawasan

tersebut dinamakan penyelesaian tersaur.


Rantau tersaur

Perkara yang paling penting skelai dalam bab ini ialah set kesemua titik dalam satah “memuaskan” misalnya, kesemua syarat (a) ke (b) dalam contoh.

Perslilangan bagi keempat-empat satah separuh tertutup tersebut ialah rantau

terlorek pada Rajah dan ia adalah set kesemua titik di atas atau di dalam sisiempat

ABCD. Rantau seperti ini dikenali sebagai rantau tersaur oleh kerana kesemua titik

dalam rantau ini memuaskan kesemua syarat (a) ke (b) dalam contoh diatas.

Keempat titik A, B, C dan D dikenali sebagai titik ekstrem bagi rantau.

A(1, -1) ialah penyelesaian bagi { x=1y=−1

B(3, -1) ialah penyelesaian bagi {x− y=4y=−1

C(4, 0)ialah penyelesaian bagi {x+2 y=4x− y=4

D(1 , 32 ) ialah penyelesaian bagi {x+2 y=4x=−1


Rantau Tersaur

A B

C

D


Famili Garis Lurus selari

Semua garis lurus dalam bentuk ax + by = c, dengan a dan b pemalar tetapi c

boleh mengambil nilai-nilai berlainan, membentuk suatu family garis lurus

selari dengan setiap satunya mempunyai kecerunan - ab

dan pintasan pada

paksi –y, cb

.

Pertimbangkan garis lurus x + y = c dengan c boleh mengambil nilai-nilai

berlainan.

Rajah dibawah menunjukkan beberapa kedudukan bagi family garis lurus

selari.

Kita dapati bahawa:

Kesemua garis lurus adalah selari

Garis lurus akan bergerak lebih jauh daripada asalan ke atas

apabila nilai c akan menokok; manakala garis lurus akan

bergerak lebih jauh daripada asalnya kebawah apabila nilai c

menyusut.

Dengan menggunakan kaedah garis bergerak seperti ini, kita dapat

mencarikan nilai maksimum dan nilai minimum bagi fungsi dalam bentuk f = ax + by

yang tertakluk kepada kekangan-kekangan tertentu.


c menokok

c menyusut


Pentafsiran masalah dan pembentukan model.

Sebelum mempertimbangkan kaedah penyelesaian masalah pengaturcaraan

linear secara mendalam, kita haruslah sanggup menyatakan sesuatu masalah

secara terpiawai.

Faktor-faktor yang utama dalam penyelesaian masalah pengaturacaraan

linear ialah objektif dan kekangan.

Objektif

Langkah pertama dalam penyelesaian masalah pengaturacaraan linear

adalah menentukan keputusan yang dikehendaki

Objektif.

Misalnya, objektif yang dikehendaki mungkin untuk memaksimumkan

keuntungan, atau sumbangan atau meminimumkan kos atau masa

sebarang sukatan lain yang sesuai.

Selepas menetapkan objektif itu, baharulah kita dapat menyatakan

unsur-unsur yang terlibat untuk mencapai objektif ini secara matematik.

Ungkapan matematik ini disebut fungsi objektif.

Kekangan

Keadaan yang menghadkan pencapaian objektid-objektif tersebut ke atas

sentiasa wujud.

Factor-faktor ini dikenali sebagai batasan atau kekangan. Batasan-batasan

dalam sebarang masalah ini haruslah dicamkan dengan jelas dan dinyatakan

secara matematik sebelum masalah dapat diselesaikan.



Pengaturcaraan masalah lelurus

adalah di mana kita adalah untuk mencari nilai maksimum atau minimum

ungkapan linear

ax + by + cz +. . .

(Dipanggil fungsi objektif), Tertakluk kepada beberapa linear kekangan borang

Ax + By + Cz +. . . ≤ N

atau

Ax + By + Cz +. . . ≥ N.

Nilai terbesar atau terkecil fungsi objektif dipanggil nilai optimum,

Dan koleksi nilai-nilai x, y, z,. . . yang memberikan nilai optimum adalah

merupakan suatu penyelesaian optimum.

Pembolehubah x, y, z,. . . dipanggil keputusan pembolehubah.

Contoh: Berikut adalah satu contoh masalah pengaturcaraan linear:

Cari nilai maksimum

p = 3x - 2y + 4z

tertakluk kepada

4x + 3y - z ≥ 3

x + 2y + z ≤ 4

x ≥ 0, y ≥ 0, z ≥ 0

Fungsi objektif p = 3x - 2y + 4z. Kekangan

4x + 3y - z ≥ 3

x + 2y + z ≤ 4

x ≥ 0, y ≥ 0, z ≥ 0.



Melakarkan Set Penyelesaian Ketaksamaan satu Linear

Lakaran kawasan yang diwakili oleh ketaksamaan linear dalam dua pembolehubah:

1. Lakarkan garis lurus yang diperolehi dengan menggantikan ketaksamaan dengan

kesamaan.

2. Pilih titik ujian tidak on-line ((0,0) adalah pilihan yang baik jika garisan tidak melalui

asalan, dan jika garisan tidak melalui asal-usul titik di atas salah satu daripada paksi

akan menjadi pilihan yang baik) .

3. Jika titik ujian memuaskan ketaksamaan, maka set penyelesaian seluruh rantau

pada sebelah yang sama baris sebagai titik ujian. Jika tidak, ia adalah rantau di sisi

lain garis. Dalam kedua-dua kes, bayangan daripada sisi yang tidak mengandungi

penyelesaian, meninggalkan rantau menunjukkan penyelesaian.

Contoh: Untuk lakaran ketaksamaan linear 3x - 4y ≤ 12,

lakaran pertama garis 3x - 4y = 12.

Seterusnya, pilih asal-usul (0, 0) sebagai titik ujian (kerana ia tidak berada di

talian). Menggantikan x = 0, y = 0 dalam ketaksamaan memberi 3 (0) - 4 (0) ≤ 12.



Oleh kerana ini adalah satu kenyataan yang benar, (0, 0) dalam set

penyelesaian, jadi set penyelesaian yang terdiri daripada semua mata di sebelah

yang sama sebagai (0, 0). Rantau ini ditinggalkan unshaded, manakala rantau

(kelabu) berlorek disekat.

Wilayah dilaksanakan

Rantau dilaksanakan ditentukan oleh koleksi ketidaksamaan linear pengumpulan

mata yang memuaskan ketaksamaan.

Untuk lakar kawasan yang dilaksanakan ditentukan oleh koleksi ketidaksamaan

linear dalam dua pembolehubah:

Lakarkan kawasan-kawasan yang diwakili oleh setiap ketidaksamaan pada

graf yang sama, ingat untuk teduhkan bahagian-bahagian satah yang anda

tidak mahu.

Apakah yang tidak dilorekan apabila anda telah selesai rantau dilaksanakan.



Contohnya,

Rantau dilaksanakan untuk koleksi berikut ketidaksamaan rantau tidak berlorek yang

ditunjukkan di bawah (termasuk sempadan).

3x - 4y ≤ 12,

x + 2y ≥ 4

x ≥ 1

y ≥ 0.



Kaedah grafik

Kaedah grafik untuk menyelesaikan masalah pengaturcaraan linear dalam dua tidak

adalah seperti berikut.

1. Graf rantau dilaksanakan.

2. Pengiraan di koordinat titik sudut.

3. Gantikan koordinat titik sudut ke dalam fungsi objektif untuk melihat yang

memberikan nilai optimum.

4. Jika rantau dilaksanakan adalah tidak terbatas, kaedah ini boleh

mengelirukan: penyelesaian optimum sentiasa wujud apabila rantau

dilaksanakan disempadani, tetapi mungkin atau mungkin tidak wujud apabila

rantau dilaksanakan tanpa had.

Contoh : Meminimumkan C = 3x + 4y tertakluk kepada kekangan

3x - 4y ≤ 12,

x + 2y ≥ 4

x ≥ 1, y ≥ 0.

Rantau dilaksanakan untuk set ini kekangan yang ditunjukkan di atas. Di sini sekali

lagi dengan titik yang ditunjukkan sudut.

Jadual berikut menunjukkan nilai C

pada setiap titik sudut:

Oleh itu, penyelesaian x = 1, y = 1.5,

memberikan nilai minimum C = 9.


Kordina

t

C = 3x + 4y

(1, 1.5) 3(1)+4(1.5) = 9 minimum

(4, 0) 3(4)+4(0) = 12


Kaedah simplex untuk Masalah Maksimalisasi Standard

Untuk menyelesaikan masalah pemaksimuman standard menggunakan

kaedah simplex, Kita mengambil langkah-langkah berikut:

Langkah 1.

Tukar kepada sistem persamaan dengan memperkintenalenalkan kendur

pembolehubah untuk menghidupkan kekangan ke dalam persamaan, dan

menulis semula fungsi objektif dalam bentuk standard.

Langkah 2.

Tulis “tableau” awal.

Langkah 3.

Pilih lajur pangsi: Pilih nombor negatif dengan magnitud yang terbesar di baris

bawah (tidak termasuk kemasukan paling kanan). Lajur lajur pangsi. (Jika

terdapat dua calon, pilih salah satu) Jika semua nombor dalam baris bawah

sifar atau positif (tidak termasuk kemasukan paling kanan), maka anda telah

selesai: penyelesaian asas memaksimumkan fungsi objektif (lihat di bawah

untuk penyelesaian asas ).

Langkah 4.

Pilih pangsi dalam ruang pangsi: pangsi perlu sentiasa menjadi nombor

positif. Untuk setiap kemasukan b positif dalam ruang pangsi, mengira nisbah

a / b, di mana bilangan dalam ruang jawapan yang berturut-turut itu. Daripada

jumlah ini ujian nisbah, Pilih satu yang paling kecil. B nombor yang sepadan

pangsi.



Langkah 5.

Gunakan pangsi untuk mengosongkan ruang yang dalam cara yang biasa

(menjaga mengikut penetapan yang tepat untuk merumuskan operasi baris

yang diterangkan dalam Bab 2) dan kemudian melabel semula baris pangsi

dengan label dari ruangan pangsi. Pemboleh ubah yang pada asalnya

pelabelan baris pangsi berlepas atau keluar berubah-ubah dan pemboleh

ubah yang pelabelan ruang yang memasuki pemboleh ubah.

Langkah 6.

Pergi ke Langkah 3.



Penyelesaian Asas

Untuk mendapatkan penyelesaian asas sepadan dengan tablo mana-mana

dalam kaedah simplex, yang ditetapkan kepada sifar semua pemboleh ubah

yang tidak muncul sebagai label baris (ini adalah tidak aktif pembolehubah).

Nilai pembolehubah yang tidak muncul sebagai label berturut-turut (1

pembolehubah aktif) Bilangan dalam ruang yang paling kanan di baris

tersebut dibahagikan dengan bilangan berturut-turut itu dalam ruang yang

dilabel oleh pemboleh ubah yang sama.

Dalam tablo berikut

x dan daripada s t anda p Tahun

-1 0 0 1 0 0 0 4

1 0 3 0 0 8 0 12

4 0 0 0 3 0 0 2

-5 2 0 0 0 6 0 4

6 0 0 0 0 0 5 -25

penyelesaian asas

x = 0, y = 2, z = 4, s = 4, t = 2 / 3, u = 0, p = - 5,

dan pembolehubah aktif y, z, s, t, dan p.



Kekangan yang tidak standard

Untuk menyelesaikan masalah pengaturcaraan linear dengan kekangan Ax

bentuk + By +. . ≥ N dengan N positif, tolak pemboleh ubah lebihan dari sebelah

kiri, dan bukannya menambah pembolehubah kendur.

Penyelesaian asas yang sama kepada tablo awal tidak akan dilaksanakan

sejak beberapa pemboleh ubah yang aktif akan negatif, dan seterusnya kaedah-

kaedah untuk pivoting awal adalah berbeza dari orang-orang di atas.

Bintang pada semua baris yang memberikan nilai negatif bagi pembolehubah

aktif yang berkaitan (kecuali bagi pembolehubah yang objektif, yang dibenarkan

untuk menjadi negatif). Jika terdapat baris berbintang, anda akan perlu bermula

dengan Fasa I:

Fasa I: Masuk ke Wilayah dilaksanakan (menghapuskan Bintang)

Dalam barisan berbintang yang pertama, cari bilangan positif terbesar.

Gunakan nisbah ujian seperti dalam seksyen sebelumnya untuk mencari pangsi

dalam ruang itu (tidak termasuk baris bawah), maka pangsi terhadap kemasukan itu.

Jika nisbah terendah berlaku kedua-dua berturut-turut berbintang dan

berturut-turut tidak berbintang, pangsi berturut-turut berbintang dan bukannya yang

tidak berbintang. Ulangi sehingga tiada baris berbintang kekal, kemudian pergi ke

Fasa II.

Fasa II: Gunakan Kaedah Simpleks untuk Masalah Maksimalisasi Standard

Jika terdapat mana-mana penyertaan yang negatif di sebelah kiri baris bawah

selepas Fasa I, menggunakan kaedah yang diterangkan di atas untuk

menyelesaikan masalah pemaksimuman standard.


http://people.hofstra.edu/Stefan_Waner/RealWorld/Summary4.html#standard_method

http://people.hofstra.edu/Stefan_Waner/RealWorld/Summary4.html#standard_method


Kaedah simplex untuk Masalah meminimumkan

Untuk menyelesaikan masalah pengurangan yang menggunakan kaedah simplex,

ubahkannya kepada masalah pemaksimuman. Jika anda perlu untuk mengurangkan

c, sebaliknya memaksimumkan p = -c.

Masalah LP meminimumkan:

Kurangkan C = 3x + 4y - 8z tertakluk kepada kekangan

3x - 4y ≤ 12,

x + 2y + z ≥ 4

4x - 2y + 5z ≤ 20

x ≥ 0, y ≥ 0, z ≥ 0

boleh digantikan dengan yang berikut pemaksimuman masalah:

Memaksimumkan P = -3x - 4y + 8z tertakluk kepada kekangan

3x - 4y ≤ 12,

x + 2y + z ≥ 4

4x - 2y + 5z ≤ 20

x ≥ 0, y ≥ 0, z ≥ 0.



Kaedah Simpleks

2/lebih pembolehubah keputusan dan kekangan mestilah “ ≤”.

Langkah –langkah:

Langkah 1

Tukarkan kekangan(ketaksamaan) dalam bentuk piawai(persamaan).

Kekangan dengan ketaksamaan ≤ yang telah diubah dalam bentuk

persamaan mesti ditambah dengan pembolehubah lalaian, s.

Langkah 2

Pilih pembolehubah bukan asas yang masuk menjadi pembolehubah

asas dengan mengikut syarat keoptimuman.

Berhenti jika tiada lagi pembolehubah yang boleh masuk.

Penyelesaian optimum diperoleh apabila pemboleh asas mempunyai

nilai manakala pembolehubah bukan asas bernilai 0.

Langkah 3

Pilih pembolehubah asas yang keluar menjadi pembolehubah bukan

asas menggunakan syarat kesauran. Tentukan penyelesaian asas

yang baru dengan menggunakan pengiraan Gauss-Jordan.

(ulang langkah 1)

Syarat keoptimuman

Masalah pemaksimuman Masalah peminimuman

- Pembolehubah asas yang

masuk mempunyai pekali

paling negative pada baris z.

- Penyelesaian optimum

diperoleh jika kesemua pekali

pembolehubah bukan asas

pada baris z bukan negative.

- Pembolehubah asas yang

masuk mempunyai pekali

paling positif pada baris z.

- Penyelesaian optimum

diperoleh jika kesemua pekali

pembolehubah bukan asas

pada baris z bukan positif.



Syarat kesauran

Pembolehubah asas yang keluar mempunyai nisbah tak negative yang paling

kecil(penyebut mesti lebih besar dari sifar).

Nisbah = Nilai pada sebelahkanannilai pada lajur pangsi

Gauss – Jordan

Baris baru = baris lama – (pekali jalur pangsi x baris pangsi baru)

Kaedah M

System kekangan bertanda ≥, = dan ≤

System kekangan yang digunakan memerlukan nilai (pemalar) diletakkan di

sebelah kanan tanda ketaksamaan atasa samaan dan nilai positf.

System kekangan diubah dan menjadi satu system persamaan dengan

peraturan-peraturan berikut:

1) Kekangan yang bertanda ≤ ditambah satu pembolehubah S

2) Kekangan bertanda ≥ ditambah dengan satu pembolehubah buatan R dan

dikurangkan dengan pembolehubah lalaian S.

3) Kekangan yang bertanda = ditambahkan dengan pembolehubah buatan R

Fungsi objektif

- Masalah peminimuman –∑ (+MR) ditambahkan pada fungsi objektif asal.

- Masalah pemaksimuman –∑ (−MR) ditambahkan pada fungsi objektif asal.


persamaan linear

Documents