Реферат: Математические методы в инновационном менеджменте

--PAGE_BREAK--
Сетевой график и правила его построения
Одним из математических методов современной теории управ­ления большими системами, широко применяемым на практике, яв­ляется метод сетевого планирования и управления (СПУ). Методы СПУ были разработаны сравнительно недавно. Так как они раз­рабатывались в разных странах, возникло несколько их разновид­ностей: СПУ—в СССР, РЕRТ и СРМ—в США и др.

Метод РЕRТ применяется в планировании научно-исследова­тельских и опытно-конструкторских разработок, для которых харак­терна неопределенность в оценке затрат времени, необходимого для выполнения отдельных операций (работ). Метод СРМ применяется тогда, когда оценки времени операций детерминированные.

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

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

В системах СПУ используются следующие, наиболее распро­страненные способы построения сетевых графиков:

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

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

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

В сетевом графике различают три вида событий: исходное, за­вершающее и промежуточное. Исходное — это такое событие, с ко­торого начинается выполнение комплекса операций. Завершающее соответствует достижению конечной цели, т. е. завершению комп­лекса операций. Сетевые графики с несколькими завершающими событиями называются многоцелевыми. К промежуточным относят­ся все прочие события.

События обозначаются кружками или другими геометрическими фигурами. Предполагается, что события не имеют продолжительно­сти и наступают как бы мгновенно.

Моментом свершения события считается момент окончания вы­полнения всех входящих в это событие операций.
<img width=«228» height=«88» src=«ref-2_699661513-3374.coolpic» v:shapes="_x0000_i1135">

Рис. 1.4.
<img width=«212» height=«111» src=«ref-2_699664887-3858.coolpic» v:shapes="_x0000_i1136">

Рис. 1.5.

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

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

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

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

При построении сетевых графиков необходимо соблюдать опре­деленные правила:

1) в сети не должно быть событий (кроме исходного), в которые не входит ни одна дуга;

2) не должно быть событий (кроме завершающего), из которых не выходит ни одной дуги;

3) сеть не должна содержать контуров;

4) любая пара событий сетевого графика может быть соединена не более чем одной дугой. Если изобразить одновременно (парал­лельно) выполняемые три различные операции b
, с, ас общими на­чальным и конечным событиями (рис. 1.4), то возникает путаница из-за того, что различные операции имеют одно и то же обозначе­ние (2,5). В этом случае рекомендуется ввести дополнительные со­бытия и соединить их с последующими фиктивными операциями (рис.1.5);

5) если какие-либо операции могут быть начаты до полного окончания непосредственно предшествующей им операции, то последнюю целесообразно представить как ряд последовательно вы­полняемых операций, завершающихся определенными событиями. Например, если операции с и dмогут быть начаты до полного окон­чания операции b
,то операцию b
 рекомендуется разбить на элемен­тарные операции b
1
,
b
2и b
зи представить выполнение всех опера­ций в виде графика, изображенного на рис. 1.6.

Для отражения технологической или ресурсной зависимости в выполнении операций применяют фиктивные операции.
 <img width=«246» height=«83» src=«ref-2_699668745-4102.coolpic» v:shapes="_x0000_i1137"> <img width=«193» height=«102» src=«ref-2_699672847-3865.coolpic» v:shapes="_x0000_i1138">

      Рис. 1.6.                               Рис.1.7.

Предполо­жим, что операция  с может выполняться после завершения опера­ций а и b
,а операция d
—только после завершения операции b
. Эта зависимость представлена на рис. 1.7, из которого видно, что операция с следует за операцией а и фиктивной операцией (2,3). В свою очередь операция (2,3) следует за операцией b
.Тогда в силу транзитивности выполнение операции bпредшествует выпол­нению операции с.

Построение сетевого графика начинается с составления списка операций (работ), подлежащих выполнению (см. табл. 1.4). После­довательность операций в списке произвольная. Порядок нумерации операций осуществляется в соответствии с последовательностью их записи в списке. Перечень операций тщательно продумывается и в зависимости от конкретных условий с определенной степенью де­тализируется. Операции, включенные в список, характеризуются определенной продолжительностью, которая устанавливается на ос­нове действующих нормативов или по аналогии с ранее выполняв­шимися операциями. Такие временные оценки называются детерми­нированными. Если же нормативные данные временных оценок опе­раций отсутствуют, то определяются вероятностные оценки.

После составления списка операций приступают к процедуре по­строения сети.

Пример.Необходимо построить укрупненный сетевой график выполнения комплекса операций по реконструкции цеха. Список операций представлен в табл. 1.4. Сетевой график комплекса операций изображен на рис. 1.8.

Решение.Опе­рации графика, за исключением операций (2,3) и (5,6), являются действительными. Числа в скобках, приписанные дугам, означают продолжитель­ность выполнения соответствующих операций. Операции а1 и а2 не опираются ни на какие операции, следовательно, поэтому на графике изобразим их дугами, вы­ходящими из события (1), означающего начало выполнения комплекса операций. Операции а3, а5 и а6опираются на операцию а1, поэтому на графике эти дуги непосредственно следуют за дугой а1. Событие (2) озна­чает момент окончания операции а1 и начала операций, представленных дугами, выходящими из этого события. Операция а4, опирается на операции а1 и а2. Гра­фически это условие отражено посредством последовательного изображения опе­раций (1,3) и (3,4) и введения фиктивной операции (2,3). Событие (3) инци­дентно операциям (1,3) и (2,3), следовательно, моментом свершения события (3} будет такой момент, к которому будут выполнены все входящие в это собы­тие операции и может быть начата операция, отраженная дугой, выходящей из него. Аналогично с учетом технологии выполнения изображены на графике остальные операции. Завершающее событие (9) означает момент окончания вы­полнения всего комплекса операций по реконструкции цеха. Шифры операций (см. табл. 1.4) состоят из номеров начального и конечного событий и практиче­ски в список заносятся после составления графика.

Таблица 1.4

Список операций для построения сетевого графика

Опера-ция

Шифр операции

Наименование операции

Опирается на операции

Продолжитель-ность, дни

<img width=«20» height=«28» src=«ref-2_699676712-190.coolpic» v:shapes="_x0000_i1139">

(1,2)

Подготовительные работы

-

5

<img width=«23» height=«28» src=«ref-2_699676902-196.coolpic» v:shapes="_x0000_i1140">

(1,3)

Демонтаж старого оборудования

-

3

<img width=«21» height=«29» src=«ref-2_699677098-194.coolpic» v:shapes="_x0000_i1141">

(2,6)

Ремонтные строительно-монтажные работы

<img width=«20» height=«28» src=«ref-2_699676712-190.coolpic» v:shapes="_x0000_i1142">

30

<img width=«23» height=«28» src=«ref-2_699677482-197.coolpic» v:shapes="_x0000_i1143">

(3,4)

Подготовка фундамента под новое оборудование

<img width=«20» height=«28» src=«ref-2_699676712-190.coolpic» v:shapes="_x0000_i1144">, <img width=«23» height=«28» src=«ref-2_699676902-196.coolpic» v:shapes="_x0000_i1145">

16

<img width=«21» height=«29» src=«ref-2_699678065-190.coolpic» v:shapes="_x0000_i1146">

(2,4)

Подготовка к монтажу нового оборудования

<img width=«20» height=«28» src=«ref-2_699676712-190.coolpic» v:shapes="_x0000_i1147">

10

<img width=«21» height=«29» src=«ref-2_699678445-194.coolpic» v:shapes="_x0000_i1148">

(2,5)

Электротехнические работы

<img width=«20» height=«28» src=«ref-2_699676712-190.coolpic» v:shapes="_x0000_i1149">

12

<img width=«23» height=«29» src=«ref-2_699678829-192.coolpic» v:shapes="_x0000_i1150">

(4,5)

Монтаж нового оборудования

<img width=«23» height=«28» src=«ref-2_699677482-197.coolpic» v:shapes="_x0000_i1151">, <img width=«21» height=«29» src=«ref-2_699678065-190.coolpic» v:shapes="_x0000_i1152">

8

<img width=«21» height=«29» src=«ref-2_699679408-195.coolpic» v:shapes="_x0000_i1153">

(5,7)

Подключение оборудования к электросети

<img width=«21» height=«29» src=«ref-2_699678445-194.coolpic» v:shapes="_x0000_i1154">, <img width=«23» height=«29» src=«ref-2_699678829-192.coolpic» v:shapes="_x0000_i1155">

2

<img width=«21» height=«29» src=«ref-2_699679989-195.coolpic» v:shapes="_x0000_i1156">

(7,8)

Наладка и технологические испытания оборудования

<img width=«21» height=«29» src=«ref-2_699679408-195.coolpic» v:shapes="_x0000_i1157">

6

<img width=«27» height=«29» src=«ref-2_699680379-205.coolpic» v:shapes="_x0000_i1158">

(6,8)

Отделочные работы

<img width=«21» height=«29» src=«ref-2_699677098-194.coolpic» v:shapes="_x0000_i1159">, <img width=«21» height=«29» src=«ref-2_699678445-194.coolpic» v:shapes="_x0000_i1160">, <img width=«23» height=«29» src=«ref-2_699678829-192.coolpic» v:shapes="_x0000_i1161">

8

<img width=«25» height=«28» src=«ref-2_699681164-201.coolpic» v:shapes="_x0000_i1162">

(8,9)

Приемка цеха в эксплуатацию

<img width=«21» height=«29» src=«ref-2_699679989-195.coolpic» v:shapes="_x0000_i1163">, <img width=«27» height=«29» src=«ref-2_699680379-205.coolpic» v:shapes="_x0000_i1164">

1



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

Построение сетевых графиков скоротечных комплексов опера­ций, когда из-за недостатка времени нет возможности производить оптимизационные расчеты, осуществляется с учетом технологиче­ских и ресурсных ограничений. Построение графиков нескоротечных комплексов операций, когда достаточно времени для их исследова­ния, выполняется лишь с учетом технологических ограничений. Та­кой подход обеспечивает минимальную продолжительность выпол­нения комплекса операций. После построения графика рассчитыва­ются его временные параметры и производится оптимизация по ресурсам или другим показателям, для чего используются формаль­ные методы оптимизации.
<img width=«418» height=«149» src=«ref-2_699681765-12573.coolpic» v:shapes="_x0000_i1165">

Рис. 1.8.

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

Для управления ходом выполнения комплекса операций, пред­ставленного сетевой моделью, оперирующая сторона должна распо­лагать количественными параметрами элементов сети. К таким па­раметрам относятся: продолжительность выполнения всего комп­лекса операций, сроки выполнения отдельных операций и их ре­зервы времени. Важнейшим параметром сетевого графика является также критический путь. Различают следующие виды путей: пол­ный, предшествующий событию, следующий за событием.

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

Предшествующий событию путь — это путь от исходного собы­тия до данного.

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

Критическим называется полный путь, имеющий наибольшую продолжительность во времени, Операции и события, принадлежа­щие критическому пути, называются соответственно критическими операциями и критическими событиями. Суммарная продолжитель­ность операций, принадлежащих критическому пути, равна крити­ческому времени <img width=«20» height=«25» src=«ref-2_699694338-103.coolpic» v:shapes="_x0000_i1166">выполнения комплекса операций в целом. На графике критический путь, как правило, выделяется жирной линией.

Расчет параметров сетевого графика может осуществляться раз­личными методами. Рассмотрим один из них.

Предположим, что продолжительности выполнения операций <img width=«16» height=«25» src=«ref-2_699694441-98.coolpic» v:shapes="_x0000_i1167">известны и приписаны у соответствующих дуг графика (рис. 1.9).

Определим, прежде всего, ожидаемые (ранние) сроки свершения событий <img width=«13» height=«24» src=«ref-2_699694539-89.coolpic» v:shapes="_x0000_i1168"> сетевого графика. Исходное событие означает момент начала выполнения комплекса операций, следовательно, <img width=«40» height=«23» src=«ref-2_699694628-127.coolpic» v:shapes="_x0000_i1169">. Со­бытие (2) свершится, очевидно, спустя 2 ед. времени после сверше­ния события (1), так как время выполнения операции (1, 2) равно 2.

Следовательно, <img width=«148» height=«23» src=«ref-2_699694755-244.coolpic» v:shapes="_x0000_i1170">. Событию (3) предшествуют два пути: <img width=«76» height=«23» src=«ref-2_699694999-171.coolpic» v:shapes="_x0000_i1171"> и <img width=«101» height=«23» src=«ref-2_699695170-197.coolpic» v:shapes="_x0000_i1172">. Продолжительность первого пути равна 1 ед. времени, а второго 2 ед. времени, так как <img width=«125» height=«24» src=«ref-2_699695367-225.coolpic» v:shapes="_x0000_i1173">. Продолжительность второго пути можно найти добавле­нием к ожидаемому сроку свершения события (2) времени выполнения операции (2.3), т.е.<img width=«121» height=«24» src=«ref-2_699695592-222.coolpic» v:shapes="_x0000_i1174">. Поскольку событие (3) может свершиться не раньше момента окончания всех входящих в него операций, то <img width=«311» height=«24» src=«ref-2_699695814-475.coolpic» v:shapes="_x0000_i1175">.
<img width=«531» height=«229» src=«ref-2_699696289-15558.coolpic» v:shapes="_x0000_i1176">

Рис. 1.9.

В событие (4) входят две дуги, исходящие из событий (1) и (3), -для которых ожидаемые сроки свершения найдены. Следова­тельно, ожидаемый срок свершения события (4) <img width=«313» height=«24» src=«ref-2_699711847-473.coolpic» v:shapes="_x0000_i1177">
 . Аналогично находятся ожидаемые сроки свершения событий (5), (6) и (7). Значения <img width=«71» height=«27» src=«ref-2_699712320-163.coolpic» v:shapes="_x0000_i1178">, при­писаны соответствующим событиям на рис. 1.9.

Общую формулу для нахождения ожидаемых сроков свершения событий можно записать так:

<img width=«40» height=«23» src=«ref-2_699694628-127.coolpic» v:shapes="_x0000_i1179">;

<img width=«204» height=«25» src=«ref-2_699712610-326.coolpic» v:shapes="_x0000_i1180">

 для <img width=«86» height=«29» src=«ref-2_699712936-426.coolpic» v:shapes="_x0000_i1181">  — подмножества дуг сети, входящих в событие (j
).

Ожидаемый срок свершения события (7)  <img width=«47» height=«24» src=«ref-2_699713362-135.coolpic» v:shapes="_x0000_i1182">совпадает с кри­тическим временем (суммарной продолжительностью операций, принадлежащих критическому пути). Возвращаясь теперь от завер­шающего события к исходному, выделим операции, принадлежащие критическому пути.  Из трех операций, входящих в событие (7), <img width=«62» height=«30» src=«ref-2_699713497-195.coolpic» v:shapes="_x0000_i1183"> определила операция (5,7), выполнение которой начинается после свершения события (5) и продолжается 3 ед. времени <img width=«136» height=«24» src=«ref-2_699713692-246.coolpic» v:shapes="_x0000_i1184">. Момент свершения события (5) определила опе­рация (3, 5), так как<img width=«131» height=«24» src=«ref-2_699713938-240.coolpic» v:shapes="_x0000_i1185">. В свою очередь момент свер­шения события (3) определила операция (2, 3), а события (2) — операция (1, 2). Эти операции на графике рис. 1.9 выделены жир­ной линией. Таким образом, критический путь <img width=«151» height=«25» src=«ref-2_699714178-249.coolpic» v:shapes="_x0000_i1186">. Увеличение времени выполнения любой операции, принадлежащей критическому пути, ведет к увеличению времени выполнения комплекса операций. Увеличение же времени выполнения или за­держка с выполнением некритических операций может не отразить­ся на сроке свершения завершающего события. Например, время выполнения операции (4, 5) может быть увеличено или начало ее выполнения может быть отсрочено на 1 ед. времени, и это не отра­зится на сроке свершения события (5), а, следовательно, и всего комплекса операций.

Начало выполнения операции (4, 7) может быть отсрочено на 3 ед. времени. Отсюда следует, что для события (4), не лежащего на критическом пути, существует предельный (поздний) срок свер­шения. Обозначим  предельный срок свершения любого события сетевого графика через <img width=«65» height=«27» src=«ref-2_699714427-165.coolpic» v:shapes="_x0000_i1187">. Примем,  что ожидаемый и пре­дельный сроки свершения завершающего события (п) совпадают <img width=«57» height=«25» src=«ref-2_699714592-159.coolpic» v:shapes="_x0000_i1188">, тогда предельный срок свершения любого события сете­вого графика равен минимальной разности между предельными сроками окончания операций, исходящих из данного события, и вре­менем выполнения соответствующих операций. Нахождение пре­дельного срока осуществляется по формуле

<img width=«44» height=«25» src=«ref-2_699714751-137.coolpic» v:shapes="_x0000_i1189">;

<img width=«189» height=«28» src=«ref-2_699714888-326.coolpic» v:shapes="_x0000_i1190">,

для  <img width=«61» height=«27» src=«ref-2_699715214-307.coolpic» v:shapes="_x0000_i1191">  — подмножества дуг сети, исходящих из события <img width=«20» height=«21» src=«ref-2_699715521-102.coolpic» v:shapes="_x0000_i1192">.

В нашем примере <img width=«76» height=«25» src=«ref-2_699715623-171.coolpic» v:shapes="_x0000_i1193">. Определим этот показатель для оставшихся событий. Из события (5) исходит одна операция, следова­тельно, <img width=«153» height=«25» src=«ref-2_699715794-254.coolpic» v:shapes="_x0000_i1194">. Аналогично <img width=«109» height=«25» src=«ref-2_699716048-216.coolpic» v:shapes="_x0000_i1195">. Из события (4) исходят три операции, поэтому <img width=«409» height=«25» src=«ref-2_699716264-589.coolpic» v:shapes="_x0000_i1196">. Аналогично находим, что <img width=«132» height=«25» src=«ref-2_699716853-243.coolpic» v:shapes="_x0000_i1197"> (на рис. 1.9 предельные сроки свершения со­бытий указаны в скобках). Для критических событий эти сроки сов­падают с ожидаемыми.

