Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Сигал И.Х. -> "Введение в прикладное дискретное программирование " -> 7

Введение в прикладное дискретное программирование - Сигал И.Х.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 2 3 4 5 6 < 7 > 8 9 10 11 12 13 .. 84 >> Следующая


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

Xi + Х2 —>• max, х = (х\, Х2) Є G.

Построим область G. Пусть а > 0 — иррациональное число, например а = у/2. Тогда на прямой х% = ах і нет ни одной точки с обеими целочисленными координатами, кроме точки (0, 0). Рассмотрим прямую Х2 = OLXi при Xi > 0, Х2 > 0. Возьмем Xi = а, тогда Х2 = оса. В полученном прямоугольнике с вершинами (0,0); (а, 0); (а, аа); (0, аа) выделим все точки с целочисленными координатами и проведем из точки (а, аа) два отрезка так, чтобы в полученном четырехугольнике OABC не было ни одной целочисленной точки, кроме точки (0, 0) (рис. 1.1).

Область G построена. Параметр а может быть выбран так, чтобы решением линейной задачи была точка (а, аа), тогда, выбирая а, можно сделать (жі + Х2) = а(1 + а) сколь угодно большим числом. Решение целочисленной задачи — точка (0,0), х\ + Х2 — 0. Поэтому разность между значениями линейных функций целочисленной и линейной задачи для оптимальных решений этих задач может быть сколь угодно большой. Пусть теперь область G имеет вид треугольника ABC (рис. 1.2). В этом случае линейная задача имеет то же решение, что и ранее, а целочисленная задача неразрешима.
Гл. 1. Постановка задач дискретного программирования 19

Рассмотрение этого простого примера позволяет сделать два важных вывода:

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

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

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

Задача о ранце. Имеется п предметов, каждый из которых характеризуется стоимостью Cj > О VL весом a j > 0, j = 1, 2,..., п. Имеется ранец, грузоподъемность которого равна R > 0. Требуется положить в ранец набор предметов с максимальной суммарной стоимостью. При

п

этом предполагается, что a j > R1 0 < aj < R1 j = I, 2,..., п. Для

j=i

описания задачи на языке целочисленного линейного программирования введем булевы переменные Xj:

_ Г 1, если предмет j кладется в ранец,

J — 1 0, если предмет j не кладется в ранец.

Тогда целевая функция имеет вид

п

f(x) = CjXj —> max.

J=і

Ограничение на грузоподъемность —

п

ajxj — R-

J=I

Получена следующая задача целочисленного (булевого) линейного программирования:

п

f(x) = CjXj —> max,

J=і

п

aJxJ — ^

J = I

xJ є {ML J = 1,2,...,п.

Множество G в этой задаче — это множество п-мерных булевых векторов х = (X11 X21..., хп) с компонентами 0, 1, удовлетворяющих

2*
20 Разд. I. Предмет и модели дискретного программирования

условию

E

ajXj < R.

j=і

Очевидно, что |G| = 2". Оценим эту величину:

п = 10, 210 = 1024 ~ IO3,

п = 20 , 220 ~ IO6,

п = 30 , 230 ~ IO9,

п = 40 , 240 ~ IO12.

Если ЭВМ имеет быстродействие IO6 операций в секунду, то легко оценить время, необходимое для выполнения полного перебора.

Задача о коммивояжере. Пусть P = (1,2,... ,п) — конечное множество точек, Cij >0 — «расстояние» от точки і до точки j, с = (Cij)nxn — матрица «расстояний». Маршрут z коммивояжера — это любая перестановка точек из P, z = (i\, i%,..., in). Длина l(z) маршрута z есть сумма соответствующих элементов матрицы (?):

п

l(z) = ^2chik+i (іп+і = ч). k=I

Пусть Z — множество всех маршрутов. Необходимо найти маршрут Zo Є Z такой, что

l(zо) = min l(z), z Є Z.

В этой задаче G = Z, \G\ = (п — 1)!. Оценим величину \G\, пользуясь первым членом асимптотического представления Стирлинга для факториала n, ^ п„е-„^

Пусть п = 30, е = 2, 71 « 3, п = 3,14 « 3. Тогда

|G| и (у)3° л/2 • 3 • 30 = 10зол/Ї80;

отсюда видно, что трудоемкость вычислений резко растет с ростом размерности задачи.

1.2. Особенности задач

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

— для каждой точки х Є G можно определить некоторым образом понятие непустой окрестности Gx С G;

— можно указать достаточно эффективно проверяемые необходимые и достаточные условия локальной оптимальности; на основании этих условий локальный оптимум целевой функции на G может быть
Гл. 1. Постановка задач дискретного программирования 21

найден при помощи некоторого конечного (или бесконечного сходящегося) процесса;

— локальный оптимум целевой функции совпадает с глобальным.

К регулярным относятся задачи линейного и выпуклого программирования. К нерегулярным, наряду с дискретными, относятся многоэкстремальные задачи, в которых локальный экстремум может не совпадать с глобальным. Дискретные задачи характеризуются тем, что область допустимых решений невыпукла и несвязна, а это делает невозможным решение их с помощью стандартных методов, применяемых для решения регулярных задач математического программирования.
Предыдущая << 1 .. 2 3 4 5 6 < 7 > 8 9 10 11 12 13 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100