ਵਿਦਿਆਰਥੀ ਦਾ ਗਣਿਤਿਕ ਅਨੁਭਵ ਅਧੂਰਾ ਹੈ ਜੇਕਰ ਉਸਨੂੰ ਕਦੇ ਵੀ ਆਪਣੇ ਦੁਆਰਾ ਘੜੀ ਗਈ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਦਾ ਮੌਕਾ ਨਾ ਮਿਲਿਆ ਹੋਵੇ। - ਜੀ. ਪੋਲਿਆ

12.1 ਜਾਣ-ਪਛਾਣ

ਪਿਛਲੀਆਂ ਕਲਾਸਾਂ ਵਿੱਚ, ਅਸੀਂ ਰੇਖਿਕ ਸਮੀਕਰਣਾਂ ਦੀਆਂ ਪ੍ਰਣਾਲੀਆਂ ਅਤੇ ਰੋਜ਼ਾਨਾ ਸਮੱਸਿਆਵਾਂ ਵਿੱਚ ਉਨ੍ਹਾਂ ਦੇ ਉਪਯੋਗਾਂ ਬਾਰੇ ਚਰਚਾ ਕੀਤੀ ਹੈ। ਕਲਾਸ XI ਵਿੱਚ, ਅਸੀਂ ਦੋ ਚਲਾਂ ਵਿੱਚ ਰੇਖਿਕ ਅਸਮਾਨਤਾਵਾਂ ਅਤੇ ਰੇਖਿਕ ਅਸਮਾਨਤਾਵਾਂ ਦੀਆਂ ਪ੍ਰਣਾਲੀਆਂ ਅਤੇ ਗ੍ਰਾਫਿਕਲ ਵਿਧੀ ਦੁਆਰਾ ਉਨ੍ਹਾਂ ਦੇ ਹੱਲਾਂ ਦਾ ਅਧਿਐਨ ਕੀਤਾ ਹੈ। ਗਣਿਤ ਵਿੱਚ ਬਹੁਤ ਸਾਰੇ ਉਪਯੋਗ ਅਸਮਾਨਤਾਵਾਂ/ਸਮੀਕਰਣਾਂ ਦੀਆਂ ਪ੍ਰਣਾਲੀਆਂ ਨੂੰ ਸ਼ਾਮਲ ਕਰਦੇ ਹਨ। ਇਸ ਅਧਿਆਏ ਵਿੱਚ, ਅਸੀਂ ਹੇਠਾਂ ਦਿੱਤੇ ਗਏ ਕਿਸਮ ਦੀਆਂ ਕੁਝ ਅਸਲ ਜੀਵਨ ਸਮੱਸਿਆਵਾਂ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ ਰੇਖਿਕ ਅਸਮਾਨਤਾਵਾਂ/ਸਮੀਕਰਣਾਂ ਦੀਆਂ ਪ੍ਰਣਾਲੀਆਂ ਲਾਗੂ ਕਰਾਂਗੇ:

ਇੱਕ ਫਰਨੀਚਰ ਵਪਾਰੀ ਸਿਰਫ ਦੋ ਚੀਜ਼ਾਂ-ਮੇਜ਼ ਅਤੇ ਕੁਰਸੀਆਂ ਵਿੱਚ ਕਾਰੋਬਾਰ ਕਰਦਾ ਹੈ। ਉਸ ਕੋਲ ਨਿਵੇਸ਼ ਲਈ 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$ ਨੂੰ ਫੈਸਲਾ ਚਲ ਕਿਹਾ ਜਾਂਦਾ ਹੈ।

ਪ੍ਰਤਿਬੰਧ ਰੇਖਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ ਸਮੱਸਿਆ ਦੇ ਚਲਾਂ ‘ਤੇ ਰੇਖਿਕ ਅਸਮਾਨਤਾਵਾਂ ਜਾਂ ਸਮੀਕਰਣ ਜਾਂ ਪਾਬੰਦੀਆਂ ਨੂੰ ਪ੍ਰਤਿਬੰਧ ਕਿਹਾ ਜਾਂਦਾ ਹੈ। ਸ਼ਰਤਾਂ $x \geq 0, y \geq 0$ ਨੂੰ ਗੈਰ-ਨਕਾਰਾਤਮਕ ਪਾਬੰਦੀਆਂ ਕਿਹਾ ਜਾਂਦਾ ਹੈ। ਉੱਪਰ ਦਿੱਤੇ ਉਦਾਹਰਣ ਵਿੱਚ, ਅਸਮਾਨਤਾਵਾਂ (1) ਤੋਂ (4) ਦਾ ਸਮੂਹ ਪ੍ਰਤਿਬੰਧ ਹੈ।

ਆਪਟੀਮਾਈਜ਼ੇਸ਼ਨ ਸਮੱਸਿਆ ਇੱਕ ਸਮੱਸਿਆ ਜੋ ਇੱਕ ਰੇਖਿਕ ਫੰਕਸ਼ਨ (ਮੰਨ ਲਓ ਦੋ ਚਲਾਂ $x$ ਅਤੇ $y$ ਦਾ) ਨੂੰ ਵੱਧ ਤੋਂ ਵੱਧ ਜਾਂ ਘੱਟ ਤੋਂ ਘੱਟ ਕਰਨਾ ਚਾਹੁੰਦੀ ਹੈ, ਜੋ ਕਿ ਰੇਖਿਕ ਅਸਮਾਨਤਾਵਾਂ ਦੇ ਸਮੂਹ ਦੁਆਰਾ ਨਿਰਧਾਰਤ ਕੁਝ ਪ੍ਰਤਿਬੰਧਾਂ ਦੇ ਅਧੀਨ ਹੈ, ਨੂੰ ਆਪਟੀਮਾਈਜ਼ੇਸ਼ਨ ਸਮੱਸਿਆ ਕਿਹਾ ਜਾਂਦਾ ਹੈ। ਰੇਖਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ ਸਮੱਸਿਆਵਾਂ ਆਪਟੀਮਾਈਜ਼ੇਸ਼ਨ ਸਮੱਸਿਆਵਾਂ ਦੀ ਖਾਸ ਕਿਸਮ ਹਨ। ਕੁਰਸੀਆਂ ਅਤੇ ਮੇਜ਼ਾਂ ਖਰੀਦਣ ਵਿੱਚ ਵਪਾਰੀ ਦੁਆਰਾ ਇੱਕ ਦਿੱਤੀ ਗਈ ਰਕਮ ਨਿਵੇਸ਼ ਕਰਨ ਦੀ ਉੱਪਰ ਦਿੱਤੀ ਸਮੱਸਿਆ ਇੱਕ ਆਪਟੀਮਾਈਜ਼ੇਸ਼ਨ ਸਮੱਸਿਆ ਦੇ ਨਾਲ-ਨਾਲ ਇੱਕ ਰੇਖਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ ਸਮੱਸਿਆ ਦਾ ਉਦਾਹਰਨ ਹੈ।

ਅਸੀਂ ਹੁਣ ਚਰਚਾ ਕਰਾਂਗੇ ਕਿ ਰੇਖਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ ਸਮੱਸਿਆ ਦੇ ਹੱਲ ਕਿਵੇਂ ਲੱਭੇ ਜਾਣ। ਇਸ ਅਧਿਆਏ ਵਿੱਚ, ਅਸੀਂ ਸਿਰਫ ਗ੍ਰਾਫਿਕਲ ਵਿਧੀ ਨਾਲ ਸੰਬੰਧਿਤ ਰਹਾਂਗੇ।

12.2.2 ਰੇਖਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ ਸਮੱਸਿਆਵਾਂ ਨੂੰ ਹੱਲ ਕਰਨ ਦੀ ਗ੍ਰਾਫਿਕਲ ਵਿਧੀ

ਕਲਾਸ XI ਵਿੱਚ, ਅਸੀਂ ਸਿੱਖਿਆ ਹੈ ਕਿ ਦੋ ਚਲਾਂ $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$ ‘ਤੇ ਵੱਧ ਤੋਂ ਵੱਧ ਅਤੇ ਘ