I тарау. Сызықтық программалау есептері

F=f(x)- функциясы V көпмүшелігінде анықталған, ал W - V көпмүшелігінің кейбір ішкі көпмүшелігі.

Оптимизациялық есеп (V, F, W ) үштік түрінде беріледі. Мұндағы F=f(x) функциясы мақсатты функция, ал W - оптимизациялық есептің мүмкін болатын көпмүшелігі (мүмкін болатын шешімдер жиыны) деп аталады.

Оптимизациялық есептер екі түрде болады: максимизациялау есептері және минимизациялау есептері. Минимизациялау (максимизациялау) (V, F, W ) есебі мүмкін болатын W көпмүшелігінде F мақсатты функцияның ең кіші (ең үлкен) мәндерін табуға негізделген [4, 5].

(V, F, W ) минимизациялау (максимизациялау ) есебін шешу үшін, оның тиімді шешімін табу жеткілікті, яғни кез келген хÎ W үшін F(х₀)£ F(x) (F(х₀)³ F(x)) шарты орындалатын х_{0Î W} табу.

Оптимизациялық есептің тиімді шешімі болмаса, онда есеп шешілмейді деп аталады. (V, F, W ) минимизациялау (максимизациялау) есебінің шешімі болмайды, егер W облысында F мақсатты функциясы төменнен (жоғарыдан) шенелмеген болса.

Оптимизациялық есепті шешу дегеніміз - есептің тиімді шешімін табу немесе шешімі жоқтығын анықтау.

Кез келген максимизация есебін (V, F, W ) минимизация есебімен (V, -F, W ) ауыстыруға болады; бұл есептердің екеуінің де шешімдері болмайды немесе екеуінің де тиімді шешімдері болады.

Оптимизациялық есепті шешу әдістері мақсатты функцияның түріне және W мүмкін болатын жиындар облысына байланысты болады.

Егер мақсатты функция n айнымалыдан тұратын функция болса, онда оптимизациялық есепті шешу әдісін көбінесе математикалық программалу әдісі деп атайды. Есептерде бірқатар амалдар программасы (шешу жоспары) ізделінетіндіктен осы жағдайда «программалау» термині қолданылды. Осы жағдайда шартты, яғни есепте кейбір программа жағдайлары (шешу жоспарлары) ізделінеді. Математикалық программалаудың негізгі бөлімі сызықтық программалау болып табылады [6].

(V, F, W ) оптимизациялық есебіндегі V=Rⁿ-дегі мақсаттық функциясы сызықтық, W - бірқатар сызықтық теңдеулер және n белгісізі бар сызықтық теңсіздіктер жүйесінің шешімдер жиыны болса, онда оны сызықтық программалау есебі деп атаймыз.

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

в) берілген есеп (минимизациялау немесе максимизациялау) қандай типке жататыны анықталса.

Егер I = Æ (I = M ) болса, онда (1.2) – (1.3) жүйесі тек қана сызықтық теңсіздіктен (теңдеуден) тұрады.

(m x n) өлшемді матрицада (i, j) элементінің орнында (1.2) – (1.3) жүйесінің і-шектеуінің х_j коэффиценті тұрса, яғни

бағаналары (1.2) – (1.3) есебінің шарт векторы деп аталады. Р₀ векторы берілген есептің шектеулер векторы деп аталады.

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

1⁰. Сызықтық программалау есебінің мүмкін болатын шешімдерінің жиыны Rⁿ кеңістігінің дөңес немесе бос ішкі жиыны болып табылады.

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

3⁰. Сызықтық программалу есептерінің тиімді шешімі (егер ол бар болса) үнемі мүмкін болатын шешімднр жиынының шекарасында болады және Rⁿ кеңістігінің ішкі дөңес жиыны болады.