Некритические события имеют резервы времени, которые пока­зывают, на какой предельно допустимый срок может задержаться свершение событий без изменения срока свершения завершающего события. Резерв времени <img width=«19» height=«24» src=«ref-2_699717096-101.coolpic» v:shapes="_x0000_i1198"> события (i
)равен разности между пре­дельным и ожидаемым сроком его свершения:

<img width=«72» height=«25» src=«ref-2_699717197-165.coolpic» v:shapes="_x0000_i1199"> .


Ожидаемые и предельные сроки свершения событий находятся в диалектическом единстве со сроками начала и окончания операций:

ранний срок начала выполнения операции (i, j
) равен ожидаемому сроку свершения (i
)-roсобытия <img width=«65» height=«27» src=«ref-2_699717362-180.coolpic» v:shapes="_x0000_i1200">;

поздний срок окончания операции совпадает с поздним сроком свершения ее конечного собы­тия <img width=«65» height=«27» src=«ref-2_699717542-185.coolpic» v:shapes="_x0000_i1201">;

поздний срок начала выполнения операции равен разности между предельным сроком свершения ее конечного события и продолжительностью <img width=«93» height=«27» src=«ref-2_699717727-219.coolpic» v:shapes="_x0000_i1202">;

ранний срок окончания опера­ции равен сумме ожидаемого срока свершения ее начального события и продолжительности <img width=«93» height=«27» src=«ref-2_699717946-217.coolpic» v:shapes="_x0000_i1203">.

Сроки выполнения операций находятся в границах, определяемых параметрами: <img width=«141» height=«34» src=«ref-2_699718163-402.coolpic» v:shapes="_x0000_i1204">. Следовательно, операции, как и со­бытия, могут иметь некоторый резерв времени. Различают четыре разновидности резервов времени операций: полный, свободный, част­ный первого вида и частный второго вида.

Полный резерв времени операции <img width=«21» height=«27» src=«ref-2_699718565-115.coolpic» v:shapes="_x0000_i1205"> показывает, насколько можно сдвинуть начало выполнения операции или увеличить ее продолжительность, не изменяя ожидаемого срока свершения на­чального события, при условии, что конечное для данной операции событие свершится не позднее своего предельного срока. Величина полного резерва времени вычисляется по формуле:

<img width=«181» height=«27» src=«ref-2_699718680-338.coolpic» v:shapes="_x0000_i1206">.

Свободный резерв времени операции <img width=«21» height=«27» src=«ref-2_699719018-115.coolpic» v:shapes="_x0000_i1207"> показывает, насколь­ко можно увеличить продолжительность или отсрочить начало вы­полнения операции (i
,
j
) при условии, что начальное и конечное ее события свершаются в ожидаемое время:

<img width=«180» height=«27» src=«ref-2_699719133-322.coolpic» v:shapes="_x0000_i1208">.

Частный резерв времени первого вида <img width=«21» height=«27» src=«ref-2_699719455-113.coolpic» v:shapes="_x0000_i1209">— это запас времени, которым можно располагать при выполнении операции (i
,
j
) в предположении, что начальное и конечное ее события свершаются в предельные сроки;

<img width=«181» height=«27» src=«ref-2_699719568-335.coolpic» v:shapes="_x0000_i1210">.

Частный резерв времени второго вида <img width=«21» height=«27» src=«ref-2_699719903-115.coolpic» v:shapes="_x0000_i1211"> — это запас времени, которым можно располагать при выполнении операции (i
,
j
) в пред­положении, что ее начальное событие свершится в предельное, а конечное — в ожидаемое время. Для некоторых операций интервал времени между предельным сроком свершения начального события и ожидаемым сроком свершения конечного события может быть меньше их продолжительности. В этом случае<img width=«21» height=«27» src=«ref-2_699719903-115.coolpic» v:shapes="_x0000_i1212">,- принимается рав­ным нулю. Определяется частный резерв времени второго вида по формуле:

<img width=«161» height=«27» src=«ref-2_699720133-313.coolpic» v:shapes="_x0000_i1213">.<img width=«12» height=«23» src=«ref-2_699720446-73.coolpic» v:shapes="_x0000_i1214">

Найдем резервы времени операции (4, 6) сетевого графика (см. рис. 1.9):

<img width=«236» height=«25» src=«ref-2_699720519-393.coolpic» v:shapes="_x0000_i1215">;

<img width=«229» height=«25» src=«ref-2_699720912-363.coolpic» v:shapes="_x0000_i1216">;

<img width=«236» height=«25» src=«ref-2_699721275-386.coolpic» v:shapes="_x0000_i1217">;

<img width=«295» height=«25» src=«ref-2_699721661-459.coolpic» v:shapes="_x0000_i1218">.
 Расчеты на вероятностных сетях

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

Расчет параметров и анализ сетей случайной структуры связан с известными трудностями. Поэтому на практике обычно применя­ются детерминированные сети со случайными временными оценка­ми операций. Такие сети называются вероятностными. При иссле­довании вероятностных сетей могут встретиться два случая:

1)  опе­рации не являются новыми, и мы приближенно знаем для каждой из них функцию распределения продолжительности выполнения;

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

В первом случае по известной функции распределения нетрудно определить среднее значение продолжительности выполнения каж­дой операции (математическое ожидание) и дисперсию. Во втором случае применяется метод усреднения. Исходными данными для метода усреднения являются вероятностные оценки продолжитель­ности каждой операции:     

а — минимальная продолжительность (оп­тимистическая оценка) операции;

в— максимальная продолжи­тельность;

т -вероятная продолжительность (мода) операции.

Эти оценки времени задаются ответствен­ным исполнителем или группой экспертов.

<img width=«304» height=«148» src=«ref-2_699722120-6350.coolpic» v:shapes="_x0000_i1219">

Рис. 1.10

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

Функция плотности бета-распределения (рис. 1,10) аналитически представима в виде

<img width=«224» height=«51» src=«ref-2_699728470-594.coolpic» v:shapes="_x0000_i1220"> 

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

<img width=«132» height=«51» src=«ref-2_699729064-443.coolpic» v:shapes="_x0000_i1221"> =1.

По известной функции распределения   f(t)   находятся числовые характеристики операций:

среднее значение (математическое ожидание) продолжительно­сти операции

<img width=«252» height=«51» src=«ref-2_699729507-706.coolpic» v:shapes="_x0000_i1222">;

дисперсия

<img width=«175» height=«51» src=«ref-2_699730213-520.coolpic» v:shapes="_x0000_i1223">’

Статистический анализ, проведенный эмпирико-экспериментальным путем разработчиками математического аппарата системы PERT, позволил установить, что    <img width=«64» height=«21» src=«ref-2_699730733-157.coolpic» v:shapes="_x0000_i1224">. Следовательно,
                                    <img width=«96» height=«41» src=«ref-2_699730890-259.coolpic» v:shapes="_x0000_i1225">;                                                 (1.1)

                                   <img width=«103» height=«49» src=«ref-2_699731149-348.coolpic» v:shapes="_x0000_i1226">.                                                  (1.2)

После определения математических ожиданий продолжительно­стей операций по формуле (1.1) проводится расчет временных пара­метров сети, как и в детерминированном случае. Длительность кри­тического пути рассматривают как математическое ожидание слу­чайной величины tкр:

<img width=«135» height=«39» src=«ref-2_699731497-472.coolpic» v:shapes="_x0000_i1227">.

Дисперсию продолжительности пути считают равной сумме дис­персий продолжительностей операций, находящихся на критиче­ском пути:

<img width=«120» height=«40» src=«ref-2_699731969-494.coolpic» v:shapes="_x0000_i1228">.

Расчет временных параметров сети по средним значениям продолжительностей операций не позволяет строго опре­делить срок завершения комплекса операций. Откло­нение случайных величин<img width=«16» height=«25» src=«ref-2_699694441-98.coolpic» v:shapes="_x0000_i1229"> от их средних значений <img width=«17» height=«25» src=«ref-2_699732561-102.coolpic» v:shapes="_x0000_i1230">может быть как в большую, так и в меньшую сторону. Поэтому фактическая продолжительность выполнения комплекса операций tф может быть больше или меньше tкр. В связи с этим представляет большой инте­рес оценка вероятности завершения комплекса операций к опреде­ленному сроку, которая зависит от дисперсии  <img width=«41» height=«25» src=«ref-2_699732663-161.coolpic» v:shapes="_x0000_i1231">  продолжительности критического пути. При одних значениях величин    мо­жет быть один критический путь, при других — другой. Однако если продолжительности работ отклоняются от своих средних значений на такую малую величину, что критический путь не изменяется, и если на критическом пути лежит значительное число операций (20 или более), то на основании центральной предельной теоремы мож­но приближенно считать, что его продолжительность подчиняется нормальному закону распределения с параметрами <img width=«21» height=«25» src=«ref-2_699732824-105.coolpic» v:shapes="_x0000_i1232"> и<img width=«41» height=«25» src=«ref-2_699732663-161.coolpic» v:shapes="_x0000_i1233">. Тогда вычисление вероятности того, что фактическая продолжи­тельность выполнения комплекса операций tф меньше планового ди­рективного срока Тпл, производится по формуле:

<img width=«160» height=«25» src=«ref-2_699733090-313.coolpic» v:shapes="_x0000_i1234"> ,                                           (1.3)
где <img width=«136» height=«52» src=«ref-2_699733403-497.coolpic» v:shapes="_x0000_i1235">  — функция Лапласа, значения которой берутся из таблиц (Приложение 1):

<img width=«87» height=«51» src=«ref-2_699733900-257.coolpic» v:shapes="_x0000_i1236"> ,

а <img width=«93» height=«29» src=«ref-2_699734157-260.coolpic» v:shapes="_x0000_i1237">  — среднеквадратическое отклонение.

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

Рассмотрим подход к определению математического ожидания <img width=«21» height=«25» src=«ref-2_699732824-105.coolpic» v:shapes="_x0000_i1238">и дисперсии <img width=«37» height=«25» src=«ref-2_699734522-156.coolpic» v:shapes="_x0000_i1239"> операций (ij) сетевого проекта на основе двух оценок: оптимистической а и пессимистической b
.Многочисленные эмпирико-экспериментальные исследования двухоценочной методи­ки показали, что в бета-распределении величины p и q, определенные для большого количества сетевых моделей, близки к постоян­ным значениям   p=1, q=2. Выбрав их в качестве стандартных по­казателей степени, получим функцию, которая относится к классу бета-распределений и имеет следующие параметры:

математическое ожидание

                                           <img width=«153» height=«51» src=«ref-2_699734678-490.coolpic» v:shapes="_x0000_i1240"> ;                                         (1.4)

дисперсию

                                              <img width=«223» height=«52» src=«ref-2_699735168-671.coolpic» v:shapes="_x0000_i1241">                               (1.5)

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

Пример.Найти критическое время tкр  выполнения комплекса операций, представленного на рис. 1.11, используя средние оценки продолжительности и ди­сперсию, а также определить:

1) вероятность выполнения комплекса операций за

а)   Тпл =35 дней;

б)   Тпл =42 дня,

2) время, за которое комплекс операций будет выполнен с вероятностью, не меньшей

а) Р=0.75;

б) Р=0.35,

3)  вероят­ность завершения операции (2. 5) в 8-й день.

Оптимистическая оценка  <img width=«22» height=«27» src=«ref-2_699735839-105.coolpic» v:shapes="_x0000_i1242"> и пес­симистическая оценка <img width=«19» height=«25» src=«ref-2_699735944-106.coolpic» v:shapes="_x0000_i1243"> для каждой операции заданы в табл. 1.6. Случайные от­клонения времени выполнения операций от математических ожиданий не меняют критического пути.

<img width=«412» height=«171» src=«ref-2_699736050-8732.coolpic» v:shapes="_x0000_i1244">

Рис. 1.11.

Решение

По формулам (3.4), (3.5) вычислим  <img width=«17» height=«25» src=«ref-2_699732561-102.coolpic» v:shapes="_x0000_i1245">и  <img width=«41» height=«25» src=«ref-2_699744884-145.coolpic» v:shapes="_x0000_i1246">и занесем в две правые гра­фы табл. 1.5.

Осуществив расчет продолжительности критического пути по средним оценкам вре­мени (приписаны дугам графика), получим <img width=«53» height=«25» src=«ref-2_699745029-150.coolpic» v:shapes="_x0000_i1247">  дней. Такой же расчет по оптимистиче­ским оценкам приводит к величине <img width=«85» height=«25» src=«ref-2_699745179-193.coolpic» v:shapes="_x0000_i1248">дня, по пессимистическим  — <img width=«89» height=«25» src=«ref-2_699745372-199.coolpic» v:shapes="_x0000_i1249">дня. Практи­чески же комплекс операций может быть выполнен с некоторой вероятностью в лю­бой срок из интервала [27,5...53,75].

Критический путь включает 6 операций, поэтому при определении доверительного интервала для продолжительности проекта по нормальному закону распределения ошибка окажется значительной. Заметим, что практически все руководства по методам СПУ этот факт игнорируют, вводя в заблуждение и читателя, и лиц, в интересах которых проводится расчет.
Таблица 1.5

Исходные параметры

Расчетные параметры

(i,j)

<img width=«20» height=«25» src=«ref-2_699745571-103.coolpic» v:shapes="_x0000_i1250">

<img width=«19» height=«25» src=«ref-2_699735944-106.coolpic» v:shapes="_x0000_i1251">

<img width=«17» height=«25» src=«ref-2_699732561-102.coolpic» v:shapes="_x0000_i1252">

<img width=«23» height=«25» src=«ref-2_699745882-113.coolpic» v:shapes="_x0000_i1253">

(1,2)

1

3,5

2

0,25

(2,3)

2

4,5

3

0,25

(2,4)

2,5

6,25

4

0,56

(2,5)

4

6,5

5

0,25

(3,7)

1,5

2,75

2

0,063

(4,6)

5

10

7

1

(5,8)

5,4

8,25

6

0,56

(6,7)

3

5,5

4

0,25

(7,8)

8

10,5

9

0,25

(8,9)

8

18

12

4


    продолжение
--PAGE_BREAK--Используя функцию Лапласа, получим
<img width=«175» height=«44» src=«ref-2_699745995-397.coolpic» v:shapes="_x0000_i1254"> 

и вероятность завершить проект за 38 дней:

<img width=«349» height=«48» src=«ref-2_699746392-739.coolpic» v:shapes="_x0000_i1255">.

Аналогично определяется вероятность выполнения комплекса операций за Тпл = 42 дня:

<img width=«439» height=«44» src=«ref-2_699747131-827.coolpic» v:shapes="_x0000_i1256">.

Определим теперь время, за которое комплекс операций будет выполнен с вероятностью, не меньшей чем Р = 0,75.

Величине Ф(u) = P – 0,5 = 0,25 соответствует значение u = 0,86.

Следовательно,

<img width=«303» height=«29» src=«ref-2_699747958-1035.coolpic» v:shapes="_x0000_i1257">дней.

ДляР = 0,35 имеемФ(u) = 0,35 – 0,5 = -0,15 и <img width=«82» height=«26» src=«ref-2_699748993-343.coolpic» v:shapes="_x0000_i1258">. Таким образом,

<img width=«252» height=«24» src=«ref-2_699749336-413.coolpic» v:shapes="_x0000_i1259"> дней.

Ожидаемый срок свершения 5-го события t5 = 7. Сумма дисперсий операций, принадлежащих пути (1 – 2 – 5), ведущему к 5-му событию,

<img width=«223» height=«24» src=«ref-2_699749749-375.coolpic» v:shapes="_x0000_i1260"> .

Таким образом,

<img width=«515» height=«53» src=«ref-2_699750124-1048.coolpic» v:shapes="_x0000_i1261">.

Следовательно, при расчетах с использованием нормального закона с вероятностью 0,921 операция (2, 5) будет завершена в плановый срок.
Обзор методов линейного программирования
Большое число экономических задач сводится к линейным ма­тематическим моделям. Традиционно оптимизационные линейные математические модели называются задачами линейного програм­мирования. Этот термин появился в конце 30-х годов, когда про­граммирование на компьютере еще не было развито, и соответ­ствует не очень удачному переводу с английского. Под линейным программированием понимается линейное плани­рование, т.е. получение оптимального плана—решения в задачах с линейной структурой. В данной книге встречаются также терми­ны «нелинейное программирование» и «динамическое програм­мирование», которые аналогичным образом подразумевают полу­чение оптимального решения задач с соответствующей структурой.

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

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

Задача. Некоторому заводу требуется составить опти­мальный план выпуска двух видов изделий при определенных возможностях четырех видов машин. План выпуска этих изде­лий надо составить так, чтобы от реализации изготовленной про­дукции завод получил наибольшую прибыль. Оба вида изделий последовательно обрабатываются этими машинами. В плане должно быть предусмотрено, что первая машина ежедневно мо­жет обрабатывать эту продукцию лишь в течение8 ч, вторая— 12ч, третья —12ч, четвертая —9 ч.

В табл. 1.6 указано время, необходимое для обработки каждого изделия этих двух видов (в часах). Нуль означает, что изделие машинами данного вида обрабатывать не надо.

Таблица 1.6

Завод от реализации одного изделия I вида получает 4 руб., а от реализации одного изделия II вида—6 руб. прибыли.

Построим математическую модель этой задачи. Пусть      — число изделий I вида,      — число изделий II вида. Так как машины каж­дого вида (1, 2, 3, 4) могут обрабатывать продукцию не более (18, 12, 12, 9) часов соответственно, то получаем следующую систему ограничений:

<img width=«122» height=«76» src=«ref-2_699751172-4431.coolpic» v:shapes="_x0000_i1262">                                              (1.6)

Общая прибыль может быть выражена как
<img width=«121» height=«25» src=«ref-2_699755603-1577.coolpic» v:shapes="_x0000_i1263">                                               (1.7)
где    х1        и   х2   удовлетворяют условиям задачи (1.6).
Таким образом, построенная математическая модель данной за­дачи состоит из системы неравенств (1.6), на множестве решений ко­торой надо найти наибольшее значение целевой функции (1.7).

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

Максимизировать (минимизировать) функцию

<img width=«85» height=«40» src=«ref-2_699757180-1590.coolpic» v:shapes="_x0000_i1264">                                                (1.8)

при ограничениях

<img width=«193» height=«148» src=«ref-2_699758770-6571.coolpic» v:shapes="_x0000_i1265">                     (1.9)-(1.11)

                    

Функция (1.8) — линейная, ограничения (1.9) — (1.11) — линейные. Задача содержит п переменных и т ограничений.

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

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

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

1) Записывают уравнения прямых, соответствующих ограничениям, и строят их на плоскости.

2) Определяют области, в которых выполняются ограничения задачи. Для   этого выбирают произвольную точку на плоскости   ХОУ      и подстав­ляют ее координаты в левую часть одного из неравенств. Если неравенство верно, то искомая полуплоскость находится с той же стороны    от прямой, что и точка; в противном случае искомая полуплоскость лежит с противоположной стороны от прямой. Эти действия последовательно выполняются для всех неравенств, отражающих ограничения задачи. Определяют область допустимых решений задачи, как область пересечения т полуплоскостей, соответствующих т ограничениям.

3) Определяют направление возрастания (убывания) целевой функции. Это можно сделать двумя способами. Можно построить вектор—нормаль, который показывает направление возрастания функции. В противоположном ему направлении функция убывает. Можно просто построить две линии уровня для целевой функции, приравняв ее двум  произвольным константам, и по их расположению определить направление возрастания (убывания) целевой функции.

4) Определяют граничную точку (точки) области допустимых решений, в которых целевая функция принимает максимальное или минимальное значение.

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

 Наиболее распространенный метод решения задач линейного программирования — это симплекс-метод.

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

Для применения симплекс-метода задачу следует записать в канонической форме:

<img width=«198» height=«29» src=«ref-2_699765341-2282.coolpic» v:shapes="_x0000_i1266">                         

<img width=«203» height=«108» src=«ref-2_699767623-6409.coolpic» v:shapes="_x0000_i1267">                                           (1.12)

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

Переход к канонической форме записи производится с помощью следующих простых действий.

1) Если требуется найти минимум f, то, заменяя fна –f
, переходят к зада­че максимизации, так как min

f
=
max
(-
f
).

2) Если ограничение содержит неравенство со знаком   <, то от него пе­реходят к равенству, добавляя в левую часть ограничения дополнительную неотрицательную переменную.

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

4) Если в задаче какая-либо из переменных произвольна, то от нее избав­ляются, заменяя ее разностью двух других неотрицательных перемен­ных. Например, для произвольной переменной  <img width=«21» height=«29» src=«ref-2_699774032-187.coolpic» v:shapes="_x0000_i1268">, полагают <img width=«15» height=«28» src=«ref-2_699774219-73.coolpic» v:shapes="_x0000_i1269"><img width=«115» height=«39» src=«ref-2_699774292-393.coolpic» v:shapes="_x0000_i1270">     где <img width=«96» height=«39» src=«ref-2_699774685-448.coolpic» v:shapes="_x0000_i1271">.

Суть симплекс-метода состоит в направленном переборе решений системы (1.12). Каждое следующее решение улучшает значение целевой функции.       Симплекс-метод включает два этапа:

·     определение начального решения, удовлетворяющего ограничениям;

·     последовательное улучшение начального решения и получение оптимального решения задачи.

Любое решение задачи линейного программирования называется опорным планом задачи.

Система (1.12) содержит т линейно независимых уравнений, их число меньше числа, неизвестных, входящих в систему, следовательно, ее можно разрешить относительно т неиз­вестных, например <img width=«97» height=«29» src=«ref-2_699775133-342.coolpic» v:shapes="_x0000_i1272">, выразив их через остальные неиз­вестные:

<img width=«204» height=«99» src=«ref-2_699775475-6105.coolpic» v:shapes="_x0000_i1273">

(Коэффициенты в полученной системе, естественно, отличны от коэффициентов системы (1.12), но для простоты обозначены той же буквой).

После указанных преобразований задача приводится к каноническому виду и осуществляется направленный перебор переменных путем перевода свободных в базисные.

Ввод переменной в список базисных переменных означает, что ей приписывается отличное от 0 положительное значение, т.е. ее значение увеличивается. Максимальное значение коэффициента при х1 в форму­ле для fсоответствует максимальному по абсолютной величине отри­цательному элементу в последней строке симплекс-таблицы, следова­тельно, понятен выбор новой базисной переменной.

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

Рассмотрим теперь задачу линейного программирования следующе­го вида:

<img width=«236» height=«131» src=«ref-2_699781580-8747.coolpic» v:shapes="_x0000_i1274">                                    (1.13)

В задаче требуется максимизировать целевую функцию; все ограничения являются неравенствами со знаком   £, все перемен­ные  хj       неотрицательны; задача содержит n
управляющих переменных и т ограничений. Коэффициенты при переменных в целевой функции: c1,
c
2,...,
cn; свободные члены: b
1,

b2.....
bm
.

Двойственная задача линейного программирования имеет вид

<img width=«195» height=«124» src=«ref-2_699790327-8751.coolpic» v:shapes="_x0000_i1275">                                    (1.14)

В двойственной задаче требуется найти минимум целевой фун­кции, ограничения — неравенства со знаком ³, управляющие переменные y1,
y2...,
ym.неотрицательны. Задача содержит mуправ­ляющих переменных и nограничений. Коэффициенты целевой функции  такой задачи b1.b2,...,bm              являются свободными членами исход­ной ЗЛП, а свободные члены двойственной задачи c1,
c
2,...,
cn
— коэффициентами целевой функции исходной ЗЛП. Матрица ко­эффициентов двойственной задачи транспонирована, т.е. строки заменены столбцами, а столбцы — строками.

Задачи (1.13) и (1.14) называются парой взаим­но двойственных задач линейного программирования. Для двойственных задач верна следующая теорема.

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

<img width=«12» height=«23» src=«ref-2_699720446-73.coolpic» v:shapes="_x0000_i1276"> Пусть в качестве управляющих переменных <img width=«71» height=«28» src=«ref-2_699799151-171.coolpic» v:shapes="_x0000_i1277"> исход­ной модели рассматривается число изделий, производимых неко­торым предприятием, а параметрами  <img width=«17» height=«25» src=«ref-2_699799322-102.coolpic» v:shapes="_x0000_i1278"> — количество ресурсов  <img width=«9» height=«17» src=«ref-2_699799424-80.coolpic» v:shapes="_x0000_i1279">-го типа, используемых для изготовления изделий. Через  <img width=«20» height=«25» src=«ref-2_699745571-103.coolpic» v:shapes="_x0000_i1280"> обозначено количество ресурсов   <img width=«9» height=«17» src=«ref-2_699799424-80.coolpic» v:shapes="_x0000_i1281">-го типа, идущее на изготовление одного изделия <img width=«13» height=«20» src=«ref-2_699799687-88.coolpic» v:shapes="_x0000_i1282">-го вида, (<img width=«17» height=«25» src=«ref-2_699799775-96.coolpic» v:shapes="_x0000_i1283"> — прибыль от реали­зации одного изделия  <img width=«13» height=«20» src=«ref-2_699799687-88.coolpic» v:shapes="_x0000_i1284">-го вида). Тогда исходная модель, соответствует задаче определения оптимального плана про­изводства продукции, обеспечивающего максимальную прибыль.

Предложим, что предприятие решило прекратить производство изделий и продать ресурсы, идущие на их изготовление. Обозначим через <img width=«26» height=«37» src=«ref-2_699799959-193.coolpic» v:shapes="_x0000_i1285">, цены на единицу ресурсов его <img width=«9» height=«17» src=«ref-2_699799424-80.coolpic» v:shapes="_x0000_i1286">-го вида, <img width=«49» height=«25» src=«ref-2_699800232-141.coolpic» v:shapes="_x0000_i1287">. Цены на ресурсы должны удовлетворять следующим двум условиям: во-первых, они не должны быть слишком высокими, иначе ресурсы невозможно будет продать; а во-вторых, цены на ресурсы должны быть такими, чтобы прибыль от их реализации была больше прибыли от реали­зации готовой продукции. Первое условие выражается целевой функцией в задаче (1.14), второе условие — ее ограничениями. В левой части каж­дого из неравенств стоит прибыль от продажи ресурсов всех типов, идущих на изготовление   <img width=«13» height=«20» src=«ref-2_699799687-88.coolpic» v:shapes="_x0000_i1288">-го изделия, в правой части — при­быль от продажи    <img width=«13» height=«20» src=«ref-2_699799687-88.coolpic» v:shapes="_x0000_i1289">-го изделия, <img width=«49» height=«25» src=«ref-2_699800549-141.coolpic» v:shapes="_x0000_i1290">. Таким образом, двойствен­ная задача (1.14) соответствует следующей экономичес­кой проблеме: по каким минимальным ценам следует продавать ресурсы, чтобы прибыль от их реализации была больше прибыли, полученной от реализации продукции, изготавливаемой с исполь­зованием этих ресурсов. Значения переменных  <img width=«19» height=«26» src=«ref-2_699800690-100.coolpic» v:shapes="_x0000_i1291"> часто называют «теневыми» ценами.

Построение двойственной задачи позволяет глубже разобраться в поставленной экономической проблеме.
Характеристика методов нелинейного программирования

В общем виде задача нелинейного программирования (ЗНЛП) формулируется следующим образом:

<img width=«191» height=«24» src=«ref-2_699800790-319.coolpic» v:shapes="_x0000_i1292">.                                      (1.15)

     <img width=«207» height=«107» src=«ref-2_699801109-1037.coolpic» v:shapes="_x0000_i1293">                                    (1.16)

где  <img width=«19» height=«25» src=«ref-2_699802146-97.coolpic» v:shapes="_x0000_i1294"> -   управляющие переменные или решения ЗНП, <img width=«49» height=«25» src=«ref-2_699800549-141.coolpic» v:shapes="_x0000_i1295">;

        <img width=«16» height=«24» src=«ref-2_699802384-97.coolpic» v:shapes="_x0000_i1296">   — фиксированные параметры, <img width=«49» height=«25» src=«ref-2_699800232-141.coolpic» v:shapes="_x0000_i1297">;

 <img width=«84» height=«27» src=«ref-2_699802622-192.coolpic» v:shapes="_x0000_i1298"> — заданные функции от  <img width=«13» height=«15» src=«ref-2_699802814-84.coolpic» v:shapes="_x0000_i1299"> переменных.

Если<img width=«16» height=«21» src=«ref-2_699802898-93.coolpic» v:shapes="_x0000_i1300">и<img width=«19» height=«24» src=«ref-2_699802991-96.coolpic» v:shapes="_x0000_i1301">линейны, то ЗНЛП переходит в задачу ли­нейного программирования.

Решить задачу нелинейного программирования — это значит найти такие значения управляющих переменных <img width=«68» height=«28» src=«ref-2_699803087-172.coolpic» v:shapes="_x0000_i1302">, кото­рые удовлетворяют системе ограничений (1.16) и доставляют мак­симум или минимум функции <img width=«16» height=«21» src=«ref-2_699802898-93.coolpic» v:shapes="_x0000_i1303">.

Для задачи нелинейного программирования, в отличие от ли­нейных задач, нет единого метода решения. В зависимости от вида целевой функции (1.15) и ограничений (1.16) разработано не­сколько специальных методов решения, к которым относятся ме­тоды множителей Лагранжа, квадратичное и выпуклое програм­мирование, градиентные методы, ряд приближенных методов решения, графический метод.

Заметим, что нелинейное моделирование экономических задач часто бывает довольно искусственным. Большая часть экономи­ческих проблем сводится к линейным моделям, поэтому в данном пособии нелинейные модели и методы расчета рассмотрены до­статочно кратко.

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

                                           <img width=«148» height=«23» src=«ref-2_699803352-279.coolpic» v:shapes="_x0000_i1304">.                                     (1.17)

                                      <img width=«196» height=«85» src=«ref-2_699803631-932.coolpic» v:shapes="_x0000_i1305">                                (1.18)
Система ограничений (1.18) определяет в <img width=«13» height=«15» src=«ref-2_699802814-84.coolpic» v:shapes="_x0000_i1306">-мерном простран­стве некоторую область, которая является областью допустимых решений задачи.

Решить ЗНЛП графически — это значит найти точку области допустимых решений (1.18), через которую проходит линия <img width=«91» height=«23» src=«ref-2_699804647-194.coolpic» v:shapes="_x0000_i1307"> наивысшего (наинизшего) уровня.

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

Так же, как и для линейных задач, ЗНЛП удобно решать графи­чески, когда функция и ограничения содержат две переменные. Алгоритм в этом случае состоит в следующем.

Шаг 1.На плоскости  <img width=«40» height=«23» src=«ref-2_699804841-136.coolpic» v:shapes="_x0000_i1308">   строят область допустимых реше­ний, определенную ограничениями (1.18). Если она пуста, т.е. ог­раничения несовместны, то задача не имеет реше­ния. В противном случае переходят к шагу 2.

Шаг
2
.Строят линию уровня функции <img width=«91» height=«23» src=«ref-2_699804647-194.coolpic» v:shapes="_x0000_i1309">,где С — некоторая константа. Переход к шагу 3.

Шаг
3
.Определяют направление возрастания (при максими­зации) или убывания (при минимизации) функции <img width=«16» height=«21» src=«ref-2_699802898-93.coolpic» v:shapes="_x0000_i1310">.

Шаг 4.Находят точку области допустимых решений, через ко­торую проходит линия уровня <img width=«91» height=«23» src=«ref-2_699804647-194.coolpic» v:shapes="_x0000_i1311"> с наибольшим (при максимизации) или наименьшим (при минимизации) значением С, либо устанавливают неограниченность функции на области допустимых решений.

Шаг 5.   Определяются значения <img width=«16» height=«23» src=«ref-2_699805458-93.coolpic» v:shapes="_x0000_i1312">, <img width=«19» height=«23» src=«ref-2_699805551-95.coolpic» v:shapes="_x0000_i1313">  для точки, найденной на шаге 4, и величину функции <img width=«16» height=«21» src=«ref-2_699802898-93.coolpic» v:shapes="_x0000_i1314">в этой точке.

В задачах большей размерности для определения условного экстремума могут быть  использованы методы дифференциального исчисления, если <img width=«79» height=«24» src=«ref-2_699805739-179.coolpic» v:shapes="_x0000_i1315"> имеет  не ниже второй производной. Тогда процесс решения ЗНЛП состоит в определении внутри допустимого множества всех стационарных точек функции <img width=«75» height=«24» src=«ref-2_699805918-177.coolpic» v:shapes="_x0000_i1316">, удовлетворяющих условию <img width=«205» height=«47» src=«ref-2_699806095-444.coolpic» v:shapes="_x0000_i1317">, проверке всех стационарных точек на максимум и сравнении этих значений с максимальными значениями, которых достигает целевая функция на границах допустимого множества.

Этот вывод следует из теоремы об экстремальных значениях Вейерштрасса-Больцано.

Теорема  1. Если <img width=«76» height=«24» src=«ref-2_699806539-177.coolpic» v:shapes="_x0000_i1318">  — непрерывная функция, определенная на замкнутом и ограниченном множестве <img width=«16» height=«17» src=«ref-2_699806716-91.coolpic» v:shapes="_x0000_i1319">, то она достигает на этом множестве, по крайней мере, один раз максимального и минимального значения (теорема существования экстремума).

Следующая теорема определяет возможные местоположения экстремума.

Теорема  2.Если<img width=«76» height=«24» src=«ref-2_699806539-177.coolpic» v:shapes="_x0000_i1320"> является функцией нескольких переменных, определенной на допустимой области <img width=«16» height=«17» src=«ref-2_699806716-91.coolpic» v:shapes="_x0000_i1321">, то максимальное значение <img width=«16» height=«21» src=«ref-2_699802898-93.coolpic» v:shapes="_x0000_i1322">, если оно существует, достигается в одной или нескольких точках, которые принадлежат одному из следующих множеств:

·        <img width=«17» height=«23» src=«ref-2_699807168-99.coolpic» v:shapes="_x0000_i1323">  — множество стационарных точек;

·        <img width=«19» height=«23» src=«ref-2_699807267-102.coolpic» v:shapes="_x0000_i1324">  — множество точек границы;

·        <img width=«19» height=«24» src=«ref-2_699807369-102.coolpic» v:shapes="_x0000_i1325">  — множество точек, где <img width=«76» height=«24» src=«ref-2_699806539-177.coolpic» v:shapes="_x0000_i1326"> не дифференцируема.

Иначе говоря, глобальный максимум (минимум) ищут среди локальных.

Определение 1.Функция <img width=«16» height=«21» src=«ref-2_699802898-93.coolpic» v:shapes="_x0000_i1327"> достигает относительного (локального) максимума в точках <img width=«88» height=«25» src=«ref-2_699807741-211.coolpic» v:shapes="_x0000_i1328">, если для всех точек <img width=«16» height=«17» src=«ref-2_699806716-91.coolpic» v:shapes="_x0000_i1329"> лежащих в малой окрестности точки <img width=«87» height=«25» src=«ref-2_699808043-211.coolpic» v:shapes="_x0000_i1330">, имеет место неравенство:

<img width=«200» height=«25» src=«ref-2_699808254-368.coolpic» v:shapes="_x0000_i1331">.

Определение 2.Функция <img width=«16» height=«21» src=«ref-2_699802898-93.coolpic» v:shapes="_x0000_i1332">достигает абсолютного (глобального) максимума в точках <img width=«12» height=«23» src=«ref-2_699720446-73.coolpic» v:shapes="_x0000_i1333"><img width=«87» height=«25» src=«ref-2_699808043-211.coolpic» v:shapes="_x0000_i1334">, если для всех точек <img width=«89» height=«25» src=«ref-2_699808999-314.coolpic» v:shapes="_x0000_i1335"> справедливо неравенство

<img width=«200» height=«25» src=«ref-2_699808254-368.coolpic» v:shapes="_x0000_i1336">.

Остановимся на возможности глобального экстремума в стационарных точках.

Для нахождения стационарных точек <img width=«16» height=«17» src=«ref-2_699806716-91.coolpic» v:shapes="_x0000_i1337">можно использовать теорему 3.

