Главная Прочее
Проблемы автоматизированной обработки информации
|
|
|||||
Методы линейного программированияЗадачу выбора можно решать методами линейного программирования после преобразования задачи (3.1)…(3.3) к стандартной форме задачи линейного программирования. Такое преобразование можно осуществить по следующей схеме. Матрицу исходных данных задачи выбора А порядка n транспонировать в матрицу С размера [1n2] ![]() ![]() (3.4) где Ai - i-я строка матрицы А. Аналогично переменные сгруппировать в матрицу-строку ![]() ![]() , где - матрица-строка, составленная из следующих компонентов: Ограничения (3.2), (3.3) преобразовываются к виду , (3.5) где ![]() ![]() ; Матрица Ei содержит во всех строках, кроме i-й нулевые элементы, а в строке i - все элементы равны единице. I - единичная матрица порядка n. Матрица В имеет размер [n21]. Получив (3.4) и (3.5), можно сформулировать задачу выбора как стандартную задачу линейного программирования. ![]() ![]() (3.6) Метод динамического программированияДля реализации метода динамического программирования введём функцию Беллмана в следующем виде: - оптимальное значение критерия (3.1) при распределении k типов ресурсов с номерами между первыми k пунктами потребления. На первом шаге необходимо вычислить n значений , , , …, . На втором шаге последовательно определить значения Число таких - число сочетаний из n элементов по 2. На третьем шаге следует использовать соотношения ![]() ![]() , которые соответствуют вариантам решения на третьем шаге. Для произвольного k-го шага (i < k n) можно записать функциональные уравнения динамического программирования ![]() ![]() (3.7) Число вариантов решения на k-м шаге будет равно . Оно увеличивается с ростом k (при k=1 равно n), достигает максимума при k=n/2 или k=(n+1)/2 и k=(n-1)/2 (для нечётных n) и снова снижается до n на последнем n-м шаге. Общее число вариантов решения, которое необходимо проанализировать за все n шагов динамического программирования, определим по формуле: ![]() ![]() (3.8) Метод не является самым эффективным среди методов решения задачи выбора. Методы кратчайшего увеличивающего путиВ последние годы благодаря работам японских учёных (К.Томизава), получили распространение методы кратчайшего увеличивающего пути (КУП). Пусть в матрице исходных данных выбора порядка n (обозначим её A(n)) выделена квадратная подматрица порядка (n-1), т.е. A(n-1), и пусть для этой подматрицы каким-либо образом найдено оптимальное решение. Для простоты предположим, что это оптимальное решение сформировано из элементов главной диагонали A(n-1). Как же найти оптимальное решение для полной задачи? Поскольку для A(n-1) известно оптимальное решение, то возможны две альтернативы: добавить к известному решению «свободный» элемент ; заменить в оптимальном для матрицы A(n-1) решении элемент парой элементов и . Сформируем n разностей . Последняя из них для i=n есть ноль. Все остальные могут быть как положительными, так и отрицательными. Выберем из этих n разностей наименьшую. Если она будет равна нулю, то к решению для A(n-1) необходимо добавить элемент , если это отрицательное число, то из A(n-1) нужно исключить соответствующий минимальной разности элемент и ввести в решение элементы и . Очевидно, что для A(n) при этом будет получено оптимальное решение. В методах кратчайшего увеличивающего пути для получения A(n-1) используют матрицу A(n-2), для получения A(n-2) - A(n-3) и т.д. Первоначальную матрицу определяют в результате проведения подготовительного этапа. Оценки сложности для точных методов КУП - среднее время счёта задачи выбора; - коэффициент пропорциональности, зависящий от квалификации программиста, типа ЭВМ и т.д. |
<< | СОДЕРЖАНИЕ | >> |
---|