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

++b=0

где , что и требовалось доказать.

Глава 2. Линейное программирование

.1 Общая задача оптимизации. Линейное программирование

На практике постоянно встречаются такие ситуации, когда достичь

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

f(x) max (min), хХ (1)

Определенная таким образом задача называется задачей оптимизации.

Множество Х называется допустимым множеством данной задачи, а функция f(x) - целевой функцией.

В большинстве случаев точка х задается набором из нескольких чисел:

х=(, ,… ,)

Очень многое зависит от того, в каком виде задается допустимое множество Х. Во многих случаях Х выделяется из  с помощью системы неравенств:

(2)

где , ,… ,  - заданные функции в .

Иначе говоря, Х есть множество точек (, ,… ,),

удовлетворяющих системе неравенств (2).

В этом случае задача оптимизации примет вид:

Даны функция n переменных f(, ,… ,) и система неравенств (2). Требуется найти max (min) f(x) при условиях (2):

f(, ,… ,) max (min) при условиях (2).

Понятно, что следует найти не только само значение max (min) f, но и

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

Задачи подобного рода получили название задачи математического

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

  … ,

или части переменных.

В зависимости от характера функций f, , … ,  различают разные

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

+…++b=0.

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

.        Задача о банке (пример из книги Дж. Синки «Управление финансами в коммерческом банке»)

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

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

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

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

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

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

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

)        х , у

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

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

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

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

2. Задача о диете.

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

Рассмотрим простую математическую модель этой задачи.

Пусть имеется два вида продуктов: П₁ и П₂, содержащих питательные вещества А, В, С. Известно, сколько питательного вещества того или иного вида содержится в 1 кг продуктов П₁ и П₂: эти сведения указаны в таблице

Кроме этих данных, нам известны: а, b, с - ежесуточные потребности организма в А, В, С (соответственно) и s₁, s₂ - стоимости 1 кг продуктов П₁и П₂ (соответственно). Требуется рассчитать количество х₁ продукта П₁ и количество х₂ продукта П₂ так, чтобы обеспечить необходимое количество питательных веществ при минимальных затратах на продукты.

Так как s₁- стоимость одного кг продукта П₁, то x₁× s₁ - стоимость х₁ кг продукта П₁;

аналогично х₂s₂ - стоимость х₂ кг продукта П₂, следовательно общая стоимость продуктов, которую надо минимизировать будет f (х)= s_l х₁ + s₂ х₂.

3. Задача об использовании ресурсов.

Предприятие имеет в своем распоряжении определенное количество ресурсов разного рода: рабочую силу, деньги, сырье, оборудование, производственные ресурсы, площади и т.п. Допустим, например, ресурсы трех видов R₁, R₂, R₃ имеются в количестве соответственно b₁, b₂, b₃ условных единиц. Предприятие выпускает два вида товаров T₁, T₂, причем известно, сколько единиц каждого ресурса требуется для производства одной единицы каждого товара. Пусть а_ij - число единиц ресурса Ri(i =1, 2, 3), необходимое для производства единицы товара Tj(j= 1, 2).

Известно, что доход, получаемый предприятием от единицы каждого товаров, соответственно равен с₁, с₂. Требуется при данных ресурсах выпустить такую комбинацию товаров, при которой доход предприятия оказался бы максимальным. Обозначим через х₁, х₂ соответственно количества товаров Т₁,Т₂. Очевидно, доход предприятия f = с₁x₁ +с₂х₂.

4. Транспортная задача.

Уголь, добываемый в нескольких месторождениях, отправляется ряду потребителей: заводам, электростанциям и т.п. Известно, сколько угля добывается в каждом месторождений, скажем, за месяц, и сколько его требуется на тот же срок любому из потребителей. Известны расстояния между месторождениями и потребителями, а также условия сообщения между ними; учитывая эти данные, можно подсчитать во что обходится перевозка каждой тонны угля из любого месторождения в любой пункт потребления. Требуется при этих условиях спланировать перевозки угля таким образом, чтобы затраты на них были минимальными.

Примем для простоты, что имеются лишь два месторождения М,,М₂ и три потребителя П₁, П ₂, П ₃. Количество угля в М₁ и в М₂ равно соответственно a₁ и а₂; запросы потребителей П₁, П₂, П₃ пусть будут соответственно b₁, b₂, b₃. Будем считать, что суммарные запасы равны суммарным потребностям: a₁ +а₂ = b₁ +b₂ + b₃ (такое предположение вполне естественно). Наконец, заданы числа с_ij (i =1, 2, j= 1,2,3) - стоимости перевозки тонны угля из M_i в П_j. Задача состоит в нахождении шести чисел х₁₁, x₁₂, x₁₃, x₂₁, x₂₂, x₂₃, где x_ij - количество угля, предназначенное к отправке из М_i в П j.

Для удобства обозрения составим такую таблицу:

Дадим теперь общую формулировку задачи линейного программирования.

Пусть S - система линейных ограничений (т. е. линейных уравнений или нестрогих линейных неравенств) с n переменными , ,… ,, а f(х) - целевая функция вида:

+…++с.

Требуется решить задачу

f(x) min при условиях S.

Обычно система S включает в себя условия неотрицательности всех переменных:

  … , , (3)

что вытекает из реального экономического смысла чисел , ,… ,. Будем называть эти условия тривиальными ограничениями.

Наиболее часто встречаются две разновидности задачи линейного программирования.

.        Каноническая задача линейного программирования.

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

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

Это означает, что система S состоит только из неравенств, в число которых входят тривиальные ограничения (3). Примером могут служить задачи о банке, диете, использовании ресурсов.

Указанные две разновидности сводятся одна к другой. Покажем сначала, как свести стандартную задачу к канонической.

Пусть имеется стандартная задача линейного программирования (задача А):

+…++с min при условиях S,

где S- заданная система линейных неравенств, включающая (3). Обозначим число нетривиальных неравенств в системе S через т и рассмотрим любое из них:

+…++b0. (4)

Введем новую дополнительную переменную и заменим неравенство (4) двумя ограничениями: уравнением

+…++b=

и условием 0.

Если указанную замену произвести с каждым нетривиальным неравенством системы S, то получим новую систему , состоящую из уравнений, а также условий неотрицательности всех переменных: исходных , ,…,, а также дополнительных , ... , . Отметим, что дополнительные переменные , ... ,  обычно называют балансовыми.

Задачу   min при условиях S, назовем задачей В.

Легко убедиться в эквивалентности задач А и В: любое оптимальное решение задачи А дает оптимальное решение задачи В, если к значениям переменных , ,…, добавить значения балансовых переменных. Обратно, любое оптимальное решение задачи В, если отбросить значения балансовых переменных, дает оптимальное решение задачи А.