ವಿದ್ಯಾರ್ಥಿಯ ಗಣಿತೀಯ ಅನುಭವ ಅಪೂರ್ಣವಾಗಿದೆ, ಅವನು ತಾನೇ ಕಂಡುಹಿಡಿದ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವ ಅವಕಾಶ ಎಂದಿಗೂ ಪಡೆಯದಿದ್ದರೆ. - ಜಿ. ಪೋಲ್ಯಾ

12.1 ಪರಿಚಯ

ಹಿಂದಿನ ತರಗತಿಗಳಲ್ಲಿ, ನಾವು ರೇಖೀಯ ಸಮೀಕರಣಗಳ ವ್ಯವಸ್ಥೆಗಳನ್ನು ಮತ್ತು ದೈನಂದಿನ ಸಮಸ್ಯೆಗಳಲ್ಲಿ ಅವುಗಳ ಅನ್ವಯಗಳನ್ನು ಚರ್ಚಿಸಿದ್ದೇವೆ. 11ನೇ ತರಗತಿಯಲ್ಲಿ, ನಾವು ರೇಖೀಯ ಅಸಮಾನತೆಗಳು ಮತ್ತು ಎರಡು ಚರಾಂಕಗಳಲ್ಲಿ ರೇಖೀಯ ಅಸಮಾನತೆಗಳ ವ್ಯವಸ್ಥೆಗಳನ್ನು ಮತ್ತು ಅವುಗಳ ಪರಿಹಾರಗಳನ್ನು ರೇಖಾಚಿತ್ರ ವಿಧಾನದಿಂದ ಅಧ್ಯಯನ ಮಾಡಿದ್ದೇವೆ. ಗಣಿತಶಾಸ್ತ್ರದಲ್ಲಿ ಅನೇಕ ಅನ್ವಯಗಳು ಅಸಮಾನತೆಗಳು/ಸಮೀಕರಣಗಳ ವ್ಯವಸ್ಥೆಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತವೆ. ಈ ಅಧ್ಯಾಯದಲ್ಲಿ, ನಾವು ರೇಖೀಯ ಅಸಮಾನತೆಗಳು/ಸಮೀಕರಣಗಳ ವ್ಯವಸ್ಥೆಗಳನ್ನು ಕೆಳಗೆ ನೀಡಲಾದ ರೀತಿಯ ಕೆಲವು ನೈಜ ಜೀವನದ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಲು ಅನ್ವಯಿಸುತ್ತೇವೆ:

ಒಂದು ಪೀಠೋಪಕರಣ ವ್ಯಾಪಾರಿ ಕೇವಲ ಎರಡು ವಸ್ತುಗಳಲ್ಲಿ-ಮೇಜುಗಳು ಮತ್ತು ಕುರ್ಚಿಗಳಲ್ಲಿ ವ್ಯವಹರಿಸುತ್ತಾನೆ. ಅವನ ಬಳಿ ಹೂಡಿಕೆ ಮಾಡಲು ರೂ. 50,000 ಇದೆ ಮತ್ತು ಗರಿಷ್ಠ 60 ತುಂಡುಗಳ ಸಂಗ್ರಹಣಾ ಸ್ಥಳವಿದೆ. ಒಂದು ಮೇಜಿನ ಬೆಲೆ ರೂ. 2500 ಮತ್ತು ಒಂದು ಕುರ್ಚಿಯ ಬೆಲೆ ರೂ. 500. ಒಂದು ಮೇಜಿನ ಮಾರಾಟದಿಂದ ಅವನು ರೂ. 250 ಲಾಭ ಮಾಡಬಹುದು ಮತ್ತು ಒಂದು

ಎಲ್. ಕ್ಯಾಂಟೊರೊವಿಚ್ ಕುರ್ಚಿಯ ಮಾರಾಟದಿಂದ ರೂ. 75 ಲಾಭ ಮಾಡಬಹುದು ಎಂದು ಅವನು ಅಂದಾಜು ಮಾಡುತ್ತಾನೆ. ಲಭ್ಯವಿರುವ ಹಣದಿಂದ ಎಷ್ಟು ಮೇಜುಗಳು ಮತ್ತು ಕುರ್ಚಿಗಳನ್ನು ಕೊಳ್ಳಬೇಕು ಎಂದು ತಿಳಿಯಲು ಅವನು ಬಯಸುತ್ತಾನೆ, ಇದರಿಂದ ಅವನ ಒಟ್ಟು ಲಾಭವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸಬಹುದು, ಅವನು ಕೊಳ್ಳುವ ಎಲ್ಲಾ ವಸ್ತುಗಳನ್ನು ಮಾರಾಟ ಮಾಡಬಹುದು ಎಂದು ಭಾವಿಸಿ. ಲಾಭವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸಲು (ಅಥವಾ, ಕನಿಷ್ಠಗೊಳಿಸಲು) ಪ್ರಯತ್ನಿಸುವ ಇಂತಹ ರೀತಿಯ ಸಮಸ್ಯೆಗಳು ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳು ಎಂಬ ಸಾಮಾನ್ಯ ವರ್ಗದ ಸಮಸ್ಯೆಗಳನ್ನು ರೂಪಿಸುತ್ತವೆ. ಹೀಗಾಗಿ, ಒಂದು ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯು ಗರಿಷ್ಠ ಲಾಭ, ಕನಿಷ್ಠ ವೆಚ್ಚ, ಅಥವಾ ಸಂಪನ್ಮೂಲಗಳ ಕನಿಷ್ಠ ಬಳಕೆ ಇತ್ಯಾದಿಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವುದನ್ನು ಒಳಗೊಂಡಿರಬಹುದು.

ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳ ಒಂದು ವಿಶೇಷ ಆದರೆ ಬಹಳ ಮುಖ್ಯವಾದ ವರ್ಗವೆಂದರೆ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆ. ಮೇಲೆ ಹೇಳಿದ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯು ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಯ ಒಂದು ಉದಾಹರಣೆಯಾಗಿದೆ. ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗಳು ಕೈಗಾರಿಕೆ, ವಾಣಿಜ್ಯ, ನಿರ್ವಹಣಾ ವಿಜ್ಞಾನ ಇತ್ಯಾದಿಗಳಲ್ಲಿ ಅವುಗಳ ವ್ಯಾಪಕ ಅನ್ವಯಿಸುವಿಕೆಯಿಂದಾಗಿ ಹೆಚ್ಚು ಆಸಕ್ತಿದಾಯಕವಾಗಿವೆ.

