Задачи разбиения множества, как задача целочисленного линейного программирования. Сводимость многостадийной задачи размещения к простейшей icon

Задачи разбиения множества, как задача целочисленного линейного программирования. Сводимость многостадийной задачи размещения к простейшей


Смотрите также:
Краснер Н. Я., Пастухов А. И., Щепина И. Н...
Название Лекция-семинар: Построение математических моделей целочисленного линейного...
Название Лекция-семинар: Построение математических моделей целочисленного линейного...
Название Лекция-семинар: Построение математических моделей целочисленного линейного...
Название Лекция-семинар: Построение математических моделей целочисленного линейного...
Программа вступительного испытания по предмету «Информационные системы в экономике»...
Решение задачи линейного программирования в ms...
Задача линейного программирования. Симплекс-метод и его сходимость...
Математическое программирование в text...
Лабороторная работа №2. На основе первой лабораторной работы разработать программу...
Задачи линейного программирования упр Составить математическую модель следующей задачи (не...
Работа По теме: «Целочисленное программирование»...



Загрузка...
скачать



ОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

КАФЕДРА ПРИКЛАДНОЙ И ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ


Эффективная сводимость некоторых задач размещения производства


Дипломная работа

студентки гр. МП-804

Андрющенко А. А.





(подпись)


Научный руководитель:

к. ф. - м. н.

Еремеев А. В.





(подпись)


Омск 2003


СОДЕРЖАНИЕ


Введение.

1.

2.

3.


4.

5.

6.


7.

Многостадийная задача размещения.

1.1 Содержательная постановка многостадийной задачи размещения.

1.2 Модель многостадийной задачи размещения.

Простейшая задача размещения.

2.1 Содержательная постановка простейшей задачи размещения.

2.2 Модель простейшей задачи размещения.

Задача о наименьшем покрытии множества.

3.1 Содержательная постановка задачи о наименьшем покрытии множества.

3.2 Задача о наименьшем покрытии множества, как задача целочисленного линейного программирования.

Задача разбиения множества.

4.1 Задачи разбиения множества, как задача целочисленного линейного программирования.

Сводимость многостадийной задачи размещения к простейшей

задаче размещения.

5.1 Описание сводимости.

5.2 Пример.

5.3 Доказательство корректности сводимости.

Сводимость простейшей задачи размещения к задаче наименьшего

покрытия.

6.1 Сводимость простейшей задачи размещения к задаче разбиения

множества.

6.2 Сводимость задачи разбиения множества к задаче наименьшего

покрытия.

6.3 Связь между оптимумами задачи наименьшего покрытия и

простейшей задачи размещения.

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

Литература.

Приложение.


ВВЕДЕНИЕ


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

В данной работе рассмотрены несколько из многочисленного множества задач подобного плана. Реализована сводимость многостадийной задачи размещения (МЗР) к простейшей задаче размещения (ПЗР), а также сводимость простейшей задачи размещения к задаче о наименьшем покрытии множества (ЗНПМ).

ЗНПМ


ПЗР

МЗР




Для реализации сводимости ПЗР к ЗНПМ, использовалась задача о разбиении множества (ЗРМ).


Т4

ЗНПМ

ЗРМ











T


Т1



ПЗР

По аналогии с [11], сводимость от ПЗР к ЗРМ обозначим Т1, а от ЗРМ к ЗНПМ - Т4.

Целями данной работы являются доказательство корректности одной сводимости МЗР к ПЗР. Кроме того, требуется построить композицию сводимостей Т = (Т4○Т1) от ПЗР к ЗНПМ через ЗРМ и найти изменение значения оптимального решения при обратном переходе от ЗНПМ к ПЗР, а также провести экспериментальные исследования этой сводимости.


^ 1. МНОГОСТАДИЙНАЯ ЗАДАЧА РАЗМЕЩЕНИЯ


1.1 Содержательная постановка многостадийной задачи размещения [5].


Обозначим через I множество возможных пунктов размещения предприятий, и пусть J множество потребителей, которым необходима их продукция. Будем полагать, что имеется определённый набор типов предприятий и для производства продукции требуется участие предприятий разного типа. Без ограничения общности будем считать, что в каждом пункте iI можно разместить только одно предприятие заданного типа. Продукция, прежде чем попасть к потребителю, должна пройти несколько стадий обработки на предприятиях разного типа, т.е. заданы технологические цепочки вида p={i1,…,is(p)}, возможно, разной длины, согласно которым продукция последовательно проходит обработку на предприятиях i1, затем i2 , и т.д., is(p). В одной цепочке предприятия могут повторяться.

Пусть:

P – множество различных цепочек и положим Pi={pP | ip}, iI;

mi 0 – стоимость открытия предприятия в пункте i;

ci 0 – удельная стоимость производства;

dii` 0 – удельная стоимость транспортировки продукции из пункта i в пункт i`;

Dpj0 - суммарная удельная стоимость транспортировки к потребителю j готовой продукции, изготовленной по технологической цепочке p:

Величина задаёт удельные затраты на доставку продукции из последнего пункта is(p) к потребителю j.

p – суммарная удельная стоимость производства (задаётся аналогично)



j – объём продукции, необходимый потребителю j;


Введём следующие переменные:



.

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


^ 1.2 Модель многостадийной задачи размещения.


С использованием введённых обозначений МЗР может быть записана следующим образом:


, (1.2.1)

(1.2.2)

(1.2.3)

(1.2.4)


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

^ 2. ПРОСТЕЙШАЯ ЗАДАЧА РАЗМЕЩЕНИЯ


    1. Содержательная постановка простейшей задачи размещения [3].


Пусть:

- множество возможных пунктов производства некоторого однородного продукта;

- совокупность пунктов потребления этого продукта.

fj - (единиц) потребность в продукции в пункте потребления j

сij – затраты на перевозку единицы продукта из пункта производства i до пункта потребления j.

Требуется найти xij - потребность потребителя j в какой-либо продукции i, которая удовлетворяет приведённым в модели ограничениям.


^ 2.2 Модель простейшей задачи размещения:


, (2.2.1)

(2.2.2)

(2.2.3)

(2.2.4)

(2.2.5)


Здесь:

m- число возможных пунктов производства некоторого однородного продукта, ;

n – совокупность пунктов потребления этого продукта, ;

fi – фиксированная стоимость доставки средства i;

cij – общая стоимость поставки для потребителя j продукции i (включает в себя стоимость единицы продукции i (вместе с переменным производством, административными затратами и т.д.); стоимость транспортировки одной единицы продукции i к потребителю j; количество продукции, требуемых потребителем j), все cij>0;

yi определяется следующим образом: yi=1, если продукция i открыта и yi=0 иначе;

xij – спрос потребителя j на какую-либо продукцию i.


Ограничение (2.2.3) устанавливает связь между открытыми предприятиями и положительными перевозками.


^ 3. ЗАДАЧА О НАИМЕНЬШЕМ ПОКРЫТИИ МНОЖЕСТВА


3.1 Содержательная постановка задачи о наименьшем покрытии множества [3]:


Пусть даны множество M={1, …, m} и набор его подмножеств М1, …, Мn, такие, что . Совокупность подмножеств Mj, jJ{1, …, n} называется покрытием множества М, если . Каждому Mj приписан вес Фj0. Требуется найти покрытие минимального суммарного веса. Задача невзвешенная, если все подмножества Mj имеют единичные веса. Задачу о покрытии можно сформулировать, как задачу целочисленного линейного программирования.


^ 3.2 Задача о наименьшем покрытии множества, как задача целочисленного линейного программирования:


(3.2.1)

(3.2.2)

(3.2.3)


Здесь:

- матрица размером s*k, состоящая из нулей и единиц, подмножество   I строк определяет покрытие столбцов J, если ; λi=1 если строка i находится в покрытии и λi=0 иначе.


^ 4. ЗАДАЧА РАЗБИЕНИЯ МНОЖЕСТВА


Определение [3]: Пусть А – множество и пусть Х1, … , Хr – некоторые не пустые подмножества А. Совокупность множеств назовём разбиением множества А, если выполняются следующие условия: .


^ 4.1 Задачи разбиения множества, как задача целочисленного линейного программирования:


(4.1.1)

(4.1.2)

(4.1.3)


Здесь:

- матрица размером r*h, состоящая из нулей и единиц. Таким образом, подмножество I*  I= строчек определяет разбиение J=, если ;

zi=1 если столбец i находится в разбиении и zi=0 иначе;

bi – весовые коэффициенты для zi=1, .


^ 5. СВОДИМОСТЬ МНОГОСТАДИЙНОЙ ЗАДАЧИ РАЗМЕЩЕНИЯ К ПРОСТЕЙШЕЙ ЗАДАЧЕ РАЗМЕЩЕНИЯ


5.1 Описание сводимости


Рассмотрим сводимость МЗР к ПЗР, предложенную в [7]. Аналогичная сводимость была предложена ранее А.А. Агеевым, но с использованием полиномов от булевых переменных [1]. Интерес представляет доказательство корректности этой сводимости иным образом.

Итак, в результате сводимости строится ПЗР, где матрица С=С`={с`ij} и вектор F=F`={f`i} имеют специальную структуру:


(5.1.1)

(5.1.2)

(5.1.3)

(5.1.4)

(5.1.5)


Матрица С`={с`ij} разбита на блоки, каждый блок имеет определённый смысл:









Обычные потребители

Фиктивные

потребители первого рода


Фиктивные потребители второго рода







1 … |J|

1 … |P|

1 … |P1|

1 … |P2|




1 … |Pm|



Поставщики-цепи

1

.

.

.

|P|

d11…..d1j

. .

. .

dp1…..dpj

0  …...

 0 .…..

………….

 …..  0

……..

. .

. .

……. 

……….

. .

. .

……. ..




……..

. .

. .

……. 


Поставщики -дополнение цепей

1

.

.

.

|P|

……..

. .

. .

……. 

0  …...

 0 .…..

……….…

 …..  0

0  0 ...0

……. 

. .

……. 

……… 

 0  … 

. .

……. ...




……. .

. .

…….. 

 0 0 …



Поставщики - предприятия

1

.

.

.

|I|

……..

. .

. .

……. 

……..

. .

. .

……. 

0  …...

 0 .…..

………...

 …..  0

0  …...

 0 .…..

……….….

 …..  0




0  …...

 0 .…..

……….…

 …..  0


Обозначим каждый блок матрицы С`={с`ij} цифрой для более наглядного объяснения построения:




















I1.


I2.


I3.


I4.





Iw.


II1.


II2.


II3.


II4.





IIw.


III1.


III2.


III3.


III4.





IIIw.


Будем называть «флаговой строкой» в блоке II3 первую строку, в блоке II4 вторую строку, и так далее, в блоке IIw последнюю строку.

Здесь строки, относящиеся к блокам II3, …, IIw имеют нули во «флаговой» строке в столбцах i, если i-е предприятие входит в данную цепочку. Остальные элементы блоков II3, …, IIw равны . Столбцы, содержащие бесконечность во «флаговой» строке вычёркиваем. Эти блоки назовём фиктивными потребителями второго рода.

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

dpj=i(p+Dpj).


Из структуры матрицы видно, что в построенной ПЗР число потребителей составляет |J|+|P|+, а число предприятий равно 2|P|+|I|. Здесь , где - количество предприятий, входящих в первую цепочку, - количество предприятий, входящих во вторую цепочку, и так далее, - количество предприятий, входящих в последнюю цепочку.

Вектор F`={f`i} имеет следующий вид:





1 …. |P|

1 …. |P|

1 …. |I|

F`=

М …. М

М …. М

f1 …. f |I|


Где М>


Теперь докажем, что оптимальные решения построенной ПЗР при обратном переходе к МЗР переходят в оптимальные. Для этого сначала покажем, что допустимые решения построенной ПЗР переходят в допустимые решения МЗР.


Несколько слов о трудоёмкости: ПЗР с применением данной сводимости строится за время О((2|P|+|I|)*(|J|+|P|+)), то есть с полиномиальной трудоёмкостью.


5.2 Пример


Пусть в МЗР имеется 4 завода, 4 потребителя, 4 цепи. Пусть также в первую цепочку входят первое и второе предприятия, во вторую цепочку входят второе и третье предприятия, в третью цепочку входят третье и четвёртое предприятия, в четвёртую – четвёртое и первое. То есть I=4, J=4, P=4, P1={1, 2}, P2={2, 3}, P3={3, 4}, P4={4, 1}.

Рассмотрим следующее допустимое решение:


, .


При переходе от МЗР к ПЗР получаем задачу, в которой матрица С`={с`ij} и вектор F`={f`i} выглядят таким образом:





С`={с`ij}:
















F`={f`i}:

d11 d12 d13 d14

d21 d22 d23 d24

d31 d32 d33 d34

d41 d42 d43 d44

0   

 0  

  0 

   0

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   




М

М

М

М

   

   

   

   

0   

 0  

  0 

   0

0 0  

   

   

   

   

 0 0 

   

   

   

   

  0 0

   

   

   

   

0   0




М

М

М

М

   

   

   

   

   

   

   

   

0   

 0  

  0 

   0

0   

 0  

  0 

   0

0   

 0  

  0 

   0

0   

 0  

  0 

   0




1

1

0

1


По построению сводимости, столбцы, содержащие бесконечность во «флаговой» строке, надо вычеркнуть. Таким образом получим задачу с такими данными:






С`={с`ij}:
















F={fi}:

d11 d12 d13 d14

d21 d22 d23 d24

d31 d32 d33 d34

d41 d42 d43 d44

0   

 0  

  0 

   0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 




М

М

М

М

   

   

   

   

0   

 0  

  0 

   0

0 0

 

 

 

 

0 0

 

 

 

 

0 0

 

 

 

 

0 0




М

М

М

М

   

   

   

   

   

   

   

   

0 

 0

 

 

 

0 

 0

 

 

 

0 

 0

0 

 

 

 0




1

1

0

1


Постоим матрицу переменных X={xij} и вектор Y={yi}, используя данные МЗР, матрицу С`={с`ij} и вектор F`={f`i}, так чтобы это не противоречило допустимости решения ПЗР.





X={xij}:
















Y={yi}:

1 1 1 0

0 0 0 0

0 0 0 0

0 0 0 1

1 0 0 0

0 0 0 0

0 0 0 0

0 0 0 1

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0




1

0

0

1

0 0 0 0

0 0 0 0

0 0 0 0

0 0 0 0

0 0 0 0

0 1 0 0

0 0 1 0

0 0 0 0

0 0

0 0

0 0

0 0

0 0

1 1

0 0

0 0

0 0

0 0

1 1

0 0

0 0

0 0

0 0

0 0




0

1

1

0

0 0 0 0

0 0 0 0

0 0 0 0

0 0 0 0

0 0 0 0

0 0 0 0

0 0 0 0

0 0 0 0

1 0

0 1

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

1 0

0 0

0 0

0 1




1

1

0

1


Отметим, что если в i-й строке матрицы X={xij} стоит хотя бы одна единица, то на i-м месте вектора Y={yi} стоит единица. Наоборот, если i-я строка матрицы X={xij} состоит из нулей, то на i-м месте вектора Y={yi} стоит нуль.

Матрица переменных X={xij} и вектор Y={yi} также имеют блочную структуру.

Обозначим каждый блок матрицы и вектора цифрой для более наглядного объяснения построения:





X={xij}:
















Y={yi}:


I1.


I2.


I3.


I4.


I5.


I6.





I.


II1.


II2.


II3.


II4.


II5.


II6.





II.


III1.


III2.


III3.


III4.


III5.


III6.





III.


Сразу отметим, что построение блоков I3, I4, I5, I6, II1, III1 и III2 очевидно. Рассмотрим структуру остальных блоков. Решение прежде всего должно быть допустимым, т.е. должны выполняться ограничения ПЗР (2.2.2)-(2.2.5).


Блок I1 соответствует матрице переменных МЗР.

Блок I2 говорит о том, что в МЗР открыты только первая и четвёртая цепочки, поэтому, на позициях (1, 1) и (4, 4) в этом блоке стоят единицы.

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

В блоках II4 и II5 во второй и третьей строке соответственно можно ставить единицы.

Ограничение (2.2.2) ПЗР говорит о том, что в каждом столбце матрицы X={xij} должна стоять ровно одна единица. Следовательно, блоки III4 и III5 состоят из нулей.

Так как блок III вектора Y={yi} ПЗР соответствует вектору МЗР, то в первой, второй и четвёртой строках блоков III3 и III6 должны стоять единицы. По построению, в блоке III3 в первой и второй строках стоят единицы, в блоке III6 они стоят в первой и четвёртой строках.

Используя ограничение (2.2.2) ПЗР, блоки II3 и II6 содержат нули.


^ 5.3 Доказательство корректности сводимости


Определение: будем говорить, что для матрицы X={xij} ПЗР выполнено свойство комплиментарности, если в блоке I2 единицы стоят только на местах (i,i), и это означает, что продукция i-й цепочки производится, а в блоке II2 единицы стоят только на местах (j,j) и это означает, что продукция j-й цепочки не выпускается.


Определение: Решение ПЗР имеет правильную структуру, если выполнено свойство комплиментарности и количество величин L в целевой функции не превышает множества Р цепочек МЗР.


Лемма 1. Решение правильной структуры ПЗР за полиномиальное время может быть преобразовано в допустимое решение МЗР.

Доказательство:

Для доказательства леммы достаточно проверить, что решение правильной структуры ПЗР при переходе в МЗР удовлетворяет ограничениям МЗР.

Ограничения МЗР (1.2.2) выполнены в силу ограничения ПЗР (2.2.2).

Проверим выполнение второй группы ограничений МЗР (1.2.3). В матрице X={xij} в блоке III|J|+|P|+i, соответствующем i-й цепи, в строке i ставим единицу, если y2|P|+i=1. Это с учётом ограничения (1.2.2) означает, что в блоке II|J|+|P|+i в строке i стоит нуль. Здесь i=1, …, . В блоке II2 единицы стоят в элементах (j, j), если продукция j-й цепочки не выпускается. С учётом этого, в блоках II|J|+|P|+i и III|J|+|P|+i при i=1, …, |P| можно назначить единицы в элементах, которые не повлекут появление новых штрафов. Преследуя эту же цель, в блоке I1 в строке i назначим единицу, если она есть в i-й строке блока I2. Благодаря построенному таким образом решению, вторая группа ограничений МЗР (1.2.3) выполнена.

Рассмотрим величину изменения значения целевой функции ПЗР при переходе от ПЗР к МЗР.

Лемма 2. Пусть fПЗР – значение целевой функции ПЗР, fМЗР – значение целевой функции МЗР и пусть X={xij} и Y={yi} некоторое решение правильной структуры ПЗР, и - допустимое решение МЗР, построенное по принципу, описанному в Лемме 1. Тогда fПЗР = fМЗР+М*|P| , где M>, Р – множество цепочек МЗР.

Доказательство:

При подстановке X={xij} и Y={yi} в целевую функцию ПЗР получим следующее:




Лемма 3. Оптимальное решение ПЗР имеет правильную структуру.

Доказательство проведём от противного. Предположим, что оптимальное решение ПЗР не правильной структуры, т.е. не выполнено свойство комплиментарности матрицы X={xij}. Но если решение не имеет правильную структуру, то значение целевых функций ПЗР и МЗР будет отличаться никак не меньше, чем на величину М(|P|+1), что противоречит наличию оптимального решения. Следовательно, оптимальное решение ПЗР имеет правильную структуру.


Утверждение: Оптимальное решение ПЗР с использованием сводимости, описанной в Лемме 1, переходит в оптимальное решение МЗР.

Доказательство проведём от противного. Пусть - значение целевой функции оптимального решения X*={x*ij} и Y*={y*i} ПЗР. В МЗР этому решению соответствует значение целевой функции , это допустимое решение и МЗР, построенное по принципу, описанному в Лемме 1.

Пусть - значение целевой функции оптимального решения и в МЗР и < . По этому оптимальному решению МЗР с использованием исследуемой сводимости, построим допустимое решение ПЗР X={xij} и Y={yi}.

Пользуясь Леммой 2, можно записать следующее: = +М*|P| и = +M*|P|. Воспользуемся тем, что - значение целевой функции оптимального решения МЗР и < . Тогда <. Противоречие. Следовательно, оптимальное решение ПЗР переходит в оптимальное решение МЗР.


^ 6. СВОДИМОСТЬ ПРОСТЕЙШЕЙ ЗАДАЧИ РАЗМЕЩЕНИЯ К ЗАДАЧЕ НАИМЕНЬШЕГО ПОКРЫТИЯ


6.1 Сводимость простейшей задачи размещения к задаче разбиения множества


Рассмотрим вид ЗРМ, полученной после преобразования Т1 [11]. Корректность этой сводимости обоснованна в [11].

Т1 : Сводимость ПЗР к ЗРМ

Не ограничивая общности (и не меняя т.о. оптимальное решение) можно требовать, чтобы в ПЗР все xij=0 или xij=1 . Тогда, все rij также будут равняться либо 0, либо 1.


(6.1.1)

(6.1.2)

(6.1.3)

(6.1.4)


Здесь .

Сводимость ПЗР к ЗРМ осуществляется с помощью преобразования Т1 (6.1.1) - (6.1.4). Целевая функция в ЗР имеет вид (4.1.1), а у задачи, полученной после преобразования Т1 – (6.1.1). С помощью преобразования Т1 осуществляется переход от ПЗР к ЗР, следовательно нам надо чтобы



. (6.1.5)


Ограничения ЗР, полученные с помощью преобразования Т1 из ПЗР имеют вид (6.1.2) – (6.1.4), что соответствует ограничениям ЗР (4.1.2) – (4.1.3).

Таким образом, ЗР, полученная после преобразования Т1, выглядит так:


(6.1.6)

(6.1.7)

(6.1.8)

(6.1.9)


^ 6.2. Сводимость задачи разбиения множества к задаче наименьшего покрытия.


Рассмотрим вид ЗНПМ, полученной после преобразования Т4 [11]. Корректность этой сводимости обоснованна в [11].

Т4 : Сводимость ЗРМ к ЗНПМ


(6.2.1)

(6.2.2)


Здесь, - достаточно большая константа.

Сводимость ЗРМ к ЗНПМ осуществляется с помощью преобразования Т4 (6.2.1) – (6.2.2). Преобразуем целевую функцию ЗРМ (6.2.1) :


, (6.2.3)


далее, используя (6.1.5), и тот факт, что , получим, что целевая функция после преобразования Т4 будет иметь вид :


. (6.2.4)


Ограничения ЗНПМ, полученной после преобразования Т4, с переходом от равенств к неравенствам получают вид:


(6.2.5)

(6.2.6)


Проведём преобразования целевой функции ЗНПМ (6.2.4), полученной после преобразования Т4, которые сделают более наглядным переход от ЗРМ к ЗНПМ. Выразим zi, aij через новые переменные xij, rij и . Для этого используем ограничения ЗРМ, полученные после преобразования Т1 (6.1.2) – (6.1.4) и ограничения ЗРМ (4.1.2) – (4.1.3). Используя преобразование Т1, из ПЗР строится ЗРМ, следовательно должно выполняться равенство:


. (6.2.7)


Приравняем целевую функцию ЗНПМ (3.2.1) к целевой функции ЗНПМ, полученной после преобразования Т4 (6.2.4). Получим следующее:


(6.2.8)


Так как выполнено равенство (6.2.7), то




.


Итак, ЗНПМ после всех приведённых выше преобразований выглядит следующим образом:


(6.2.9)

(6.2.10)

(6.2.11)

(6.2.12)


где и xij, , fi, cij – это переменные и коэффициенты из ПЗР (2.2.1) – (2.2.5).


Число переменных в построенной ЗНПМ равно 2mn+m, а число ограничений mn+n, где m – число возможных пунктов производства, n – число пунктов потребления.


ЗНПМ с применением этой сводимости строится за время O((2*n*m+m)*(m*n+m)), то есть с полиномиальной трудоёмкостью.


^ 6.3. Обратный переход от задачи наименьшего покрытия к простейшей задаче размещения


При этом переходе интерес представляет изменение значения оптимального решения ПЗР. Используем тривиальный факт:


Утверждение. Пусть задача А сводится к задаче В, а задача В сводится к задаче С и пусть xc – оптимум задачи С тогда xb=g(xc) – оптимум задачи В, пусть yb – оптимум задачи B тогда ya=h(yb) – оптимум задачи A, и из всего этого следует, что если zc – оптимум задачи С, то za=h(g(zc)) – оптимум задачи A.

Утверждение. Пусть - оптимальное значение целевой функции ЗНПМ, - оптимальное значение целевой функции ПЗР,

тогда (6.3.1)

Доказательство:


, (6.3.2)


т.к. , то


. (6.3.3)


Используя (6.2.7), получим:


. (6.3.4)


Далее, рассмотрим, чему равна сумма . Это сумма всех ограничений ЗНПМ, полученной после преобразования Т4. Эти ограничения соответствуют ограничениям ЗРМ (4.1.2) – (4.1.3). Заметим, что эти ограничения выполнены для оптимального решения Х*={x*ij}, Y*={y*i} и R*={r*ij} ЗНПМ. Х*={x*ij} входит в ограничения ЗНПМ, полученной после преобразования Т4 два раза, т.к. xij входит в два ограничения ЗРМ ; Y*={y*i} входит в ограничения ЗНПМ, полученной после преобразования Т4 n раз; R*={r*ij} входит в ограничения ЗНПМ, полученной после преобразования Т4 один раз.

Поэтому


.


Ввиду (6.1.2) и (6.1.2), можно записать:




.


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

,

где m – число возможных пунктов производства, n – число пунктов потребления.


Таким образом, зная оптимальное значение целевой функции ЗНПМ можно быстро найти оптимальное значение целевой функции ПЗР, которое будет отличаться от оптимального значения целевой функции ЗНПМ на величину Lmn.


^ 7. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ СВОДИМОСТЕЙ И ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ


Программа сводимости ПЗР к ЗНПМ. была написана с использованием среды программирования Delphi 6. Кроме того были запрограммированы приближённый алгоритм Dorit S. Hochbaum [2, 10] и жадный алгоритм V.Chvatal [9]. Так же для решения ЗНПМ использовались генетический алгоритм [6] и пакет OPL-Studio.


На вход запрограммированных приближённого алгоритма Dorit S. Hochbaum и жадного алгоритма V.Chvatal подаётся файл ПЗР имя_файла.txt в формате OR-Library [8]. В этом файле находится следующая информация:

  • Число возможных пунктов производства некоторого однородного продукта (m);

  • Совокупность пунктов потребления этого продукта (n);

  • Столбец стоимостей доставки средства i (fi), i = 1 m;

  • Матрица стоимостей общей поставки для потребителя j продукции i (cij), i = 1 m, j = 1 n.


Так как жадный алгоритм V.Chvatal решает ЗНПМ, а на вход подаётся ПЗР, то первым делом, после считывания данных из файла, по ПЗР строится ЗНПМ, а затем уже к ней применяется жадный алгоритм V.Chvatal.


На выходе программ два файла.

Первый файл имя_файла.znp с построенной ЗНПМ в формате библиотеки OR-library, в котором содержатся:

  • Размерности задачи;

  • Коэффициенты целевой функции;

  • Матрица ограничений.

Во втором файле имя_файла.res:

  • Значение целевой функции для решения, полученного «жадным алгоритмом» V.Chvatal;

  • Вектор открытых предприятий;

  • Вектор поставок.


Эксперименты проводились с задачами трёх типов:

  1. Задачи небольших размерностей с целочисленными данными,

  2. Задачи библиотеки OR-library с нецелочисленными данными,

  3. Задачи библиотеки Ю.А. Кочетова [4] с целочисленными данными.


Интересные результаты были получены на задачах небольших размерностей (приложение 1).

К сожалению, OPL-Studio не всегда находит оптимальное решение ЗНПМ после сводимости и, следовательно, после сводимости ЗНПМ к ПЗР получаем допустимое решение, а не оптимальное. После получения таких неожиданных результатов возникло сомнение о правильности сводимости, так как при помощи пакета OPL-Studio находится оптимальное решение тестируемых задач. Сомнения были развеяны после проведения следующего эксперимента. При решении исходной ПЗР с помощью этого пакета, находим оптимальное решение X*={}, Y*={}. Далее, в стандартный набор ограничений тестируемой ЗНПМ добавляем ограничения вида . После этого, находим решение ЗНПМ. При переходе к решению ПЗР при помощи (6.3.1), получаем оптимальное решение. С помощью этого эксперимента был сделан вывод, что пакет OPL-Studio не на всех тестируемых задачах данного типа корректно работает.

Генетический алгоритм тестировался с вероятностями мутации равными 0,1 и 0,8. С помощью этой программы находим решение ЗНПМ. При переходе к ПЗР с использованием (6.3.1) можно сделать вывод, что найденное решение ПЗР является допустимым.

Приближённый алгоритм Dorit S. Hochbaum решает ПЗР, результатом работы этого алгоритма является допустимое решение ПЗР.

Жадный алгоритм V.Chvatal решает ЗНПМ. При переходе к ПЗР с использованием (6.3.1) можно сделать вывод, что этому алгоритму трудно найти даже допустимое решение.

Для наглядности полученных результатов построен график (приложение 2).


Задачи библиотеки OR-library (приложение 3) оказались легко решаемыми для большинства используемых программ.

С помощью пакета OPL-Studio на тестируемых ЗНПМ размерностью 850 x 1616 и 1300 x 2525 найдено решение, которое после сводимости к ПЗР, с использованием (6.3.1) даёт оптимальное решение ПЗР. Но ЗНПМ размерностью 5050 x 2550 не были решены, так как размерность этих задач превышает допустимые размерности задач, которые можно решить при помощи пакета OPL-Studio.

Генетический алгоритм с вероятностью мутации равной 0,8 находит решение ЗНПМ. При переходе к ПЗР с использованием (6.3.1) можно сделать вывод, что найденное решение ПЗР является допустимым.

Генетический алгоритм с вероятностью мутации равной 0,1 находит решение ЗНПМ, которое при переходе к ПЗР с использованием равенства (6.3.1), допустимым не является.

К сожалению, с помощью генетического алгоритма не удалось просчитать ЗНПМ размерностью 5050 х 2550, так как столкнулись с проблемой, аналогичной той, которая возникла на ЗНПМ той же размерности при попытке просчитать их с помощью пакета OPL-Studio.

^ Приближённый алгоритм Dorit S. Hochbaum решил все тестируемые ПЗР рассматриваемого типа. Результатом работы этого алгоритма является допустимое решение ПЗР.

^ Жадный алгоритм V.Chvatal решает ЗНПМ. При переходе к ПЗР с использованием (6.3.1) можно сделать вывод, что этому алгоритму трудно найти даже допустимое решение.

Для наглядности полученных результатов построен график (приложение 4).


Задачи библиотеки Ю.А. Кочетова имеют большую размерность, поэтому они оказались очень трудными для решения после сведения. Все используемые алгоритмы либо не находили допустимого решения, либо находили, но при этом давали большую погрешность.


ЛИТЕРАТУРА


[1] Агеев А.А. «О сложности задач минимизации полиномов от булевых переменных».- В кн. Экстремальные задачи исследования операций (Управляемые системы). Новосибирск, 1983, вып. 23, с. 3-11.

[2] Андрющенко А.А. «Реализация одной сводимости простейшей задачи размещения к задаче наименьшего покрытия». Отчёт по практической работе, Омск, ОмГУ, 2002.

[3] Береснеев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации – Новосибирск.: Наука, 1978.

[4] Е.Н. Гончаров, Д.С. Иваненко, Ю.А. Кочетов, Н.А. Кочетова, М.Г. Пащёнко “Электронная библиотека. Дискретные задачи размещения” // Труды XII Байкальской международной конференции «Методы оптимизации и их приложения». – Иркутск.: ИС СО РАН, 2001 г. с. 132-137

[5] Гончаров Е.Н., Кочетов Ю.А. «Вероятностный поиск с запретами для дискретных задач безусловной оптимизации» В кн. Дискретный анализ и исследование операций. Новосибирск. Сер. 2, 2002,  Т. 9,  № 2, c. 13–30.

[6] А.В. Еремеев «Генетический алгоритм для задачи о покрытии»// Дискретный анализ и исследование операций. Сер. 2, 2000, Т. 7, №1, с. 47-60.

[7] А.В.Еремеев. Личная беседа.

[8] Beasley J.E. OR-library: distributing test problems by electronic mail // J.Oper.Res.Soc. 1990. V.41, N11. P.1069-1072.

[9] Chvatal V. A greedy heuristic for the set covering problem // Math. Oper. Res. 1979. V.4, N3. P.233-235.

[10] Hochbaum Dorit S. «Heuristic for the fixed cost median problem»//Mathematical Programming 1982 V.22 P. 148-162

[11] J. Krarub, P. M. Pruzan. The simple plant location problem: Survey and synthesis // European Journal of Operational Research, 1983. V.12, P.36-47.





Скачать 292,4 Kb.
оставить комментарий
Дата02.10.2011
Размер292,4 Kb.
ТипЗадача, Образовательные материалы
Добавить документ в свой блог или на сайт

отлично
  1
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх