- •Введение
- •Глава I определениясистемного анализа
- •Системность - общее свойство материи
- •Определения системного анализа
- •Понятие сложной системы
- •Характеристика задач системного анализа
- •Особенности задач системного анализа
- •Глава 2 характеристика этапов системного анализа
- •Процедуры системного анализа
- •Анализ структуры системы
- •Построение моделей систем
- •Исследование ресурсных возможностей
- •Определение целей системного анализа
- •Формирование критериев
- •Генерирование альтернатив
- •Реализация выбора и принятия решений
- •Внедрение результатов анализа
- •Глава 3 построение моделей систем
- •Понятие модели системы
- •Агрегирование - метод обобщения моделей
- •Глава 4 имитационное моделирование - метод проведения системных исследований
- •Сущность имитационного моделирования
- •Композиция дискретных систем
- •Содержательное описание сложной системы
- •Глава 5 теория подобия - методология обоснования применения моделей
- •Модели и виды подобия
- •Основные понятия физического подобия
- •Элементы статистической теории подобия
- •Глава 6 эксперимент - средство построения модели
- •Характеристика эксперимента
- •Обработка экспериментальных данных
- •Глава 7 параметрические методы обработки экспериментальной информации
- •7.1. Оценивание показателей систем и определениеихточности
- •7.2. Использование метода максимального правдоподобия для оценивания параметров законов распределения
- •Глава I определения системного анализа 7
- •Глава 2 33
- •Глава 3 построение моделей систем 53
- •Глава I определения системного анализа 7
- •Глава 2 33
- •Глава 3 построение моделей систем 53
- •7.5. Примеры оценки показателей законов распределения
- •Глава 8
- •Глава I определения системного анализа 7
- •Глава 2 33
- •Глава 3 построение моделей систем 53
- •Формулировка теоремы Байеса для событий
- •Глава I определения системного анализа 7
- •Глава 2 33
- •Глава 3 построение моделей систем 53
- •8.3. Вычисление апостериорной плотности при последовательном накоплении информации
- •Достаточные статистики
- •Сопряженные распределения
- •8.9. Оценивание параметров семейства гамма-распределений
- •Глава I определения системного анализа 7
- •Глава 2 33
- •Глава 3 построение моделей систем 53
- •Глава 9
- •Общие замечания
- •Ядерная оценка плотности
- •Глава 10
- •Задача линейного программирования
- •Глава I определения системного анализа 7
- •Глава 2 33
- •Глава 3 построение моделей систем 53
- •Метод искусственных переменных
- •Дискретное программирование
- •Нелинейное программирование
- •Глава 11 системный анализ и модели теории массового обслуживания
- •Глава I определения системного анализа 7
- •Глава 2 33
- •Глава 3 построение моделей систем 53
- •Замкнутые системы с ожиданием
- •11.5. Пример расчета надежности системы с ограниченным количеством запасных элементов
- •Глава 12 численные методы в системном анализе
- •Метод последовательных приближений
- •Глава I определения системного анализа 7
- •Глава 2 33
- •Глава 3 построение моделей систем 53
- •Глава 13 выбор или принятие решений
- •Глава I определения системного анализа 7
- •Глава 2 33
- •Глава 3 построение моделей систем 53
Дискретное программирование
Постановка задачи дискретного программирования. Многие задачи системного анализа, такие как распределение ресурсов, задачи сетевого планирования и управления, календарного планирования, описываются математическими моделями дискретного программирования.
Рассмотрим общую задачу максимизации.
Найти тах/(хх,х2,..., хп) (10.10)
при условиях
g,(xt, X2,..., хп )< 0;
(10.11)
Sm (X1,X2,...,хп) < 0;
V- =J-V =Ox = 4 —.
ОПТ 2 5 2 опт 9 3 ОПТ 2
2
Проверка показывает, что никакое округление компонент этого плана не дает допустимого решения, удовлетворяющего ограничениям этой задачи. Искомое целочисленное решение задачи X1 опт= 2, X2 от~2,х3от=5.
Таким образом, для решения задачи дискретного программирования (ЗДП) необходимы специальные методы. Методы решения ЗДП по принципу подхода к проблеме делят на три группы: 1) методы отсечения или отсекающих плоскостей; 2) метод ветвей и границ; 3) методы случайного поиска и эвристические методы.
Математические модели задач дискретного программирования. По структуре математической модели задачи дискретного программирования разделяют на следующие классы:
задачи с неделимостями;
экстремальные комбинаторные задачи;
задачи на несвязных и на невыпуклых плоскостях;
задачи с разрывными целевыми функциями.
Рассмотрим существо некоторых из них.
Задачи с неделимостями. Математические модели задач с неделимостями основаны на требовании целочисленности переменных {х}, вытекающем из физических условий практических задач.
К таким задачам относится задача об определении оптимальной структуры производственной программы, где [xjt X2,..., хл} - объемы выпуска продукции.
Эта задача заключается в отыскании
шfYcjxj (10.13)
при
Yaijxj-bi(i=\,2,...,m) (10.14)
J=і
X1 >0,х2 >0,...,хп 2 0;х; -целые при je.J. (10.15)
Если J = N = (1, 2,..., п), то задача называется полностью целочисленной, в противном случае, ecsmJ^N-частично целочисленной.
Задача о ранце. Одной из наиболее распространенных задач целочисленного программирования является так называемая задача о ранце.
Рассмотрим постановку данной задачи. Турист готовится к длительному переходу в горах. В рюкзаке он может нести груз, масса которого не более W. Этот груз может включать в себя п видов предметов, каждый предмет типа j, массой оо J= 1, 2,..., п. Для каждого вида предмета турист определяет его ценность E во время перехода. Задача заключается в определении количества предметов каждого типа, которые он должен положить в рюкзак, чтобы суммарная ценность снаряжения была максимальной.
Обозначим через Xj количество предметов j-го типа в рюкзаке. Тогда математическая модель задачи такова:
(10.16)
J=і
при ограничениях
YjbjX J<W, Xj > 0, Xj-целое, г'= 1,2,..., т. (10.17)
J=і
Экстремальные комбинаторные задачи. В данных задачах необходимо найти экстремум некоторой целевой функции, заданной на конечном множестве, элементами которого служат перестановки из п
символов (объектов).
Одной из наиболее простых задач этого класса является задача о назначениях-, найти такую перестановку (px,p2,...,pj из чисел 1, 2, 3,...,
п
п, при которой обеспечен mmXc,p по всем перестановкам (р{,р2,...,р). Каждая такая перестановка может быть представлена точкой в п2-
мерном евклидовом пространстве или в виде матрицы Xnxn = ||х,у1|.
Вводим переменные :
= 1, если г'-й механизм предназначен для /-Й работы;
Xjj = 0-в противном случае.
Очевидно, что должно выполняться условие
YxV = 1;IxU = 1; 1 = п;І = 1' п-(10-18)
>=1 J=I
Данные ограничения означают, что один механизм может быть предназначен для выполнения только одной работы. Тогда задача будет состоять в определении таких чисел {xj, при которых достигается минимум функционала при ограничениях (10.18). Задача о коммивояжере. Ймеется (п + 1) город. Задана матрица
С = ||с(:/1 расстояний между городами. Выезжая из исходного города Aff коммивояжер должен побывать во всех остальных городах по одному разу и вернуться в город Aq. Требуется определить, в каком порядке следует объезжать города, чтобы суммарное пройденное расстояние было минимально.
Введем переменные:
Xjj= 1, если коммивояжер переезжает из населенного пункта AlBAj;
Xij = 0 - в противном случае.
Математическая модель задачи имеет следующий вид:
найти
minXX^xiy (10.19)
1*0 J= о
при условиях
YxU =1’(j = 1>2’-’п);(10.20)
1=0
JlXij = 1, (і = I, 2,..., n);
(10.21)
Ui-Uj^nxij <n-l, (i,;' = l, 2(10.22)
где и., му - произвольные целые и неотрицательные числа.
Условие (10.20) означает, что коммивояжер выезжает из каждого города один раз, а условие (10.21) - что он въезжает один раз в каждый город.
Если ограничить задачу только условиями (10.20) и (10.21), она будет эквивалентна задаче о назначениях, план которой не обязан быть цикличным. Иначе говоря, путь коммивояжера при этом можно представить как ряд несвязанных подциклов, в то время как его путь в действительности состоит из одного цикла.
Покажем, что для любого цикла, начинающегося в Ag, можно найти
и., удовлетворяющие условию (10.22). Пусть и. =р, если коммивояжер посещает город А. нар-м этапе. Отсюда следует, что U1- и.< п - 1 для всех і и у, и, таким образом, условие (10.22) выполняется при Xfj = 0. При Xij = 1 условие (10.22) выполняется как строгое равенство:
Ui-Uj +nx.j = p-(p + l) + n = n-l.
Метод ветвей и границ для задачи целочисленного программирования. Рассмотрим частично целочисленную задачу ЛП: минимизировать
г = /(X) = JciXi, (10.23)
1=1
при условиях
JaijXi > Ъ}, 0 =1, 2,..., т)•; (10.24)
1=1
0<х, (i = i,2,...,л); (10.25)
х. - целые числа. (10.26)
Процесс поиска оптимального решения начинают с решения непрерывной задачи ЛП. Если полученный при этом оптимальный план X0 не удовлетворяет условию (10.26), то значение целевой функции ^0=/(X0) дает нижнюю оценку для искомого решения, т.е. min z = ^0.
Пусть некоторая переменная х.0 (1< iQ < т) не получила в плане
X0 целочисленного решения. В целочисленном плане значение X10 следует либо уменьшить, по крайней мере до [х.0], либо увеличить, по крайней мере до [X0]+ 1.
Если границы изменения хю заранее не заданы, то их можно вычислить, решив для этого две вспомогательные задачи ЛП. Эти задачи состоят в максимизации и минимизации хю при условиях (10.24) и (10.25).
Теперь для каждого фиксированного целочисленного значения хй в найденном отрезке (X0min, Xi0max) находят minz, решая задачу ЛП с ограничениями (10.24), (10.25) и с дополнительным ограничениемх(0< кю.
Таким образом, все указанные выше возможности можно представить в виде некоторого дерева, в котором вершина 0 отвечает плану
X0, а каждая из соединенных с ней вершин отвечает оптимальному плану следующей задачи: минимизировать z при условиях (10.24), (10.25) и дополнительном условии, что переменной х0 дано значение хю < кю, где к& - целое число. Каждой из таких вершин приписывают оценку Qk) = q(i , к), которая равна minz при указанных выше ограничениях. Очевидно, |0 < £(/0, к), для всех к.
Если оптимальные планы полученных задач удовлетворяют условиям целочисленности, то план с минимальной оценкой = ^(/0, к) и будет оптимальным планом исходной задачи. В противном случае возникает необходимость в продолжении ветвления. При этом каждый раз для очередного ветвления выбирают вершину с наименьшей оценкой.
Любой маршрут в дереве от начальной вершины 0 до некоторой вершины определяет допустимую последовательность выбора целочисленных решений для переменных. Процесс продолжают до тех пор, пока продолжение ветвления становится невозможным.
' Каждая конечная вершина отвечает некоторому допустимому целочисленному плану. Вершина с минимальной оценкой дает оптимальный план.
Рассмотрим алгоритм решения задачи целочисленного программирования. На первом этапе необходимо задать множество G(0), определяемое условиями (10.24), (10.25). Далее формируются множества
G^}(v = l, 2,..., pt; к = I, 2,...), задаваемые условиями (10.24), (10.25) и дополнительным условием
Xj <[*;„] или Xj <[х;о], (10.27)
где [Xyo] - целая часть Xyo.
^Далее осуществляется вычисление оценок. Для множества G(0)
оценку £(G(0)) определяют как £(G<0))= /(Х0), где X0 - оптимальный план непрерывной задачи ЛП.
;(1)
73
•
Для множества Gv'*' оценку £(G**’) определяют аналогично:
$(с'*>) = /(х<*>),
где Х<*> - оптимальный план задачи с условиями (10.24), (10.25) и с дополнительным условием (10.27).
Если множество Gjlci оказывается пустым, ему приписывают оценку
^Gf1) = CO.
На следующем этапе осуществляется нахождение планов. Если план X0 удовлетворяет условию целочисленности (10.26), X0-оптимальный план задачи. Если Xlvk) удовлетворяет условию целочисленности (10.26), он является оптимальным планом задачи с условиями (10.24), (10.25), (10.27) и некоторым планом исходной задачи (10.23) - (10.26).
Далее выполняют ветвление. Ветвление производят в том случае, когда план Xf1 не удовлетворяет условию целочисленности (10.26).
Пусть X1pkJ - одна из нецелочисленных компонент плана, где 1 < р <«,, тогда множество G**1 разбивают на два подмножества:
gV*1 = gVJ1Ug^ ’ iiPh46m
G<*> ={Х/Хє GlkK хр <[дсД (10.28)
G™={х/х є GlkK хр >[<v>] + l}.(10.2?)
Укажем некоторые особенности метода ветвей и границ для задач ЦП.
Если все коэффициенты Cj целевой функции - целые при 1 <7 < я, и равны нулю при j > я,, то оценку J;(G<‘>) можно заменить на более
сильную оценку £1(g*m) = ]/(x*‘’)£, где ]а[ обозначено наименьшее целое, но не меньшее, чем а, т.е. округленное до ближайшего целого с избытком.
Алгоритм метода в вычислительном отношении представляет собой последовательность задач ЛП, причем конечность алгоритма следует из предполагаемой ограниченности множества G.
Из описания алгоритма следует, что в применении метода ветвей и границ для полностью целочисленных и для частично целочисленных задач нет никакой разницы.
Геометрически этот метод можно интерпретировать таким образом. Гипер-плоскость, определяемая целевой функцией задачи, вдавливается внутрь многогранника планов соответствующей задачи ЛП до встречи с ближайшей целочисленной точкой этого многогранника.
■ Пример применения метода ветвей и границ для решения задач дискретного программирования. Постановка задачи следующая: минимизировать функцию min(-x, +х2) при ограничениях
Ixl +1 Ix2 < 38;
X1 +х2 <7;
Axl - Sx2 < 5;
X1, Xi > 0; X1, х2 - целые числа.
—* {40 231
Нулевой шаг. Оптимальный план задачи ЛП X0 = —,— , тоща
имеем £(G0) = ]/(X0)[ = ]-7[ = -7.
Поскольку план X0 не удовлетворяет условию целочисленности, возьмем его нецелочисленную компоненту X1 и разобьем множество
G(0) на G,(l> и G‘'>:
G,(,) = (x/XeG°,x, <4};
Gjn=IXZXeG0, *,>5}- Первый шаг. Решаем две задачи ЛП, заключающиеся в минимизации исходной задачи по множествам G,0) и Gj1'.
В первом случае минимум достигается при
ҐЇЇ
Множество Gj0 оказывается пустым, поэтому = ■
Разбиваем g,(1) на G10/ и G,™, где G1tJ' ={Х/Хе G,°\ х2 <2j и
, G# = {Х/Хє G,(1), X2 > З}. Обозначим G"1 = G<2>, Gg =Gf, G® =G<2>.
Второй шаг. Решаем две задачи ЛП, заключающиеся в минимизации исходной задачи при дополнительном ограничении X1 < 2 и х2 > 3, тогда
-5-
=
-5:
=
-5; С2)
и»
Х,^=|з1 2} и ^1(Gf) = Xf ={2І 3} и ^1(Gf) =
-5—
2
Gf=O^1(Gf) = -. Производим разветвление множества G,(2):
G,(2) =G®(JG
Xf = Xf =|гі, з| и S1(Gf) = -S; G43 =Gf =0 и №f ) = ~. Дерево решении приведено нарис. 10.2.
Итак получен целочисленный план Xf = {3,2}, причем = min^1 (Cf )£' (Cf )£' (Cf );^ (Cf )} = min{-5; °°; -5; ~} = -5. План Xf ={3,2} - оптимальный, так как
/(X) = -5 < min&Gf ),^(Gf ),^(Gf)}.
где Gf = {Х/Хє Gf, X1 <3},Gf ={Х/Хє Gf, х, >4}.
Обозначим Gf = G,(3), Gf =Gf, Gft = Gf, Gf =Gf.
Третий шаг. Решаем две задачи ЛП, заключающиеся в минимизации исходной задачи по множествам Gf и Gf.
Находим Xf ={3,2} и §*(Gf )=]-5[=-5; Gf=O и ^'(Gf ) = -,
Рис.
10.2.
Дерево решений
задачи
целочисленного
программирования