ಈ ಅಧ್ಯಾಯದಲ್ಲಿ, ನಾವು ಕೆಲವು ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗಳನ್ನು ಮತ್ತು ಅವುಗಳ ಪರಿಹಾರಗಳನ್ನು ಕೇವಲ ರೇಖಾಚಿತ್ರ ವಿಧಾನದಿಂದ ಅಧ್ಯಯನ ಮಾಡುತ್ತೇವೆ, ಅಂತಹ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಲು ಅನೇಕ ಇತರ ವಿಧಾನಗಳೂ ಇದ್ದರೂ ಸಹ.

12.2 ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆ ಮತ್ತು ಅದರ ಗಣಿತೀಯ ಸೂತ್ರೀಕರಣ

ನಾವು ನಮ್ಮ ಚರ್ಚೆಯನ್ನು ಮೇಲಿನ ಪೀಠೋಪಕರಣ ವ್ಯಾಪಾರಿಯ ಉದಾಹರಣೆಯೊಂದಿಗೆ ಪ್ರಾರಂಭಿಸುತ್ತೇವೆ, ಅದು ಎರಡು ಚರಾಂಕಗಳಲ್ಲಿ ಸಮಸ್ಯೆಯ ಗಣಿತೀಯ ಸೂತ್ರೀಕರಣಕ್ಕೆ ಮುಂದೆ ನಡೆಸುತ್ತದೆ. ಈ ಉದಾಹರಣೆಯಲ್ಲಿ, ನಾವು ಗಮನಿಸುತ್ತೇವೆ

(i) ವ್ಯಾಪಾರಿಯು ತನ್ನ ಹಣವನ್ನು ಮೇಜುಗಳು ಅಥವಾ ಕುರ್ಚಿಗಳು ಅಥವಾ ಅವುಗಳ ಸಂಯೋಜನೆಯನ್ನು ಕೊಳ್ಳುವಲ್ಲಿ ಹೂಡಿಕೆ ಮಾಡಬಹುದು. ಮತ್ತಷ್ಟು, ವಿಭಿನ್ನ ಹೂಡಿಕೆ ತಂತ್ರಗಳನ್ನು ಅನುಸರಿಸುವ ಮೂಲಕ ಅವನು ವಿಭಿನ್ನ ಲಾಭಗಳನ್ನು ಗಳಿಸುತ್ತಾನೆ.

(ii) ಕೆಲವು ಅತೀಮಾನ್ಯ ಪರಿಸ್ಥಿತಿಗಳು ಅಥವಾ ನಿರ್ಬಂಧಗಳಿವೆ ಅಂದರೆ, ಅವನ ಹೂಡಿಕೆಯು ಗರಿಷ್ಠ ರೂ. 50,000 ವರೆಗೆ ಮಾತ್ರ ಸೀಮಿತವಾಗಿದೆ ಮತ್ತು ಅವನ ಸಂಗ್ರಹಣಾ ಸ್ಥಳವೂ ಗರಿಷ್ಠ 60 ತುಂಡುಗಳಿಗೆ ಮಾತ್ರ ಸೀಮಿತವಾಗಿದೆ.

ಅವನು ಕೇವಲ ಮೇಜುಗಳನ್ನು ಮಾತ್ರ ಕೊಳ್ಳಲು ಮತ್ತು ಕುರ್ಚಿಗಳನ್ನು ಕೊಳ್ಳದಿರಲು ನಿರ್ಧರಿಸುತ್ತಾನೆ ಎಂದು ಭಾವಿಸೋಣ, ಆಗ ಅವನು $50000 \div 2500$, ಅಂದರೆ 20 ಮೇಜುಗಳನ್ನು ಕೊಳ್ಳಬಹುದು. ಈ ಸಂದರ್ಭದಲ್ಲಿ ಅವನ ಲಾಭವು ರೂ. $(250 \times 20)$, ಅಂದರೆ ರೂ. $\mathbf{5 0 0 0}$ ಆಗಿರುತ್ತದೆ.

ಅವನು ಕೇವಲ ಕುರ್ಚಿಗಳನ್ನು ಮಾತ್ರ ಕೊಳ್ಳಲು ಮತ್ತು ಮೇಜುಗಳನ್ನು ಕೊಳ್ಳದಿರಲು ಆಯ್ಕೆ ಮಾಡುತ್ತಾನೆ ಎಂದು ಭಾವಿಸೋಣ. ರೂ. 50,000 ರ ಬಂಡವಾಳದೊಂದಿಗೆ, ಅವನು $50000 \div 500$, ಅಂದರೆ 100 ಕುರ್ಚಿಗಳನ್ನು ಕೊಳ್ಳಬಹುದು. ಆದರೆ ಅವನು ಕೇವಲ 60 ತುಂಡುಗಳನ್ನು ಮಾತ್ರ ಸಂಗ್ರಹಿಸಬಹುದು. ಆದ್ದರಿಂದ, ಅವನು ಕೇವಲ 60 ಕುರ್ಚಿಗಳನ್ನು ಮಾತ್ರ ಕೊಳ್ಳಲು ಬಲವಂತವಾಗುತ್ತಾನೆ, ಅದು ಅವನಿಗೆ ರೂ. $(60 \times 75)$, ಅಂದರೆ ರೂ. 4500 ರ ಒಟ್ಟು ಲಾಭವನ್ನು ನೀಡುತ್ತದೆ.

ಅನೇಕ ಇತರ ಸಾಧ್ಯತೆಗಳಿವೆ, ಉದಾಹರಣೆಗೆ, ಅವನು 10 ಮೇಜುಗಳು ಮತ್ತು 50 ಕುರ್ಚಿಗಳನ್ನು ಕೊಳ್ಳಲು ಆಯ್ಕೆ ಮಾಡಬಹುದು, ಏಕೆಂದರೆ ಅವನು ಕೇವಲ 60 ತುಂಡುಗಳನ್ನು ಮಾತ್ರ ಸಂಗ್ರಹಿಸಬಹುದು. ಈ ಸಂದರ್ಭದಲ್ಲಿ ಒಟ್ಟು ಲಾಭವು ರೂ. $(10 \times 250+50 \times 75)$, ಅಂದರೆ ರೂ. $\mathbf{6 2 5 0}$ ಇತ್ಯಾದಿ ಆಗಿರುತ್ತದೆ.

ಹೀಗಾಗಿ, ವ್ಯಾಪಾರಿಯು ತನ್ನ ಹಣವನ್ನು ವಿಭಿನ್ನ ರೀತಿಯಲ್ಲಿ ಹೂಡಿಕೆ ಮಾಡಬಹುದು ಮತ್ತು ವಿಭಿನ್ನ ಹೂಡಿಕೆ ತಂತ್ರಗಳನ್ನು ಅನುಸರಿಸುವ ಮೂಲಕ ಅವನು ವಿಭಿನ್ನ ಲಾಭಗಳನ್ನು ಗಳಿಸುತ್ತಾನೆ ಎಂದು ನಾವು ಕಂಡುಕೊಳ್ಳುತ್ತೇವೆ.

ಈಗ ಸಮಸ್ಯೆಯೆಂದರೆ: ಗರಿಷ್ಠ ಲಾಭ ಪಡೆಯಲು ಅವನು ತನ್ನ ಹಣವನ್ನು ಹೇಗೆ ಹೂಡಿಕೆ ಮಾಡಬೇಕು? ಈ ಪ್ರಶ್ನೆಗೆ ಉತ್ತರಿಸಲು, ಸಮಸ್ಯೆಯನ್ನು ಗಣಿತೀಯವಾಗಿ ರೂಪಿಸಲು ಪ್ರಯತ್ನಿಸೋಣ.

12.2.1 ಸಮಸ್ಯೆಯ ಗಣಿತೀಯ ಸೂತ್ರೀಕರಣ

$x$ ಅನ್ನು ಮೇಜುಗಳ ಸಂಖ್ಯೆ ಮತ್ತು $y$ ಅನ್ನು ಕುರ್ಚಿಗಳ ಸಂಖ್ಯೆಯಾಗಿರಲಿ, ಅವುಗಳನ್ನು ವ್ಯಾಪಾರಿ ಕೊಳ್ಳುತ್ತಾನೆ. ನಿಸ್ಸಂಶಯವಾಗಿ, $x$ ಮತ್ತು $y$ ಋಣೇತರವಲ್ಲದವುಗಳಾಗಿರಬೇಕು, ಅಂದರೆ,

$$ \begin{align*} & x \geq 0 \tag{1}\\ & y \geq 0 \tag{2} \end{align*} \text { (Non-negative constraints) } $$

ವ್ಯಾಪಾರಿಯು ಅವನು ಹೂಡಿಕೆ ಮಾಡಬಹುದಾದ ಗರಿಷ್ಠ ಮೊತ್ತದಿಂದ (ಇಲ್ಲಿ ಅದು ರೂ. 50,000) ಮತ್ತು ಅವನು ಸಂಗ್ರಹಿಸಬಹುದಾದ ಗರಿಷ್ಠ ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯಿಂದ (ಇಲ್ಲಿ ಅದು 60) ನಿರ್ಬಂಧಿತನಾಗಿದ್ದಾನೆ.

ಗಣಿತೀಯವಾಗಿ ಹೇಳಲಾಗಿದೆ,

ಅಥವಾ $$ \begin{array}{rlrl} 2500 x+500 y & \leq 50,000 & \text { (investment constraint ) } \\ 5 x+y & \leq 100 & & \\ x+y & \leq 60 & & \text { (storage constraint) } \tag{4} \end{array} $$

ವ್ಯಾಪಾರಿಯು ಹೂಡಿಕೆ ಮಾಡುವ ರೀತಿಯು ಅವನ ಲಾಭವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸುವಂತಿರಬೇಕು, ಅದನ್ನು $Z$ ಎಂದು ಹೇಳೋಣ, ಇದನ್ನು $x$ ಮತ್ತು $y$ ನ ಕಾರ್ಯವಾಗಿ ನೀಡಲಾಗಿದೆ

$Z=250 x+75 y$ (ಉದ್ದೇಶ ಕಾರ್ಯ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ)

ಗಣಿತೀಯವಾಗಿ, ಕೊಟ್ಟ ಸಮಸ್ಯೆಯು ಈಗ ಇದಕ್ಕೆ ಕಡಿಮೆಯಾಗುತ್ತದೆ:

ಗರಿಷ್ಠಗೊಳಿಸಿ $Z=250 x+75 y$

ನಿರ್ಬಂಧಗಳಿಗೆ ಒಳಪಟ್ಟಂತೆ:

$$ \begin{aligned} 5 x+y & \leq 100 \\ x+y & \leq 60 \\ x \geq 0, y & \geq 0 \end{aligned} $$

ಆದ್ದರಿಂದ, ನಾವು ರೇಖೀಯ ಕಾರ್ಯ $Z$ ಅನ್ನು ಕೆಲವು ನಿರ್ಬಂಧಗಳಿಂದ ನಿರ್ಧರಿಸಲಾದ ಋಣೇತರವಲ್ಲದ ಚರಾಂಕಗಳೊಂದಿಗಿನ ರೇಖೀಯ ಅಸಮಾನತೆಗಳ ಗುಂಪಿನಿಂದ ನಿರ್ಧರಿಸಲಾದ ಕೆಲವು ಪರಿಸ್ಥಿತಿಗಳಿಗೆ ಒಳಪಟ್ಟು ಗರಿಷ್ಠಗೊಳಿಸಬೇಕು. ಕೆಲವು ಇತರ ಸಮಸ್ಯೆಗಳೂ ಇವೆ, ಅಲ್ಲಿ ನಾವು ರೇಖೀಯ ಕಾರ್ಯವನ್ನು ಕನಿಷ್ಠಗೊಳಿಸಬೇಕು, ಅದು ಋಣೇತರವಲ್ಲದ ಚರಾಂಕಗಳೊಂದಿಗಿನ ರೇಖೀಯ ಅಸಮಾನತೆಗಳ ಗುಂಪಿನಿಂದ ನಿರ್ಧರಿಸಲಾದ ಕೆಲವು ಪರಿಸ್ಥಿತಿಗಳಿಗೆ ಒಳಪಟ್ಟಿರುತ್ತದೆ. ಅಂತಹ ಸಮಸ್ಯೆಗಳನ್ನು ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗಳು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ.

ಹೀಗಾಗಿ, ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಯು ಹಲವಾರು ಚರಾಂಕಗಳ ($x$ ಮತ್ತು $y$ ಎಂದು ಹೇಳೋಣ) ರೇಖೀಯ ಕಾರ್ಯದ (ಉದ್ದೇಶ ಕಾರ್ಯ ಎಂದು ಕರೆಯಲ್ಪಡುವ) ಸೂಕ್ತ ಮೌಲ್ಯವನ್ನು (ಗರಿಷ್ಠ ಅಥವಾ ಕನಿಷ್ಠ ಮೌಲ್ಯ) ಕಂಡುಹಿಡಿಯುವುದರೊಂದಿಗೆ ಸಂಬಂಧಿಸಿದೆ, ಚರಾಂಕಗಳು ಋಣೇತರವಲ್ಲದವುಗಳು ಮತ್ತು ರೇಖೀಯ ಅಸಮಾನತೆಗಳ ಗುಂಪಿನಿಂದ (ರೇಖೀಯ ನಿರ್ಬಂಧಗಳು ಎಂದು ಕರೆಯಲ್ಪಡುವ) ತೃಪ್ತಿಪಡಿಸಲ್ಪಡುತ್ತವೆ ಎಂಬ ಪರಿಸ್ಥಿತಿಗಳಿಗೆ ಒಳಪಟ್ಟು. ರೇಖೀಯ ಎಂಬ ಪದವು ಸಮಸ್ಯೆಯಲ್ಲಿ ಬಳಸಲಾದ ಎಲ್ಲಾ ಗಣಿತೀಯ ಸಂಬಂಧಗಳು ರೇಖೀಯ ಸಂಬಂಧಗಳಾಗಿವೆ ಎಂದು ಸೂಚಿಸುತ್ತದೆ, ಆದರೆ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಎಂಬ ಪದವು ನಿರ್ದಿಷ್ಟ ಕಾರ್ಯಕ್ರಮ ಅಥವಾ ಕ್ರಮದ ಯೋಜನೆಯನ್ನು ನಿರ್ಧರಿಸುವ ವಿಧಾನವನ್ನು ಸೂಚಿಸುತ್ತದೆ.

ನಾವು ಮುಂದೆ ಹೋಗುವ ಮೊದಲು, ನಾವು ಈಗ ಕೆಲವು ಪದಗಳನ್ನು (ಮೇಲೆ ಬಳಸಲಾಗಿದೆ) ಔಪಚಾರಿಕವಾಗಿ ವ್ಯಾಖ್ಯಾನಿಸುತ್ತೇವೆ, ಅವುಗಳನ್ನು ನಾವು ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗಳಲ್ಲಿ ಬಳಸುತ್ತೇವೆ:

