М И Н И СТ Е РСТ В О О Б РА ЗО В А Н И Я РО ССИ Й СК О Й Ф Е Д Е РА Ц И И В О РО Н Е Ж СК И Й ГО СУ Д А РСТ В Е Е Н Ы Й ...
5 downloads
178 Views
203KB Size
Report
This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
Report copyright / DMCA form
М И Н И СТ Е РСТ В О О Б РА ЗО В А Н И Я РО ССИ Й СК О Й Ф Е Д Е РА Ц И И В О РО Н Е Ж СК И Й ГО СУ Д А РСТ В Е Е Н Ы Й У Н И В Е РСИ Т Е Т
Э К О НО М И К О – М А Т Е М А Т И Ч Е С К О Е М О Д Е Л И РО В А НИ Е В Х И М И И и Э К О Л О ГИ И П особие для студентов С пециальность «Х имия »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
С оставители: Б уты рск ая Е ленаВ асильева, В асильеваВ ераИ вановна Редак тор Т ихомироваО льг аА лек сандрована