Методы линейного программирования
Задачу выбора можно решать методами линейного программирования после преобразования задачи (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) и т.д.
Первоначальную матрицу определяют в результате проведения подготовительного этапа.
Оценки сложности для точных методов КУП
- среднее время счёта задачи выбора;
- коэффициент пропорциональности, зависящий от квалификации программиста, типа ЭВМ и т.д.
