Осжақты есепті құрудың алгоритмі.

қ осжақ ты есепті қ ұ рудың алгоритмі

1. Бастапқ ы есептің шектеулер жү йесінің барлық тең сіздіктерін бір мағ ынағ а келтіру керек: егер бастапқ ы есепте сызық тық функцияның максимумы ізделінсе, онда шектеулер жү йесінің барлық тең сіздіктерін “ ” тү ріне, ал егер минимумы ізделінсе “ ” тү ріне келтіру керек. Егер осы айтылғ ан талап орындалмайтындай тең сіздік кездессе, онда оны (-1)-ге кө бейту керек.

2. Жү йенің кең ейтілген матрицасын қ ұ рамыз. Бұ л матрицағ а матрицасындағ ы айнымалылардың коэффициенттері, шектеулер жү йесінің бос мү шелер бағ аны жә не сызық тық функциядағ ы айнымалылардың коэффициенттерінен тұ ратын жол енгізіледі.

3. матрицасына транспонирленген матрицасын табу керек.

4. Алынғ ан матрицасының жә не айнымалылардың теріс еместік шартының негізінде қ осжақ ты есепті қ ұ рамыз.

3.1-мысал.

,

шектеулеріндегі

сызық тық программалау есебіне қ осжақ ты есеп қ ұ ру керек.

Шығ арылуы.

1. Бастапқ ы есеп максимум табуғ а арналғ ан. Сондық тан шектеулер жү йесіндегі тең сіздіктер “ ” тү рінде болуы керек. Берілген есепте бірінші тең сіздіктің таң басы “ ”, оны “ ” тү ріне келтіру ү шін (-1)-ге кө бейтеміз.

2. Жү йенің кең ейтілген матрицасын қ ұ рамыз:

(соң ғ ы жол – мақ сат функциясының айнымалыларының коэффициенттері, соң ғ ы бағ ан – бос мү шелер бағ аны).

3. матрицасына транспонирленген матрицасын жазамыз:

(соң ғ ы жол – бос мү шелер, соң ғ ы бағ ан – мақ сат функциясының айнымалыларының коэффициенттер бағ аны).

4. матрицасының негізінде қ осжақ ты есепті қ ұ рамыз:

,

шектеулеріндегі

.

Жауабы.

,

шектеулеріндегі

.