В слу чае конечного допустимого множества число его элементов обыч но настолько велико, что их прямой перебор с целью поиска экстремума оказывается практически нереализуемым. Так, например, целочисленное линейное программирование зани мается изучением и решением задачи линейного программирова ния с дополнительным условием целочисленности участвующих в постановке данной задачи переменных. Распространенными ме тодами решения таких задач являются методы отсечения. Каноническая задача целочисленного линейного программи рования в матричной форме записи имеет вид: С(Л = (С,^)-^тах Ах^Ь Xj > О X:- целые числа, j =\,2,...,и Здесь X = (хрХ,,--,А'„) есть вектор переменных, принимающих п целые значения; (С, А^ = ^^i^i - скалярное произведение векто- ра С=(Ср С2, ..., с^) на вектор X; А=(а.) - матрица системы огра ничений размера т х п; b - вектор размерности т свободных членов системы ограничений. Если j = i,/7,, где /ij < /7, то соответствующая задача называ ется часнгично-целочисленной, при этом (п -п^) переменных могут принимать любые вещественные значения. В задачах дискретного программирования переменные при нимают дискретные вещественные значения. Много экономических задач содержат целочисленные пере менные. Эти задачи имеют устоявшуюся классификацию. 1. Задачи с неделимостями. Сюда относятся задачи планиро вания дискретного производства, например планирование выпус ка станков, турбин, морских судов, атомных реакторов и т.д.; транспортные задачи, в которых необходимо определить опти мальное число вагонов, автомашин, судов; задачи оптималь ного раскроя материалов; задачи размещения контейнеров на палубах судов; планирование научно-исследовательских работ, не переходящих на следующий период (год). Классический пример задачи с неделимостями - задача о ран це, которая формулируется следующим образом. Имеется п пред метов, объем каждого предмета равен v , / = l,/t, объем ранца - F, с. - ценность /-го предмета. Все предметы не помещаются в ранец. Требуется определить такой набор предметов, которые следует поместить в ранец, чтобы при этом их суммарная цен ность была максимально возможной. Вместо объема может быть использован вес предмета (упаковки товара). Соответствующая математическая модель имеет следующий вид: /=1 /=1 где Л7 = 1, если /-Й предмет отбирается для укладки в ранец, О в обратном случае. 2. Комбинаторные задачи. В них требуется найти экстремум функции (чаще всего линейной) нескольких переменных на ко нечном множестве элементов. Из комбинаторных экстремальных задач, сводящихся к моделям дискретного программирования и имеющих большое прикладное значение, следует выделить зада чу о назначениях, задачу о коммивояжере (о бродячем торговце) и задачи теории расписаний. Задача о назначениях состоит в назначении п кандидатов на заданные п работ, при котором суммарные затраты минимальны (или общий экономический эффект максимален). При этом каж дого кандидата можно назначить только на одну работу, а каж дая работа должна быть выполнена только одним кандидатом. Пусть время выполнения /-й работы у-м исполнителем равно /... Вводятся переменные 159 [l, если i-я работа выполняетсяу-м исполнителем, •^ [ О Б обратном случае. Математическая модель задачи о назначениях имеет следую щий вид: /7 П п п .М Задача о коммивоялсере заключается в нахождении замкнуто го маршрута, проходящего через все пункты, при котором сум марное расстояние по маршруту из начального пункта А в этот же пункт А (рис. 1) минимально. Рис. 1 Пусть имеется /7+1 город (пункт). Известна матрица расстоя ний между городами / и у, которую обозначим С =(<^/Хх;г Выезжая из какого-то начального города (например, А), ком мивояжеру необходимо объехать все города, побывав в каждом из них только по одному разу, за исключением начального, чтобы суммарное расстояние было минимальным. Вводятся переменные ^и = I, если коммивояжер переезжает из города / в городу, О в обратном случае. (1) 160 Задача о коммивояжере формулируется следующим образом: минимизировать целевую функцию (2) условиях: С(Х)= X Е 0/ •^// -^min i=OJ=0 п /=0 // 7=0 (3) (4) III -иj + п-Xj: < / ? - ! , i,j-\,п; / Ф J. (5) Переменные и. и w. в ограничениях (5) принимают произволь ные вещественные значения (не умаляя общности, их можно счи тать и целыми неотрицательными числами). Условия (3) означа ют, что коммивояжер выезжает из каждого города ровно один раз. Условия (4) показывают, что коммивояжер въезжает в каждый город только один раз. Если ограничиться условиями (3) и (4), то эта задача превращается в задачу о назначениях, решение которой не обязательно будет цикличным. Иначе говоря, путь коммивоя жера может распасться на несколько не связанных между собой подциклов. Для устранения такой возможности служит условие (5). Задачи теории расписания возникают в связи с упорядочени ем использования набора машин и оборудования для обработки некоторого множества деталей (изделий). При этом должны быть выполнены определенные технологические условия и обеспече но достижение оптимального значения заданного критерия ка чества расписания. 3. Задачи о покрытии и другие задачи дискретиой оптимизации сетей связаны с нахождением минимального подмножества ре бер заданного графа, содержащего все его вершины. Эти задачи находят применение при синтезе логических сетей, в задачах оп ределения кратчайшего пути в графе и др. 161 4. Задачи оптимального размещения производства, специализа ции и кооперирования. Так как объекты производства продукции являются неделимыми, то в таких задачах возникает требование целочисленности переменных. Размещение предприятий должно учитывать расположение источников сырья, рынков сбыта това ров и других факторов. Существуют два основных класса методов решения задач дис кретного программирования. Рассмотрим их на примере цело численного линейного программирования. 1. Методы отсечения. Суть этих методов заключается в том, что сначала задача решается без условия целочисленности. При этом может получиться целочисленный оптимальный план. В этом случае задача решена. Если план нецелочисленный, то выбира ется дробная компонента (координата) плана и строится допол нительное линейное ограничение. Это линейное ограничение обладает следующими свойствами: • данное ограничение не выполняется для нецелочисленного оптимального плана; • оно выполняется для любого допустимого целочисленно го плана. Далее решается расширенная задача с добавленным ограни чением. В результате получается либо целочисленный план, либо нецелочисленный. Если план нецелочисленный, то опять вводится новое линейное ограничение, и так далее, пока не будет найден оптимальный план или будет показано, что таких планов нет. Геометрически вводимое линейное ограничение представляет собой гиперплоскость, поэтому данный метод и назван методом отсечения, или методом отсекающих плоскостей. Впервые метод отсечения был предложен Р. Гомори. Для решения частично диск ретных задач линейного программирования методом отсечения может быть использован алгоритм Дальтона и Ллевелина. 2. Комбинаторные методы основываются на конечности чис ла допустимых планов задачи, используя ее комбинаторный ха рактер. Главная идея таких методов заключается в замене полно го перебора всех планов задачи их частичным (неполным) перебором. Это осуществляется отбрасыванием некоторых под множеств вариантов, заведомо не дающих оптимума. Дальней ший перебор ведется лишь среди оставшихся вариантов, являю щихся перспективными в отношении получения оптимального плана. По своему характеру комбинаторные методы весьма раз- 162 нообразны. При этом центральное место среди них занимают методы, объединенные под названием «метод ветвей и границ». Фактическое появление метода ветвей и границ связано с ра ботой Литтла, Мурти, Суини и Кэрел, посвященной задаче ком мивояжера, причем в этой же работе впервые было предложено общепринятое название «метод ветвей и границ». В основе этого метода при решении задачи на максимум ле жат следующие построения, позволяющие существенно умень шить объем перебора. • Вычисление верхней границы (оценки). Вычисляется верх няя оценка целевой функции на множестве допустимых планов D, • Разбиение на подмножества (ветвление). Данная процеду ра связана с разбиением множества планов D на дерево подмно жеств. Схематически процесс ветвления множества планов пока зан на рис. 2. Рис.2 • Пересчет оценок, т.е. вычисление целевой функции на вы деленных подмножествах. Если целочисленный оптимальный план не получен, то отбрасываются неперспективные варианты допустимых планов, а перспективные подмножества подлежат дальнейшему ветвлению. 163 Таким образом, сокращение перебора всех возможных реше ний задач дискретного программирования происходит за счет отсеивания по тому или иному правилу заведомо неприемлемых решений.
Ви переглядаєте статтю (реферат): «ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ» з дисципліни «Теорія систем і системний аналіз в управлінні організаціями»
