Кіріспе

Оптимизациялау мәселелерін шешу әдісі, теледидар хабарларын таратуды білдіретін ретроним. Сызықтық бағдарламалау (LP), сондай-ақ сызықтық оптимизация деп аталады, математикалық модельдегі ең жақсы нәтижеге (максималды пайда немесе ең төменгі шығын сияқты) қол жеткізу әдісі болып табылады, оның талаптары мен мақсаты сызықтық қатынастармен өрнектеледі. Сызықтық бағдарламалау – математикалық бағдарламалаудың (математикалық оңтайландыру деп те аталады) ерекше жағдайы. Формальдырақ айтқанда, сызықтық бағдарламалау – сызықтық теңдіктер мен сызықтық теңсіздіктердің шектеулеріне бағынышты сызықтық мақсатты функцияны оңтайландыру тәсілі. Оның мүмкін болатын аймағы – дөңгелек политоп, ол шекті жарты кеңістіктердің қиылысы ретінде анықталған жиын, әрқайсысы сызықтық теңсіздікпен сипатталады. Оның мақсатты функциясы – осы политопта анықталған нақты мәнді аффиндік (сызықтық) функция. Сызықтық бағдарламалау алгоритмі, егер мұндай нүкте болса, осы функцияның ең үлкен (немесе ең кіші) мәнін иеленетін политоптың нүктесін табады. Сызықтық бағдарламалар – стандартты түрде өрнектелуі мүмкін мәселелер. Мұнда – анықталуға тиіс айнымалылардың компоненттері, – берілген векторлар, ал – берілген матрица. Осы жағдайда, барынша арттырылуға тиіс функция (осы жағдайда) мақсатты функция деп аталады. – және шектеулері мақсатты функция оңтайландырылатын дөңгелек политопты анықтайды. Сызықтық бағдарламалау зерттеудің түрлі салаларында қолданылуы мүмкін. Бұл математикада кеңінен қолданылады, сондай-ақ бизнес, экономика және кейбір инженерлік мәселелерде де қолданылады. Сызықтық бағдарламалау модельдерін қолданатын салалар: көлік, энергетика, телекоммуникация және өндіріс. Ол жоспарлау, маршрутизация, кестелеу, тағайындау және жобалаудағы әртүрлі мәселелерді модельдеуде өте пайдалы болып көрінді.

Тарих

Сызықтық теңсіздіктер жүйесін шешу мәселесі кем дегенде 1827 жылға, оларды шешу әдісін жариялаған Фурьеге дейін жетеді, және оның есімімен Фурье-Мотцкин жою әдісі аталған. 1930 жылдардың соңында кеңестік математик Леонид Канторович пен американдық экономист Василий Леонтьев тәуелсіз түрде сызықтық бағдарламалаудың практикалық қолданысын зерттеді. Канторович өндіріс кестелеріне назар аударды, ал Леонтьев экономикалық қолданыстарды зерттеді. Олардың маңызды еңбектері ондаған жылдар бойы көңілден тыс қалды. Бұрылыс Екінші дүниежүзілік соғыс кезінде болды, сызықтық бағдарламалау өте маңызды құрал ретінде пайда болды. Ол соғыс уақытындағы күрделі мәселелерді шешуде кеңінен қолданылды, оның ішінде көлік логистикасы, кестелеу және ресурстарды бөлу. Сызықтық бағдарламалау бұл процестерді шығындар мен қолданыстағы ресурстар сияқты маңызды шектеулерді ескере отырып оңтайландыруда құнды болып шықты. Бастапқыда көпке танылмағанмен, соғыс кезіндегі жетістіктері сызықтық бағдарламалауды танымал етті. Екінші дүниежүзілік соғыстан кейін бұл әдіс кеңінен мойындалып, операциялық зерттеулерден экономикаға дейінгі түрлі салалардағы негізгі құралға айналды. Канторович пен Леонтьевтің 1930 жылдардың соңындағы елеусіз қалған үлесі, шешім қабылдау процестерін оңтайландыруда сызықтық бағдарламалауды қабылдау мен пайдаланудың негізіне айналды. Канторовичтің еңбегі бастапқыда КСРО-да назардан тыс қалды. Канторовичпен шамалас уақытта голланд-американдық экономист Т.К. Купманс классикалық экономикалық мәселелерді сызықтық бағдарламалар түрінде тұжырымдады. Кейіннен Канторович пен Купманс 1975 жылғы Экономика ғылымдары саласындағы Нобельдік сыйлықты бөлісті. Хичкок 1957 жылы қайтыс болды, ал Нобельдік сыйлық постмортумды түрде берілмейді. 1946-1947 жылдары Джордж Б. Данциг АҚШ Әуе күштеріндегі жоспарлау мәселелерін шешу үшін жалпы сызықтық бағдарламалау формуласын тәуелсіз түрде жасады. 1947 жылы Данциг симплекс әдісін де ойлап тапты, ол көп жағдайда сызықтық бағдарламалау мәселесін тиімді шешуге мүмкіндік берді. Бірақ осы саладағы маңызды теориялық және практикалық серпіліс 1984 жылы Нарендра Кармаркар сызықтық бағдарламалау мәселелерін шешу үшін жаңа ішкі нүкте әдісін ұсынғанда болды.

Қолданылуы

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

Мысалдар

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

Қосымша бос күй

Дуальдың оңтайлы шешімін, егер комплементарлық дұрыссыздық теоремасы арқылы, примальдың оңтайлы шешімі ғана белгілі болса, табуға болады. Теорема былай тұжырымдайды:

x = (x1, x2, ..., xn) примальдық шешімдер жиымына жатады және y = (y1, y2, ..., ym) дуальдық шешімдер жиымына жатады делік. (w1, w2, ..., wm) сәйкес примальдық бос айнымалыларды, ал (z1, z2, ..., zn) сәйкес дуальдық бос айнымалыларды белгілейді. Онда x және y өздерінің тиісті мәселелері үшін оңтайлы болады, егер және тек қана егер:
xj zj = 0, j = 1, 2, ..., n және
wi yi = 0, i = 1, 2, ..., m.

Демек, егер примальдың i-ші бос айнымалысы нөлге тең болмаса, онда дуальдың i-ші айнымалысы нөлге тең болады. Сол сияқты, егер дуальдың j-ші бос айнымалысы нөлге тең болмаса, онда примальдың j-ші айнымалысы нөлге тең болады. Оптималдылықтың бұл қажетті шарты қарапайым экономикалық принципті көрсетеді. Стандартты түрінде (максимизацияланғанда), егер шектелген примальдық ресурста бос орын болса (яғни "қалдықтар" болса), онда осы ресурстың қосымша көлемі құнды болмауы керек. Сол сияқты, егер дуальдық (көлеңкелік) бағаның теріс емес болу талабы орындалмаса, яғни баға нөлге тең болмаса, онда жетіспейтін ресурстар болуы керек ("қалдықтар" жоқ).

Оңтайлы шешімдердің болуы

Геометриялық тұрғыдан алғанда, сызықтық шектеулер мүмкін болатын аймақты анықтайды, ол – дөңес полиэдр. Сызықтық функция – дөңес функция, яғни кез келген жергілікті минимум жаһандық минимум болып табылады; сондай-ақ, сызықтық функция – қуыс функция, яғни кез келген жергілікті максимум жаһандық максимум болып табылады. Оптималды шешім міндетті түрде болуы керек емес, себебі екі мәселе бар. Біріншіден, егер шектеулер келіспесе, онда мүмкін болатын шешім болмайды: мысалы, x ≥ 2 және x ≤ 1 шектеулерін бірдей орындау мүмкін емес; мұндай жағдайда, сызықтық бағдарлама (LP) шешімі жоқ деп айтамыз. Екіншіден, егер полиэдр мақсатты функция градиентінің бағытында шектелмеген болса (мұнда мақсатты функция градиенті – мақсатты функцияның коэффициенттерінің векторы), онда оптималды мәнге қол жеткізілмейді, өйткені мақсатты функцияның кез келген шекті мәнінен де жақсы нәтиже алуға болады.

Көпбұрыштардың оңтайлы шыңдары (және сәулелері)

Әйтпесе, егер мүмкін болатын шешім болса және егер шектеу жиынтығы шектелген болса, онда оңтайлы мән әрқашан шектеу жиынтығының шекарасында, дөңес функциялар үшін максимум принципі (немесе ойыс функциялар үшін минимум принципі) бойынша қол жеткізіледі, себебі сызықтық функциялар бір мезгілде дөңес және ойыс болып табылады. Дегенмен, кейбір мәселелерде ерекше оңтайлы шешімдер болуы мүмкін; мысалы, сызықтық теңсіздіктер жүйесіне мүмкін болатын шешім табу мәселесі – мақсатты функциясы нөлдік функция (яғни, барлық жерде нөл мәнін қабылдайтын тұрақты функция) болатын сызықтық бағдарламалау мәселесі. Мұндай мүмкіншілік мәселесінде, егер екі түрлі шешім болса, онда шешімдердің кез келген дөңес комбинациясы да шешім болып табылады. Политоптың төбелері негізгі мүмкін шешімдер деп те аталады. Мұндай атаудың себебі мынадай: d айнымалылардың санын белгілейік. Сызықтық теңсіздіктердің негізгі теоремасы (мәселе шешілген жағдайда) LP-нің әрбір x* төбесі үшін, LP-ден d (немесе одан кем) теңсіздік шектеулерінің жиынтығы бар екенін көрсетеді, осы d шектеуді теңдестіктер ретінде қарастырғанда бірегей шешім x* болады. Осылайша, LP шешімдерінің үздіксіздігіне қарағанда, осы төбелерді шектеулер жиынтығының белгілі бір ішкі жиынтықтарын (дискретті жиынтық) қарастыру арқылы зерттеуге болады. Бұл принцип сызықтық бағдарламаларды шешуге арналған симплекс алгоритмінің негізі болып табылады.

Данцигтің симплекстік алгоритмі

Джордж Данциг 1947 жылы жасаған симплекс алгоритмі LP мәселелерін политоптың төбесінде қолданылатын шешімді құрастыру арқылы шешеді, содан кейін мақсаттық функцияның мәні төмендемейтіндей политоптың қабырғалары бойынша жолмен қозғалып, оптималдыққа жеткенше іздейді. Көптеген практикалық мәселелерде "тоқтау" кездеседі: мақсаттық функцияның өсуінсіз көптеген півоттар жасалады. Сирек кездесетін практикалық мәселелерде симплекс алгоритмінің стандартты нұсқалары тікелей "айналып" кетуі мүмкін, бұл практикалық мәселелердегі оның әрекетіне ұқсас. Дегенмен, симплекс алгоритмінің ең жаман жағдайдағы өнімділігі нашар: Кли мен Минти сызықтық бағдарламалау мәселелерінің бірнешеуін жасады, онда симплекс әдісі проблеманың өлшеміне экспоненциалды түрде қадамдар қажет болады. Шындығында, біраз уақыт бойы сызықтық бағдарламалау мәселесі полиномиалдық уақытта шешілетіні, яғни күрделілік класы P-ге жататыны белгісіз болды.

Қиылысу алгоритмі

Дантцигтің симплекс алгоритмі сияқты, крисс-кросс алгоритмі де негіздер арасында ауысып, негіз алмастыру алгоритмі болып табылады. Дегенмен, крисс-кросс алгоритмінің қанағаттандырылуын сақтауы міндетті емес, ол қанағаттандырылған негізден қанағаттандырылмаған негізге де ауысуы мүмкін. Крисс-кросс алгоритмінің сызықтық бағдарламалаудағы полиномиалдық уақыт күрделілігі жоқ. Екі алгоритм де ең жаман жағдайда D өлшемді (бұзылған) кубтың барлық 2D бұрыштарын, яғни Klee-Minty кубын аралап шығады.

Ішкі нүкте

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

Хачиянға сәйкес эллипсоидты алгоритм

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

Вайдияның 87 алгоритмі

1987 жылы Вайдия уақыт ішінде жұмыс істейтін алгоритмді ұсынды.

Вайдияның 89 алгоритмі

1989 жылы Вайдия уақыт ішінде жұмыс істейтін алгоритмді жасады. Формальды түрде айтқанда, алгоритм ең нашар жағдайда арифметикалық операцияларды орындайды, мұндағы шектеулер саны – , айнымалылар саны – , ал биттер саны – .

Кіріс үнемділік уақыт алгоритмдері

2015 жылы Ли мен Сидфорд сызықтық бағдарламалауды уақытында шешуге болатынын көрсетті, мұнда нөлге тең емес элементтердің санын білдіреді, ал ең нашар жағдайда уақытты қабылдау жалғасады.

Ағымдағы матрицаны көбейту уақыты алгоритмі

2019 жылы Коэн, Ли және Сонг орындалу уақытын уақытқа дейін жақсартты, мұндағы – матрица көбейтудің экспоненті, ал – матрица көбейтудің дуалды экспоненті. (Қорытынды) дегеніміз – бұл матрицаны матрицаға уақыт ішінде көбейтуге болатын ең үлкен сан. Ли, Сонг және Чжанның келесі жұмысында олар басқа әдіс арқылы да сол нәтижені қайталады. Бұл екі алгоритм және жағдайында тиімді болып қалады. Цзян, Сонг, Вайнштейн және Чжанның нәтижесі оны уақытқа дейін жақсартты.

Ішкі нүктелік әдістер мен симплекс алгоритмдерін салыстыру

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