Сурет. Деңгей сызықтары және вектор бағыттауыштары

Ос нүктелердің әрқайсысының барлық нүктелерінде мақсат функция бір мәнге тең. Сондықтан бұл түзулерді мақсат функцияның деңгей сызықтары деп атайды. N(3,9) векторы осы түзулердің барлығына перпендикуляр және мақсат функцияның үлкен өсу бағытын көрсетеді.

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

Мысал. Z = х_: + 2х₂ функциясын максимизациялайтын, Z = х_: + 2х₂ функциясын минимизациялайтын

2х_г + х₂ > 2, х_х + Зх₂ > 3, Xj - х₂> -1, < Зх_х - х₂ < 6, Xj + х₂ < 5, _Xl>0, х₂>0 теңсіздіктер жүйесінің тиімді графикалық шешімін табыңыз.

16 сурет-Сызықтық программалау есебінің графикалық шешімі

Бұл жерден егер мүмкін шешімдер аймағы дөңес көпбұрыш болса, онда Z сызықтық функциясының max немесе min осы көпбұрыштың төбелерінің төбелерінің бірінде жетеді.

Может представиться случай, когда экстремальное зна­чение Z экстремалды мәні екі төбеде алынатын жағдай кездеседі, онда осы екі төбелені біріктіріп тұрған кесіндіде жататын кез келген нүктеде экстремалды мән алынады. Теңсіздіктер жүйесінің мүмкін мәндерінің түрі (екі айнымалы үшін) бос, бір нүкте, дөңес көпбұрыш немесе дөңес шектелмеген көпбұрышты аймақ болуы мүмкін.

Сызықтық программалау есебінің барлық жоспарлар жиыны дөңес. Келесі теорема орынды: СП есебінің сызықтық функциясы шешім көпбұрышының (көпжақтың) бұрыштық нүктесінде экстремалды мәнін алады.

Егер теңсіздіктер жүйесінде белгісіздер саны үшке тең болса, онда әрбір теңдік геометриялық түрде үш өлшемді жазықтықтың жартылай жазықтығын ұсынады. Бұл жартылай жазықтықтар қиылыса отырып, шешімнің көпжағы деп аталатын жалпы бөлігін құрайды.

Сонымен, егер сызықтық программалау есебінің сызықтық функциясы шешімнің көпжағында шектелсе, онда:

1) сызықтық программалау есебінің сызықтық функциясы отимум нүктесіне жететін шешім көпжағының (көпбұрышының) бұрыштық нүктесі бар болады;

2) әрбір таяныш жоспар шешім көпжағының бұрыштық нүктесіне сәйкес келеді.

Сондықтан сызықтық программалау есебін шешу үшін тек шешім көпжағының бұрыштық нүктесін, яғни таяныш жоспарды зерттеу қажет. СП-дың қарастырылып отырған есептеу әдістерінің негізінде келесі іргелі теорема жатыр.

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

Бұл теорема, кем дегенде бір тиімді таяныш шешімнің бар екенін көрсетеді, бірақ, есепте бірнеше тиімді таяныш шешім (альтернативный оптимум) кездесуі мүмкін.

Демек, сызықтық программалау есебін шешудің принципиальды схемасыкелесідей:

Жордан шығаруы көмегімен жүйенің таяныш шешімі табылады;

осы есептер үшін Z функциясының мәні есептелінеді;

табылған шешімдерден экстремалды Z табылады.

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

Шешімді біртіндеп жақсарту идеясы симплекс әдісімен сызықтық прогарммалау есебін шешудің негізгі сандық әдісінде жатыр.