Айқындық жағдайында шешімдер қабылдау есептері

Дәріс 5. Айқындық жағдайында шешімдер қабылдау есептері

Сызықтық программалау. Сызықтық программалау есептерінің математикалық модельдері

Сызықтық программалау (СП) есебінің жалпы қойылымы: берілген

𝑛

𝐹 = ∑ 𝑐𝑗𝑥𝑗

𝑗=1

(1)

функциясының

∑𝑛 𝑎𝑖𝑗𝑥𝑗 ≤ 𝑏𝑖 (𝑖 = 1̅̅̅,̅𝑘̅),

𝑗=1 (2)

∑𝑛 𝑎𝑖𝑗𝑥𝑗 = 𝑏𝑖 (𝑖 = ̅𝑘̅̅+̅̅̅1̅̅,̅𝑚̅̅),

𝑗=1 (3)

𝑥𝑗 ≥ 0 (𝑗 = ̅1̅̅,̅𝑙, 𝑙 ≤ 𝑛) (4)

шарттары орындалғандағы максимум немесе минимум мәнін табу керек, мұндағы 𝑐𝑗, 𝑎𝑖𝑗, 𝑏𝑖 – берілген тұрақты сандар және 𝑘 ≤ 𝑚.

Берілген (1) функция СП есебінің мақсаттық функциясы, ал (2)-(4) шарттар сол есептің шектеулері деп аталады. Мақсаттық функциясы мен шектеулерге 𝑥𝑗 ≥ 0 (𝑗 = ̅1̅̅,̅𝑛̅) айнымалыларының бірінші дәрежесі ғана

кіретіндіктен (1)-(4) есебін сызықты программалау (СП) есебі деп атайды.

СП есебінің стандарттық (симметриялық) қойылымында берілген мақсаттық функциясының 𝑘 = 𝑚, 𝑙 = 𝑛 үшін (2), (4) шарттар орындалғандағы максимум мәні ізделінеді. Басқаша айтқанда, СП есебінің стандарттық қойылымында (2), (3) шектеулердің орнына тек теңсіздіктер беріледі.

СП есебінің канондық (негізгі) қойылымында мақсаттық функциясының 𝑘 = 0, 𝑙 = 𝑛 үшін (3), (4) шарттар орындалғандағы максимум мәні ізделінеді. Басқаша айтқанда, СП есебінің канондық қойылымында (2),

(3) шектеулердің орнына тек теңдіктер ғана беріледі.

Берілген (2)-(4) шектеулерді қанағаттандыратын 𝑋⃗ = (𝑥1, 𝑥2, … , 𝑥𝑛)

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

Мақсаттық функциясының экстремум мәндерін қамтамасыз ететін

⃗𝑋⃗⃗⃗∗⃗ =

(𝑥∗, 𝑥∗, … , 𝑥∗ ) жоспарын СП есебінің тиімді жоспары деп атайды. Мақсаттық

1 2 𝑛

функциясы үшін әрқашан 𝐹(𝑋) ≤ 𝐹(𝑋∗) немесе 𝐹(𝑋) ≥ 𝐹(𝑋∗) теңсіздігі

орындалады.

СП есебінің осы үш қойылымы да өзара эквивалентті. Олай болса, бір қойылымдағы СП есебін екінші қойылымдағы СП есебіне түрлендіруге болады. Демек, бір қойылымдағы СП есебінің тиімді жоспары екінші қойылымдағы СП есебінің де тиімді жоспары болады. Ал 𝐹 мақсаттық функциясының минимумы (немесе максимумы) ізделінетін СП есебін қарама-

қарсы таңбалы, яғни 𝐹 мақсаттық функциясының максимумы (сәйкесінше минимумы) ізделінетін СП есебіне келтіруге болады.

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

Сызықтық программалау есептерінің математикалық модельдері 1-мысал. Тігін тігу цехы екі түрлі киім тігіп шығарады: көйлек және

костюм. Оған 3 түрлі шикізат пайдаланылады: мақта мата, жібек мата, фурнитура. Көйлектің және костюмнің құны сәйкесінше 3500 және 5600 теңгені құрайды. Шикізат қоры: мақта мата 210 м, жібек мата 145 м, фурнитура 108 дана. Бір көйлекті тігіп шығару үшін 3 м мақта мата, 2 м жібек мата, 3 фурнитура жұмсалса, бір костюмді тігу үшін 4 м мақта мата, 2 м жібек мата және 2 фурнитура қажет. Ең көп кіріс әкелетін көйлек пен костюм тігу жоспарын табу керек. Экономикалық есептің математикалық моделін құрыңыз.

Шешу: