Курсовая работа (т): Применение аналитической геометрии в экономике

2.2 Геометрия задачи линейного программирования

Рассмотрим задачу линейного программирования по отысканию максимума (или минимума) линейной функции f(x) = (с, х) на допустимом множестве X, заданном с помощью системы S линейных ограничений (уравнений или нестрогих неравенств).

Напомним, что множество Х , заданное с помощью линейных ограничений в называют выпуклой многогранной областью в . Таким образом, геометрический смысл задачи линейного программирования состоит в отыскании максимума (минимума) заданной линейной функции f(x) на заданном выпуклом множестве X

Будем говорить, что целевая функция в задаче линейного программирования ограничена, если в задаче на максимум целевая функция ограничена на допустимом множестве сверху, а в задаче на минимум - снизу.

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

Теорема 1.

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

При исследовании задачи линейного программирования важную роль играет понятие угловой точки. Напомним, что точка X называется угловой точкой множества X, если она не является внутренней точкой ни для какого отрезка АВ, целиком содержащегося в X.

Теорема 2.

Если в задаче линейного программирования f(x) max(min) при условии хX допустимое множество X имеет хотя бы одну угловую точку, а целевая функция f(x) ограничена, то угловая точка X, в которой f(x) принимает наибольшее (наименьшее) значение среди всех угловых точек X, является оптимальным решением данной задачи.

Из теоремы 2 вытекает, что задачу линейного программирования с

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

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

Полезна также следующая лемма (без доказательства).

Лемма 1.

Пусть X - множество всех оптимальных решений задачи линейного программирования f(x) = (с, х) max при условии х X. Тогда всякая угловая точка множества X является угловой точкой допустимого множества.

2.3 Строение множества оптимальных решений

Напомним, что допустимое ограниченное множество X в задаче линейного программирования является выпуклым многогранником. Имеет место следующая лемма о строении выпуклых многогранников.

Лемма 1.

Выпуклый многогранник совпадает с выпуклой оболочкой своих угловых точек.

Покажем, что справедлива следующая теорема о строении множества X

Теорема 1.

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

Доказательство.

В силу ограниченности X найдется такое число М, что для любой точки хX все ее координаты по модулю не превосходят М: ||< М, ||< М, ... , ||< М. Пусть f(x) = (с, х) - целевая функция, а С = max{ ||, ||, ... ,|| } - наибольшее значение модуля ее коэффициентов. Имеем неравенство:

Значит, f(x) ограничена и сверху, и снизу на X. По теореме 1 из параграфа 2.2 имеется хотя бы одно оптимальное решение, т.е. задача линейного программирования разрешима. Пусть - множество всех оптимальных решений. Так как  подмножество X, то - ограниченное множество. По лемме 1 множество совпадает с выпуклой оболочкой своих угловых точек.

По лемме 1 из параграфа 2.2. угловые точки являются и угловыми точками множества X.

Теорема доказана.

2.4 Графический метод решения задачи линейного программирования при малом числе переменных

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

Пусть область допустимых решений X задается системой неравенств вида:

а целевая функция f =  Требуется найти максимум (или минимум) f на множестве X, а также точку, в которой достигается этот максимум (или минимум).

При описании графического метода используется понятие линии

уровня: линией уровня функции f (х, у) называется множество всех точек

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

Графический метод состоит в следующем.

. Строится множество X всех допустимых решений.

. Если X пустое множество, то задача не имеет решения.

. Если множество Х не пусто , то рассматриваются прямые уровня f =  при монотонном изменении  от - до . При увеличении α прямая f =  смещается параллельно в направлении вектора . Если А - первая точка встречи прямой уровня с областью X, f (А)= , то прямая уровня f (х)=  при  <  не имеет общих точек с X. Значит, что  = minf на X. Аналогично, если А - последняя точка пересечения линии уровня с X, то

 (А) = max f на X.

Если первой точки пересечения линии уровня с X не существует, т.е. при всех  из некоторого промежутка вида [-,] прямая f =  пересекает X, то min f = - на X, и задача на минимум не имеет решения.

Таким образом, из чертежа всегда видно, разрешима задача или нет. Из чертежа также видно, имеются ли у допустимого множества X вершины. Отметим, что отсутствие вершины - явление редкое. Непустое допустимое множество X без вершин может быть только двух видов:

) X - полуплоскость;

) Х- область, ограниченная двумя параллельными прямыми.

Если у X имеется хотя бы одна вершина, то при ограниченной целевой функции оптимальное значение можно найти методом перебора вершин. Для вычисления целевой функции в некоторой вершине V допустимого множества X необходимо знать точное значение ее координат. Для определения координат вершины V решаем систему линейных уравнений вида:

где i и j - номера прямых, ограничивающих область X, на пересечении которых находится вершина V.

При использовании графического метода можно избежать полного перебора вершин. Действительно, если из чертежа видно, что А - единственная первая (или последняя) точка пересечения линии уровня с X, то не нужно вычислять координаты других вершин, так как А - единственное оптимальное решение. В некоторых случаях из чертежа не ясно, в какой именно точке линия уровня пересекает в первый раз допустимое множество X. В этом случае нужно найти координаты всех "подозрительных" на оптимальность вершин, вычислить для указанных вершин их значения целевой функции и выбрать из них вершины с оптимальным значением. Заметим, что могут быть две оптимальные вершины А и В. Тогда множество всех оптимальных решений  - весь отрезок АВ.

Пусть  = maxf (или  = minf) - оптимальное значение f на множестве X. Множество  - подмножество линии уровня f = , причем множество выпукло как пересечение выпуклых множеств. Поэтому возможны лишь следующие случаи:

а) - точка на прямой уровня f =;

б) - отрезок на прямой уровня f =;

в) - луч, лежащий на прямой f =;

г) совпадает с прямой уровня f =.

Пример 1.

Задача о банке.

Пусть собственные средства в банке в сумме с депозитами составляют 100 млн. долл. Часть этих средств, но не менее 35 млн. долл. должна быть размещена в кредитах. Кредиты являются неликвидными активами банка, так как в случае непредвиденной потребности в наличности обратить кредиты в деньги без существенных потерь невозможно.

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

Пусть х - средства (млн. долл.), размещенные в кредитах, у - средства, вложенные в ценные бумаги.

Имеем следующую систему линейных ограничений:

)        х + у 100 - балансовое ограничение;

)        х  35 -кредитное ограничение;

)        у  0,3(х + у) - ликвидное ограничение

)        х , у

Цель банка состоит в том, чтобы получит максимальную прибыль от

кредитов и ценных бумаг:

f =  +   max при условиях 1) - 4)

где  - доходность кредитов,  - доходность ценных бумаг.

Так как кредиты менее ликвидны, чем ценные бумаги, то обычно . Мы пришли к задаче линейного программирования с ограничениями 1) - 4) и целевой функцией f, которую требуется максимизировать.

Решение

рис. 1

Областью решений указанных неравенств будет треугольник ABC, изображенный на рис. 1. Построим вектор  и прямую уровня, перпендикулярную вектору  и проходящую через начало координат. Перемещая эту прямую параллельно в направлении вектора , найдем последнюю точку пересечения прямой уровня и допустимого множества X. Это будет точка С и ее координаты получаются при решении следующей системы линейных уравнений:

Итак, оптимальный портфель активов (точка максимума) есть

 ()= (70;30). Максимальная прибыль составит

Пример 2.

Требуется максимизировать линейную форму при ограничениях:

Решение.

рис. 2

Заменяя знаки неравенств на знаки точных равенств, построим область решений по уравнениям прямых:

(рис. 2).

Областью решений неравенств является треугольник MNP. Построим

вектор  = (2;2). Тогда линия уровня при выходе из треугольника решений пройдет через точку Р(3,  ), а значит в точке Р линейная функция  принимает наибольшее значение, т.е. максимизируется

Случай трех переменных

Для функции f() аналогом линии уровня является поверхность

уровня, т.е. множество всех точек трехмерного пространства , в которых функция f() принимает определенное значение. Для функции вида:

 =++