Экономико-математические методы (Абчук)

Последний, шестой план является оптимальным, ибо все раз­ ности между псевдостоимостями и стоимостями положительные.

Перепишем оптимальный план, исключив из него сколь угод­ но малые величины г (табл. 3.15).

Графически оптимальный план распределения проектов по­ казан на рис. 3.3.

Проекты

Рис. 3.3

Нелинейное программирование (планирование)

Нелинейное программирование (планирование) — математиче­ ские методы отыскания максимума или минимума функции при нали­ чии ограничений в виде неравенств или уравнений.

Максимизируемая (минимизируемая) функция представля­ ет собой принятый критерий эффективности решения задачи, со­ ответствующий поставленной цели. Он носит название целевой функции.

Ограничения характеризуют имеющиеся возможности ре­ шения задачи.

Целевая функция или хотя бы одно из ограничений нелинейны (т.е. на графиках изображаются непрямыми - кривыми - линиями).

Существо решения задач нелинейного программирования за­ ключается в том, чтобы найти условия, обращающие целевую функ­ цию в минимум или максимум.

Решение, удовлетворяющее условиям задачи и соответству­ ющее намеченной цели, называется оптимальным планом.

Нелинейное программирование служит для выбора наилуч­ шего плана распределения ограниченных ресурсов в целях реше­ ния поставленной задачи.

В общем виде постановка задачи нелинейного программирова­ ния сводится к следующему.

Условия задачи представляются с помощью системы нелинейных уравнений или неравенств, выражающих ограничения,

где Z,, Z2, ..., Zm - соответствующие функции, характеризующие условие решения поставленной задачи (ограничения); х - искомые величины, содержащие решение задачи.

Целевая функция задается в виде:

Причем по крайней мере одна из функций у, Z,, Z2,..., Zm ~ нелинейная.

Методами нелинейного программирования решаются зада­ чи распределения неоднородных ресурсов.

Пусть имеется m разнородных ресурсов, которые предпола­ гается реализовать для бизнеса в п регионах страны.

Известны оценочные возможности (вероятности) начать биз­ нес в j-м регионе (Р.), а также эффективности использования i-ro ре­ сурса в n-м регионе (ох).

Распределение ресурсов по регионам характеризуется так называемым параметром управления (h..):

JO, если i - й ресурс не направляется в j - й регион, ,j 11, если i - й ресурс направляется в j - й регион.

Необходимо распределить ресурсы по регионам таким об­ разом (выбирать такие значения h.), чтобы величина полной веро­ ятности достижения цели Р была максимальной:

Должно выполняться также ограничение

п

и

ЭТО ограничение означает, что каждый из m ресурсов обяза­ тельно должен назначаться в какой-либо из регионов.

Ниже приводится ряд типовых задач, решаемых с помощью нелинейного программирования, которые иллюстрируют его воз­ можности и приемы решения.

П р и м е р 3.5

Собственник располагает четырьмя видами разнородных ресурсов, которые можно реализовать для бизнеса в четырех реги­ онах страны (m = n = 4). Оценочные возможности (вероятности) начать бизнес в j-м регионе (Р.) заданы табл. 3.16.

Затем матрица А подвергается эквивалентному преобразо­ ванию, для чего:

-отыскивается в каждом ее столбце максимальный элемент

ивычитаются из него все элементы этого столбца;

-в каждой строке полученной таким образом матрицы отыс­ кивается минимальный элемент и вычитается из всех элементов

этой строки.

Полученная матрица обозначается А(0). В ней в каждой строке

икаждом столбце есть хотя бы один нуль.

В первом столбце матрицы А(0) выбирается любой нуль и отмечается звездочкой. Затем просматривается второй столбец и отмечается в нем звездочкой нуль лишь в том случае, если в этой же строке нуля со звездочкой нет. И так далее по всем столбцам. Полученные нули со звездочками называются независимыми.

Далее решение выполняется методом последовательных при­ ближений (итераций). Каждый шаг итерации увеличивает число независимых нулей на единицу. Решение оканчивается тогда, ког­ да число независимых нулей становится равным п. Поскольку в нашей матрице А(0) три независимых нуля, достаточно одной ите­ рации (так как п = 4).

Итерация выполняется в следующей последовательности.

1. В матрице А(0) (в общем случае в матрице, полученной в ре­ зультате предыдущей итерации) выделяются знаком "+" столбцы, со­ держащие независимые нули. Элементы матрицы, лежащие в выде­ ленных столбцах, называются выделенными (см. ниже матрицу а).

