5. Целочисленное программирование icon

5. Целочисленное программирование




Скачати 313.54 Kb.
Назва5. Целочисленное программирование
Дата06.09.2012
Розмір313.54 Kb.
ТипЗадача

5. Целочисленное программирование


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

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


^ 5.1. Формулировка задачи линейного целочисленного программирования и ее математическая модель

Рассмотрим один пример такой задачи. Пусть имеет ряд неделимых предметов (ценностей) П1, П2, ..., Пn, которые необходимо увезти из небезопасного района. Известные стоимости этих предметов: с1, с2, ..., сn и их веса q1, q2, ..., qn. Количество и вид предметов, которые мы можем увезти, лимитируется грузоподъемностью Q перевозочных средств. Требуется из всего набора предметов выбрать наиболее ценный набор (с максимальной суммарной стоимостью предметов), вес которого укладывается в Q.

Введем в рассмотрение переменные xi, i=1;n, определяемые условием



Очевидно, что целевая функция, которую необходимо максимизировать, имеет вид

.

Условие ограничения грузоподъемности запишется в виде неравенства:

q1x1+q2x2+...+qnxnQ.

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

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


^ 5.2. Решение задачи линейного полностью целочисленного программирования методом отсекающих плоскостей

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

максимизировать L=7x1+9x2 при ограничениях:



x1 и x2 - неотрицательные целые.

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



Рис. 5.1.


Оптимальное значение целевых функции hmax=63 достигается в точке N с дробными координатами х1=9/2; х2=7/2.

В основе метода отсекающих плоскостей лежит преобразование области решений задачи с ослабленными ограничениями в выпуклый многогранник, экстремальная точка которого является оптимальным решением исходной целочисленной задачи. При этом все допустимые целочисленные решения исходной задачи должны лежать внутри или на границе построенного многогранника. На рис.5.1. показано, как введение двух дополнительных ограничений позволяет получить новую точку с координатами х1=4; х2=3, являющуюся оптимальным решением сформулированной выше задачи целочисленного программирования. Дополнительные ограничения введены таким образом, чтобы область, отсеченная от множества допустимых решений ослабленной задачи, не содержит точек с целочисленными координатами, а в новой области допустимых значений, вершины, соприкасание с отсеченной областью, имеют целочисленные координаты (отсеченная область на рис 5.1. заштрихована).

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

Например, ограничение

,

необходимо записать в виде

,

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

На первом шаге решения задачи целочисленного программирования решается задача (например, симплекс-методом) с ослабленными ограничениями, не содержащими условия целочиcленности переменных. Если полученное решение оказывается целочисленным, то оно является также решением исходной задачи. В противном случае переходят ко второму шагу.

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

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

С ослабленными ограничениями (без наложения условия целочисленности переменных) эта задача формулируется следующим образом:



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

БП

х1

х2

х3

х4

Реш. bi

x2

0

1

7/22

1/22

7/2

x1

1

0

-(1/22)

3/22

9/2

L

0

0





-63

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

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

Представим, все нецелочисленные значения базисных переменных bi в виде

bi=[bi]+fi. (5.1.)

где [bi] - означает округление до целого наименьшего числа, а fi=bi-[bi].

В качестве примера в приведем следующую таблицу


bi









-1

[bi]

3

0

-3

-1

-1

fi









0


Очевидно, что 0fi<1.

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

Для рассматриваемого примера

и следовательно,

и .

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

Уравнение отсекающей плоскости получается следующим образом. Базисная переменная xi производящей строки выражается через небазисные переменные:

(5.2.)

где ij - соответствующие коэффициенты і-й строки оптимальной симплекс-таблицы.

Если взять в рассматриваемом примере в качестве производящей строки строку, соответствующую базисной переменной x2, получим



Используя соотношение (5.1.), перепишем выражение (5.2.) в виде

(5.3.)

где .

Поскольку все переменные хі і=1, n должны принимать целые значения, левая часть выражения (5.3.) должны быть целочисленной, откуда следует, что и правая часть этого выражения должна принимать целые значения.

Далее, так как fij0 и xj0 для всех i и j, то

.

И, следовательно, выполняется неравенство

. (5.4.)

Поскольку fi1, то и , но так левая часть должна принимать целые значения, то необходимое условие ее целочисленности имеет вид

.

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

. (5.5.)

где sk - неотрицательная дополнительная переменная, которая должна принимать целые значения.

Итак, отсечение Гомори для полностью целочисленной задачи задается уравнением

. (5.6.)

Для рассматриваемого примера, получаем

.

Составляем новую симплекс-таблицу, вводя новую базисную переменную s1:



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

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

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

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

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

Для рассматриваемой задачи использование двойственного симплекс-метода приводит к таблице

БП

х1

х2

х3

х4

s1

Реш.

х2

0

1

0

0

1

3

х1

1

0

0

1/7

-1/7

32/7

s1

0

0

1

1/7

-22/7

11/7

L

0

0

0

-1

-8

-59


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

Производящая строка , соответствующая базисной переменной х1, дает следующее уравнение

.

Тогда отсечение Гомори определяется уравнением с новой неизвестной s2:

.

Составляем новую симплекс таблицу, вводя новую базисную переменную s2:




Исключаемой переменной для этой таблицы в соответствии с условием допустимости является s2, вводимой в соответствии с условием оптимальности - х4.

В результате использования двойственного симплекс-метода получаем новую таблицу



БП

х1

х2

х3

х4

s1

s2

Реш.

х2

0

1

0

0

1

0

3

х1

1

0

0

0

-1

1

4

x3

0

0

1

0

-4

1

1

х4

0

0

0

1

6

-7

4

L

0

0

0

0

-2

-7

-55


Полученная таблица дает оптимальное целочисленное решение исходной задачи х1=4; х2=3; L=55.

Отметим, что общие число отсекающих ограничений не может превышать количества переменных исходной задачи, а именно (m+n).

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

,

записанное в переменных х1 и х2, после соответствующей замены принимает следующий вид:

или s1-x2=3.

Это уравнение эквивалентно неравенству х23. Аналогичным образом второе отсечение

.

порождает эквивалентное ограничение в переменных х1 и х2:

.

На рис. 5.1. показано, как введение этих двух ограничений позволяет получить новую оптимальную точку с координатами (4,3) в которой достигается оптимум исходной целочисленной задачи.


^ 5.3. Решение частично целочисленных задач

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

В данной задаче нужно строить отсечения другого типа, хотя общая идея решения частично целочисленных задач сохраняется.

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

.

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

, (5.7.)

. (5.8.)

Пусть I+ - множество значений j, для которых ;

I- - множество значений j, для которых .

Из формул (5.7.) и (5.8.) получаем

, (5.9.)

. (5.10.)

Так как соотношение (5.7.) и (5.8.), а следовательно, (5.9.) и (5.10.) не могут выполняться одновременно, имеется возможность объединить (5.9.) и (5.10.) в одно ограничение вида

, (5.11.)

где se0 есть неотрицательная дополнительная переменная.

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

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

Из производящей строки соответствующей х1, запишем соотношение

,

откуда I-={3}; I+={4}; f1=.

В соответствии с выражением (5.11.) соответствующие ограничение Гомори для частично целочисленной задачи принимает вид



или

.

Добавим это ограничение в симплекс-таблицу:



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

БП

х1

х2

х3

х4

s1

Реш.

х2

0

1

10/33

0

1/3

10/3

х1

1

0

-1/11

0

1

4

х4

0

0

1/3

1

-22/3

11/3

L

0

0

-23/11

0

-10

-58


Оптимальное решение достигается в точке с координатами х1=4; ;

max L=58.

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

Можно использовать уравнение более эффективного отсечения [1]:

,

где




Полностью целочисленную задачу также можно решить путем введения отсечений Гомори для частично целочисленной задачи.

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


ТЕСТЫ

(верно (В) или неверно (Н))

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

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

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

5.4. При построении отсечения Гомори для полностью целочисленной задачи на дополнительную переменную также накладывается условие целочисленности.

5.5. Отсечение может исключить некоторое допустимое целочисленное решение заведомо не являющиеся оптимальным.

5.6. Полностью целочисленную задачу можно решить путем введения отсечений Гомори для частично целочисленной задачи.

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

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

5.9. Условия допустимости и оптимальности двойственного симплекс-метода не отличаются от условий допустимости и оптимальности симплекс-метода.

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


ЗАДАЧИ


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

5.1.




5.2.




5.3.




5.4.



5.5.



5.6.



5.7.



5.8.

.

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

5.9.

БП

х1

х2

х3

х4

x5

Реш.

х3

5/11

9/11

0

0

1

7/11

х4

2/11

3/11

1

0

0

10/11

х5

16/11

-4/11

0

1

0

3/11

L

-3

-4

0

0

0

0


5.10.

БП

х1

х2

х3

х4

x5

Реш.

х3

0

0

1

-7/3

5/6

1/6

х1

