Студопедия — Применение метода ветвей и границ к решению задач линейного целочисленного программирования
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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






 

Рассмотрим задачу ЦЛП в матричной форме записи. Обозначим ОДП этой задачи D, а ОДП ЗЛП без ограничений целочисленности - G. Точно так же обозначим соответствующие системы ограничений, а сами задачи будем называть D-задача и G-задача.

max CX

D представляет собой часть G. G будем рассматривать в качестве исходного множества (рис.19).

 

Решим вначале G-задачу. Пусть при решении этой задачи получен оптимальный план ХG. Значение целевой функции на нем zG - оптимум G-задачи - будем использовать в качестве границы . В самом деле,

zG СХ Х G;

zG СХ Х D.

Если план ХG целочисленный, то решение задачи окончено. Таким образом, мы ответили на первый и третий вопросы, конкретизирующие метод ветвей и границ.

Предположим, что хотя бы одна компонента ХG не целочисленна: хGi Z.

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

Обозначим целую часть числа хGiGi].

Конкретизируем второй вопрос.

Разобьем D на D1 и D2 следующим образом:

D1={X D: хi Gi]};

D2={X D: хi Gi] + 1}

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

Разбивая D, мы одновременно разбиваем и G (рис.20).

Это разбиение обладает следующими свойствами:

G1 G2 G (объединение этих множеств содержится в G, но не равно ему);

D1 D2 = D (в устраненном «коридоре» нет ни одной точки с целочисленными координатами).

 

 

При этом устраняется и план ХG.

Далее решение задачи продолжается для каждого из подмножеств G1 и G2.

Сходимость алгоритма основана на том, что в ограниченной ОДП множество дискретных точек конечно.

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

 

3.5. Пример решения задачи целочисленного линейного программирования методом ветвей и границ

 

Требуется решить следующую задачу:

max 2х1 + х2

1 + 2х2 10

1 + 8х2 13

х1,2 0

х1,2 Z

Вначале решим эту задачу графически без ограничений целочисленности. Решение может быть найдено как симплекс-методом, так и графически. Найдем его графически (рис.21).

 

 

 

Координаты точки оптимума можно найти, решив систему уравнений:

1 + 2х2 = 10 х1=27/17

1 + 8х2 = 13 х2=35/34

ХG = (27/17;35/34), zG=143/34.

Начнем строить дерево, первая вершина которого будет соответствовать всей ОДП нецелочисленной задачи (G), а ее оценка будет равна zG (рис.22).

 

 


Полученный план не является целочисленным, поэтому возьмем его произвольную нецелочисленную компоненту, например, первую (х1 Z; [х1] = [27/17] = 1) и разобьем ОДП на две части следующим образом:

G1 = {X G: х1 1};

G2 = {X G: х1 2}.

Изобразим это графически (рис.23).

 

 

 

 

 


Из рис.6 видно, что G2 представляет собой одну точку ХG2=(2;0), следовательно, на этом множестве оптимум задачи равен 4 ( 2=4).

План ХG2 является целочисленным, следовательно, решение целочисленной задачи уже, возможно, найдено. Однако, следует еще найти оценку множества G1. Она может оказаться не менее 4 (но обязательно не более 143/34). Если это так, то нужно проверить, не является ли целочисленным решение задачи на G1. Если оно целое, то является решением задачи, а если нет, то процесс решения необходимо продолжить, разбивая G1.

На G1 точку оптимума можно найти, решив систему уравнений:

х1 = 1 х1=1

1 + 8х2 = 13 х2=5/4

ХG1 = (1; 5/4), zG1=13/4.

Оценка меньше 4, следовательно, решением задачи является Х*G2=(2;0),z*=4.

 

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

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

 

Вопросы и упражнения

 

1. Как ставится задача целочисленного линейного программирования?

2. Какие существуют подходы к решению такой задачи?

3. В чем заключается идея метода ветвей и границ?

4. Как применяется этот метод к задаче целочисленного линейного программирования?

5. Как применяется этот метод (в ППП QSB) к задачам с булевыми переменными?

6. Решить методом ветвей и границ (и проиллюстрировать решение построением дерева) задачу

max 3х1 + 2х2

1 + 5х2 35

1 + 4х2 36

х1,2 0

х1,2 Z

 

 







Дата добавления: 2015-08-27; просмотров: 522. Нарушение авторских прав; Мы поможем в написании вашей работы!



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

Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

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

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

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

Конституционно-правовые нормы, их особенности и виды Характеристика отрасли права немыслима без уяснения особенностей составляющих ее норм...

Толкование Конституции Российской Федерации: виды, способы, юридическое значение Толкование права – это специальный вид юридической деятельности по раскрытию смыслового содержания правовых норм, необходимый в процессе как законотворчества, так и реализации права...

ОСНОВНЫЕ ТИПЫ МОЗГА ПОЗВОНОЧНЫХ Ихтиопсидный тип мозга характерен для низших позвоночных - рыб и амфибий...

Принципы, критерии и методы оценки и аттестации персонала   Аттестация персонала является одной их важнейших функций управления персоналом...

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

Studopedia.info - Студопедия - 2014-2024 год . (0.011 сек.) русская версия | украинская версия