Verbum

Сацкоў Юрый Назаравіч

т. 14, с. 209

ЛІНЕ́ЙНАЕ ПРАГРАМАВА́ННЕ,

раздзел матэматычнага праграмавання, прысвечаны тэорыі і метадам рашэння задач аб экстрэмумах (мінімумах ці максімумах) лінейных функцый пры абмежаваннях, зададзеных сістэмамі лінейных роўнасцей і няроўнасцей.

Задачы Л.п. з’яўляюцца матэм. мадэлямі задач эканомікі і вытв-сці, напр., задача рацыянальнага размеркавання часу (аптымальнага плана работы) прадпрыемства па розных тэхнал. спосабах, трансп. задача, дзе адшукваецца найб. эканомны план дастаўкі прадуктаў з пунктаў вытв-сці ў пункты спажывання, задача складання самага таннага кармавога рацыёну з пэўных кармоў. Агульная пастаноўка задачы і метад яе рашэння прапанаваны Л.В.Кантаровічам (1939), найб. пашыраны сімплекс-метад рашэння задач (накіраваны перабор мноства дазволеных рашэнняў) — амер. матэматыкам Дж.​Данцыгам (1949). Гл. таксама Аперацый даследаванне.

На Беларусі праблемы Л.п. і яго дастасаванняў даследуюцца ў Ін-це матэматыкі Нац. АН, БДУ і інш.

Літ.:

Данциг Дж. Б. Линейное программирование, его применения и обобщения: Пер. с англ. М., 1966;

Габасов Р., Кириллова Ф.М. Методы линейного программирования. Ч. 1—3. Мн., 1977—80.

Ю.​Н.​Сацкоў.

т. 9, с. 266

МАТЭМАТЫ́ЧНАЕ ПРАГРАМАВА́НЕ,

раздзел прыкладной матэматыкі, прысвечаны тэорыі і метадам вызначэння максімумаў (ці мінімумаў) функцый многіх пераменных пры наяўнасці дадатковых абмежаванняў, зададзеных сістэмай роўнасцей і няроўнасцей. Сфарміравалася ў 1950-я г. ў сувязі з практычнымі задачамі выбару аптымальнага варыянта сярод многіх магчымых (гл. Аперацый даследаванне, Гульняў тэорыя).

Задачы М.п. з’яўляюцца матэм. мадэлямі розных задач эканомікі, тэхнікі, вытв-сці, ваен. справы, у якіх патрабуецца вызначыць аптымальны план (праграму) дзеянняў з улікам пэўных умоў і абмежаванняў. Асн. раздзелы М.п.: лінейнае праграмаванне, нелінейнае праграмаванне, а таксама выпуклае (мэтавая функцыя і мноства дазволеных планаў у ім выпуклыя; гл. Выпукласць і ўвагнутасць) і цэлалікавае (пераменныя — цэлыя лікі) праграмаванні; шэраг задач М.п. рашаецца на аснове метаду дынамічнага праграмавання. Разглядаюцца таксама стахастычныя задачы для мадэліравання практычных сітуацый ва ўмовах рызыкі і неакрэсленасці.

На Беларусі мадэлі і метады М.п. даследуюцца ў Ін-тах матэматыкі і тэхн. кібернетыкі Нац. АН, БДУ.

Літ.:

Карманов В.Г. Математическое программирование. 3 изд. М., 1986.

Ю.​Н.​Сацкоў.

т. 10, с. 212

ГРА́ФАЎ ТЭО́РЫЯ,

раздзел матэматыкі, які вывучае аб’екты на аснове геаметрычнага падыходу. Асн. паняцце графаў тэорыі — граф: мноства пунктаў (вяршынь) і мноства сувязей (рэбраў, дуг), што злучаюць некаторыя (або ўсе) пары вяршынь. Напр., сетка чыгунак, аўтамаб. (або інш.) дарог з пазначэннем на дугах адлегласцей паміж населенымі пунктамі або іх прапускных здольнасцей. Выкарыстоўваецца ў тэорыі перадачы інфармацыі, тэорыі трансп. сетак, камп’ютэрнай графіцы, аўтаматызацыі праектавання і інш.

Першыя задачы графаў тэорыі былі звязаны з рашэннем галаваломак і матэм. забаўляльных задач (напр., задачы аб Кёнігсбергскіх мастах, аб расстаноўцы ферзей на шахматнай дошцы, аб перавозках, кругасветным падарожжы, задача 4 фарбаў і інш.). Адным з першых вынікаў у графаў тэорыі быў крытэрый існавання абходу графа без паўтораў рэбраў (Л.Эйлер, 1736). У 19 ст. з’явіліся работы, у якіх пры рашэнні практычных задач атрыманы важныя вынікі ў графаў тэорыі (задачы пабудавання эл. ланцугоў, падліку хім. рэчываў з рознымі тыпамі малекулярных злучэнняў і інш.). У 20 ст. задачы, звязаныя з графамі, з’явіліся ў тапалогіі, алгебры, тэорыі лікаў, тэорыі імавернасці і інш. Найб. развіццё графаў тэорыя атрымала з 1950-х г. у сувязі са станаўленнем кібернетыкі і развіццём выліч. тэхнікі.

На Беларусі даследаванні па графаў тэорыі вядуцца ў БДУ (уплыў розных параметраў на ўласцівасці графаў), Ін-це матэматыкі (розныя прадстаўленні графаў, алгарытмічныя аспекты графаў тэорыі), Ін-це тэхн. кібернетыкі (графы ў задачах аптымальнага ўпарадкавання) Нац. АН.

Літ.:

Лекции по теории графов. М., 1990.

Ю.​Н.​Сацкоў.

т. 5, с. 411