ಉದ್ದೇಶ ಕಾರ್ಯ ರೇಖೀಯ ಕಾರ್ಯ $Z=a x+b y$, ಇಲ್ಲಿ $a, b$ ಸ್ಥಿರಾಂಕಗಳು, ಅದನ್ನು ಗರಿಷ್ಠಗೊಳಿಸಬೇಕು ಅಥವಾ ಕನಿಷ್ಠಗೊಳಿಸಬೇಕು, ಅದನ್ನು ರೇಖೀಯ ಉದ್ದೇಶ ಕಾರ್ಯ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ.

ಮೇಲಿನ ಉದಾಹರಣೆಯಲ್ಲಿ, $Z=250 x+75 y$ ಒಂದು ರೇಖೀಯ ಉದ್ದೇಶ ಕಾರ್ಯವಾಗಿದೆ. ಚರಾಂಕಗಳು $x$ ಮತ್ತು $y$ ಅನ್ನು ನಿರ್ಧಾರ ಚರಾಂಕಗಳು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ.

ನಿರ್ಬಂಧಗಳು ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಯ ಚರಾಂಕಗಳ ಮೇಲಿನ ರೇಖೀಯ ಅಸಮಾನತೆಗಳು ಅಥವಾ ಸಮೀಕರಣಗಳು ಅಥವಾ ನಿರ್ಬಂಧಗಳನ್ನು ನಿರ್ಬಂಧಗಳು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಪರಿಸ್ಥಿತಿಗಳು ⟦37⟅ ಅನ್ನು ಋಣೇತರ ನಿರ್ಬಂಧಗಳು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಮೇಲಿನ ಉದಾಹರಣೆಯಲ್ಲಿ, ಅಸಮಾನತೆಗಳ ಗುಂಪು (1) ರಿಂದ (4) ವರೆಗೆ ನಿರ್ಬಂಧಗಳಾಗಿವೆ.

ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆ ಒಂದು ಸಮಸ್ಯೆಯು ರೇಖೀಯ ಕಾರ್ಯವನ್ನು ($x$ ಮತ್ತು $y$ ಎಂದು ಹೇಳೋಣ) ಗರಿಷ್ಠಗೊಳಿಸಲು ಅಥವಾ ಕನಿಷ್ಠಗೊಳಿಸಲು ಪ್ರಯತ್ನಿಸುತ್ತದೆ, ಅದು ರೇಖೀಯ ಅಸಮಾನತೆಗಳ ಗುಂಪಿನಿಂದ ನಿರ್ಧರಿಸಲಾದ ಕೆಲವು ನಿರ್ಬಂಧಗಳಿಗೆ ಒಳಪಟ್ಟಿರುತ್ತದೆ, ಅದನ್ನು ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗಳು ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳ ವಿಶೇಷ ಪ್ರಕಾರವಾಗಿದೆ. ಕುರ್ಚಿಗಳು ಮತ್ತು ಮೇಜುಗಳನ್ನು ಖರೀದಿಸುವಲ್ಲಿ ವ್ಯಾಪಾರಿಯಿಂದ ನಿರ್ದಿಷ್ಟ ಮೊತ್ತವನ್ನು ಹೂಡಿಕೆ ಮಾಡುವ ಮೇಲಿನ ಸಮಸ್ಯೆಯು ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯ ಉದಾಹರಣೆಯಾಗಿದೆ ಮತ್ತು ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಯೂ ಆಗಿದೆ.

ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗೆ ಪರಿಹಾರಗಳನ್ನು ಹೇಗೆ ಕಂಡುಹಿಡಿಯಬೇಕು ಎಂಬುದನ್ನು ನಾವು ಈಗ ಚರ್ಚಿಸುತ್ತೇವೆ. ಈ ಅಧ್ಯಾಯದಲ್ಲಿ, ನಾವು ಕೇವಲ ರೇಖಾಚಿತ್ರ ವಿಧಾನದೊಂದಿಗೆ ಮಾತ್ರ ಸಂಬಂಧಿಸಿರುತ್ತೇವೆ.

12.2.2 ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸುವ ರೇಖಾಚಿತ್ರ ವಿಧಾನ

11ನೇ ತರಗತಿಯಲ್ಲಿ, ನಾವು ಎರಡು ಚರಾಂಕಗಳು $x$ ಮತ್ತು $y$ ಅನ್ನು ಒಳಗೊಂಡ ರೇಖೀಯ ಅಸಮಾನತೆಗಳ ವ್ಯವಸ್ಥೆಯನ್ನು ರೇಖಾಚಿತ್ರಿಸಲು ಮತ್ತು ಅದರ ಪರಿಹಾರಗಳನ್ನು ರೇಖಾಚಿತ್ರೀಯವಾಗಿ ಕಂಡುಹಿಡಿಯಲು ಕಲಿತಿದ್ದೇವೆ. ನಾವು ಈಗ ವಿಭಾಗ 12.2 ರಲ್ಲಿ ಚರ್ಚಿಸಿದ ಮೇಜುಗಳು ಮತ್ತು ಕುರ್ಚಿಗಳಲ್ಲಿ ಹೂಡಿಕೆಯ ಸಮಸ್ಯೆಯನ್ನು ರೇಖಾಚಿತ್ರೀಯವಾಗಿ ಪರಿಹರಿಸೋಣ. ರೇಖೀಯ ಅಸಮಾನತೆಗಳಾಗಿ ಹೇಳಲಾದ ನಿರ್ಬಂಧಗಳನ್ನು ರೇಖಾಚಿತ್ರಿಸೋಣ:

