Program matematika (Bahasa Indonesia)
Mathematics program (English)
Sumber asli / Authoritative original
Lewati ke konten utama
Daftar Isi Indeks
Cari di Buku
Hasil Pencarian:
Tidak ada hasil.
Bacakan Pengaturan Keterbacaan Sblm Naik Lnjt \(\newcommand{\set}[1]{\{#1\}}
\newcommand{\ints}{\mathbb{Z}}
\newcommand{\posints}{\mathbb{N}}
\newcommand{\rats}{\mathbb{Q}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\complexes}{\mathbb{C}}
\newcommand{\twospace}{\mathbb{R}^2}
\newcommand{\threepace}{\mathbb{R}^3}
\newcommand{\dspace}{\mathbb{R}^d}
\newcommand{\nni}{\mathbb{N}_0}
\newcommand{\nonnegints}{\mathbb{N}_0}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\prob}{\operatorname{prob}}
\newcommand{\Prob}{\operatorname{Prob}}
\newcommand{\height}{\operatorname{height}}
\newcommand{\width}{\operatorname{width}}
\newcommand{\length}{\operatorname{length}}
\newcommand{\crit}{\operatorname{crit}}
\newcommand{\inc}{\operatorname{inc}}
\newcommand{\HP}{\mathbf{H_P}}
\newcommand{\HCP}{\mathbf{H^c_P}}
\newcommand{\GP}{\mathbf{G_P}}
\newcommand{\GQ}{\mathbf{G_Q}}
\newcommand{\AG}{\mathbf{A_G}}
\newcommand{\GCP}{\mathbf{G^c_P}}
\newcommand{\PXP}{\mathbf{P}=(X,P)}
\newcommand{\QYQ}{\mathbf{Q}=(Y,Q)}
\newcommand{\GVE}{\mathbf{G}=(V,E)}
\newcommand{\HWF}{\mathbf{H}=(W,F)}
\newcommand{\bfC}{\mathbf{C}}
\newcommand{\bfG}{\mathbf{G}}
\newcommand{\bfH}{\mathbf{H}}
\newcommand{\bfF}{\mathbf{F}}
\newcommand{\bfI}{\mathbf{I}}
\newcommand{\bfK}{\mathbf{K}}
\newcommand{\bfP}{\mathbf{P}}
\newcommand{\bfQ}{\mathbf{Q}}
\newcommand{\bfR}{\mathbf{R}}
\newcommand{\bfS}{\mathbf{S}}
\newcommand{\bfT}{\mathbf{T}}
\newcommand{\bfNP}{\mathbf{NP}}
\newcommand{\bftwo}{\mathbf{2}}
\newcommand{\cgA}{\mathcal{A}}
\newcommand{\cgB}{\mathcal{B}}
\newcommand{\cgC}{\mathcal{C}}
\newcommand{\cgD}{\mathcal{D}}
\newcommand{\cgE}{\mathcal{E}}
\newcommand{\cgF}{\mathcal{F}}
\newcommand{\cgG}{\mathcal{G}}
\newcommand{\cgM}{\mathcal{M}}
\newcommand{\cgN}{\mathcal{N}}
\newcommand{\cgP}{\mathcal{P}}
\newcommand{\cgR}{\mathcal{R}}
\newcommand{\cgS}{\mathcal{S}}
\newcommand{\bfn}{\mathbf{n}}
\newcommand{\bfm}{\mathbf{m}}
\newcommand{\bfk}{\mathbf{k}}
\newcommand{\bfs}{\mathbf{s}}
\newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}}
\newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}}
\newcommand{\surjection}{\xrightarrow[\text{onto}]{}}
\newcommand{\nin}{\not\in}
\newcommand{\prufer}{\text{prüfer}}
\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\stab}{stab}
\DeclareMathOperator{\var}{var}
\newcommand{\inv}{^{-1}}
\newcommand{\ds}{\displaystyle}
\newcommand{\mbf}[1]{\mathbf{#1}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Subbab 13.6 Solusi Bilangan Bulat untuk Masalah Pemrograman Linear
Masalah pemrograman linear adalah masalah optimisasi yang dapat dinyatakan dalam bentuk berikut: tentukan nilai maksimum dari fungsi linear
\begin{equation*}
c_1x_1+c_2x_2+c_3x_3+\dots+c_n x_n
\end{equation*}
dengan tunduk pada \(m\) kendala \(C_1\text{,}\) \(C_2,\dots,C_m\text{,}\) dengan setiap kendala \(C_i\) berupa persamaan linear berbentuk
\begin{equation*}
C_i:\quad a_{i1}x_1+a_{i2}x_2+a_{i3}x_3+\dots+a_{in}x_n=b_i
\end{equation*}
dengan semua koefisien dan konstanta berupa bilangan real.
Walaupun pokok bahasan umum pemrograman linear terlalu luas untuk mata kuliah ini, penting bagi kita untuk mencatat hal-hal berikut:
Masalah pemrograman linear merupakan kelas masalah optimisasi yang
sangat penting dan mempunyai banyak penerapan dalam bidang teknik, sains, dan industri.
Terdapat algoritma yang relatif efisien untuk menemukan solusi masalah pemrograman linear.
Masalah pemrograman linear dengan koefisien dan konstanta rasional mempunyai solusi optimal bernilai rasional—jika masalah tersebut memang mempunyai solusi optimal.
Masalah pemrograman linear dengan koefisien dan konstanta bilangan bulat tidak harus mempunyai solusi optimal bernilai bilangan bulat—meskipun mempunyai solusi optimal bernilai rasional.
Salah satu tema yang sangat penting dalam riset operasi ialah menentukan kapan masalah pemrograman linear yang dirumuskan dengan bilangan bulat mempunyai solusi optimal bernilai bilangan bulat. Persoalan ini halus dan sering kali sangat sulit.
Masalah menemukan aliran maksimum dalam suatu jaringan merupakan kasus khusus dari masalah pemrograman linear.
Masalah aliran jaringan yang semua kapasitasnya berupa bilangan bulat mempunyai aliran maksimum dengan aliran bernilai bilangan bulat pada setiap sisi. Algoritma pelabelan Ford–Fulkerson menjamin hal ini!
Secara umum, algoritma pemrograman linear tidak digunakan pada jaringan. Sebagai gantinya, algoritma khusus seperti Ford–Fulkerson terbukti lebih efisien dalam praktik.
