Некоторые общие сведения о линейном программировании

Понятие экономической модели

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

Формализация основных особенностей функционирования экономических объектов позволяет:

1) оценить возможные последствия воздействия на них;

2) оценить их перспективные изменения;

3) использовать полученные оценки в управлении.

Примеры экономических моделей:

- модели экономического роста;

- модели потребительского выбора;

- модели равновесия на товарных и финансовых рынках;

- модели фирмы и многие другие.

-

Задача оптимального планирования является самой важной из задач так называемого линейного программирования (ЛП).

Если сформулировать задачу ЛП без экономической интерпретации, то она такова: найти экстремум линейной функции при линейных ограничениях на переменные.

При этом множество значений переменных, удовлетворяющих всем (линейным) ограничениям задачи, называется допустимым множеством. Допустимое множество представляет собой некоторое тело в линейном числовом пространстве размерности n, равной числу переменных задачи. Линейная функция, экстремум которой ищется, называется целевой функцией.

Сама точка экстремума, если она существует, называется оптимальным решением задачи ЛП, в отличие от любой точки допустимого множества, которая называется просто решением (или допустимым решением) задачи ЛП.

Линейное программирование возникло в СССР. В конце 30-х годов XX в. cоветский экономист и математик Леонид Витальевич Конторович открыл класс этих задач и придумал некоторые частные методы их решения. В 1975 г. фактически за это открытие он был удостоен Нобелевской премии по экономике, что свидетельствует о большой важности задачи ЛП.

С чисто математической точки зрения задачи ЛП интересны тем, что методы нахождения экстремумов с помощью производной здесь не применимы. Действительно, рассмотрим простую задачу ЛП:

Х-1 → max, 0≤ х ≤3

Поскольку производная целевой функции равна 1, то критических точек в исследуемом промежутке нет и найти экстремум по классической схеме нельзя (рис.1). И в самом деле, максимум целевой функции достигается в точке х=3, которая не является внутренней точкой области определения (методы нахождения экстремумов с помощью производной рассматривались еще в школьной программе).

На практике иногда приходится решать такие задачи ЛП, в которых много видов ресурсов (иногда сотни и тысячи) и много видов продукции (такого же порядка). Для решения задач ЛП разработаны мощные математические методы и такие задачи сегодня решают только на компьютере. Самый известный алгоритм решения задач ЛП – это так называемый симплекс-метод, придуманный американским математиком Дж. Данцигом в 1949 г.

Теоретической основой ЛП являются две теоремы (подробнее ЛП изучается в 5 семестре):

1-я основная теорема ЛП.

Задача ЛП имеет оптимальное решение тогда и только тогда, когда целевая функция ограничена на допустимом множестве в направлении экстремума.

Эта теорема не имеет места в более общих ситуациях. Например, функция у=1/х ограничена снизу нулем на множестве (0, +∞), но точки минимума на этом множестве у нее нет.

2-я основная теорема ЛП.

Дата добавления: 2014-01-04