Целевая функция или хотя бы одно из ограничений нелинейны (т
е. на графиках изображаются непрямыми (кривыми) линиями).
Существо решения задач нелинейного программирования заключается в том, чтобы найти условия, обращающие целевую функцию в минимум или максимум.
Решение, удовлетворяющее условиям задачи и соответствующее намеченной цели, называется оптимальным планом.
Нелинейное программирование служит для выбора наилучшего плана распределения ограниченных ресурсов в целях решения поставленной задачи.
В общем виде постановка задачи нелинейного программирования сводится к следующему.
(6.41)
Условия задачи представляются с помощью системы нелинейных уравнений или неравенств, выражающих ограничения, налагаемые на использование имеющихся ресурсов:
Z1 (Xj, х2,..., х„) > 0, Z2 (Xj, х2,..., хп) > 0,
(6.40)
Zm(xl, x2,...,xn) >0, при ХЇ > 0,
где Z\, Z2, ..., Zm — соответствующие функции, характеризующие условие решения поставленной задачи (ограничения); Xj — искомые величины, содержащие решение задачи. Целевая функция задается в виде:
У =Л*ь х2, ..., х„).
Причем по крайней мере одна из функций у, Z\, Z2, ..., Zm — нелинейная.
Методами нелинейного программирования решаются задачи распределения неоднородных ресурсов.
Пусть имеется т разнородных ресурсов, которые предполагается реализовать для бизнеса в п регионах страны.
Известны оценочные возможности (вероятности) начать бизнес в j-м регионе (Pj), а также эффективности использования /-го ресурса в п-м регионе (Щ).
Распределение ресурсов по регионам характеризуется так называемым параметром управления (Л;/):
0, если і-й ресурс не направляется в j-й регион,
1, если /-Й ресурс направляется
в j-й регион.
Необходимо распределить ресурсы по регионам таким образом (выбрать такие значения Л;/), чтобы величина полной вероятности достижения цели Рц была максимальной:
(6.42)
= max.
l-Ild-Vv
j=I
Должно выполняться также ограничение
п
Y^hy =1 ' = 1,2,..., m.
J=І
Это ограничение означает, что каждый из т ресурсов обязательно должен назначаться в какой-либо из регионов.
Ниже приводится ряд типовых задач, решаемых с помощью нелинейного программирования, которые иллюстрируют его воз-можности и приемы решения.
(6.43)
Пример 6.5
Собственник располагает четырьмя видами разнородных ресурсов, которые можно реализовать для бизнеса в четырех регионах страны (т = п = 4). Оценочные возможности (вероятности) начать бизнес в j-м регионе (Р;) заданы табл. 6.16.
Таблица 6.16
Вероятности начать бизнес в регионе
Регионы 1 2 3 4
Вероятности (Рj) 0,2 0,4 0,3 0,1
Эффективности при использовании /-го ресурса в j-м регионе
(Wjj) заданы табл. 6.17.
Таблица 6.17
Эффективность использования ресурсов
Номер ресурса Номер региона
1 2 3 4
1 0,81 0,65 0,32 0,47
2 0,66 0,51 0,19 0,75
3 0,32 0,17 0,39 0,15
4 0,43 0,46 0,58 0,60
Необходимо распределить ресурсы по регионам таким образом, чтобы полная вероятность достижения цели деятельности (успеха) оказалась максимальной. При этом каждый ресурс должен быть обязательно распределен в каком-либо регионе.
Решение
Рассмотрим наиболее простой случай, когда в каждый из регионов может быть направлено не более одной единицы ресурса. Задача нелинейного программирования при этом может быть сведена к одному из частных случаев задачи линейного программирования.
В нашем случае т = п. Решение при этом сводится к составлению матрицы А=||/),о),/1 и выбору из каждой ее строки и каждого столбца по одному элементу таким образом, чтобы сумма их оказалась наибольшей. Это один из частных случаев задачи линейного программирования.
Вычислительную процедуру удобно выполнить с помощью следующего метода.
Вначале рассчитываются элементы матрицы
1 2 3 4
162 260 96 47 1
132 204 57 75 2
64 68 117 15 3
86 184 174 60 4
А=|%...103||. Регионы (столбцы)
А =
Ресурсы (строки)
Затем матрица А подвергается эквивалентному преобразованию, для чего:
— отыскивается в каждом ее столбце максимальный элемент и вычитаются из него все элементы этого столбца;
— в каждой строке полученной таким образом матрицы отыс-кивается минимальный элемент и вычитается из всех элементов этой строки.
Полученная матрица обозначается А(()'. В ней в каждой строке и каждом столбце есть хотя бы один нуль.
В первом столбце матрицы А(()' выбирается любой нуль и отмечается звездочкой. Затем просматривается второй столбец и отмечается в нем звездочкой нуль лишь в том случае, если в этой же строке нуля со звездочкой нет. И так далее по всем столбцам.
Полученные нули со звездочками называются независимыми.
0* 0 78 28
30 56 117 0*
41 135 0* 3
76 76 0 15
Далее решение выполняется методом последовательных при-ближений (итераций). Каждый шаг итерации увеличивает число независимых нулей на единицу. Решение оканчивается тогда, когда число независимых нулей становится равным п. Поскольку в нашей матрице А(()' три независимых нуля, достаточно одной итерации (так как п = 4).
Итерация выполняется в следующей последовательности.
1) В матрице А(()' (в общем случае в матрице, полученной в ре-зультате предыдущей итерации) выделяются знаком «+» столбцы, содержащие независимые нули. Элементы матрицы, лежащие в выделенных столбцах, называются выделенными (см. ниже матрицу а).
2) Смотрим, есть ли среди невыделенных элементов нули. Если есть, переходим к п. 3. Если нет — к п. 5.
3) Над любым невыделенным нулем становится знак «'». Смотрим, есть ли 0* в строке, содержащей 0'. Если есть, выделяем знаком «+» эту строку (она называется выделенной) и снимаем (обводим кружком) знак выделения над столбцом, содержащим О* (см. ниже матрицу а). Затем возвращаемся к п. 2. Если нет — переходим к п. 4.
4) Начиная с 0', в строке которого на предыдущем шаге не был обнаружен 0*, строим цепочку с чередованием 0* и 0' до тех пор, пока это возможно. Переход от 0' к 0* совершается по столбцу, а от 0* к 0' — по строке (см. ниже матрицу в).
Над нечетными элементами цепочки ставятся звездочки, а над четными они снимаются. При этом количество независимых нулей возрастает на один. Все плюсы и штрихи уничтожаются.
Если число 0* оказывается меньше и, возвращаемся к п. 1, если равно п — переходим к п. 6.
5) Выбирается минимальный элемент из всех невыделенных (в матрице а он подчеркнут). Этот элемент вычитается из всех невы-деленных и прибавляется к элементам, находящимся на пересечении выделенных строк и столбцов (см. матрицы а и б). Далее переходим к п. 2.
6) Устанавливается оптимальное распределение ресурсов по регионам. Оно соответствует тем местам матрицы г, где стоят не-зависимые нули.
