Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

3.3. Частный алгоритм реализации метода. Представление и преобразование данных

Выше была изучена последовательность действий, приводящих к получению z*, тогда как поставленная задача требует найти точку X* = (x*1, х*2, ..., х*n), в которой z достигает значения z*. Прежде чем перейти к описанию процедуры поиска X*, заметим, что любая из величин bq (q = 1,....., n-1) заключена в пределах 0≤bq≤bn, поскольку


(из-за неотрицательности произведений ajxj). Для упрощения последующих рассуждений удобно предположить, что bn и aj (j = 1,..., n) - целые числа. Это условие вместе с условием "xj - целые" (j = 1,....,n) определяет целочисленность всех bq.

Порядок операций теперь может быть таким:

- выбирается переменная Х\, которой разрешается принимать целые значения от 0 до [b1/a1] при 0≤b1≤bn, пусть х̂1 есть то значение х1, при котором f1(x1) достигает максимума (ясно, что х̂1 зависит от величины b1); составляется таблица, где собраны все оптимальные x1 = x̂1, соответствующие допустимым b1, причем каждому b1 может отвечать несколько значений x̂1 (табл. 3.1);

- определяются величины х̂2(b2), доставляющие максимум функции f2(x2)+Ψ1(b22х2) при 0≤х2≤[b2/a2], 0≤b2≤bn; результаты сводятся в табл. 3.2; при ее составлении удобно пользоваться результатами предыдущего шага, находя значения функции Ψ1 для разных b22х2, которые в силу сделанных выше предположений положительны, целочисленны и не превышают bn;

- рассмотренные операции повторяются для всех оставшихся x̂q(bq), (q = 3,..., n-1), и на каждом шаге используется предыдущая таблица, содержащая значения Ψq-1 в итоге возникает набор сходных по форме таблиц, содержащих перечни оптимальных x̂q (q = 1,...., n - 1);

- анализируется последнее соотношение


вследствие того, что bn задано однозначно исходными условиями задачи, таблица с х̂n(bn) состоит всего из одного столбца, который дополняет предшествующие результаты; теперь остается выбрать из множества найденных x̂q (q = 1,...,n) одну или несколько совокупностей значений х*1, x*2, ..., х*n, определяющих X*, z*; сделать это можно с помощью уже составленных ранее таблиц;

- в качестве х*n принимается х̂n (это необходимо, так как лишь при хn = х̂n достигается z* независимо от того, каковы x̂n-1,.....,x̂1); если на предыдущем шаге получено несколько значений х̂n, принимаемых здесь за х*n, последующий анализ проводится применительно к каждому из них, начиная с произвольно взятого;

- при известном х*n вычисляется b*n-1 = bnnх*n; теперь нужно обращать внимание лишь на тот столбец в таблице, содержащей сводку х̂n-1 который соответствует именно b*n-1, потому что все другие величины bn-1 допускались ранее в предположении 0≥bn-1≤bn, вытекающем, в свою очередь, из возможности принятия переменной хn целого ряда неотрицательных значений; следовательно, х*n-1 = x̂n-1 (b*n-1);

- при известных х*n и х*n-1 вычисляется b*n-2 = bn - аnх*n - аn-1x*n-1, и по таблице, содержащей хn-2, находим х*n-2 = x̂n-2(b*n-2); тем же способом определяются остальные х*n-k (k = 3, n = 1); в результате получаем одну или несколько совокупностей величин x*j (конец процесса).

Таблица 3.1
Таблица 3.1

Таблица 3.2
Таблица 3.2

Обращаясь к терминологии предыдущего раздела, можно сказать, что в рассмотренной здесь процедуре поиска X* содержанием шага (этапа) процесса принятия решений является определение очередного x*q (q = n,...., 1). Состояние процесса к началу этапа характеризуется соответствующей величиной bq, и поэтому Ψq можно назвать функцией состояния.

В данном случае на каждом шаге встречался скалярный параметр bq и требовалось найти лишь одну переменную x̂q, хотя на практике чаще приходится иметь дело с векторами Вq и Хq. В дальнейшем на это будет обращено внимание, но сейчас важнее оценить возможность отказа от введенного выше условия "xj, aj, bn - целые числа", что позволит расширить круг задач, к которым применима приведенная здесь методология решения.

Исключив требование целочисленности xj, aj, bn, можно приступить к решению задачи с сепарабельной целевой функцией


и ограничениями


так же, как это было сделано выше, т. е. найти Ψ1(61) = maxx1 f11) при 0≤b1≤bn и далее все функции состояний


при 0≤bq≤bn, xq≥0, q = 2,....,n, последняя из которых определит z*. На этой стадии решения все различия сводятся к тому, что переменные xq (q = 1,...., n-1) меняются в пределах от 0 до bq/aq (а не до [bq/aq]), и поиск частных максимумов по xq ведется, вообще говоря, иными методами. Например, в первом варианте задачи любая функция Ψq могла быть найдена перебором значений суммы fq(xq)-Ψq-1(bq-1), а во втором варианте более перспективным может оказаться путь решения уравнений d/dxq [fqq-1] = 0.

При дальнейшем изучении различий между этими вариантами возникают вопросы о формах представления информации, которая ранее отражалась в табл. 3.1, 3.2, а также о способах определения оптимальных значений х*n-1, х*n-2, .. при известных x̂q(bq) (q = 1,....,n). Оба вопроса не являются принципиальными, хотя и важны сами по себе. Первый решается применительно к конкретной обстановке (xq и Ψq могут быть представлены, в частности, в виде формул или графиков, если их исследованием занимается человек, в виде систем уравнений или сеток значений, если все "передано" вычислительной машине и т. д.). Это, в свою очередь, накладывает отпечаток на способы получения x*j (j = n,....,1), среди которых наиболее надежными можно считать непосредственные вычисления значений Ь*n-1 ,..., b*1 и x*n-1 = x̂n-1(b*n-1), x*n-2 = x̂n-2 (b*n-2),....

Таким образом, отбрасывая требования целочисленности xj, aj, bn, мы не меняем метод решения в целом, меняются лишь приемы промежуточных вычислений.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"