Методы линейного программирования

Задачу выбора можно решать методами линейного программирования после преобразования задачи (3.1)…(3.3) к стандартной форме задачи линейного программирования. Такое преобразование можно осуществить по следующей схеме.

Матрицу исходных данных задачи выбора А порядка n транспонировать в матрицу С размера [1n²]

(3.4)

где A_i - i-я строка матрицы А.

Аналогично переменные сгруппировать в матрицу-строку

,

где - матрица-строка, составленная из следующих компонентов:

Ограничения (3.2), (3.3) преобразовываются к виду

, (3.5)

где

;

Матрица E_i содержит во всех строках, кроме i-й нулевые элементы, а в строке i - все элементы равны единице.

I - единичная матрица порядка n.

Матрица В имеет размер [n²1].

Получив (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) и т.д.

Первоначальную матрицу определяют в результате проведения подготовительного этапа.

Оценки сложности для точных методов КУП

- среднее время счёта задачи выбора;

- коэффициент пропорциональности, зависящий от квалификации программиста, типа ЭВМ и т.д.