Файл: Чесноков, Н. И. Оптимизация решений при разработке урановых месторождений.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.10.2024
Просмотров: 164
Скачиваний: 0
И если в выражении (3.89) т а xZ зависело от Ь, то
Л= 1 |
|
|
|
|
с (3.91) |
от |
b — апхп, |
|
Е fi(Xi) зависит в соответствии |
||||||||
і = 1 |
|
|
|
|
|
|
|
|
поэтому можно написать |
|
|
|
|
|
|
||
max |
V Л (л-,-) = |
а„_І (b ~ |
anxn). |
(3.92) |
||||
........ Xn-U=\ |
нам |
удалось |
определить |
|||||
Предположим, |
что |
|||||||
a„_i (b — а„Хп) |
для всех допустимых значений |
х„, |
тогда |
|||||
в соответствии |
с |
равенствами (3.90) и (3.92) можно |
||||||
записать следующее: |
|
|
|
|
|
|
||
max Z = |
шах [/л (л„) -f- ая_, (b — а„х„)], |
|
(3.93) |
|||||
|
|
хп |
па |
который нужно |
умножить |
|||
где а„_і — коэффициент, |
||||||||
(b — а„х„), чтобы |
получить |
максимальное значение Z. |
В данном случае х„ может принимать значения от 0 до Ь/ап, иначе может быть нарушено условие неотрицатель ности [см. (3.89)].
Для определения максимума в равенстве (3.93) сле
дует подставить все допустимые значения х„, |
а затем |
выбрать наибольшее значение А: |
|
Ап {х„) = fn {х„) + а„_, (b — апх„). |
(3.94) |
Одновременно с вычислением максимального значе ния А определяют оптимальное значение .ѵ„ (обозначим
его через л-?,). Как видно из изложенного, отыскание maxZ можно было бы свести к решению задачи с одним неизвестным, если бы была известна вторая половина уравнения (3.94), а именно ап- і { Ь— а„х„).
Следующим шагом будет определение гх„_і (b — а„х„). Эта функция представлена уравнением (3.94). Для npoизвольно взятого неотрицательного числа c можно написать
а„_, ( с |
) |
max |
п—1 |
(3.95) |
V f,(xt) |
||||
и |
•v" -v=.......xn |
- 1 |
|
|
ГІ—I |
|
|
|
|
|
|
|
(3.96) |
|
|
Y^aixi < c . |
|||
|
/=! |
|
|
|
Если провести те же вычисления и преобразования с |
||||
уравнениями от (3.89) |
до |
(3.93) |
включительно, получим |
|
(с) = max |
(я„_д) + а„_ 2 (с — ап_уХп_,)}, |
(3.97) |
||
ХП—1 |
|
|
|
|
186
где |
|
|
|
«n-s (d) = |
max |
У № )> |
(3.98) |
причем |
•V, |
1 1=1 |
|
|
|
|
|
|
У] а^і < d |
|
(3.99) |
|
1=1 |
|
|
и X может изменяться от 0 до с/ап-\. Таким образом, если была бы известная функция ct„_2 (d), можно было
бы определить а„_і(с), используя лишь одну неизвест ную дг„_|. Так же как для выражения (3.94), вычисляем а,,-] (с) для различных значений х„_г, тем самым опре деляем
|
max |
(^n_j) + an_ t (с — а,,_хх ^ )] |
|
|
и оптимальное значение х °_ г |
|
|||
Аналогично |
можно |
определить а„ _ 2 (d), а„_з |
и т. д., |
|
пока не подойдем к вычислению |
|
|||
|
|
ах (k) = max fx (хх) |
(3.100) |
|
|
|
^здесь |
0 < хх < — ^ . |
|
Теперь, чтобы определить maxZ, нужно сначала най |
||||
ти a\(k), |
а потом выполнить все указанные выше дейст |
|||
вия в обратном порядке. |
|
|||
Практически это выполняется следующим образом. |
||||
Вначале |
определяют |
последовательность функций |
||
а.і(с)= |
max |
{ |
/,-(хг). Затем вычисляют |
а\(с). |
V |
||||
•V,, л-= . |
X ‘ |
|
|
После этого, используя рекуррентные соотношения, опре деляют (22(с), аз(с),..., а(с)„_і и max Z.
В общем виде рекуррентные соотношения имеют вид
[см. уравнения |
(3.93) и (3.97)]: |
|
|
|
|
а к(с) = max |
|
|
к-1 |
|
|
fк(xk) + |
max |
2 |
ft (x,) |
(3.101) |
|
х к |
- |
.........ѵ/г—1 ‘=1 |
|
|
|
Но поскольку |
|
|
|
|
|
|
max |
V |
ft (xt) |
|
|
|
xu xi.........Л'у,._1 7=1 |
|
|
|
187
определяется при условии
|
|
|
к-1 |
|
|
|
|
|
|
|
|
X |
а,- -V, < |
С — а АдгА, |
|
|
|
|
|
|
1^=1 |
|
|
|
|
|
|
|
max V |
(л-,) = |
а*_, (с — акхк), |
|
|||
|
|
|
I |
|
|
|
|
|
поэтому (3.101) |
может быть |
переписано в следующем |
||||||
виде: |
|
|
|
|
|
|
|
|
|
«* (с) = |
max [/* (а*) + |
а*_, (с — аА**)]; |
(3.102) |
||||
|
|
|
хк |
|
|
|
|
|
Тогда |
|
|
|
|
|
|
|
|
|
|
|
maxZ — a N(b). |
|
(3.103) |
|||
При решении практической задачи динамического |
||||||||
программирования вначале определяют |
|
|
||||||
|
|
|
|
(с) — max /у (.rt), |
|
(3.104) |
||
|
(0, Ь) |
|
|
|
А*1 |
|
|
|
где с= |
О^лр ^ |
(c/oj); |
(лр — частные значения пе |
|||||
ременной первого шага оптимизации). |
|
— значе |
||||||
Результаты расчетов сводят в табл. 42 (.ѵ° |
||||||||
ние д‘і, |
максимизирующее f\(x|)). |
|
|
|||||
|
|
|
|
|
|
|
Таблиц а 42 |
|
С |
0 |
1 |
2 |
|
к- 1 |
к |
Ь |
|
а, (с) |
а, (0) |
а, (1) а, |
(2) |
аЛ_ 1(/.-D |
ак (*) |
а. (Ь) |
||
■ѵ?(с) |
0 |
|
-ѵ?(2) |
|
■ѵ?(А—О 1 |
.ѵ)Ѵ) |
а?(Ь) |
|
Л'1(0) |
|
|
У величины А‘° может быть несколько значений, тогда
их все вписывают в табл. 42. И в этом случае может потребоваться определить одно оптимальное решение, тогда в таблицу вписывают одно значение х ° . Если тре
буются все оптимальные решения, то в табл. 42 вписы вают все значения х°.
188
Затем, когда сц (с) становится известным, применив
рекуррентное соотношение |
|
|
а2 (с) = |
max [/., (л'2) -|- а1 (с — а2.ѵ2)] |
(3.105) |
при 0 ^л'2 ^ (с/а2), |
определяют «2 (c) для всех |
допусти |
мых значений с. При вычислении гх2(с) при фиксирован ном с находят значения Д2:
А, (0, с) =-■/а (0) + ах (с),
А (1, с) = /2(1) -І-аДс — а2),
(3.106)
Наибольшее значение Л2 |
и является 0 2 (c). Параллельно |
|||||||
с вычислением а2(с) определяют х\ |
(значение |
х2, |
мак |
|||||
симизирующее А2). |
а2(с) |
нужно |
знать |
только |
||||
Для |
определения |
|||||||
аі (с — а2х2) при О^д:2^ с /а 2. |
|
|
|
|
|
|||
В связи с тем что аДс) |
определено для всехО ^с^Ь , |
|||||||
можно найти аі (с — 02*2) |
из |
табл. |
42 |
(число, |
стоящее |
|||
на пересечении строки аі и столбца, |
в котором |
нахо |
||||||
дится значение Ch = c — а2х2). |
|
|
|
|
|
|||
После |
этого составляют |
вторую |
аналогичную |
таб |
||||
лицу (см. табл. 44) для а2(с) |
и х\. |
В таком нее порядке |
||||||
строят таблицы для а3(с), |
0 4 ( c ) , а5(с) |
и т. д. до a n - i ( c ) . |
Значение max 2 и хп° можно определить либо с примене нием таблиц, либо с помощью уравнения (3.90).
Определив таким образом |
maxZ |
и дД, дД, ...,х °,вы |
числяют |
|
|
шах Z = 2 |
ft (*/) |
|
І = 1 |
|
|
при условиях |
|
|
п |
0; і = |
_____ |
at X[4Zb; а > |
(1, и). |
Как видно из изложенного, при большом числе пере менных и интервалов изменения переменных выполнение такой работы вручную очень сложно. Рассмотренная последовательность вычислений может быть легко за программирована для решения на ЭВМ. Кроме того,
189
применение рекуррентных соотношении позволяет ис пользовать стандартные программы.
При решении задачи динамического программирова ния, где в качестве одной из переменных является вре мя, рекуррентные соотношения имеют вид, аналогичный (3.102). Только в этом случае //,(4, *а) — состояние си стемы b (к—т)-м промежутке времени, а оц_і (с—щ,/;,)— оптимальное состояние системы от начального до (k— 1)-го интервала времени. Следовательно, в данном случае а/, и сц_і зависят от времени.
Сравним метод динамического программирования с методом простого перебора вариантов. Пусть в задаче имеется 5 переменных (п = 5) и ограничение Sx,-^25. Тогда при простом переборе вариантов (т.е. при распре делении 25 единиц на 5 групп) число их будет А:
А(ft + 6 — I)!
6! (ft — I)!
При /1 = 5, Ь = 25
А= (5 + 2 5 - 1 ) !
25! (5— і)!
ИЛИ
А = 29'28'27'2- = 29-7-9-13 = 23 751.
4-3-2
При решении задачи методом динамического програм мирования число вариантов будет равно
А = Ь п + ( я - 'НМ ;!) + п,
или после подставки значения b и п
А — 25 f5 А- |
^ + 5 = 1430, |
т.е. почти в 17 раз меньше, чем при простом переборе вариантов. Эффективность метода динамического про граммирования по сравнению с методом полного перебо ра вариантов становится еще выше при увеличении п. Причина состоит в том, что на каждом шаге для кон кретного с все неблагоприятные комбинации переменных исключаются из дальнейших расчетов. Это преимуще ство динамического программирования приобретает осо бенно важное значение при решении задач с большим
190
числом переменных. Например, для линейного програм мирования перебор вариантов может быть оправдан при одном или двух ограничениях. При большом числе огра ничении более эффективным является симплекс-метод. Причина заключается в том, что при наличии, например, 100 ограничении необходимо перебрать 100 параметров состояния. Если при этом каждый параметр принимает 100 различных значений, таблица значений функции аі, будет содержать 100100 различных значений. При реше нии такой задачи на ЭВМ со скоростью ІО16 значений Uh в 1 сек потребовалось бы затратить для этого 10093 лет [55]. Это следует учитывать при выборе вычислитель ного метода решения задач линейного программирова ния. Динамическое программирование целесообразно использовать лишь тогда, когда его применение эффек тивнее других методов.
Рассмотрим практический пример. На одни из заво дов, перерабатывающих руду, поступает сырье с не скольких рудников. Причем руда по сортам посту пает неравномерно, следствием чего являются большие потери металла, цена которого составляет 10,0 руб. за 1 кг.
Врезультате проведенного анализа и в соответствии
сперспективой развития рудииков-поставщиков и пере рабатывающего завода было выявлено следующее:
1)суточный объем перерабатываемой руды не пре вышает 10 тыс. г;
2) на завод поставляют руду сорта А (1 тыс. г со держит 1 т металла); сорта Б (2 тыс. т содержат 1 г металла); сорта В (2 тыс. г содержат 1 т металла; тех нология переработки более экономична, чем руды сорта Б, несмотря на одинаковое содержание металла);
3) в случаях, когда руды сорта А поставляется на завод больше, чем может переработать завод руды это го сорта, она подается на комплекс аппаратов, перера
батывающих руды сорта Б или В. При этом снижается извлечение и как следствие этого дополнительно те ряется 40 кг металла на 1 тыс. г руды сорта А. Если поставляется больше руды сорта Б, чем может перера ботать завод, то дополнительные потери металла состав ляют 30 кг на каждые 2 тыс. г руды. Поставка руды сорта В в количестве, большем, чем может быть пере работано на заводе, приводит к дополнительной потере 65 кг металла на каждые 2 тыс. г руды;
191