Теорема  3.Пусть <img width=«95» height=«24» src=«ref-2_699809772-202.coolpic» v:shapes="_x0000_i1338">  — дифференцируема в некоторой  области <img width=«16» height=«17» src=«ref-2_699806716-91.coolpic» v:shapes="_x0000_i1339">. Если в некоторой внутренней точке <img width=«87» height=«25» src=«ref-2_699808043-211.coolpic» v:shapes="_x0000_i1340">области <img width=«16» height=«17» src=«ref-2_699806716-91.coolpic» v:shapes="_x0000_i1341"> функция <img width=«16» height=«21» src=«ref-2_699802898-93.coolpic» v:shapes="_x0000_i1342"> имеет относительный   максимум, то

              <img width=«223» height=«48» src=«ref-2_699810460-493.coolpic» v:shapes="_x0000_i1343"> .                                       (1.19)

Для того чтобы определить, действительно ли являются найденные стационарные точки точками максимума или минимума (или не тем  и не другим), необходимо исследовать <img width=«95» height=«24» src=«ref-2_699809772-202.coolpic» v:shapes="_x0000_i1344"> в окрестности стационарных точек и определить, является она выпуклой или вогнутой.

Определение 3.Пусть <img width=«16» height=«17» src=«ref-2_699806716-91.coolpic» v:shapes="_x0000_i1345"> — выпуклое множество точек <img width=«13» height=«15» src=«ref-2_699802814-84.coolpic» v:shapes="_x0000_i1346">-мерного пространства. Функция <img width=«16» height=«21» src=«ref-2_699802898-93.coolpic» v:shapes="_x0000_i1347">, определенная на <img width=«16» height=«17» src=«ref-2_699806716-91.coolpic» v:shapes="_x0000_i1348">, называется вогнутой (выпуклой вверх), если для любой пары точек <img width=«64» height=«23» src=«ref-2_699811514-159.coolpic» v:shapes="_x0000_i1349"> и произвольного  <img width=«61» height=«19» src=«ref-2_699811673-148.coolpic» v:shapes="_x0000_i1350">выполняется неравенство (рис. 1.12):

               <img width=«285» height=«23» src=«ref-2_699811821-521.coolpic» v:shapes="_x0000_i1351">.                               (1.20)

Если

   <img width=«292» height=«25» src=«ref-2_699812342-578.coolpic» v:shapes="_x0000_i1352">,                               (1.21)

то функция называется выпуклой (рис. 1.13).

Если  (1.20) и (1.21) есть строгие неравенства, то функция называется строго вогнутой или строго выпуклой.

Критерий выпуклости и вогнутости функции <img width=«30» height=«19» src=«ref-2_699812920-170.coolpic» v:shapes="_x0000_i1353"> переменных может быть сформулирован в виде следующей теоремы.

<img width=«277» height=«230» src=«ref-2_699813090-7529.coolpic» v:shapes="_x0000_i1354">

Рис. 1.12
<img width=«338» height=«250» src=«ref-2_699820619-2000.coolpic» v:shapes="_x0000_i1355">
Рис. 1.13
Теорема 4.Дифференцируемая функция <img width=«41» height=«25» src=«ref-2_699822619-146.coolpic» v:shapes="_x0000_i1356"> строго вогнута в некоторой окрестности точки <img width=«125» height=«27» src=«ref-2_699822765-265.coolpic» v:shapes="_x0000_i1357">, если выполняются следующие условия:

<img width=«437» height=«88» src=«ref-2_699823030-1753.coolpic» v:shapes="_x0000_i1358"> ,

т.е. если знаки определителей чередуются, где

                                    <img width=«189» height=«52» src=«ref-2_699824783-519.coolpic» v:shapes="_x0000_i1359">.                                         (1.22)

Функция <img width=«41» height=«25» src=«ref-2_699822619-146.coolpic» v:shapes="_x0000_i1360"> строго выпукла в окрестности точки <img width=«24» height=«23» src=«ref-2_699825448-110.coolpic» v:shapes="_x0000_i1361">, если все определители (выписанные выше) положительны. В результате  объединения условий теоремы 3 и 4 приходим к следующему утверждению.

Теорема 5.Для того чтобы в точке <img width=«24» height=«23» src=«ref-2_699825448-110.coolpic» v:shapes="_x0000_i1362"> достигался внутренний относительный максимум, достаточно  равенства нулю всех первых частных производных и строгой     вогнутости функции в окрестности <img width=«24» height=«23» src=«ref-2_699825448-110.coolpic» v:shapes="_x0000_i1363">.

Для того чтобы в точке <img width=«24» height=«23» src=«ref-2_699825448-110.coolpic» v:shapes="_x0000_i1364"> был относительный минимум, необходимо и достаточно, чтобы все частные производные обращались в 0 в точке <img width=«24» height=«23» src=«ref-2_699825448-110.coolpic» v:shapes="_x0000_i1365">, а сама функция в ее окрестности была строго выпукла.

Пример.Пусть<img width=«265» height=«24» src=«ref-2_699825998-441.coolpic» v:shapes="_x0000_i1366">. Стационарная точка <img width=«71» height=«27» src=«ref-2_699826439-271.coolpic» v:shapes="_x0000_i1367">. Исследуем точку   на относительный максимум или минимум:

<img width=«392» height=«23» src=«ref-2_699826710-563.coolpic» v:shapes="_x0000_i1368">

Так как

<img width=«352» height=«51» src=«ref-2_699827273-913.coolpic» v:shapes="_x0000_i1369">,

то функция <img width=«16» height=«21» src=«ref-2_699802898-93.coolpic» v:shapes="_x0000_i1370">достигает в точке <img width=«104» height=«24» src=«ref-2_699828279-206.coolpic» v:shapes="_x0000_i1371"> относительного минимума.

Справедливо следующее утверждение. Если <img width=«41» height=«25» src=«ref-2_699822619-146.coolpic» v:shapes="_x0000_i1372"> — строго выпуклая (вогнутая) функция на всем множестве <img width=«16» height=«17» src=«ref-2_699806716-91.coolpic» v:shapes="_x0000_i1373">, то <img width=«16» height=«21» src=«ref-2_699802898-93.coolpic» v:shapes="_x0000_i1374">обладает только  одним относительным минимумом (максимумом), который является и абсолютным.

Теорема 6  (о выпуклости допустимого множества решений).

Пусть <img width=«183» height=«27» src=«ref-2_699828815-363.coolpic» v:shapes="_x0000_i1375"> и <img width=«39» height=«19» src=«ref-2_699829178-117.coolpic» v:shapes="_x0000_i1376">  — ограничения задачи нелинейного программирования. Если функции <img width=«81» height=«24» src=«ref-2_699829295-169.coolpic» v:shapes="_x0000_i1377">  — вогнуты, то допустимое множество <img width=«99» height=«25» src=«ref-2_699829464-337.coolpic» v:shapes="_x0000_i1378"> и <img width=«147» height=«27» src=«ref-2_699829801-295.coolpic» v:shapes="_x0000_i1379"> является выпуклым.

Теорема 7.Если функции <img width=«151» height=«28» src=«ref-2_699830096-326.coolpic» v:shapes="_x0000_i1380"> вогнуты (выпуклы) на множестве <img width=«16» height=«17» src=«ref-2_699806716-91.coolpic» v:shapes="_x0000_i1381">, то функция <img width=«113» height=«47» src=«ref-2_699830513-427.coolpic» v:shapes="_x0000_i1382"> также вогнута (выпукла), при условии, что <img width=«119» height=«24» src=«ref-2_699830940-227.coolpic» v:shapes="_x0000_i1383">.

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

В общем случае ЗНЛП являются многоэкстремальными. Поэтому и необходимо изучение области допустимых решений, чтобы   выяснить является ли найденный экстремум глобальным.

Установим  условие единственного   глобального экстремума для задачи

<img width=«180» height=«32» src=«ref-2_699831167-505.coolpic» v:shapes="_x0000_i1384">.                                     (1.23)

Для этого рассмотрим функцию одной переменной <img width=«41» height=«23» src=«ref-2_699831672-135.coolpic» v:shapes="_x0000_i1385">. Очевидно, что функция достигает экстремуму (минимума) либо внутри допустимой области (при некотором <img width=«49» height=«23» src=«ref-2_699831807-142.coolpic» v:shapes="_x0000_i1386">, либо на ее границе (при  <img width=«44» height=«23» src=«ref-2_699831949-129.coolpic» v:shapes="_x0000_i1387">). В первом случае <img width=«45» height=«24» src=«ref-2_699832078-140.coolpic» v:shapes="_x0000_i1388"> и производная в этой точке должна быть равна нулю. Во втором случае   <img width=«45» height=«24» src=«ref-2_699832218-137.coolpic» v:shapes="_x0000_i1389"> и производная должна быть  неотрицательная, т.е. <img width=«81» height=«45» src=«ref-2_699832355-270.coolpic» v:shapes="_x0000_i1390">, так как в иначе при увеличении <img width=«16» height=«23» src=«ref-2_699805458-93.coolpic» v:shapes="_x0000_i1391"> (перемещение внутрь допустимой области) можно получить меньшее значение <img width=«41» height=«23» src=«ref-2_699831672-135.coolpic» v:shapes="_x0000_i1392"> и, следовательно, экстремум будет находиться внутри допустимой области.  Таким образом, необходимые условия  экстремума для одномерной задачи имеют вид

<img width=«180» height=«45» src=«ref-2_699832853-435.coolpic» v:shapes="_x0000_i1393">.

По аналогии можно показать, что для задачи (1.23) минимизации функции <img width=«19» height=«22» src=«ref-2_699833288-180.coolpic» v:shapes="_x0000_i1394"> переменных необходимые условия экстремума имеют вид

<img width=«12» height=«23» src=«ref-2_699720446-73.coolpic» v:shapes="_x0000_i1395"><img width=«255» height=«47» src=«ref-2_699833541-539.coolpic» v:shapes="_x0000_i1396">                      (1.24)

т.е. градиент функции в точке  минимума на границе  допустимой области должен быть или равен нулю,  или направлен внутрь допустимой области.

Для задачи  максимизации функции <img width=«19» height=«21» src=«ref-2_699834080-171.coolpic» v:shapes="_x0000_i1397"> неотрицательных переменных необходимые условия экстремума имеют вид:

<img width=«255» height=«47» src=«ref-2_699834251-532.coolpic» v:shapes="_x0000_i1398">                    (1.25)

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

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

                      <img width=«240» height=«28» src=«ref-2_699834783-399.coolpic» v:shapes="_x0000_i1399">,                                (1.26)

т.е. экстремум ищется не на всей полуплоскости, а лишь в определенной ее точке, отвечающей ограничению на ресурсы <img width=«69» height=«25» src=«ref-2_699835182-181.coolpic» v:shapes="_x0000_i1400">. В осно­ве методов решения этих задач лежит метод множителей Лагранжа, который позволяет сформулировать необходимые и достаточ­ные условия экстремума для задачи нахождения глобального экстремума.

Объясним идею метода на примере ЗНЛП,  содержащей две переменные.

<img width=«165» height=«56» src=«ref-2_699835363-2970.coolpic» v:shapes="_x0000_i1401">

На плоскости<img width=«40» height=«23» src=«ref-2_699804841-136.coolpic» v:shapes="_x0000_i1402">уравнение <img width=«85» height=«23» src=«ref-2_699838469-195.coolpic» v:shapes="_x0000_i1403"> определяет график некоторой функции, представленный на рис. 1.14. На нем показа­ны несколько линий уровня некоторой функции <img width=«63» height=«23» src=«ref-2_699838664-164.coolpic» v:shapes="_x0000_i1404">  и вы­бранное в качестве примера направление ее возрастания.

<img width=«406» height=«269» src=«ref-2_699838828-17527.coolpic» v:shapes="_x0000_i1405">

Рис. 1.14.

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

<img width=«262» height=«37» src=«ref-2_699856355-2934.coolpic» v:shapes="_x0000_i1406">

Следовательно, в точке <img width=«16» height=«17» src=«ref-2_699859289-92.coolpic» v:shapes="_x0000_i1407"> векторы-нормали к функциям  <img width=«85» height=«23» src=«ref-2_699838469-195.coolpic» v:shapes="_x0000_i1408"> и <img width=«87» height=«23» src=«ref-2_699859576-189.coolpic» v:shapes="_x0000_i1409"> пропорциональны. Обозначим эти век­торы соответственно через  <img width=«13» height=«24» src=«ref-2_699859765-95.coolpic» v:shapes="_x0000_i1410">  и  <img width=«9» height=«24» src=«ref-2_699859860-85.coolpic» v:shapes="_x0000_i1411">. Получаем

<img width=«95» height=«37» src=«ref-2_699859945-1429.coolpic» v:shapes="_x0000_i1412">

где   <img width=«15» height=«19» src=«ref-2_699861374-90.coolpic» v:shapes="_x0000_i1413">  — некоторый коэффициент пропорциональности. Коор­динатами векторов  <img width=«9» height=«24» src=«ref-2_699859860-85.coolpic» v:shapes="_x0000_i1414"> и <img width=«13» height=«24» src=«ref-2_699859765-95.coolpic» v:shapes="_x0000_i1415"> как градиентовявляются значения частных производ­ных функций  <img width=«16» height=«21» src=«ref-2_699802898-93.coolpic» v:shapes="_x0000_i1416">  и <img width=«15» height=«17» src=«ref-2_699861737-87.coolpic» v:shapes="_x0000_i1417"> соответственно в точке А

<img width=«187» height=«118» src=«ref-2_699861824-5003.coolpic» v:shapes="_x0000_i1418">

Из условия пропорциональности в точке А имеем

<img width=«147» height=«116» src=«ref-2_699866827-4712.coolpic» v:shapes="_x0000_i1419">
Поскольку <img width=«15» height=«19» src=«ref-2_699861374-90.coolpic» v:shapes="_x0000_i1420"> не произвольно, а определяется в точке А через <img width=«20» height=«22» src=«ref-2_699871629-97.coolpic» v:shapes="_x0000_i1421">, то для определения значений <img width=«37» height=«23» src=«ref-2_699871726-119.coolpic» v:shapes="_x0000_i1422">в которых функция   дости­гает максимума, к этим уравнениям надо добавить условие при­надлежности точки А графику функции    <img width=«85» height=«23» src=«ref-2_699838469-195.coolpic» v:shapes="_x0000_i1423">.

Окончательно получаем систему уравнений, которой удовлетворяет оптимальное решение поставленной задачи

<img width=«182» height=«144» src=«ref-2_699872040-6081.coolpic» v:shapes="_x0000_i1424">

Введем новую функцию

<img width=«301» height=«34» src=«ref-2_699878121-3664.coolpic» v:shapes="_x0000_i1425">

Тогда последняя система перепишется в виде

<img width=«368» height=«167» src=«ref-2_699881785-14002.coolpic» v:shapes="_x0000_i1426">

В отличие от задачи для функции<img width=«16» height=«21» src=«ref-2_699802898-93.coolpic» v:shapes="_x0000_i1427"> поиск экстремума <img width=«17» height=«17» src=«ref-2_699895880-91.coolpic» v:shapes="_x0000_i1428"> уже идет не в ограниченной области. Следовательно, имеем задачу безусловной оптимизации, которая может быть решена методами дифференциального исчисления.

Функцию F и называют функцией Лагранжа.

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

Шаг 1.Составляют функцию Лагранжа

<img width=«399» height=«78» src=«ref-2_699895971-6024.coolpic» v:shapes="_x0000_i1429">

Шаг 2.Находят частные производные функции Лагранжа по                        <img width=«123» height=«28» src=«ref-2_699901995-240.coolpic» v:shapes="_x0000_i1430"> иприравнивают их к нулю:

<img width=«281» height=«87» src=«ref-2_699902235-6664.coolpic» v:shapes="_x0000_i1431">                        (1.27)

Шаг 3.Решают систему (1.27) и определяют точки, в которых функция        может иметь экстремум.

Шаг 4.Проверяют полученные на шаге 3 точки на экстремум по ее вогнутости (выпуклости), т.е. изначально   выпуклость определяют из вторых производных, а для неотрицательных переменных и без вычисления вторых производных в силу (1.24) и (1.25), и определяют экстремальное значение функции    в найденной точке.

Таким образом, в случае ограничений заданных в виде равенств, ЗНЛП может быть решена методом множителей Лагранжа. С учетом неотрицательности переменных и определенных нами условий (1.24), (1.25) может этим же методом быть решена и задача с неравенствами (1.23). Если же какая либо из переменных <img width=«23» height=«33» src=«ref-2_699908899-178.coolpic» v:shapes="_x0000_i1432"> не ограничена в знаке (т.е. может быть и отрицательной), то необходимые и достаточные условия экстремума в ЗНЛП устанавливаются на основе теорем Куна-Такера и теоремы о седловой точке.

Теорема Куна-Таккераустанавливает необходимые и достаточные условия экстремума для общей задачи нелинейного программирования (НЛП) и фор­мулируется следующим образом: если функции <img width=«41» height=«21» src=«ref-2_699909077-134.coolpic» v:shapes="_x0000_i1433"> и <img width=«97» height=«27» src=«ref-2_699909211-225.coolpic» v:shapes="_x0000_i1434">, дифференцируемы и выпуклы, а допустимое множество <img width=«277» height=«28» src=«ref-2_699909436-622.coolpic» v:shapes="_x0000_i1435"> содержит внутренние точки, то  для оптимальности вектора <img width=«24» height=«20» src=«ref-2_699910058-105.coolpic» v:shapes="_x0000_i1436"> необходимо и достаточно, чтобы  нашелся неотрицательный вектор <img width=«143» height=«27» src=«ref-2_699910163-272.coolpic» v:shapes="_x0000_i1437">, который вместе с вектором <img width=«24» height=«20» src=«ref-2_699910058-105.coolpic» v:shapes="_x0000_i1438"> удовлетворяет системе  равенств (1.27) (подразумевается <img width=«49» height=«25» src=«ref-2_699910540-143.coolpic» v:shapes="_x0000_i1439">). Точка <img width=«69» height=«22» src=«ref-2_699910683-163.coolpic» v:shapes="_x0000_i1440">в данном случае является седловой точкой функции Лагранжа.

Точка <img width=«69» height=«22» src=«ref-2_699910683-163.coolpic» v:shapes="_x0000_i1441">называется седловой точкой функции <img width=«60» height=«21» src=«ref-2_699911009-163.coolpic» v:shapes="_x0000_i1442">, если для любых <img width=«88» height=«21» src=«ref-2_699911172-188.coolpic» v:shapes="_x0000_i1443"> выполняется условие

<img width=«233» height=«24» src=«ref-2_699911360-389.coolpic» v:shapes="_x0000_i1444">.                            (1.28)

Это условие означает, что в седловой точке функция <img width=«60» height=«21» src=«ref-2_699911009-163.coolpic» v:shapes="_x0000_i1445"> имеет минимум по <img width=«19» height=«17» src=«ref-2_699911912-97.coolpic» v:shapes="_x0000_i1446"> (левое неравенство) и максимум по <img width=«17» height=«19» src=«ref-2_699912009-93.coolpic» v:shapes="_x0000_i1447"> (правое неравенство).

Заметим, что условия (1.28) – это необходимые условия минимума функции Лагранжа, записанные по правилу (1.24) для неотрицательных переменных <img width=«97» height=«28» src=«ref-2_699912102-210.coolpic» v:shapes="_x0000_i1448">, а условия (6.23) – необходимые условия максимума этой функции, записанные по правилу (6.12) для неотрицательных переменных <img width=«92» height=«27» src=«ref-2_699912312-210.coolpic» v:shapes="_x0000_i1449">. Именно поэтому задача НЛП при  выполнении условий теоремы Куна-Таккера сводится к задаче отыскания седловой точки функции Лагранжа.

Теорема о седловой точке  определяет условия, при которых седловая  точка функции Лагранжа определяет оптимальное решение исходной задачи НЛП, и формулируется следующим образом: если <img width=«95» height=«27» src=«ref-2_699912522-215.coolpic» v:shapes="_x0000_i1450">, а вектор <img width=«24» height=«20» src=«ref-2_699910058-105.coolpic» v:shapes="_x0000_i1451">  минимизирует функцию Лагранжа <img width=«67» height=«24» src=«ref-2_699912842-173.coolpic» v:shapes="_x0000_i1452"> и выполняются условия

                     <img width=«299» height=«27» src=«ref-2_699913015-491.coolpic» v:shapes="_x0000_i1453">,                               (1.29)

то <img width=«69» height=«22» src=«ref-2_699910683-163.coolpic» v:shapes="_x0000_i1454"> — седловая точка функции Лагранжа, а <img width=«24» height=«20» src=«ref-2_699910058-105.coolpic» v:shapes="_x0000_i1455"> — оптимальное решение исходной  задачи НЛП.

В отличие от теоремы Куна-Таккера теорема о седловой точке справедлива при любых предположениях, о характере и свойствах целевой функции и функций ограничений, и в силу этого она является не только основной теоремой НЛП, но и основной (фундаментальной) теоремой математического  программирования. Она устанавливает достаточные условия экстремума (но не необходимые) для любой задачи математического программирования. Это означает, что в точке экстремума общей задачи НЛП функция Лагранжа может и не иметь седловой точки. Если же функция Лагранжа имеет седловую точку, то эта точка одновременно определяет  оптимальное решение исходной задачи.

Градиентные методы оптимизации.Теорема Куна-Таккера, оп­ределяя необходимые (в некоторых случаях и достаточные) условия существования оптимального решения, не дает вычислительного алго­ритма для отыскания самого решения.

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

Пусть требуется найти

<img width=«143» height=«31» src=«ref-2_699913774-588.coolpic» v:shapes="_x0000_i1456">,

причем  на переменные <img width=«75» height=«24» src=«ref-2_699914362-156.coolpic» v:shapes="_x0000_i1457"> не наложено ограничений. Градиентом функции <img width=«36» height=«25» src=«ref-2_699914518-135.coolpic» v:shapes="_x0000_i1458">называется вектор частных производных

                                           <img width=«275» height=«51» src=«ref-2_699914653-711.coolpic» v:shapes="_x0000_i1459">                     (1.30)

Пусть <img width=«24» height=«23» src=«ref-2_699915364-111.coolpic» v:shapes="_x0000_i1460">  — произвольная начальная точка. Тогда движение   представляющей точки описывается следующими уравнением:

                                <img width=«304» height=«25» src=«ref-2_699915475-496.coolpic» v:shapes="_x0000_i1461">,                         (1.31)

где <img width=«16» height=«17» src=«ref-2_699915971-92.coolpic» v:shapes="_x0000_i1462"> — величина шага, <img width=«24» height=«23» src=«ref-2_699916063-112.coolpic» v:shapes="_x0000_i1463">  — состояние до последнего шага. Так как <img width=«81» height=«25» src=«ref-2_699916175-213.coolpic» v:shapes="_x0000_i1464"> характеризует направление возрастания <img width=«36» height=«21» src=«ref-2_699916388-128.coolpic» v:shapes="_x0000_i1465">, то очевидно <img width=«203» height=«25» src=«ref-2_699916516-368.coolpic» v:shapes="_x0000_i1466">. В случае, если решается задача минимизации, то движение происходит в направлении антиградиента:

                                            <img width=«159» height=«25» src=«ref-2_699916884-289.coolpic» v:shapes="_x0000_i1467">.                                            (1.32)

Можно показать, что для выпуклых функций точка <img width=«25» height=«23» src=«ref-2_699917173-111.coolpic» v:shapes="_x0000_i1468"> при  <img width=«48» height=«19» src=«ref-2_699917284-132.coolpic» v:shapes="_x0000_i1469">стремится      в область  абсолютного экстремума, которая по размерам  соизмерима с <img width=«16» height=«17» src=«ref-2_699915971-92.coolpic» v:shapes="_x0000_i1470">. Поэтому вместо уравнений (1.31) и (1.32) с постоянным шагом можно перейти к переменному  шагу <img width=«21» height=«24» src=«ref-2_699917508-103.coolpic» v:shapes="_x0000_i1471">. Выбор  <img width=«21» height=«24» src=«ref-2_699917508-103.coolpic» v:shapes="_x0000_i1472"> может производиться по-разному. В частности <img width=«21» height=«24» src=«ref-2_699917508-103.coolpic» v:shapes="_x0000_i1473"> можно выбирать из следующего условия:

                               <img width=«241» height=«33» src=«ref-2_699917817-543.coolpic» v:shapes="_x0000_i1474">,                                       (1.33)

т.е. следует двигаться в направлении однажды вычисленного градиента до тех пор, пока <img width=«41» height=«25» src=«ref-2_699918360-144.coolpic» v:shapes="_x0000_i1475"> не перестанет возрастать. Такую разновидность называют полношаговым градиентным методом (или методом наискорейшего спуска).

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

Большинство реальных практических задач (распределения ресурсов, сетевое планирования и управление, календарное плани­рование, др.) описываются математическими моделями с дискретными состояниями и оказываются задачами дискретного про­граммирования.

Рассмотрим следующую  общую задачу максимизации:

найти

                                             <img width=«138» height=«25» src=«ref-2_699918504-475.coolpic» v:shapes="_x0000_i1476">                                          (1.34)

 

при условиях

    <img width=«139» height=«72» src=«ref-2_699918979-498.coolpic» v:shapes="_x0000_i1477">                                          (1.35)

и                                             <img width=«148» height=«24» src=«ref-2_699919477-254.coolpic» v:shapes="_x0000_i1478">                                        (1.36)
где D — некоторое подмножество действительных чисел.

Если множество D является конечным или счетным, то условие (1.36) — это условие дискретности, и данная задача является задачей дискретного программирования. Если вдобавок вводится ограничение хj

—целые числа (j= 1, 2, ..., п), то приходят к задачам целочисленного программирования (ЦП), кото­рое является частным случаем дискретного программирования.

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

Методы решения задач дискретного программирования по принци­пу подхода к проблеме делят на 3 группы: 1) методы отсечения или отсекающих плоскостей; 2) метод ветвей и границ; 3) методы случай­ного поиска и эвристические методы.

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

