Математик программалаштириш-нинг махсус масалалари Ўйинлар назарияси Чизиқсиз программалаштириш

2 - расм
Бунда .
Демак, глобал максимум , минимум нуқтаси эса тенг экан.
Шартли экстремум. Лагранж кўпайтувчилар усули
Шартсиз чизиқсиз программалаштириш масаласи ва уни ечиш усули. Агар чизиқсиз программалаштириш масаласида
(1)
номаълум ўзгарувчиларга шартлар қўйилмаса, у ҳолда бу масала шартсиз чизиқсиз программалаштириш масаласи дейилади. Бу масала вектор кўринишда қуйидагича бўлади
(2)
яъни, _. Бу масала чизиқсиз программалаштиришнинг шартсиз максимал масаласи дейилади.
Бу шартсиз чизиқсиз программалаштириш масаланинг экстремал қийматларини аниқлашни, кўп ўзгарувчили функциянинг дифференциал ҳисоби мавзусида кўриб ўтган эдик. Бунга кўра, бу каби функцияларнинг экстремум қийматлари, иккинчи тартибли хусусий ҳосилалардан тузилган Гессе матрицасининг мусбат ёки манфий аниқланганлигидан иборат бўлиб, бу эса ўз навбатида Сильвестр методи билан топилар эди.
Шартли чизиқсиз программалаштириш масаласи. Лагранж кўпайтувчилар усули. Чизиқли программалаштириш масаласи берилган бўлсин
(3)
(4)
Фараз қиламиз, функциялар , ўзларининг биринчи тартибли узлуксиз ҳосилаларга эга бўлсин.
Чегаравий масалалар тенгламалар кўринишида берилгани учун, масалани ечиш учун, кўп ўзгарувчили функциянинг шартли экстремумини топиш усулидан фойдаланамиз.
Масалани ечиш учун Лагранж функцияси тузилади
(5)
Сўнгра, унинг биринчи тартибли хусусий ҳосилалари аниқланади

Бу ҳосилаларни нолга тенглаштириб қуйидаги система ҳосил қилинади
(6)
Системани ечиб, функцияга экстремал қиймат берувчи нуқталар тўплами топилади.
(5) функция, Лагранж функцияси, - сонлар Лагранж кўпайтувчилари дейилади. Агар функция нуқтада экстремумга эга бўлса, у ҳолда шундай вектор топиладики, бунда нуқта (6) системанинг ечими бўлади.
Демак, (6) системани ечиб, функцияга экстремал қийматлар берувчи нуқталар тўплами ҳосил қилинади. Бу нуқталардан фойдаланиб функциянинг глобал экстремум қийматларини аниқлаш мумкин.
Лагранж функциясининг иккинчи тартибли тўла дифференциали қуйидагича берилади
. (7)
Бу формуладаги ёзув, нинг квадратини ифодалайди, яъни .
формуланинг ишорасини аниқлаш учун, ва ифодалар орасидаги муносабатни ҳам аниқлаш зарур. Бу (7) формуладан кўриниб турибдики, ўзгарувчилар бўйича хусусий ҳосилалар мавжуд эмас. Стационар нуқтада функциянинг тўла дифференциали нолга тенг:
.
Лагранж кўпайтувчилар усули асосида масалани ечиш этаплари:
1. Лагранж функцияси тузилади

2. Лагранж функциясидан барча ўзгарувчилар бўйича(6) хусусий ҳосила топилиб, нолга тенглаштирилади. Ҳосил бўлган тенгламалар системасини ечиш натижасида барча стационар нуқталар топилади.
3. Лагранж функциясининг иккинчи тартибли тўла дифференциали тузилади ва унингш ишораси ҳар бир стационар нуқтада аниқланади. Агар стационар нуқтада шарт бажарилса, бу стационар нуқта локал максимум, аксинча эса, яъни бўлса, локал минимум бўлади.
Мисол. Функциянинг шартли экстремум нуқтасини топинг

чегаравий шартда:

Ечиш. Лагранж функцияси тузилади
.
Лагранж функциясининг хусусий ҳосилаларини аниқлаймиз

Бу тенгламалар системасининг ечими да .
Функциянинг иккинчи тартибли ҳосилаларини аниқлаймиз

Бу стационар нуқтани экстремумга текширамиз:
.
Энди нинг ишорасини аниқлаш учун стационар нуқталарнинг хоссасидан фойдаланамиз, белгилаш олиб
.
Демак, , бундан эса
.
Демак, нуқта берилган функциянинг максимум нуқтаси экан
.
Масалани иккинчи усул билан ҳисоблаймиз.
Ушбу симметрик матрицадан фойдаланиб масаланинг оптимал ечимини аниқлаймиз
.
Агар стационар нуқтада бўлса, берилган функция бу нуқтада минимумга эришади аксинча эса, яъни бўлса, максимумга эришади.
Юқоридаги масаланинг оптимал ечимини бошқа усул билан аниқлаймиз.
А матрицани, нуқта учун ёзиб оламиз
Бунда
.
.
Демак, бўлгани учун, нуқта берилган функциянинг максимум нуқтаси бўлар экан, бундан эса
.

Мисол. Функция шартли экстремум нуқтасини топинг
чегаравий шартларда:

Ечиш. Лагранж функцияси тузилади

Лагранж функцияси дан номаълум ўзгарувчилар ва параметрлар бўйича хусусий ҳосилалар олиб, уларни нолга тенглаштириб, қуйидаги тенгламалар системаси ҳосил қилинади:

Бундан .