3Основылинейногопрограммирования

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

ПримерызадачЛП.Макроэкономическиелинейныемодели

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

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

и,всвоюочередь,снабжаетдругиеотраслисвоейпродукцией.Крометого,каждаяот-расльвыпускаетпродукцию,котораяпотребляетсявнепроизводственнойсфере(сферепотребления,созданиезапасов).

Допустим,чтодляотраслиiизвестно,чтоa_{ijединиц}продукцииэтойотраслиисполь-зуетсядляпроизводстваединицы(!)продукцииотраслиjиc_{iединиц}продукцииэтойотраслииспользуетсявнепроизводственнойсфере(накопление,потребление).Величинаc_iтакженазываетсявнешнимспросом.Требуетсяопределитьx_i–валовыйобъем(ко-личествоединиц)продукцииотраслиi,i=1,...,n,так,чтобывыполнялосьусловиемежотраслевогобаланса:

_n

^aij^xj^+ci^=xi^,xi^{≥0,i=1,...,n,}

j=1

иливматричнойформе

x−Ax=c,x≥0.

^{ПриведенныесоотношенияназываютсямодельюЛеонтьева.Соотношениеx−Ax=c}

^{можноослабить:x−Ax≥c(вэтомслучаеcопределяетнижнююграницувнешнего}

спроса).СмодельюЛеонтьевасвязанынекоторыезадачиоптимизации.

1)Задачамаксимизациисуммарноговаловоговыпускаприограниченныхтру-довыхресурсах.

Пустьдлявыпускаединицыпродукцииотраслиjтребуетсяt_{jединиц}трудовыхресурсов.Обозначимt=(t₁,...,t_n).ПустьT–общееколичествотрудовыхресурсов,имеющеесявналичии.Тогдамодельзадачимаксимизациисуммарноговаловоговыпускаприограни-ченныхтрудовыхресурсахсостоитвследующем:

_n

^xj^→max,

j=1

^_x−Ax≥c

n

^

_j=1^t_j^x_j^≤T

^x≥0

2)Задачаминимизациитребуемыхтрудовыхресурсовпризаданномуровнесуммарноговаловоговыпуска:

_n

^tj^xj^→min,

j=1

^_x−Ax≥c

n

^

_j=1^x_j^≥V

^x≥0,

гдеV–заданныйуровеньсуммарноговаловоговыпуска.

Микроэкономическиелинейныемодели

Модельоптимальнойпрограммыпредприятия.Предприятиевыпускаетnвидовпродукции.Длявыпускаединицыпродукциивидаjтребуетсяa_{ijединиц}ресурсаi,кото-рыйимеетсявобъемеb_i,i=1,...,m(всегоимеетсяmвидовресурсов).Выпускединицы

продукциивидаjприноситприбыльвобъемеp_j.Требуетсяопределитьпрограммувы-пускапродукцииx=(x₁,...,x_n),гдеx_j–количествовыпускаемойпродукциивидаj,такую,чтовыполненыограничениянаресурсыисуммарнаяприбыльмаксимальна.Со-ответствующаязадачаЛПимеетвид:

n

j=1

_{( n}

p_jxj→max,

_j=1^{aijxj≤bi,i=1,...,m,}

^{xj≥0,j=1,...,n}

Модельраспределенияресурсов.Имеетсяnвидовдеятельностииmвидовресур-сов.Ресурсiимеетсявобъемеb_i,i=1,...,m.Спомощьюединицыi-горесурсаможновыполнитьd_ij-ючастьj-говидадеятельностииприэтомзатратыбудутсоставлятьc_ij.Введемпеременныеx_ij,показывающиекакоеколичестворесурсаiнаправленодлявидадеятельностиj.Задачасостоитвследующем.

m n

^cij^xij^→min,

i=1j=1

m

n

^

^ _i=1^d_ij^x_ij^{=1,j=1,...,n,}

_j=1^xij^≤bi^,i=1,...,m,

^{xij≥0,i=1,...,m,j=1,...,n.}

Модельоптимальнойкупли-продаживалюты.Рассмотримситуацию,когдабро-керосуществляеткуплю-продажувалютысцельюполученияприбылизасчетразницывкурсахвалют.Пустьn–количестводоступныхвалютныхрынков,m–количествоопе-рацийкупли-продажи.Обозначимчерезr_ijколичестводенежныхединицi-говалютногорынка,которыеможнокупить(r_ij>0)либопродать(r_ij<0)врезультатеоперацииjстандартногообъема.Например,припроведенииоперацииномер2стандартногообъема,продавая2доллара,можнокупить1еврои2000бел.рублей.Пустьx_j–объемоперацииj.Вэтомслучаесоответствующиевеличиныr_ijумножаютсянаx_j.Например,продавая

^2x₂^{долларов,можнополучитьx}₂^{еврои2000x}₂^{бел.рублей.}

Рассмотримидеализированнуюситуацию,когдавсеоперациивыполняютсяодновремен-но.Ограничениесостоитвтом,чтоколичествопроданныхденежныхединицнедолжнопревосходитьколичествакупленныхдлякаждоговидавалюты.Задачасостоитвотыс-каниитакихобъемовопераций,чтоколичестводенежныхединицпоодномуизтиповвалют,например,первому,максимально.Соответствующаяматематическаямодельвы-

_{глядитследующимобразом.}

n

j=1

n

r_1jxj→max,

j=1

^rij^xj^{≥0,i=1,...,m.}