1.     Находим оптимальное решение задачи линейного програм­мирования без учета условия целочисленности решения. Если по­лученное решение является целочисленным, то прекращаем вычис­лительный процесс. В противном случае переходим к п. 2.

2.      Вводим дополнительное ограничение, исключающее полученное нецелочисленное решение, и возвращаемся к п. 1.

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

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

<img width=«600» height=«290» src=«ref-2_699919731-4466.coolpic» v:shapes="_x0000_s1028 _x0000_s1029 _x0000_s1030 _x0000_s1031 _x0000_s1032 _x0000_s1033 _x0000_s1034 _x0000_s1035 _x0000_s1036 _x0000_s1037 _x0000_s1038 _x0000_s1039 _x0000_s1040 _x0000_s1041 _x0000_s1042 _x0000_s1043 _x0000_s1044 _x0000_s1045 _x0000_s1046 _x0000_s1047 _x0000_s1048 _x0000_s1049 _x0000_s1050 _x0000_s1051 _x0000_s1052 _x0000_s1053 _x0000_s1054 _x0000_s1055 _x0000_s1056 _x0000_s1057 _x0000_s1058 _x0000_s1059 _x0000_s1060 _x0000_s1061 _x0000_s1062 _x0000_s1063 _x0000_s1064 _x0000_s1065 _x0000_s1066 _x0000_s1067 _x0000_s1068 _x0000_s1069 _x0000_s1070 _x0000_s1071 _x0000_s1072 _x0000_s1073 _x0000_s1074 _x0000_s1075 _x0000_s1076 _x0000_s1077">
Представляем процесс поиска решения в виде графа типа «дерево». При начале построения дерева первую переменную <img width=«20» height=«28» src=«ref-2_699924197-180.coolpic» v:shapes="_x0000_i1493"> можно включить <img width=«64» height=«28» src=«ref-2_699924377-321.coolpic» v:shapes="_x0000_i1494"> или не включить <img width=«69» height=«31» src=«ref-2_699924698-375.coolpic» v:shapes="_x0000_i1025">, т.е. из корневой вершины выходят две ветви. Аналогично в каждой из введенных вершин можно поступить со второй переменной (рис. 1.15).Так и образуется дерево возможных вариантов.
Рис. 1.15.

На первом уровне построенного нами дерева <img width=«140» height=«29» src=«ref-2_699925073-492.coolpic» v:shapes="_x0000_i1026">. Очевидно, что далее для любого <img width=«16» height=«23» src=«ref-2_699659950-189.coolpic» v:shapes="_x0000_i1495"> имеем число вершин (т.е. вариантов) <img width=«60» height=«27» src=«ref-2_699925754-310.coolpic» v:shapes="_x0000_i1496">.

Значение целевой функции L, вычисленное вдоль ветви, дает границу решения по ней. Очевидно, что, построив дерево полностью и перебрав все 2n
вариантов границ решения, можно определить оптимальный план для данной задачи. Метод ветвей и границ, а также метод динамического программирования и разработаны для исключения полного перебора при расчете границ по всем ветвям.

Основная идея метода динамического программирования за­ключается в замене одновременного выбора большого количества параметров поочередным их выбором. Поэтому многомерная задача опти­мизации сводится к многошаговой задаче меньшей размерности. Основа такой замены – формирование рекуррентного соотношения, получившего название функционального уравнения. В результате решения функционального урав­нения получают оптимальную зависимость, по кото­рой обратной прогонкой  определяют оптимальный набор переменных задачи.


Контрольные вопросы:

1.     Сформулируйте понятие  «оптимизации». Приведите примеры сфер    деятельности, где можно использовать методы оптимизации.

2.     Укажите условия необходимые для постановки задачи  оптимизации.


3.     Перечислите основные параметры сетевого графика.

4.     Как осуществляется моделирование инновационных проектов на сетях?

5.     Сформулируйте задачу планирования производства и составьте ее математическую модель.

6.     Сформулируйте основную задачу линейного программирования.

7.     Что такое целевая функция задачи линейного программирования?

8.     Что такое допустимое решение задачи линейного программирования?

9.     Что такое оптимальное решение задачи линейного программирования?

10.Как преобразовать к виду основной задачи линейного программирования задачу, в которой ограничения представляют собой неравенства?

11.Может ли задача линейного программирования иметь более одного оптимального решения?

12.Сформулируйте общую задачу нелинейного программирования.

13.Какова геометрическая интерпретация общей задачи нелинейного программирования?

14.Приведите примеры применения задач нелинейного программирования в экономике.

15.В чем состоят необходимые и достаточные условия экстремума функции нескольких переменных?

16.В чем заключается метод Лагранжа поиска условного экстремума?

17.Перечислите методы решения задач целочисленного программирования.

18.В чем состоит сущность метода ветвей и границ?

19.На чем основана основная идея методов динамического программирования?
Упражнения

1. Используя процедуру ранжирования, произвести нумерацию событий в сетевом графике, изобра­женном на рис. 1.15. Определить продолжительности полных путей, а также путей, предшествующих событиям 5 и 7, и путей, следую­щих за событиями 2 и 5. Найти критический путь и его продолжи­тельность. Считая продолжительности работ полученными по двухоценочной модели с дисперсией равной 0,3 от ожидаемой продолжительности, определить время, за которое комплекс будет выполнен с вероятностью 0,95.

<img width=«333» height=«163» src=«ref-2_699926064-9220.coolpic» v:shapes="_x0000_i1497">
Рис. 1.15.
2. В  сетевом  графике,  изображенном  на  рис. 1.16,  произвести нумерацию событий на основе процедуры ранжирования и определить ранние и поздние сроки на­чала и окончания работ.Найти критический путь и его продолжи­тельность. Рассчитать полные резервы времени для некритических работ.
<img width=«291» height=«208» src=«ref-2_699935284-11103.coolpic» v:shapes="_x0000_i1498">

Рис. 1.16.
Считая продолжительности работ средними с дисперсией в 0,2 от ожидаемой продолжительности, определить время, в течение которого проект будет выполнен с вероятностью 0,95

3.  Для изготовления различных изделий A и B используется 2 вида сырья. На производство единицы изделия A его требуется затратить: 1-го вида -15кг, 2-го вида — 11кг, 3-го вида — 9кг. На производство единицы изделия B требуется затратить сырья 1-го вида — 4кг, 2-го вида — 5кг, 3-го вида — 10кг.

Производство обеспечено сырьем 1-го вида в количестве 1095кг, 2-го вида — 865кг, 3-го вида -1080кг. Прибыль от реализации единицы готового изделия А составляет 3 рубля, изделия B — 2 рубля.

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

1.     Мардас А. Н., Мардас О.А.Краткий курс практического менеджмента. – СПб.: Литера, 2002.

2.     Троцкий М. и др. Управление проектами: Пер. с польск. – М.: Финансы и статистика, 2006.

3.     Колемаев В. А., Малыхин В. И., Бодров А. П. и др. Математические методы принятия решений в экономике: Учебник. – М.: Финстатинформ, 1999.

4.     Карандаев И. С., Малыхин В. И., Соловьев В. И. Прикладная математика: Учебное пособие. – М.: ИНФРА-М, 2001.

5.     Кузнецов А. В., Сакович В. А., Холод Н. И. Высшая математика: Математическое программирование: Учебник. – Минск: Вышэйшая школа, 2001.

6.     Кузнецов А. В., Сакович В. А., Холод Н. И. и др. Сборник задач и упражнений по высшей математике: Математическое программирование: Учебное пособие. – Минск: Вышэйшая школа, 2001.
1.2. Специальные задачи сетевого планирования и управления

Оптимизация на сетях с дискретным потреблением ресурсов. Возобновляемые и невозобновляемые ресурсы. Оптимальное распределение ресурсов для последовательно-параллельных графов. Эвристические  алгоритмы распределения ресурсов на сетевом графике произвольного вида. Эвристические алгоритмы составления рационального расписания при распределении ограниченных ресурсов.
Понятие о ресурсно-временной оптимизации

Оптимизация комплекса операций по времени, представленного сетевым графиком, сводится к сокращению продолжительности кри­тического пути. Такая задача возникает тогда, когда критическое время выполнения комплекса операций превосходит срок <img width=«17» height=«24» src=«ref-2_699946387-101.coolpic» v:shapes="_x0000_i1499">, задан­ный оперирующей стороной. Естественно предположить, что сокра­щение времени выполнения комплекса операций требует осущест­вления определенных мероприятий или вложения каких-то средств.

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

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

При оптимизации с использованием дополнительных средств возможны две постановки задачи.

1. Задан сетевой график <img width=«12» height=«23» src=«ref-2_699720446-73.coolpic» v:shapes="_x0000_i1500"><img width=«52» height=«27» src=«ref-2_699946561-163.coolpic» v:shapes="_x0000_i1501"> выполнения комплекса операций. Время выполнения каждой операции равно  <img width=«16» height=«25» src=«ref-2_699694441-98.coolpic» v:shapes="_x0000_i1502"><img width=«12» height=«23» src=«ref-2_699720446-73.coolpic» v:shapes="_x0000_i1503">. Известно, что   вложение <img width=«19» height=«25» src=«ref-2_699946895-100.coolpic» v:shapes="_x0000_i1504"> дополнительных средств в операцию <img width=«35» height=«21» src=«ref-2_699946995-121.coolpic» v:shapes="_x0000_i1505"> сокращает  время  выполнения с <img width=«16» height=«25» src=«ref-2_699694441-98.coolpic» v:shapes="_x0000_i1506">                 до <img width=«105» height=«27» src=«ref-2_699947214-245.coolpic» v:shapes="_x0000_i1507">. Следует, однако, иметь в виду, что насыщение кри­тических операций ресурсами не беспредельно. Для каждой опера­ции существует минимально возможное время ее выполнения, рав­ное <img width=«20» height=«25» src=«ref-2_699947459-109.coolpic» v:shapes="_x0000_i1508">. Требуется определить время начала <img width=«21» height=«27» src=«ref-2_699947568-113.coolpic» v:shapes="_x0000_i1509">, и окончания  <img width=«21» height=«27» src=«ref-2_699947681-112.coolpic» v:shapes="_x0000_i1510">выполнения операций, а также сколько дополнительных средств  <img width=«27» height=«36» src=«ref-2_699947793-194.coolpic» v:shapes="_x0000_i1511"> вложить в каждую из операций <img width=«35» height=«21» src=«ref-2_699946995-121.coolpic» v:shapes="_x0000_i1512">, чтобы: общее время выполне­ния комплекса операций было минимальным; сумма вложенных до­полнительных средств не превышала заданной величины <img width=«16» height=«17» src=«ref-2_699948108-91.coolpic» v:shapes="_x0000_i1513">; время выполнения каждой операции было не меньше минимально возмож­ного времени  <img width=«20» height=«25» src=«ref-2_699947459-109.coolpic» v:shapes="_x0000_i1514">.

Математически условия задачи можно записать следующим об­разом:

                                      <img width=«120» height=«27» src=«ref-2_699948308-234.coolpic» v:shapes="_x0000_i1515">;                                                        (1.37)

                                        <img width=«76» height=«45» src=«ref-2_699948542-353.coolpic» v:shapes="_x0000_i1516">;                                                              (1.38)

                                 <img width=«87» height=«27» src=«ref-2_699948895-219.coolpic» v:shapes="_x0000_i1517"> для всех <img width=«57» height=«27» src=«ref-2_699949114-164.coolpic» v:shapes="_x0000_i1518">;                                     (1.39)

                                <img width=«111» height=«27» src=«ref-2_699949278-250.coolpic» v:shapes="_x0000_i1519">  для всех <img width=«57» height=«27» src=«ref-2_699949114-164.coolpic» v:shapes="_x0000_i1520">;                                (1.40)

                                       <img width=«56» height=«27» src=«ref-2_699949692-169.coolpic» v:shapes="_x0000_i1521"> для всех <img width=«64» height=«21» src=«ref-2_699949861-153.coolpic» v:shapes="_x0000_i1522">;                                     (1.41)

                               <img width=«144» height=«27» src=«ref-2_699950014-297.coolpic» v:shapes="_x0000_i1523"> для всех <img width=«57» height=«27» src=«ref-2_699949114-164.coolpic» v:shapes="_x0000_i1524">.                           (1.42)

Добавив при необходимости фиктивную операцию, выходящую из последнего события, целевую функцию любого графика можно записать в виде выражения (1.27).

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

Критический путь <img width=«27» height=«27» src=«ref-2_699950475-114.coolpic» v:shapes="_x0000_i1525"> в данной задаче является функцией от объемов дополнительно вкладываемых средств <img width=«24» height=«31» src=«ref-2_699950589-107.coolpic» v:shapes="_x0000_i1526">.

 Сформулированная задача относится к классу задач математического программирования и может быть решена методами линей­ного или нелинейного программирования в соответствии с видом функций  <img width=«49» height=«25» src=«ref-2_699950696-156.coolpic» v:shapes="_x0000_i1527">.

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

Продолжительность комплекса не должна превышать величину  <img width=«24» height=«34» src=«ref-2_699950852-195.coolpic» v:shapes="_x0000_i1528"> (директивное время). Задача предполагает определение значений неизвестных величин <img width=«21» height=«28» src=«ref-2_699951047-103.coolpic» v:shapes="_x0000_i1529"> (объемы дополнительно вкладываемых средств в операции <img width=«35» height=«21» src=«ref-2_699946995-121.coolpic» v:shapes="_x0000_i1530">) таким образом, чтобы:

суммарное количество дополнительно привлекаемых средств было минимальным, т. е.

<img width=«143» height=«40» src=«ref-2_699951271-442.coolpic» v:shapes="_x0000_i1531">;

 время завершения комплекса операций было не выше заданного срока <img width=«17» height=«24» src=«ref-2_699951713-100.coolpic» v:shapes="_x0000_i1532">, а время выполнения каждой операции <img width=«57» height=«27» src=«ref-2_699949114-164.coolpic» v:shapes="_x0000_i1533">  — не мень­ше минимально возможного времени <img width=«20» height=«25» src=«ref-2_699947459-109.coolpic» v:shapes="_x0000_i1534">, что выражается соотноше­ниями:

<img width=«65» height=«27» src=«ref-2_699952086-177.coolpic» v:shapes="_x0000_i1535">;

<img width=«87» height=«27» src=«ref-2_699948895-219.coolpic» v:shapes="_x0000_i1536">  для всех <img width=«57» height=«27» src=«ref-2_699949114-164.coolpic» v:shapes="_x0000_i1537">.

(Здесь предполагается, что зависимость продолжительности выполнения операций от вложен­ных средств выражается соотношениями  <img width=«117» height=«27» src=«ref-2_699952646-258.coolpic» v:shapes="_x0000_i1538"> для всех <img width=«57» height=«27» src=«ref-2_699949114-164.coolpic» v:shapes="_x0000_i1539">);

время окончания любой операции <img width=«35» height=«21» src=«ref-2_699946995-121.coolpic» v:shapes="_x0000_i1540">сетевого графика было не больше времени начала непосредственно следующей за ней опера­ции <img width=«33» height=«21» src=«ref-2_699953189-119.coolpic» v:shapes="_x0000_i1541">, т.е. для любых смежных операций сети <img width=«35» height=«21» src=«ref-2_699946995-121.coolpic» v:shapes="_x0000_i1542"> и <img width=«33» height=«21» src=«ref-2_699953189-119.coolpic» v:shapes="_x0000_i1543"> должно выполняться условие

<img width=«56» height=«27» src=«ref-2_699953548-175.coolpic» v:shapes="_x0000_i1544">;

наконец, соблюдалось условие неотрицательности переменных

<img width=«147» height=«27» src=«ref-2_699953723-302.coolpic» v:shapes="_x0000_i1545"> для всех <img width=«57» height=«27» src=«ref-2_699949114-164.coolpic» v:shapes="_x0000_i1546">.

Рассмотрим теперь оптимизацию в случае использования внутренних резервов.

В этом случае комплекс операций задан сетевым графиком. Известно время выполнения <img width=«16» height=«25» src=«ref-2_699694441-98.coolpic» v:shapes="_x0000_i1547">  каждой операции <img width=«35» height=«21» src=«ref-2_699946995-121.coolpic» v:shapes="_x0000_i1548">. В распоряжении опе­рирующей стороны имеются подвижные средства в количестве<img width=«27» height=«29» src=«ref-2_699954408-222.coolpic» v:shapes="_x0000_i1549">ед., которые распределены между операциями. Для выполнения каж­дой операции <img width=«35» height=«21» src=«ref-2_699946995-121.coolpic» v:shapes="_x0000_i1550">выделено <img width=«22» height=«29» src=«ref-2_699954751-112.coolpic» v:shapes="_x0000_i1551">ед. подвижных средств. Средства <img width=«25» height=«33» src=«ref-2_699954863-191.coolpic» v:shapes="_x0000_i1552">, снятые с операции <img width=«35» height=«21» src=«ref-2_699946995-121.coolpic» v:shapes="_x0000_i1553">, увеличивают продолжительность вы­полнения операции с <img width=«16» height=«25» src=«ref-2_699694441-98.coolpic» v:shapes="_x0000_i1554"> до <img width=«109» height=«27» src=«ref-2_699955273-252.coolpic» v:shapes="_x0000_i1555">, а средства <img width=«21» height=«28» src=«ref-2_699951047-103.coolpic» v:shapes="_x0000_i1556">, вложен­ные в операцию, уменьшают продолжительность ее выполнения до величины <img width=«108» height=«27» src=«ref-2_699955628-255.coolpic» v:shapes="_x0000_i1557">.

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

Требуется так перераспределить подвижные средства между операциями, чтобы продолжительность выполнения комплекса опе­раций была минимальной.

Обозначим количество средств, перебрасываемых на операцию <img width=«35» height=«21» src=«ref-2_699946995-121.coolpic» v:shapes="_x0000_i1558">, через <img width=«19» height=«27» src=«ref-2_699956004-103.coolpic» v:shapes="_x0000_i1559">  (если с операции  <img width=«35» height=«21» src=«ref-2_699946995-121.coolpic» v:shapes="_x0000_i1560">снимаются средства, то зна­чение<img width=«25» height=«30» src=«ref-2_699956228-106.coolpic» v:shapes="_x0000_i1561">отрицательно).

Новые продолжительности будут равны:

для операций, с которых снимаются средства,

<img width=«85» height=«29» src=«ref-2_699956334-245.coolpic» v:shapes="_x0000_i1562">;

для операций, на которые перебрасываются средства

<img width=«79» height=«27» src=«ref-2_699956579-208.coolpic» v:shapes="_x0000_i1563">.

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

<img width=«69» height=«40» src=«ref-2_699956787-324.coolpic» v:shapes="_x0000_i1564">.

Количество подвижных средств, снимаемых с операций  <img width=«35» height=«21» src=«ref-2_699946995-121.coolpic» v:shapes="_x0000_i1565">, не должно превышать соответствующих величин       

                                      <img width=«121» height=«29» src=«ref-2_699957232-256.coolpic» v:shapes="_x0000_i1566">.                                                  (1.43)

Целевая функция, отражающая общую продолжительность вы­полнения комплекса операций, имеет вид

<img width=«180» height=«40» src=«ref-2_699957488-599.coolpic» v:shapes="_x0000_i1567">.

Ограничения (1.43) записываются для всех операций сетевого графика, так как в результате расчетов критические операции могут перейти в некритические и наоборот. По той же причине в целевую функцию включены две суммы. В первую сумму включаются опера­ции, с которых снимаются средства, во вторую — операции, на кото­рые перебрасываются средства, если те и другие входят в критиче­ский путь.

Методы решения таких задач определяются видом функции <img width=«79» height=«27» src=«ref-2_699956579-208.coolpic» v:shapes="_x0000_i1568">.

Постановки задач оптимального распределения ресурсов

на сетях

В рамках нашего курса под ресурсами будем понимать любые ресурсы организации — от персонала до производственных площадей. <img width=«12» height=«23» src=«ref-2_699720446-73.coolpic» v:shapes="_x0000_i1569">Вместе с тем, при всей общности подхода будем учитывать, что существуют две принципиально разные группы ресурсов в силу разницы их использования при выполнении работ:

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

·        нескладируемые (или возобновляемые) ресурсы, то есть те, которые в процессе   выполнения работ не расходуются, не изменяют свою натуральную форму, но производят некоторый расходуемый фактор (человеко-день, тонно-км и т.д.). Чаще всего это исполнители (люди или механизмы, которые могут быть перемещены на другую работу). Их часто называют ресурсами  типа «мощность», в то время как складируемые ресурсы  это ресурсы типа «материалы».

Расход ресурсов типа «материалы» можно описать функцией «время-стоимость»:

<img width=«145» height=«46» src=«ref-2_699958368-634.coolpic» v:shapes="_x0000_i1570">.

<img width=«304» height=«319» src=«ref-2_699959002-1797.coolpic» v:shapes="_x0000_s1078 _x0000_s1079 _x0000_s1080 _x0000_s1081 _x0000_s1082 _x0000_s1083 _x0000_s1084 _x0000_s1085 _x0000_s1086 _x0000_s1087 _x0000_s1088 _x0000_s1089">
Как правило, это функция убывающая (рис. 1.17):
Рис. 1.17.

Здесь:

       <img width=«20» height=«25» src=«ref-2_699745571-103.coolpic» v:shapes="_x0000_i1575">  — минимальная продолжительность работы;

       <img width=«19» height=«25» src=«ref-2_699735944-106.coolpic» v:shapes="_x0000_i1576">  — максимальная продолжительность работы.

 В предшествующем параграфе мы предполагали, данная функция линейна и, естественно, при оптимизации комплекса работ, описываемого сетевым графиком, приходили к задаче линейного программирования. На самом деле такое предположение — это чистая утопия. В общем случае функция, связывающая продолжительность работы и потребляемый на ней складируемый ресурс дискретна и нелинейна, что на рис. 1.17 отражено точечной линией.

При оптимизации расхода нескладируемых ресурсов в качестве связи со временем выполнения работы вводят мощность потребления ресурса <img width=«22» height=«27» src=«ref-2_699961008-107.coolpic» v:shapes="_x0000_i1577">,  т.е. количество единиц ресурса, используемых в единицу времени для выполнения работы <img width=«35» height=«21» src=«ref-2_699946995-121.coolpic» v:shapes="_x0000_i1578">.

Таким образом, можно сформулировать две постановки задачи:

1.     Заданы ограничения на потребляемые ресурсы. Требуется распределить  ресурсы по работам сетевого графика таким образом, чтобы минимизировать критическое время <img width=«35» height=«38» src=«ref-2_699961236-231.coolpic» v:shapes="_x0000_i1579">. Такие задачи обычно относятся к нескладируемым ресурсам.

2.     Задан <img width=«40» height=«37» src=«ref-2_699961467-241.coolpic» v:shapes="_x0000_i1580">  — директивный срок выполнения комплекса работ. Необходимо минимизировать ресурсы, которые потребны для выполнения этого комплекса. Такие задачи обычно относят к складируемым ресурсам.

Переходя к рассмотрению методов ресурсно-временной оптимизации в задачах с произвольной функцией «время-стоимость» отметим, что сетевой график сам в силу топологии приводит к нелинейности потребления ресурсов во времени.  Связь между временем выполнения работы и затратами ресурсов (стоимостью)  также нелинейна. Следовательно,  всегда имеем нелинейную задачу оптимизации. А общего метода решения таких задач не существует. В большинстве случаев используются эвристические  (построенные на догадках) методы, не гарантирующие оптимальность решения. Вместе с тем, для определенного круга задач точное решение может быть найдено, в частности методами динамического программирования.
    продолжение
--PAGE_BREAK-- Ресурсно-временная оптимизация на сетях с невозобновляемыми ресурсами


Поскольку о принципах формализации ресурсно-временной оптимизации нескладируемых ресурсов на сетях в предположении линейности функции «время-стоимость» мы уже говорили ранее, то будем рассматривать эвристические алгоритмы для функций произвольного вида.

Сформулируем постановку задачи математически.

Задан комплекс работ в виде сетевого графа <img width=«112» height=«35» src=«ref-2_699961708-561.coolpic» v:shapes="_x0000_i1581">, где <img width=«32» height=«26» src=«ref-2_699962269-249.coolpic» v:shapes="_x0000_i1582"> — сетевой граф.

Для каждой работы заданы стоимость (связь между продолжительностью и затратами невозобновляемых ресурсов)<img width=«108» height=«34» src=«ref-2_699962518-464.coolpic» v:shapes="_x0000_i1583">, допустимая продолжительность ее выполнения <img width=«108» height=«33» src=«ref-2_699962982-452.coolpic» v:shapes="_x0000_i1584"> и директивный срок выполнения <img width=«41» height=«38» src=«ref-2_699963434-247.coolpic» v:shapes="_x0000_i1585">всего комплекса, т.е. предполагается, что в итоге критическое время проекта приводится к величине <img width=«90» height=«35» src=«ref-2_699963681-379.coolpic» v:shapes="_x0000_i1586">.

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

<img width=«265» height=«52» src=«ref-2_699964060-1130.coolpic» v:shapes="_x0000_i1587">

при условии

<img width=«90» height=«35» src=«ref-2_699963681-379.coolpic» v:shapes="_x0000_i1588">.

Предположим, что комплекс работ может быть представлен как чисто последовательный граф (рис. 1.18):

<img width=«462» height=«54» src=«ref-2_699965569-952.coolpic» v:shapes="_x0000_s1090 _x0000_s1091 _x0000_s1092 _x0000_s1093 _x0000_s1094 _x0000_s1095 _x0000_s1096 _x0000_s1097 _x0000_s1098 _x0000_s1099">

Рис. 1.18.

Для определенности зададим продолжительность (<img width=«22» height=«34» src=«ref-2_699966521-182.coolpic» v:shapes="_x0000_i1589">) и расход ресурсов <img width=«30» height=«45» src=«ref-2_699966703-211.coolpic» v:shapes="_x0000_i1590">на каждой операции (табл. 1.7).
Таблица 1.7

Данные о продолжительности и расходе ресурсов на операциях комплекса



Для оптимального распределения ресурсов воспользуемся табличным методом решения задач динамического программирования.

Первоначально рассматриваем варианты выполнения сочетания работ (0-1) и (1-2). Поскольку вторая операция может выполняться по трем вариантам, то возможны и три варианта выполнения пути (0-1-2) (табл. 1.8). Продолжительность и расход ресурсов по каждому варианту отражен во внутренних клетках таблицы. Первая строка чисел в этой таблице образуется как сумма продолжительностей работ (0-1) и (1-2) по определенному варианту выполнения. Вторая строка – сумма потребляемых ресурсов. Стрелки символизируют рассматриваемую динамическую последовательность, т.е. возможные варианты времени выполнения пути (0-1-2) при различных затратах ресурсов.

<img width=«91» height=«113» src=«ref-2_699967723-304.coolpic» v:shapes="_x0000_s1170">Таблица 1.8

         <img width=«19» height=«23» src=«ref-2_699968027-100.coolpic» v:shapes="_x0000_i1599">

<img width=«19» height=«24» src=«ref-2_699966914-102.coolpic» v:shapes="_x0000_i1600">       <img width=«21» height=«23» src=«ref-2_699968229-100.coolpic» v:shapes="_x0000_i1601">

<img width=«21» height=«24» src=«ref-2_699967016-101.coolpic» v:shapes="_x0000_i1602">   

48

20

32

40

24

60

2

4


50

<img width=«95» height=«19» src=«ref-2_699968430-135.coolpic» v:shapes="_x0000_s1165">24

34

<img width=«63» height=«12» src=«ref-2_699968565-103.coolpic» v:shapes="_x0000_s1164">44

26

64



Присоединяем к этой последовательности следующую операцию (2-3). В этот раз на очередном шаге также возможны три последовательности (табл. 1.9).
<img width=«12» height=«75» src=«ref-2_699968668-139.coolpic» v:shapes="_x0000_s1166">Таблица 1.9

Присоединив к вариантам последовательности (0-1-2-3) работу (3-4), получим все возможные варианты выполнения комплекса, строящиеся на основании принципа оптимальности Беллмана (табл. 1.10).

Таблица 1.10

 

Оптимальную динамическую последовательность, а значит и оптимальное распределение ресурсов при минимизации времени выполнения проекта, получаем, строя ее по принципу «минимальное время за те же ресурсы». Такая последовательность в табл. 1.10 выделена жирно и представлена стрелками. Она показывает (выделено цветом), что работу (3-4) следует выполнять, используя 20 единиц ресурсов и с продолжительностью 8 единиц времени. Предшествующий же путь необходимо выполнить за 66 ед. времени, затратив 114 ед. ресурсов. Данным величинам соответствует продолжительность работы (2-3) в 40 ед. времени с затратами 50 ед. ресурсов и предшествующий путь (0-1-2)с продолжительностью 26 и затратами 64 ед. (табл. 1.9).

Продолжая действовать по той же схеме, на основании последовательности, отраженной  в табл. 1.8, приходим  к заключению, что операцию (1-2) следует выполнять по третьему варианту, т.е. за 24 ед. времени с расходом 60 ед. и, естественно, операцию (0-1) за 2 ед. времени с расходом 4.

Окончательно имеем распределение ресурсов на проект, выделенное цветом в табл. 1.7, и приводящее к реализации проекта за 74 ед. времени с общим расходом невозобновляемых ресурсов в 134 единицы.

Таким образом, метод динамического программирования позволяет точно решить задачу ресурсно-временной оптимизации на последовательном графе.

Этот же метод работает и для чисто  «параллельного» графа (рис. 1.19).

<img width=«258» height=«138» src=«ref-2_699971030-1144.coolpic» v:shapes="_x0000_s1104 _x0000_s1105 _x0000_s1106 _x0000_s1107 _x0000_s1108 _x0000_s1109 _x0000_s1110 _x0000_s1111 _x0000_s1112">



Рис. 1.19.
Действительно, по данным о последовательных операциях (0-1), (1-3) и (0-2), (2-3) можно провести вначале «сшивку», подобную той, которая отражена на рис. 1.20.  Затем для образовавшегося чисто параллельного графа распределяют ресурсы методом динамического программирования в минимаксной задаче (табл. 1.11).

<img width=«190» height=«110» src=«ref-2_699972174-750.coolpic» v:shapes="_x0000_s1113 _x0000_s1114 _x0000_s1115 _x0000_s1116 _x0000_s1117 _x0000_s1118">
<img width=«135» height=«16» src=«ref-2_699972924-144.coolpic» v:shapes="_x0000_s1168">



Рис. 1.20
Таблица 1.11



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

Iпуть: <img width=«24» height=«24» src=«ref-2_699973383-109.coolpic» v:shapes="_x0000_i1615">=5;            <img width=«27» height=«24» src=«ref-2_699973601-109.coolpic» v:shapes="_x0000_i1616">=30.  IIпуть: <img width=«24» height=«24» src=«ref-2_699973492-109.coolpic» v:shapes="_x0000_i1617"> = 5;              <img width=«27» height=«24» src=«ref-2_699973710-109.coolpic» v:shapes="_x0000_i1618"> = 10.

Последовательность завершается в клетке со временем проекта равным (не превышающим) <img width=«27» height=«27» src=«ref-2_699975079-121.coolpic» v:shapes="_x0000_i1619">.

Этот метод может быть обобщен на более сложные сетевые графики (рис. 1.21). Свертка в этом случае проводится по отдельным кускам графа, сводимым в одну дугу. К примеру, вначале свертывают операции (1-3) и (1-4) последовательно, а затем пути (1-3-4) и (1-4) параллельно. Далеесшиваем пути (1-4-5) и (1-2-5),  и т.д. Однако наличие в графике на рис. 4.5 работы (3-6) не позволит свернуть путь (1-3-4). Аналогично, нельзя осуществить оптимизацию подобным образом для сетевого графика, представленного на рис. 1.22. Поэтому рассмотренный подход (метод динамического программирования) применим только для чисто последовательно-параллельных графов. В определенных случаях для взаимозаменяемых ресурсов решение может быть получено методом ветвей и границ.

<img width=«378» height=«174» src=«ref-2_699975200-1866.coolpic» v:shapes="_x0000_s1334 _x0000_s1335 _x0000_s1336 _x0000_s1337 _x0000_s1338 _x0000_s1339 _x0000_s1340 _x0000_s1341 _x0000_s1342 _x0000_s1343 _x0000_s1344 _x0000_s1345 _x0000_s1346 _x0000_s1347 _x0000_s1348 _x0000_s1349 _x0000_s1350 _x0000_s1351 _x0000_s1352 _x0000_s1353">


Рис. 1.21

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

<img width=«211» height=«153» src=«ref-2_699977066-1097.coolpic» v:shapes="_x0000_s1141 _x0000_s1142 _x0000_s1143 _x0000_s1144 _x0000_s1145 _x0000_s1146 _x0000_s1147 _x0000_s1148 _x0000_s1149 _x0000_s1150">
Рис. 1.22.    продолжение
--PAGE_BREAK--
Эвристические  алгоритмы распределения

ресурсов на сетевом графике произвольного вида


Задача минимизации расхода ресурсов при заданном директивном сроке выполнения проекта. Допустим мы уверены в том, что каждая работа комплекса выполнима во временном интервале <img width=«97» height=«30» src=«ref-2_699978163-307.coolpic» v:shapes="_x0000_i1620">. Тогда, если на все работы направить максимально возможные ресурсы, иначе говоря, обеспечить <img width=«49» height=«25» src=«ref-2_699978470-142.coolpic» v:shapes="_x0000_i1621">, то продолжительность критического пути будет минимальной из возможных (<img width=«92» height=«34» src=«ref-2_699978612-348.coolpic» v:shapes="_x0000_i1622">), а расход ресурсов — максимальным (<img width=«80» height=«25» src=«ref-2_699978960-336.coolpic» v:shapes="_x0000_i1623">). Если же <img width=«57» height=«29» src=«ref-2_699979296-156.coolpic» v:shapes="_x0000_i1624">, то, соответственно, <img width=«91» height=«33» src=«ref-2_699979452-379.coolpic» v:shapes="_x0000_i1625">и <img width=«76» height=«25» src=«ref-2_699979831-306.coolpic» v:shapes="_x0000_i1626">.

Отметим, что если по <img width=«12» height=«23» src=«ref-2_699720446-73.coolpic» v:shapes="_x0000_i1627">первому варианту закрепления ресурсов (при <img width=«48» height=«25» src=«ref-2_699980210-148.coolpic» v:shapes="_x0000_i1628">), рассчитанное критическое время проекта превышает директивное (<img width=«79» height=«27» src=«ref-2_699980358-213.coolpic» v:shapes="_x0000_i1629">), то задача минимизации расхода при наличных ресурсах не имеет решения. Если же <img width=«79» height=«27» src=«ref-2_699980571-220.coolpic» v:shapes="_x0000_i1630">, то  закрепление минимально возможных ресурсов за каждой из работ приводит и к оптимальному решению. Однако возможно условие <img width=«161» height=«34» src=«ref-2_699980791-461.coolpic» v:shapes="_x0000_i1631">. Тогда для каждой из работ необходимо определить величину  <img width=«20» height=«31» src=«ref-2_699981252-106.coolpic» v:shapes="_x0000_i1632">  из допустимого промежутка <img width=«97» height=«30» src=«ref-2_699978163-307.coolpic» v:shapes="_x0000_i1633">, обеспечивающую минимальность потребления ресурсов всем проектом.

Решение нашей задачи в этом случае отыскивается по следующему эвристическому алгоритму:

1.     Примем <img width=«48» height=«25» src=«ref-2_699980210-148.coolpic» v:shapes="_x0000_i1634"> и найдем первый возможный критический путь <img width=«24» height=«27» src=«ref-2_699981813-127.coolpic» v:shapes="_x0000_i1635"> с продолжительностью <img width=«39» height=«27» src=«ref-2_699981940-148.coolpic» v:shapes="_x0000_i1636">. Если <img width=«79» height=«27» src=«ref-2_699980571-220.coolpic» v:shapes="_x0000_i1637">, то распределение ресурсов, обеспечивающее  <img width=«58» height=«30» src=«ref-2_699982308-160.coolpic» v:shapes="_x0000_i1638">, приводит к оптимальному решению, причем <img width=«95» height=«27» src=«ref-2_699982468-236.coolpic» v:shapes="_x0000_i1639">. Если же нет, то осуществляем переход ко второму шагу алгоритма.

2.     Для работ <img width=«71» height=«27» src=«ref-2_699982704-201.coolpic» v:shapes="_x0000_i1640"> произвести оптимальное распределение ресурсов как для последовательного сетевого графика, ориентируясь на условие <img width=«79» height=«27» src=«ref-2_699980571-220.coolpic» v:shapes="_x0000_i1641">.

3.     На основании полученной динамической последовательности определить продолжительности операций <img width=«21» height=«27» src=«ref-2_699983125-120.coolpic» v:shapes="_x0000_i1642"> для <img width=«81» height=«24» src=«ref-2_699983245-201.coolpic» v:shapes="_x0000_i1643">и исключить из множества критических работ операции с <img width=«52» height=«27» src=«ref-2_699983446-167.coolpic» v:shapes="_x0000_i1644">.

4.     Положить <img width=«48» height=«25» src=«ref-2_699980210-148.coolpic» v:shapes="_x0000_i1645"> для <img width=«71» height=«27» src=«ref-2_699983761-206.coolpic» v:shapes="_x0000_i1646"> и <img width=«52» height=«27» src=«ref-2_699983967-165.coolpic» v:shapes="_x0000_i1647"> для <img width=«71» height=«27» src=«ref-2_699982704-201.coolpic» v:shapes="_x0000_i1648">. Рассчитать (определить) <img width=«27» height=«27» src=«ref-2_699984333-131.coolpic» v:shapes="_x0000_i1649"> и <img width=«28» height=«27» src=«ref-2_699984464-136.coolpic» v:shapes="_x0000_i1650">. Проверить условие <img width=«69» height=«27» src=«ref-2_699984600-204.coolpic» v:shapes="_x0000_i1651">. Если оно выполняется, то   план распределения ресурсов, полученный на данном шаге, оптимален. В противном случае перейти к п.2.

Задание.

Примените данный алгоритм к численному примеру (рис. 1.23, табл. 1.12).

<img width=«211» height=«153» src=«ref-2_699984804-1093.coolpic» v:shapes="_x0000_s1151 _x0000_s1152 _x0000_s1153 _x0000_s1154 _x0000_s1155 _x0000_s1156 _x0000_s1157 _x0000_s1158 _x0000_s1159 _x0000_s1160">
 Рис. 1.23.
Таблица 1.12

<img width=«19» height=«24» src=«ref-2_699966914-102.coolpic» v:shapes="_x0000_i1652">

<img width=«21» height=«24» src=«ref-2_699967016-101.coolpic» v:shapes="_x0000_i1653">

<img width=«20» height=«24» src=«ref-2_699969089-102.coolpic» v:shapes="_x0000_i1654">

<img width=«21» height=«24» src=«ref-2_699969294-103.coolpic» v:shapes="_x0000_i1655">

<img width=«19» height=«23» src=«ref-2_699967117-101.coolpic» v:shapes="_x0000_i1656">

<img width=«21» height=«23» src=«ref-2_699967218-100.coolpic» v:shapes="_x0000_i1657">

<img width=«19» height=«24» src=«ref-2_699986506-100.coolpic» v:shapes="_x0000_i1658">

<img width=«21» height=«24» src=«ref-2_699986606-100.coolpic» v:shapes="_x0000_i1659">


<img width=«19» height=«24» src=«ref-2_699967318-103.coolpic» v:shapes="_x0000_i1660">

<img width=«21» height=«24» src=«ref-2_699967421-101.coolpic» v:shapes="_x0000_i1661">

18

32

16

5

8

16

17

6

19

66

12

48

10

16

6

24

14

24

8

74

10

56

8

20

5

32

11

42

6

80

6

72



















Требуется определить минимальную стоимость проекта Cпри условии <img width=«63» height=«25» src=«ref-2_699986910-174.coolpic» v:shapes="_x0000_i1662"> =28.
Задача минимизации времени выполнения проекта при заданном количестве ресурсов. Рассмотрим теперь задачу минимизации времени выполнения комплекса работ при заданном количестве ресурсов типа «мощность».

Пусть, к примеру, комплекс работ задан следующим сетевым графиком (рис. 1.24)
<img width=«419» height=«322» src=«ref-2_699987084-4036.coolpic» v:shapes="_x0000_s1174 _x0000_s1175 _x0000_s1176 _x0000_s1177 _x0000_s1178 _x0000_s1179 _x0000_s1180 _x0000_s1181 _x0000_s1182 _x0000_s1183 _x0000_s1184 _x0000_s1185 _x0000_s1186 _x0000_s1187 _x0000_s1188 _x0000_s1189 _x0000_s1190 _x0000_s1191 _x0000_s1192 _x0000_s1193 _x0000_s1194 _x0000_s1195 _x0000_s1196">
Рис. 1.24.

Не принимая в расчет потребление ресурсов  (указано в скобках над каждой из операций графика), произведем расчет временных параметров: ранних <img width=«22» height=«28» src=«ref-2_699991120-108.coolpic» v:shapes="_x0000_i1663"> и  поздних <img width=«20» height=«28» src=«ref-2_699991228-104.coolpic» v:shapes="_x0000_i1664"> сроков наступления событий (левый и правый секторы соответственно в кружке-событии на рис. 1.24).  Получим критическое время проекта <img width=«49» height=«25» src=«ref-2_699991332-142.coolpic» v:shapes="_x0000_i1665">.

Построим далее таблицу (табл. 1.13) для отражения количества  ресурсов (исполнителей), задействованных в каждом временном интервале (в определенный день). В ней символ <img width=«31» height=«27» src=«ref-2_699991474-187.coolpic» v:shapes="_x0000_i1666"> означает суммарное количество потребных ресурсов на данном временном интервале. В нашем случае выполнение проекта за 9 дней возможно, если мы располагаем 7 исполнителями.

Предположим, однако, что количество исполнителей ограничено и равно С=5. Требуется определить порядок выполнения комплекса, при котором  критическое время проекта минимально (<img width=«73» height=«25» src=«ref-2_699991661-170.coolpic» v:shapes="_x0000_i1667">).
Таблица 1.13

Код операции

Время <img width=«9» height=«16» src=«ref-2_699991831-81.coolpic» v:shapes="_x0000_i1668">

<img width=«15» height=«20» src=«ref-2_699991912-91.coolpic» v:shapes="_x0000_i1669">

1

2

3

4

5

6

7

8

9

10

0-1

4

4

















0-2

2

2

2

2













1-2





3

3

3











1-3





2

2

2

2

2

2

2



2-3











3









<img width=«31» height=«27» src=«ref-2_699991474-187.coolpic» v:shapes="_x0000_i1670">

6

6

7

7

5

5

2

2

2





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

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

1-ое правило. При назначении планового срока выполнения работы предпочтение отдается той операции, у которой минимален поздний срок свершения <img width=«26» height=«33» src=«ref-2_699992190-122.coolpic» v:shapes="_x0000_i1671">завершающего события <img width=«13» height=«20» src=«ref-2_699799687-88.coolpic» v:shapes="_x0000_i1672">.

Возможно применение данного правила и в отношении максимального раннего срока <img width=«33» height=«36» src=«ref-2_699992400-211.coolpic» v:shapes="_x0000_i1673">свершения начального события iвыбираемой операции.

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

2-ое правило. При  включении в расписание предпочтение отдается той работе, которая предполагает большее потребление ресурсов, т.е. с   <img width=«156» height=«33» src=«ref-2_699992611-723.coolpic» v:shapes="_x0000_i1674">, где <img width=«28» height=«34» src=«ref-2_699993334-201.coolpic» v:shapes="_x0000_i1675">означает общие затраты (затраты в единицу времени).

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

1-ое правило предпочтения требует предварительного расчета параметров сетевого графика (<img width=«21» height=«27» src=«ref-2_699993535-112.coolpic» v:shapes="_x0000_i1676"> или <img width=«23» height=«25» src=«ref-2_699993647-109.coolpic» v:shapes="_x0000_i1677">).

2-ое правило более просто в применении, поскольку  не предполагает расчета сетевого графика.

Вернемся к примеру, заданному рис. 1.24, и рассмотрим порядок применения 2-ого правила предпочтения (табл. 1.14).
Таблица 1.14

Код операции

Время <img width=«9» height=«16» src=«ref-2_699991831-81.coolpic» v:shapes="_x0000_i1678">

<img width=«15» height=«20» src=«ref-2_699991912-91.coolpic» v:shapes="_x0000_i1679">

1

2

3

4

5

6

7

8

9

10

11

12

0-1

4

4





















0-2





2

2

2

2













1-2





3

3

3















1-3











2

2

2

2

2

2

2

2-3













3











<img width=«31» height=«27» src=«ref-2_699991474-187.coolpic» v:shapes="_x0000_i1680">

4

4

5

5

5

4

5

2

2

2

2

2



Построение данной таблицы осуществлено следующим образом.

В начальном (нулевом) событии графика возможно одновременное начало операций (0-1) и (0-2). В первый день тогда потребовалось бы 6 исполнителей. Но мы ограничены величиной С=5, поэтому, используя второе правило предпочтения, включаем в расписание только работу (0-1), как потребляющую большее количество ресурсов. Это вынуждает начало работы (0-2) сдвигать в третий временной интервал. Однако в третий день освободятся исполнители («мощности»), которые были до этого задействованы на операции (0-1). Поэтому на очередном шаге включаем в расписание работу (1-2), как требующую больших ресурсов и присоединяем к ней еще не выполнявшуюся операцию (0-2), поскольку располагаем достаточным количеством (2 единицы) свободных исполнителей. Суммарное потребление ресурсов в третий, четвертый и пятый дни будет составлять 5 единиц (нижняя строка табл. 1.14).

В шестом временном интервале три исполнителя высвобождаются. Максимальное потребление ресурсов на еще не выполнявшихся операциях равно 3 (работа 2-3). Однако включить ее в расписание сейчас нельзя, поскольку событие 2 еще не наступило. Поэтому в шестой  временной интервал планируем начало операции (1-3), требующей две единицы ресурсов и продолжающейся до 12-го дня включительно.

Поскольку в седьмой день освободятся исполнители с работы (0-2), то на него можно спланировать операцию (2-3).

Таким образом, при заданном ограничении на ресурсы весь комплекс, отражаемый сетевым графиком на рис. 1.24, может быть выполнен за 12 единиц времени.

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

<img width=«105» height=«66» src=«ref-2_699994115-452.coolpic» v:shapes="_x0000_i1681">

и критической продолжительности проекта <img width=«78» height=«32» src=«ref-2_699994567-189.coolpic» v:shapes="_x0000_i1682"> при отсутствии ограничений на ресурсы.

Применив этот подход к нашему примеру, получим

<img width=«133» height=«66» src=«ref-2_699994756-534.coolpic» v:shapes="_x0000_i1683">,

<img width=«115» height=«33» src=«ref-2_699995290-398.coolpic» v:shapes="_x0000_i1684">

Следовательно,

<img width=«165» height=«28» src=«ref-2_699995688-503.coolpic» v:shapes="_x0000_i1685">,

и относительная погрешность результата расчетов по данному алгоритму (которую можно сравнивать с аналогичной по другим алгоритмам), составит величину

<img width=«76» height=«47» src=«ref-2_699996191-225.coolpic» v:shapes="_x0000_i1686">,

где через Tобозначена величина, получаемая при построении расписания ( в нашем примереT
=12).

Контрольные вопросы:

1.     Перечислите основные постановки задач ресурсно-временной оптимизации на сетях.

2.     Как осуществляется оптимизация в случае нелинейности функции «время-стоимость»?

3.     Как осуществить оптимизацию затрат на инновационный проект?

Упражнение

Для выполнения комплекса операций по ремонту оборудования, представленного сетевым графиком (рис. 1.25), в первые три  дня выделено 7 ед., в четвертый и пятый день – 6 ед., а в последующее время – 8 ед. ресурсов. Каждой дуге графика приписаны два числа: первое – временная оценка в днях; второе – количество потребляемых ресурсов при выполнении операции.

<img width=«533» height=«252» src=«ref-2_699996416-2297.coolpic» v:shapes="_x0000_s1198 _x0000_s1199 _x0000_s1200 _x0000_s1201 _x0000_s1202 _x0000_s1203 _x0000_s1204 _x0000_s1205 _x0000_s1206 _x0000_s1207 _x0000_s1208 _x0000_s1209 _x0000_s1210 _x0000_s1211 _x0000_s1212 _x0000_s1213 _x0000_s1214 _x0000_s1215 _x0000_s1216 _x0000_s1217 _x0000_s1218">



7(2)
Рис. 1.25. 

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

1.     Мардас А. Н., Мардас О.А.Краткий курс практического менеджмента. – СПб.: Литера, 2002.

2.     Вентцель Е.С. Введение в исследование операций. – М.: «Советское радио», 1964.    продолжение
--PAGE_BREAK--
1.3.        
Специальные транспортные  задачи и алгоритмы

Критерии оптимальности в транспортных задачах.  Минимаксная транспортная задача. Транспортная задача с приоритетами. Динамические транспортные задачи. Динамические транспортные задачи с запаздыванием. Порядок решения специальных задач на компьютере.
Простые модификации транспортной задачи
Транспортная задача находит широкое применение при решении задач материально-технического обеспечения, распределении ресурсов, организации ремонта техники и т.п.

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

Требуется минимизировать

<img width=«100» height=«47» src=«ref-2_699998713-436.coolpic» v:shapes="_x0000_i1687">

при ограничениях

<img width=«165» height=«47» src=«ref-2_699999149-445.coolpic» v:shapes="_x0000_i1688">

<img width=«173» height=«45» src=«ref-2_699999594-442.coolpic» v:shapes="_x0000_i1689">

<img width=«327» height=«47» src=«ref-2_700000036-701.coolpic» v:shapes="_x0000_i1690">

где

с
ij   — стоимость перевозки единицы груза из  i-того пункта от­правления до  j-того пункта назначения;

x
ij
-количество груза, пе­ревезенного из i
-того пункта отправления в j
-тый пункт назначе­ния;

a
ij
—запасы груза на i-том пункте отправления;

b
ij
—потреб­ности в грузе на j
-том пункте назначения.

Ограничения транспортной задачи означают, что количество груза, выво­зимого из i
-го пункта отправления, равно запасам груза в этом пункте и количество груза, ввозимого в j
-ый пункт назначения, равно потребностям в грузе для данного пункта назначения. Из последнего условия  следует, что общие запасы и потребности в грузе равны.

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

Классическая транспортная задача (ТЗ) является задачей линейного программи­рования и может быть решена симплексным методом. Однако ос­новная особенность этой задачи — равенство единице коэффициен­тов в уравнениях-ограничениях позволила разработать специальные методы ее решения, более эффективные, чем симплексный метод.

В работе Л. В. Канторовича «Математические методы органи­зации и планирования производства», вышедшей в <metricconverter productid=«1939 г» w:st=«on»>1939 г., изло­жен метод разрешающих множителей и указано, что он пригоден для решения транспортной задачи. В <metricconverter productid=«1949 г» w:st=«on»>1949 г. Л. В. Канторович и М. К. Гавурин предложили один из наиболее эффективных мето­дов решения транспортной задачи — метод потенциалов.

При решении транспортной задачи на ЭВМ наиболее эффекти­вен венгерский метод, разработанный в конце 50-х годов прошлого века.

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

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

Простейшим способом определения опорного плана является так называемый способ «северо-западного угла».

Сущность его поясним на конкретном примере. Допустим, что тре­буется определить опорный план для ТЗ, исходные данные для ко­торой приведены в табл. 1.15. Будем заполнять ее перевозками постепенно, начиная с левой верхней клетки («северо-западного» угла таблицы). Первой заполняется клетка A
1 –
B
1.Спрос пункта назначения В1 составляет 30 единиц, запасы пункта отправления а1—40 единиц. Следовательно, спрос В1 можно полностью удов­летворить за счет запасов А1. Следующая клетка A
1 –
B
2. Спрос пункта назначения В2 — 100 единиц, оставшиеся запасы пункта отправления А1—10 единиц. Назначаем перевозку A
1 –
B
2 — 10 единиц. Так как запасы пункта отправления А1 полностью ис­черпаны, то переходим к пункту отправления А2. Рассмотрим клет­ку A
2 –
B
2. Неудовлетворенный спрос В2, составляет 90 единиц, за­пасы А2—80 единиц. Назначаем перевозку A
2 –
B
280 единиц. За­пасы пункта отправления А2, полностью исчерпаны, переходим к распределению запасов пункта отправления A
3.
Таблица 1.15

<img width=«124» height=«65» src=«ref-2_700000737-261.coolpic» v:shapes="_x0000_s1222">ПН

ПО

<img width=«40» height=«49» src=«ref-2_700000998-306.coolpic» v:shapes="_x0000_i1691">

<img width=«43» height=«49» src=«ref-2_700001304-322.coolpic» v:shapes="_x0000_i1692">

<img width=«43» height=«51» src=«ref-2_700001626-317.coolpic» v:shapes="_x0000_i1693">

<img width=«35» height=«51» src=«ref-2_700001943-243.coolpic» v:shapes="_x0000_i1694">

<img width=«35» height=«43» src=«ref-2_700002186-249.coolpic» v:shapes="_x0000_i1695">

10

1

3

40

<img width=«38» height=«43» src=«ref-2_700002435-266.coolpic» v:shapes="_x0000_i1696">

6

2

5

80

<img width=«38» height=«45» src=«ref-2_700002701-265.coolpic» v:shapes="_x0000_i1697">

12

5

14

60

<img width=«33» height=«48» src=«ref-2_700002966-252.coolpic» v:shapes="_x0000_i1698">

30

100

50

80



Пункту назначения В2, требуется еще 10 единиц; пункту назна­чения В3 — 50 единиц. Запасы пункта отправления A
3 составляют 60 единиц. Назначаем перевозку A
3 –
B
2,—10 единиц, A
3 –
B
3— 50 единиц. Полученное распределение перевозок приведено в табл. 1.16. Таким образом, способ «северо-западного угла» весьма прост, но полученный с его помощью план может существенно от­личаться от оптимального плана.
Таблица 1.16

<img width=«124» height=«65» src=«ref-2_700000737-261.coolpic» v:shapes="_x0000_s1223">ПН

ПО

<img width=«40» height=«49» src=«ref-2_700000998-306.coolpic» v:shapes="_x0000_i1699">

<img width=«43» height=«49» src=«ref-2_700001304-322.coolpic» v:shapes="_x0000_i1700">

<img width=«43» height=«51» src=«ref-2_700001626-317.coolpic» v:shapes="_x0000_i1701">

<img width=«35» height=«51» src=«ref-2_700001943-243.coolpic» v:shapes="_x0000_i1702">

<img width=«35» height=«43» src=«ref-2_700002186-249.coolpic» v:shapes="_x0000_i1703">

10

30

1

10

3

40

<img width=«38» height=«43» src=«ref-2_700002435-266.coolpic» v:shapes="_x0000_i1704">

6

2

80

5

80

<img width=«38» height=«45» src=«ref-2_700002701-265.coolpic» v:shapes="_x0000_i1705">

12

5

10

14

50

60

<img width=«33» height=«48» src=«ref-2_700002966-252.coolpic» v:shapes="_x0000_i1706">

30

100

50

80



Лучшие результаты дает способ наименьшего элемента в мат­рице. Сущность этого способа рассмотрим на этом же примере. В табл. 1.15 выбираем клетку с минимальным эле­ментом. Такой клеткой является A
1–
B
2.Потребности пункта на­значения В2 составляют 100 единиц, запасы пункта отправления А1 —40 единиц. Назначаем перевозку А1—В2 в40 единиц. Так как запасы пункта отправления А1 полностью исчерпаны, то первую строку исключаем из дальнейшего рассмотрения. Определяем сле­дующую клетку A
2 –
B
2 с минимальным элементом. Неудовлетво­ренные запасы пункта назначения В2 - 60 единиц, запасы пункта отправления А2 — 80 единиц, назначаем перевозку A
2–
B
2 —60 еди­ниц. Аналогичным образом назначаем все остальные перевозки, указанные в табл. 1.17.
Таблица 1.17

<img width=«124» height=«65» src=«ref-2_700000737-261.coolpic» v:shapes="_x0000_s1224">ПН

ПО

<img width=«40» height=«49» src=«ref-2_700000998-306.coolpic» v:shapes="_x0000_i1707">

<img width=«43» height=«49» src=«ref-2_700001304-322.coolpic» v:shapes="_x0000_i1708">

<img width=«43» height=«51» src=«ref-2_700001626-317.coolpic» v:shapes="_x0000_i1709">

<img width=«35» height=«51» src=«ref-2_700001943-243.coolpic» v:shapes="_x0000_i1710">

<img width=«35» height=«43» src=«ref-2_700002186-249.coolpic» v:shapes="_x0000_i1711">

10

1

40

3

40

<img width=«38» height=«43» src=«ref-2_700002435-266.coolpic» v:shapes="_x0000_i1712">

6

2

60

5

20

80

<img width=«38» height=«45» src=«ref-2_700002701-265.coolpic» v:shapes="_x0000_i1713">

12

30

5

14

30

60

<img width=«33» height=«48» src=«ref-2_700002966-252.coolpic» v:shapes="_x0000_i1714">

30

100

50

80



Еще более точное приближение опорного плана к оптимальному дает способ Фогеля (способ предложен американским ученым У. Фогелем).

Процесс решения  начинается с определения разностей между двумя наименьшими элементами каждой строки и каждого столб­ца (табл. 1.18). Обозначим эти разности <img width=«30» height=«37» src=«ref-2_700008180-212.coolpic» v:shapes="_x0000_i1715"> и <img width=«34» height=«39» src=«ref-2_700008392-222.coolpic» v:shapes="_x0000_i1716">соответственно. На­пример, в строке А1 минимальный элемент равен 1, следующий за ним по величине элемент—3, разность между ними оказывается равной 2. Эта и другие разности по строкам и столбцам выписаны в табл. 1.18. За­тем из всех разностей строк и столбцов выбираем наибольшую. В нашем примере это разность <img width=«32» height=«37» src=«ref-2_700008614-218.coolpic» v:shapes="_x0000_i1717">=7 в строке A
3. Определяем клетку с мини­мальным элементом в этой строке A
3 –
B
2и в эту клетку записываем поставки A
3 –
B
260 единиц. Запасы пункта отправления A
3 исчер­паны. Исключаем строку A
3из рассмотрения и определяем новые разности. В нашем примере разности не изменились, но в общем случае они могут и пересчитываться. Определяем следующую мак­симальную разность 4, которой соответствует минимальный эле­мент в клетке A
2 –
B
1, равный 6. Назначаем перевозки A
1–
B
2 и аналогич­ным образом продолжаем вычислительную процедуру до назна­чения всех перевозок. Результаты назначения приведены в табл. 1.18.
Таблица 1.18

<img width=«124» height=«65» src=«ref-2_700000737-261.coolpic» v:shapes="_x0000_s1225">ПН

ПО

<img width=«40» height=«49» src=«ref-2_700000998-306.coolpic» v:shapes="_x0000_i1718">

<img width=«43» height=«49» src=«ref-2_700001304-322.coolpic» v:shapes="_x0000_i1719">

<img width=«43» height=«51» src=«ref-2_700001626-317.coolpic» v:shapes="_x0000_i1720">

<img width=«35» height=«51» src=«ref-2_700001943-243.coolpic» v:shapes="_x0000_i1721">

<img width=«35» height=«44» src=«ref-2_700010281-238.coolpic» v:shapes="_x0000_i1722">

<img width=«35» height=«43» src=«ref-2_700002186-249.coolpic» v:shapes="_x0000_i1723">

10

1

3

40

40

2

<img width=«38» height=«43» src=«ref-2_700002435-266.coolpic» v:shapes="_x0000_i1724">

6

30

2

40

5

10

80

3

<img width=«38» height=«45» src=«ref-2_700002701-265.coolpic» v:shapes="_x0000_i1725">

12

5

60

14

60

7

<img width=«33» height=«48» src=«ref-2_700002966-252.coolpic» v:shapes="_x0000_i1726">

30

100

50

80



<img width=«40» height=«46» src=«ref-2_700011551-247.coolpic» v:shapes="_x0000_i1727">

4

1

2





Сравним опорные планы, полученные рассмотренными спосо­бами.

Опорный план, полученный способом «северо-западного угла», дает следующую стоимость перевозок:

L
1=10*30+1*10+2*80+5*10+14*50= 1220.

Опорному плану, полученному способом наименьшего элемента (см. табл.3.3), соответствует

L
2=1 • 40+2 • 60+5 • 20+ 12 • 30+ 14 • 30= 1040.

Наиболее точные результаты дает опорный план, полученный способом Фогеля (см. табл.3.4):

L
3=5*60+6*30+2*40+5*10+3*40=730.

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

Транспортная задача по критерию времени (минимаксная ТЗ). Во многих практи­ческих задачах эффективность перевозок определяется не их стои­мостью, а временем Т, в течение которого все перевозки будут за­вершены. Тогда наилучшим планом перевозок бу­дет считаться тот план, при котором время окончания всех перево­зок минимально.

Обозначим через t
ijвремя, необходимое на пере­возку груза из пункта отправления Аi
,в пункт назначения Вj
. Предполагается, что время t
ijне зависит от количества перевози­мого груза хij
.  Тогда математически транспортная задача по критерию времени может быть сфор­мулирована следующим образом.

Требуется определить план перевозок, при котором

                   <img width=«111» height=«48» src=«ref-2_700011798-317.coolpic» v:shapes="_x0000_i1728">                                                (1.44)

при ограничениях

<img width=«77» height=«47» src=«ref-2_700012115-337.coolpic» v:shapes="_x0000_i1729">  <img width=«65» height=«21» src=«ref-2_700012452-143.coolpic» v:shapes="_x0000_i1730">,                                    (1.45)

<img width=«76» height=«45» src=«ref-2_700012595-336.coolpic» v:shapes="_x0000_i1731">  <img width=«65» height=«21» src=«ref-2_700012931-142.coolpic» v:shapes="_x0000_i1732">,                                     (1.46)

Задача (1.44) — (1.46) не является задачей линейного програм­мирования. Однако, последовательно решая эту задачу по крите­рию стоимости (t
ijиграет роль стоимости перевозок) и запрещая после каждого решения элементы матрицы стоимости, для которых

tij<img width=«13» height=«16» src=«ref-2_700013073-87.coolpic» v:shapes="_x0000_i1733"> tij
*
=
max

tij для хij
>0,

можно получить решение задачи (1.44)— (1.46).

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

Рассмотрим пример. Пусть задана матрица

<img width=«12» height=«23» src=«ref-2_699720446-73.coolpic» v:shapes="_x0000_i1734"><img width=«251» height=«75» src=«ref-2_700013233-4169.coolpic» v:shapes="_x0000_i1735">

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

<img width=«216» height=«40» src=«ref-2_700017402-2547.coolpic» v:shapes="_x0000_i1736">

Максимальное значение времени  для ненулевых перевозок t11 =10. Подставляя t11 =М,по­лучим

<img width=«177» height=«44» src=«ref-2_700019949-2665.coolpic» v:shapes="_x0000_i1737">,
Вновь решив задачу по критерию стоимости для данной матрицы, получим новый план

<img width=«321» height=«62» src=«ref-2_700022614-4087.coolpic» v:shapes="_x0000_i1738">,

которому соответствует максимальное время перевозки t21=7. Заменяя все значения tij
>7 на М, получим новую матрицу

<img width=«322» height=«51» src=«ref-2_700026701-3919.coolpic» v:shapes="_x0000_i1739">.

Так как все элементы первого столбца равны М, то получен­ная при решении такой задачи по критерию стоимости целевая функция L
>М.Следовательно, оптимальному решению задачи по крите­рию времени соответствует план, полученный на предыдущем шаге и Т=7.

Необходимо за­метить, что при решении задач по критерию стоимости на первых итерациях могут быть использованы приближенные способы опре­деления допустимого плана. Последняя итерация, которая приво­дит к L
>М,должна быть выполнена методом потенциалов или венгерским методом, так как эти методы обеспечивают точное ре­шение задачи.

Транспортная задача с приоритетами возникает, если при обеспечении удовлетворения потребителей (поставщиков) необходимо обеспечить обслуживание в определенной очередности. Мы рассмотрим суть данной задачи в рамках динамической транспортной задачи.    продолжение
--PAGE_BREAK--