$$ \begin{align*} 5 x+y & \leq 100 \tag{1} \\ x+y & \leq 60 \tag{2} \\ x & \geq 0 \tag{3} \\ y & \geq 0 \tag{4} \end{align*} $$

ಈ ವ್ಯವಸ್ಥೆಯ ರೇಖಾಚಿತ್ರವು (ನೆರಳು ಪ್ರದೇಶ) ಅಸಮಾನತೆಗಳು (1) ರಿಂದ (4) ರಿಂದ ನಿರ್ಧರಿಸಲಾದ ಎಲ್ಲಾ ಅರ್ಧ ಸಮತಲಗಳಿಗೆ ಸಾಮಾನ್ಯವಾದ ಬಿಂದುಗಳನ್ನು ಒಳಗೊಂಡಿದೆ (ಚಿತ್ರ 12.1). ಈ ಪ್ರದೇಶದಲ್ಲಿನ ಪ್ರತಿ ಬಿಂದುವು ಮೇಜುಗಳು ಮತ್ತು ಕುರ್ಚಿಗಳಲ್ಲಿ ಹೂಡಿಕೆ ಮಾಡಲು ವ್ಯಾಪಾರಿಗೆ ತೆರೆದಿರುವ ಸಾಧ್ಯವಾದ ಆಯ್ಕೆಯನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ. ಆದ್ದರಿಂದ, ಈ ಪ್ರದೇಶವನ್ನು ಸಮಸ್ಯೆಗೆ ಸಾಧ್ಯ ಪ್ರದೇಶ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಈ ಪ್ರದೇಶದ ಪ್ರತಿ ಬಿಂದುವನ್ನು ಸಮಸ್ಯೆಗೆ ಸಾಧ್ಯ ಪರಿಹಾರ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಹೀಗಾಗಿ, ನಾವು ಹೊಂದಿದ್ದೇವೆ,

ಚಿತ್ರ 12.1

ಸಾಧ್ಯ ಪ್ರದೇಶ ಎಲ್ಲಾ ನಿರ್ಬಂಧಗಳು ಮತ್ತು ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಯ ಋಣೇತರ ನಿರ್ಬಂಧಗಳು $x, y \geq 0$ ಅನ್ನು ಒಳಗೊಂಡು ನಿರ್ಧರಿಸಲಾದ ಸಾಮಾನ್ಯ ಪ್ರದೇಶವನ್ನು ಸಮಸ್ಯೆಗೆ ಸಾಧ್ಯ ಪ್ರದೇಶ (ಅಥವಾ ಪರಿಹಾರ ಪ್ರದೇಶ) ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಚಿತ್ರ 12.1 ರಲ್ಲಿ, ಪ್ರದೇಶ OABC (ನೆರಳು) ಸಮಸ್ಯೆಗೆ ಸಾಧ್ಯ ಪ್ರದೇಶವಾಗಿದೆ. ಸಾಧ್ಯ ಪ್ರದೇಶವನ್ನು ಹೊರತುಪಡಿಸಿದ ಪ್ರದೇಶವನ್ನು ಅಸಾಧ್ಯ ಪ್ರದೇಶ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ.

ಸಾಧ್ಯ ಪರಿಹಾರಗಳು ಸಾಧ್ಯ ಪ್ರದೇಶದ ಒಳಗೆ ಮತ್ತು ಗಡಿಯ ಮೇಲಿನ ಬಿಂದುಗಳು ನಿರ್ಬಂಧಗಳ ಸಾಧ್ಯ ಪರಿಹಾರಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತವೆ. ಚಿತ್ರ 12.1 ರಲ್ಲಿ, ಸಾಧ್ಯ ಪ್ರದೇಶದ ಒಳಗೆ ಮತ್ತು ಗಡಿಯ ಮೇಲಿನ ಪ್ರತಿ ಬಿಂದು $OABC$ ಸಮಸ್ಯೆಗೆ ಸಾಧ್ಯ ಪರಿಹಾರವನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ಬಿಂದು $(10,50)$ ಸಮಸ್ಯೆಯ ಸಾಧ್ಯ ಪರಿಹಾರವಾಗಿದೆ ಮತ್ತು ಬಿಂದುಗಳು $(0,60),(20,0)$ ಇತ್ಯಾದಿಗಳೂ ಸಹ ಆಗಿವೆ.

ಸಾಧ್ಯ ಪ್ರದೇಶದ ಹೊರಗಿನ ಯಾವುದೇ ಬಿಂದುವನ್ನು ಅಸಾಧ್ಯ ಪರಿಹಾರ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ಬಿಂದು $(25,40)$ ಸಮಸ್ಯೆಯ ಅಸಾಧ್ಯ ಪರಿಹಾರವಾಗಿದೆ.

ಸೂಕ್ತ (ಸಾಧ್ಯ) ಪರಿಹಾರ: ಸಾಧ್ಯ ಪ್ರದೇಶದಲ್ಲಿನ ಯಾವುದೇ ಬಿಂದುವು ಉದ್ದೇಶ ಕಾರ್ಯದ ಸೂಕ್ತ ಮೌಲ್ಯವನ್ನು (ಗರಿಷ್ಠ ಅಥವಾ ಕನಿಷ್ಠ) ನೀಡಿದರೆ, ಅದನ್ನು ಸೂಕ್ತ ಪರಿಹಾರ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ.

ಈಗ, ನಾವು ನೋಡುತ್ತೇವೆ, ಸಾಧ್ಯ ಪ್ರದೇಶದಲ್ಲಿನ ಪ್ರತಿ ಬಿಂದು $OABC$ (1) ರಿಂದ (4) ರಲ್ಲಿ ನೀಡಲಾದ ಎಲ್ಲಾ ನಿರ್ಬಂಧಗಳನ್ನು ತೃಪ್ತಿಪಡಿಸುತ್ತದೆ, ಮತ್ತು ಅನಂತವಾಗಿ ಅನೇಕ ಬಿಂದುಗಳಿರುವುದರಿಂದ, ಉದ್ದೇಶ ಕಾರ್ಯ $Z=250 x+75 y$ ನ ಗರಿಷ್ಠ ಮೌಲ್ಯವನ್ನು ನೀಡುವ ಬಿಂದುವನ್ನು ಹೇಗೆ ಕಂಡುಹಿಡಿಯಬೇಕು ಎಂಬುದು ಸ್ಪಷ್ಟವಾಗಿಲ್ಲ. ಈ ಪರಿಸ್ಥಿತಿಯನ್ನು ನಿಭಾಯಿಸಲು, ನಾವು ಕೆಳಗಿನ ಪ್ರಮೇಯಗಳನ್ನು ಬಳಸುತ್ತೇವೆ, ಅವು ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸುವಲ್ಲಿ ಮೂಲಭೂತವಾಗಿವೆ. ಈ ಪ್ರಮೇಯಗಳ ಪುರಾವೆಗಳು ಪುಸ್ತಕದ ವ್ಯಾಪ್ತಿಯನ್ನು ಮೀರಿದೆ.

ಪ್ರಮೇಯ 1 $R$ ಅನ್ನು ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗೆ ಸಾಧ್ಯ ಪ್ರದೇಶ (ಕುತ್ಪ ಅಥವಾ ಕಾನ್ವೆಕ್ಸ್ ಬಹುಭುಜಾಕೃತಿ) ಆಗಿರಲಿ ಮತ್ತು $Z=a x+b y$ ಅನ್ನು ಉದ್ದೇಶ ಕಾರ್ಯವಾಗಿರಲಿ. ಯಾವಾಗ $Z$ ಒಂದು ಸೂಕ್ತ ಮೌಲ್ಯವನ್ನು (ಗರಿಷ್ಠ ಅಥವಾ ಕನಿಷ್ಠ) ಹೊಂದಿರುತ್ತದೆ, ಅಲ್ಲಿ ಚರಾಂಕಗಳು $x$ ಮತ್ತು $y$ ರೇಖೀಯ ಅಸಮಾನತೆಗಳಿಂದ ವರ್ಣಿಸಲ್ಪಟ್ಟ ನಿರ್ಬಂಧಗಳಿಗೆ ಒಳಪಟ್ಟಿರುತ್ತವೆ, ಈ ಸೂಕ್ತ ಮೌಲ್ಯವು ಸಾಧ್ಯ ಪ್ರದೇಶದ ಮೂಲೆಯ ಬಿಂದುವಿನಲ್ಲಿ* (ಶೃಂಗ) ಸಂಭವಿಸಬೇಕು.

ಪ್ರಮೇಯ 2 $R$ ಅನ್ನು ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗೆ ಸಾಧ್ಯ ಪ್ರದೇಶವಾಗಿರಲಿ, ಮತ್ತು $Z=a x+b y$ ಅನ್ನು ಉದ್ದೇಶ ಕಾರ್ಯವಾಗಿರಲಿ. $R$ ಸೀಮಿತವಾಗಿದ್ದರೆ**, ಆಗ ಉದ್ದೇಶ ಕಾರ್ಯ $Z$ ಅನ್ನು $R$ ಮೇಲೆ ಗರಿಷ್ಠ ಮತ್ತು ಕನಿಷ್ಠ ಮೌಲ್ಯಗಳೆರಡನ್ನೂ ಹೊಂದಿರುತ್ತದೆ ಮತ್ತು ಇವುಗಳಲ್ಲಿ ಪ್ರತಿಯೊಂದೂ R ನ ಮೂಲೆಯ ಬಿಂದುವಿನಲ್ಲಿ (ಶೃಂಗ) ಸಂಭವಿಸುತ್ತದೆ.

ಟಿಪ್ಪಣಿ $R$ ಅಸೀಮಿತವಾಗಿದ್ದರೆ, ಆಗ ಉದ್ದೇಶ ಕಾರ್ಯದ ಗರಿಷ್ಠ ಅಥವಾ ಕನಿಷ್ಠ ಮೌಲ್ಯವು ಅಸ್ತಿತ್ವದಲ್ಲಿಲ್ಲದಿರಬಹುದು. ಆದಾಗ್ಯೂ, ಅದು ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದರೆ, ಅದು R ನ ಮೂಲೆಯ ಬಿಂದುವಿನಲ್ಲಿ ಸಂಭವಿಸಬೇಕು. (ಪ್ರಮೇಯ 1 ರ ಪ್ರಕಾರ).

ಮೇಲಿನ ಉದಾಹರಣೆಯಲ್ಲಿ, ಸೀಮಿತ (ಸಾಧ್ಯ) ಪ್ರದೇಶದ ಮೂಲೆಯ ಬಿಂದುಗಳು (ಶೃಂಗಗಳು): $O, A, B$ ಮತ್ತು $C$ ಮತ್ತು ಅವುಗಳ ನಿರ್ದೇಶಾಂಕಗಳನ್ನು ಕ್ರಮವಾಗಿ $(0,0),(20,0),(10,50)$ ಮತ್ತು $(0,60)$ ಎಂದು ಕಂಡುಹಿಡಿಯುವುದು ಸುಲಭ. ಈಗ ಈ ಬಿಂದುಗಳಲ್ಲಿ $Z$ ನ ಮೌಲ್ಯಗಳನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡೋಣ.

ನಾವು ಹೊಂದಿದ್ದೇವೆ

• ಸಾಧ್ಯ ಪ್ರದೇಶದ ಮೂಲೆಯ ಬಿಂದುವು ಪ್ರದೇಶದಲ್ಲಿನ ಒಂದು ಬಿಂದುವಾಗಿದೆ, ಅದು ಎರಡು ಗಡಿ ರೇಖೆಗಳ ಛೇದನವಾಗಿದೆ.

• ರೇಖೀಯ ಅಸಮಾನತೆಗಳ ವ್ಯವಸ್ಥೆಯ ಸಾಧ್ಯ ಪ್ರದೇಶವು ಸೀಮಿತವಾಗಿದೆ ಎಂದು ಹೇಳಲಾಗುತ್ತದೆ, ಅದನ್ನು ವೃತ್ತದೊಳಗೆ ಸುತ್ತುವರಿಯಬಹುದಾದರೆ. ಇಲ್ಲದಿದ್ದರೆ, ಅದನ್ನು ಅಸೀಮಿತ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಅಸೀಮಿತ ಎಂದರೆ ಸಾಧ್ಯ ಪ್ರದೇಶವು ಯಾವುದೇ ದಿಕ್ಕಿನಲ್ಲಿ ಅನಿರ್ದಿಷ್ಟವಾಗಿ ವಿಸ್ತರಿಸುತ್ತದೆ.

ವ್ಯಾಪಾರಿಗೆ ಗರಿಷ್ಠ ಲಾಭವು ಹೂಡಿಕೆ ತಂತ್ರ $(10,50)$, ಅಂದರೆ 10 ಮೇಜುಗಳು ಮತ್ತು 50 ಕುರ್ಚಿಗಳನ್ನು ಕೊಳ್ಳುವುದರಿಂದ ಉಂಟಾಗುತ್ತದೆ ಎಂದು ನಾವು ಗಮನಿಸುತ್ತೇವೆ.

ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವ ಈ ವಿಧಾನವನ್ನು ಮೂಲೆಯ ಬಿಂದು ವಿಧಾನ ಎಂದು ಸೂಚಿಸಲಾಗುತ್ತದೆ. ಈ ವಿಧಾನವು ಕೆಳಗಿನ ಹಂತಗಳನ್ನು ಒಳಗೊಂಡಿದೆ:

1. ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಯ ಸಾಧ್ಯ ಪ್ರದೇಶವನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ ಮತ್ತು ಅದರ ಮೂಲೆಯ ಬಿಂದುಗಳನ್ನು (ಶೃಂಗಗಳನ್ನು) ಪರೀಕ್ಷೆಯ ಮೂಲಕ ಅಥವಾ ಆ ಬಿಂದುವಿನಲ್ಲಿ ಛೇದಿಸುವ ಎರಡು ರೇಖೆಗಳ ಸಮೀಕರಣಗಳನ್ನು ಪರಿಹರಿಸುವ ಮೂಲಕ ನಿರ್ಧರಿಸಿ.

2. ಪ್ರತಿ ಮೂಲೆಯ ಬಿಂದುವಿನಲ್ಲಿ ಉದ್ದೇಶ ಕಾರ್ಯ $Z=a x+b y$ ಅನ್ನು ಮೌಲ್ಯಮಾಪನ ಮಾಡಿ. $\mathbf{M}$ ಮತ್ತು $m$ ಅನ್ನು ಕ್ರಮವಾಗಿ ಈ ಬಿಂದುಗಳ ದೊಡ್ಡ ಮತ್ತು ಚಿಕ್ಕ ಮೌಲ್ಯಗಳನ್ನು ಸೂಚಿಸಲಿ.

3. (i) ಸಾಧ್ಯ ಪ್ರದೇಶವು ಸೀಮಿತವಾಗಿದ್ದಾಗ, $M$ ಮತ್ತು $m$ $Z$ ನ ಗರಿಷ್ಠ ಮತ್ತು ಕನಿಷ್ಠ ಮೌಲ್ಯಗಳಾಗಿವೆ.

(ii) ಸಂದರ್ಭದಲ್ಲಿ, ಸಾಧ್ಯ ಪ್ರದೇಶವು ಅಸೀಮಿತವಾಗಿದ್ದರೆ, ನಾವು ಹೊಂದಿದ್ದೇವೆ:

4. (a) $M$ $Z$ ನ ಗರಿಷ್ಠ ಮೌಲ್ಯವಾಗಿದೆ, $a x+b y>M$ ನಿಂದ ನಿರ್ಧರಿಸಲಾದ ತೆರೆದ ಅರ್ಧ ಸಮತಲವು ಸಾಧ್ಯ ಪ್ರದೇಶದೊಂದಿಗೆ ಯಾವುದೇ ಬಿಂದುವನ್ನು ಹೊಂದಿರದಿದ್ದರೆ. ಇಲ್ಲದಿದ್ದರೆ, $Z$ ಗೆ ಗರಿಷ್ಠ ಮೌಲ್ಯವಿಲ್ಲ.

(b) ಅಂತೆಯೇ, $m$ $Z$ ನ ಕನಿಷ್ಠ ಮೌಲ್ಯವಾಗಿದ