1

0

0

-1/6

-2/3

1/2

х2

0

1

0

2/3

1/3

5/6

L

0

0

0

-7/6

-5/3

-67/6


5.11.

БП

х1

х2

х3

х4

x5

Реш.

х4

0

-2/7

-1

1

6/7

13/7

х1

1

8/7

2

0

-3/7

4/7

L

0

-(20/7)

3

0

-(10/7)

39/7


5.12.

БП

х1

х2

х3

х4

x5

Реш.

х2

6/5

1

0

0

1/5

1/5

х3

8/5

0

1

0

-13/5

7/5

х4

3/5

0

0

1

2/5

3/5

L

17/5

0

0

0

2/5

2/6


5.13.

БП

х1

х2

х3

х4

x5

Реш.

х3

-1

0

1

0

4

2

х2

-2/9

1

0

0

16/9

14/9

х1

15/9

0

0

1

-7/9

41/9

L

-16/9

0

0

0

-(115/9)

-50/9


5.14.

БП

х1

х2

х3

х4

x5

Реш.

х2

0

1

5/7

0

1/7

1/7

х4

0

0

13/7

1

-(20/7)

15/7

х1

1

0

-9/7

0

4/7

2/7

L

0

0

-3/7

0

-18/7

-12/7


5.15.

БП

х1

х2

х3

х4

x5

Реш.

х1

1

4/3

-17/3

0

0

1/3

х4

0

-7/6

1/6

1

0

5/6

х5

0

-1/3

8/3

0

1

2/3

L

0

1/3

46/3

0

0

2/3



5.16.

БП

х1

х2

х3

х4

x5

Реш.

х1

1

1/4

-3/4

7/2

0

7/4

х5

0

1/2

5/2

-(1/2)

1

3/2

L

0

19/4

47/4

9/4

0

37/4


5.17.

БП

х1

х2

х3

х4

x5

Реш.

х5

0

0

5/2

7/3

1

1/2

х1

1

0

2

-(20/3)

0

2/3

х2

1/6

0

1

17/6

-1/3

0

L

0

0

13/3

2/3

0

-1


5.18.

БП

х1

х2

х3

х4

x5

Реш.

х1

1

1/3

0

-2/3

0

1/3

х3

2/3

0

5/3

1

7/3

0

х5

4/3

0

13/3

0

8/3

1

L

0

-2

0

-7/3

0

-1




5.19.



5.20.

.

5.21.



5.22.




5.23.



5.24.



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


Проект

Распределение капиталовложений

Прибыль от



год 1

год 2

год 3

проекта

1

5+i

1+i

8+i

20+i

2

4+i

7+i

10+i

40+i

3

3+i

9+i

2+i

20+i

4

7+i

4+i

1+i

15+i

5

8+i

6+i

10+i

30+i

Максимально возможный объем капиталовложений


25+i


25+i


25+i


25+i


i - личный номер каждого студента.

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





Схожі:

5. Целочисленное программирование icon5. Целочисленное программирование
Целочисленное программирование ориентировано на решение задач математического программирования, в которых все или некоторые переменные...
5. Целочисленное программирование icon5. Целочисленное программирование
Целочисленные программирование ориентировано на решение задач математического программирования, в которых все или некоторые переменные...
5. Целочисленное программирование icon5. Целочисленное программирование
Целочисленные программирование ориентировано на решение задач математического программирования, в которых все или некоторые переменные...
5. Целочисленное программирование icon5. Целочисленное программирование
Целочисленные программирование ориентировано на решение задач математического программирования, в которых все или некоторые переменные...
5. Целочисленное программирование icon6. Динамическое программирование
Динамическое программирование представляет собой математический аппарат, разработанный с целью повышения эффективности при решении...
5. Целочисленное программирование icon6. Динамическое программирование
Динамическое программирование представляет собой математический аппарат, разработанный с целью повышения эффективности при решении...
5. Целочисленное программирование icon6. Динамическое программирование
Динамическое программирование представляет собой математический аппарат, разработанный с целью повышения эффективности при решении...
5. Целочисленное программирование icon6. Динамическое программирование
Динамическое программирование представляет собой математический аппарат, разработанный с целью повышения эффективности при решении...
5. Целочисленное программирование icon6. Динамическое программирование
Динамическое программирование представляет собой математический аппарат, разработанный с целью повышения эффективности при решении...
5. Целочисленное программирование icon6. Динамическое программирование
Динамическое программирование представляет собой математический аппарат, разработанный с целью повышения эффективности при решении...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи