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

сызық тық тең деулер мен тең сіздіктерден тұ ратын, айнымалысы бар

(1.7)

жү йе жә не

(1.8)

функциясы берілсін.

(1.7) жү йеде алдымен тең сіздік, содан кейін тең дік берілген. Егер осы тең сіздіктер мен тең діктер бастапқ ы берілуінде басқ аша орналасса, орындарын ауыстыру нә тижесінде айтылғ ан тү рге келтіруге болады. Жү йенің сол жағ ы оң жағ ынан кіші не тең болсын дейміз, егер қ андай да бір тең сіздікте керісінше болса, онда сол тең сіздікті «-1»-ге кө бейту арқ ылы қ ажетті таң бамызды аламыз.

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

(1.8) сызық тық функция тиімді (яғ ни, максималды немесе минималды) мә нді қ абылдайтындай жә не

, (1.9)

шартын қ анағ аттандыратындай (1.7) жү йенің шешімін табу қ ажет.

(1.7) жү йе шектеулер жү йесі деп, (1.8) - функциясы сызық тық функция немесе мақ сат функциясы деп, ал (1.9) шарт теріс еместік шарты деп аталады.

Экстремумды іздеу типін таң дау салыстырмалы сипатта болады. Себебі, функциясының максимумын іздеу функциясының минимумын іздеумен пара-пар.

(1.9) шартты қ анағ аттандыратын, (1.8) сызық тық функция тиімді мә нді (максималды немесе минималды) қ абылдайтындай (1.7) шектеулер жү йесінің шешімі тиімді шешім (немесе тиімді жоспар) деп аталады.

Егер айнымалысы бар сызық тық тең деулер жү йесінің айнымалыларының коэффициенттерінен қ ұ рылғ ан матрицаның анық тауышы нө лден ө зге болса, онда кез келген айнымалысы негізгі (немесе базистік) деп аталады. Қ алғ ан айнымалы негізгі емес (немесе бос) айнымалы деп аталады.

Егер сызық тық программалау есебінің барлық айнымалылары теріс еместік шартты қ анағ аттандырса жә не (1.7) шектеулер жү йесі:

а) тек қ ана тең сіздіктерден тұ рса, онда сызық тық программалау есебі стандартты немесе симметриялы;

ә)тек қ ана тең діктерден тұ рса, онда сызық тық программалау есебі канондық немесе негізгі;

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

Кез келген сызық тық программалау есебін канондық тү рге келтіруге болады. Айталық, сызық тық программалау есебі стандартты тү рде берілсін:

Стандартты программалау есебін канондық тү рге келтіру ү шін шектеулер жү йесіне теріс емес (тең сіздіктің саны қ анша болса, қ осымша айнымалылар саны да сонша) қ осымша айнымалыларын енгіземіз.

Қ арастырылып отырғ ан есепте барлық тең сіздіктердің таң басы «» болғ андық тан, қ осымша айнымалылар «+» таң басымен енгізіледі, ал егер тең сіздіктердің таң басы «» болса, онда қ осымша айнымалылар «-» таң басымен енгізіледі.