Экономико-математическое моделирование в химии и экологии: Учебно-методическое пособие

М И Н И СТ Е РСТ В О О Б РА ЗО В А Н И Я РО ССИ Й СК О Й Ф Е Д Е РА Ц И И В О РО Н Е Ж СК И Й ГО СУ Д А РСТ В Е Е Н Ы Й У Н И В Е РСИ Т Е Т

Э К О НО М И К О – М А Т Е М А Т И Ч Е С К О Е М О Д Е Л И РО В А НИ Е В Х И М И И и Э К О Л О ГИ И П особие для студентов С пециальность «Х имия »011000

В О РО НЕ Ж 2003

2

Утверж денонауч но-методич еск им советом химич еск огоф ак ультета21 ноя бря 2003 г. ( проток ол№ 5)

С оставители: Б уты рск ая Е .В ., В асильеваВ .И .

П особие подготовленонак аф едре аналитич еск ой химии химич еск ого ф ак ультетаВ оронеж ск огогосударственног оуниверситета. Рек омендуется для студентов4 к урсад/охимич еск огоф ак ультета.

3

В аж нейш ей задач ей химич еск ого производства я вля ется получ ение мак симальны х прибы лей при эф ф ек тивном использовании имею щ ихся ресурсов и минимальном вы бросе в ок руж аю щ ую среду вредны х химич еск их вещ еств, а так ж е к онтроль соответствия этоговы броса установленны м нормам. С математич еск ой точ к и зрения реш ение так ой задач и сводится к оты ск анию эк стремума нек оторой ф унк ции при налич ии ог ранич ений. П роблема приня тия оптимальны х реш ений при управлении производственны ми процессами привела к созданию специальны х методов, к оторы е приня то объ единя ть под названием «исследование операций». И с с ледо в ан и е о п ераци й – науч ная дисциплина, разрабаты ваю щ ая и применя ю щ ая математич еск ие методы для к олич ественног о обоснования принимаемы х реш ений по орг анизации управления . О дним из основны х методов этой дисциплины я вля ется математич еск ое моделирование. П ри математич еск ом моделировании эф ф ек тивность работы предприя тия описы вается нек оторой ф унк цией Z, назы ваемой ф унк цией цели, к оторую нуж но мак симизировать (прибы ль) или минимизировать (суммарны е затраты ). Функ ция цели зависит от ря да различ ны х переменны х: x1 , x 2 ,L x n , т.е. имеет вид Z ( x1 , x 2 ,L xn ) . К роме этого работа предприя тия имеет ря д ог ранич ений: например, расход сы рья не мож ет превы ш ать запасов сы рья , вы брос вредны х вещ еств не мож ет превы ш ать П Д К и др., к оторы е записы ваю тся в виде системы неравенств: ϕ i ( x1 , x2 ,L xn ) ≤ b i , i = 1, 2,Lm . В общ ем случ ае математич еск ая постановк а задач и оптимизации планирования ф ормулируется следую щ им образом: най ти переменны е x1 , x2 ,L xn , обращ аю щ ие вмак симум (минимум) целевую ф унк цию , т.е. Z ( x1, x2 ,L x n ) → max и удовлетворя ю щ ие системе неравенств

ϕ i ( x1 , x2 ,L xn ) ≤ b i , i = 1, 2,Lm Наиболее разработанны м я вля ется метод линейног о программирования . Л и н ейн о е п ро грам м и ро в ан и е – раздел математик и, в к отором изуч аю т методы реш ения задач на оты ск ание эк стремума (мак симума или минимума) линейной ф унк ции при налич ии огранич ений в виде линей ны х уравнений или линейны х неравенств. В егорамк и ук лады вается ш ирок ий к руг задач : 1. Задач аобиспользовании ресурсов(задач апланирования производства); 2. Задач а составления рациона (задач и о диете, задач и о смеся х, задач и о балансе питательны х вещ естввпродук тах питания ); 3. Задач и об использовании мощ ностей (задач аозаг рузк е оборудования ); 4. Т ранспортная задач а (обеспеч ение предприя тия сы рьем при минимальны х расходах наперевозк и); 5. Задач аовы бороч ном к онтроле продук ции; и друг ие.

4

Задачао распределении ресурсов Рассмотрим п ро с т ейш у ю задач у о распределении ресурсов. П остановк а так ой задач и зак лю ч ается в следую щ ем: химич еск ое предприя тие вы пуск ает два вида продук ции А и В , используя при этом сы рье трех типов: 1,2,3. На изготовление единицы изделия А требуется затратить а 1 единиц сы рья 1 вида, а2 единиц сы рья 2 вида, а3 единиц сы рья 3 вида. На изготовление единицы изделия В требуется затратить b1 единиц сы рья 1 вида, b2 единиц сы рья 2 вида, b3 единиц сы рья 3 вида. П роизводство обеспеч ено сы рьем к аж дого вида в к олич естве р1 , р2, р3 . П ри производстве единицы продук ции А вы брасы вается в ок руж аю щ ую среду α1 единиц вредноговещ ества 1 и α 2 вредноговещ ества2, а при производстве единицы продук ции В − β1 единиц вредноговещ ества 1 и β 2 вредного вещ ества 2, предельно допустимы е вы бросы (П Д В ) равны δ1 и δ 2 . П рибы ль от единицы изделия А составля ет с 1 ед., а от единицы изделия В – с 2 ед. Необходимо составить так ой план вы пуск а продук ции А и В , ч тобы прибы ль бы ла мак симальной, а вы бросы не превы ш али П Д В . Запиш ем данны е задач и ввиде эк ономич еск ой таблицы

Т ип сы рья

Нормы сы рья наединицу продук ции

Запасы сы рья

А

В

1

а1

b1

P1

2

а1

b1

P2

3

а1

b1

P3

Т ип вредного вещ ества 1 2 П рибы ль на единицу продук ции

В ы бросы наединицупродук ции

α1 α2

β1 β2

c1

c2

П редельно допустимы е вы бросы δ1 δ2

