Имя материала: Математика в экономике

Автор: Солодовников А.С.

§ 7.1. общая задача оптимизации. линейное программирование. примеры задач

 

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

J[x) -» max (min), х Є X. (7.1)

Определенная таким образом задача называется задачей оптимизации. Множество X называется допустимым множеством данной задачи, а функцияДх) — целевой функцией.

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

x = (Х|, х^,х^,

т. е. является точкой «-мерного арифметического пространства R". Соответственно множество X есть подмножество в R".

 

Очень многое зависит от того, в каком виде задается допустимое

множество X. Во многих случаях X выделяется из R" с помощью системы неравенств (нестрогих):

g (Х,х2, ...,*„)> О . г2(*|.*2>-.*іі)*0 (7.2)

gm(xi,x2, ...,*„)> О

 

гдеg,g2           gm — какие-то заданные функции в R".

Иначе говоря, X есть множество точек (jc,, х2,хп) G R", удовлетворяющих системе неравенств (7.2).

В этом случае задача оптимизации приобретает следующий вид. Даны функция п переменных f(xx, х2,хп) и система неравенств (7.2). Требуется найти max (min)/при условиях (7.2):

/(jC|, дг2,хп) ->   max (min) при условиях (7.2).

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

Задачи подобного рода получили название задачи математического программирования (не следует путать математическое программирование с машинным). При этом функцию / называют целевой функцией, а неравенства g, > 0 (;' = 1, 2,     т) — ограничениями.

В большинстве случаев в число ограничений входят условия неотрицательности переменных:

х{>0,х2>0,...,хп>0

или части переменных, но это, впрочем, не обязательно.

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

ах +а2х2 + ...+а„хп + Ь.

128

Тогда говорят о задаче линейного программирования. Линейное программирование оформилось как отдельный раздел прикладной математики в 40-50-х гг. XX в., когда выяснилось, что целый ряд задач из сферы планирования и управления может быть сформулирован в виде задач линейного программирования. Для решения таких задач разработаны эффективные методы, с одним из которых (так называемым симплекс-методом) мы будем дальше знакомиться. Подсчитано, что в настоящее время примерно80-85\%всех решаемых на практике задач оптимизации относится к задачам линейного программирования.

В дальнейшем, вместо того,чтобы одновременно рассматривать оба типа задач:/(х) -> max и f [х) -» min, мы будем изучать задачи только какого-нибудь одного типа. Такой подход оправдан тем, что всякая задача на максимум сводится к задаче на минимум (и наоборот) путем умножения целевой функции на -I.

Еще раз напомним, что в задаче оптимизации (7.1) множество X называется допустимым. Соответственно любая точка х Є X называется допустимым решением. Допустимое решение, дающее max (min) /, называется оптимальным решением. Неравенства (7.2) называются ограничениями.

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

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

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

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

9-3700 129

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

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

)х+у^0         —балансовое ограничение;

х > 35  — кредитное ограничение;

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

х > 0, у > 0.

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

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

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

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

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

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

Пусть имеются два вида продуктов: Я, и Я2, содержащих питательные вещества А, В, С. В 1 кг продуктов Я, и Я2 содержится определенное количество питательных веществ того или иного вида. Эти сведения представлены в следующей таблице.

 

 

А

В

с

В 1 КГ #|

 

 

с

В 1 КГ #2

а2

ьг

с2

Кроме этих данных нам известны: a, ft, с — ежесуточные потребности организма в А, В, С и s]t s2 — стоимость 1 кг продуктов П, П2. Требуется рассчитать количество хх продукта Я( и количество х2 продукта Я2 так, чтобы обеспечить необходимое количество питательных веществ при минимальных затратах на продукты. Очевидно, общая стоимость продуктов будет/=5|*1 +^2*2-

Общее количество вещества А в обоих видах продуктов равно alxl + а^. Оно должно быть не меньше а: аххх + а^ > а.

Аналогичные неравенства должны выполняться для В и С Таким образом, перед нами задача линейного программирования.

Дана система

0|Х] + а2х2 > а ■ b]Xl+b2x2>b у C|jr, + с2х2 > с

