Սիմպլեքս մեթոդ

Սիմլեքս մեթոդ, գծային ծրագրավորման օպտիմալացման խնդիրների լուծման ալգորիթմ, որի օգնությամբ դիտարկում են ուռուցիկ բազմանիստ որոշման տիրույթը բազմաչափ էվկլիդյան տարածության մեջ։

Մեթոդի էությունն է կառուցվում է հենային պլան, որի օգնությամբ անընդհատ հաշվում ենք նպատակային ֆունկցիան այնքան, մինչև տեղի է ունենում օպտիմալության պայմանը։

Պատմական ակնարկ

Պատմության մեջ առաջին անգամ գծային ծրագրավորման ընդհանուր խնդիրրը առաջարկվել է 1947 թվականին Ջորջ Բերնարդ Դանցիգի, Մարշալ Վուդի և ԱՄՆ-ի ռազմաօդային ուժերի դեպարտամենտի աշխատակիցների կողմից։ Այդ ժամանակ խումբը զբաղված էր ռազմական առաջադրանքներում ու պլանավորման խնդիրներում մաթեմատիկական և մոտ գիտությունների մեթոդների օգտագործման ուսումնասիրությամբ։ Հետագայում այդ գաղափարների զարգացման համար BBC ընկերությունը ստեղծեց Project SCOOP անունով հատուկ խումբ։ Առաջին հաջող լուծումը գծային ծրագրավորման համար արվեց 1952 թվականին ЭВМ SEAC խմբի կողմից։

Նկարագրություն

Գծային ծրագրավորման խնդիրը այն է, որ անհրաժեշտ է գտնել որոշակի գծային ֆունկցիայի մինիմալ կամ մաքսիմալ արժեքը տրված սահմանափակումներին բավարարող բազմաչափ որոշման տիրույթում։

Փոփոխականների վրա դրված սահմանափակումներից յուրաքանչյուրը իրենից կիսահարթություն է ներկայացնում։ Արդյունքում բոլոր սահմանափակումերը միասին ձևավորում են բազմանկյուն, որը նաև կոչվում է էվկլիդյան տարածություն։ W(x) = C հավասարումը, որտեղ W(x) գծային ֆունկցիան պետք է ընդունի մաքսիմում արժեք (կամ մինիմում),պատկանում է L(C) հիպերհարթությունը։ C պարամետրից կախվածության ուղիղները ստեղծում են մակարդակի ուղիղների ընտանիք։ Այնուհետև պետք է ընտրի C-ի այն մաքսիմում (կամ մինիմում)արժեքը, որի դեպքում մակարդակի ուղիղը շոշափում է բազմանիստ որոշման տիրույթը գոնե մեկ անգամ։ Այդ մաքսիմում (կամ մինիմում)արժեքին համապատասխանող կետը փնտրվում է տիրույթի անկյունային կետերում։ Սիմպլեքս մեթոդի սկզբունքն այն է, որ ընտրվում է ինչ-որ անկյունային կետ, որից հետո սկսում ենք շարժվել բազմանիստի մնացած անկյունային կետերում։ Երբ արդեն մի անկյունային կետից մյուսը անցնելուց հետո ֆունկցիայի արժեքը չի մեծանում(փոքրանում), ուրեմն գտել ենք օպտիմալ լուծումը։ Այսպիսով սիմպլեքս-մեթոդի հաշվողական գործընթացը բաժանվում է երկու փուլի․

թույատրելի արժեքների որոշում,
մի անկյունային կետից հաջորդաբար անցում մյուսին, որը կապահովի նպատակային ֆունկցիայի օպտիմալ արժեքը։

Գրականություն

Хемди А. Таха Глава 3. Симплекс-метод // Введение в исследование операций = Operations Research: An Introduction. — 7-е изд. — М.: «Вильямс», 2007. — С. 95-141. — ISBN 0-13-032374-8
Акулич И.Л. Глава 1. Задачи линейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9
Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 5-8459-0857-4
В. Н. Шевченко, Н. Ю. Золотых Линейное и целочисленное линейное программирование. — Нижний Новгород: Издательство Нижегородского госуниверситета им. Н.И. Лобачевского, 2004. — С. 63-66 (раздел 2.8. Замечания о сложности решения ЗЛП).

Արտաքին հղումներ

Վիքիպահեստն ունի նյութեր, որոնք վերաբերում են «Սիմպլեքս մեթոդ» հոդվածին։