Раздел 11. Глоссарий (словарь)

Математическое программирование — это раздел высшей математики, посвященный решению задач, связанных с нахождением экстремумов функций нескольких переменных при наличии ограничений на переменные.

Методами математического программированиярешаются задачи о распределении ресурсов, планировании выпуска продукции, ценообразовании, транспортные задачи и тл

Переменными задачи называются величины х_{, х₂, ••-, х_а, которые полностью характеризуют экономический процесс. Их обычно записывают в виде вектора X— (*,, х_г, ..., х_я).~

Система ограничений включает в себя систему уравнений и неравенств, которым удовяетворяюгпврвиениме-залачи и которые следуют из ограниченности ресурсов *ши д§угих экономических или физических условий, например положительности переменных и т.п.

Целевой функцией называют функцию переменных задачи* которая характеризует качество выполнения задачи и экстремум которой требуется найти.

Общая задача математического программирования формулируется следующим образом: найти экстремум целевой функции

Z{X) = /{*,, Xj, ..., х_я) ~» max (min) ,

и еоответетвующие ему переменные при условии, что эти переменные удовлетворяют системе ограничений

Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор X =* (х,, х_г, ..., х_я), удовлетворяющий системе ограничений и условиям неотрицательности.

Множество допустимых решений (планов) задачи образует область допустимых решений (ОДР).

Оптимальным решением (планом) задачи линейного программирования называется такое допустимое решение (план) задачи, при котором целевая функция достигает экстремума.

В общем случае задача линейного прогаммирования записывается так, что ограничениями являются как уравнения, так и неравенства, а переменные могут быть как неотрицательными, так и произвольно изменяющимися. В Том случае, когда все офаничения являются уравнениями и все переменные удовлетворяют условию неотрицательности, задачу линейного профаммирования называют канонической

Опорным решением задачи линейного программирования называется такое допустимое решение Х= (х,₀, х₂₀,..., х^, 0,..., 0), для которого векторы условий, соответствующие положительным координатам A_v А₂, .,., А_т, линейно независимы.

Число отличных от нуля координат опорного решения не может быть больше ранга г системы векторов условий (т.е. числа линейно независимых уравнений системы ограничений

Если число отличных от нуля координат опорного решения равно от, то оно (решение) называется невырожденным, в противном случае (меньше /я) — вырожденйым.

Базисом опорного решения называется базис системы векторов условий задачи, в состав которого «ходят векторы, соответствующие отличным от нуля координатам опорного решения

Симплексный метод — это метод целенаправленного перебора опорн-ых решений задачи

Задаче линейного программирования (исходной, или прямой) можно поставить в соответствие другую задачу, которая называется двойственной или сопряженной. Обе эти задачи образуют пару двойственных (или сопряженных) задач линейного программирования. Каждая из задач является двойственной к другой задаче рассматриваемой пары.

В транспортных задачах под поставщиками и потребителями понимаются различные промышленные и сельскохозяйственные предприятия, заводы, фабрики, склады, магазины и т.д. Однородными считаются грузы, которые могут,быть перевезены одним видом транспорта. Под стоимостью перевозок понимаются тарифы, расстояния, время, расход топлива и т.п.

Цикломназывается такая последовательность клеток таблицы транспортной задачи (/^у,), </,,у_г), (i₂J₂), • •-, (i_k,J_{), в которой две и только две соседние клетки расположены в одной строке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце.

Числа А называются оценками свободных клеток таблицы или векторов-условий транспортной задачи, не входящих в базис опорного ре-шения. В этом случае признак оптимальности можно сформулировать так же, как в симплексном методе {для задачи на минимум): опорное решение является оптимальным, еепи для всеХ векторов-условий (клеток таблицы) оценки неположительные