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

 

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

 

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

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

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