С оставим эк ономик о-математич еск ую модель задач и. О бознач им х1, х2 – объ емы вы пуск аемой продук ции А и В соответственно. Т огда

5

F

( х1, х2 ) = c1 х1

+ c2 х2 à max, т.к . прибы ль долж набы ть мак симальной .

П ри огранич ения х a1 х1 + b 1 х2 ≤ p1 (1)

т.к . расход сы рья не долж ен

a2 х1 + b 2 х2 ≤ p 2 a3 х1 + b 3 х2 ≤ p3

превы ш ать запасовсы рья

α 1 х1 + β 1 х2 ≤ δ 1 α 2 х1 + β 2 х2 ≤ δ 2

так к ак вы брос вредны х

x1 , x2 ≥ 0

вещ ествне долж енпревы ш ать ПДВ.

Задач а состоит в том, ч тобы найти так ие неотрицательны е х1 и х 2, ч тобы они удовлетворя ли системе ог ранич ений (1) и обеспеч ивали мак симальное знач ение ф унк ции F. Функ ция F назы вается фу н кци ей цели . И ф унк ция цели и система ог ранич ений я вля ю тся линейны ми ф унк ция ми. Задач а о распределении ресурсов мож ет бы ть реш ена тремя методами : геометрич еск ий метод, симплек сны й метод с использованием симплек сны х таблиц, алгебро-симплек с метод, или пош аговы й метод. Рассмотрим геометрич еск ий метод реш ения задач и линейногопрограммирования нак онк ретном примере. Геометрическийметод решения задачи линейног о прог раммирования В общ ем случ ае переменны е в ф унк цию цели могут входить с разны ми знак ами, а неравенства–огранич ения мог ут содерж ать знак и к ак ≤ , так и ≥ . П усть необходимограф ич еск им методом реш ить следую щ ую задач у линейного программирования : найти мак симум и минимум ф унк ции

F(x ) = 2 x1 − x 2 П ри огранич ения х - 2 x1 + x2 ≤ 6 (1) 3 x1 + 2x2 ≤ 26 (2) x1 - 2 x2 ≤ 6 (3) 2 x1 + x2 ≥ 2 (4) xi ≥ 0 П остроим на плоск ости x10x2 многоугольник реш ений. Д ля этого построим пря мы е - 2 x1 + x2 = 6 ; 3 x1 + 2x2 = 26 ; x1 - 2 x2 = 6 ; 2 x1 + x2 = 2. ( П ря мую строим подвум точ к ам, ч астоудобновзя ть точ к и , леж ащ ие наося х к оординат, например, для пря мой -2 x1 + x2 = 6 этоточ к и (x1=0 ; x2= 6 ) и (x2 =0; x1 = − 3 )). К аж дая из этих пря мы х разбивает плоск ость на две полуплоск ости, в одной из к оторы х неравенство вы полня ется , а в друг ой – нет. Д ля вы бора нуж ной полуплоск ости подставим в к аж дое из неравенств к оординаты нач ала к оординат. Е сли при этом получ им верное неравенство, то нуж ная полуплоск ость содерж ит нач алок оординат, впротивном случ ае – не содерж ит. П олуплоск ость–реш ение обознач им стрелк ами. Например, для пря мой -2 x1 + x2

6

= 6, из системы огранич ений получ аем 0 < 6 - верно, следовательно, полуплоск ость–реш ение содерж ит нач ало к оординат (аналог ич нодля друг их пря мы х). М ногоугольник реш ений - мног оугольник А В С DЕ F (рис.1). В к аж дой ег о точ к е вы полнены все огранич ения на переменны е, задаваемы е системой ог ранич ений. М ож нопок азать, ч тоф унк ция цели принимает свое наибольш ее и наименьш ее знач ение либо при знач ения х х1 и х2 , я вля ю щ ихся к оординатами верш инданногомног оугольник а, т.е. в одной из точ ек А ,В ,С ,D, E, F, либо, на одной из сторон этого мног оугольник а. К ак ж е найти нуж ную верш ину? С троим век тор–градиент целевой ф унк ции r  ∂F ∂F  g= ;  = {2, − 1 }. x x ∂ ∂  1 2 Л ю бая линия , перпендик уля рная этому век тору, я вля ется линией уровня целевой ф унк ции ( линией, на к оторой знач ение целевой ф унк ции постоя нно). Например, пря мая 2 x1 - x2 =0, изображ енная пунк тиром, я вля ется линией, в к аж дой точ к е к оторой знач ение целевой ф унк ции равнонулю . X2

С

(1) (2) 6 В

(4)

2 А 1 E 0

2 х1 − х2 = 0

-1

1

D (3)

F 2

3

4

5

6

7

8

X1

r g

Рис.1 В ек тор-г радиент пок азы вает направление роста ф унк ции F. П ередвигая линию r уровня в направлении век тора g , будем увелич ивать целевую ф унк цию .

7 r П ередвигая линию уровня в направлении, противополож ном g , будем уменьш ать целевую ф унк цию . П еремещ аем пунк тирную линию в r направлении g , при этом точ к а вы хода пунк тирной линии из многоугольник а реш ений – точ к а D, следовательно, в точ к е D целевая ф унк ция имеет мак симум, r перемещ аем пунк тирную линию в направлении противополож ном g , при этом в последню ю оч ередь попадаем на пря мую В C, линия уровня сливается с пря мой А В , следовательно, в лю бой точ к е линии В C целевая ф унк ция имеет минимум на данной системе огранич ений. К оординаты точ к и D найдем из реш ения системы

3х 1 + 2 х 2 = 26 отсю дах1 = 8 , х2 = 1  х − 2 х = 6  1 2 М ак симальное знач ение ф унк ции равно

Fmax = 2 ⋅ 8 − 1 = 17 при x1 = 8 , x2 = 1 . М инимальное знач ение ф унк ции равно Fmin= - 6 влю бой точ к е пря мой А В . О б щ ая задача линейног о прог раммирования В о бщем виде задач а линейного программирования ф ормулируется следую щ им образом: Д анасистемаm линейны х уравнений и неравенствс n переменны ми  n  ∑ aij x j ≤ bi (i = 1,2,..., k )  j =1 n  ∑ aij x j = bi (i = k + 1, k + 2,..., m ) j x j ≥ 0 ( j = 1,2,..., l; l ≤ n). и линей ная ф унк ция F = c1 x1 + c2 x2 + L + cn x n Необходимо найти так ое реш ение системы X = ( x1 , x2 ,L xn ) , при к отором линейная ф унк ция F (ф унк ция цели) принимает оптимальное (т.е. мак симальное или минимальное ) знач ение. Е сли система огранич ений состоит лиш ь из одних неравенств, а все переменны е неотрицательны , тотак ая задач а линейного программирования назы вается с т ан дарт н о й; если система ог ранич ений состоит из одних уравнений, тозадач а назы вается кан о н и чес ко й. Л ю бая задач а линейног о программирования мож ет бы ть сведена к к анонич еск ой, стандартной или общ ей задач е. До п у с т и м ым и ли о п о рн ым

8

реш ением назы вается реш ение, при к отором все переменны е неотрицательны . Д ля к анонич еск ой задач и множ ество всех допустимы х реш ений задач и представля ет вы пук лы й многогранник , к оторы й назы вается мног огранник ом реш ений. Е сли задач а линейного программирования имеет оптимальное реш ение, то линей ная ф унк ция F принимает мак симальное (минимальное ) знач ение в одной из угловы х точ ек многог ранник а реш ений. К аж дому допустимому базисному реш ению задач и линейного программирования соответствует уг ловая точ к а многог ранник а реш ений и наоборот, к аж дой уг ловой точ к е мног огранник а реш ений соответствует допустимое базисное реш ение. Т ак им образом, оптимум линейной ф унк ции задач и линейног опрог раммирования следует иск ать среди к онеч ногоч исла ее допустимы х базисны х реш ений . О дин из путей реш ения задач и линейного программирования – перебрать к онеч ное ч ислодопустимы х базисны х реш ений системы огранич ений и вы брать среди них то, на к отором ф унк ция цели принимает оптимальное реш ение. Геометрич еск и это соответствует перебору всех уг ловы х точ ек мног огранник а реш ений . Т ак ой перебор в к онце к онцов приведет к оптимальному реш ению ( если оно сущ ествует ), однак о его прак тич еск ое осущ ествление свя зано с ог ромны ми трудностя ми, так к ак для реальны х задач ч ислодопустимы х базисны х реш ений хотя и к онеч но, номож ет бы ть ч резвы ч айновелик о. Ч исло перебираемы х допустимы х базисны х реш ений мож но сок ратить, если проводить перебор не беспоря доч но, а с уч етом изменений линейной ф унк ции, т.е. добивая сь того, ч тобы к аж дое следую щ ее реш ение бы лоближ е к оптимуму, ч ем преды дущ ее. И дея последовательногоулуч ш ения реш ения лег ла в основу универсальногометодареш ения задач линейногопрограммирования – симплек сного метода. Д ля реализации симплек сного метода необходимо освоить три основны х элемента: - способ определения к ак ог о–либо первонач альног о допустимого базисного реш ения задач и; - правилопереходак луч ш ему( точ нее, не худш ему) реш ению ; - к ритерий проверк и оптимальности найденногореш ения . Кри т ери й о п т и м альн о с т и реш ения при оты ск ании мак симума линейной ф унк ции: если в вы раж ении линейной ф унк ции цели ч ерез неосновны е переменны е отсутствую т полож ительны е к оэф ф ициенты при неосновны х переменны х, то реш ение оптимально. К ритерий оптимальности реш ения при оты ск ании минимума линейной ф унк ции: если в вы раж ении линейной ф унк ции ч ерез неосновны е переменны е отсутствую т отрицательны е к оэф ф ициенты при неосновны х переменны х, тореш ение оптимально. Рассмотрим реш ение задач и линейного программирования с использованием симплек сны х таблиц на к онк ретном примере.

9

Симплекс-методс использованием таб лиц Найти мак симум ф унк ции F = 6 х1 - 2 х2 + 4 х3 х1 + х2 + х 3 ≤ 2 2 х1 + х2 + х3 ≤ 2 х1 ,х2 ,х3 , ≥ 0 Запиш ем задач у в к анонич еск ом виде, т.е. в виде, к огда система огранич ений записана в виде равенств. Д ля этоговведем дополнительны е неотрицательны е переменны е х4, х5 , и введем их в систему ог ранич ений, ч тобы онаиз системы неравенствпревратилась всистемуравенств. Задач апримет вид F = 6 х1 - 2 х2+ 4 х 3àmax х1 + х2 + х 3 + х4 = 2 2 х1 + х2 + х3 + х5 = 2 х1 ,х2 ,х3 , ≥ 0 В ы бираем основны е, или базисны е переменны е, и неосновны е переменны е. К ак этосделать? С нач ала определим ч ислоосновны х (базисны х) переменны х. О но равно ч ислу независимы х уравнений – ог ранич ений. У нас этих уравнений – два. П оэтому ч ислоосновны х ( базисны х ) переменны х равнодвум. Л ю бы е две переменны е мож нопробовать вы брать за базисны е, например, х1 и х 5, или х1 и х2 и т.д. О днак о к оэф ф ициенты при основны х переменны х долж ны образовы вать отлич ны й от нуля определитель. Ч асто удобно за основны е (базисны е) переменны е вы брать дополнительны е переменны е, к оторы е мы ввели в систему ог ранич ений, ч тобы она превратилась в систему равенств. В ы берем х4 , х5 за основны е переменны е, а х1 , х2 , х3 - за неосновны е переменны е. Нач альны й базис не я вля ется оптимальны м,так к ак переменны е х 1 и х3 входя т в F сознак ом + и, увелич ивая лю бую из этих переменны х, мож но увелич ить F. Запиш ем поданны м задач и симплек с–таблицу 1, к оторая строится из к оэф ф ициентовпри неизвестны х системы огранич ений и ф унк ции цели: С и м п лекс -т абли ца 1 С вободны й Б азис ч лен Х

Х

1

Х

2

Х

3

Х

4

Х

5

2

1

1

1

1

0

2

2

1

1

0

1

0

-6

2

-4

0

0

4

Х 5 F

П оследня я строк а состоит из к оэф ф ициентов ф унк ции цели с противополож ны м знак ом. П оэтому к ритерием оптимальности плана при

10

нахож дении мак симума ф унк ции F я вля ется отсутствие в последней строк е отрицательны х элементов, при нахож дении минимума ф унк ции F в последней строк е не долж нобы ть полож ительны х элементов. Т ак к ак последня я строк а содерж ит отрицательны е элементы , то данное реш ение не оптимально. В ы берем столбец Х 1 c мак симальной отрицательной оценк ой – 6 за разреш аю щ ий и вы ч ислим отнош ение свободны х ч ленов к полож ительны м элементам этого столбца: 2/2, 2/1. И з них наименьш ее 2/2. С оответствую щ ая строк а х5 - разреш аю щ ая . Разреш аю щ ий элемент 2. Д ля получ ения симплек с таблицы 2 используем правилопря моуг ольник а, согласно к оторому элемент в новой симплек с таблице вы ч исля ется следую щ им образом: все элементы к лю ч евого столбца равны 0 за иск лю ч ением разреш аю щ его, к оторы й равен 1 , все элементы к лю ч евой строк и получ аю тся их делением на разреш аю щ ий элемент, остальны е элементы вы ч исля ю тся поф ормуле A⋅B а'ij = a ij − * , a * где а - разреш аю щ ий элемент В Например, а*, А , В , а34 для элементаа34 третьей а* строк и ч етвертог остолбцапок азаны вверш инах А аij пунк тирногопря моуг ольник атабл.1 и элемент 1 ⋅ ( − 6) . а34 таблицы 2 равена'34 = −4 − = −1 2 Э тим самы м мы вы водим из базиса х5 (разреш аю щ ая строк а ) и вводим вбазис х1 (разреш аю щ ий столбец). П олуч им симплек с – таблицу2 С и м п лекс – т абли ца 2 С вободБ азис ны й X1 ч лен

X2

X3

X4

X5

Х

4

1

0

0.5

0.5

1

-0.5

Х

1

1

1

0.5

0.5

0

0.5

6

0

5

-1

0

3

F

Т ак к ак последня я строк а содерж ит отрицательны е элементы , то данное реш ение не оптимально. В ы берем столбец x3 за разреш аю щ ий и вы ч ислим отнош ение свободны х ч ленов к полож ительны м элементам этого столбца: 1: 0.5, 1: 0. 5. О тнош ения одинак овы . В ы бираем лю бую строк у (Х 4 ) за разреш аю щ ую . Разреш аю щ ий элемент 0.5 . П ри переходе к следую щ ей таблице мож но использовать правило пря моугольник а, рассмотренное вы ш е, а мож но вы полня ть с таблицей элементарны е преобразования . К элементарны м преобразования м симплек с-таблицы относя тся следую щ ие: 1. Умнож ение всех элементов строк и (столбца) таблицы на ч исло, не равное нулю .

11

2. П рибавление к к аж дому элементу одной строк и (столбца) соответствую щ их элементов другой строк и (столбца), умнож енны х на лю бое ч исло. Э лементарны ми преобразования ми делаем на месте разреш аю щ егоэлемента 1, а на месте других элементов разреш аю щ ег остолбца нули. П оследовательность элементарны х преобразований запиш ем справа от таблицы . Э тим самы м мы вы водим из базисах4 (разреш аю щ ая строк а) и вводим вбазис х3 (разреш аю щ ий столбец). П олуч им симплек с–таблицу3: С и м п лекс -т абли ца 3. С вободны й Б азис ч лен X1 X2 X3 X4 X5 Х

3

2

0

1

1

2

-1

Х 1 F

0 8

1 0

0 6

0 0

-1 2

1 2

Т ак к ак последня я строк а не содерж ит отрицательны е элементы , получ или оптимальное реш ение. О птимальное знач ение ф унк ции цели находится в последней строк е в столбце свободны й ч лен, знач ения переменны х, при к оторы х это знач ение достиг ается , находя тся в столбце свободны х ч ленов напротив соответствую щ ей базисной переменной , если при этом не все переменны е исходной задач и я вля ю тся базисны ми, то, не входя щ ие в базис переменны е равны 0. Fmax = 8 при х1 = 0 , х2 = 0, х3 = 2 . А лг еб ро-симплекс-метод (пошаг овы йсимплекс-метод) А лгебро-симплес–метод рассмотрим нак онк ретном примере. Найти минимум ф унк ции F = -2 x1 - 4 x2 ⇒ min П ри огранич ения х

- x1 +5 x2

≤ 30

x1 + x2 ≤ 12 xi

≥0

Д ля реш ения задач и симплек с-методом запиш ем данную задач у в к анонич еск ом виде. Д ля этого введем дополнительны е неотрицательны е переменны е x3 , x4 , x5 и введем их в систему огранич ений, ч тобы она из системы неравенствпревратилась всистемуравенств. Задач апримет вид F = - 2 x1 - 4 x2 ⇒ min

П ри огранич ения х - x1 +5 x2 + х3 = 30 x1 + x2 + х4 = 12 xi ≥ 0

12

1 шаг В ы берем x3 , x4 за основны е переменны е, а x1 , x2 за неосновны е переменны е. В ы разим основны е переменны е и F ч ерез неосновны е переменны е.  х3 = 30 + х1 − 5 х2 (1)   х4 = 12 − х1 − х2 ( 2) С истемауравнений (1) и (2) назы вается о бщи м реш ением системы огранич ений в базисе х3, х4 . П олож им в общ ем реш ении неосновны е переменны е х 1 и х 2 равны ми нулю , получ им реш ение системы огранич ений в виде х1 =0, х2 =0, х3 =30, х4 = 12, или к ратк о в век торном виде Х = ( 0, 0 , 30, 12), к оторое назы вается бази с н ым реш ением или нач альны м планом задач и. Б азисное реш ение назы вается до п у с т и м ым , если все к омпоненты век тора Х неотрицательны . В данном случ ае мы получ или допустимое базисное реш ение. В этом случ ае вы раж аем целевую ф унк цию ч ерез неосновны е переменны е. На первом ш аг е F уж е вы раж енач ерез х1 и х 2. F = - 2 x1 - 4 x2 ⇒ min Д анное реш ение не я вля ется оптимальны м, так к ак переменны е х1 и х 2 входя т в F со знак ом минус и, увелич ивая х1 и х2 мож но уменьш ить F. В водим переменную х 2, входя щ ую в F с наибольш им отрицательны м к оэф ф ициентом в базис. П роанализируем мак симальное увелич ение этой переменной, ч тобы все остальны е переменны е остались неотрицательны ми. И з (1 ) следует, ч то х 2 мож ет бы ть мак симальноувелич енадо 30 : 5 =6, из (2 ) – до12. Т ак им образом переменную х2 мож но мак симально увелич ить до 6, при этом все остальны е переменны е останутся неотрицательны ми. М ак симальное увелич ение переменной х2 определя ется из уравнения ( 1 ). С оответствую щ ую этомууравнению переменную х3 будем вы водить из базиса. 2 шаг . О сновны е переменны е х2 и х4. Неосновны е переменны е х1 и х 3. И з (1) имеем х2 = 6 + 0, 2 х1 − 0,2 х3 П одставим х2 востальны е огранич ения и F, получ им х4 = 12 − х1 − (6 + 0,2 х1 − 0,2 х3 ) = 6 − 1,2 х1 + 0,2 х3 Д анны й базис я вля ется допустимы м, так к ак при нулевы х знач ения х х 1 и х3 знач ения базисны х переменны х неотрицательны . Рассч иты ваем F:

F = −2 x 1 − 4(6 + 0, 2х 1 − 0,2 х 3 ) = −24 − 2,8x 1 + 0,8x 3 П олуч или задач у

F = −24 − 2,8 x1 + 0,8 x3 ⇒ min

13

П ри огранич ения х

х2 = 6 + 0,2 х1 − 0,2 х3 х4 = 6 − 1,2 х1 + 0,2 х3

(3)

Д анное реш ение не я вля ется оптимальны м, так к ак переменная х1 входит в F со знак ом - и увелич ивая х1 мож ноуменьш ить F. В водим переменную х1 вбазис. П ри этом проанализируем мак симальное увелич ение этой переменной ,ч тобы все остальны е переменны е остались неотрицательны ми. И з ( 3 ) следует, ч тох 1 мож ет бы ть мак симально увелич ена до 6 : 1, 2 =5 и при этом все остальны е переменны е останутся неотрицательны ми. Т ак к ак мак симальное увелич ение переменной х1 определя ется из уравнения ( 3 ), к оторое определя ет переменную х4 , тоиз базисавы водим х4. 3 шаг . О сновны е переменны е х1, х2. Неосновны е переменны е х 3 , х4. И з ( 3 ) получ им 1 5 х1 = 5 + х 3 − х 4 6 6 П одставим х1 востальны е огранич ения и F получ им 1 5  1 1  х 2 = 6 + 0,2 5 + х 3 − х 4  − 0,2 х 3 = 7 − х 3 − х 4 6 6  6 6  1 5  1 1  F = −24 − 2,8 5 + х 3 − х 4  + 0,8x 3 = −38 + х 3 + 2 х 4 6 6  3 3  xi ≥ 0 1 1 П олуч или задач у F = −38 + х3 + 2 х4 → min 3 3

х1 = 5 +

1 5 х3 − х4 6 6

1 1 х2 = 7 − х 3 − х 4 6 6 В се переменны е входя т в F со знак ом +, следовательно ф унк ция F не мож ет бы ть больш е уменьш ена. П олуч енное реш ение я вля ется оптимальны м. Fmin = - 38 при х1 = 5 , х2 = 7 . А лг оритм пошаг овог о симплекс-метода Запиш ем общ ую задач улинейногопрограммирования . Д анасистемаm линейны х уравнений и неравенствсn переменны ми

 n  ∑ aij x j ≤ bi (i = 1,2,..., k )  j =1 n  ∑ aij x j = bi (i = k + 1, k + 2,..., m ) j x j ≥ 0 ( j = 1,2,..., l; l ≤ n).

14

и линей ная ф унк ция F = c1 x1 + c2 x2 + L + cn x n А лгоритм пош аг ового симплек с-метода в общ ем случ ае зак лю ч ается в следую щ ем: 1. С истему ог ранич ений записы ваю т в к анонич еск ом виде, т.е. введением дополнительны х неотрицательны х переменны х неравенства системы ог ранич ений превращ аю т вравенства. 2. В получ енной системе огранич ений вы бираю т m переменны х за основны е переменны е и оставш иеся n – m за неосновны е переменны е. О сновны ми мог ут бы ть переменны е, если определитель, составленны й из к оэф ф ициентов при этих переменны х, отлич енот 0. 3. В ы раж аю т основны е переменны е ч ерез неосновны е переменны е, так ая запись назы вается общ им реш ением системы огранич ений в базисе основны х переменны х. 4. П роверя ю т, я вля ется ли вы бранное реш ение допустимы м. Д ля этог ов общ ем реш ении, получ енном на преды дущ ем ш аг е, полаг аю т неосновны е переменны е равны ми нулю и вы ч исля ю т получ ивш иеся при этом знач ения основны х переменны х. Реш ение, при к отором неосновны е переменны е равны нулю , а основны е переменны е неотрицательны , назы вается допустимы м базисны м реш ением. Реш ение, при к отором неосновны е переменны е равны нулю , асреди основны х переменны х имею тся отрицательны е, назы вается недопустимы м базисны м реш ением. 5. Е сли получ енное в п.4 реш ение я вля ется недопустимы м базисны м реш ением, тоот получ енногонедопустимогобазисногореш ения переходя т к допустимому базисному реш ению или устанавливаю т, ч то система огранич ений противореч ива, т.е. задач ане имеет реш ения . 6. Е сли в п.4 получ ено допустимое базисное реш ение, то ф унк цию цели вы раж аю т ч ерез неосновны е переменны е и проверя ю т, вы полнен ли к ритерий оптимальности реш ения . А именно: к ритерий оптимальности реш ения при оты ск ании мак симума линейной ф унк ции: если в вы раж ении ф унк ции цели ч ерез неосновны е переменны е отсутствую т полож ительны е к оэф ф ициенты при неосновны х переменны х, то реш ение оптимально. К ритерий оптимальности реш ения при оты ск ании минимума линей ной ф унк ции: если в вы раж ении ф унк ции цели ч ерез неосновны е переменны е отсутствую т отрицательны е к оэф ф ициенты при неосновны х переменны х, тореш ение оптимально. 7. Е сли к ритерий оптимальности не вы полнен, то переходя т к новому допустимому базисному реш ению дотех пор, пок а к ритерий оптимальности не будет вы полненили не будет установлено, ч тозадач ане имеет реш ения .

15

8. Е сли к ритерий оптимальности вы полнен, то оптимизация реш ения зак онч ена. 9. П овторя ю т пп. 6-8 дотех пор, пок ане будет получ енооптимальное реш ение. В ы писы ваю т к омпоненты оптимального реш ения (оптимальны й план) и находя т оптимальное знач ение линей ной ф унк ции. 10. Е сли допустимое базисное реш ения я вля ется оптимальны м, а в вы раж ении ф унк ции цели ч ерез неосновны е переменны е отсутствует хотя бы одна неосновная переменная , то получ енное базисное реш ение не я вля ется единственны м. 11. Е сли к ритерий оптимальности реш ения не вы полнен, а вовсех уравнения х системы огранич ений неосновны е переменны е входя т с полож ительны ми к оэф ф ициентами или отсутствую т совсем, тоф унк ция цели не имеет к онеч ного оптимума, т.е. Fmax= ∞ , Fmin = - ∞ . Задачи линейног о прог раммирования О дна из задач линейногопрограммирования – задач аораспределении ресурсов - рассмотренавы ш е. Рассмотрим простейш ую задачу о с о с т ав лен и и раци о н а, к к оторой так ж е сводится задача о ди ет е и задача о с м ес ях. П усть имеется 3 вида продук тов : П1 , П 2 , П 3 . С тоимость единицы к аж догопродук та известна с 1 , с 2, с 3 соответственно. И з этих продук тов необходимосоставить пищ евой рацион, к оторы й долж ен содерж ать белк ов не менее b1 единиц, ж иров не менее b 2 единиц, углеводов не менее b3 единиц. Е диница продук та П 1 содерж ит а11 единиц белк ов, а12 единиц уг леводов, а13 единиц ж иров, аналогич но для продук тов П 2 , П 3 содерж ание белк ов, ж иров и углеводов задается к оэф ф ициентами аij. Т ребуется так составить пищ евой рацион, ч тобы обеспеч ить минимальную стоимость рациона при содерж ании в нем необходимого к олич ества питательны х вещ еств. П усть х1 , х2, х3 – к олич ества продук тов П 1, П 2, П 3 , входя щ их врацион. Задач алинейногопрог раммирования осоставлении рационаимеет вид: так к ак общ ая стоимость долж набы ть F = c1 x1 + c2 x2 + c3 x3 ⇒ min минимальной a11 x1 + a 21 x 2 + a31 x3 ≥ b1  a12 x1 + a 22 x2 + a32 x3 ≥ b2 a x + a x + a x ≥ b , 23 2 33 3 3  13 1  хij ≥ 0  так к ак содерж ание питательны х вещ еств в рационе не долж но бы ть меньш е нормы . Рассмотрим простейш ую задачу о загру зке о бо ру до в ан и я. П усть имею тся два вида станк ов (1 и 2), производя щ их минеральны е удобрения трех видов (А1 ,A2 и A3). С танок первог овидапроизводит в меся ц а11 ед. удобрения А1 , а12 единиц удобрения А2 и а 13 единиц удобрения А3, аналогич но производительность второго станк а равна а21, а22 , а23 . К аж ды й к илограмм удобрения А1 приносит предприя тию доход с 1, удобрения А2 – с 2 , удобрения А3 – с 3. П редприя тию дан

16

план, согласно к оторому оно долж но вы пустить не менее b1 к г удобрения А1 , не более b2 к г удобрения А2 и не менее b 3 к г удобрения А3. П усть хij – ч исло станк ов вида i, заня ты х производством удобрения Аj. Т ребуется так распределить заг рузк у станк ов, ч тобы прибы ль бы ла наибольш ей. Задач а линейногопрог раммирования имеет вид: F = c1 ( x11 + x21 ) + c2 ( x12 + x22 ) + c3 ( x13 + x23 ) ⇒ max  x11 + x12 + x13 ≤ N1 x + x + x ≤ N 22 23 2  21 a11 x11 + a 21 x 21 ≥ b1 a x + a x ≤ b 22 22 2  12 12 a13 x13 + a23 x23 ≥ b3   xij ≥ 0 Где N1 и N2 – к олич ества станк ов первого и второго вида, заня ты х производством удобрений. В аж ны м ч астны м случ аем задач и линейног опрог раммирования я вля ется т ран с п о рт н ая задача, позволя ю щ ая спланировать обеспеч ение химич еск ого предприя тия сы рьем при минимальны х транспортны х затратах. Рассмотрим транспортную задач унак онк ретном примере. Т ранспортная задача П усть на предприя тии имеется 4 ск лада, на к оторы е поступает продук ция от трех поставщ ик ов. М ощ ности поставщ ик ов и потребителей, а так ж е затраты на перевозк у единицы груза для к аж дой пары поставщ ик -потребитель сведены втаблицу: П отребит ель

213

157

130

90

Ui

П оставщ ик 5

300

2

3

–

1 +

157

53 1

4

90 1

1

100

190

-4

100 1

2 + 160

0

1

4

– 30

-4

Vj 5 3 5 1 Т ак им образом, у первог опоставщ ик аимеется 300 ед. товара, увторого– 100, у третьег о – 190. И меется так ж е 4 потребителя этого товара, первому потребителю требуется 213 ед, второму – 157 ед., третьему – 130 ед. , ч етвертому – 90 ед. данноготовара. В левом верхнем углу произвольной (i,j)-й к летк и (i-номер строк и, j-номер столбца) стоит так назы ваемы й к оэф ф ициент

17

затрат сij - затраты на перевозк у единицы г руза от i-гопродавца к j-му пок упателю . П остроим эк ономик о-математич еск ую модель данной задач и. И ск омы й объ ем перевозк и от i-гопоставщ ик а к j-му потребителю обознач им ч ерез xij и назовем поставк ой к летк и (i,j). Например, х12 – иск омы й объ ем перевозк и от 1-го поставщ ик а к овторому потребителю или поставк а к летк и (1,2). Нуж нонайти объ емы перевозок для к аж дой пары поставщ ик – потребитель так , ч тобы : 1. М ощ ности всех поставщ ик овбы ли реализованы . 2. С просы всех потребителей бы ли удовлетворены . 3. С уммарны е затраты наперевозк убы ли бы минимальны . Ч тобы мощ ность к аж дого из поставщ ик ов бы ла реализована, необходимо составить уравнения балансадля к аж дой строк и таблицы поставок , т.е. x11 + x12 + x13 + x14 = 300 x21 + x22 + x 23 + x24 = 100 x31 + x32 + x33 + x34 = 190 А налогич но, ч тобы спрос к аж догопотребителя бы л удовлетворен, необходимо составить уравнения балансадля к аж догостолбцатаблицы поставок : x11 + x 21 + x31 + х41 = 213 x12 + x22 + x32 + х42 = 157 x13 + x 23 + x33 + х43 = 130 x14 + x24 + x34 + х44 = 190 О ч евидно, ч то объ ем перевозимого г руза не мож ет бы ть отрицательны м, поэтомуследует дополнительнопредполож ить ч то xij > = 0 (i=1,2,3 ; j=1,2,3,4 ) С уммарны е затраты F на перевозк у вы раж аю тся ч ерез к оэф ф ициент затрат следую щ им образом F = ∑ cij × xij , ij

где c ij – соответствую щ ий к оэф ф ициент затрат. Необходимо найти так ое реш ение X=(x11, x12 ,… ), при к отором линейная ф унк ция F принимает минимальное знач ение. Задач а, при к оторой суммарная мощ ность поставщ ик ов равна суммарной мощ ности потребителей, назы вается зак ры той 300+100+190=213+157+130+90. Д ля реш ения задач и необходимо составить первонач альное распределение поставок . Наиболее распространенны ми я вля ю тся два метода нахож дения первонач альног о распределения : метод северо-западного угла и метод наименьш их затрат. М етод северо-западногоуглазак лю ч ается втом, ч то к аж ды й раз находится самая северо-западная к летк а и в нее делается мак симально возмож ная поставк а. С огласно методу наименьш их затрат, к аж ды й раз находим к летк у с наименьш им к оэф ф ициентом затрат и делаем в нее мак симальновозмож ную поставк у. Нач альное распределение исходной задач и находим с помощ ью метода наименьш их затрат. В исходной таблице наименьш ий к затрат равен 1,

18

вы бираем к летк у (2,3) и делаем в нее мак симальную поставк у 100 и вы ч ерк иваем вторую строк у из рассмотрения , так к ак второй постащ ик весь товар отдал, затем вы бираем к летк у (3,3) и делаем в нее поставк у 30 ( так к ак третьему потребителю нуж но тольк о130 ед. груза, а 100 он уж е получ ил), и вы ч ерк иваем третий столбец из рассмотрения , так к ак третий потребитель получ ил весь товар. Д алее опя ть вы бираем к летк у с к =1 – (3,1) и делаем в нее поставк у 160 ед., так к ак 30 ед третий постащ ик уж е отдал, при этом из рассмотрения вы ч ерк ивается третья строк а. Затем 90 ед. ставим вк летк у (1,4) и вы ч ерк иваем 4 столбец из рассмотрения . У нас остались две к летк и, вк оторы е мож носделать поставк и – (1,2) и (1,1). Д елаем в них поставк и 157 и 53. Е сли распределение составлено правильно, то ч исло заполненны х к леток долж но равня ться ч ислустрок + ч ислостолбцов - единица. Д ля проверк и оптимальности распределения используется метод потенциалов, к оторы й зак лю ч ается в следую щ ем. П усть Ui – потенциал i-й строк и а Vj – потенциал j-го столбца. Зададим потенциал первой строк и U1 – произвольно, например, U1=0. Д алее потенциалы Ui и Vj подбираем так , ч тобы для з а пол н е н н ы х к л е т ок Ui +Vj =С ij. Ui пиш ем справа от таблицы , а Vj – под таблицей. Например, для к летк и ( 1 , 1 ) имеем: U1 + V1 = 5 , следовательно, V1 = 5 , так к ак U1=0. Находим все потенциалы и строим матрицуоценок к леток 0 0 − 3 0   Dij = C ij − U i + V j =  0 5 0 4  0 3 0 7    Т ак к ак в матрице имею тся отрицательны е элементы , получ енное распределение не оптимально. Необходимо сделать поставк у в к летк у с отрицательной оценк ой, в данном случ ае (1,3). Д елаем перестановк у поцик лу, ук азанному пунк тиром, вк лю ч аю щ ему к летк у (1,3). Ц ик л перестановк и в транспортной задач е представля ет собой замк нуты й мног оугольник , одна верш ина к оторого находится в к летк е, в к оторую , исходя из анализа матрицы оценок к леток , необходимосделать поставк у. В данной задач е эток летк а (1,3). Э той верш ине цик ла присваивается знак +. О стальны е верш ины цик ла находя тся в заполненны х к летк ах, в к аж дой заполненной к летк е, ломаная , составля ю щ ая цик л, делает поворот на 90 г радусов. В данном примере цик л проходит ч ерез к летк и (1,3), (3,3), (3,1) и (1, 1) . Д алее делаем следую щ ие ш аги: 1. П осле вы бора цик ла перестановк и в углах цик ла расставля ем знак и следую щ им образом. О т полож ительной верш ины (1,3) переходим к соседней верш ине, ч ередуя знак и, присваиваемы е верш инам цик ла( см. табл.1). 2. С реди отрицательны х верш ин цик ла находим к летк у с минимальной поставк ой к летк и, (эток летк а(3,3) с поставк ой к летк и 30). 3.Наследую щ ем ш аге в полож ительны е верш ины цик ла добавля ем поставк у30, аиз к леток сотрицательны ми верш инами вы ч итаем поставк у30. В результате получ им распределение

(

)

19 П отребит ель

213

157

130

90

Ui

П оставщ ик –

300

+

0

4

90

30

157

23 1

100

1

2

3

5

1

1

-1

–

+

100 2

1

1

4

-4

190 190

Vj

5

3

2

1

О пя ть ищ ем все потенциалы и строим матрицуоценок к леток  0 0 0 0   Dij = C ij − U i + V j =  − 3 2 0 1   0 3 3 7   Т ак к ак в матрице имею тся отрицательны е элементы , получ енное распределение не оптимально. Д елаем перестановк у по цик лу, ук азанному пунк тиром. В результате получ им распределение

(

)

П отребит ель

213

157

130

90

Ui

П оставщ ик 5

3

2

1

300

0 157 1

4

53 1

90 1

100

-1 23 1

77 2

1

4

190

-1 190

Vj

2

3

2

1

О пя ть находим все потенциалы и строим матрицуоценок к леток

3 0 0 0   Dij = Cij − U i + V j =  0 2 0 1  0 0 0 4  

(

)

20

М атрица не содерж ит отрицательны х элементов, следовательно, данное распределение оптимально. П ри этом транспортны е расходы составя т: F = 3 ⋅ 157 + 2 ⋅ 53 + 1 ⋅ 90 + 1 ⋅ 23 + 1 ⋅ 77 + 1 ⋅ 190 = 957 ден . ед. Т ранспортны е расходы для нач альногораспределения ( потаблице 1):

F = 5 ⋅ 53 + 3 ⋅ 157 + 1 ⋅ 90 + 1 ⋅ 100 + 1 ⋅ 160 + 1 ⋅ 30 = 1116 ден . ед.

21

К онтрольны е вопросы 1. П редмет и метод дисциплины «И сследование операций». 2. П оня тие математич еск огомоделирования . 3. О пределение линей ногопрограммирования . 4. Задач аораспределении ресурсов: постановк аи математич еск ая модель. 5. С тандартная , к анонич еск ая и общ ая задач и линейног опрограммирования . 6. О бщ ее, базисное и ч астное реш ение системы линей ны х уравнений. Д опустимое и недопустимое базисны е реш ения . 7. Геометрич еск ое реш ение стандартной задач и линейног опрограммирования . 8. П ереход от стандартной задач и линейного прог раммирования к к анонич еск ой. 9. С трук тура симплек с-таблицы . К ритерии оптимальности опорногоплана при оты ск ании мак симумацелевой ф унк ции. П ереход к новомуопорномуплану. 10. П ош аговы й симплек с – метод. Е гоалгоритм. 11. Задач и линейног опрограммирования . 12. Зак ры тая транспортная задач а. П остановк аи математич еск ая модель. 13. О ты ск ание первогоопорног опланаперевозок . 14. М етод потенциалов. В ы ч исление оценок к леток . 15. П оня тие цик ла в транспортной задач е. П ереход к новому опорному плану. К ритерий оптимальности планаперевозок .

22

1. 2.

3. 4. 5.

Л итература К омпью терное моделирование / П од ред. Г.А . Угольницк ого. – М .: В уз. к н. – (Э к ология ).- 2000.- 117 с. И сследование операций в эк ономик е/ Н.Ш .К ремер, Б .А .П утк о, И .М .Т риш ин, М .Н.Фридман; П од ред. Н.Ш .К ремера. – М .: Б анк и и бирж и, Ю НИ Т И , 1997.407 с. А к улич И .Л . М атематич еск ое прог раммирование в примерах и задач ах. / И .Л . А к улич . – М .: В ы сш . ш к ., 1986.- 167 с. Горч ак ов А .А . К омпью терны е эк ономик о-математич еск ие модели / А .А . Горч ак ов, И .В . О рлова. – М .: К омпью тер, Ю НИ Т И , 1995.- 261 c. Федоров М .П . М атематич еск ие основы эк ологии / М .П . Федоров, М .Ф.Романов; П од ред. В .И .Зубова. – С пб.: изд-воС П бГТ У, 1999.- 155 с. Содерж ание

В ведение Задач аораспределении ресурсов Геометрич еск ий метод реш ения ЗЛ П О бщ ая задач аЛ П С имплек с-методс использованием таблиц П ош аговы й симплек с-метод А лгоритм пош аговог осимплек с-метода Задач и линейногопрограммирования Т ранспортная задач а К онтрольны е вопросы Л итература

3 4 5 7 9 11 13 15 16 21 22

23

С оставители: Б уты рск ая Е ленаВ асильева, В асильеваВ ераИ вановна Редак тор Т ихомироваО льг аА лек сандрована