трех линейных неравенств с двумя неизвестными хх,х2 и линейная

ФУНКЦИЯ/= J|JC| + ^2^2-

Среди решений системы (7.3), удовлетворяющих дополнительно условию неотрицательности:

хх>0,х2>0, (7.4)

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

/-» min при условиях (7.3), (7.4).

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

3. Задача об использовании ресурсов. Предприятие имеет в своем распоряжении определенное количество ресурсов: рабочую силу, деньги, сырье, оборудование, производственные ресурсы, площади и т. п. Допустим, например, ресурсы трех видов R{,R2, Л3 имеются в количестве соответственно ЬХ,Ъ2,ЬЪ условных единиц. Предприятие выпускает два вида товаров 7*,, Т2. Причем известно, сколько единиц каждого ресурса требуется для производства единицы каждого товара. Пусть atj — число единиц ресурса Л, (іі = 1, 2, 3), необходимое для производства единицы товара Tj (j = І, 2). Доход, получаемый предприятием от единицы каждого вида товаров, соответственно равен с, с2. Требуется при данных ресурсах выпустить такую комбинацию товаров, при которой доход предприятия оказался бы максимальным.

Обозначим через я, х2 соответственно количество товаров Г,, Т2.

ОчеВИДНО, ДОХОД Предприятия/ = СХ{ + с2х2.

Общее количество ресурса Rx, используемого при выпуске обоих товаров, равно а, ,х, + аХ2х2. Оно не должно превосходить запаса Ьх, т. е. ахххх + аХ2х2<Ьх.

Вообще, количество ресурса Ri (/ = 1, 2, 3), используемого при выпуске обоих товаров, равное aiXxx + аі2х2, не должно превосходить Ь,, т. е. должны выполняться неравенства

aiXxx+ai2x2<bi 0=1,2,3).

Математическая задача об использовании ресурсов состоит в определении значений неизвестных х (, х2, удовлетворяющих условиям:

х,>0,

*2>0, • ахххх + аХ2х2<Ьх, а2ххх+а22х2<Ь2, аъххх+аЪ2х2<Ьг,

и максимизирующих функцию/= сххх + с2х2.

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

Имеются два месторождения Мх, М2 и три потребителя Пх, П2, Я3. Количество угля в М| и М2 соответственно ах и а2. Запросы потребителей Я,, Я2, Я3 пусть будут b{, Ь2, Ьъ. Считаем, что суммарные запасы равны суммарным потребностям: ах + а2 = Ьх + Ь2 + й3 (такое предположение вполне естественно). Наконец, заданы числа Су (Ы, 2;j=,2, 3)( представляющие собой стоимость перевозки тонны угля из М{ в Я,.

Необходимо Определить ШеСТЬ ЧИСеЛ Ххх, Хх2, Xxi, X2X, Х22, Х23, где

Хц — количество угля, предназначенное к отправке из М, к П-. 132

Общее количество угля, вывезенное из Л/|, должно равняться а Отсюда имеем условие

*11 +х2 + х3 = а-Аналогичное условие должно выполняться для My.

х2 + x22 + x2i = al Общее количество угля, доставленное в Я,, должно равняться Ьх. Отсюда:;С| 1 + хг = °-

Аналогично получаем условия:

Х2 + x22 = b2 xxi + x23 = b3.

Предполагаем, что затраты на перевозку прямо пропорциональны

КОЛИЧеСТВу ПереВОЗИМОГО УГЛЯ, Т. Є. ПереВОЗКа ИЗ М{ В IIj СТОИТ СдХу.

Тогда общие затраты по всем перевозкам будут

2 = СххХхх+Сх2Хх2+СхгХ{г + С1хХ2х+С22Х22 + С2уХ2ъ.

Таким образом, приходим к следующей задаче. Дана система

 

х\

+ хХ2 + ххъ

= ах

хг

+ х22 +

= а2

ххх

+ х2

= ьх

х2

+ х22

= Ь2

 

+ хгз

= *3

пяти линейных уравнений с шестью неизвестными и линейная функция z. Требуется среди неотрицательных решений ххх,хХ2, jc,3, *2i> х22, х23 системы (7.5) выбрать такое, при котором функция z Достигает наименьшего значения (минимизируется).

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

Из четырех рассмотренных выше примеров, казалось бы, только первые три подходят под общую схему задач математического программирования. Так, в четвертом примере не все ограничения неравенства; часть из них (а именно (7.5)) являются уравнениями. Однако случай уравнений легко свести к случаю неравенств: достаточно каждое уравнение g(x) = 0 заменить системой из двух неравенств g(x) > 0 и g(x) < 0. Впрочем, сведение уравнений к неравенствам может быть осуществлено и более эффективным способом (см. ниже).

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

Пусть S — система линейных ограничений (т.е. линейных уравнений или нестрогих линейных неравенств) с п переменными

х,, х2,    хп, a fix) — целевая функция вида

fix) = c,jc, + с2х2 + ... + cjc„ + с.

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

fix) -> min при условиях S.

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

х,>0,х2>0,...,*„>(), (7.6)

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

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

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

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

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

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

/= с{Х + с2х2 + ... + спхп + с -> min при условиях S,

где S — заданная система линейных неравенств, включающая (7.6). Пусть т — число нетривиальных неравенств в системе 5. Рассмотрим любое из этих неравенств:

axl+a2x2 + ...+anxn + bz0. (7.7)

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

аіх]+а2х2 + ... + аПхП + Ь = х^

и условием      > 0.

Если подобную замену произвести с каждым из нетривиальных неравенств системы S, то получим новую систему 5|, состоящую из

уравнений, а также условий неотрицательности всех переменных: исходных xitx2,хп, а также дополнительных xn+1,хп+т. Заметим, что дополнительные переменные xn+i, ■■■,хп+т называют обычно балансовыми.

Назовем задачей В задачу/-> min при условиях 5,.

 

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

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

системы (7.2) балансовую переменную х3, для второго — х4, для третьего неравенства — х5, получим каноническую задачу:

/= sxxx + s2x2 -* min при условиях

 

*3>

clxi + с-,х

bX + Ь2х2 -Ь = х4,

2Х2 ~ с ~ х5'

х, >0,х2>0, ...,х5>0.

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

/= -Х| + х2 + х3 - 2х4 -> min при условиях

(7.8)

-2*1 + 3*2+ -*з + *4=1> -*1 + Зх2 + 2*з - х4 = 2, х, >0,х2>0,х3>0,х4>0

— назовем ее задачей В.

Применив к системе из двух уравнений (7.8) метод Гаусса, выделим базис неизвестных:

jx3 = *,-2x2+l,

[х4 = х- х2-

Учитывая эти равенства, можно написать новое выражение для/: /= -х, + х2 + (х, - 2х2 + 1) - 2(Х] - х^ = -2х| + х2 + 1.

Рассмотрим теперь новую задачу линейного программирования, которую назовем задачей А:

/ = -2х| + х2 + 1 -> min при условиях

(7.9)

xj - 2х2+ 1 ^0, Х| -х2>0, х,>0,х2>0.

Если эту стандартную задачу мы захотели бы свести к канонической, то пришлось бы ввести балансовые переменные х3 и х4 и заменить систему (7.9) новой системой

Xj -2х2+ 1 = х3, ■ х, -х2 = х4, (7.10) Х| >0,х2£0,хз>0,х4£0,

но тогда новая задача:

/= -2х| + х2 + 1 -> min при условиях (7.10)

ничем, в сущности, не будет отличаться от исходной задачи В.

Таким образом, задача В свелась к стандартной задаче А с меньшим числом переменных.

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 |