Линейные модели в экономике (стр. 1 )

ЛИНЕЙНЫЕ МОДЕЛИ
В ЭКОНОМИКЕ

Лекция 10
ОБЩИЕ СВЕДЕНИЯ О ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

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

10.1. ЗАДАЧА ОБ ИСПОЛЬЗОВАНИИ РЕСУРСОВ

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

Пусть предприятие из m видов ресурсов производит n видов продукции. Пусть для производства одной единицы j-го вида продукции расходуется единиц i-го вида ресурса. Матрица называется технологической.

Пусть – удельная прибыль от реализации одной единицы j-й продукции. Эти удельные прибыли образуют вектор . Тогда произведение есть величина прибыли, полученной при реализации X единиц произведенной продукции, где . Обозначим эту прибыль .

Пусть – число единиц i-го ресурса, имеющегося в распоряжении предприятия. Тогда необходимость учитывать ограниченность запасов ресурсов при составлении планов производства выражается системой неравенств:

, i = 1, …, m. (10.1)

Требуется при данных ресурсах выпустить такую комбинацию товаров, при которой доход предприятия оказался бы максимальным. Иначе говоря, требуется найти наибольшее значение функции при условиях (10.1). Определенная таким образом задача называется задачей оптимизации. Ее записывают так:

, (10.2)

(10.3)

, , …, . (10.4)

Функция называется целевой функцией.

Определение. Допустимым решением (планом) данной задачи называется любой вектор Х, удовлетворяющий системе ограничений (10.3) и условиям неотрицательности (10.4).

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

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

10.2. ОБЩАЯ ЗАДАЧА
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Сформулируем в общем виде задачу линейного программирования: найти экстремум линейной функции при линейных же ограничениях на переменные.

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

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

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

Прежде чем сформулировать вторую теорему, заметим, что допустимое множество, на котором ищется экстремум, – это многогранное тело (при – многоугольник, при – многогранник в трехмерном пространстве). Вершины этого многогранного тела называются угловыми точками.

Теорема 10.2. Если экстремум целевой функции в задаче линейного программирования достигается, то он достигается в некоторой угловой точке допустимого множества.

Заметим, что угловых точек – конечное число. Симплекс-метод представляет собой направленный перебор угловых точек допустимого множества.

Рассмотрим решение задачи линейного программирования с двумя переменными графическим методом.

Пример 10.1. Решить задачу линейного программирования:

,

, .

Решение. На плоскости возьмем прямоугольную систему координат (рис. 10.1).

Рис. 10.1

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

Аналогично строим прямые и и выбираем соответствующие полуплоскости.

Учитываем еще условия неотрицательности , .

Пересечение всех пяти полуплоскостей дает искомое допустимое множество – пятиугольник OABCD.

Строим линию уровня , например, при : . Перемещаем линию уровня в направлении нормали. Последняя точка, по которой линия уровня еще пересекает допустимое множество, и будет точкой максимума. В нашем случае это точка С. Ее координаты найдем, решая совместно уравнения прямых, которые пересекаются в точке С:

получаем , . Вычисляем .

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

10.3. ЭЛЕМЕНТЫ ТЕОРИИ ДВОЙСТВЕННОСТИ

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

Рассмотрим задачу использования ресурсов. Пусть для изготовления n видов продукции , , …, используют m видов ресурсов , , …, (это могут быть различные виды сырья, электроэнергия, полуфабрикаты и т. п.). Объем каждого вида ресурсов известен; иначе говоря, известен вектор запасов ресурсов . Известна также норма расхода i-го ресурса на производство единицы j-го вида продукции, т. е. известна технологическая матрица , i = 1, 2, …, m; j = 1, 2, …, n. Кроме того, известна прибыль, получаемая от реализации единицы каждого вида продукции, т. е. известен вектор прибылей . (Здесь вектор B – вектор-столбец, а вектор С – вектор-строка.)