Лінейнае праграмаванне

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

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

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

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

Для рашэння задач лінейнага праграмавання патрабавалася распрацаваць асобыя метады. Асновы тэорыі гэтай галіны матэматыкі былі закладзены ў 1940-х гадах.

Магчыма графічнае рашэнне задач з дзвюма і некалькімі пераменнымі. Найбольш пашыраны сімплекс-метад (накіраваны перабор мноства дазволеных рашэнняў).

Задачы лінейнага праграмавання ўзнікаюць пры вырашэнні пытанняў планавання, найлепшай арганізацыі перавозак, рацыянальнага выкарыстання абсталявання, рабочай сілы, рознага роду рэсурсаў — кармавых, сыравіны і інш. Задачы эканамічных даследаванняў, як правіла, патрабуюць правядзення вялікай колькасці працаёмкіх разлікаў. Рашэнне гэтых задач істотна спрасцілася пасля з'яўлення электронна-вылічальных машын.

Літаратура

• Гутковіч Г. Лінейнае праграміраванне. — Мн.: Народная асвета, 1979. — 64 с., іл.
• Сацкоў Ю. Н. Лінейнае праграмаванне // Беларуская энцыклапедыя: У 18 т. Т. 9: Кулібін — Малаіта / Рэдкал.: Г. П. Пашкоў і інш. — Мн. : БелЭн, 1999. — Т. 9. — С. 266. — 10 000 экз. — ISBN 985-11-0035-8. — ISBN 985-11-0155-9 (т. 9).