ಹೋಮೋರಿ ವಿಧಾನ. ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸುವುದು

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

ಪೂರ್ಣಾಂಕ ಮೌಲ್ಯಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ ಅಸ್ಥಿರಗಳೊಂದಿಗೆ ಕಾರ್ಯಗಳನ್ನು ಬಳಸುವ ಮುಖ್ಯ ನಿರ್ದೇಶನವು ಉತ್ತಮಗೊಳಿಸುವಿಕೆಯಾಗಿದೆ. ಪೂರ್ಣಾಂಕ ರೇಖಾತ್ಮಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಬಳಸುವ ವಿಧಾನವನ್ನು ಕ್ಲಿಪ್ಪಿಂಗ್ ವಿಧಾನವೆಂದು ಕರೆಯಲಾಗುತ್ತದೆ.

ಹೋಮೋರಿ ವಿಧಾನವು 1957-1958ರಲ್ಲಿ ಮೊದಲು ಅಭಿವೃದ್ಧಿಪಡಿಸಿದ ಗಣಿತಜ್ಞರ ಹೆಸರಿನಿಂದ ತನ್ನ ಹೆಸರನ್ನು ಪಡೆದುಕೊಂಡಿದೆ, ಇದು ಪೂರ್ಣಾಂಕ ರೇಖಾತ್ಮಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಲು ಇನ್ನೂ ವ್ಯಾಪಕವಾಗಿ ಬಳಸಲ್ಪಡುತ್ತದೆ. ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಯ ಅಂಗೀಕೃತ ರೂಪವು ಈ ವಿಧಾನದ ಅನುಕೂಲಗಳನ್ನು ಸಂಪೂರ್ಣವಾಗಿ ಕಂಡುಕೊಳ್ಳಲು ಸಾಧ್ಯವಾಗುತ್ತದೆ.

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

ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸುವಲ್ಲಿ ಸಂಖ್ಯಾತ್ಮಕ ಕ್ರಮಾವಳಿಗಳನ್ನು ದೃಢೀಕರಿಸಲು, ವಿವಿಧ ಹೆಚ್ಚುವರಿ ಪರಿಸ್ಥಿತಿಗಳನ್ನು ಮೇಲ್ವಿಚಾರಣೆ ಮಾಡಲು ಅಗತ್ಯವಾಗುತ್ತದೆ.

ಗೊಮೊರಿ ವಿಧಾನವನ್ನು ಬಳಸುವುದರಿಂದ, ಸಮಸ್ಯೆ ಯೋಜನೆಗಳ ಸೆಟ್ ಅನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಪರಿಹಾರಗಳ ಪಾಲಿಟೋಪ್ ಎಂದು ಕರೆಯಲ್ಪಡುವ ಪರಿಭಾಷೆ ಎಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ. ಇದರಿಂದ ಮುಂದುವರೆಯುವುದು ಪ್ರಶ್ನೆಯಲ್ಲಿನ ಸಮಸ್ಯೆಗಳಿಗಾಗಿ ಎಲ್ಲಾ ಅವಿಭಾಜ್ಯ ಯೋಜನೆಗಳ ಸಮೂಹವು ಸೀಮಿತ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿದೆ ಎಂದು ಅನುಸರಿಸುತ್ತದೆ.

ಅಲ್ಲದೆ, ಒಂದು ಕಾರ್ಯದ ಪೂರ್ಣಾಂಕವನ್ನು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಲು, ಗುಣಾಂಕ ಮೌಲ್ಯಗಳು ಸಹ ಪೂರ್ಣಾಂಕಗಳೆಂದು ಊಹಿಸಲಾಗಿದೆ. ಇಂತಹ ಪರಿಸ್ಥಿತಿಗಳ ತೀವ್ರತೆಯ ಹೊರತಾಗಿಯೂ, ಅವುಗಳನ್ನು ಸ್ವಲ್ಪಮಟ್ಟಿಗೆ ಕಳುಹಿಸಬಹುದು.

ಹೋಮೋರಿ ವಿಧಾನವು ವಾಸ್ತವವಾಗಿ, ಪೂರ್ಣಾಂಕಗಳಲ್ಲದ ನಿರ್ಧಾರಗಳನ್ನು ಕಡಿತಗೊಳಿಸುವ ನಿರ್ಬಂಧಗಳನ್ನು ನಿರ್ಮಿಸುತ್ತದೆ. ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಪೂರ್ಣಾಂಕ-ಮೌಲ್ಯದ ಯೋಜನೆಗೆ ಯಾವುದೇ ಪರಿಹಾರವನ್ನು ಕಡಿತಗೊಳಿಸಲಾಗುವುದಿಲ್ಲ.

ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವ ಕ್ರಮಾವಳಿಗೆ ಸರಳವಾದ ವಿಧಾನದಿಂದ ಸೂಕ್ತವಾದ ರೂಪಾಂತರಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವುದು, ಪೂರ್ಣಾಂಕದ ಸ್ಥಿತಿಯನ್ನು ಗಣನೆಗೆ ತೆಗೆದುಕೊಳ್ಳದೆಯೇ. ಸೂಕ್ತವಾದ ಯೋಜನೆಯ ಎಲ್ಲಾ ಘಟಕಗಳಲ್ಲಿ ಪೂರ್ಣಾಂಕಗಳಿಗೆ ಸಂಬಂಧಿಸಿದ ಪರಿಹಾರಗಳಿವೆ, ಆಗ ನಾವು ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ನ ಗುರಿಯನ್ನು ಸಾಧಿಸಬಹುದು ಎಂದು ಊಹಿಸಬಹುದು. ಸಮಸ್ಯೆಯ undecidability ಬಹಿರಂಗ ಸಾಧ್ಯವಿದೆ, ಆದ್ದರಿಂದ ನಾವು ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗೆ ಯಾವುದೇ ಪರಿಹಾರವಿಲ್ಲ ಎಂದು ಪುರಾವೆ ಸಿಗುತ್ತದೆ.

ಅತ್ಯುತ್ತಮ ಪರಿಹಾರದ ಘಟಕಗಳಲ್ಲಿ ನಾನ್-ಇಂಟಿಜರ್ ಸಂಖ್ಯೆಗಳು ಇರುವಾಗ ಒಂದು ರೂಪಾಂತರವು ಸಾಧ್ಯ. ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಕೆಲಸದ ಎಲ್ಲ ನಿರ್ಬಂಧಗಳಿಗೆ ಒಂದು ಹೊಸ ನಿರ್ಬಂಧವನ್ನು ಸೇರಿಸಲಾಗುತ್ತದೆ. ಒಂದು ಹೊಸ ಮಿತಿಯನ್ನು ಅನೇಕ ಗುಣಲಕ್ಷಣಗಳ ಉಪಸ್ಥಿತಿಯಿಂದ ನಿರೂಪಿಸಲಾಗಿದೆ. ಎಲ್ಲಾ ಮೊದಲನೆಯದು, ಇದು ರೇಖೀಯವಾಗಿರಬೇಕು, ಇದು ಸೂಕ್ತವಾದ ಸೆಟ್ನಿಂದ ನಾನ್-ಇಂಟಿಜರ್ ಯೋಜನೆಯನ್ನು ಕತ್ತರಿಸಿರಬೇಕು. ಏಕೈಕ ಪೂರ್ಣಾಂಕ ಪರಿಹಾರವನ್ನು ಕಳೆದುಕೊಳ್ಳಬಾರದು, ಕತ್ತರಿಸಿಬಿಡಬೇಕು.

ನಿರ್ಬಂಧವನ್ನು ನಿರ್ಮಿಸುವಾಗ, ನೀವು ಅತ್ಯುತ್ತಮವಾದ ಯೋಜನೆಯ ಅಂಶವನ್ನು ಅತಿದೊಡ್ಡ ಭಾಗಶಃ ಭಾಗವಾಗಿ ಆರಿಸಬೇಕು. ಈ ನಿರ್ಬಂಧವು ಅಸ್ತಿತ್ವದಲ್ಲಿರುವ ಸಿಂಪ್ಲೆಕ್ಸ್ ಟೇಬಲ್ಗೆ ಸೇರಿಸಲ್ಪಡುತ್ತದೆ.

ಸಾಮಾನ್ಯ ಸಿಂಪ್ಲೆಕ್ಸ್ ರೂಪಾಂತರಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಪಡೆದ ಸಮಸ್ಯೆಯ ಪರಿಹಾರವನ್ನು ನಾವು ಕಂಡುಕೊಳ್ಳುತ್ತೇವೆ. ಸ್ಥಿತಿಯನ್ನು ತೃಪ್ತಿಪಡಿಸಿದರೆ, ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲಾಗುತ್ತಿದ್ದರೆ, ಪೂರ್ಣಾಂಕದ ಅತ್ಯುತ್ತಮ ಯೋಜನೆಯ ಉಪಸ್ಥಿತಿಗಾಗಿ ನಾವು ಸಮಸ್ಯೆಯ ಪರಿಹಾರವನ್ನು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಮತ್ತೆ ಫಲಿತಾಂಶವನ್ನು ನಾನ್-ಇಂಟಿಜರ್ ಪರಿಹಾರಗಳ ಉಪಸ್ಥಿತಿಯೊಂದಿಗೆ ಪಡೆದರೆ, ನಾವು ಹೆಚ್ಚುವರಿ ನಿರ್ಬಂಧವನ್ನು ಪರಿಚಯಿಸುತ್ತೇವೆ ಮತ್ತು ನಾವು ಲೆಕ್ಕಾಚಾರಗಳ ಪ್ರಕ್ರಿಯೆಯನ್ನು ಪುನರಾವರ್ತಿಸುತ್ತೇವೆ.

ಪರಿಮಿತ ಸಂಖ್ಯೆಯ ಪುನರಾವರ್ತನೆಗಳನ್ನು ನಡೆಸಿದ ನಂತರ, ನಾವು ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಮೊದಲು ಉಂಟಾದ ಸಮಸ್ಯೆಗೆ ಸೂಕ್ತವಾದ ಯೋಜನೆಯನ್ನು ಪಡೆದುಕೊಳ್ಳುತ್ತೇವೆ, ಅಥವಾ ಸಮಸ್ಯೆಯ ಬಗೆಗಿನ ಅಸಮರ್ಥತೆಯನ್ನು ಸಾಧಿಸುತ್ತೇವೆ.