2.Смотрим, есть ли среди невыделенных элементов нули. Если есть, переходим к п. 3. Если нет - к п. 5.

3.Над любым невыделенным нулем ставится знак "'". Смот­ рим, есть ли 0* в строке, содержащей 0'. Если есть, выделяем знаком "+" эту строку (она называется выделенной) и снимаем (обводим круж­ ком) знак выделения над столбцом, содержащим 0* (см. ниже матрицу а). Затем возвращаемся к п. 2. Если нет - переходим к п. 4.

4.Начиная с 0', в строке которого на предыдущем шаге не был обнаружен 0*, строим цепочку с чередованием 0Ф и 0' до тех пор, пока это возможно. Переход от 0' к 0* совершается по столбцу,

аот 0* к 0' - по строке (см. ниже матрицу в).

Над нечетными элементами цепочки ставятся звездочки, а над четными они снимаются. При этом количество независимых нулей возрастает на один. Все плюсы и штрихи уничтожаются.

Если число 0* оказывается меньше п, возвращаемся к п. 1, если равно п - переходим к п. 6.

5.Выбирается минимальный элемент из всех невыделенных (в матрице а он подчеркнут). Этот элемент вычитается из всех не­ выделенных и прибавляется к элементам, находящимся на пере­ сечении выделенных строк и столбцов (см. матрицу а и б). Далее переходим к п. 2.

6.Устанавливается оптимальное распределение поисковых единиц по районам действий. Оно соответствует тем местам мат­ рицы г, где стоят независимые нули.

Вычисляется максимальное значение Р, равное сумме а., стоя­ щих на местах независимых нулей.

Последовательное преобразование матрицы А(0) примени­ тельно к данному примеру (матрицы а, б, в, г) показано ниже.

Соответствующая этому распределению максимальная ве­ роятность достижения цели равна сумме соответствующих элемен­ тов матрицы А.

Р = 0,132 + 0,260 + 0,174 + 0,015 = 0,581. Рассмотренный пример относится к случаю, когда m = п.

Если m < п, необходимо ввести п - m фиктивных поисковых еди-

ниц с нулевыми возможностями (ш. = 0 для i > m), сведя тем самым задачу к рассмотренному случаю.

П р и м е р 3.6

Имеется две группы разнородных ресурсов (т = 2), которые можно вложить в три инвестиционных проекта (п = 3). В первой груп­ пе шесть единиц ресурсов (N} = 6), во второй - десять (N2 = 10).

Степени важности проектов заданы табл. 3.19.

Таблица 3.19

Степени важности проектов

Эффективности вложений ресурсов различного рода (со ) заданы табл. 3.20.

Таблица 3.20

Эффективности вложений ресурсов различного рода в регионы

Распределение ресурсов по проектам характеризуется мат­ рицей А = || г ||, где х.. - количество ресурсов i-ro типа, назначае­ мых на j-й проект.

Необходимо распределить ресурсы по проектам таким об­ разом, чтобы суммарная эффективность была максимальной:

Должны выполняться такие ограничения:

п

£ * . . = N J ; i = l,2,...,m;

(3.47)

ху >0, i = l,2,...,m; j = l,2,...,n.

Решение

-В области изменения максимизируемой функции опреде­ ляется исходное допустимое решение, удовлетворяющее ограничи­ тельным условиям задачи;

-с помощью специального критерия проверяется, достаточ­ но ли близко полученное решение к оптимальному;

-если полученное отклонение больше требуемого, то путем построения так называемого возможного направления и определе­ ния в этом направлении конечного шага получают новое допусти­ мое решение, которое увеличивает значение максимизируемой функции;

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

где А(0) - матрица, характеризующая исходное распределение ре­ сурсов по проектам.

В качестве исходного (начального) распределения может быть взято любое (в том числе и произвольное) распределение (матрица А(0)), не противоречащее ограничительным условиям за­ дачи. Чем это начальное распределение окажется ближе к оптималь­ ному, тем меньше необходимое число итераций.

Мы можем здесь воспользоваться приближенным решени­ ем этой же задачи, полученным с помощью метода динамического программирования (см. ниже в данном параграфе).

Номера проектов (столбцы)

Далее осуществляется итеративный процесс; в результате вы­ полнения к итераций получается к-е приближение к оптимальному распределению: