Курс предприним

Целевая функция или хотя бы одно из ограничений нелинейны (т

е. на графиках изображаются непрямыми (кривыми) линиями).

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

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

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

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

(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) Устанавливается оптимальное распределение ресурсов по регионам. Оно соответствует тем местам матрицы г, где стоят не-зависимые нули.

Курс предприним

Эта часть процесса…

Поскольку модель, как правило, не может учесть всех факторов, влияющих на решение задачи, то информация, полученная на выходе модели, должна подвергаться творческому анализу со стороны человека, и лишь после этого …

Рекламация — претензия…

п.). Рентабельность — отношение прибыли к затратам. Рейтинг — краткосрочная аренда имущества без права его приобретения. Репрезентация — представительство. Реет — остаток. Реституция — возврат сторонам сделки всего полученного по …

Документы, свидетельствующие о…

Различают частные закладные и закладные листы. Частная за-кладная — долговое обязательство, выданное заемщиком (например, ипотечным банком) кредитору и заверенное нотариально. В частной закладной должны быть указаны срок погашения кредита, величина …

Как с нами связаться:

Украина:
г.Александрия
тел./факс +38 05235  77193 Бухгалтерия
+38 050 512 11 94 — гл. инженер-менеджер (продажи всего оборудования)

+38 050 457 13 30 — Рашид - продажи новинок
e-mail: msd@inbox.ru
msd@msd.com.ua
Схема проезда к производственному офису:
Схема проезда к МСД

Оперативная связь

Укажите свой телефон или адрес эл. почты — наш менеджер перезвонит Вам в удобное для Вас время.