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

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




Скачати 398.6 Kb.
Назва5. Целочисленное программирование
Сторінка1/3
Дата20.09.2012
Розмір398.6 Kb.
ТипЗадача
  1   2   3

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


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

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


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

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

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

(1 - если предмет Пі перевозится; 0 - если предмет Пі не перевозится).

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

.

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

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

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

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


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

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

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

-x1+3x26;

7x1+x235;

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

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


х2


4 N




3




2




1




0 1 2 3 4 5 6 х1

-1 L=0


Рис. 5.1


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

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

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

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

,

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

12x1+9x244,

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

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

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

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

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

найти max L=7x1+9x2, при ограничениях -x1+3x26; 7x1+x235; x10; x20.

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

БП

х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:

БП

х1

х2

х3

х4

s1

Реш.




х2

0

1

7/22

1/22

0

7/2




х1

1

0

-1/22

3/22

0

9/2




s1

0

0

-7/22



1



вед. строка

L

0

0





0

-63




вед.

столбец

Данное решение является оптимальным (коэффициенты в 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:


БП

х1

х2

х3

х4

s1

s2

Реш.




х2

0

1

0

0

1

0

3




х1

1

0

0

1/7

-1/7

0

32/7




x3

0

0

1

1/7

-22/7

0

11/7




s2

0

0

0

-1/7

-6/7

1

-4/7

вед. строка

L

0

0

0

-1

-8

0

-59




вед.

столбец

Исключаемой переменной для этой таблицы в соответствии с условием допустимости является 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:

х127.

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

  1   2   3

Схожі:

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


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